What is an Efficient Implementation of the lambda-calculus?
DOI:
https://doi.org/10.7146/dpb.v20i344.6574Abstract
We propose to measure the efficiency of any implementation of the lambda-calculus as a function of a new parameter mu, that is itself a function of any lambda-expression. Complexity is expressed here as a function of nu 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 Omega(nu), i.e. a linear lower bound. Furthermore, we show that implementations based upon Turner Combinators of Hughes Super-combinators have complexities 2Omega(nu), i.e. an exponential lower bound. It is open whether any implementation of polynomial complexity, nu^0(1), exists, although some implementations have been implicitly claimed to have this complexity.Downloads
Published
1991-02-01
How to Cite
Frandsen, G. S., & Sturtivant, C. (1991). What is an Efficient Implementation of the lambda-calculus?. DAIMI Report Series, 20(344). https://doi.org/10.7146/dpb.v20i344.6574
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.