nigel@hfserver.hfnet.bt.co.uk (Nigel Cliffe) (06/08/89)
I have a problem with backtracking, and retracts that don't appear to
happen - here is a simplified example:
If I have a database with repeated facts in it and want to a) get just the
unique entries, and b) retract the contents of the database as I get those
entries then one way that ought to work is this:
:- dynamic foo/1.
foo(bar1).
foo(bar1).
foo(bar2).
write_unique_foos :-
foo(X),
write(X),nl,
retractall(foo(X)),
fail.
Now if the predicate "write_unique_foos" is called, then I get all three
values for foo written, not just the two unique ones as I would expect.
However if I trace the execution, and test the contents of the database at
various points from the debugger then "foo(bar1)" has disappeared after the
first call to "retractall".
Can anyone explain why this happens.
I know that I can get the result I want by using setof, and probably
hundreds of other methods as well, I'm just curious as to why things don't
behave as I would expect.
Just incase this is system dependent, I'm using Quintus 2.4 on a Sun3 running
Sun OS 3.5.
--
Nigel Cliffe -
British Telecom Research Labs, Martlesham Heath, Ipswich, IP5 7RE, UK
voice: +44 473 645275 fax: +44 473 637557 email: nigel@hfnet.bt.co.ukcdsm@doc.ic.ac.uk (Chris Moss) (06/09/89)
In article <575@hfserver.hfnet.bt.co.uk> nigel@hfserver.hfnet.bt.co.uk (Nigel Cliffe) writes: > >I have a problem with backtracking, and retracts that don't appear to >happen - here is a simplified example: ... >write_unique_foos :- > foo(X), > write(X),nl, > retractall(foo(X)), > fail. > >Now if the predicate "write_unique_foos" is called, then I get all three >values for foo written, not just the two unique ones as I would expect. >However if I trace the execution, and test the contents of the database at >various points from the debugger then "foo(bar1)" has disappeared after the >first call to "retractall". > >Can anyone explain why this happens. Under Quintus version 2 retracts take effect immediately for any new query started but they don't affect a query already started. This is quite a consistent behaviour, is good semantically and avoids various inconsistencies that would otherwise happen. Read Section 2.1 of the release notes for version 2.0 of Quintus. The situation is comparable to the classic readers/writers method of ensuring file consistency. If you have already started reading (i.e. activated a query) then the file (relation) stays the same, but any new readers (activations) get the new version. This behaviour was proposed for the Prolog standard but I gather some people are trying to revert to the naive method with all its inconsistencies. See the Lindholm/O'Keefe paper in the Melbourne LP conference. Chris Moss
sehr@uicsrd.csrd.uiuc.edu (David C. Sehr) (06/09/89)
The reason that your predicate prints all the clauses for foo is
given in the Quintus manual, in chapter 14, on page 145 (version 2.3).
It says:
Beginning with Release 2.0, the definition of an interpreted
procedure that is to be visible to a call is effectively frozen
when the call is made. A procedure always contains, as far as
a call to it is concerned, exactly the clauses it contained when
the call was made.
This is exactly what happens when you call foo ahead of the retractall,
and hence all clauses for foo are still live until the last one is tried.
The Quintus solution renders clearer a favorite example of mine.
Try they following on your other favorite Prolog system and see the
result.
a :- assertz(a), fail.
?- a.
In C-Prolog 1.4 this will fail, whereas adding the clause (a :- fail)
after the first will succeed. This is not at all a desirable situation
in my opinion, but is understandable in terms of the implementation of
choice points.
David
-----
David C. Sehr
Center for Supercomputing Research and Development
University of Illinois at Urbana-Champaign
305 Talbot Lab
104 South Wright Street
Urbana, IL 61801-2932
UUCP: {seismo,pur-ee,convex}!uiucdcs!uicsrd!sehr
ARPANET: sehr%uicsrd@a.cs.uiuc.edu
CSNET: sehr%uicsrd@uiuc.csnet
BITNET: sehr@uicsrd.csrd.uiuc.edu
-----
David C. Sehr
Center for Supercomputing Research and Development
University of Illinois at Urbana-Champaign
305 Talbot Lab
104 South Wright Street
Urbana, IL 61801-2932
UUCP: {seismo,pur-ee,convex}!uiucdcs!uicsrd!sehrpx@unl.fctunl.rccn.pt (Joaquim Baptista (pxQuim)) (06/10/89)
In article <575@hfserver.hfnet.bt.co.uk> nigel@hfserver.hfnet.bt.co.uk (Nigel Cliffe) writes: > > I have a problem with backtracking, and retracts that don't appear to > happen - here is a simplified example: > > If I have a database with repeated facts in it and want to a) get just the > unique entries, and b) retract the contents of the database as I get those > entries then one way that ought to work is this: > > :- dynamic foo/1. > foo(bar1). > foo(bar1). > foo(bar2). > > write_unique_foos :- > foo(X), > write(X),nl, > retractall(foo(X)), > fail. > > Now if the predicate "write_unique_foos" is called, then I get all three > values for foo written, not just the two unique ones as I would expect. > However if I trace the execution, and test the contents of the database at > various points from the debugger then "foo(bar1)" has disappeared after the > first call to "retractall". > > Can anyone explain why this happens. > > I know that I can get the result I want by using setof, and probably > hundreds of other methods as well, I'm just curious as to why things don't > behave as I would expect. > > Just incase this is system dependent, I'm using Quintus 2.4 on a Sun3 running > Sun OS 3.5. > This problem is a feature rather than a bug, and occurs because of the usual implementations for the prolog interpreters. When one calls one predicate, as you did in foo(X), a "frame" is pushed onto the stack. The actual formats of this frame differ, so I will have to simplify it a little. Anyway, this frame will have information about the first clause foo(bar1), and will know that, on failure, it should try the second foo(bar2). This "will know that" is just a pointer for the second clause. Now, when you retractall(foo(X)), both clauses will go away, but the pointer to the second stored in the frame will not. That is why your program, in backtracking, will still find the second clause. Note that if you had... foo(bar1) foo(bar2) foo(bar1) ...then your program probabily would run as you expected. Variations on this problem also arise with asserta and assertz, as in: /* this will write 1 and fail */ a(1). exec1:- a(X), write(X), asserta(a(X)), fail. /* this will loop forever, exhausting your heap space, writing 1211111111... */ b(1). b(2). exec2:- b(X), write(X), assertz(b(X)), fail. /* this will do one of the above, depending on your system. Tail recursion optimization will make it do as exec1; else it will do as exec2. */ c(1). exec3:- c(X), write(X), assertz(c(X)), fail. One way to solve your problem is not to depend on backtracking, as in: :- dynamic foo/1. /* I've never seen one of this, but I guess what it does. */ foo(bar1). foo(bar2). foo(bar3). write_unique_foos :- foo(X), write(X), nl, retractall(foo(X)), write_unique_foos. This works in all the interpreters and compilers I know of (more or less dinamic foo/1 :-). Hope this enlightened you. Feel free to write. -- -------- Joaquim Manuel Soares Baptista | BITNET/Internet: px@fctunl.rccn.pt Centro de Inteligencia Artificial | UUCP: px@unl.uucp Uninova | ARPA: px%fctunl.rccn.pt@mitvma.mit.edu Fac. de Ciencias e Tecnologia/UNL | PSI/VMS: PSI%(+2680)005010310::PX 2825 Monte de Caparica | Fax: (+351) (1) 295 4461 PORTUGAL | Sound: (+351) (1) 295 4464 ext. 1360
slzr@GTE.COM (Suzanne Sluizer) (06/10/89)
In article <575@hfserver.hfnet.bt.co.uk> nigel@hfserver.hfnet.bt.co.uk (Nigel Cliffe) writes: > >I have a problem with backtracking, and retracts that don't appear to >happen - here is a simplified example: [deleted example of retracting something that you are backtracking over] >Can anyone explain why this happens. I would imagine that you will get much more technical explanations than I could give you, from various net people. However, I can give you a very simple idea of why Prolog isn't handling this. Your problem comes from the fact that by retracting something that you are backtracking over, Prolog gets "confused". Basically, Prolog loses track of "foo(X)" when you retract it, which makes it impossible to properly resatisfy that goal. You are lucky that you're using a robust Prolog -- it is possible to get "bus errors" and "core dumps" if Prolog doesn't handle this situation gracefully. -- Suzanne Sluizer CSNET: slzr%gte.com@RELAY.CS.NET GTE Laboratories UUCP: ...!harvard!bunny!slzr 617-466-2882 "Truth is a pathless land." -- Krishnamurti
armagan@PRC.Unisys.COM (Armagan Ozdinc) (06/12/89)
In article <PX.89Jun9194119@uniq.unl.fctunl.rccn.pt>, px@unl.fctunl.rccn.pt (Joaquim Baptista (pxQuim)) writes: > > Variations on this problem also arise with asserta and assertz, as in: > > /* this will loop forever, exhausting your heap space, > writing 1211111111... */ > b(1). b(2). > exec2:- b(X), write(X), assertz(b(X)), fail. > In Quintus Prolog 2.4, exec2 doesn't behave as you describe above. It prints 12 and fails. Armagan Ozdinc Unisys Corporation Paoli Research Center
lang@PRC.Unisys.COM (Francois-Michel Lang) (06/13/89)
In article <10539@burdvax.PRC.Unisys.COM> armagan@PRC.Unisys.COM (Armagan Ozdinc) writes: >In article <PX.89Jun9194119@uniq.unl.fctunl.rccn.pt>, px@unl.fctunl.rccn.pt (Joaquim Baptista (pxQuim)) writes: >> >> Variations on this problem also arise with asserta and assertz, as in: >> >> /* this will loop forever, exhausting your heap space, >> writing 1211111111... */ >> b(1). b(2). >> exec2:- b(X), write(X), assertz(b(X)), fail. > >In Quintus Prolog 2.4, exec2 doesn't behave as you describe above. It >prints 12 and fails. An article that is very relevant to this entire discussion of retractall and backtracking is the following: @INPROCEEDINGS{DefensibleSemantics, AUTHOR="Timothy G. Lindholm and Richard A. O'Keefe", TITLE="Efficient Implementation of a Defensible Semantics for Dynamic Prolog Code", BOOKTITLE=ilpc4, EDITOR="Jean-Louis Lassez", PAGES="21-39", PUBLISHER="The MIT Press", ADDRESS="Cambridge, MA", YEAR=1987 } Lindholm and O'Keefe describe several different approaches to dynamic code---i.e., a predicate whose definition can be modified at runtime, in particular by asserting or retracting clauses for that predicate. Any program that depends specifically on whether the Prolog system that is being used implements the "immediate update" or "logical" approach to handling dynamic code will *not* be very portable! ---------------------------------------------------------------------------- Francois-Michel Lang Paoli Research Center, Unisys Corporation lang@prc.unisys.com (215) 648-7256 Dept of Comp & Info Science, U of PA lang@cis.upenn.edu (215) 898-9511
px@unl.fctunl.rccn.pt (Joaquim Baptista (pxQuim)) (06/13/89)
In article <10539@burdvax.PRC.Unisys.COM> armagan@PRC.Unisys.COM (Armagan Ozdinc) writes: In article <PX.89Jun9194119@uniq.unl.fctunl.rccn.pt>, Joaquim Baptista writes: > > Variations on this problem also arise with asserta and assertz, as in: > > /* this will loop forever, exhausting your heap space, > writing 1211111111... */ > b(1). b(2). > exec2:- b(X), write(X), assertz(b(X)), fail. > In Quintus Prolog 2.4, exec2 doesn't behave as you describe above. It prints 12 and fails. Armagan Ozdinc Unisys Corporation Paoli Research Center One of the postings on this subject mentioned that Quintos Prolog has the nice property of 'freezing' the definition of a predicate when you call it, which seems nice to me. This is a solution to the assert/retract semantics that I had never heard of. However, Prolog-2 for IBM PC and C-Prolog will behave as I said. I believe Arity/Prolog will do that as well, but I'me not completely sure. -- -------- Joaquim Manuel Soares Baptista | BITNET/Internet: px@fctunl.rccn.pt Centro de Inteligencia Artificial | UUCP: px@unl.uucp Uninova | ARPA: px%fctunl.rccn.pt@mitvma.mit.edu Fac. de Ciencias e Tecnologia/UNL | PSI/VMS: PSI%(+2680)005010310::PX 2825 Monte de Caparica | Fax: (+351) (1) 295 4461 PORTUGAL | Sound: (+351) (1) 295 4464 ext. 1360