Open AccessWhat is an Efficient Implementation of the lambda-calculus?
Author(s) -
Gudmund Skovbjerg Frandsen,
Carl Sturtivant
Publication year - 1991
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v20i344.6574
Subject(s) - combinatory logic , implementation , lambda calculus , lambda , function (biology) , exponential function , upper and lower bounds , computer science , polynomial , mathematics , calculus (dental) , theoretical computer science , discrete mathematics , programming language , physics , medicine , mathematical analysis , dentistry , evolutionary biology , optics , biology
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.