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)
[Kapitel]

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)

Ämnesområden

Data- och informationsvetenskap

Chalmers infrastruktur