Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!munnari.oz.au!lee From: lee@munnari.oz.au (Lee Naish) Newsgroups: comp.lang.prolog Subject: Re: non-sequential recursion Message-ID: <2687@munnari.oz.au> Date: 12 Nov 89 12:16:35 GMT References: <1593@aipna.ed.ac.uk> Sender: news@cs.mu.oz.au Reply-To: lee@munmurra.UUCP (Lee Naish) Distribution: comp Organization: Comp Sci, University of Melbourne Lines: 36 In article ted@nmsu.edu (Ted Dunning) writes: >prolog dialects such as sicstus and nu allow a goal to be frozen >pending the instantiation of a variable. this facility can be used to >implement a sort of instantaneous failure on a higher level at the >cost of handing the variable to be instantiated down to the >descendants. for example, > > >parent :- set_failure_point(X), first_child(X), write(didnt_backtrack),nl. >parent :- write(back_tracked), nl. > >first_child(X) :- second_child(X). > >second_child(X) :- write(deep), nl, cause_failure(X), write(not_here), nl. > > >set_failure_point(X) :- freeze(X,X=1). >cause_failure(2). The call to cause_failure binds X to 2, then the frozen goal X=1 is woken up and fails. However, the system does not immediately backtrack to where set_failure_point was called. When cause_failure is backtracked into it fails, undoing the binding of X and restoring the frozen goal. Backtracking then continues in the normal way. The need for intelligent backtracking can sometimes be avoided by reordering calls. Coroutining gives more flexibility in doing this. However, current implementations of coroutining are not a general solution to the intelligent backtracking problem. Several years ago I suggested a form of coroutining which behaved like a simple intelligent backtracking scheme (so simple it saves no extra information during forward execution). I thought of implementing it on top of MU-Prolog but never got around to it. It is described in "Heterogeneous SLD Resolution", JLP, 1:4, Dec 1984. lee