TEACH PROLOGINPOP                           Allan Ramsay, October 1985

         CONTENTS - (Use <ENTER> g to access required sections)

 -- Introduction
 -- Rough equivalents between POP-11 and PROLOG - first attempt
 -- Equivalents including CUT
 -- Using CATCH and THROW to implement CUT
 -- Exercises

-- Introduction -------------------------------------------------------

This file gives some examples of how POP-11 equivalents of PROLOG
clauses might be defined. The POP-11 procedures given below are very
like the procedures which are generated by the POPLOG version of PROLOG,
though with a considerable number of simplifications. The aim of this
document is to give people who understand POP-11 well a concrete model
of how PROLOG works. For a more theoretical, and more complete,
discussion of what is going on here, see DOC *CONTINUATION. For (very
technical) discussions of other ways of implementing PROLOG, see
"Implementations of PROLOG", ed. J Campbell (Ellis Horwood, 1984).

People who want to know how to call PROLOG programs from POP-11, or
POP-11 programs from PROLOG, should see HELP *POPTOPLOG, *PLOGTOPOP
(these are PROLOG HELP files - you will have to be using PROLOG for HELP
to get them for you).

-- Rough equivalents between POP-11 and PROLOG - first attempt --------

The following shows some PROLOG predicates and their POP-11 equivalents.
The POP-11 procedures contain a number of operators and syntax words
which are not part of ordinary POP-11. They are mostly to do with
managing PROLOG variables. They include a procedure called UNIFY, which
matches two structures, which may contain Prolog variables. If they can
be matched, UNIFY returns <true> and also keeps track of any variable
bindings it had to posit. SAVE (and RESTORE) save (and restore) the
bindings that had been established by calls of UNIFY. PROLOG_VARS
declares the words that follow to be Prolog variables, i.e. things which
UNIFY, SAVE and RESTORE should pay attention to.

    member(X, [X | _]).
    member(X, [_ | L]) :-
        member(X, L).

    define member_2 (contn, x, l);
        prolog_vars X, L, V1 ;
        SAVE();         /* Save current values of Prolog variables */
        if      unify(x, X)
                and unify(l, X :: V1)
        then    contn();
        endif;
        RESTORE();
            /* Undo all assignments to Prolog variables since SAVE */
        SAVE();         /* Now save them again */
        if      unify(x, X)
                and unify(l, V1 :: L)
        then    member_2(contn, X, L);
        endif;
        RESTORE();
    enddefine;

    intersect([X | L1], L2, [X | L3]) :-
        member(X, L2),
        intersect(L1, L2, L3).
    intersect([_ | L1], L2, L3) :-
        intersect(L1, L2, L3).
    intersect([], _, []).

    define intersect_3 (contn, l1, l2, l3);
        prolog_vars X, L1, L2, L3, V1, V2 ;
        SAVE();
        if      unify(l1, X :: L1)
                and unify(l2, L2)
                and unify(l3, X :: L3)
        then    member_2(intersect_3(% contn, L1, L2, L3 %), X, L2);
                    /* Note the new continuation, made out of a closure of
                       the next subgoal and the incoming continuation. (See
                       *CLOSURES, or "POP-11: a practical ..." 11.3 for more
                       on closures */
        endif;
        RESTORE();
        SAVE();
        if      unify(l1, V1 :: L1)
                and unify(l2, L2)
                and unify(l3, L3)
        then    intersect(contn, L1, L2, L3);
        endif;
        RESTORE();
        SAVE();
        if      unify(l1, nil)
                and unify(l2, V2)
                and unify(l3, nil)
        then    contn();
        endif;
        RESTORE();
    enddefine;

The above POP-11 procedures are roughly equivalent to what would be
produced in the POPLOG version of PROLOG if it were not for the fact
that we have to deal with "cuts" (see HELP *CUT). The next section shows
what the POP-11 procedures have to look like if our system is to include
cuts.

-- Equivalents including CUT ------------------------------------------

To accommodate the notion of CUT, we need to make use of the POP-11
procedures CATCH and THROW. These procedures are fairly intricate. The
following explanation is too brief to make them clear, as are the
descriptions in HELP *CATCH, *THROW. You would be well advised to read
the description in "POP-11: a practical ...", which at least gives a
concrete example of their use, before trying to read the description
below of how to implement CUT. This section also makes extremely heavy
use of complex POP-11 closures. Don't bother trying to read it unless
you are confident you understand how they work.

For those people who do not have access to the book, here is an
extremely brief explanation of CATCH and THROW. CATCH and THROW enable
you to specify that some procedure in your program should return a
result immediately to a procedure higher up the calling sequence,
skipping over any remaining instructions in procedures in between the
two. CATCH is called with three arguments. The first is a procedure to
be run immediately. The second is a procedure to be run if THROW is
called while the first is running. The third is some pattern which is to
be matched against the object which has been thrown - if they do not
match, then the call of THROW must be aimed at some different catcher
higher up the calling sequence. THROW is called with a single argument.
Its effect is to cause control to return the first enclosing call of
CATCH whose third argument matches THROW's own argument.

Using these procedures, we can implement CUT by making it call THROW. At
the point where the CUT is called, we make up a unique object, which is
to be thrown if ever we try to backtrack over the cut. We call the next
sub-goal after the CUT using CATCH, rather than simply applying it. If
this call of CATCH is ever thrown the object it is waiting for, it exits
immediately from the clause/procedure in which it was called.

    define cut (contn, thrown);
        contn();            /* CUT succeeds immediately, and calls its
                               continuation */
        throw(thrown);      /* But if the continuation returns, denoting
                               the fact that it failed, then CUT throws
                               its other argument to anyone who is
                               waiting to catch it */
    enddefine;

    intersect([X | L1], L2, [X | L3]) :-
        member(X, L2), !,   /* Cut included to ensure correct behaviour */
        intersect(L1, L2, L3).
    intersect([_ | L1], L2, L3) :-
        intersect(L1, L2, L3).
    intersect([], _, []).

    define intersect_3 (contn, l1, l2, l3);
        prolog_vars X, L1, L2, L3, V1, V2, thrown, newcontn ;
        SAVE();
        if      unify(l1, X :: L1)
                and unify(l2, L2)
                and unify(l3, X :: L3)
        then    gensym("thrown") -> thrown; /* Make up a unique object
                                               for CUT to throw */
                catch(% cut(% intersect_3(% contn, L1, L2, L3 %), thrown %),
                        exitfrom(% intersect_3 %) %),
                        thrown %) -> newcontn;
                                            /* See below for a description of
                                               this object, which is to be the
                                               continuation of MEMBER_2,
                                               i.e. what it does next if
                                               it succeeds */
                member_2(newcont, X, L2);
        endif;
        RESTORE();
        SAVE();
        if      unify(l1, V1 :: L1)
                and unify(l2, L2)
                and unify(l3, L3)
        then    intersect(contn, L1, L2, L3);
        endif;
        RESTORE();
        SAVE();
        if      unify(l1, nil)
                and unify(l2, V2)
                and unify(l3, nil)
        then    contn();
        endif;
        RESTORE();
    enddefine;

-- Using CATCH and THROW to implement CUT -----------------------------

In the above definition of INTERSECT_3, the following closure of CATCH
was constructed to deal with the fact that the first PROLOG clause for
INTERSECT contained a cut immediately after the call of MEMBER:

    catch(% cut(% intersect_3(% contn, L1, L2, L3 %), thrown %),
            exitfrom(% intersect_3 %) %),
            thrown %)

This unbelievably complicated object is to be the continuation for the
call of MEMBER_2. It is a closure of CATCH, i.e. a procedure which is
just like CATCH but has all its arguments "frozen in". When it is called
(which will happen if the call of MEMBER_2 for which it is the
continuation is successful) it will apply CATCH to these frozen
arguments. The first of these is a closure of CUT. So, since the first
thing CATCH does is apply its first argument, this closure of CUT will
get run. The first thing CUT does its apply its own first argument, in
this case a closure of INTERSECT_3 on the original continuation and the
unified values of L1, L2 and L3 (this is exactly as it was in the
original version without the cut). If this continuation ever returns,
CUT will THROW its second argument. This will be caught by the call of
CATCH, which will then apply its second argument. This is (yet another)
closure, this time of a procedure called EXITFROM (see HELP *EXITFROM).
EXITFROM causes control to return immediately from the nearest enclosing
call of its argument, in this case INTERSECT_3.

All this achieves the effect of CUT in two stages. The first stage is
achieved by the calls of CATCH and THROW. When THROW is called, it
performs an immediate exit through all the procedures between the place
where it was called and the place where it gets caught. It is these
procedures which contain all the backtrack points for previous subgoals
of the current main goal, so short-cutting the normal procedure return
mechanism to these procedures will mean that all these backtrack points
get thrown away. The second stage of the CUT is performed by the call of
EXITFROM. This makes the procedure which is supposed to achieve the
current goal return immediately, without continuing with any of its
other IF ... THEN ... ENDIF clauses, which embody alternate ways of
achieving the same goal.

-- Exercises ----------------------------------------------------------

1. Write a program to compile PROLOG clauses without cuts into POP-11
procedures.

2. Write a program to compile PROLOG clauses with cuts into POP-11
procedures.

-----<Copyright University of Sussex 1987.  All rights reserved.>-------
