🚀 go-pugleaf

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
********************