PURE VERSUS IMPURE LISP

The aspect of purity versus impurity that we address involves the abse nce versus presence of mutation: the use of primitives (RPLACA and RPL ACD 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 s tructures 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 tem poral sequence of input and output operations must be maintained (that is, if computations must be ''on-line''), then a difference in comple xity remains. We do this by comparing the power of pure and impure ''L isp machines.'' We show that what an impure Lisp machine does in n ste ps (executions of primitive operations), a pure Lisp machine can do in O(n log n) steps, and that in some cases n(n log n) steps are necessa ry.