Pippenger compares pure to impure LISP with respect to program complexity. Impure LISP is defined as the form of LISP that has rplaca and rplacd primitives (or their equivalents) for destructive replacement of the list head and list tail with new values. The author considers only symbolic and online computations.

The paper answers the question of whether every impure LISP program that transforms a word over a finite alphabet into a Boolean value can be transformed into an equivalent pure LISP program in such a way that the number of executed primitives in the pure LISP program is larger by a constant value than the number of executed primitives in the impure LISP program.

The main result of the paper is stated in Theorem 1.1, which states that there is a symbolic online computation that can be performed by an impure LISP program with at most O ( n ) primitive operations for the first n outputs, but for which every pure LISP program, for some input sequences, performs at least G ( n log n ) primitive operations. G ( f ( n ) ) is a function bounded below by a positive constant multiple of f ( n ).

The paper is well written and easy to follow. Proofs of some theorems are done by a simple Scheme program, which makes the paper even more interesting.