gast@CS.UCLA.EDU (03/12/88)
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!gastfinin@antares.PRC.Unisys.COM (Tim Finin) (03/14/88)
From: gast@CS.UCLA.EDU
Subject: A Suggested Additional Predicate for Prolog
Date: 12 Mar 88 07:23:48 GMT
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."...
I recall that Micro-Planner had such predicates for assert and
retract. I think that the normal assert (THASSERT) and retract
predicates (THREMOVE?) predicates had the desired behavior and that
there were alternates which were not undone on backup. Tim
------------------------------------------------------------------------------
Tim Finin finin@prc.unisys.com
Paoli Research Center ..!{psuvax1,sdcrdcf,cbmvax,bpa}!burdvax!finin
Unisys Corporation 215-648-7446 (o)ok@quintus.UUCP (Richard A. O'Keefe) (03/14/88)
In article <10303@shemp.CS.UCLA.EDU>, gast@CS.UCLA.EDU writes: [ he wants backtrackable assert and retract, and concentrates on back_retract(Clause). ] > 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. Eh? Remember, N! gets *very* big, *very* fast. What does it matter how fast "programming permutations" is, when doing it at all is the kiss of death to efficiency? I hope I've misunderstood. > By the way, assert and retract are unlike most predicates in that > their bindings are not undone on backtracking. Eh? The variable _bindings_ most certainly ARE undone! The change to the data base is not, but then write/1 doesn't erase the screen and read/1 doesn't reach out and shove your fingers backwards either. > 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. You forgot the smiley. The only Prolog interpreter I've ever seen where the text of the clause was stored was one done by Michael McCord in SNOBOL. There are ways that an enabled/disabled flag could be cheaply associated with a clause, but I strongly suspect that Mr Gast hasn't thought through the interactions between back_retract/1 and the cut. What is supposed to happen if I do back_retract(foo), abort. Is foo supposed to be gone, or not? > In all of these cases back_retract > 1) changes an N**N problem to a N! problem. Stirling's approximation: N! = sqrt(2*pi*N) * (N/e)**N * (1 + 1/12N + 1/288N**2 + O(1/N**3)) For example, (N!)/(N**N) ~=~ 9x10**-9 for N=21, which looks like a big improvement, but 21! ~=~ 5x10**19. Suppose an operation takes 1 microsecond, for what value of N would doing it N! times take more than a year? There are roughly 3.16x10**7 seconds in a year, so for what value of N is N! > 3.16x10**13? 16! is 1.5 times too small, 17! is 11 times too big. Think about it: if the basic operation costs 1 microsecond, and we do N! of them, for N=17 it will take 11 years. For N=14, it will take a little over a day. Converting an N**N algorithm to an N! one converts something which is practically impossible to something which is only practically impossible. -- Those who do not understand Prolog are condemned to reinvent Lisp, poorly.
miller@ACORN.CS.ROCHESTER.EDU (Brad Miller) (03/17/88)
Date: 12 Mar 88 07:23:48 GMT
From: gast@CS.UCLA.EDU
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.
It is, in fact, our current plan that RHET (a PROLOG varient implemented in
LISP primarily for KR uses rather than "logic programming") will have all
functions with side effects that can supply undo functions to automatically
get undone if they are backtracked on. So assert, retract, and possibly user
functions could be undone if an appropriate undo function is declared.
Once this is in place, it is the non-retracting assert that will be
unavailable! We currently haven't implemented it, because of some
non-trivial interactions with intelligent backtracking.
Mainly, this just discourages use of these predicates: if someone were to do
a PROVE-ALL, that is, to find all the proofs of some goal, some of whose
proof trees included ASSERTS and others that did not, it is unclear which of
these proofs will be considered "final" and not have their assertions
undone. (Prove-all generates a proof, records it, and then "fails" in order
to generate another proof).
So what this really comes down to, is you have to be very careful about
side-effects, when they are useful, and what sort of persistance (per proof,
indefinite, just the current branch, etc.) you want them to have. We
certainly haven't "solved" these problems, we will just pick some convenient
definitions (for the KR work we do) and implement that.
------
miller@cs.rochester.edu {...allegra!rochester!miller}
Brad Miller
U. Rochester Comp Sci Dept.
'If anything is True, this is.'cdsm@ivax.doc.ic.ac.uk (Chris Moss) (03/23/88)
In article <10303@shemp.CS.UCLA.EDU> gast@CS.UCLA.EDU () writes: >I suggest that back_retract would be useful for many applications. >(Not mutually exclusive) > +) finding permutations > +) solving constraints etc. David, you need to learn the style of programming in Prolog before you make suggestions as to how to change it. Read one of the better books: e.g. Sterling & Shapiro's "The Art of Prolog". You will find that the use of data structures is almost ALWAYS preferable to using assert and retract. e.g. write a list permutation routine and compare the speed with one using assert and retract (any one, not just yours) -- the better the Prolog the bigger the difference. That's why nobody bothers to improve assert and retract (there are other reasons too). Chris Moss.