From ok@atlas.otago.ac.nz Wed Sep 20 04:20:00 2000 Received: from atlas.otago.ac.nz (atlas.otago.ac.nz [139.80.32.250]) by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id EAA25154 for ; Wed, 20 Sep 2000 04:19:58 +0200 (MET DST) Received: (from ok@localhost) by atlas.otago.ac.nz (8.9.3/8.9.3) id OAA00327; Wed, 20 Sep 2000 14:20:09 +1200 (NZST) Date: Wed, 20 Sep 2000 14:20:09 +1200 (NZST) From: "Richard A. O'Keefe" Message-Id: <200009200220.OAA00327@atlas.otago.ac.nz> To: GordonStreeter@bigfoot.com, ok@atlas.otago.ac.nz, prolog@swi.psy.uva.nl Subject: Re: Circular references [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.)