Computing Cyclic List Structures

F. Lockwood Morris, Syracuse University
J. S. Schwartz, Syracuse University

SU-CIS-80-02

Description/Abstract

It is argued that list structures containing cycles are useful and unobjectionable Lisp entities. If this is so, it is desirable to have a means of computing them less foreign to the equational-definition style characteristic of Lisp than are the list-structure-altering primitives rplaca and rplacd. A notion is developed of a reasonable system of mutually recursive equations, guaranteed to have a unique solution in list structures. The notion is given in terms of the computations invoked by the equations, without reference to the forms of expressions appearing in them. A variety of programming examples are presented, including a curious implementation of the Knuth-Morris-Pratt string matching algorithm. Two methods of implementing the recursive definitions facility are discussed.