Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!elroy!cit-vax!ucla-cs!gast
From: gast@CS.UCLA.EDU
Newsgroups: comp.lang.prolog
Subject: A Suggested Additional Predicate for Prolog
Message-ID: <10303@shemp.CS.UCLA.EDU>
Date: 12 Mar 88 07:23:48 GMT
Sender: news@CS.UCLA.EDU
Reply-To: gast@CS.UCLA.EDU ()
Organization: UCLA Computer Science Department
Lines: 204

Logic programming seems to me to be an ideal paradigm for dealing with
combinations and permutations.  If there were some way to temporarily
retract a clause, but leave it's position in the database unchanged,
programming permutations would be much easier and faster.

In other words, the retract should be undone on backtracking.  For
consistency sake, an assert that is undone on backtracking should also
be included, but the rest of this comment does not concern itself with
a "backtrackable assert."

By the way, assert and retract are unlike most predicates in that
their bindings are not undone on backtracking.  This behavior is
non-orthogonal.  Thus, I propose to have orthogonal predicates
for adding to or deleting from the database.

I therefore propose that the following predicate be added to Prolog.

    back_retract(Clause).

back_retract will temporarily make that clause not part of the data-
base, but back_retract will not change the clause's location
in the database.  When backtracking occurs, back_retract allows
that clause to be unified again.

It is, therefore, generally not the same as a retract and assert
because back_retract does not change the position of the clause
within the database.  retract and assertz, on the other hand, would
change the location of the clause in the database--the clause would
be moved to the end of the database.

While it would be difficult to write back_retract in pure Prolog, it would
be easy to implement it in the implementation language if that language
is not Prolog.  A possible method assuming an ascii computer is
to change the first character of the primary functor of the clause.
For example,
    back_retract(x(3))
could temporarily change the name x to ^Mx, where ^M indicates that
the high order bit of the next character is set.  That is, the ascii
representation of the predicate would be 248, not 120.  As 248 does
not unify with 120, pattern matching would fail.  A few predicates
like back_retract and assert would need to handle ^M character, but
most predicates should not.  This method should be fast unlike assert
and retract which are frequently slow.

I suggest that back_retract would be useful for many applications.
(Not mutually exclusive)
    +) finding permutations
    +) solving constraints
    +) solving puzzles like magic squares or SEND + MORE = MONEY
       (see below).
    +) avoiding cyclic graphs  (back_retract the arc).
    +) playing tic-tac-toe (when a move is made, back_retract that square).
    +) etc.

In all of these cases back_retract 

    1) changes an N**N problem to a N! problem.
    2) allows the constraints to be mixed with the part of the code
       generating the permutations.

For example, the following program can find all of the permutations of
1, 2, and 3 (if a semi-colon causes backtracking).

    assert(num(1)).
    assert(num(2)).
    assert(num(3)).

    perm3(A,B,C) :-
       num(A), back_retract(num(A)),
       num(B), back_retract(num(B)),
       num(C) .

In this program, num(A) instantiates A to 1.  Then back_retract(num(A))
temporarily removes num(1) from the database.  Then num(B) instantiates
B to 2, and back_retract(num(B)), temporarily removes num(2) from the
database.  Finally, num(C) instantiates C to 3.  The back_retract(num(C))
is not actually needed and so it is not included.  Then if a semi-colon
is typed, another num(C) will be tried, but there are none--num(C) is
at the end of the database, so back_retract(num(B)) is backtracked,
which ends the temporary retraction of num(2), and so num(2) is once
again unifiable.  num(B) then tries to find another instantiation--which
is does by unifying B and 3.  num(3) is then temporarily retracted.
etc. etc.

It seems as if this same technique could be used to solve crypto-
arithmetic puzzles
like
        S E N D
      + M O R E
      ---------
      M O N E Y
      
(Colmerauer, CACM, Dec 85, page 1310).

--------program follows--------

Since M must be 1, we call puz, so that M is instantiated to 1. 
Colmerauer checks to see that M and S are not equal to zero.
My constraint is equivalent.

*/

% Assert the possible numbers for the other letters.  1 is not included
% since M=1.
:- assert(num(0)).  :- assert(num(2)).  :- assert(num(3)).
:- assert(num(4)).  :- assert(num(5)).  :- assert(num(6)).
:- assert(num(7)).  :- assert(num(8)).  :- assert(num(9)).

% call with M = 1 to get one solution.  If the argument is a variable,
% then backtracking can occur, but no other solutions are found.
% solve from right to left
puz(M) :-
    M=1,
    num(D), back_retract(D),
    num(E), back_retract(E),
    constraint(C1,Y,D,E,0), num(Y), back_retract(Y),

    num(N), back_retract(N),
    num(R), back_retract(R),
    constraint(C2,E,N,R,C1),       % already back_retracted E.

    num(E), % already back_retracted E.
    num(O), back_retract(D),
    constraint(C3,N,E,O,C2),       % already back_retracted N.

    num(S), back_retract(D),
    constraint(C4,O,S,M,C3),       % already back_retracted O.

    % Really, all we have to check is that M=C4=1,
	% but we do it the long way
    constraint(0,M,0,0,C4),

	% output the answer
    tab(2), write(S), write(E), write(N), write(D), nl,
    write(' +'), write(M), write(O), write(R), write(E), nl,
    tab(1),write(M), write(O), write(N), write(E), write(Y), nl.


% constraint(-carryout, -sum, +add1, +add2, +carryin)

% First get case where no carry out.  Then case where there is carry out.

constraint(0, Sum, Add1, Add2, CarryIn) :-
    Sum is Add1 + Add2 + CarryIn,
    Sum =< 9,
    !.

constraint(1, Sum, Add1, Add2, CarryIn) :-
    Sum is Add1 + Add2 + CarryIn - 10.

--------program ends--------

The use of the back_retract allows the combinatoric aspect of the
program to be nicely interleaved with the constraint side of the program.

This program can be implemented in Prolog without using back_retract,
but it is slower and the user is forced to do significantly more typing
which is error prone.  Alternatively, "member" and "lists" could be
used, but their use is not all that convenient either.

For example, using the same basic structure as above, we can write:

puz(M) :-
    M=1,
    num(D),
    num(E), E \= D,
    constraint(C1,Y,D,E,0), num(Y), Y \=D, Y \= E,

    num(N), N \= D, N \= E, N \= Y,
    num(R), R \= D, R \= E, R \= Y, R \= N,
    constraint(C2,E,N,R,C1),      % already know \= M, D, Y, N, R

    num(E), 
    num(O), O \= D, O \= E, O \= Y, O \= N, O \= R,
    constraint(C3,N,E,O,C2),      % already know \= M, D, E, Y, R, O

    num(S), S \= D, S \= E, S \= Y, S \= N, S \= R, S \= O,
    constraint(C4,O,S,M,C3),      % already know \= M, D, E, Y, N, R, O, S

    % Really, all we have to check is that M=C4=1,
	% but we do it the long way
    constraint(0,M,0,0,C4),

    tab(2), write(S), write(E), write(N), write(D), nl,
    write(' +'), write(M), write(O), write(R), write(E), nl,
    tab(1),write(M), write(O), write(N), write(E), write(Y), nl.

The other predicates are unchanged and so are not shown again.
This program in C-prolog takes in 3.2 seconds of user time on a Sun 3.
(By examining the constraints closely, I sure it could be made faster).

Thus,
    back_retract(S),
in the program serves the same purpose as
    S \= D, S \= E, S \= Y, S \= N, S \= R, S \= O,
in the alternative.

Thus, because it is orthogonal with most of the rest of Prolog and
it is useful, I recommend back_retract be included in Prolog.

I look forward to hearing your comments

David Gast
gast@cs.ucla.edu
!ucla-cs!gast