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. 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
{"_id":"AJb4nCJZdh56by8Et","bibbaseid":"sands-gustavsson-moran-lambdacalculiandlinearspeedups-2002","downloads":0,"creationDate":"2017-02-03T08:24:26.821Z","title":"Lambda Calculi and Linear Speedups","author_short":["Sands, D.","Gustavsson, J.","Moran, A."],"year":2002,"bibtype":"incollection","biburl":"http://www.cse.chalmers.se/~dave/davewww2016.bib","bibdata":{"bibtype":"incollection","type":"incollection","author":[{"firstnames":["David"],"propositions":[],"lastnames":["Sands"],"suffixes":[]},{"firstnames":["J."],"propositions":[],"lastnames":["Gustavsson"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Moran"],"suffixes":[]}],"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","bibtex":"@InCollection{Sands:Lambda02,\n author = \t {David Sands and J. Gustavsson and A. Moran},\n title = \t {Lambda Calculi and Linear Speedups},\n booktitle = \t {The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones},\n publisher = {Springer Verlag},\n year = \t 2002,\n number = \t 2566,\n series = \t {LNCS},\n abstract = {The equational theories at the core of most functional programming\nare variations on the standard lambda calculus. The best known\nof these is the call-by-value lambda calculus whose core is the\nvalue-beta computation rule.\nThis paper investigates the transformational power of this core theory of\nfunctional programming. The main result is that the equational theory\nof the call-by-value lambda calculus cannot speed up (or slow down)\nprograms by more than a constant factor. The corresponding result also\nholds for call-by-need but we show that it does not hold for call-byname:\nthere are programs for which a single beta reduction can change\nthe program's asymptotic complexity.},\n url_Paper = \t {http://www.cse.chalmers.se/~dave/papers/Sands-Gustavsson-Moran.pdf}\n}\n\n","author_short":["Sands, D.","Gustavsson, J.","Moran, A."],"key":"Sands:Lambda02","id":"Sands:Lambda02","bibbaseid":"sands-gustavsson-moran-lambdacalculiandlinearspeedups-2002","role":"author","urls":{" paper":"http://www.cse.chalmers.se/~dave/papers/Sands-Gustavsson-Moran.pdf"},"downloads":0},"search_terms":["lambda","calculi","linear","speedups","sands","gustavsson","moran"],"keywords":[],"authorIDs":[],"dataSources":["SBHWXKotbthoEYKJv"]}