Re: [Xsb-development] Re: bug in the cut

[Michael K. <ki...@cs...>]

Hi Kostis,
Thanks for taking a look at it. Did you test your smaller program with
local scheduling? I am not convinced by Luis' arguments either, but I
"understand" them at a very high level.

The issue here is recursion through tabled predicates and through a cut,
which also exists in your program, even though buggy_cut/3 is not itself
tabled. The predicates t_buggy_cut/3 and buggy_cut/3 are in the same
strongly connected component and are mutually recursive through a
cut. Because of local scheduling, XSB tries to compute all answers. What
happens then with the cut is a dark area according to Luis.

I agree that leaving the semantics of recursion through tables and cuts
undefined would make for a very big hole in the tabled logic programming
paradigm.


	--michael  



> About two weeks ago, Michael reported a "bug in the cut" which can be
> summarized as follows:
>  > 
>  > Take a look at the clauses for buggy_cut/3 at the top.
>  > The 2nd & 3d clauses look like this:
>  > 
>  > buggy_cut(_h209,M,_h237) :-
>  >       var(M),
>  >       !,            %% THIS CUT IS THE PROBLEMATIC ONE
>  >       ....
>  > buggy_cut(_h209,M,_h237) :-
>  >       (var(M) ->
>  >          nl, writeln('......  ' = M),  nl
>  >       ; true
>  >       ),
>  >      ....
>  >
>  > Therefore, the writeln statement in the last clause should never be
>  > reached, but it is executed!
>  >
> 
> A (relatively complicated) program was submitted by Michael as a bug
> report.
> 
> Luis apparently looked into it and dismissed it as a non-bug writing:
>  >> 
>  >> buggy_cut/3 is a tabled predicate. So, yes, cut does not work as
>  >> expected with tabled predicates. Scheduling in tabling is not
>  >> guaranteed to look at clauses in a top-down (wrt the code)
>  >> fashion.
>  >> ... [SNIP] ...
>  >> I'm sorry, but I don't believe we intend to support such
>  >> uses of cut. 
> 
> I was on vacation and could not react or look into this earlier, but
> the above really puzzles me. Clauses are looked in a top-down fashion,
> aren't they? I was under the impression that cuts which do not cut
> over a tabled predicate are OK and the other ones (the "bad" ones) are
> caught by a runtime test. Isn't this the case anymore?
> 
> I would not so easily dismiss Mikael's program as an "illegal" one. I
> personally cannot see why it is illegal (Luis, can you please explain
> it to me?) and even if does contain an illegal cut, the question
> remains why XSB does not warn its users about it. I would classify
> this as a bug.
> 
> I've spent some time creating a program which is smaller that
> Michael's and trying to make some sense out of it. In my version,
> buggy_cut is not tabled. Below I include it in the hope that it can
> help track down what's happening.
> 
> Incidentally, XXX (which is CHAT-based) does not exhibit any anomalous
> behaviour on this program or on Michael's. Until we understand what's
> going on, this might be a fluke. I suspect however that it is not.
> 
> Cheers,
> Kostis.
> 
> %==================================================================
> 
> :- export test/0, t_buggy_cut/3.
> :- import sk_not/1 from tables.
> 
> test :- t_buggy_cut(_X,owl_equivalentProperty,_Y).
> 
> :- table t_buggy_cut/3.
> 
> t_buggy_cut(X,Y,Z) :- buggy_cut(X,Y,Z).
> 
> buggy_cut(X,M,Y) :-
>         derived_fd(X,M,Y).
> buggy_cut(X,M,Z) :-
>         var(M),
>         !,
>         candidate_object_ifd(_h295,_h309,X),
>         flora_funct_arity(M,_h309),
>         ifd(_h295,M,Z).	% this predicate fails.
> buggy_cut(X,M,Z) :-
> 	(var(M) ->
> 	    nl,
> 	    writeln('VAR AFTER var(M),! in prev clause ' = (X,M,Z)),
> 	    nl
> 	; true
> 	),
>         flora_funct_arity(M,FA),
>         sk_not(foo_fd(X,FA)),
> 	fail.
> 
> foo_fd(S,MethSign) :-
>     	flora_funct_arity(M,MethSign),
> 	derived_fd(S,M,_).
> 
> foo_ifd(S,MethSign) :-
> 	nonvar(MethSign),
> 	ifd(S,MethSign,_).
> 
> derived_fd(animals_hasFather,rdf_type,owl_FunctionalProperty).
> derived_fd(animals_Mark,animals_hasFather,animals_John).
> derived_fd(animals_Mark,animals_hasFather,animals_JohnSmith).
> derived_fd(Z,P,Y) :-
> 	t_buggy_cut(X,owl_sameAs,Z),
> 	t_buggy_cut(X,P,Y).
> derived_fd(X,owl_sameAs,Y) :-
> 	t_isa(P,owl_FunctionalProperty),
> 	t_buggy_cut(S,P,X),
> 	t_buggy_cut(S,P,Y).
> derived_fd(_,owl_sameAs,_) :-
> 	t_isa(_,owl_InverseFunctionalProperty).	% this call fails.
> 
> derived_isa(X,_C) :-
> %	writeln('Here 1'(X)),
> 	ifd(_,_,X).	% calls to this predicate fail
> derived_isa(X,C) :-
> 	t_buggy_cut(X,rdf_type,C).
> derived_isa(X,C) :-
> 	t_buggy_cut(X,P,_),
> 	t_buggy_cut(P,rdfs_domain,C).
> 
> derived_sub(C,rdfs_Resource) :-
> 	t_isa(C,rdfs_Class).
> 
> % This predicate fails.
> candidate_object_ifd(X,Y,Z) :-
>         var(Y),
>         t_isa(Z,X),
>         foo_ifd(X,Y).	% this call fails.
> 
> :- table t_sub/2.
> 
> t_sub(owl_FunctionalProperty,rdf_Property).
> t_sub(X,Y) :-
> 	derived_sub(X,Y).
> t_sub(X,Y) :-
> 	t_sub(X,Z),
> 	derived_sub(Z,Y).
> 
> :- table t_isa/2.
> % This predicate succeeds with only
> % t_isa(animals_hasFather,owl_FunctionalProperty).
> % t_isa(animals_hasFather,rdf_Property).
> 
> t_isa(X,Y) :-
>         derived_isa(X,Y).
> t_isa(_h209,_h223) :-
>         t_sub(_h249,_h223),
>         derived_isa(_h209,_h249).
> 
> % This predicate fails.
> ifd(X,Y,_) :-
>         var(Y),
> 	t_sub(X,W),
> 	foo_ifd(W,_).
> 
> flora_funct_arity(M,F/A) :-
> 	( var(M) ->
> 	   ( var(F) -> abort('BUG: Unbound call to flora_funct_arity/2')
>            ; true
> 	   )
> 	; true
>         ),
> 	functor(M,F,A).
> 
> 
> -------------------------------------------------------
> This SF.Net email sponsored by: Free pre-built ASP.NET sites including
> Data Reports, E-commerce, Portals, and Forums are available now.
> Download today and enter to win an XBOX or Visual Studio .NET.
> http://aspnet.click-url.com/go/psa00100006ave/direct;at.asp_061203_01/01
> _______________________________________________
> Xsb-development mailing list
> Xsb...@li...
> https://lists.sourceforge.net/lists/listinfo/xsb-development
>