Subject: Re: Circular references

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 20 Sep 2000 14:20:09 +1200 (NZST)

[Concerning circular references]
	I'll certainly take this advice under consideration.  It is more
	than a little amusing to me that, when I first discovered that
	the circular references were the source of the problem, I looked
	for advice in your book, and decided that the idea must have
	been beneath your mention.

I simply never thought of writing anything about it.
I *was* aware at the time that the Prolog-III people were talking about
"rational trees", and I was also aware that someone had given them a logical
semantics by bending the definition of equality.
What's more, I was also aware of David H. D. Warren's cunning use of cyclic
terms to implement coroutining on top of DEC-10 Prolog, which worked largely
because as architect of DEC-10 Prolog, he was able to skate safely around
gaps in the specification that would have swallowed lesser programmers.
However, I was also aware that (at the time) almost no Edinburgh-compatible
Prolog systems had built-in operators that could do anything useful with
cyclic terms (apart from type test predicates, functor/3, and arg/3, of
course).  It's like someone writing a guide-book not bothering to say
"don't climb high-voltage power pylons", you know it is dangerous, so you
forget that some people might try it.

Here's a favourite example of why cyclic terms make life hard.
It comes from Scheme.  Scheme has a built-in function "list?" which
is true iff its argument is a proper list (made of dotted pairs, does
end, and ends with a nil).  Absent cyclic terms, it would be

    (define (list? X)
        (if (pair? X) (list? (cdr X)) (null? X)))

But in the presence of cyclic terms, it has to use tortoise-and-hare:

    (define (list? X)
      (define (tnh X Y)
        (cond
          ((not (pair? X)) (null? X))             ; finite end
          ((not (pair? (cdr X))) (null? (cdr X))) ; finite end
          (else
            (let ((X (cdr (cdr X))) (Y (cdr Y)))
              (if (eq? X Y) #f                    ; cycle detected
                  (tnh X Y)) )) ))                ; two steps X, one step Y
      (tnh X X))

You really *don't* want to have to make several dozen built in predicates
fiendishly complicated to support a rather dubious feature.

Perhaps a more illuminating way of thinking about the pervasive nastiness
that creeps in when you work with cyclic terms is this:

    length(L, N) :-			% length xs = aux xs 0
        length_loop(L, 0, N).		%   where

    length_loop([], N, N).		%       aux [] n = n
    length_loop([_|T], N0, N) :-	%       aux (_:xs) n = aux xs (n+1)
        succ(N0, N1),
        length_loop(T, N1, N).

If L is a ground term in the Herbrand base, then whether it is a list or
not, the query ?- length(L, N) ***must*** terminate.  (In a strict
functional language, the definition of length on the right must terminate.)
But if L may be cyclic, then there is no reason to expect that query to
terminate (and in a lazy functional language, the given definition of
length sometimes *doesn't* terminate).  Simply patching a couple of dozen
built in operations (the compare/3 family, the =/2 family, the sort/2
family (what _should_ sort/2 do, given an infinite list? fail I guess),
the write/1 family, and so on) does NOT help with user-defined code.
(For example, the path_arg/3 family in the Quintus library.)  Suddenly,
*every* recursive user-defined predicate that obviously terminates has
to be checked with the most extraordinary care, because the reasoning one
uses simply isn't valid any more.

To be sure, Prolog failed to detect the error of creating cyclic terms.
Mercury has compile-time detection for that, thank goodness, making it
something one can suggest to a Software Engineer with a straight face.
What that meant in practice was that one programmed in Prolog *as if*
cyclic terms could not exist (using library(unify) if in doubt), and if
a program mysteriously failed to terminate, one swore at Prolog ("may the
breath of a thousand aerosols pollute your environment stack") and tried
clever debugging techniques (like
	term_expansion((Head :-Body), (Skel :- unify(Skel,Head), Body)) :-
	    same_functor(Head, Skel).
only rather more code than that, of course, to turn "fast" unifications
into "safe" unifications).  We usually get away with it, because we're not
*trying* to get into danger.

	I'm no Prolog expert, so I wouldn't think of arguing the point
	with you.  I'm using circular references to maintain
	navigability in both directions between parent and child
	structures.  There may be a better to do that, but I don't have
	the funds to redesign my application at this point.  Maybe in
	the next release, if there is a next release.

Ah yes, "The Leprous Curse of DOM".  I sent a critical note to the XML
InfoSet people pointing out that their allegedly "language-independent"
model in fact went out of its way, for no apparent reason, to make
InfoSet conformance totally impossible in strict functional and logical
languages (because they required parent links).  I also pointed out that
it similarly prohibits hash consing, which can save quite a lot of space.

I think that every Prolog programmer would be the better for a little
functional programming experience.  With the exception of logical variables
on one side and function closures on the other, data structure design
really is similar.

Everything depends on what your original requirements actually are.

For argument's sake, let's take

    :- type node(Data) --> node(Data,[node(Data)]).
	/* The label and children of a node */

    :- type ctx(Data) --> ctx(node(Data),[node(Data)],[node(Data)]).
	/* A node with its left and right siblings */
    :- type pos(Data) --> pos(Data,[ctx(Data)]).
	/* A non-empty stack of contexts (the root context is
           ctx(Tree,[],[])), with the Data  of the
           active tip redundantly pulled out for faster access.
	*/

    :- pred start(?node(Data), ?pos(Data)).
    %  start(Node, Pos) is true when Node is a node and Pos is a tree
    %  position representing "Node as the root".

    start(Node, pos(Data,[ctx(Node,[],[])])) :- Node = node(Data,_).

    :- pred right(?pos(Data), ?pos(Data)).
    %  right(PosL, PosR) is true when PosL and PosR represent positions
    %  in the same tree, with PosR one step to the right.

    right(pos(D1,[ctx(N1,L,[N2|R])|A]),
	  pos(D2,[ctx(N2,[N1|L],R)|A])) :-
	N1 = node(D1,_),
	N2 = node(D2,_).

    :- pred left(?pos(Data), ?pos(Data)).
    %  left(PosR, PosL) is true when PosL and PosR represent positions
    %  in the same tree, with PosL one step to the left.
    %  It is just right/2 with the arguments flipped.

    left(pos(D1,[ctx(N1,[N2|L],R)|A]),
         pos(D2,[ctx(N2,L,[N1|R])|A])) :-
	N1 = node(D1,_),
	N2 = node(D2,_).

    :- pred up(+pos(Data), ?pos(Data)).
    %  up(PosD, PosU) is true when PosD and PosU are positions in the
    %  same tree, and PosU is one step up from PosD.  When we take a
    %  step up, we forget which child we were looking at, so this is
    %  not directly invertible.

    up(pos(_,[_|A]), pos(D,A)) :-
	A = [ctx(node(D),_,_)|_].

    :- pred down(?pos(Data), ?pos(Data)).
    %  down(PosU, PosD) is true when PosD and PosU are positions in
    %  the same tree, and PosD represents the position "at the leftmost
    %  child of PosU".  Because we know which child PosD must be, this
    %  is directly invertible.

    down(pos(Dp,A), pos(Dc,[ctx(N,[],R)|A])) :-
	A = [ctx(node(Dp,[N|R]),_,_)|_],
	N = node(Dc,_).

    :- pred at_root(+pos(Data)).
    %  at_root(Pos) is true if Pos has no proper ancestors.

    at_root(pos(_,[_])).
	
    :- pred at_leaf(+pos(Data)).
    %  at_leaf(Pos) is true if Pos has no children.

    at_leaf(pos(_,[ctx(node(_,[]),_,_)|_])).

    :- pred at_left(+pos(Data)).
    %  at_left(Pos) is true if Pos is at a node that has no left sibling.

    at_left(pos(_,[ctx(_,[],_)|_])).

    :- pred at_right(+pos(Data)).
    %  at_right(Pos) is true if Pos is at a node that has no right sibling.

    at_right(pos(_,[ctx(_,_,[])|_])).

    /* ancestor, descendant, sibling, and variously indexed forms of these
       are left as an exercise for the reader, because someone has just
       come to see me.
    */

I owe the basic idea here to David H. D. Warren, who used it in his own
(Prolog-implemented) editor, and I have just reconstructed it from memory.
The data structure that represents a position in the tree is rather bulkier
than a single pointer would be, BUT
 - the tree itself is more compact (better to spend a few dozen words
   on the current position than many thousands of words on the tree),
 - whenever you could have navigated from one node to another in O(N)
   time using up,down,left,right pointers, you can do the same navigation
   using [up,down,left,right]/2 in O(N) time too (by inspection, each of
   the predicates is O(1) if the output argument is uninstantiated).
 - the method is applicable in Mercury and ML; no cycles needed.

Now, I have no idea just what kinds of "navigability" were needed.
(Look at some of the lovely XML toolkits that have been written in
Haskell for some ideas about high level navigation.)