Lambda-Kalkül

Als Symbol für den Lambda-Kalkül wird das kleine Lambda, der elfte Buchstabe des griechischen Alphabets, benutzt

Der Lambda-Kalkül ist eine formale Sprache zur Untersuchung von Funktionen. Er beschreibt die Definition von Funktionen und gebundenen Parametern und wurde in den 1930er Jahren von Alonzo Church und Stephen Cole Kleene eingeführt. Heute ist er ein wichtiges Konstrukt für die Theoretische Informatik, Logik höherer Stufe und Linguistik.

Geschichte

Alonzo Church benutzte den Lambda-Kalkül, um 1936 sowohl eine negative Antwort auf das Entscheidungsproblem zu geben als auch eine Fundierung eines logischen Systems zu finden, wie es den Principia Mathematica von Bertrand Russell und Alfred North Whitehead zugrunde lag. Mittels des untypisierten Lambda-Kalküls kann man klar definieren, was eine berechenbare Funktion ist. Die Frage, ob zwei Lambda-Ausdrücke (s. u.) äquivalent sind, kann im Allgemeinen nicht algorithmisch entschieden werden. In seiner typisierten Form kann der Kalkül benutzt werden, um Logik höherer Stufe darzustellen. Der Lambda-Kalkül hat die Entwicklung funktionaler Programmiersprachen, die Forschung um Typsysteme von Programmiersprachen im Allgemeinen sowie moderne Teildisziplinen in der Logik wie die Typtheorie wesentlich beeinflusst.

Meilensteine der Entwicklung waren im Einzelnen:

Der untypisierte Lambda-Kalkül

Motivation

Ausgehend von einem mathematischen Term, wie beispielsweise x+2, lässt sich eine Funktion bilden, die x auf x+2 abbildet. Man schreibt auch x↦x+2. Beim Lambda-Kalkül geht es zunächst darum, solche Funktionsbildungen sprachlich zu formalisieren. Im Lambda-Kalkül würde man statt x↦x+2 den Term

  • λx.x+2

schreiben. Man sagt, dass die freie Variable x durch λ-Abstraktion gebunden wird. Die Variablen-Bindung kommt in der Mathematik auch in anderen Bereichen vor:

Die abstrahierte Variable muss nicht notwendigerweise im Term vorkommen, z. B. λx.2 . Dieser λ-Ausdruck bezeichnet dann die Funktion, die jedes x auf 2 abbildet. Etwas allgemeiner ist λx.y die Funktion, die konstant y ist. Wird nachträglich noch nach y abstrahiert, so erhält man mit λy.λx.y eine Formalisierung der Funktion, die jedem Wert y die Funktion zuordnet, die konstant y ist. Der Ausdruck λy.λx.y repräsentiert also eine funktionswertige Funktion. Im Lambda-Kalkül lassen sich aber auch Funktionen ausdrücken, deren Argumente bereits Funktionen sind. Nimmt man bspw. die Funktion, die jeder Funktion f eine andere Funktion f2 zuordnet, die so entsteht, dass f zweimal angewandt wird, so wird f2 durch den λ-Term λx.f(f(x)) dargestellt und die Zuordnung f↦f2 durch λf.λx.f(f(x)).

Da λ-Terme als Funktionen gesehen werden, kann man sie auf ein Argument anwenden. Man spricht von Applikation und schreibt im Lambda-Kalkül eher f x statt f(x). Klammern können Terme gruppieren. Die Applikation als Verbindungsprinzip von Termen ist definitionsgemäß linksassoziativ, d. h. f x y bedeutet (f x) y. In der üblichen mathematischen Notation würde man hier (f(x))(y) schreiben. Wendet man nun einen Lambda-Term λx.θ auf ein Argument a an, also (λx.θ) a, so berechnet sich das Ergebnis dadurch, dass in dem Term θ jedes Vorkommen der Variablen x durch a ersetzt wird. Diese Ableitungsregel nennt man β-Konversion.

λ-Terme formulieren eher allgemeine Prinzipien der Mathematik und bezeichnen nicht so sehr Objekte des üblichen mathematischen Universums. Beispielsweise formuliert λx.x das Zuordnungsprinzip der identischen Abbildung, doch diese ist immer auf eine gegebene Menge als Definitionsmenge bezogen. Eine universelle Identität als Funktion ist in der mengentheoretischen Formulierung der Mathematik nicht definiert. Der Lambda-Kalkül im strengen Sinne ist daher eher als ein Neuentwurf der Mathematik zu sehen, in dem die Grundobjekte als universelle Funktionen verstanden werden, im Gegensatz zur axiomatischen Mengenlehre, deren Grundobjekte Mengen sind.

Zahlen und Terme wie x+2 sind zunächst nicht Bestandteil eines reinen Lambda-Kalküls. Ähnlich wie in der Mengenlehre, in der man Zahlen und Arithmetik allein aus dem Mengenbegriff heraus konstruieren kann, ist es aber auch im Lambda-Kalkül möglich, auf der Basis von λ-Abstraktion und Applikation die Arithmetik zu definieren. Da im Lambda-Kalkül jeder Term als einstellige Funktion verstanden wird, muss eine Addition als die Funktion verstanden werden, die jeder Zahl y diejenige (einstellige) Funktion zuordnet, die zu jeder Zahl x den Wert y addiert (s. Currying).

Lambda-Terme ohne freie Variablen werden auch als Kombinatoren bezeichnet. Die Kombinatorische Logik (oder Kombinator-Kalkül) kann als alternativer Ansatz zum Lambda-Kalkül gesehen werden.

Formale Definition

In seiner einfachsten, dennoch vollständigen Form gibt es im Lambda-Kalkül lediglich drei Arten der Termbildung, erklärt durch die folgenden Produktionsregeln:

  1. Jedes Variablensymbol v∈{x,y,z,…} ist ein Term, kurz Variable genannt. Die Menge der verfügbaren Variablensymbole muss hierbei mindestens abzählbar-unendlich sein.
  2. Sind t1,t2 Terme, so ist auch (t1 t2) ein Term, genannt die Applikation von t1 auf t2.
  3. Ist v eine Variable und t ein Term, so ist auch (λv.t) ein Term, genannt die Abstraktion von t bezüglich v.
  4. Nichts anderes ist ein Term.

In Backus-Naur-Form notiert sich dies kurzum als:

Term ::= v | (Term Term) | (λv. Term)

Soweit die Variablensymbole hier als die einzigen Primterme (atomaren Terme) bzw. Blätter der abstrakten Syntaxbäume auftreten, wird der Lambda-Kalkül für praktische Zwecke üblicherweise noch um Konstantensymbole als zweite Art von Primtermen erweitert.

Die Menge der freien Variablen FV(t) kann induktiv über der Struktur eines λ-Terms t wie folgt definiert werden:

  1. FV(v)={v}, falls der Term eine Variable v ist
  2. FV(t1 t2)=FV(t1)∪FV(t2) für Applikationen, und
  3. FV(λv.t)=FV(t)∖{v}, falls der Term eine Abstraktion ist, sind seine freien Variablen die freien Variablen von t außer v.

Die Menge der gebundenen Variablen BV(t) eines Terms t errechnet sich auch induktiv:

  1. BV(v)=∅︀, falls der Term eine Variable v ist
  2. BV(t1 t2)=BV(t1)∪BV(t2) für Applikationen, und
  3. BV(λv.t)=BV(t)∪{v}, falls der Term eine Abstraktion ist, sind seine gebundenen Variablen die gebundenen Variablen von t vereinigt v.

Mittels der Definition von freien und gebundenen Variablen kann nun der Begriff der (freien) Variablensubstitution (Einsetzung) induktiv definiert werden durch:

  1. v[w←t]=v falls w nicht dieselbe Variable wie v ist,
  2. v[v←t]=t,
  3. (t1 t2)[v←t]=(t1[v←t] t2[v←t]),
  4. (λv.t′)[v←t]=(λv.t′),
  5. (λv.t′)[w←t]=(λv.t′[w←t]) falls w nicht dieselbe Variable wie v ist und FV(t) disjunkt von BV(λv.t′) ist.

Hierbei steht s[v←t] für den Term s, in dem jedes freie Vorkommen der Variable v durch den Term t ersetzt wurde. Falls v nicht in s vorhanden ist, wird auch nichts ersetzt. Die alternativen Schreibweisen s[t/v], s[tv] oder s[v:=t] sind ebenfalls gebräuchlich.

Beispielsweise resultiert ((λx.x) x)[x←y] im Term ((λx.x) y).

Man beachte, dass die Substitution nur partiell definiert ist; ggf. müssen gebundene Variablen geeignet umbenannt werden (siehe α-Kongruenz im Folgenden), so dass niemals eine freie Variable in einem Substitut durch Einsetzung für eine Variable gebunden wird.

Über der Menge der λ-Terme können nun Kongruenzregeln (hier ≡ geschrieben) definiert werden, die die Intuition formal fassen, dass zwei Ausdrücke dieselbe Funktion beschreiben. Diese Relationen sind durch die sogenannte α-Konversion, die β-Konversion sowie die η-Konversion erfasst.

Kongruenzregeln

α-Konversion

Die α-Konversionsregel formalisiert die Idee, dass die Namen von gebundenen Variablen „Schall und Rauch“ sind; z. B. beschreiben λx.x und λy.y dieselbe Funktion. Allerdings sind die Details nicht ganz so einfach wie es zunächst erscheint: Eine Reihe von Einschränkungen müssen beachtet werden, wenn gebundene Variablen durch andere gebundene Variablen ersetzt werden.

Formal lautet die Regel wie folgt:

(λv.t) ≡ (λw.t[v←w])

falls w in t nirgends frei vorkommt und w in t dort nicht gebunden ist, wo es ein v ersetzt. Da eine Kongruenzregel in jedem Teilterm anwendbar ist, erlaubt sie die Ableitung, dass λx.(λx.x) x gleich λy.(λx.x) y ist.

β-Konversion

Die β-Konversionsregel formalisiert das Konzept der „Funktionsanwendung“. Wird sie ausschließlich von links nach rechts angewandt, spricht man auch von β-Reduktion. Formal lässt sie sich durch

((λv.t) t′) ≡ t[v←t′]

beschreiben, wobei alle freien Variablen in t′ in t[v←t′] frei bleiben müssen (siehe Nebenbedingung bei der Substitutionsdefinition).

Ein Term heißt in β-Normalform, wenn keine β-Reduktion mehr anwendbar ist (nicht für alle Terme existiert eine β-Normalform; siehe unten). Ein tiefes Resultat von Church und Rosser über den λ-Kalkül besagt, dass die Reihenfolgen von α-Konversionen und β-Reduktionen in gewissem Sinn keine Rolle spielt: wenn man einen Term zu zwei Termen t1 und t2 ableitet, gibt es immer eine Möglichkeit, t1 und t2 jeweils zu einem gemeinsamen Term t3 abzuleiten.

η-Konversion

Die η-Konversion kann optional zum Kalkül hinzugefügt werden. Sie formalisiert das Konzept der Extensionalität, d. h., dass zwei Funktionen genau dann gleich sind, wenn sie für alle Argumente dasselbe Resultat liefern. Formal ist die η-Konversion beschrieben durch:

λx.f x ≡ f, wenn x nicht freie Variable von f ist.

Weitere Beispiele

  • Der Term λx.λy.(x y falsch⁡) ist eine Möglichkeit von vielen, die logische Funktion und darzustellen. Hierzu versteht man wahr als Abkürzung für λx.λy.x und falsch als Abkürzung für λx.λy.y. Der Term erfüllt alle Forderungen, die man an die Funktion und stellt.
    • und⁡ wahr⁡ wahr⁡ ≡def (λx.λy.(x y falsch⁡)) wahr⁡ wahr⁡ ≡ββ wahr⁡ wahr⁡ falsch⁡ ≡def (λx.λy.x) wahr⁡ falsch⁡ ≡β (λy.wahr⁡) falsch⁡ ≡β wahr
    • und⁡ wahr⁡ falsch⁡ ≡ … ≡ wahr⁡ falsch⁡ falsch⁡ ≡ … ≡ (λy.falsch⁡) falsch⁡ ≡ falsch
    • und⁡ falsch⁡ wahr⁡ ≡ falsch⁡ wahr⁡ falsch⁡ ≡ (λx.λy.y) wahr⁡ falsch⁡ ≡ (λy.y) falsch⁡ ≡ falsch
    • und⁡ falsch⁡ falsch⁡ ≡ falsch⁡ falsch⁡ falsch⁡ ≡ … ≡ (λy.y) falsch⁡ ≡ falsch
  • Man kann in ähnlicher Weise Zahlen, Tupel und Listen in λ-Ausdrücken codieren (z. B. durch sogenannte Church-Numerale)
  • Man kann beliebige rekursive Funktionen durch den Fixpunkt-Kombinator 𝐘=λg.(λx.g (x x))(λx.g (x x)) darstellen.

Typisierter Lambda-Kalkül

Die zentrale Idee des typisierten Lambda-Kalküls ist es, nur noch Lambda-Ausdrücke zu betrachten, denen sich ein Typ durch ein System von Typinferenzregeln zuordnen lässt. Das einfachste Typsystem, das von Church in seiner Theory of Simple Types vorgestellt wurde, sieht die Typen vor, die durch folgende Grammatik in Backus-Naur-Form generiert werden:

TT ::= I (Individuen) | O (Wahrheitswerte) | (TT → TT) (Funktionstypen)

Den Typ I kann man sich als Zahlen vorstellen, O wird für boolesche Werte wie Wahr und Falsch verwendet.

Zusätzlich wird eine Umgebung Γ definiert; dies ist eine Funktion, die Variablensymbolen Typen TT zuordnet.

Ein Tripel aus einer Umgebung Γ, einem Ausdruck E und einem Typ T, geschrieben Γ⊢E:T wird ein Typurteil genannt.

Nun können die Inferenzregeln Beziehungen zwischen Ausdrücken, ihren Typen und Typurteilen herstellen: Γ⊢v:Γ(v)(Variable)

Γ⊢t1:(τ1→τ2)Γ⊢t2:τ1Γ⊢(t1 t2):τ2(Applikation)

Γ[a↦τ1]⊢t:τ2Γ⊢λa.t:τ1→τ2(Abstraktion)

Hierbei ist Γ[a↦τ1] diejenige Funktion, die an der Stelle a den Typ τ1 zuordnet, und ansonsten die Funktion Γ ist. (Anders ausgedrückt: Der Parameter a der Funktion ist vom Typ τ1 und genau diese Information wird der Umgebung hinzugefügt.)

Durch Einführung einer zweiten Umgebung sind auch Konstantensymbole behandelbar; eine weitere wichtige Erweiterung besteht darin, in Typen auch die Kategorie der Typvariablen α,β,γ etc. oder Typkonstruktoren wie Menge, Liste etc. zuzulassen: so entstehen schon sehr mächtige funktionale oder logische Kernsprachen. Menge ist beispielsweise eine Funktion, die den beliebigen Typen α auf den Typ „Menge, deren Elemente vom Typ α sind“ abbildet; Liste analog; geschrieben Menge⁡(α) und Liste⁡(β), wobei auch wie gehabt die Klammern fehlen dürfen. Das Konzept kann leicht weiter abstrahiert werden, indem statt eines konkreten Typkonstruktors auch eine Variable verwendet wird, z. B. Φ(α). Typkonstruktoren dürfen allgemein auch mehrere Argumente besitzen, wie beispielsweise der Pfeil: Der Typ Pfeil⁡αβ ist nichts anderes als α→β, zeigt aber besser, dass der Pfeil ein Typkonstruktor in zwei Variablen ist. Insbesondere ist auch bei Typkonstruktoren Currying möglich, und Pfeil⁡α ist ein Typkonstruktor in einer Variablen.

Es ist entscheidbar, ob ein untypisierter Term sich typisieren lässt, selbst wenn die Umgebung Γ unbekannt ist (eine Variante mit Typvariablen und Typkonstruktoren ist der Algorithmus nach Hindley-Milner).

Die Menge der typisierbaren Ausdrücke ist eine echte Teilmenge des untypisierten Lambda-Kalküls; z. B. lässt sich der Y-Kombinator nicht typisieren. Andererseits ist für typisierte Ausdrücke die Gleichheit zwischen zwei Funktionen modulo α- und β-Konversionen entscheidbar. Es ist bekannt, dass das Matching-Problem auf Lambda-Ausdrücken bis zur vierten Ordnung entscheidbar ist. Das Unifikationsproblem ist unentscheidbar; allerdings gibt es praktisch brauchbare approximative Algorithmen.

Anwendung in der Semantik

Die Semantik ist dasjenige Teilgebiet der Linguistik, welches die Bedeutung natürlichsprachlicher Ausdrücke analysiert. Die formale Semantik nutzt dazu zunächst einfache Mittel der Prädikatenlogik und Mengenlehre. Diese erweitert man um Grundlagen des Lambda-Kalküls, etwa um mittels Lambda-Abstraktion Propositionen als Eigenschaften zu repräsentieren und komplexere Nominalphrasen, Adjektivphrasen und einige Verbalphrasen darstellen zu können. Grundlage ist etwa eine modelltheoretische semantische Interpretation der intensionalen Logik Richard Montagues.

Anwendung in der Informatik

Der Lambda-Kalkül ist auch die formale Grundlage für viele, insbesondere funktionale Programmiersprachen, wie z. B. Scheme oder Lisp. Einige Programmiersprachen bieten Konzepte wie anonyme Funktionen an, auf die sich einige der Regeln des Lambda-Kalküls anwenden lassen. Die Programmiersprachen erlauben jedoch meist mehr als der reine Lambda-Kalkül, wie beispielsweise Nebeneffekte.

Siehe auch