CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Lambda Calculi and Linear Speedups

David Sands (Institutionen för datavetenskap) ; Jörgen Gustavsson (Institutionen för datavetenskap, Funktionell programmering) ; Andrew Keith Moran (Institutionen för datavetenskap)
The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones (2002)

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 (λχ.M) V → M[V/χ] where V is restricted to be a value rather than an arbitrary term. 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.

Denna post skapades 2013-06-14.
CPL Pubid: 178519


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap (2002-2004)
Institutionen för datavetenskap, Funktionell programmering (2002-2004)


Data- och informationsvetenskap

Chalmers infrastruktur