Ferienakademie im Sarntal 2000
Kurs 1: Formale Modelle von Programmiersprachen


Stefan Büttcher

Lambda-Kalkül mit Call by Need

Formale Programmiersprachen mit lazy evaluation implementieren den Call by Name Lambda-Kalkül. Sinnvolle Programmiersprachen mit lazy evaluation umgehen die mit Call by Name verbundene wiederholte Auswertung des selben Parameters, die ja immer das selbe Resultat liefert, dadurch, dass sie bei der ersten Auswertung das Ergebnis speichern und bei einer erneuten Auswertung lediglich auf den gespeicherten Wert zurückgreifen.
In meinem Vortrag habe ich gezeigt, wie Call by Need mit Hilfe von Lambda-Termen dargestellt werden kann und welche Reduktionsregeln zum Einsatz kommen. Schließlich habe ich eine mögliche Implementierung von Call by Need vorgestellt, die das lazy Verhalten bereits auf Sourcecode-Ebene charakterisiert.

Literatur

  • Z. Ariola, P. Wadler et al.: "A Call-By-Need Lambda Calculus"
    Principles of Programming Languages (PoPL) ‘95, 1/95
  • J. Maraist, M. Odersky, P. Wadler: "The Call-by-Need Lambda Calculus"
    Journal of Functional Programming 1998
  • D. Friedman, D. Wise: "CONS should not evaluate its arguments"
    Int. Conference on Automata, Languages and Programming (ICALP) ‘76
  • R. Stansifer: "Theorie und Entwicklung von Programmiersprachen"
    Prentice-Hall 1995
Da kommt noch ein Vortrags-Foto…