Parallel Beta Reduction Is Not Elementary Recursive

• Published in: Information and computation 2001-10, Vol.170 (1), p.49-80
• Main Authors: Asperti, Andrea, Mairson, Harry G.
• Format: Article
• Language: English
• Subjects: Algebra; Algorithmics. Computability. Computer arithmetics; Applied sciences; Associative rings and algebras; Computer science; control theory; systems; Exact sciences and technology; Mathematics; Sciences and techniques of general use; Theoretical computing
• ISSN: 0890-5401; 1090-2651
• DOI: 10.1006/inco.2001.2869

We analyze the inherent complexity of implementing Lévy's notion of optimal evaluation for the λ-calculus, where similar redexes are contracted in one step via so-called parallel β-reduction. Optimal evaluation was finally realized by Lamping, who introduced a beautiful graph reduction technology for sharing evaluation contexts dual to the sharing of values. His pioneering insights have been modified and improved in subsequent implementations of optimal reduction. We prove that the cost of parallel β-reduction is not bounded by any Kalmár-elementary recursive function. Not only do we establish that the parallel β-step cannot be a unit-cost operation, we demonstrate that the time complexity of implementing a sequence of n parallel β-steps is not bounded as O(2n), O(22n), O(222n), or in general, O(Kl(n)), where Kl(n) is a fixed stack of l 2's with an n on top. A key insight, essential to the establishment of this non-elementary lower bound, is that any simply typed λ-term can be reduced to normal form in a number of parallel β-steps that is only polynomial in the length of the explicitly typed term. The result follows from Statman's theorem that deciding equivalence of typed λ-terms is not elementary recursive. The main theorem gives a lower bound on the work that must be done by any technology that implements Lévy's notion of optimal reduction. However, in the significant case of Lamping's solution, we make some important remarks addressing how work done by β-reduction is translated into equivalent work carried out by his bookkeeping nodes. In particular, we identify the computational paradigms of superposition of values and of higher-order sharing, appealing to compelling analogies with quantum mechanics and SIMD-parallelism.