Lambda Calculi and Linear Speedups. Sands, D., Gustavsson, J., & Moran, A. In The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones, of LNCS. Springer Verlag, 2002.
Lambda Calculi and Linear Speedups [pdf]Paper  abstract   bibtex   
The equational theories at the core of most functional programming are variations on the standard lambda calculus. The best known of these is the call-by-value lambda calculus whose core is the value-beta computation rule. This paper investigates the transformational power of this core theory of functional programming. The main result is that the equational theory of the call-by-value lambda calculus cannot speed up (or slow down) programs by more than a constant factor. The corresponding result also holds for call-by-need but we show that it does not hold for call-byname: there are programs for which a single beta reduction can change the program's asymptotic complexity.

Downloads: 0