^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} unknown^{4} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1007/3540543961_14

Abstract:

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.

Type:

Conference paper

Language:

English

Published in:

Functional Programming Languages and Computer Architecture: 5th Acm Conference Cambridge, Ma, Usa, August 26–30, 1991 Proceedings, 1991, p. 289-312

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Lecture Notes in Computer Science

Review type:

Peer Review

Conference:

ACM Conference on Functional Programming Languages and Computer Architecture, 1991