Lambda Calculi and Linear Speedups. Sands, D.; Gustavsson, J.; and 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.
@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