We propose to measure the efficiency of any implementation of the λ-calculus as a function of a new parameter v, that is itself a function of any λ-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 Ω(v), i.e. a linear lower bound. Furthermore, we show that implementations based upon Turner Combinators or Hughes Super-combinators have complexities 2Ω(v), i.e. an exponential lower bound. It is open whether any implementation of polynomial complexity, vO(1), exists, although some implementations have been implicitly claimed to have this complexity.
|Original language||English (US)|
|Title of host publication||Functional Programming Languages and Computer Architecture - 5th ACM Conference, Proceedings|
|Number of pages||24|
|State||Published - 1991|
|Event||5th Conference on Functional Programming Languages and Computer Architecture, 1991 - Cambridge, United States|
Duration: Aug 26 1991 → Aug 30 1991
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||5th Conference on Functional Programming Languages and Computer Architecture, 1991|
|Period||8/26/91 → 8/30/91|
Bibliographical noteFunding Information:
*This research was partially carried out, while visiting Dartmouth College, New Hampshire tThis research was partially carried out, while supported by the Danish Natural Science Research Council (grant No. 11-7991) and while supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM).