Computing cyclic list structures

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 definition facility are discussed.

REFERENCES

• 1: Landin, P.J., "The mechanical evaluation of expressions", The Computer Journal 6, 4 (January 1964), pp. 308-319.
• 2: Burge, W.H., Recursive Programming Techniques, Addison-Wesley, Reading Mass. (1975).
• 3: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 4: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 5: Friedman, D.P. and Wise, D.S., "Cons should not evaluate its arguments", Third International Colloquium on Automata, Languages, and Programming, Michaelson, S. and Milner, R., eds., Edinburgh University Press, (1976).
• 6: Morris, F.L., "On list structures and their use in the programming of unification", Syracuse University, C.I.S. report 4-78.
• 7: Knuth, D.E., Morris, J.H., and Pratt, V.R., "Fast pattern matching in strings," SIAM Journal of Computing 6 2 (June 1977), pp. 323-350.
• 8: Schwarz, J.S., "Verifying the safe use of destructive operations in applicative programs", Proc. 3rd International Symposium on Programming, B. Robinet ed., Dunod, Paris (1978).

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Algorithms, Languages, Performance