Pure versus Impure Lisp

Document Type

Article

Department

Mathematics (HMC)

Publication Date

3-1997

Abstract

The aspect of purity versus impurity that we address involves the absence versus presence of mutation: the use of primitives (RPLACA and RPLACD in Lisp, set-car! and set-cdr! in Scheme) that change the state of pairs without creating new pairs. It is well known that cyclic list structures can be created by impure Lisp, but not by pure Lisp. In this sense, impure Lisp is “more powerful” than pure Lisp. If the inputs and outputs are restricted to be sequences of atomic symbols, however, this difference in computability disappears. We show that if the temporal sequence of input and output operations must be maintained (that is, if computations must be “on-line”), then a difference in complexity remains. We do this by comparing the power of pure and impure “Lisp machines.” We show that what an impure Lisp machine does in n steps (executions of primitive operations), a pure Lisp machine can do in O(n log n) steps, and that in some cases V(n log n) steps are necessary.

Rights Information

© 1997 ACM

Link to Full Text

Share

COinS