1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 unknown4 Department of Computer Science, Science and Technology, Aarhus University
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