What is an efficient implementation of the λ-calculus?

Gudmund S. Frandsen, Carl Sturtivant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationFunctional Programming Languages and Computer Architecture - 5th ACM Conference, Proceedings
EditorsJohn Hughes
PublisherSpringer Verlag
Pages289-312
Number of pages24
ISBN (Print)9783540475996
DOIs
StatePublished - 1991
Event5th Conference on Functional Programming Languages and Computer Architecture, 1991 - Cambridge, United States
Duration: Aug 26 1991Aug 30 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume523 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th Conference on Functional Programming Languages and Computer Architecture, 1991
CountryUnited States
CityCambridge
Period8/26/918/30/91

Bibliographical note

Funding 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).

Fingerprint Dive into the research topics of 'What is an efficient implementation of the λ-calculus?'. Together they form a unique fingerprint.

Cite this