Skimmed a paper titled "Pure versus Impure Lisp" by Nicholas Pippenger the other day. Impure Lisp dialects allow mutations. Pippenger wanted to know if pure Lisp, without mutation, was less "powerful". Under two conditions he showed the following,
A computation in impure Lisp upper bounded by O(n) is lower bounded in pure Lisp by big-omega n log n. Basically, given the same problem there's a theoretical lower limit to pure Lisp's efficiency compared to impure Lisp.
But then the guys at FP Lunch lead me to a follow-up paper titled "More Haste, Less Speed: Lazy Versus Eager Evaluation". In it, Bird, Jone and de Moor showed that if you changed the pure Lisp evaluator to pure and lazy as oppose to Pippenger's original pure and eager then you can get the same linear time as the impure program. Interestingly enough, the authors noted that lazy evaluation is often implemented with mutations behind the scenes (via memoization), so it's really a discussion of restricted mutation. This is along the lines of an earlier posting I made about the problem with immutability and how compilers can, behind the scenes, solve some of the inefficiencies of immutability, but then it becomes a philosophical debate on what it really means to be immutable (or pure).
And that concludes another installment of interesting topics I'll never need to know.
