[REM: destructive operations on circular emulation of infinite list]

[Rob MacLachlan <RAM@CMU-CS-C.ARPA>]

Date: 1985 March 20 03:01:16 PST (=GMT-8hr)
From: Robert Elton Maas <REM at IMSSS.SU.EDU>
Sender: REM%IMSSS at SU-SCORE.ARPA (for undeliverable-mail notifications)
Reply-To: REM at MIT-MC.ARPA
To:   RAM
cc:   "cork%umass-cs.csnet" at CSNET-RELAY.ARPA
Re:   destructive operations on circular emulation of infinite list
Sent: to SU-AI.ARPA by IMSSS.? via ETHERNET with PUPFTP; 1985-Mar-20 14:51:18 PST (=GMT-8hr)

> Date: Wed, 20 Mar 1985  05:07 EST
> From: Rob MacLachlan <RAM@CMU-CS-C.ARPA>
> Subject: Implementation of MAP, SOME, EVERY, etc...
> 
>     I think that a sufficiently fascist interpretation of the CLM
> would say that this is erroneous.  Nowhere in the CLM is it stated
> that a circular list is the same as an infinite list, and it is
> unlikely that any implementation would consistently have those
> semantics.   Setting element 537 of an infinite list should only
> change element 537.  Setting element 537 in a one-element circular
> list would probably change all the elements if it terminates.

I agree. Mathematically if LISP emulates an infinite list by a
circular list instead of by a continuation, and you ask LISP to make
an infinite list, then if you ask LISP to change a single element, the
circular list must be converted to a linear list up to the point of
change so that only the single element you specify will get changed. A
problem arises however if you fake out LISP by doing a RPLACD or NCONC
et al yourself without telling LISP whether you really meant to end
upwith a circular list (side-effects shared) or an emulation of an
infinite lisp (unfold-on-modify). In that case CLM should say the
result is implementation-dependent and such trick should be avoided in
portable code. Rebuttal?

>     The definition of a normal list in the Lists chapter is one
> terminated by NIL.  By this definition, a circular list is a dotted
> list.

Does it say anything except a normal list is a dotted list? There are
no other datatypes in the world? Or does it allow a third choice
(infinite list, circular list, list-by-continuation, etc.) which it
then fails to properly document?

> I believe that there was a decision at one point that functions
> which use lists as sequences (a superset of the sequence functions)
> are allowed to complain about dotted lists.

I think they should complain about (finite) dotted lists, but permit
both normal lists and circular/infinite lists if the latter is/are
permitted otherwise in CL. The semantics of MAPping down a set of
lists none of which is normal nor dotted, should be that the process
runs forever until a THROW-type event happens or the environment runs
out of memory or another kind of error happens. For example, a
reasonable hack would be to MAP down a circular list of ten elements
and when a realtime interupt happens process the current cell and THROW
out of the otherwise-infinite loop, thereby processing a random element
from a finite set. Or MAP down a circular list of devices trying to
find one that is available, looping forever if none of them ever
become free, otherwise using the first random one that becomes free.
The code for looping in a circular list seems to me cleaner than using
a 2-level loop with the outer loop DOing FOREVER the inner finite loop.

If the manual is unclear, I favor the above. If the manual clearly
forbids my interpretation, then I guess it's too late to change it.