bimbart@kulcs.uucp (Bart Demoen) (03/15/88)
See what you can do in BIMprolog:
back_retract((_h :- _b)) :-
clause(_h,_b,_n) ,
functor(_h,_f,_a) , functor(_nh,_f,_a) ,
clause(_nh,_nb,_n) ,
(retract((_h :- _b),_n) ;
assert((_nh :- _nb),_n) , fail ) .
clause/3 has as 3th argument the number of the clause:
ex. database = a(x) .
a(y) .
a(z) .
then ?- clause(a(y),true,2) . succeeds
and ?- clause(a(X),true,3) . says:
X = z
and ?- clause(a(x),true,N) . says:
N = 1
the second argument in retract/2 has a similar meaning ;
in a call to assert/2, the 2nd arg must be instantiated and the clause is
asserted at the arg2'th place in the database; in this way, asserta/1 is just
a special case of assert/2, with definition:
asserta(_x) :- assert(_x,1) .
so the query ?- assert(a(foo),3) . on the above database has as effect that the
database will look afterwards like:
a(x) .
a(y) .
a(foo) .
a(z) .
But there should be a better way of doing what you want.ok@quintus.UUCP (Richard A. O'Keefe) (03/15/88)
In article <1194@kulcs.kulcs.uucp>, bimbart@kulcs.uucp (Bart Demoen) writes: > See what you can do in BIMprolog: [ I have reformatted this so that I can read it: if you want to see how Bart Demoen wrote it, read his message. ] > back_retract((HeadUsed:- BodyUsed)) :- > clause(HeadUsed, BodyUsed, Index), % FIND the clause > functor(HeadUsed, Symbol, Arity), > functor(HeadCopy, Symbol, Arity), > clause(HeadCopy, BodyCopy, Index), % COPY the clause > ( retract((HeadUsed :- BodyUsed), Index) % DELETE the clause > ; assert((HeadCopy :- BodyCopy), Index), % REPLACE the clause > fail % resume failing > ). Porting problem: DEC-10 Prolog has assert(+Clause, -Ref) and clause(+Head, ?Body, -Ref) where Ref is a sort of pointer, and several other Prologs do the same. Even AAIS Prolog tries. But that's a minor change, just invent new names for the operations. This will do what the original poster wants, ONLY IF there are no other changes to the same predicate. Consider back_retract(<clause>) -- removes 3rd clause asserta(<new clause>) fail This will shuffle the data base, which was not what was wanted. This kind of excessively unpleasant interaction is precisely why the DEC-10 Prolog family hasn't got "positional" data base commands. We could get around this by having an 'assert_before' predicate which took a clause and a data base reference and put the clause before the one the reference pointed to (even if the referenced clause had since been deleted): * back_retract(Clause) :- * prolog_clause(Clause, Head, Body), % see DECONS.PL in DEC-10 lib * clause(Head, Body, Ref), % FIND the clause * instance(Ref, Copy), % COPY the clause * ( erase(Ref) % DELETE the clause * ; assert_before(Ref, Copy), % REPLACE the clause * fail % resume failing * ). This would be free of shuffling problems, even when other updates to the predicate in question were being made. However, both versions of back_retract/1 have a rather more serious failure mode. Consider back_retract(<clause>), ... !, ... fail By analogy with variable bindings, you would expect the back-retracted clause to reappear. But the cut will have had the effect of pruning away the "assert". Was it in 1983 or 1984 that I pointed this problem out in the Prolog Digest, with reference to an 'assume' operation? This problem is the reason that Quintus Prolog hasn't got backtrackable assignment to global variables in the library: cuts prune away the restoration code. > But there should be a better way of doing what you want. If back_retract is being used to simulate something even vaguely logical, there has been some very interesting work done at Stony Brook on extending Prolog with some features of dynamic logic. Roughly speaking, there are three classes of predicates: pure predicates (don't depend on things that change) state predicates (depend on things that change, but change nothing) transition predicates (express a relation between states) For example, we might say p(X) :- <-fred(X)> q(X). p(X) is true in a world W if there is a world W1 such that -(fred(X), W, W1) -- roughly, retract and q(X) is true in W1. Note that this doesn't change W. Permanent changes are effected by the top level, where queries have the meaning "let W be the current world; if there is a world W1 and a substitution S such that the query arrives in W1 with substitution S, print S and make W1 the current world." I'm sorry that I can't remember the name of the person who was working on this. He promised me a copy of a paper about it, but it never arrived, so I can't give you a reference either. A pity, because this strikes me as the obviously right way to handle "local" data base updates, it's even related to an existing logic! It remains the case that converting an O(N**N) operation to an O(N!) -- which the original poster cited as motive for having back_retract/1 -- is scarcely worth the trouble.
micha@ecrcvax.UUCP (Micha Meier) (03/16/88)
In article <777@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >However, both versions of back_retract/1 have a rather more serious >failure mode. > >Consider > > back_retract(<clause>), > ... > !, > ... > fail > >By analogy with variable bindings, you would expect the back-retracted >clause to reappear. But the cut will have had the effect of pruning >away the "assert". Was it in 1983 or 1984 that I pointed this problem >out in the Prolog Digest, with reference to an 'assume' operation? 1983, but not really pointed out :-) This is only an implementation problem. If you, instead of using code to implement the backtrackable retract, push a suitable reference on the trail, then it works fine even with the cut, provided that you do not tidy up the trail (as described in the old engine). For some systems this might be too costly, as they use no special trail entries, but if the trail is already used to undo different things, that one is easily incorporated. You can get backtrackable assignment for free, then. Since several people here at ECRC asked me to provide backtrackable assert and retract, I assume that it can really be useful. One possible application is hypothetical reasoning - with the asserts and retracts you create alternative worlds, but you certainly want to be able to return to your universe. This is completely logical. Another area where it could be used is for database integrity constraints checking, or of course for theorem proving. Since all this stuff is logical, the above mentioned implementation can be used (there are no cuts), but sometimes it is desirable to have the old clause back at the position where it was before. --Micha
ok@quintus.UUCP (Richard A. O'Keefe) (03/17/88)
In article <516@ecrcvax.UUCP>, micha@ecrcvax.UUCP (Micha Meier) writes: > In article <777@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: > > back_retract(<clause>), > > ... > > !, > > ... > > fail > This is only an implementation problem. The point of my message was that the "obvious" way of doing this in Prolog doesn't work. I think it was worth mentioning this because it is one of those old chestnuts that keeps popping up. Someone once kindly showed Quintus how to implement backtrackable global assignment; he'd put a fair bit of work into it, but the ( change /* exit */ ; /* redo */ undo_change, fail ) pattern was what he had used, so it didn't actually work. Credit: of the Prologs I know anything about, LM-Prolog has had undoable side-effects longest. I've seen a demo of LM-Prolog "undrawing" a picture, I think this was at IJCAI-83. The person who explained the technique of pushing arbitrary functions onto the trail to me was Preben Folkjaer, then of InterFace. Pushing functions on the trail is a neat trick, but it isn't a panacea. Consider the problem of I/O: you really don't want to push a function onto the trail for every character you write. Chris Moss has a paper, I don't know where it appeared, on undoable I/O, and when you can actually produce the output. > Since several people here at ECRC asked me to provide > backtrackable assert and retract, I assume that it can > really be useful. You should see the things people ask for in comp.lang.c! > One possible application is hypothetical > reasoning - with the asserts and retracts you create > alternative worlds, but you certainly want to be able to > return to your universe. I think Sanjay Manchanda's approach is much cleaner. Undo the side effect of an assert or retract? But <+X> and <-X> haven't GOT any side effects! For hypothetical reasoning in general, Ken Bowen's approach to meta-level reasoning is to make the alternative worlds explicit as data values; in a system like that you can reason about several worlds at once. If we can get logical arrays with acceptable efficiency (which would be useful in any case), it seems that the Manchanda & Bowen approaches need not be inferior in efficiency to the backtrackable side efffects approach. What happens if you are using a system with backtrackable side effects (such as back_retract) and the code aborts (explicit call to abort, or to some sort of error signalling operation)? Do the side-effects get unwound then? I'm not asking "how do you do it", but "what do you want it to do?" What happens if you have an AND-parallel system and one process executes back_retract, do the other processes notice the change or not? If you take the Bowen or Manchanda approach to data base updates, the answer is obvious: nothing is changing, you just get additional worlds. (The Manchanda approach may be easier for AND-parallel systems.)
tarau@ouareau.iro.umontreal.ca (Paul Tarau) (04/05/88)
A number of recent articles by Bart Demoen, Richard O'Keefe,
Sanjay Manchanda and Paul Voda re-opened the problem of the
"assert" family of primitives. I agree that we can do better without.
However, as much as we restrict us to a unique path of the Prolog
proof-tree, it is possible to manipulate their "soft" counterparts
safely and to implement them efficiently. I introduce these soft
counterparts in the context of an abstract data-type, namely a
"soft-database". They may be useful to do explicit hypothetical
resonning in Prolog.
Soft databases are sets of Prolog clauses having their
modifications undone on backtracking exactly as if they
were an ordinary Prolog data structure.
Soft databases contain chunks of executable Prolog code and/or
global "data".
Each one-argument operation on a soft-database is mapped in
a three-argument meta-logical operation using the following
transformation:
operation(SoftClause) ---> operation(SoftClause,OldDb,NewDb)
We can implement them simply by using the DCG preprocessor,
who can handle the last two arguments in a very nice way.
The basic idea is to meta-evaluate our program by a source-to-source
transformation of most of the operations on the soft database, using
a DCG driven term-expansion. On the other hand we must insure that
predicates which do not use meta-evaluation have not to pay for.
In the source file, clauses which use the soft database
operations are represented by the functor "-->" as in DCG rules.
This means that two additional arguments are appended at the end of
each predicate-term (say Db1 and Db2), to simulate the state of the
database before and after the call. However, if the predicate-term
is a variable, (say X), this gives "phrase(X,Db1,Db2)" and X will
be only expanded at run-time, when it becomes instantiated.
The "-->" functor may be interpreted declaratively
as a grammar based specification of the problem, or
procedurally as a description of soft data-base transformations.
The meta-circular evaluation mechanism works by chaining successive
states of the soft database.
"Assume" and "assume_last" work like asserta and assertz,
"forget" works like retract, but all their effect is backtrackable.
Previously assumed code in the database can be activated by using "wake-up".
The "{}" escape mechanism provides a call to Prolog without term-expansion.
The predicates "demo" and "wake_up" implement the meta-circular evaluation
mechanism.
This mechanism works as if it were a conventional meta-interpreter but
it is far more efficient, as only a limited amount of interpretation
is done (when compiled code explicitly uses wake-up).
In this case, the soft database is searched by "assumed" for a
matching clause, then "demo" is called and the body of the current
clause is traversed recursively, until a callable compiled predicate-term
is reached.
Then control is transferred to compiled code, which works as fast
as it can.
If one of the predicates which interact with the database
is called, it effectively uses the 2 hidden arguments
corresponding to the state of the database.
Suppose, for example that in the source code "assume(C)" is called.
The DCG expansion done at compile time insures that
"assume(C,Db1,Db2)" will execute, and if "Db1" is the state of
the database before, then "Db2" will be the state of the database
after assuming C.
/*------------------------ cut here -----------------------------------*/
% main predicate
go :- make_empty_database(_,Db),readloop(Db,_).
% definition of soft database operations
make_empty_database(_,Db):-new(Db). % the old database may be lost
assume(C)-->add_front(C). % like 'asserta'
assume_last(C)-->add_end(C). % like 'assertz'
forget(C)-->remove(C). % like retract, potentially non-monotonic operation
% retrieve a soft clause as data
assumed(C,D,D):-find(C,D). % like 'clause', but does not copy
% activate a soft-clause as code
wake_up(H) --> % works like 'call'
assumed(T),{copy_term(T,C)},
( {C = (H :- B)} -> demo(B) % match a clause with a body
; {C = H} % match a fact
).
% meta-circular interpreter
demo(C) -->
( {C=(P,Q)} -> (demo(P),demo(Q))
; {C=(I->T;E)} -> (demo(I) -> demo(T) ; demo(E))
; {C=(P;Q)} -> (demo(P);demo(Q))
; C
).
% hack for 'demo' to handle {} when evaluating itself
{C} --> {call(C)}.
getdb(Db,Db,Db). % gets the database as a term
setdb(Db,_,Db). % sets the database - the previous is lost
% failure driven printing of the assumed clauses
showdb -->
{write('Soft database:'),nl},getdb(Db),{numbervars(Db,0,_)},
assumed(C),{write(C),write('.'),nl,fail}
; {true}.
% simple read-eval loop
readloop -->
{nl,write('<READ LOOP>'),nl,write('| ?- '),read(X)},
( X -> {write('Yes.')}
; {write('No.')}
),{nl},readloop.
% difference list based implementation of
% soft database manipulation tools
% makes a new difference list
new(H:H).
% adds to the front of a difference list
add_front(X,H:T,[X|H]:T).
% adds to the end of a difference list
add_end(X,H:[X|T],H:T).
% finds an element of the difference list
find(X,H:T):- H\==T,
( H=[X|_]
; H=[_|H1],H1\==T,
find(X,H1:T)
).
% removes an element of the difference list
remove(X,L1:T,R1:T):- L1\==T,
( L1=[X|R1]
; L1=[Y|L2],L2\==T,R1=[Y|R2],
remove(X,L2:T,R2:T)
).
% As an example, let us consider the following solution
% to the N-queens problem:
queens(N) -->
make_free_positions(N),place(N),print_solution,{fail}
; {true}.
% makes a pool of free positions
make_free_positions(P) -->
{P>0} -> assume(free(P)),{P1 is P-1},make_free_positions(P1)
; {true} .
% try to place the queen Q
place(Q) -->
{Q>0} -> forget(free(P)),{S is Q+P, D is Q-P},% generate
not_under_attack(S,D), % test
{NewQ is Q-1},place(NewQ)
; {true}.
% tests if on diagonals S and D the queen is not under attack
% and assimilates the proposed position as the
% intersection of two diagonals
not_under_attack(S,D) -->
assumed(on_diagonals(S1,D1)),
{ S=S1
; D=D1
} -> {fail}
; assume(on_diagonals(S,D)).
% calculates the position of each queen and prints it
print_solution -->
assumed(on_diagonals(S,D)),{P is (S-D)//2,write(P),fail}
; {nl}.
The program was tested in Quintus Prolog 2.0, on a Sun 3.
To use it, type "go" and then something like "queens(8)" or
"assume(phone(mike,X)),assume(phone(mary,X)),showdb".
If soft databases will be of some interest on the net I will post some
less trivial applications to games and automated induction.
Paul Tarau