We shall refer to Lisp with or without these mutation primitives as impure or pure Lisp, respectively.

This answer is not completely satisfying, however, because it assumes we want our programs to produce a particular representation of the answer, and it is this representation - rather than the answer - that is beyond the power of pure Lisp.

Can every impure Lisp program solving such a problem be transformed into a pure Lisp program with the same input-output behavior, in such a way that the number of primitives executed by the pure program exceeds the number performed by the impure program by at most a constant factor?

Our question regarding pure versus impure Lisp undoubtedly occurred to many workers, but its first appearance in print seems to be due to Hood and Melville [1981], who conclude their paper with the remark "It would be interesting to exhibit a problem for which the lower bound in Pure LISP is worse than some implementation using rplaca and rplacd." (The positive results of their paper apply to symbolic and on-line computations, so it does not seem unreasonable to suppose that they would not be repelled by the additional restrictions we have imposed.)

THEOREM 1.1 There is a symbolic on-line computation that can be performed by an impure Lisp program in such a way that at most O(n) primitive operations are needed to produce the first n outputs, but for which every pure Lisp program must perform (for some input sequences) at least [Omega](n log n) primitive operations to produce the first n outputs.

Every symbolic on-line computation that can be performed by an impure Lisp program in such a way that at most T(n) primitive operations are needed to produce the first n outputs can be performed by a pure Lisp program that performs at most O(T(n) log T(n)) primitive operations (for all inputs sequences and for all values of n) to produce the first n outputs.

It is well known that a last-in-first-out stack discipline is easily implemented in pure Lisp, but the obvious implementation of a first-in-first-out queue relies on mutation to add items at the tail of the queue.

Clinger) is that pure Lisp must be compiled (rather than interpreted) if it is to express computations with the same efficiency as impure Lisp.

THEOREM 3.1 Every on-line symbolic impure Lisp machine M can be simulated by a pure Lisp machine M' in such a way that all outputs produced by M within the first n steps are produced by M[prime]within the first O(n log n) steps.

This can almost be proved by combining Theorem 1 of Ben-Amram and Galil [1992], where n steps on a RAM are simulated by O(n log n) steps on a pure Lisp machine, with an obvious simulation of n steps on an impure Lisp machine simulated by O(n) steps on a RAM.

The heart of the simulation is a technique for simulating mutation of array entries in pure Lisp. Such simulations have undoubtedly been discovered by many workers, but the first appearance in print seems to be that of Myers [1984].