In *The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones*, of *LNCS*. Springer Verlag, 2002.

Paper abstract bibtex

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.

@InCollection{Sands:Lambda02, author = {David Sands and J. Gustavsson and A. Moran}, title = {Lambda Calculi and Linear Speedups}, booktitle = {The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones}, publisher = {Springer Verlag}, year = 2002, number = 2566, series = {LNCS}, abstract = {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.}, url_Paper = {http://www.cse.chalmers.se/~dave/papers/Sands-Gustavsson-Moran.pdf} }

Downloads: 0