Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!mailrus!ames!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.lisp
Subject: Re: Total ordering for Lisp objects ?
Message-ID: <29362@news.Think.COM>
Date: 12 Sep 89 21:46:38 GMT
References: <5896@lifia.imag.fr> <865@skye.ed.ac.uk> <2084@munnari.oz.au> <4932@ubc-cs.UUCP>
Sender: news@Think.COM
Organization: Thinking Machines Corporation, Cambridge MA, USA
Lines: 24

In article <4932@ubc-cs.UUCP> morrison@grads.cs.ubc.ca (Rick Morrison) writes:
>In article <2084@munnari.oz.au> ok@cs.mu.oz.au (Richard O'Keefe) writes:
>>The ordering of a and b has changed although a and b still point to the
>>"same" objects.  (Think about one stack group trying to sort a list while
>>another is happily mutating it...)
>I don't get. How does this argue against defining a total ordering
>on LISP objects? Admittedly the above example violates referential
>transparency, but this is a result of the use of destructive assignment.

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.

A recursive ordering relation also loses when circular structures are
involved.  Again, Prolog doesn't have these (destructive assignment is
necessary to create them).

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar