Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!visix!andyt
From: andyt@visix.UUCP (Andy Turk)
Newsgroups: comp.lang.lisp
Subject: Re: Total ordering for Lisp objects ?
Summary: Prolog has it's problems too...
Message-ID: <217@visix.UUCP>
Date: 13 Sep 89 18:22:46 GMT
References: <5896@lifia.imag.fr> <865@skye.ed.ac.uk> <2084@munnari.oz.au> <29362@news.Think.COM>
Organization: Visix Software, Arlington, Virginia
Lines: 29

In article <29362@news.Think.COM>, barmar@think.COM (Barry Margolin) writes:

> It doesn't argue against defining a total ordering, but it does argue
> against copying Prolog's algorithm, which specifies that the ordering
> of two structured objects is a function of the ordering of their
> contents.  Prolog has no destructive assignment, so it doesn't suffer
> such problems.

> Barry Margolin
> Thinking Machines Corp.
> 
> barmar@think.com
> {uunet,harvard}!think!barmar

In the case of Prolog, you don't need destructive assignment to screw up
an enduring term order.  The problem is that of unbound variables.  Unbound
variables CAN be modified ONCE.  If you sort two terms that have unbound vars
in them, then if the order cannot be established from the ground parts of the
terms, there should be no order between the two terms.  However, most
Prologs will actually use the implementation's representation of unbound
variables (pointers) to come up with an ordering.  Obviously, this order can
change if any of the variables used to order the terms are bound at a later
time.

-- 
-------------------------------------------------------------------------
     Andrew K. Turk                           visix!andyt@uunet.uu.net

        "I don't know what happened to my face." -- Dizzy Gillespie