Path: utzoo!mnetor!uunet!husc6!bloom-beacon!mcgill-vision!iros1!ouareau!tarau
From: tarau@ouareau.iro.umontreal.ca (Paul Tarau)
Newsgroups: comp.lang.prolog
Subject: Re: back_retract
Message-ID: <510@mannix.iros1.UUCP>
Date: 5 Apr 88 16:13:32 GMT
References: <1194@kulcs.kulcs.uucp> <777@cresswell.quintus.UUCP>
Sender: news@iros1.UUCP
Reply-To: tarau@iros1.UUCP (Paul Tarau)
Organization: Universite de Montreal
Lines: 194
Keywords: backtrackable assert and retract, DCG term expansion
Summary: Soft databases

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