lee@mungunni.OZ (Lee Naish) (03/21/85)
(In response to articles about bugs/features? in retract in a
couple of Prolog systems recently in the digest/net.lang.prolog)
I'm not surprised there are buggy versions of retract around.
It is one of the nastiest bits of Prolog to implement and no-one has even
completely defined how it should behave in all cases. Consider the
following kind of goal:
?- . . . p(X), . . . retract(p(Y)), . . .
When we get around to calling retract, the call to p(X) has just matched
some clause, say C. Retracting clauses before C in the database is not
too tricky. If we try to retract C we cannot reclaim the memory immediately
but it should be done after backtracking or perhaps if cut is called.
The effect on the call to p(X) is not properly defined. The same is true
for retracting clauses after C in the database. When p(X) backtracks, will
it be able to match these clauses? In some implementations it may depend
on whether there are other references to the clauses (so the memory cannot
be reclaimed immediately).
The situation becomes even worse in a database system, like the one
attached to MU-Prolog. Rather than a simple linked list (for example)
in main memory and accessed sequentially, we have a fairly complicated
dynamic hashing data structure in a file with concurrent access.
The normal solution to the inevitable problems is the readers/writers
restriction. In Prolog this leads to deadlocks since the same process
is doing the reading and writing. Our current solution in the database
system is to make people put a cut between p(X) and retract(p(Y)).
This means that the call to p reading the database can be killed before
retract writes on the database. The operational semantics are also
(relatively) unambiguous.
This is just one of many examples where retract (and assert and cut)
is not defined properly. Does anyone have any sugestions for well defined
semantics (preferably possible to implement) or alternatives?
Lee Naish
ACSNET: lee@mulga
UUCP: {decvax,vax135,eagle}!mulga!lee
ARPANET: decvax!mulga!lee@Berkeley