PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (04/06/87)
PROLOG Digest Monday, 6 Apr 1987 Volume 5 : Issue 24
Today's Topics:
Query - Compare/3,
Programming - 91 Function & Turtles
----------------------------------------------------------------------
Date: 27 Mar 87 02:10:21 GMT
From: Bjorn Danielsson <mcvax!enea!zyx!bd@seismo.css.gov>
Subject: compare/3 problem
In the process of implementing Prolog, I and the people I am working
with have been considering the problem of comparing variables with
compare/3. The goal is that two variables should always be sorted in
the same order, as long as their bindings don't change.
In an implementation that is based on a Warren Abstract Machine, the
natural way to compare variables is to compare their addresses. This
normally sorts older variables to be < newer ones. However, it
occurred to us that put_unsafe_value might cause problems with
permanent variables (in Warren's terminology) that become globalized.
Try the following program on your favourite WAM-based Prolog:
test :- foo(X), bar(X).
foo(X) :- compare(Z,Y,X), compare(Z,Y,X).
bar(_).
The query "?- test." should preferably succeed. (It didn't on one of
the commercially available, widely popular Prologs we tried :-)
The obvious fix is to let compare/3 globalize variables.
-- Bjorn Danielsson
------------------------------
Date: Mon, 30 Mar 87 09:33:01 est
From: Paul Hudak <hudak-paul@YALE.ARPA>
Subject: 91 function
<Some comments on the 91 function and the use of cut.>
In Manna's book "Mathematical Theory of Computation" the "91 function"
is defined on p. 411 as:
f(x) = if x>100 then x-10 else f(f(x+11)) (1)
It turns out that this is equivalent to:
f(x) = if x>100 then x-10 else 91 (2)
but "coding it up" this way sort of misses out on the computational
aspect of definition (1). In Prolog Digest V5 #22 the Prolog solution:
foo(91,91). (3)
foo(X, Z) :-
X > 100,
Y is X - 10,
foo(Y, Z).
foo(X, Z) :-
Y is X + 11,
foo(Y, N),
foo(N, Z).
was given; but this misses the point in much the same way (2) does.
Furthermore, it is "technically" wrong in that without a cut an
infinite number of solutions are returned, although they are all the
same (91). An alternative solution was also given:
foo(X, Z):- (4)
X > 100,
Z is X - 10, !.
foo(X, Z) :-
Y is X + 11,
foo(Y, N),
foo(N, Z).
but the CUT sure makes this ugly. In the spirit of Manna's definition,
I suppose the best version is:
foo(X, Z):- (5)
X > 100,
Z is X - 10.
foo(X, Z) :-
X =< 100,
Y is X + 11,
foo(Y, N),
foo(N, Z).
But this has a repeated test (X>100, X=<100). Is there a better way?
Note that the solution in a functional language such as pure lisp is
just:
f(x) = if x>100 then x-10 else f(f(x+11))
which looks an awful lot like (1)...
-- Paul Hudak
------------------------------
Date: Wed, 1 Apr 87 9:06:44 PST
From: Kenneth Kahn <kahn.pa@Xerox.COM>
Subject: Turtles
Regarding using turtles for a dynamic backtracking display of Prolog
execution. Four years ago I wrote a system and a paper entitled "A
Grammar Kit for Prolog" about the same idea for DCGs in Prolog. The
system (using a backtracking turtle) drew the parse tree as it was
parsing and erased upon backtracking. The paper was published in a
book called "New Horizons in Educational Computing" edited by Yazdani,
Ellis Horwood Press, 1984. The program became one of the more popular
demo programs in LM-Prolog. I think the backtracking display really
did help explain the operation of a Prolog system. I have worries
about how well it scales for debugging large programs.
Eisenstadt and Brayshaw have written a really good graphical
debugger/viewer for Prolog. The paper is called "The Transparent Prolog
Machine -- An Execution Model and Graphical Debugger for Logic
Programming", Open University, HCRL, TR 21, December 1986
------------------------------
End of PROLOG Digest
********************