PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (08/12/86)
PROLOG Digest Tuesday, 12 Aug 1986 Volume 4 : Issue 36
Today's Topics:
Implementation - Manipulating ->,
Puzzle - Farmer & Extension Tables
----------------------------------------------------------------------
Date: Sun 10 Aug 86 14:04:09-PDT
From: Fernando Pereira <PEREIRA@SRI-CANDIDE.ARPA>
Subject: Manipulating Programs With ->
To be honest I can't remember any substantial discussion on
this topic back when -> was added to the DEC-10 interpreter,
but looking back into it I see a very good reason. The
alternatives of a disjunction are like the alternative
clauses of a disjunction, -> is like cut in one of those
clauses. Thus
p :- a -> b; c.
is equivalent to
p :- q.
q :- a, !, b.
q :- c.
If -> had the higher precedence, the most obvious interpretation
would be
q :- a, !, r.
r :- b.
r :- c.
which is clearly useless. The argument becomes even more compelling
if one thinks about the intended interpretation of goals like
(a -> b;
c;
d -> f;
g)
-- F
------------------------------
Date: 11 Aug 1986 11:10-EST
From: Saumya Debray <debray%suny-sbcs@csnet-relay>
Subject: Manipulating Programs With ->
I agree with you regarding the parse of "P -> Q ; R",
_if_ we're to understand -> in terms of cut. I'd
prefer not to have to do that as far as possible --
for one thing, understanding program behaviour in the
presence of cuts isn't always straightforward, and
for another, cuts can invalidate program transformations
that one would like to have hold (e.g. "hard" cuts
invalidate unfold transformations; "soft" cuts as in
-> can invalidate "clause factoring" transformations,
as in the example I gave earlier).
I guess I'd much rather deal with a distfix ->/3, which
I find more intuitive.
-Saumya Debray
[recall; Much of this ground has been covered in prehistoric Digest
exchanges. Reconsulting the Archives might be in order. -ed]
------------------------------
Date: 11 Aug 1986 11:17-EST
From: Suzanne Dietrich <suzanne%suny-sb@csnet-relay>
Subject: Farmer Puzzle and Extension Tables
I agree with Ed Windes:
>- First, I don't think your 'linked' procedure is doing what it
>should. Seems to me that the query 'linked(state(1,1,1,1),X).'
>should produce four distinct alternatives.
The alternatives are:
1) farmer takes the fox
2) farmer takes the goose
3) farmer takes the grain
4) farmer takes only himself across
Also, I think there may be a typo in the 'linked' procedure.
>linked(state(F1,X1,G1,A1),state(F2,X2,G2,A2)) :-same(no,F1,F2),
>
>(same(yes,X1,X2);(same(yes,F1,X1),same(yes,G1,G2),same(yes,A1,A2))),
>(same(yes,G1,A2);(same(yes,F1,G1),same(yes,X1,X2),same(yes,A1,A2))),
---------------------^ Should this be G2?
>(same(yes,A1,A2);(same(yes,F1,A1),same(yes,G1,G2),same(yes,X1,X2))).
Ed Windes also suggests:
>- Second, you need to rewrite your 'path' procedure because
>A) it is left-recursive, and B) you need to keep a record of
>states already visited, and exclude them from the possible
>next states.
The path procedure as written is logically correct. Unfortunately,
Prolog enters an infinite loop on this program due to the points
A and B above.
Consider another solution to the Farmer Program (of unknown
origin):
-----------------------------------------------------------
/* state(Farmer,Fox,Goose,Grain) */
state(n,n,n,n). /* Initial state */
state(X,X,U,V):- /* Farmer takes Fox */
safe(X,X,U,V),opp(X,X1),state(X1,X1,U,V).
state(X,Y,X,V):- /* Farmer takes Goose */
safe(X,Y,X,V),opp(X,X1),state(X1,Y,X1,V).
state(X,Y,U,X):- /* Farmer takes Grain */
safe(X,Y,U,X),opp(X,X1),state(X1,Y,U,X1).
state(X,Y,U,V):- /* Farmer goes by himself */
safe(X,Y,U,V),opp(X,X1),state(X1,Y,U,V).
/* North(n) and South(s) are opposite shores */
opp(n,s).
opp(s,n).
/* safe(Farmer,Fox,Goose,Grain) */
safe(X,Y,X,V). /* Farmer is with Goose */
safe(X,X,X1,X):-opp(X,X1). /* Farmer is not with Goose */
/* QUERY: state(s,s,s,s). */
-----------------------------------------------------------------
This program also suffers from an infinite loop due to revisiting
of states. David S. Warren and I have developed an algorithm which
evaluates most simple recursive programs (including left-recursion).
The method, known as extension tables, applies the dynamic
programming principle to computation in which previous results are
saved and later reused to avoid recomputation. The algorithm, called
the ET algorithm, is a simple source-to-source transformation on a
Prolog program. The latter farmer program is successfully executed
with an ET saved on the predicate state/4. I also used the ET
algorithm on the predicate path/2 in the former Farmer program (with
the correction of A2 to G2) and the query succeeded.
Here is the ET transformation for the predicate state/4:
1] Define a predicate code_state/4 to have the original
definition for state
code_state(n,n,n,n). /* Initial state */
code_state(X,X,U,V):- /* Farmer takes Fox */
safe(X,X,U,V),opp(X,X1),state(X1,X1,U,V).
code_state(X,Y,X,V):- /* Farmer takes Goose */
safe(X,Y,X,V),opp(X,X1),state(X1,Y,X1,V).
code_state(X,Y,U,X):- /* Farmer takes Grain */
safe(X,Y,U,X),opp(X,X1),state(X1,Y,U,X1).
code_state(X,Y,U,V):- /* Farmer goes by himself */
safe(X,Y,U,V),opp(X,X1),state(X1,Y,U,V).
2] Redefine the predicate state/4 to save calls and answers
state(X1,X2,X3,X4) :-
call_state(Y1,Y2,Y3,Y4), /* check for call */
same(state(Y1,Y2,Y3,Y4),state(X1,X2,X3,X4)),!,
et_state(X1,X2,X3,X4). /* use et answers */
state(X1,X2,X3,X4) :-
assert(call_state(X1,X2,X3,X4)), /* save call */
code_state(X1,X2,X3,X4), /* compute answer */
not(et_state(Y1,Y2,Y3,Y4),
same(state(Y1,Y2,Y3,Y4),state(X1,X2,X3,X4))),
assert(et_state(X1,X2,X3,X4)). /* save answer */
Note: The predicate same/2 identifies two terms to be the same
if they are identical upon renaming of variables.
A predicate subsumes/2 can be used instead of same/2:
if there was a previous call to p(X,Y) and p(X,b) is
called, then the answers for p(X,b) are a selection of
the answers for p(X,Y) so a table lookup can be used.
The ET algorithm is not complete for Datalog (function-free
Prolog). This simple facility, which modifies Prolog's top-down
left-to-right depth-first evaluation strategy, executes and
terminates evaluation on many programs for which Prolog's
evaluation enters an infinite loop. The ET* algorithm, which
is complete for Datalog, iterates using the ET algorithm until
no new answers are produced.
------------------------------
End of PROLOG Digest
********************