Lambda -Kalkül

Lambda -Kalkül (auch geschrieben als λ-Infinitesimalrechnung) ist ein formelles System in Mathematische Logik zum Ausdruck Berechnung basierend auf Funktion Abstraktion und Anwendung Verwenden von Variablen Bindung und Auswechslung. Es ist ein Universal Berechnungsmodell Das kann verwendet werden, um jeden zu simulieren Turing Maschine. Es wurde vom Mathematiker vorgestellt Alonzo -Kirche In den 1930er Jahren als Teil seiner Forschung zur Erforschung der Grundlagen der Mathematik.

Lambda Calculus besteht darin, Lambda -Begriffe zu konstruieren und Reduktionsvorgänge auszuführen. In der einfachsten Form von Lambda Calculus werden Begriffe nur unter Verwendung der folgenden Regeln erstellt:

Ausdrücke erzeugen wie: (λx.λy. (λz. (λx.z x) (λy.z y)) (x y)). Klammern können fallen gelassen werden, wenn der Ausdruck eindeutig ist. Für einige Anwendungen können Begriffe für logische und mathematische Konstanten und Operationen enthalten sein.

Die Reduktionsoperationen umfassen:

Wenn De Bruijn Indexierung Es wird verwendet, dann ist α-Konvertion nicht mehr erforderlich, da es keine Namenskollisionen gibt. Wenn wiederholte Anwendung der Reduktionsschritte endet schließlich, dann von der Theorem der Kirche -Rosser es wird a produzieren β-normale Form.

Variable Namen werden nicht benötigt, wenn eine universelle Lambda -Funktion verwendet wird, wie z. IOTA und JOT, die jedes Funktionsverhalten erzeugen können, indem es in verschiedenen Kombinationen auf sich selbst aufgerufen wird.

Erläuterung und Anwendungen

Lambda Calculus ist Turing vollständigdas heißt, es ist ein universelles Berechnungsmodell Das kann verwendet werden, um jeden zu simulieren Turing Maschine.^[1] Sein Namensvetter, der griechische Buchstaben Lambda (λ), wird in verwendet Lambda -Ausdrücke und Lambda -Begriffe zu bezeichnen Bindung eine Variable in a Funktion.

Lambda -Kalkül kann sein ungetarn oder tippt. In typisierten Lambda -Kalkül können Funktionen nur angewendet werden, wenn sie den "Typ" der angegebenen Eingabe "annehmen können. Typed Lambda Calculi sind schwächer als der nicht typepte Lambda -Kalkül, der das Hauptthema dieses Artikels ist, in dem Sinne, dass Typed Lambda Calculi kann weniger ausdrücken als der ungyed Calculus kann, aber dagegen tippte lambda calculi mehr Dinge, die nachgewiesen werden; in dem Einfach tippte Lambda -Kalkül Zum Beispiel ist ein Satz, dass jede Bewertungsstrategie für jede einfach typisierte Lambd-Term endet, während die Bewertung von nicht typed lambda-terms nicht enden muss. Ein Grund, warum es viele verschiedene typisierte Lambda -Kalkül gibt, war der Wunsch, mehr zu tun (was der Untyed Calculus kann), ohne aufzugeben, starke Theoreme über den Kalkül zu beweisen.

Lambda Calculus hat Anwendungen in vielen verschiedenen Bereichen in Mathematik, Philosophie,^[2] Linguistik,^[3][4] und Informatik.^[5] Lambda Calculus hat eine wichtige Rolle bei der Entwicklung des Theorie der Programmiersprachen. Funktionale Programmiersprachen Lambda Calculus implementieren. Lambda Calculus ist auch ein aktuelles Forschungsthema in Kategoriestheorie.^[6]

Geschichte

Der Lambda -Kalkül wurde vom Mathematiker eingeführt Alonzo -Kirche In den 1930er Jahren als Teil einer Untersuchung der Untersuchung der Grundlagen der Mathematik.^[7][a] Das ursprüngliche System wurde gezeigt Logisch inkonsistent 1935 wann Stephen Kleene und J. B. Rosser entwickelte die Kleene -Rosser Paradox.^[8][9]

Anschließend wurde 1936 die Kirche nur den für die Berechnung relevanten Teil isoliert und veröffentlicht, was heute als Untyped Lambda Calculus bezeichnet wird.^[10] 1940 führte er auch ein rechnerisch schwächeres, aber logisch konsistentes System ein, das als das bekannt ist Einfach tippte Lambda -Kalkül.^[11]

Bis in die 1960er Jahre, als seine Beziehung zu Programmiersprachen geklärt wurde, war der Lambda -Kalkül nur ein Formalismus. Dank an Richard Montague und die Anwendungen anderer Linguisten in der Semantik der natürlichen Sprache, der Lambda Calculus hat begonnen, einen respektablen Platz in beiden Linguistik zu genießen^[12] und Informatik.^[13]

Ursprung des Lambda -Symbols

Es gibt einige Unsicherheiten über den Grund für die Verwendung des griechischen Briefes durch die Kirche durch die Kirche Lambda (λ) als Notation zur Funktionsabteilung im Lambda-Kalkül, möglicherweise teilweise aufgrund widersprüchlicher Erklärungen durch die Kirche selbst. Nach Cardone und Hindley (2006):

Warum hat die Kirche übrigens die Notation "λ" gewählt? In [einem unveröffentlichten Brief von 1964 an Harald Dickson] erklärte er deutlich, dass er aus der Notation stammte “${\ displayStyle {\ Hat {x}}}$”Verwendet für die Klassenabstraktion von Whitehead und Russell, durch zuerst ändern "${\ displayStyle {\ Hat {x}}}$" zu "${\ displayStyle \ Land x}$"Um Funktionsabstraktion von der Klasse-Abentraktion zu unterscheiden und dann zu ändern"${\ displayStyle \ Land}$"Λ", um den Druck zu erleichtern.

Dieser Ursprung wurde auch in [Rosser, 1984, S. 338] berichtet. Andererseits teilte die Kirche in seiner späteren Jahre zwei Nachwahrer mit, dass die Wahl eher zufällig sei: Ein Symbol wurde benötigt und λ wurde zufällig ausgewählt.

Dana Scott hat diese Frage auch in verschiedenen öffentlichen Vorträgen behandelt.^[14]Scott erzählt, dass er einst eine Frage zum Ursprung des Lambda-Symbols für den ehemaligen Studenten und Schwiegersohn der Kirche, John W. Addison Jr., gestellt hat, der dann seinen Schwiegervater eine Postkarte schrieb:

Liebe Professor Kirche,

Russell hatte das IOTA -OperatorHilbert hatte das Epsilon -Operator. Warum haben Sie Lambda für Ihren Bediener gewählt?

Laut Scott bestand die gesamte Antwort der Kirche darin, die Postkarte mit der folgenden Annotation zurückzugeben: "Eeny, Meeny, Miny, Moe".

Informelle Beschreibung

Motivation

Berechnungsbare Funktionen sind ein grundlegendes Konzept in Informatik und Mathematik. Der Lambda -Kalkül liefert eine einfache Semantik Zur Berechnung können Eigenschaften der Berechnung formal untersucht werden. Der Lambda -Kalkül enthält zwei Vereinfachungen, die diese Semantik einfach machen. Die erste Vereinfachung ist, dass der Lambda Calculus Funktionen "anonym" behandelt, ohne ihnen explizite Namen zu geben. Zum Beispiel die Funktion

${\ displaystyle \ operatorname {square \ _sum} (x, y) = x^{2}+y^{2}}$

kann umgeschrieben werden in anonyme Form wie

${\ displayStyle (x, y) \ mapsto x^{2}+y^{2}}$

(was als "a) gelesen wird Tupel von x und y ist zugeordnet zu ${\ textstyle x^{2}+y^{2}}$"). In ähnlicher Weise die Funktion

${\ displayStyle \ operatorname {id} (x) = x}$

kann in anonymer Form als umgeschrieben werden als

${\ displayStyle x \ MapSto x}$

wo der Eingang einfach selbst zugeordnet ist.

Die zweite Vereinfachung ist, dass der Lambda -Kalkül nur Funktionen einer einzelnen Eingabe verwendet. Eine gewöhnliche Funktion, die zwei Eingaben erfordert, zum Beispiel die ${\ textstyle \ operatorname {square \ _sum}}$ Funktion, kann in eine äquivalente Funktion überarbeitet werden, die eine einzelne Eingabe akzeptiert, und wenn die Ausgabe zurückgibt Ein weiterer Funktion, das wiederum einen einzelnen Eingang akzeptiert. Zum Beispiel,

${\ displayStyle (x, y) \ mapsto x^{2}+y^{2}}$

kann überarbeitet werden in

${\ displaystyle x \ mapsto (y \ mapsto x^{2}+y^{2})}$

Diese Methode, bekannt als Curryingverwandelt eine Funktion, die mehrere Argumente in eine Kette von Funktionen mit jeweils ein einzelnem Argument verwandelt.

Funktionsanwendung des ${\ textstyle \ operatorname {square \ _sum}}$ Funktion zu den Argumenten (5, 2), die sofort erfolgt

${\ textstyle ((x, y) \ Mapstox x^{2}+y^{2}) (5,2)}$

${\ textstyle = 5^{2}+2^{2}}$

${\ textstyle = 29}$,

Die Bewertung der Curry -Version erfordert einen weiteren Schritt weiter

$oder$

${\ textStyle = (y \ mapsto 5^{2}+y^{2}) (2)}$ // Die Definition von ${\ displayStyle x}$ wurde mit verwendet mit ${\ displayStyle 5}$ im inneren Ausdruck. Dies ist wie eine β-Reduktion.

${\ textstyle = 5^{2}+2^{2}}$ // Die Definition von ${\ displayStyle y}$ wurde mit verwendet mit ${\ displayStyle 2}$. Auch hier ähnlich wie die β-Reduktion.

${\ textstyle = 29}$

zu dem gleichen Ergebnis kommen.

Der Lambda -Kalkül

Der Lambda -Kalkül besteht aus einer Sprache von Lambda -Begriffe, die durch eine bestimmte formale Syntax und eine Reihe von Transformationsregeln definiert werden, die die Manipulation der Lambda -Begriffe ermöglichen. Diese Transformationsregeln können als als angesehen werden Gleichungstheorie oder als ein Arbeitsdefinition.

Wie oben beschrieben, sind alle Funktionen im Lambda -Kalkül anonyme Funktionen, die keine Namen haben. Sie akzeptieren nur eine Eingabevariable mit Currying Wird verwendet, um Funktionen mehrerer Variablen zu implementieren.

Lambda -Begriffe

Die Syntax des Lambda -Kalküls definiert einige Ausdrücke als gültige Lambda -Kalkül und andere als ungültig, genau wie einige Zeichenketten gültig sind C Programme und einige sind nicht. Ein gültiger Ausdruck von Lambda Calculus wird als "Lambda -Term" bezeichnet.

Die folgenden drei Regeln geben eine Induktive Definition Dies kann angewendet werden, um alle syntaktisch gültigen Lambda -Begriffe zu erstellen:

• eine Variable, x, ist selbst ein gültiger Lambda -Begriff
• wenn t ist ein Lambda -Begriff und x ist dann eine Variable ${\ displayStyle (\ lambda x.t)}}$ (manchmal geschrieben in ASCII wie ${\ displayStyle lx.t}$) ist ein Lambda -Begriff (genannt Abstraktion);
• wenn t und s sind dann Lambda -Begriffe ${\ displayStyle (ts)}}$ ist ein Lambda -Begriff (genannt Anwendung).

Nichts anderes ist ein Lambda -Begriff. Somit ist ein Lambda -Term nur dann gültig, wenn er durch wiederholte Anwendung dieser drei Regeln erhalten werden kann. Einige Klammern können jedoch nach bestimmten Regeln weggelassen werden. Zum Beispiel sind die äußersten Klammern normalerweise nicht geschrieben. Sehen Notation, unter.

Ein Abstraktion ${\ displaystyle \ lambda x.t}$ ist eine Definition einer anonymen Funktion, die in der Lage ist, eine einzelne Eingabe zu erhalten x und ersetzen es in den Ausdruck t. Es definiert somit eine anonyme Funktion, die dauert x und kehrt zurück t. Zum Beispiel, ${\ displaystyle \ lambda x.x^{2} +2}$ ist eine Abstraktion für die Funktion ${\ displayStyle f (x) = x^{2} +2}$ Verwenden des Begriffs ${\ displaystyle x^{2} +2}$ zum t. Die Definition einer Funktion mit einer Abstraktion "legt" lediglich die Funktion "fest", ruft sie jedoch nicht auf. Die Abstraktion bindet Die Variable x im Begriff t.

Ein Anwendung ts repräsentiert die Anwendung einer Funktion t zu einem Eingang sDas heißt, es repräsentiert den Akt der Aufruffunktion t auf Eingabe s produzieren ${\ displayStyle t (s)}$.

Es gibt kein Konzept im Lambda -Kalkül der variablen Deklaration. In einer Definition wie z. ${\ displaystyle \ lambda x.x+y}$ (d.h. ${\ displayStyle f (x) = x+y}$) Die Lambda -Kalkül behandelt y als eine Variable, die noch nicht definiert ist. Die Abstraktion ${\ displaystyle \ lambda x.x+y}$ ist syntaktisch gültig und repräsentiert eine Funktion y.

Eine Klammerung kann verwendet werden und können benötigt werden, um Begriffe zu disambiguieren. Zum Beispiel, ${\ displaystyle \ lambda x. ((\ lambda x.x) x)}$ und ${\ displayStyle (\ lambda x. (\ lambda x.x)) x}$ bezeichnen unterschiedliche Begriffe (obwohl sie zufällig auf denselben Wert reduzieren). Hier definiert das erste Beispiel eine Funktion, deren Lambda -Term das Ergebnis der Anwendung von X auf die untergeordnete Funktion ist, während das zweite Beispiel die Anwendung der äußersten Funktion auf die Eingabe x ist, die die untergeordnete Funktion zurückgibt.^{[Klarstellung erforderlich]} Daher bewerten beide Beispiele auf die Identitätsfunktion ${\ displaystyle \ lambda x.x}$.

Funktionen, die bei Funktionen wirken

In Lambda Calculus werden Funktionen als 'angesehen' angesehen.Erste Klasse Werte', so können Funktionen als Eingänge verwendet werden oder als Ausgänge aus anderen Funktionen zurückgegeben werden.

Zum Beispiel, ${\ displaystyle \ lambda x.x}$ repräsentiert die Identitätsfunktion, ${\ displayStyle x \ MapSto x}$, und ${\ displayStyle (\ lambda x.x) y}$ repräsentiert die Identitätsfunktion, die auf angewendet wird ${\ displayStyle y}$. Des Weiteren, ${\ displayStyle (\ lambda x.y)}}$ repräsentiert die Konstante Funktion ${\ displayStyle x \ MapSto y}$, die Funktion, die immer zurückgibt ${\ displayStyle y}$, egal die Eingabe. In Lambda Calculus wird die Funktionsanwendung als angesehen als links-assoziativ, so dass ${\ displayStyle stx}$ meint ${\ displayStyle (st) x}$.

Es gibt mehrere Vorstellungen von "Äquivalenz" und "Reduktion", die es ermöglichen, dass Lambda -Begriffe auf "äquivalente" Lambda -Begriffe "reduziert" werden.

Alpha -Äquivalenz

Eine grundlegende Form der Äquivalenz, die zu Lambda -Termen definierbar ist, ist die Alpha -Äquivalenz. Es erfasst die Intuition, dass die bestimmte Wahl einer gebundenen Variablen in einer Abstraktion (normalerweise) nicht von Bedeutung ist. Zum Beispiel, ${\ displaystyle \ lambda x.x}$ und ${\ displaystyle \ lambda y.y}$ sind alphaäquivalente lambda-Begriffe und beide repräsentieren dieselbe Funktion (die Identitätsfunktion). Die Begriffe ${\ displayStyle x}$ und ${\ displayStyle y}$ sind nicht alpha-äquivalent, weil sie nicht in einer Abstraktion gebunden sind. In vielen Präsentationen ist es üblich, Alpha-äquivalente Lambda-Begriffe zu identifizieren.

Die folgenden Definitionen sind erforderlich, um die β-Reduktion definieren zu können:

Freie Variablen

(Freie Variablen in der Lambda -Notation und deren Kalkül sind vergleichbar mit gleichnamige lineare Algebra und mathematische Konzepte))

Das freie Variablen eines Begriffs sind jene Variablen, die nicht an eine Abstraktion gebunden sind. Der Satz freier Variablen eines Ausdrucks wird induktiv definiert:

• Die freien Variablen von ${\ displayStyle x}$ sind nur ${\ displayStyle x}$
• Das einstellen von freien Variablen von ${\ displaystyle \ lambda x.t}$ ist der Satz freier Variablen von ${\ displayStyle t}$, aber mit ${\ displayStyle x}$ ENTFERNT
• Das einstellen von freien Variablen von ${\ displayStyle ts}$ ist die Vereinigung der freien Variablen von ${\ displayStyle t}$ und die Menge der freien Variablen von ${\ displayStyle S}$.

Zum Beispiel der Lambda -Begriff, der die Identität darstellt ${\ displaystyle \ lambda x.x}$ hat keine freien Variablen, aber die Funktion ${\ displaystyle \ lambda x.yx}$ hat eine einzige freie Variable, ${\ displayStyle y}$.

Erfassungsvermeidungsersatz

Eine systematische Änderung der Variablen, um die Erfassung einer freien Variablen zu vermeiden, kann Fehler einführenIn einer funktionalen Programmiersprache, in der Funktionen erstklassige Bürger sind.^[15]

Vermuten ${\ displayStyle t}$, ${\ displayStyle S}$ und ${\ displayStyle r}$ sind Lambda -Begriffe und ${\ displayStyle x}$ und ${\ displayStyle y}$ sind Variablen. Die Notation ${\ displayStyle t [x: = r]}$ zeigt die Ersetzung von ${\ displayStyle r}$ zum ${\ displayStyle x}$ in ${\ displayStyle t}$ in einem Einfang-Vermeidung Benehmen. Dies ist so definiert, dass:

• ${\ displayStyle x [x: = r] = r}$; ${\ displayStyle x}$ Ersetzt durch ${\ displayStyle r}$ ist nur ${\ displayStyle r}$
• ${\ displayStyle y [x: = r] = y}$ wenn ${\ displayStyle x \ neq y}$; ${\ displayStyle x}$ Ersetzt durch ${\ displayStyle r}$ Beim Umgang mit ${\ displayStyle y}$ ist nur ${\ displayStyle y}$
• ${\ displayStyle (ts) [x: = r] = (t [x: = r]) (s [x: = r])}$; Die Substitution verteilt sich auf eine weitere Anwendung der Variablen
• ${\ displayStyle (\ lambda x.t) [x: = r] = \ lambda x.t}$; obwohl ${\ displayStyle x}$ wurde zu kartiert ${\ displayStyle r}$anschließend alle zuordnen ${\ displayStyle x}$ zu ${\ displayStyle t}$ wird die Lambda -Funktion nicht ändern ${\ displayStyle (\ lambda x.t)}}$
• ${\ displayStyle (\ lambda y.t) [x: = r] = \ lambda y. (t [x: = r])}$ wenn ${\ displayStyle x \ neq y}$ und ${\ displayStyle y}$ ist nicht in den freien Variablen von ${\ displayStyle r}$. Die Variable ${\ displayStyle y}$ soll "frisch" sein für ${\ displayStyle r}$.

Zum Beispiel, ${\ displayStyle (\ lambda x.x) [y: = y] = \ lambda x. (x [y: = y]) = \ lambda x.x}$, und ${\ displayStyle ((\ lambda x.y) x) [x: = y] = ((\ lambda x.y) [x: = y]) (x [x: = y]) = (\ lambda x.y) y}$.

Der Frischezustand (das erfordert das ${\ displayStyle y}$ ist nicht in den freien Variablen von ${\ displayStyle r}$) ist entscheidend, um sicherzustellen, dass die Substitution die Bedeutung von Funktionen nicht ändert. Zum Beispiel wird eine Substitution hergestellt, die die Frische -Bedingung ignoriert, kann zu Fehlern führen: ${\ displayStyle (\ lambda x.y) [y: = x] = \ lambda x. (y [y: = x]) = \ lambda x.x}$. Diese Substitution macht die konstante Funktion ${\ displaystyle \ lambda x.y}$ in die Identität ${\ displaystyle \ lambda x.x}$ durch Substitution.

Im Allgemeinen kann das Versäumnis, den Ersatzzustand zu erfüllen, durch Alpha-Renennen mit einer geeigneten frischen Variablen behoben werden. Zum Beispiel zurück zu unserem korrekten Substitutionsbegriff in ${\ displayStyle (\ lambda x.y) [y: = x]}$ Die Abstraktion kann mit einer neuen Variablen umbenannt werden ${\ displayStyle z}$, erhalten ${\ displayStyle (\ lambda z.y) [y: = x] = \ lambda z. (y [y: = x]) = \ lambda z.x}$und die Bedeutung der Funktion wird durch Substitution bewahrt.

β-Reduktion

Die β-Reduktionsregel besagt, dass eine Anwendung der Form ${\ displayStyle (\ lambda x.t) s}$ reduziert sich auf den Begriff ${\ displayStyle t [x: = s]}$. Die Notation ${\ displayStyle (\ lambda x.t) s \ to t [x: = s]}$ wird verwendet, um das anzuzeigen ${\ displayStyle (\ lambda x.t) s}$ β-reduziert ${\ displayStyle t [x: = s]}$. Zum Beispiel für jeden ${\ displayStyle S}$, ${\ displayStyle (\ lambda x.x) s \ bis x [x: = s] = s}$. Dies zeigt das ${\ displaystyle \ lambda x.x}$ Wirklich ist die Identität. Ähnlich, ${\ displayStyle (\ lambda x.y) s \ to y [x: = s] = y}$das demonstriert das ${\ displaystyle \ lambda x.y}$ ist eine konstante Funktion.

Der Lambda -Kalkül kann als idealisierte Version einer funktionalen Programmiersprache angesehen werden Haskell oder Standard ml. Nach dieser Ansicht entspricht die β-Reduktion einem rechnerischen Schritt. Dieser Schritt kann durch zusätzliche β-Reduktionen wiederholt werden, bis keine mehr Anwendungen mehr zu reduzieren sind. In der hier vorgestellten Lambda -Kalkül, wie hier dargestellt, kann dieser Reduktionsprozess nicht enden. Betrachten Sie beispielsweise den Begriff ${\ displayStyle \ Omega = (\ lambda x.xx) (\ lambda x.xx)}$. Hier ${\ displayStyle (\ lambda x.xx) (\ lambda x.xx) \ to (xx) [x: = \ lambda x.xx] = (x [x: = \ lambda x.xx]) (x [x : = \ lambda x.xx]) = (\ lambda x.xx) (\ lambda x.xx)}$. Das heißt, der Begriff reduziert sich in einer einzelnen β-Reduktion auf sich selbst, und daher wird der Reduktionsprozess niemals enden.

Ein weiterer Aspekt des nicht typed Lambda -Kalküls ist, dass sie nicht zwischen verschiedenen Arten von Daten unterscheidet. Zum Beispiel kann es wünschenswert sein, eine Funktion zu schreiben, die nur auf Zahlen arbeitet. In der nicht typed Lambda -Kalkül gibt es jedoch keine Möglichkeit, zu verhindern, dass eine Funktion angewendet wird Wahrheitswerte, Saiten oder andere nicht nummerierte Objekte.

Formale Definition

Definition

Lambda -Ausdrücke bestehen aus:

• Variablen v₁, v₂, ...;
• Die Abstraktionssymbole λ (Lambda) und. (Punkt);
• Klammern ().

Die Menge der Lambda -Ausdrücke, Λ, kann sein induktiv definiert:

1. Wenn x ist dann eine Variable x ∈ λ.
2. Wenn x ist eine Variable und M ∈ λ, dann (λx.M) ∈ λ.
3. Wenn M, N ∈ λ, dann (M n) ∈ λ.

Fälle von Regel 2 sind als bekannt als als Abstraktionen und Fälle von Regel 3 sind als bekannt als Anwendungen.^[16][17]

Notation

Um die Notation von Lambda -Ausdrücken zu behalten, werden normalerweise die folgenden Konventionen angewendet:

• Die äußersten Klammern werden fallen gelassen: M N Anstatt von (M N).
• Es wird angenommen, dass Anträge assoziativ bleiben: M N P kann geschrieben anstelle von (((M N) P).^[18]
• Der Körper einer Abstraktion erstreckt sich so weit rechts wie möglich: λx.M n bedeutet λx. (M n) und nicht (λx.M) N.
• Eine Folge von Abstraktionen ist vertraglich: λx.λy.λz.N wird als λ abgekürztxyz.N.^[19][18]

Freie und gebundene Variablen

Der Abstraktionsoperator λ soll seine Variable binden, wo immer sie im Körper der Abstraktion auftritt. Variablen, die in den Umfang einer Abstraktion fallen gebunden. In einem Ausdruck λx.M, der Teil λx wird oft genannt Bindemittelals Hinweis darauf, dass die Variable x wird durch λ gebundenx zu M. Alle anderen Variablen werden genannt frei. Zum Beispiel im Ausdruck λy.x x y, y ist eine gebundene Variable und x ist eine kostenlose Variable. Auch eine Variable ist an ihre nächste Abstraktion gebunden. Im folgenden Beispiel das einzelne Vorkommen von x im Ausdruck ist an das zweite Lambda gebunden: λx.y (λx.z x).

Der Satz von freie Variablen eines Lambda -Ausdrucks, M, wird als FV bezeichnet (M) und wird durch Rekursion auf der Struktur der Begriffe definiert, wie folgt:

1. Fv (x) = {x}, wo x ist eine Variable.
2. FV (λx.M) = Fv (M) \ {x}.
3. Fv (M n) = Fv (M) ∪ fv (N).^[20]

Ein Ausdruck, der keine freien Variablen enthält abgeschlossen. Geschlossene Lambda -Ausdrücke sind auch als bekannt als Kombinatoren und sind gleichbedeutend mit Begriffen in Kombinationslogik.

Die Ermäßigung

Die Bedeutung von Lambda -Ausdrücken wird dadurch definiert, wie Ausdrücke reduziert werden können.^[21]

Es gibt drei Arten von Reduktion:

• α-Konvertion: Ändern gebundener Variablen;
• β-Reduktion: Funktionen auf ihre Argumente anwenden;
• η-Reduktion: was einen Begriff der Erweiterung erfasst.

Wir sprechen auch von den resultierenden Äquivalenzen: zwei Ausdrücke sind αäquivalent, wenn sie in den gleichen Expression α-konvertiert werden können. β-Äquivalenz und η-Äquivalenz werden ähnlich definiert.

Der Begriff Redex, kurz für reduzierbarer Ausdruck, bezieht sich auf Subterms, die durch eine der Reduktionsregeln reduziert werden können. Zum Beispiel (λx.M) N ist ein β-reDex bei der Expression der Substitution von N zum x in M. Der Ausdruck, auf den sich ein Redex reduziert reduzieren; die Redukte von (λx.M) N ist M[x: = N].

Wenn x ist nicht frei in M, λx.M x ist auch ein η-reDex mit einer Reduktion von M.

α-Konvertion

α-Konvertion, manchmal als α-Ren darauf bezeichnet,^[22] Ermöglicht die Änderung von gebundenen Variablennamen. Zum Beispiel α-Konversion von λx.x könnte λ ergebeny.y. Begriffe, die sich nur durch α-Konvertion unterscheiden, werden genannt αäquivalent. Bei Verwendung von Lambda-Kalkül werden α-äquivalente Begriffe häufig als gleichwertig angesehen.

Die genauen Regeln für die α-Konversion sind nicht vollständig trivial. Erstens sind bei α-Konvertieren einer Abstraktion die einzigen variablen Ereignisse, die umbenannt werden, diejenigen, die an die gleiche Abstraktion gebunden sind. Zum Beispiel eine α-Konversion von λx.λx.x könnte zu λ führeny.λx.x, aber es könnte nicht führen zu λy.λx.y. Letzteres hat eine andere Bedeutung als das Original. Dies ist analog zum Programmierbegriff von variabler Schatten.

Zweitens ist eine α-Konversion nicht möglich, wenn eine Variable durch eine andere Abstraktion erfasst wird. Zum Beispiel, wenn wir ersetzen x mit y in λx.λy.xwir bekommen λy.λy.y, was überhaupt nicht gleich ist.

In Programmiersprachen mit statischer Anwendung kann α-Konvertion verwendet werden, um zu machen Namensauflösung einfacher, indem Sie sicherstellen, dass kein variabler Name Masken ein Name in einem enthaltenden Umfang (sehen α-renanning, um die Namensauflösung trivial zu machen).

In dem De Bruijn Index Notation, zwei α-äquivalente Begriffe sind syntaktisch identisch.

Auswechslung

Substitution, geschrieben M[V: = N], ist der Prozess des Ersetzens aller frei Vorkommen der Variablen V im Ausdruck M mit Ausdruck N. Die Substitution nach den Bedingungen des Lambda -Kalküls wird durch Rekursion zur Struktur der Begriffe definiert (Hinweis: x und y sind nur Variablen, während m und n ein lambda -Ausdruck sind):

x[x: = N] = N

y[x: = N] = y, wenn x ≠ y

(M₁ M₂) [x: = N] = M₁[x: = N] M₂[x: = N]

(λx.M) [x: = N] = λx.M

(λy.M) [x: = N] = λy. (M[x: = N]), wenn x ≠ y und y ∉ fv (N)

Um eine Abstraktion zu ersetzen, ist es manchmal notwendig, die Expression α zu konvertieren. Zum Beispiel ist es nicht richtig für (λx.y) [y: = x] um λ zu führenx.x, weil der Substituierte x Sollte frei sein, wurde aber gebunden. Die korrekte Substitution in diesem Fall ist λz.x, bis zu α-Äquivalenz. Die Substitution wird bis zu α-Äquivalenz eindeutig definiert.

β-Reduktion

Die β-Reduktion erfasst die Idee der Funktionsanwendung. Die β-Reduktion ist in Bezug auf die Substitution definiert: die β-Reduktion von (λV.M) N ist M[V: = N].

Beispielsweise haben wir unter der Annahme einer gewissen Codierung von 2, 7, × die folgende β-Reduktion: (λn.n × 2) 7 → 7 × 2.

Die β-Reduktion ist als das gleiche wie das Konzept von Lokale Reduzierbarkeit in natürlicher Abzugüber die Curry -Howard Isomorphismus.

η-Reduktion

η-Reduktion drückt die Idee von aus Verlängerung, was in diesem Zusammenhang ist, dass zwei Funktionen gleich sind dann und nur dann, wenn Sie geben das gleiche Ergebnis für alle Argumente. η-Reduktion Konvertiert zwischen λx.f x und f Wann immer x erscheint nicht kostenlos in f.

Die η-Reduktion ist als das gleiche wie das Konzept von lokale Vollständigkeit in natürlicher Abzugüber die Curry -Howard Isomorphismus.

Normale Formen und Zusammenfluss

Für den ungyed Lambda Calculus β-Reduktion als a Regel umschreiben ist weder stark normalisieren Noch schwach normalisieren.

Es kann jedoch gezeigt werden, dass die β-Reduktion ist konfluent Bei der Arbeit bis zur α-Konvertion (d. H. Wir betrachten zwei normale Formen als gleich, wenn es möglich ist, α in die andere zu konvertieren).

Daher haben sowohl normalisierende Begriffe als auch schwach normalisierende Begriffe eine einzigartige normale Form. Für stark normalisierende Begriffe wird jede Verringerungsstrategie garantiert die normale Form ergeben, während für schwach normalisierende Begriffe einige Reduktionsstrategien möglicherweise nicht finden.

Datenatypen codieren

Der grundlegende Lambda -Kalkül kann zum Modellieren von Booleschen verwendet werden. Arithmetik, Datenstrukturen und Rekursion, wie in den folgenden Unterabschnitten dargestellt.

Arithmetik im Lambda -Kalkül

Es gibt verschiedene Möglichkeiten, um das zu definieren natürliche Zahlen In Lambda Calculus, aber bei weitem am häufigsten sind die Kirchliche Ziffern, was wie folgt definiert werden kann:

0: = λf.λx.x

1: = λf.λx.f x

2: = λf.λx.f (f x)

3: = λf.λx.f (f (f x))

usw. Oder unter Verwendung der oben dargestellten alternativen Syntax in Notation:

0: = λfx.x

1: = λfx.f x

2: = λfx.f (f x)

3: = λfx.f (f (f x))

Eine kirchliche Ziffer ist a Funktion höherer Ordnung-Es übernimmt eine Einzelargument-Funktion fund gibt eine weitere Einzelargument-Funktion zurück. Die Kirchenzumal n ist eine Funktion, die eine Funktion nimmt f als Argument und gibt die zurück n-TH -Komposition von f, d.h. die Funktion f mit sich selbst komponiert n mal. Dies wird bezeichnet f⁽ⁿ⁾ und ist in der Tat das n-Th Kraft von f (als Operator betrachtet); f⁽⁰⁾ ist definiert als Identitätsfunktion. Solche wiederholten Zusammensetzungen (einer einzelnen Funktion f) gehorchen dem Gesetze von ExponentenAus diesem Grund können diese Ziffern für die Arithmetik verwendet werden. (Im ursprünglichen Lambda -Kalkül der Kirche war der formale Parameter eines Lambda -Ausdrucks mindestens einmal in der Funktionskörper erforderlich, die die obige Definition von machte 0 unmöglich.)

Eine Denkweise über die Kirchenzumal n, was bei der Analyse von Programmen häufig nützlich ist, ist als Anweisung "Wiederholung" n mal'. Zum Beispiel die Verwendung der PAAR und NULL Im Folgende definierte Funktionen können Sie eine Funktion definieren, die eine (verknüpfte) Liste von konstruiert n Elemente sind alle gleich zu x durch Wiederholung 'vorbereiten Sie einen anderen vor x Element' n Zeiten aus einer leeren Liste. Der Lambda -Begriff ist

λn.λx.n (PAAR x) Nil

Durch die Variation des Wiederholens und das Variieren des Arguments, auf das die Funktion wiederholt wird, wird sehr viele verschiedene Effekte erreicht.

Wir können eine Nachfolgerfunktion definieren, die eine Kirchenzumal nimmt n und kehrt zurück n + 1 durch Hinzufügen einer weiteren Anwendung von f, wobei '(mf) x' bedeutet, dass die Funktion 'f' auf 'x' "m" angewendet wird:

SUCK: = λn.λf.λx.f (n f x)

Weil die m-TH -Komposition von f komponiert mit dem n-TH -Komposition von f gibt die m+n-TH -Komposition von fAddition kann wie folgt definiert werden:

Plus: = λm.λn.λf.λx.m f (n f x)

PLUS kann als eine Funktion betrachtet werden, die zwei natürliche Zahlen als Argumente nimmt und eine natürliche Zahl zurückgibt; Es kann überprüft werden, dass

Plus 2 3

und

5

sind β-äquivalente Lambda-Ausdrücke. Seit Hinzufügen m zu einer Nummer n Kann durch Hinzufügen von 1 erreicht werden m Zeiten, eine alternative Definition ist:

Plus: = λm.λn.m Succ n^[23]

In ähnlicher Weise kann eine Multiplikation definiert werden als

Mult: = λm.λn.λf.m (n f)^[19]

Alternative

Mult: = λm.λn.m (PLUS n) 0

seitdem multiplizieren m und n ist dasselbe wie das Wiederholen des Hinzufügens n Funktion m Zeiten und dann auf Null anwenden. Exponentiation hat ein ziemlich einfaches Rendering in Kirchen Ziffern, nämlich

Pow: = λb.λe.e b^[20]

Die Vorgängerfunktion definiert durch Pred n = n - 1 für eine positive Ganzzahl n und Pred 0 = 0 ist wesentlich schwieriger. Die Formel

Pred: = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)

kann validiert werden, indem induktiv angezeigt wird, wenn T bezeichnet (λg.λh.h (g f)), dann T⁽ⁿ⁾(λu.x) = (λh.h(f^(n–1)(x))) zum n > 0. Zwei weitere Definitionen von Pred werden unten angegeben, einer verwendet Bedingungen und der andere benutzt Paare. Mit der Vorgängerfunktion ist die Subtraktion unkompliziert. Definition

Sub: = λm.λn.n Pred m,

Sub m n ergibt m − n Wenn m > n und 0 Andernfalls.

Logik und Prädikate

Nach Konvent STIMMT und FALSCH:

Richtig: = λx.λy.x

Falsch: = λx.λy.y

(Beachten Sie, dass FALSCH entspricht der oben definierten Kirche.

Mit diesen beiden Lambda -Begriffen können wir dann einige Logikoperatoren definieren (dies sind nur mögliche Formulierungen; andere Ausdrücke sind gleichermaßen korrekt):

Und: = λp.λq.p q p

Oder: = λp.λq.p p q

Nicht: = λp.p FALSCH RICHTIG

Iftenelse: = λp.λa.λb.p a b

Wir sind jetzt in der Lage, einige Logikfunktionen zu berechnen, zum Beispiel:

Und wahres Falsch

≡ (λp.λq.p q p) Richtig Falsch →_β Richtig Falsch wahr

≡ (λx.λy.x) Falsch wahr →_β FALSCH

Und das sehen wir Und wahres Falsch ist äquivalent zu FALSCH.

A Prädikat ist eine Funktion, die einen booleschen Wert zurückgibt. Das grundlegendste Prädikat ist Iszero, was zurückkehrt STIMMT Wenn ihr Argument die Kirchenzumal ist 0, und FALSCH Wenn ihr Argument eine andere kirchliche Ziffer ist:

Iszero: = λn.n (λx.FALSCH RICHTIG

Die folgenden Prädikatetests, ob das erste Argument weniger als oder gleicher ist: das zweite:

Leq: = λm.λn.Iszero (sub m n),

und da m = n, wenn Leq m n und Leq n mEs ist unkompliziert, ein Prädikat für die numerische Gleichheit zu erstellen.

Die Verfügbarkeit von Prädikaten und die obige Definition von STIMMT und FALSCH Machen Sie es bequem, "if-then-else" -Auskörper in Lambda-Kalkül zu schreiben. Beispielsweise kann die Vorgängerfunktion definiert werden als:

Pred: = λn.n (λg.λk.Iszero (g 1) k (PLUS (g k) 1)) (λv.0) 0

was überprüft werden kann, indem das induktiv gezeigt wird n (λg.λk.Iszero (g 1) k (PLUS (g k) 1)) (λv.0) ist das Hinzufügen n - 1 Funktion für n > 0.

Paare

Ein Paar (2-Tupel) kann in Bezug auf das definiert werden STIMMT und FALSCHdurch Verwendung der Kirchenkodierung für Paare. Zum Beispiel, PAAR Kapuliert das Paar (x,y), ERSTE Gibt das erste Element des Paares zurück und ZWEITE Gibt die zweite zurück.

Paar: = λx.λy.λf.f x y

Erstens: = λp.p STIMMT

Zweitens: = λp.p FALSCH

Nil: = λx.STIMMT

NULL: = λp.p (λx.λy.FALSCH)

Eine verknüpfte Liste kann entweder als NIL für die leere Liste oder als die definiert werden PAAR eines Elements und einer kleineren Liste. Das Prädikat NULL Tests für den Wert NULL. (Alternativ mit Nil: = falsch, das Konstrukt l (λh.λt.λz.deal_with_head_h_and_tail_t) (Deal_with_nil) vermeidet die Notwendigkeit eines expliziten Nulltests).

Als Beispiel für die Verwendung von Paaren ist die Schalt- und Inkrementfunktion, die kartiert (m, n) zu (n, n + 1) kann definiert werden als

Φ: = λx.Pair (zweite x) (Succ (Sekunde x))

Dies ermöglicht es uns, die vielleicht transparenteste Version der Vorgängerfunktion zu geben:

Pred: = λn.ERSTE (n Φ (Paar 0 0)).

Zusätzliche Programmierungstechniken

Es gibt einen beträchtlichen Teil von Programmierende Redewendungen Für Lambda -Kalkül. Viele davon wurden ursprünglich im Kontext der Verwendung von Lambda Calcül als Grundlage für die Verwendung von Lambda entwickelt Programmiersprache Semantikeffektiv unter Verwendung von Lambda -Kalkül als Programmiersprache mit niedriger Ebene. Da mehrere Programmiersprachen den Lambda -Kalkül (oder etwas sehr Ähnliches) als Fragment enthalten, sehen diese Techniken auch die Verwendung in der praktischen Programmierung, können dann jedoch als dunkel oder fremd wahrgenommen werden.

Genannte Konstanten

In lambda calculus, a Bibliothek Würde die Form einer Sammlung zuvor definierter Funktionen annehmen, die als Lambda-TERMS nur bestimmte Konstanten sind. Der reine Lambda-Kalkül hat kein Konzept von benannten Konstanten, da alle atomaren Lambda-Therms Variablen sind, aber man kann emulieren, indem man Konstanten benannte, indem man eine Variable als Name der Konstante beiseite legen, wobei die Abstraktion diese Variable im Hauptkörper binden und wenden Sie diese Abstraktion auf die beabsichtigte Definition an. Also zu verwenden f meinen M (einige explizite lambda-Term) in N (Ein weiterer Lambda-Term, das "Hauptprogramm"), kann man sagen

(λf.N ) M

Autoren führen oft vor syntethischer Zucker, wie zum Beispiel Lassenund das Schreiben des oben genannten in der intuitiveren Reihenfolge zu erlauben

Lassen f =M in N

Durch die Verkettung solcher Definitionen kann man ein Lambda Calculus "Programm" als Null- oder mehr Funktionsdefinitionen schreiben, gefolgt von einer Lambda-Term mit den Funktionen, die den Hauptteil des Programms darstellen.

Eine bemerkenswerte Einschränkung davon Lassen ist das der Name f ist nicht definiert in M, seit M liegt außerhalb des Rahmens der Abstraktionsbindung f; Dies bedeutet, dass eine rekursive Funktionsdefinition nicht als die verwendet werden kann M mit Lassen. Desto fortgeschrittener letrec Die syntaktische Zuckerkonstruktion, mit der das Schreiben rekursiger Funktionsdefinitionen in diesem naiven Stil stattdessen Fixpunktkombinatoren verwendet.

Rekursion und Fixpunkte

Rekursion ist die Definition einer Funktion mit der Funktion selbst. Lambda Calculus kann dies nicht als direkt ausdrücken wie einige andere Notationen: Alle Funktionen sind in Lambda Calculus anonym. Daher können wir uns nicht auf einen Wert beziehen, der noch definiert werden muss, innerhalb des Lambda -Begriffs, der denselben Wert definiert. Die Rekursion kann jedoch weiterhin erreicht werden (λx.x x) E.

Bedenke die Fakultät Funktion F(n) rekursiv definiert durch

F(n) = 1, wenn n = 0; anders n × f (n - 1).

Im Lambda -Ausdruck, der diese Funktion darstellen soll, a Parameter (In der Regel wird angenommen, dass der Lambda -Ausdruck selbst als Wert erhalten wird, so dass das Aufrufen - ihn auf ein Argument anwendet - der Rekursion ausmacht. Um eine Rekursion zu erreichen, das beabsichtigte Argument für Selbstverweise (genannt r hier) muss immer an sich selbst innerhalb des Funktionskörpers an einem Anruf übergeben werden:

G: = λr. λn. (1, wenn n = 0; anders n × (r r (n–1)))

mit r r x = F x = G r x so halten, so r = G und

F: = g g = (λx.x x) G

Die Selbstanwendung erreicht hier die Replikation und überträgt den Lambda-Ausdruck der Funktion auf den nächsten Aufruf als Argumentwert, wodurch sie zur Verfügung stellt, um zu referenzieren und dort aufgerufen zu werden.

Dies löst es, muss jedoch jeden rekursiven Aufruf als Selbstanwendung neu geschrieben werden. Wir möchten eine generische Lösung haben, ohne dass Re-Writes erforderlich ist:

G: = λr. λn. (1, wenn n = 0; anders n × (r (n–1)))

mit r x = F x = G r x so halten, so r = G r =: Fix g und

F: = fix g wo FIX g: = ((r wo r = g r) = g (FIX g)

so dass Fix g = g (Fix g) = (λn. (1, wenn n = 0; anders n × ((Fix G) (Fix) (n–1))))

Bei einem Lambda -Term mit erstem Argument, das einen rekursiven Aufruf darstellt (z. G hier die Fixpunkt Kombinator FIX wird einen selbstreplizierenden Lambda-Ausdruck zurückgeben, der die rekursive Funktion darstellt (hier,, F). Die Funktion muss zu keinem Zeitpunkt ausdrücklich an sich selbst übergeben werden, da die Selbstreplikation im Voraus angeordnet ist, wenn sie erstellt wird, um jedes Mal zu erfolgen, wenn sie aufgerufen wird. Somit der ursprüngliche Lambda -Ausdruck (Fix G) wird in sich selbst neu erstellt, bei Call-Point, erreicht Selbstreferenz.

Tatsächlich gibt es dafür viele mögliche Definitionen FIX Operator, der einfachste von ihnen ist:

Y: = λg. (λx.g (x x)) (λx.g (x x))

Im Lambda -Kalkül, Y gist ein fester Punkt von g, wie es sich ausdehnt zu:

Y g

(λh. (λx.h (x x)) (λx.h (x x))) g

(λx.g (x x)) (λx.g (x x))

g ((λx.g (x x)) (λx.g (x x)))

g (Y g)

Um unseren rekursiven Anruf bei der faktoriellen Funktion auszuführen, rufen wir einfach an (Y G) n, wo n ist die Zahl, die wir in der Faktororial berechnen. Gegeben n = 4 zum Beispiel gibt dies:

(Y G) 4

G (Y G) 4

(λr.λn. (1, wenn n = 0; anders n × (r (n−1)))) (Y G) 4

(λn. (1, wenn n = 0; anders n × (((Y G) (n−1)))) 4

1, wenn 4 = 0; sonst 4 × (((Y G) (4 - 1))

4 × (g (G (Y G) (4 - 1))

4 × (λn. (1, wenn n = 0; anders n × (((Y G) (n−1)))) (4 - 1))

4 × (1, wenn 3 = 0; sonst 3 × (((Y G) (3 - 1)))

4 × (3 × (g (g ()Y G) (3 - 1)))

4 × (3 × (λn. (1, wenn n = 0; anders n × (((Y G) (n−1)))) (3 - 1)))

4 × (3 × (1, wenn 2 = 0; sonst 2 × ((((Y G) (2 - 1)))))

4 × (3 × (2 × (g (g (g ()Y G) (2 - 1)))))

4 × (2 × (λn. (1, wenn n = 0; anders n × (((Y G) (n−1)))) (2 - 1))))

4 × (3 × (2 × (1), wenn 1 = 0; sonst 1 × ((((Y G) (1 - 1))))))

4 × (3 × (2 × (1 × (g (g)Y G) (1 - 1))))))

4 × (3 × (1 × (λn. (1, wenn n = 0; anders n × (((Y G) (n−1)))) (1 - 1)))))

4 × (3 × (2 × (1 × (1), wenn 0 = 0; sonst 0 × ((((((Y G) (0 - 1))))))

4 × (2 × (1 × (1))))))

24

Jede rekursiv definierte Funktion kann als fester Punkt einer angemessen definierten Funktion angesehen werden YJede rekursiv definierte Funktion kann als Lambda -Ausdruck ausgedrückt werden. Insbesondere können wir jetzt die Subtraktion, Multiplikation und Vergleichsprädikat natürlicher Zahlen rekursiv definieren.

Standardbegriffe

Bestimmte Begriffe haben allgemein anerkannte Namen:^[24][25][26]

I: = λx.x

S: = λx.λy.λz.x z (y z)

K: = λx.λy.x

B: = λx.λy.λz.x (y z)

C: = λx.λy.λz.x z y

W: = λx.λy.x y y

ω oder Δ: = λx.x x

Ω: = ω ω

I ist die Identitätsfunktion. SK und Bckw Formular vollständig Kombinatorrechnung Systeme, die jeden Lambda -Term ausdrücken können - sieheder nächste Abschnitt. Ω ist Y I, der kleinste Begriff, der keine normale Form hat. Y ist Standard und definiert Oben. STIMMT und FALSCH definiert Oben werden üblicherweise als abgekürzt wie T und F.

Abstraktionsentscheidung

Wenn N ist eine Lambda-Term ohne Abstraktion, enthält aber möglicherweise benannte Konstanten (Kombinatoren), dann gibt es eine Lambda-Term T(x,N) das entspricht zu λx.N aber fehlt eine Abstraktion (außer als Teil der benannten Konstanten, wenn diese als nichtatomar betrachtet werden). Dies kann auch als anonymisierende Variablen angesehen werden wie T(x,N) Entfernt alle Vorkommen von x aus N, während es dennoch zugelassen wird, dass Argumentwerte in die Positionen eingesetzt werden, wo N enthält an x. Die Konvertierungsfunktion T kann definiert werden durch:

T( x, x): = I

T( x, N): = K N wenn x ist nicht frei in N.

T( x, M N): = S T( x, M) T( x, N)

In beiden Fällen eine Begriff der Form T(x,N) P Kann durch den ersten Kombinator reduziert werden I, K, oder S Schnapp dir das Argument Pgenau wie β-Reduktion von (λx.N) P würdest du. I Gibt dieses Argument zurück. K wirft das Argument weg, genau wie (λx.N) würde tun, wenn x hat kein freies Ereignis in N. S Übergibt das Argument an beide Subterms der Anwendung und wendet dann das Ergebnis des ersten auf das Ergebnis der zweiten an.

Die Kombinatoren B und C sind ähnlich wie S, aber das Argument weiter an nur einen Untermaterial einer Anwendung weitergeben (B zu dem "Argument" Subterm und C auf die "Funktion" subterm) und somit eine nachfolgende Speicherung K Wenn es kein Ereignis gibt x in einer Untermenge. Im Vergleich zu B und C, das S Der Kombinator verbindet tatsächlich zwei Funktionen: Argumente neu ordnen und ein Argument duplizieren, damit es an zwei Stellen verwendet werden kann. Das W Kombinator macht nur Letzteres und gibt die B, C, K, W System Alternative zu Ski -Kombinatorrechnung.

Typed Lambda Calculus

A Typed Lambda Calculus ist ein Typed Formalismus Das verwendet das Lambda-Symbol (${\ displayStyle \ lambda}$) Anonyme Funktion Abstraktion zu bezeichnen. In diesem Zusammenhang sind Typen normalerweise Objekte syntaktischer Natur, die Lambda -Begriffen zugeordnet sind. Die genaue Art eines Typs hängt vom berücksichtigten Kalkül ab (siehe Arten von typisierten Lambda -Berechnungen). Aus einer gewissen Sicht können typisierte Lambda -Kalkül als Verfeinerung des Untyped Lambda Calculus Aus einer anderen Sicht können sie aber auch als grundlegendere Theorie angesehen werden und Untyped Lambda Calculus Ein Sonderfall mit nur einem Typ.^[27]

Typisierte Lambda -Kalkül sind grundlegend Programmiersprachen und sind die Basis von Typed Funktionale Programmiersprachen wie zum Beispiel Ml und Haskell und indirekt, tippte Imperative Programmierung Sprachen. Typisierte Lambda -Kalkül spielen eine wichtige Rolle bei der Gestaltung von Typsysteme für Programmiersprachen; Hier erfasst die Typbarkeit normalerweise wünschenswerte Eigenschaften des Programms, z. Das Programm verursacht keinen Verstöße gegen den Speicherzugriff.

Typed Lambda Calculi sind eng mit dem verwandt mit Mathematische Logik und Beweistheorie über die Curry -Howard Isomorphismus und sie können als die betrachtet werden interne Sprache von Klassen von Kategorien, z.B. Der einfach typisierte Lambda -Kalkül ist die Sprache von Kartesische Kategorien geschlossen (CCCS).

Reduktionsstrategien

Ob ein Begriff normalisiert oder nicht, und wie viel Arbeit bei der Normalisierung erledigt werden muss, wenn dies der Fall ist, hängt in hohem Maße von der verwendeten Reduktionsstrategie ab. Zu den gängigen Strategien zur Reduzierung von Lambda Calculus -Reduktion gehören:^[28]

Normale Ordnung

Die äußerste, äußerste Redex links wird immer zuerst reduziert. Das heißt, wenn möglich, werden die Argumente in den Körper einer Abstraktion eingesetzt, bevor die Argumente reduziert werden.

Anwendungsreihenfolge

Die links, die innerste Redex wird immer zuerst reduziert. Intuitiv bedeutet dies, dass die Argumente einer Funktion immer vor der Funktion selbst reduziert werden. Anwendende Reihenfolge versucht immer, Funktionen auf normale Formen anzuwenden, auch wenn dies nicht möglich ist.

Vollständige β-Reduktionen

Jeder Redex kann jederzeit reduziert werden. Dies bedeutet im Wesentlichen das Fehlen einer bestimmten Reduktionsstrategie - mit der Reduzierbarkeit "sind alle Wetten ausgeschaltet".

Schwache Reduktionsstrategien verringern unter Lambda -Abstraktionen nicht:

Rufen Sie nach Wert an

Ein Redex wird nur reduziert, wenn sich die rechte Seite auf einen Wert reduziert hat (Variable oder Abstraktion). Nur die äußersten Redexes werden reduziert.

Rufen Sie mit dem Namen an

Als normale Reihenfolge, aber innerhalb der Abstraktionen werden keine Reduktionen durchgeführt. Zum Beispiel, λx. (λx.x)x ist nach dieser Strategie in normaler Form, obwohl es den Redex enthält (λx.x)x.

Strategien mit dem Teilen reduzieren Berechnungen, die parallel "gleich" sind:

Optimale Reduktion

Als normale Reihenfolge, aber Berechnungen mit derselben Etikett werden gleichzeitig reduziert.

Rufen Sie nach Bedarf an

Als Aufruf mit Namen (daher schwach), aber Funktionsanwendungen, die die Begriffe duplizieren würden, nennen stattdessen das Argument, das dann nur "wenn es benötigt wird" reduziert wird.

Berechnbarkeit

Es gibt keinen Algorithmus, der als Eingabe zwei beliebige Lambda -Ausdrücke und Ausgänge dauert STIMMT oder FALSCH Abhängig davon, ob sich ein Ausdruck auf den anderen reduziert.^[10] Genauer gesagt nein berechnungsbare Funktion kann sich entscheiden die Frage. Dies war historisch gesehen das erste Problem, für das Unentschlossenheit nachgewiesen werden konnte. Wie üblich für einen solchen Beweis, berechenbar bedeutet von jedem berechnet Berechnungsmodell das ist Turing vollständig. Tatsächlich kann die Berechnbarkeit selbst über den Lambda -Kalkül definiert werden: eine Funktion F: N → N von natürlichen Zahlen ist eine rechenbare Funktion, wenn und nur wenn ein Lambda -Ausdruck besteht f so dass für jedes Paar von Paar x, y in N, F(x) =y dann und nur dann, wenn f x=_β y, wo x und y sind die Kirchliche Ziffern korrespondierend zu x und yjeweils bzw. = =_β Bedeutung Äquivalenz mit β-Reduktion. Siehe das These der Kirche und tätige These Für andere Ansätze zur Definition der Berechnung und deren Äquivalenz.

Der Beweis der Kirche für Unkomputierbarkeit reduziert zunächst das Problem, um festzustellen, ob ein bestimmter Lambda -Ausdruck a ist Normale Form. Dann geht er davon aus, dass dieses Prädikat berechnet ist und daher in Lambda -Kalkül ausgedrückt werden kann. Aufbau auf früheren Arbeiten von Kleene und Bau a Gödel -Nummerierung Für Lambda -Ausdrücke konstruiert er einen Lambda -Ausdruck e das folgt genau dem Beweis von Gödels erster Unvollständigkeitstheorem. Wenn e wird auf eine eigene Gödel -Zahl angewendet, eine Widerspruchsergebnisse.

Komplexität

Der Begriff von Rechenkomplexität Für den Lambda-Kalkül ist etwas schwierig, da die Kosten einer β-Reduktion je nach Umsetzung variieren können.^[29] Um genau zu sein, muss man irgendwie den Ort aller Vorkommen der gebundenen Variablen ermitteln V im Ausdruck E, was eine Zeitkosten impliziert, oder man muss die Standorte freier Variablen in irgendeiner Weise im Auge behalten, was eine Platzkosten impliziert. Eine naive Suche nach den Orten von V in E ist O(n) in der Länge n von E. Direktor Strings waren ein früher Ansatz, der diese Zeitkosten für eine quadratische Raumnutzung tauschte.^[30] Allgemeiner hat dies zur Untersuchung von Systemen geführt, die verwendet werden explizite Substitution.

Im Jahr 2014 wurde gezeigt, dass die Anzahl der β-Reduktionsschritte, angemessen Zeitkostenmodell, dh die Reduktion kann auf einer Turing -Maschine polynomial proportional zur Anzahl der Schritte simuliert werden.^[31] Dies war ein langjähriges offenes Problem aufgrund Größenexplosion, die Existenz von Lambda-Begriffen, die für jede β-Reduktion exponentiell wachsen. Das Ergebnis wird durch die Arbeit mit einer kompakten gemeinsamen Darstellung umgearbeitet. Das Ergebnis macht deutlich, dass die für die Bewertung eines Lambda -Terms benötigte Platzbedarf nicht proportional zur Größe des Laufzeit während der Reduzierung ist. Es ist derzeit nicht bekannt, was ein gutes Maß für die Raumkomplexität wäre.^[32]

Ein unangemessenes Modell bedeutet nicht unbedingt ineffizient. Optimale Reduktion Reduziert alle Berechnungen mit demselben Etikett in einem Schritt und vermeidet doppelte Arbeiten, aber die Anzahl der parallelen β-Reduktionsschritte, um einen bestimmten Begriff auf die normale Form zu reduzieren, ist in der Größe des Begriffs ungefähr linear. Dies ist viel zu klein, um eine angemessene Kostenmaßnahme zu sein, da jede Turing -Maschine im Lambda -Kalkül in der Größe linear proportional zur Größe der Turing -Maschine codiert werden kann. Die tatsächlichen Kosten für die Reduzierung von Lambda-Termen sind nicht auf β-Reduktion an sich zurückzuführen, sondern auf die Behandlung der Duplikation von Redexen während der β-Reduktion.^[33] Es ist nicht bekannt, ob optimale Reduktionsimplementierungen in Bezug auf ein angemessenes Kostenmodell angemessen sind und hat höchstens einen quadratischen Overhead im Vergleich zum linken obersten.^[32] Darüber hinaus übertraf die BOHM -Prototyp -Implementierung einer optimalen Reduktion beides übertriffte beide CAML Light und Haskell zu reinen Lambda -Begriffen.^[33]

Lambda -Kalkül und Programmiersprachen

Wie hervorgehoben von Peter Landin's 1965 Papier "Eine Korrespondenz zwischen Algol 60 und Lambda-Notation der Kirche",^[34] sequentiell Verfahrensprogrammierung Sprachen können in Bezug auf den Lambda -Kalkül verstanden werden, der die grundlegenden Mechanismen für die Verfahrensabstrakt- und Verfahrensanwendung (Subprogramm) liefert.

Anonyme Funktionen

Zum Beispiel in Lispeln Die "quadratische" Funktion kann wie folgt als Lambda -Ausdruck ausgedrückt werden:

(Lambda (x) (* x x)) 

Das obige Beispiel ist ein Ausdruck, der eine erstklassige Funktion bewertet. Das Symbol Lambda Erstellt eine anonyme Funktion, bei der eine Liste von Parameternamen, angezeigt wird. (x) - Nur ein einziges Argument in diesem Fall und ein Ausdruck, der als Körper der Funktion bewertet wird, (* x x). Anonyme Funktionen werden manchmal als Lambda -Ausdrücke bezeichnet.

Zum Beispiel, Pascal und viele andere imperative Sprachen haben das Tod seit langem unterstützt Unterprogramme wie Argumente zu anderen Unterprogrammen durch den Mechanismus von Funktionszeiger. Funktionszeiger sind jedoch keine ausreichende Bedingung für Funktionen erste Klasse Datentypen, da eine Funktion ein erstklassiger Datentyp ist, wenn und nur dann neue Instanzen der Funktion zur Laufzeit erstellt werden können. Und diese Laufzeitschaffung von Funktionen wird in unterstützt Smalltalk, JavaScript und Wolfram Spracheund in jüngerer Zeit in Scala, Eiffel ("Agenten"), C# ("Delegierte") und C ++ 11, unter anderen.

Parallelität und Parallelität

Das Kirchen -Rosser Eigenschaft des Lambda-Kalküls bedeutet, dass die Bewertung (β-Reduktion) in der jede Bestellung, auch parallel. Dies bedeutet, dass verschiedene Nichtdeterministische Bewertungsstrategien sind relevant. Der Lambda -Kalkül bietet jedoch keine explizite Konstrukte für Parallelität. Man kann Konstrukte hinzufügen, z. Futures zum Lambda -Kalkül. Sonstiges Prozesskalkül wurden entwickelt, um Kommunikation und Parallelität zu beschreiben.

Semantik

Die Tatsache, dass Lambda Calculus -Begriffe als Funktionen für andere Lambda -Kalkülbegriffe und sogar zu sich selbst fungieren, führte zu Fragen zur Semantik des Lambda -Kalküls. Könnte eine vernünftige Bedeutung Lambda -Kalkül zugeordnet werden? Die natürliche Semantik bestand darin, einen Satz zu finden D isomorph zum Funktionsraum D → D, der Funktionen für sich. Allerdings kein nicht triviales solches D kann existieren, durch Kardinalität Einschränkungen, weil die Menge aller Funktionen von D zu D hat größere Kardinalität als D, wenn nicht D ist ein Singleton -Set.

In den 1970ern, Dana Scott zeigte das, wenn nur kontinuierliche Funktionen wurden in Betracht gezogen, ein Satz oder Domain D mit der erforderlichen Eigenschaft konnte gefunden werden, wodurch a bereitgestellt werden Modell Für den Lambda -Kalkül.

Diese Arbeit bildete auch die Grundlage für die Denotationssemantik von Programmiersprachen.

Variationen und Erweiterungen

Diese Erweiterungen sind in der Lambda Würfel:

• Typed Lambda Calculus - Lambda -Kalkül mit typisierten Variablen (und Funktionen)
• System f -Ein typisierter Lambda-Kalkül mit Typ-Variablen
• Konstruktionsberechnung - ein typisierter Lambda -Kalkül mit Typen als erstklassige Werte

Diese formelle Systeme sind Erweiterungen von Lambda -Kalkül, die sich nicht im Lambda -Würfel befinden:

• Binärer Lambda -Kalkül - Eine Version von Lambda Calculus mit binären E/O, eine binäre Kodierung von Begriffen und eine bestimmte universelle Maschine.
• Lambda-Mu-Kalkül - Eine Erweiterung des Lambda -Kalküls zur Behandlung klassische Logik

Diese formalen Systeme sind Variationen des Lambda -Kalküls:

• Kappa -Kalkül -Ein Analogon des Lambda-Kalküls erster Ordnung

Diese formalen Systeme beziehen sich auf Lambda -Kalkül:

• Kombinationslogik - Eine Notation für mathematische Logik ohne Variablen
• Ski -Kombinatorrechnung - Ein Computersystem basierend auf der S, K und I Kombinatoren, entspricht Lambda -Kalkül, jedoch ohne variable Substitutionen reduzierbar

Siehe auch

Anmerkungen

Verweise

Weitere Lektüre

• Abelson, Harold und Gerald Jay Sussman. Struktur und Interpretation von Computerprogrammen. Die MIT -Presse. ISBN0-262-51087-1.
• Hendrik Pieter Barendregt Einführung in den Lambda -Kalkül.
• Henk Barendregt, Die Auswirkungen des Lambda -Kalküls auf Logik und Informatik. Das Bulletin der symbolischen Logik, Band 3, Nummer 2, Juni 1997.
• Barendregt, Hendrik Pieter, Der typfreie Lambda -Kalkül pp1091–1132 von Handbuch der mathematischen Logik, Nordholland (1977) ISBN0-7204-2285-x
• Cardone und Hindley, 2006. Vorgeschichte von Lambda-Kalkulus und kombinatorischer Logik. In Gabbay und Woods (Hrsg.), Handbuch der Logikgeschichte, vol. 5. Elsevier.
• Kirche, Alonzo, Ein unlösbares Problem der Elementarzahltheorie, American Journal of Mathematics, 58 (1936), S. 345–363. Dieses Papier enthält den Beweis, dass die Äquivalenz von Lambda -Ausdrücken im Allgemeinen nicht entzündbar ist.
• Alonzo -Kirche, Die Kalkül der Lambda-Konversion ( ISBN978-0-691-08394-0) ^[1]
• Frink Jr., Orrin, Bewertung: Die Berechnung der Lambda-Konversion ^[2]
• Kleene, Stephen, Eine Theorie positiver Ganzzahlen in der formalen Logik, American Journal of Mathematics, 57 (1935), S. 153–173 und 219–244. Enthält die Lambda Calculus -Definitionen mehrerer bekannter Funktionen.
• Landin, Peter, Eine Korrespondenz zwischen Algol 60 und Lambda-Notation der Kirche, Kommunikation der ACM, vol. 8, nein. 2 (1965), Seiten 89–101. Erhältlich aus der ACM -Site. Ein klassisches Papier, das die Bedeutung von Lambda -Kalkül als Grundlage für Programmiersprachen hervorhebt.
• Larson, Jim, Eine Einführung in Lambda Calculus und Schema. Eine sanfte Einführung für Programmierer.
• Schalk, A. und Simmons, H. (2005) Eine Einführung in λ-Calculi und Arithmetik mit einer anständigen Auswahl von Übungen. Anmerkungen für einen Kurs in der mathematischen Logik MSC an der Manchester University.
• de Queiroz, Ruy J.G.B. (2008). "Über Reduktionsregeln, Bedeutung als Verwendung und Proof-theoretische Semantik". Studia Logica. 90 (2): 211–247. doi:10.1007/s11225-008-9150-5. S2CID 11321602. Ein Papier, das eine formelle Untermauerung der Idee der „Bedeutung-is-Verwendung“ enthält, die, selbst wenn sie auf Beweisen beruht, sich von der Proodenstheoretik wie in der Tradition von Dummett-Prawitz unterscheidet, da es die Reduzierung als die Regeln erfordert, die Bedeutung geben.
• Hankin, Chris, Eine Einführung in Lambda Calculi für Informatiker, ISBN0954300653

Monographien/Lehrbücher für Doktoranden:

• Morten Heine Sørensen, Paweł Urzyczyn, Vorträge über den Curry -Howard -Isomorphismus, Elsevier, 2006, ISBN0-444-52077-5 ist eine kürzlich durchgeführte Monographie, die die Hauptthemen von Lambda Calculus von der Art-freier Vielfalt bis zur meisten behandelt Typed Lambda Calculi, einschließlich neuerer Entwicklungen wie reine Typsysteme und die Lambda Würfel. Es bedeckt nicht Subtyping Erweiterungen.
• Pierce, Benjamin (2002), Typen und Programmiersprachen, MIT Press, ISBN 0-262-16209-1 deckt Lambda Calculi aus praktischer Typ -Systemperspektive ab; Einige Themen wie abhängige Typen werden nur erwähnt, aber Subtyping ist ein wichtiges Thema.

Einige Teile dieses Artikels basieren auf Material von Ordner, mit Genehmigung verwendet.

Externe Links

• Graham Hutton, Lambda -Kalkül, ein kurzes (12 Minuten) Computerphile -Video auf dem Lambda -Kalkül
• Helmut Brandl, Schritt für Schritt Einführung in den Lambda -Kalkül
• "Lambda-Kalkulus", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Achim Jung, Eine kurze Einführung in den Lambda -Kalkül-(PDF)
• Dana Scott, Eine Zeitleiste des Lambda -Kalküls-(PDF)
• David C. Keenan, Zum Zerlegen eines Spottdrossels: Eine grafische Notation für den Lambda -Kalkül mit animierter Reduzierung
• Raúl Rojas, Eine Tutorial -Einführung in den Lambda -Kalkül-(PDF)
• Peter Selinger, Vorlesungsnotizen zum Lambda -Kalkül-(PDF)
• L. Allison, Einige ausführbare λ-Calculus-Beispiele
• Georg P. Loczewski, Der Lambda -Kalkül und A ++
• Bret Victor, Alligator -Eier: Ein Puzzlespiel, das auf Lambda -Kalkül basiert
• Lambda -Kalkül Archiviert 2012-10-14 bei der Wayback -Maschine an Safalras Website Archiviert 2021-05-02 am Wayback -Maschine
• LCI Lambda Dolmetscher Ein einfacher, aber leistungsstarker reine Kalkül Interpreter
• Lambda Calculus Links zu Lambda-the-ultima
• Mike Thyer, Lambda -Animator, ein grafisches Java -Applet, das alternative Reduktionsstrategien zeigt.
• Implementierung des Lambda -Kalküls Verwendung C ++ - Vorlagen
• Marius Buliga, Grafische Lambda -Kalkül
• Lambda -Kalkül als Workflow -Modell von Peter Kelly, Paul Coddington und Andrew Wendelborn; Erwähnungen Grafikreduzierung als gemeinsames Mittel zur Bewertung von Lambda -Ausdrücken und diskutiert die Anwendbarkeit von Lambda -Kalkül für verteiltes Computer (aufgrund der Kirchen -Rosser Eigenschaft, die ermöglicht parallel Grafikreduktion für Lambda -Ausdrücke).
• Shane Steinert-Threlkeld, "Lambda Calculi", Internet -Enzyklopädie der Philosophie
• Anton Salikhmetov, Makrolambda -Kalkül