We propose to measure the efficiency of any implementation of the lambda-calculus as a function of a new parameter v, that is itself a function of any lambda-expression. Complexity is expressed here as a function of v just as runtime is expressed as a function of the input size n in ordinary analysis of algorithms. This enables implementations to be compared for worst case efficiency. We argue that any implementation must have complexity OHgr(v), i.e. a linear lower bound. Furthermore, we show that implementations based upon Turner Combinators or Hughes Super-combinators have complexities 2OHgr(v), i.e. an exponential lower bound. It is open whether any implementation of polynomial complexity, v O(1), exists, although some implementations have been implicitly claimed to have this complexity.
Functional Programming Languages and Computer Architecture: 5th Acm Conference Cambridge, Ma, Usa, August 26–30, 1991 Proceedings, 1991, p. 289-312
Main Research Area:
Lecture Notes in Computer Science
ACM Conference on Functional Programming Languages and Computer Architecture, 1991