TEACH DIFFLISTS                                         Stuart Field,
                                                        July 1989

Difference lists in Prolog
--------------------------

A Prolog difference list consists of two components.  These may be
represented by separate arguments when calling predicates (as produced
by Prolog's built in DCG translator) or the two arguments may be joined
by a binary functor (such as the infix "-" or "/" operators).  The two
components share part of their structure: the second list and the "tail"
of one of the pairs which form the first list "share" (i.e. refer
{point} to the same object).  The intended meaning is that the list
itself is everything in the first list up to this pointer.

    For example:

The difference list X-Y where X == [ a, b, c | T ] and Y == T is stored
as:

          . <- {X}           
         / \                        Note: 
        a   .                       1. X and Y "bracket" the list                   
           / \                         [a,b,c].                   
          b   .                     2. Instantiating T to [] results                   
             / \                       in X being changed into an                   
            c   {T} <- {Y}             "ordinary" list [a,b,c].


Difference lists are "active" as long as the shared part (T) of the
structure is a variable.  Once this variable is instantiated, they are
joined onto whatever structure T has been instantiated to.  Because of
the properties of the logical variable, they cannot subsequently be
joined to another structure unless backtracking occurs through the
binding for T.

Instantiation of T can be used to concatenate difference lists in
constant time.  This only works if the first of the two difference lists
is "active", so that T can be instantiated.

          . <- {X}              W-Z: W == [d,e|U], Z == U
         / \
        a   .
           / \
          b   .
             / \
            c   {T} <- {Y}        . <- {W} 
                                 / \
                                d   .
                                   / \
                                  e   {U} <- {Z}


Concatenation of X-Y and W-Z can be brought about by unifying Y and W:

    append(X-Y, W-Z, X-Z):- Y = W.

or more simply (and more confusingly!) by:

    append(X-Y, Y-Z, X-Z).

This results in:

                     . <- {X}
                    / \
                   a   .
                      / \
                     b   .
                        / \
                       c   . <- {Y}
                          / \
                         d   .
                            / \
                           e   {U} <- {Z}

Thus Y is no longer "active", but Z is still active as it refers to the
variable U.

Further concatenation can be carried out either by instantiating Z to
the first part of another difference list (in which case the new list is
added to the end of X-Z) or by instantiating the active second part of
another difference list to X (in which case the other list is tacked on
to the front of X-Z).  This is essentially how Definite Clause Grammars
work.

As noted above, a difference list can be converted to a normal list by
instantiating the second part to []: the list is then no longer active,
and the first part is a standard list.  Making ordinary lists into
difference lists is harder: it involves copying the list element by
element to a new list, until the final tail (which is []) is reached;
this is replaced by a variable, which is returned as the second part of
the difference list.

One frequent and frustrating mistake with difference lists is to compare
two lists for equality by means of unification, as if they were normal
structures.  This can result in the instantiation of the second part in
such a way as to make a circular structure, e.g.:

    ([a|T]-T) = (U-U) results in

       U -> . <-----\
           / \      |
          a   {T}->-/

Prolog then prints out:

U = [a, a, a, a, a, a, a, a, a,    ..... and needs to be interrupted
with CTRL-C.  (Note that this structure violates the "occurs check" so
may result in incorrect behaviour even if it is not printed out.)

Thus the "strict equality" == must be used.  This does not carry out
unification: it merely tests if the two arguments have identical
structure, or "share" structure already.  This is not a "pure"
operation: it may give different results depending on when it is invoked
in the course of running a program, e.g.

    test(X,Y):-
        X==Y,
        write('Identical'),
        nl.

    test(X,Y):-
        X=Y,
        write('Unifiable'),
        nl,
        test1(X,Y).


    test1(X,Y):-
        X==Y,
        write('Now identical'),
        nl.

You might like to mark this and transfer into your output file, then
test it on a variety of expressions containing variables.

The net effect is that a predicate using difference list testing, which
needs '==' usually, may not work in calling modes other that the
intended one.

Further non-logical tests may also be of use, e.g.

var(Y) succeeds if the difference list X-Y is "active" at the time of
calling this goal, and fails if it is no longer "active" and cannot have
a list concatenated immediately onto its right-hand end.

nonvar(Y) is the opposite of var(Y).  '\==' is the opposite of '=='.

When non-logical expressions such as these are used to pick which clause
is relevant, I follow them with a "cut", e.g.

    % dl_member(M, X-Y):  M is a member of the difference list X-Y.

    dl_member(M, X-Y):-
        X == Y,
        !,
        fail.

    dl_member(M, [M|_]-Y).

    dl_member(M, [_|X1]-Y):-
        dl_member(M, X1-Y).

Note, however, that this can be rewritten more declaratively perhaps as
follows:

    dl_member(M, X-Y):-                 
        X \== Y,                 
        X = [M|_].                 

    dl_member(M, X-Y):-                 
        X \== Y,                 
        X = [_|X1],                 
        dl_member(M, X1-Y).

Here, unification must be performed AFTER matching, or the problems
demonstrated in test(X,Y) above will appear.

--- $poplocal/local/plog/teach/difflists
--- Copyright University of Sussex 1990. All rights reserved. ----------