pchen@uicsg.UUCP (02/28/87)
I am interested in finding out how often circular list structures arise in normal lisp operation, if at all, and if so, in what applications.
forbus@uiucdcsp.cs.uiuc.edu (03/04/87)
Almost always. One typically wants to have backpointers in complex datastructures, yielding a circularity right there.
wagner@iaoobelix.UUCP (03/12/87)
/***** iaoobelix:comp.lang.lisp / uiucdcsp!forbus / 7:25 pm Mar 4, 1987*/
I think, there are two major applications of circular lists:
1. Infinite lists. Under some circumstances (map...) it is useful to have
a list containing a periodic sequence of objects. This (circular)
list can then be used e.g. in mapcar to apply a function to an
infinite (but periodic) sequence of data objects.
2. Backpointers. (see also previous response) Imagine an object-oriented
system or a semantic net where you need to have mutual references
between objects (e.g. superclass-subclass, class-instance).
Often, however, circular lists can be avoided (yet no circular structures)
if you use symbols as placeholders for entry points into circular structures.
You have to use this technique on e.g. with reference-counting GCs (cf.
XEROX Interlisp-D).
Juergen Wagner, (USENET) ...seismo!unido.uucp!iaoobel!wagner
("Gandalf") Fraunhofer Institute IAO, Stuttgartflowers@ucla-cs.UUCP (03/15/87)
In article <6900003@iaoobelix.UUCP> wagner@iaoobelix.UUCP writes: >I think, there are two major applications of circular lists: > >1. Infinite lists. Under some circumstances (map...) it is useful to have > a list containing a periodic sequence of objects. This (circular) > list can then be used e.g. in mapcar to apply a function to an > infinite (but periodic) sequence of data objects. Infinite lists are more appriately embodied in streams (see Abelson&Sussman 3.4).
shebs@utah-orion.UUCP (Stanley T. Shebs) (03/15/87)
In article <5044@shemp.ucla-cs.UCLA.EDU> flowers@CS.UCLA.EDU (Margot Flowers) writes: >Infinite lists are more appriately embodied in streams (see >Abelson&Sussman 3.4). From a practical point of view, once the circular list is constructed, there is no more consing, while all the stream implementations I've seen use storage like there's no tomorrow. I'd be really impressed by a compiler that could transform a stream into a circular list if possible (don't some functional language systems try to do that?). BTW, it's never even occurred to me to use a circular list to model a stream. Can anybody give a real example, along with enough context to demonstrate that it was necessary and not a frob by a RPLACD fan? stan shebs shebs@cs.utah.edu
jbn@glacier.STANFORD.EDU (John B. Nagle) (03/17/87)
Worth considering is whether a slightly different set of primitives
might provide the functionality needed for back-pointers and true circularity
without making refererence-count storage management impossible.
Suppose we call the existing type of list pointer an "asymmetrical
pointer" and introduce the notion of a "symmetrical pointer". A
symmetrical pointer connects two objects and can be traversed in either
direction. Symmetrical pointers can be altered by atomic operations which
specify a pair of objects to be connected. Asymmetrical pointers cannot
be altered once created.
This is not a totally novel idea. See SLIP and Safe Mesa for examples.
It's not necessarily LISP oriented, either.
John Nagle