Aarhus University Seal / Aarhus Universitets segl

What is an efficient implementation of the λ-calculus?

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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.
Original languageEnglish
Title of host publicationFunctional Programming Languages and Computer Architecture : 5th ACM Conference Cambridge, MA, USA, August 26–30, 1991 Proceedings
EditorsJohn Hughes
Number of pages24
Publication year1991
Publication statusPublished - 1991
EventACM Conference on Functional Programming Languages and Computer Architecture - Cambridge, MA, United States
Duration: 26 Aug 199130 Aug 1991


ConferenceACM Conference on Functional Programming Languages and Computer Architecture
LandUnited States
ByCambridge, MA
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 36650232