Die Lambda-Rechnung (auch schriftlich als λ-calculus) ist ein formelles System in der mathematischen Logik, um Berechnung über die variable Schwergängigkeit und den Ersatz auszudrücken. Es wurde zuerst von Alonzo Church als eine Weise formuliert, Mathematik durch den Begriff von Funktionen im Gegensatz zum Feld der Mengenlehre zu formalisieren. Obwohl nicht sehr erfolgreich in dieser Rücksicht die Lambda-Rechnung frühe Erfolge im Gebiet der Berechenbarkeitstheorie wie eine negative Antwort auf den Entscheidungsproblem von Hilbert gefunden hat.

Wegen der Wichtigkeit vom Begriff der variablen Schwergängigkeit und des Ersatzes gibt es nicht nur ein System der Lambda-Rechnung. Historisch war das wichtigste System die ungetippte Lambda-Rechnung. In der ungetippten Lambda-Rechnung hat Funktionsanwendung keine Beschränkungen (so wird der Begriff des Gebiets einer Funktion ins System nicht eingebaut). In der Kirch-Turing-These, wie man fordert, ist die ungetippte Lambda-Rechnung dazu fähig, alle effektiv berechenbaren Funktionen zu schätzen. Die getippte Lambda-Rechnung ist eine Vielfalt, die Funktionsanwendung einschränkt, so dass Funktionen nur angewandt werden können, wenn sie dazu fähig sind, den "Typ" des gegebenen Eingangs von Daten zu akzeptieren.

Heute hat die Lambda-Rechnung Anwendungen in vielen verschiedenen Gebieten in der Mathematik, Philosophie und Informatik. Es wird noch im Gebiet der Berechenbarkeitstheorie verwendet, obwohl Maschinen von Turing wohl das bevorzugte Modell für die Berechnung sind. Lambda-Rechnung hat eine wichtige Rolle in der Entwicklung der Theorie von Programmiersprachen gespielt. Die prominentesten Kopien zur Lambda-Rechnung in der Informatik sind funktionelle Programmiersprachen, die im Wesentlichen die Rechnung (vermehrt mit einigen Konstanten und datatypes) durchführen. Außer Programmiersprachen hat die Lambda-Rechnung auch viele Anwendungen in der Probetheorie. Ein Hauptbeispiel davon ist die Ähnlichkeit des Currys-Howard, die eine Ähnlichkeit zwischen verschiedenen Systemen von getippten Lambda-Rechnungen und Systemen der formalen Logik gibt.

Lambda-Rechnung in der Geschichte der Mathematik

Die Lambda-Rechnung wurde von der Kirche des Mathematikers Alonzo in den 1930er Jahren als ein Teil einer Untersuchung der Fundamente der Mathematik eingeführt. Wie man zeigte, war das ursprüngliche System 1935 logisch inkonsequent, als Stephen Kleene und J. B. Rosser das Kleene-Rosser Paradox entwickelt haben.

Nachher 1936 hat Kirche isoliert und hat gerade den für die Berechnung wichtigen Teil veröffentlicht, was jetzt die ungetippte Lambda-Rechnung genannt wird. 1940 hat er auch ein rechenbetont schwächeres aber logisch konsequentes System eingeführt, das als die einfach getippte Lambda-Rechnung bekannt ist.

Informelle Beschreibung

Motivation

Rekursive Funktionen sind ein grundsätzliches Konzept innerhalb der Informatik und Mathematik. Der λ-calculus stellt einfache Semantik für die Berechnung zur Verfügung, Eigenschaften der Berechnung ermöglichend, formell studiert zu werden.

Denken Sie die folgenden zwei Beispiele. Die Identitätsfunktion

:

nimmt einen einzelnen Eingang, und kehrt sofort zurück (d. h. die Identität tut nichts mit seinem Eingang), wohingegen die Funktion

:

nimmt ein Paar von Eingängen, und und gibt die Summe ihrer Quadrate zurück. Mit diesen zwei Beispielen können wir einige nützliche Beobachtungen machen, die die Hauptideen in der Lambda-Rechnung motivieren.

Die erste Beobachtung besteht darin, dass Funktionen nicht ausführlich genannt zu werden brauchen. D. h. die Funktion

:

kann in der anonymen Form als umgeschrieben werden

:

(lesen Sie als "das Paar dessen, und wird zu" kartografisch dargestellt). Ähnlich

:

kann in der anonymen Form als umgeschrieben werden, wo der Eingang einfach zu sich kartografisch dargestellt wird.

Die zweite Beobachtung besteht darin, dass die spezifische Wahl des Namens für Argumente einer Funktion größtenteils irrelevant ist. D. h.

: und

:

drücken Sie dieselbe Funktion aus: die Identität. Ähnlich

: und:

drücken Sie auch dieselbe Funktion aus.

Schließlich kann jede Funktion, die zwei Eingänge, zum Beispiel vor der erwähnten Funktion verlangt, in eine gleichwertige Funktion nachgearbeitet werden, die einen einzelnen Eingang akzeptiert, und weil Produktion eine andere Funktion zurückgibt, die der Reihe nach einen einzelnen Eingang akzeptiert. Zum Beispiel,

:

kann in nachgearbeitet werden

:

Diese Transformation wird genannt, mit Currysoße zubereitend, d. h. eine Funktion umgestaltend, die vielfache Argumente auf solche Art und Weise nimmt, dass es als eine Kette von Funktionen jeder mit einem einzelnen Argument (teilweise Anwendung) genannt werden kann. Es kann zu Funktionen verallgemeinert werden, die eine beliebige Zahl von Argumenten akzeptieren.

Mit Currysoße zuzubereiten, kann am besten intuitiv durch den Gebrauch eines Beispiels ergriffen werden. Vergleichen Sie die Funktion

:

mit seiner mit Currysoße zubereiteten Form,

:

Die Funktion auf die Argumente (5, 2) anwendend, haben wir:

::

Jedoch, damit mit Currysoße zuzubereiten, haben wir:

:::

und wir sehen die mit Currysoße unzubereiteten und mit Currysoße zubereiteten Formen dasselbe Ergebnis schätzen. Bemerken Sie, dass x*x eine Konstante nach der ersten Argument-Anweisung geworden ist.

Die Lambda-Rechnung

Die Lambda-Rechnung besteht aus einer Sprache von Lambda-Begriffen zusammen mit einer equational Theorie (der auch betrieblich verstanden werden kann).

Da die Namen von Funktionen größtenteils eine Bequemlichkeit sind, hat die Lambda-Rechnung keine Mittel, eine Funktion zu nennen. Da alle Funktionen, die mehr als einen Eingang erwarten, in gleichwertige Funktionen umgestaltet werden können, die einen einzelnen Eingang akzeptieren (darüber, Mit Currysoße zuzubereiten), hat die Lambda-Rechnung keine Mittel, für eine Funktion zu schaffen, die mehr als ein Argument akzeptiert. Da die Namen von Argumenten größtenteils irrelevant sind, ist der heimische Begriff der Gleichheit zu Lambda-Begriffen Alpha-Gleichwertigkeit (sieh unten), die diesen Grundsatz kodifiziert.

Lambda-Begriffe

Die Syntax von Lambda-Begriffen ist besonders einfach. Es gibt drei Wege, auf die man sie erhält:

• ein Lambda-Begriff kann eine Variable sein;
• wenn ein Lambda-Begriff ist, und eine Variable ist, dann ein Lambda-Begriff ist (hat eine Lambda-Abstraktion genannt);
• wenn und Lambda-Begriffe sind, dann ist ein Lambda-Begriff (hat eine Anwendung genannt).

Nichts anderes ist ein Lambda-Begriff, obwohl das Einklammern verwendet werden kann und erforderlich sein kann, um Begriffe zu disambiguieren. Zum Beispiel, und zeigen Sie verschiedene Begriffe an.

Intuitiv vertritt eine Lambda-Abstraktion eine anonyme Funktion, die einen einzelnen Eingang nimmt und zu sein, der gesagt ist, um darin zu binden, und eine Anwendung die Anwendung des Eingangs zu etwas Funktion vertritt. In der Lambda-Rechnung werden Funktionen genommen, um Werte der ersten Klasse zu sein, so können Funktionen als die Eingänge an andere Funktionen gewöhnt sein, und Funktionen Funktionen als ihre Produktionen zurückgeben können.

Zum Beispiel, vertritt die Identitätsfunktion, und vertritt die Identitätsfunktion, die darauf angewandt ist. Weiter, vertritt die unveränderliche Funktion, die Funktion, die immer </tt> y </tt> macht dir nichts aus dem Eingang zurückkehrt. Es sollte bemerkt werden, dass Funktionsanwendung, so nach links assoziativ ist.

Lambda-Begriffe sind selbstständig nicht besonders interessant.

Was sie interessant macht, sind die verschiedenen Begriffe der Gleichwertigkeit und der Verminderung, die über sie definiert werden kann.

Alpha-Gleichwertigkeit

Eine grundlegende Form der Gleichwertigkeit, die zu Lambda-Begriffen definierbar ist, ist Alpha-Gleichwertigkeit. Es gewinnt die Intuition, dass die besondere Wahl einer bestimmten Variable, in einer Lambda-Abstraktion, nicht (gewöhnlich) von Bedeutung ist.

Zum Beispiel, und sind mit dem Alpha gleichwertige Lambda-Begriffe, dieselbe Identitätsfunktion vertretend.

Bemerken Sie, dass die Begriffe und nicht mit dem Alpha gleichwertig sind, weil sie in einer Lambda-Abstraktion nicht gebunden werden.

In vielen Präsentationen ist es üblich, mit dem Alpha gleichwertige Lambda-Begriffe zu identifizieren.

Die folgenden Definitionen sind notwendig, um im Stande zu sein, die Beta-Verminderung zu definieren.

Freie Variablen

Die freien Variablen eines Begriffes sind jene durch eine Lambda-Abstraktion nicht gebundenen Variablen.

D. h. die freien Variablen dessen sind gerade; die freien Variablen dessen sind die freien Variablen mit dem entfernten, und die freien Variablen dessen sind die Vereinigung der freien Variablen und.

Zum Beispiel hat der Lambda-Begriff, der die Identität vertritt, keine freien Variablen, aber die unveränderliche Funktion hat eine einzelne freie Variable.

Festnahme vermeidende Ersetzungen

Mit der Definition von freien Variablen können wir jetzt einen Festnahme vermeidenden Ersatz definieren.

Denken Sie, und sind Lambda-Begriffe und und sind Variablen.

Wir schreiben für den Ersatz für in auf eine Festnahme vermeidende Weise.

Das ist:

• ;

• wenn;

; ;

• wenn und nicht in den freien Variablen ist (manchmal hat gesagt "ist für" frisch).

Zum Beispiel, und.

Die Frische-Bedingung (das Verlangen, das nicht in den freien Variablen dessen ist) ist entscheidend, um sicherzustellen, dass Ersatz die Bedeutung von Funktionen nicht ändert.

Nehmen Sie zum Beispiel an, dass wir eine andere Ersatz-Handlung ohne die Frische-Bedingung definieren.

Dann, und verwandelt sich die unveränderliche Funktion in die Identität durch den Ersatz.

Wenn unsere Frische-Bedingung nicht entsprochen wird, dann können wir einfach Alpha - benennt mit einer angemessen frischen Variable um.

Zum Beispiel kann die Schaltung zurück zu unserem richtigen Begriff des Ersatzes, in der Lambda-Abstraktion mit einer frischen Variable umbenannt werden, um vorzuherrschen, und die Bedeutung der Funktion wird durch den Ersatz bewahrt.

Die Beta-Verminderung

Die Beta-Verminderung stellt fest, dass eine Anwendung der Form zum Begriff abnimmt (wir schreiben, als eine günstige Schnellschrift für das "Beta zu" abnimmt).

Zum Beispiel für jeden haben wir, demonstrierend, der wirklich die Identität ist.

Ähnlich, das Demonstrieren, das wirklich eine unveränderliche Funktion ist.

Die Lambda-Rechnung kann als eine idealisierte funktionelle Programmiersprache, wie Haskell oder Standard ML gesehen werden.

Unter dieser Ansicht entspricht die Beta-Verminderung einem rechenbetonten Schritt, und in der ungetippten Lambda-Rechnung, wie präsentiert, hier, die Verminderung braucht nicht zu enden.

Denken Sie zum Beispiel den Begriff.

Hier haben wir.

D. h. der Begriff nimmt zu sich in der einzelnen Beta-Verminderung ab, und deshalb wird die Verminderung nie enden.

Ein anderes Problem mit der ungetippten Lambda-Rechnung ist die Unfähigkeit, zwischen verschiedenen Arten von Daten zu unterscheiden.

Zum Beispiel können wir eine Funktion schreiben wollen, die nur auf Zahlen funktioniert.

Jedoch, in der ungetippten Lambda-Rechnung, gibt es keine Weise, unsere Funktion zu hindern, auf Wahrheitswerte oder Schnuren zum Beispiel angewandt zu werden.

Getippte Lambda-Rechnungen, die später im Artikel eingeführt werden, haben das Eigentum dass, wenn ein Begriff gut getippt wird, dann wird es nie "durchstochen" (wo es keine Einschätzungsregel für den Begriff gibt), und dass, wenn ein Begriff einen besonderen Typ, und dann hat, denselben Typ hat.

Formelle Definition

Definition

Lambda-Ausdrücke werden aus zusammengesetzt

:variables v, v..., v...

:the-Abstraktionssymbole λ und.

:parentheses

Der Satz von Lambda-Ausdrücken, Λ, kann rekursiv definiert werden:

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

Beispiele der Regel 2 sind als Abstraktionen bekannt, und Beispiele der Regel 3 sind als Anwendungen bekannt.

Notation

Um die Notation von Lambda-Ausdrücken ordentlich zu halten, wird die folgende Vereinbarung gewöhnlich angewandt.

• Äußerste Parenthesen sind fallen gelassen: M N statt (M N).

Wie man

• annimmt, werden Anwendungen assoziativ verlassen: M N P kann statt geschrieben werden ((M N) P).
• Der Körper einer Abstraktion erweitert so weites Recht wie möglich: λx. M N bedeutet λx. (M N) und nicht (λx. M) N.
• Eine Folge von Abstraktionen wird zusammengezogen: λx.λy.λz. N wird als λxyz abgekürzt. N.

Freie und bestimmte Variablen

Wie man

sagt, bindet der Abstraktionsmaschinenbediener, λ, seine Variable, wo auch immer es im Körper der Abstraktion vorkommt. Wie man sagt, werden Variablen, die im Rahmen eines Lambdas fallen, gebunden. Alle anderen Variablen werden frei genannt. Zum Beispiel im folgenden Ausdruck y ist eine bestimmte Variable, und x ist frei:. Bemerken Sie auch, dass eine Variable zu seinem "nächsten" Lambda bindet. Im folgenden Ausdruck wird ein einzelnes Ereignis von x durch das zweite Lambda gebunden:

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

1. FV (x) = {x}, wo x eine Variable ist
2. FV (λx. M) = FV (M) \{x }\
3. FV (M N) = FV (M)  FV (N)

Wie man

sagt, wird ein Ausdruck, der keine freien Variablen enthält, geschlossen. Geschlossene Lambda-Ausdrücke sind auch bekannt als combinators und sind zu Begriffen in der combinatory Logik gleichwertig.

Die Verminderung

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

Es gibt drei Arten der Verminderung:

• α-conversion: das Ändern bestimmter Variablen;
• β-reduction: Verwendung von Funktionen zu ihren Argumenten;
• η-conversion: Der einen Begriff von extensionality gewinnt.

Wir sprechen auch von den resultierenden Gleichwertigkeiten: Zwei Ausdrücke sind β-equivalent, wenn sie β-converted in denselben Ausdruck sein können, und α/η-equivalence ähnlich definiert werden.

Der Begriff redex, kurz für den reduzierbaren Ausdruck, bezieht sich auf Subbegriffe, die durch eine der Verminderungsregeln reduziert werden können. Zum Beispiel, ist ein Beta-redex; wenn darin nicht frei ist, ist ein eta-redex. Der Ausdruck, zu dem ein redex abnimmt, wird seinen Wiederkanal genannt; mit dem vorherigen Beispiel sind die Wiederkanäle dieser Ausdrücke beziehungsweise und.

α-conversion

Alpha-Konvertierung, die manchmal als Alpha-Umbenennung bekannt ist, erlaubt gebundenen Variablennamen, geändert zu werden. Zum Beispiel könnte Alpha-Konvertierung dessen tragen. Begriffe, die sich nur durch die Alpha-Konvertierung unterscheiden, werden α-equivalent genannt. Oft im Gebrauch der Lambda-Rechnung, α-equivalent Begriffe werden betrachtet, gleichwertig zu sein.

Die genauen Regeln für die Alpha-Konvertierung sind nicht völlig trivial. Erstens, wenn Alpha-Umwandeln, sind eine Abstraktion, die einzigen variablen Ereignisse, die umbenannt werden, diejenigen, die zu derselben Abstraktion gebunden werden. Zum Beispiel konnte eine Alpha-Konvertierung dessen hinauslaufen, aber sie konnte nicht hinauslaufen. Der Letztere hat eine verschiedene Bedeutung aus dem Original.

Zweitens ist Alpha-Konvertierung nicht möglich, wenn sie auf eine Variable hinauslaufen würde, die durch eine verschiedene Abstraktion wird gewinnt. Zum Beispiel, wenn wir durch darin ersetzen, kommen wir, der überhaupt nicht dasselbe ist.

Auf Programmiersprachen mit dem statischen Spielraum kann Alpha-Konvertierung verwendet werden, um einfacheren Namenentschluss durch das Sicherstellen zu fassen, dass kein Variablenname einen Namen in maskiert, Spielraum enthaltend (sieh Alpha umbenennen, um Namenentschluss trivial zu fassen).

Ersatz

Ersatz, schriftlich, ist der Prozess, alle freien Ereignisse der Variable durch den Ausdruck zu ersetzen.

Der Ersatz zu Begriffen des λ-calculus wird durch recursion auf der Struktur von Begriffen wie folgt definiert.

:::::

Um in eine Lambda-Abstraktion zu vertreten, ist es manchmal für α-convert der Ausdruck notwendig. Zum Beispiel ist es nicht richtig für hinauszulaufen, weil das eingesetzte hat frei sein sollen, aber damit geendet hat, gebunden zu werden. Der richtige Ersatz ist in diesem Fall bis zu α-equivalence. Bemerken Sie, dass Ersatz einzigartig bis zu α-equivalence definiert wird.

&beta;-reduction

Die Beta-Verminderung gewinnt die Idee von der Funktionsanwendung. Die Beta-Verminderung wird in Bezug auf den Ersatz definiert: Die Beta-Verminderung dessen ist.

Zum Beispiel, etwas Verschlüsselung annehmend, haben wir den folgenden β-reductions: .

&eta;-conversion

Eta-Konvertierung drückt die Idee von extensionality aus, der in diesem Zusammenhang ist, dass zwei Funktionen dasselbe sind, wenn, und nur wenn sie dasselbe Ergebnis für alle Argumente geben. Eta-Umwandlungsbekehrte zwischen, und wann auch immer frei darin nicht scheint.

Normale Formen und Zusammenfluss

Für die ungetippte Lambda-Rechnung β-reduction weil normalisiert eine Neuschreiben-Regel weder stark noch normalisiert schwach.

Jedoch kann es gezeigt werden, dass β-reduction Nebenfluss ist. (Natürlich arbeiten wir bis zu α-conversion, d. h. wir denken, dass zwei normale Formen gleich sind, wenn es zu α-convert ein in den anderen möglich ist.)

Deshalb haben sowohl stark normalisierende Begriffe als auch schwach normalisierende Begriffe eine einzigartige normale Form. Um Begriffe stark zu normalisieren, wie man versichert, gibt jede Verminderungsstrategie die normale Form nach, wohingegen, um Begriffe schwach zu normalisieren, einige Verminderungsstrategien scheitern können, es zu finden.

Verschlüsselung datatypes

Die grundlegende Lambda-Rechnung kann verwendet werden, um booleans, Arithmetik, Datenstrukturen und recursion, wie illustriert, in den folgenden Paragraphen zu modellieren.

Arithmetik in der Lambda-Rechnung

Es gibt mehrere mögliche Weisen, die natürlichen Zahlen in der Lambda-Rechnung zu definieren, aber bei weitem sind die allgemeinsten die Kirchziffern, die wie folgt definiert werden können:

::::

und so weiter. Oder das Verwenden der abwechselnden Syntax, die oben in der Notation präsentiert ist:

::::

Eine Kirchziffer ist eine höherwertige Funktion — sie nimmt eine Funktion des einzelnen Arguments, und gibt eine andere Funktion des einzelnen Arguments zurück. Die Kirchziffer ist eine Funktion, die eine Funktion als Argument nimmt und die-th Zusammensetzung, d. h. die Funktion zurückgibt, die mit sich Zeiten zusammengesetzt ist. Das wird angezeigt und ist tatsächlich die-th Macht (betrachtet als ein Maschinenbediener); wird definiert, um die Identitätsfunktion zu sein. Solche wiederholten Zusammensetzungen (einer einzelnen Funktion) folgen den Gesetzen von Hochzahlen, der ist, warum diese Ziffern für die Arithmetik verwendet werden können. (In der ursprünglichen Lambda-Rechnung der Kirche war der formelle Parameter eines Lambda-Ausdrucks erforderlich, mindestens einmal im Funktionskörper vorzukommen, der die obengenannte Definition von Unmöglichem gemacht hat.)

Wir können eine Nachfolger-Funktion definieren, die eine Zahl nimmt und durch das Hinzufügen einer zusätzlichen Anwendung zurückkehrt:

:

Weil die-th Zusammensetzung von gelassenen mit der-th Zusammensetzung dessen die-th Zusammensetzung dessen gibt, kann Hinzufügung wie folgt definiert werden:

:

kann als eine Funktion gedacht werden, die zwei natürliche Zahlen als Argumente nimmt und eine natürliche Zahl zurückgibt; es kann das nachgeprüft werden

:und:

sind gleichwertige Lambda-Ausdrücke. Seit dem Hinzufügen zu einer Zahl kann durch das Hinzufügen 1mal vollbracht werden, eine gleichwertige Definition ist:

:

Ähnlich kann Multiplikation als definiert werden

:

Wechselweise

:

seit dem Multiplizieren und ist dasselbe als das Wiederholen der hinzufügen Funktionszeiten und dann die Verwendung davon zur Null.

Exponentiation hat eine ziemlich einfache Übergabe in Kirchziffern, nämlich

:

Die Vorgänger-Funktion, die durch für eine positive ganze Zahl definiert ist, und ist beträchtlich schwieriger. Die Formel

:

kann durch die Vertretung induktiv davon gültig gemacht werden, wenn T, dann dafür anzeigt. Zwei andere Definitionen dessen werden unten, das ein Verwenden conditionals und die anderen Verwenden-Paare gegeben. Mit der Vorgänger-Funktion ist Subtraktion aufrichtig. Das Definieren

:

Erträge wenn und sonst.

Logik und Prädikate

Durch die Tagung werden die folgenden zwei Definitionen (bekannt als Kirche booleans) für die Boolean-Werte verwendet und:

::

:: (Bemerken Sie, dass das zur Kirchziffer-Null gleichwertig ist, die oben definiert ist)

Dann, mit diesen zwei λ-terms, können wir einige Logikmaschinenbediener definieren (das sind gerade mögliche Formulierungen; andere Ausdrücke sind ebenso richtig):

::::

Wir sind jetzt im Stande, einige logische Funktionen zum Beispiel zu schätzen:

:::::

und wir sehen, dass das dazu gleichwertig ist.

Ein Prädikat ist eine Funktion, die einen Boolean-Wert zurückgibt. Das grundsätzlichste Prädikat ist, der zurückkehrt, wenn sein Argument die Kirchziffer ist, und wenn sein Argument eine andere Kirchziffer ist:

:

Das folgende Prädikat prüft, ob das erste Argument weniger ist als oder gleich dem zweiten:

:

und seitdem, wenn und es aufrichtig ist, um ein Prädikat für die numerische Gleichheit zu bauen.

Die Verfügbarkeit von Prädikaten und die obengenannte Definition dessen und machen es günstig, Ausdrücke "wenn dann sonst" in der Lambda-Rechnung zu schreiben. Zum Beispiel kann die Vorgänger-Funktion als definiert werden:

:

der durch die Vertretung induktiv nachgeprüft werden kann, dass das das Hinzufügen  1 Funktion für> 0 ist.

Paare

Ein (2-Tupel-) Paar kann in Bezug auf definiert werden und, indem es die Kirchverschlüsselung für Paare verwendet. Zum Beispiel, fasst das Paar kurz zusammen , gibt das erste Element des Paares zurück, und gibt das zweite zurück.

:::::

Eine verbundene Liste kann entweder als die NULL für die leere Liste, oder als von einem Element und einer kleineren Liste definiert werden. Das Prädikat prüft für den Wert. (Wechselweise, mit, begegnet die Konstruktion das Bedürfnis nach einem ausführlichen UNGÜLTIGEN Test).

Als ein Beispiel des Gebrauches von Paaren kann die Shift-And-Increment-Funktion, die dazu kartografisch darstellt, als definiert werden

:

der uns erlaubt, vielleicht die durchsichtigste Version der Vorgänger-Funktion zu geben:

:

Recursion und befestigte Punkte

Recursion ist die Definition einer Funktion mit der Funktion selbst; auf dem Gesicht davon erlaubt Lambda-Rechnung das nicht (wir können uns auf einen Wert nicht beziehen, der noch innerhalb des Lambda-Begriffes definiert werden soll, der definiert, dass derselbe Wert, wie alle Funktionen in der Lambda-Rechnung anonym sind). Jedoch ist dieser Eindruck irreführend: in&ensp; &ensp;both x  beziehen sich auf denselben Lambda-Begriff, y, so ist es für einen Lambda-Ausdruck - hier y möglich - eingeordnet zu werden, um sich als sein Argument-Wert durch die Selbstanwendung zu erhalten.

Betrachten Sie zum Beispiel die durch rekursiv als definierte Factorial-Funktion

:.

Im Lambda-Ausdruck, der diese Funktion vertreten soll, wie man annehmen wird, wird ein Parameter (normalerweise der erste) den Lambda-Ausdruck selbst als sein Wert erhalten, so dass, es - Verwendung nennend, davon sich zu einem Argument - auf recursion belaufen wird. Um so recursion das beabsichtigte als selbst zu erreichen, in Argument (genannt hier) Verweise anzubringen, muss immer zu sich innerhalb des Funktionskörpers an einem Anruf-Punkt passiert werden:

:

::: with&ensp; &ensp;to, halten so&ensp;

&ensp;and :

Die Selbstanwendung erreicht Erwiderung hier, den Lambda-Ausdruck der Funktion der folgenden Beschwörung als ein Argument-Wert weitergebend, es bereitstellend, um Verweise angebracht und dort genannt zu werden.

Das behebt das spezifische Problem der Factorial-Funktion, aber wir würden gern eine allgemeine Lösung haben, d. h. das nicht Zwingen eines spezifischen schreibt für jede rekursive Funktion um:

:::: with&ensp; &ensp;to, halten so&ensp; &ensp;and

: &ensp;where&ensp;

::: so that&ensp;

In Anbetracht eines Lambda-Begriffes mit dem ersten Argument, das rekursiven Anruf (z.B hier) vertritt, wird der feste Punkt combinator einen Selbstwiederholen-Lambda-Ausdruck zurückgeben, der die rekursive Funktion (hier) vertritt. Die Funktion braucht zu sich an keinem Punkt ausführlich passiert zu werden, weil die Selbsterwiderung im Voraus eingeordnet wird, wenn es geschaffen wird, um jedes Mal getan zu werden, wenn es genannt wird. So wird der ursprüngliche Lambda-Ausdruck in sich am Anruf-Punkt erfrischt, Selbstverweisung erreichend.

Tatsächlich gibt es viele mögliche Definitionen für diesen Maschinenbediener, den einfachsten von ihnen zu sein:

:

In der Lambda-Rechnung,   ist ein fester Punkt dessen, als er sich ausbreitet zu:

:::::

Jetzt, um unseren rekursiven Anruf zur Factorial-Funktion durchzuführen, würden wir einfach rufen, wo n die Zahl ist, berechnen wir den factorial dessen. Gegebener n = 4, zum Beispiel, gibt das:

:::::::::::::::::::

Jede rekursiv definierte Funktion kann als ein fester Punkt von etwas angemessen definierter Funktion gesehen werden, die über den rekursiven Anruf mit einem Extraargument, und deshalb, das Verwenden schließt, jede rekursiv definierte Funktion kann als ein Lambda-Ausdruck ausgedrückt werden. Insbesondere wir können jetzt die Subtraktion, die Multiplikation und das Vergleich-Prädikat von natürlichen Zahlen rekursiv sauber definieren.

Standardbegriffe

Bestimmte Begriffe haben Namen allgemein akzeptiert:

:

:::::

Getippte Lambda-Rechnungen

Berechenbare Funktionen und Lambda-Rechnung

Eine Funktion F: N  N natürlicher Zahlen ist eine berechenbare Funktion, wenn, und nur wenn dort ein solcher Lambda-Ausdruck f besteht, dass für jedes Paar von x, y in N, F (x) =y wenn und nur wenn f =, wo und die Kirchziffern entsprechend x und y, beziehungsweise und = Bedeutung der Gleichwertigkeit mit der Beta-Verminderung sind. Das ist eine der vielen Weisen, Berechenbarkeit zu definieren; sieh die Kirch-Turing-These für eine Diskussion anderer Annäherungen und ihrer Gleichwertigkeit.

Unentscheidbarkeit der Gleichwertigkeit

Es gibt keinen Algorithmus, der als Eingangszwei-Lambda-Ausdrücke und Produktionen oder je nachdem nimmt, ob die zwei Ausdrücke gleichwertig sind. Das war historisch das erste Problem, für das Unentscheidbarkeit bewiesen werden konnte. Wie für einen Beweis der Unentscheidbarkeit üblich ist, zeigt der Beweis, dass keine berechenbare Funktion die Gleichwertigkeit entscheiden kann. Die These der Kirche wird dann angerufen, um zu zeigen, dass kein Algorithmus so tun kann.

Der Beweis der Kirche reduziert zuerst das Problem auf die Bestimmung, ob ein gegebener Lambda-Ausdruck eine normale Form hat. Eine normale Form ist ein gleichwertiger Ausdruck, der noch weiter laut der durch die Form auferlegten Regeln nicht reduziert werden kann. Dann nimmt er an, dass dieses Prädikat berechenbar ist, und folglich in der Lambda-Rechnung ausgedrückt werden kann. Gebäude arbeitet früher durch Kleene und das Konstruieren von für Lambda-Ausdrücke numerierendem Gödel, er baut einen Lambda-Ausdruck, der nah dem Beweis des ersten Unvollständigkeitslehrsatzes von Gödel folgt. Wenn auf seine eigene Zahl von Gödel angewandt wird, resultiert ein Widerspruch.

Lambda-Rechnung und Programmiersprachen

Wie hingewiesen, durch das 1965-Papier von Peter Landin können folgende Verfahrensprogrammiersprachen in Bezug auf die Lambda-Rechnung verstanden werden, die die grundlegenden Mechanismen für die Verfahrensabstraktion und das Verfahren (Unterprogramm) Anwendung zur Verfügung stellt.

Lambda-Rechnung reifies "fungiert" und macht sie erstklassige Gegenstände, der Durchführungskompliziertheit erhebt, wenn es durchgeführt wird.

Erstklassige Funktionen

Zum Beispiel im Lispeln kann die 'Quadrat'-Funktion als ein Lambda-Ausdruck wie folgt ausgedrückt werden:

(Lambda (x) (* x x))

</Quelle>

oder in Haskell ausgedrücktes dasselbe:

\x-> x*x - wo \den griechischen λ\anzeigt

</Quelle>

Das obengenannte Beispiel ist ein Ausdruck, der zu einer erstklassigen Funktion bewertet. Das Symbol schafft eine anonyme Funktion, in Anbetracht einer Liste von Parameter-Namen, - gerade ein einzelnes Argument in diesem Fall und ein Ausdruck, der als der Körper der Funktion bewertet wird. Das Beispiel von Haskell ist identisch. Anonyme Funktionen werden manchmal Lambda-Ausdrücke genannt.

Zum Beispiel haben Pascal und viele andere befehlende Sprachen lange vorübergehende Unterprogramme als Argumente für andere Unterprogramme durch den Mechanismus von Funktionszeigestöcken unterstützt. Jedoch sind Funktionszeigestöcke nicht genügend Bedingung für Funktionen, erste Klasse datatype weil zu sein, wenn, und nur wenn neue Beispiele einer Funktion in der Durchlaufzeit geschaffen werden können, die Funktionen erste Klasse datatype sind. Und diese Laufzeitentwicklung von Funktionen wird in C ++, Plausch, und mehr kürzlich in Scala, Eiffel ("Agenten") und C# ("Delegierte"), unter anderen unterstützt.

Unten ist ein Beispiel ausgedrückt als Eiffel "Reihenreagenz"

Reagenz (x: ECHT): ECHT Resultieren Sie wirklich: = x * beenden x

</Quelle>

Der Gegenstand entspricht dem Lambda-Ausdruck λx.x*x (mit dem Anruf durch den Wert), weil es einer Variable zugeteilt oder zu Routinen verteilt, d. h. wie jeder andere Ausdruck behandelt werden kann.

Ein Pythonschlange-Beispiel davon verwendet die Lambda-Form von Funktionen:

func = Lambda x: x ** 2

</Quelle>

Das schafft eine neue anonyme Funktion und nennt sie func, der zu anderen Funktionen passiert werden kann, die in Variablen versorgt sind, usw. kann Pythonschlange auch jede andere Funktion behandeln, die mit dem Standard def Behauptung als erstklassige Gegenstände geschaffen ist.

Dasselbe hält für den Plausch-Ausdruck

[:x | x * x]

</Quelle>

Das ist erstklassiger Gegenstand (Block-Verschluss), der in Variablen versorgt werden kann, die als Argumente usw. passiert sind.

Ein ähnlicher Ausdruck mit C ++ 11 anonyme Funktion, aber spezifisch für ganze Zahlen, ist:

[] (interne Nummer i)-> interne Nummer {kehren i * ich zurück; }\

</Quelle>

In JavaScript seit der Version 1.8, der Notation:

fungieren Sie (x) x*x;

</Quelle>

wird verwendet. In älteren Versionen

fungieren Sie (x) {geben x*x zurück; }\

</Quelle>

In Scala:

(x:Int) => x*x

</Quelle>

In

F#:

(Spaß x-> x * x)

</Quelle>

In D:

x => x * x//, wenn Parameter-Typ abgeleitet werden kann

(interne Nummer x) => x * x//, wenn Parameter-Typ angegeben werden muss

</Quelle>

Verminderungsstrategien

Ob ein Begriff normalisiert oder nicht, und wie viel Arbeit im Normalisieren davon getan werden muss, wenn es ist, hängt weit gehend von der verwendeten Verminderungsstrategie ab. Die Unterscheidung zwischen Verminderungsstrategien bezieht sich auf die Unterscheidung auf funktionellen Programmiersprachen zwischen eifriger Einschätzung und fauler Einschätzung.

Die vollen Beta-Verminderungen: Jeder redex kann jederzeit reduziert werden. Das bedeutet im Wesentlichen den Mangel an jeder besonderen Verminderungsstrategie — hinsichtlich reducibility, "alle Wetten sind von".

Ordnung von Applicative: Der niedrigstwertige, innerste redex wird immer zuerst reduziert. Intuitiv bedeutet das, dass Argumente einer Funktion immer vor der Funktion selbst reduziert werden. Ordnung von Applicative versucht immer, Funktionen auf normale Formen anzuwenden, selbst wenn das nicht möglich ist.

:Most-Programmiersprachen (einschließlich des Lispelns, ML und der befehlenden Sprachen wie C und Java) werden als "streng" beschrieben, bedeutend, dass auf das Nichtnormalisieren von Argumenten angewandte Funktionen nichtnormalisieren. Das wird im Wesentlichen mit applicative Ordnung, Anruf durch die Wertverminderung (sieh unten) getan, aber gewöhnlich "eifrige Einschätzung" genannt.

Normale Ordnung: Der leftmost, äußerster redex wird immer zuerst reduziert. D. h. wann immer möglich werden die Argumente in den Körper einer Abstraktion eingesetzt, bevor die Argumente reduziert werden.

Rufen Sie namentlich: Als normale Ordnung, aber keine Verminderungen werden innerhalb von Abstraktionen durchgeführt. Zum Beispiel ist in der normalen Form gemäß dieser Strategie, obwohl es den redex enthält.

Anruf durch den Wert: Nur die äußersten redexes werden reduziert: Ein redex wird nur reduziert, als seine rechte Seite zu einem Wert (Variable oder Lambda-Abstraktion) abgenommen ist.

Anruf durch das Bedürfnis: Als normale Ordnung, aber Funktionsanwendungen, die Begriffe stattdessen kopieren würden, nennen das Argument, das dann reduziert wird nur, "wenn es erforderlich ist". Herbeigerufen praktische Zusammenhänge "faule Einschätzung". In Durchführungen nimmt dieser "Name" die Form eines Zeigestocks mit dem durch einen thunk vertretenen redex an.

Ordnung von Applicative ist nicht eine Normalisieren-Strategie. Das übliche Gegenbeispiel ist wie folgt: Definieren Sie wo. Dieser komplette Ausdruck enthält nur einen redex, nämlich der ganze Ausdruck; sein Wiederkanal ist wieder. Da das die einzige verfügbare Verminderung ist, hat keine normale Form (laut jeder Einschätzungsstrategie). Mit applicative Ordnung wird der Ausdruck durch das erste Reduzieren auf die normale Form reduziert (da es der niedrigstwertige redex ist), aber da keine normale Form hat, applicative Ordnung scheitert, eine normale Form dafür zu finden.

Im Gegensatz ist normale Ordnung so genannt, weil es immer die Normalisieren-Verminderung findet, wenn man besteht. Im obengenannten Beispiel, nimmt laut der normalen Ordnung zu mir, einer normalen Form ab. Ein Nachteil besteht darin, dass redexes in den Argumenten kopiert werden kann, auf kopierte Berechnung hinauslaufend (zum Beispiel, nimmt zum Verwenden dieser Strategie ab; jetzt gibt es zwei redexes, so braucht volle Einschätzung noch zwei Schritte, aber wenn das Argument zuerst reduziert worden war, würde es jetzt niemanden geben).

Der positive Umtausch, Applicative-Ordnung zu verwenden, besteht darin, dass sie unnötige Berechnung nicht verursacht, wenn alle Argumente verwendet werden, weil sie nie Argumente einsetzt, die redexes enthalten, und sie folglich nie kopieren muss (der Arbeit kopieren würde). Im obengenannten Beispiel, in der Applicative-Ordnung nimmt zuerst zu und dann zur normalen Ordnung ab, zwei Schritte statt drei machend.

Am meisten rein funktionelle Programmiersprachen (namentlich Miranda und seine Nachkommen, einschließlich Haskells), und die Probesprachen des Lehrsatzes provers, verwenden faule Einschätzung, die im Wesentlichen dasselbe als Anruf durch das Bedürfnis ist. Das ist der normalen Ordnungsverminderung ähnlich, aber der Anruf durch das Bedürfnis schafft, die Verdoppelung der dem normalen Ordnungsverminderungsverwenden-Teilen innewohnenden Arbeit zu vermeiden. Im Beispiel, das oben angeführt ist, nimmt dazu ab, der zwei redexes hat, aber im Anruf durch das Bedürfnis werden sie mit demselben Gegenstand vertreten aber nicht so kopiert, wenn einer der andere reduziert wird, ist auch.

Ein Zeichen über die Kompliziertheit

Während die Idee von der Beta-Verminderung einfach genug scheint, ist es nicht ein Atomschritt, in dem es nichttriviale Kosten haben muss, wenn es rechenbetonte Kompliziertheit schätzt. Um genau zu sein, muss man irgendwie die Position von allen Ereignissen der bestimmten Variable im Ausdruck finden, Zeitkosten einbeziehend, oder man muss diese Positionen irgendwie nachgehen, Raumkosten einbeziehend. Eine naive Suche nach den Positionen darin ist O (n) in der Länge n dessen. Das hat zur Studie von Systemen geführt, die ausführlichen Ersatz verwenden. Der Direktor von Sinot spannt bieten eine Weise an, die Positionen von freien Variablen in Ausdrücken zu verfolgen.

Parallelismus und Parallelität

Das Kirch-Rosser-Eigentum der Lambda-Rechnung bedeutet, dass Einschätzung (β-reduction) in jeder Ordnung sogar in der Parallele ausgeführt werden kann. Das bedeutet, dass verschiedene nichtdeterministische Einschätzungsstrategien wichtig sind. Jedoch bietet die Lambda-Rechnung keine ausführlichen Konstruktionen für den Parallelismus an. Man kann Konstruktionen wie Terminwaren zur Lambda-Rechnung hinzufügen. Andere Prozess-Rechnungen sind entwickelt worden, um Kommunikation und Parallelität zu beschreiben.

Semantik

Die Tatsache, dass die Lambda-Rechnungsbegriff-Tat als Funktionen zu anderen Lambda-Rechnungsbegriffen, und sogar zu sich, zu Fragen über die Semantik der Lambda-Rechnung geführt hat. Konnte eine vernünftige Bedeutung Lambda-Rechnungsbegriffen zugeteilt werden? Die natürliche Semantik sollte einen Satz D isomorph zum Funktionsraum D  D, Funktionen auf sich finden. Jedoch nicht nichttrivial kann solcher D durch cardinality Einschränkungen bestehen, weil der Satz aller Funktionen von D in D größeren cardinality hat als D.

In den 1970er Jahren hat Dana Scott gezeigt, dass, wenn nur dauernde Funktionen betrachtet wurden, ein Satz oder Gebiet D mit dem erforderlichen Eigentum gefunden werden konnten, so ein Modell für die Lambda-Rechnung zur Verfügung stellend.

Diese Arbeit hat auch die Basis für die denotational Semantik von Programmiersprachen gebildet.

Siehe auch

• Applicative Rechensysteme - Behandlung von Gegenständen im Stil der Lambda-Rechnung
• Binäre Lambda-Rechnung - Eine Version der Lambda-Rechnung mit der binären Eingabe/Ausgabe, einer binären Verschlüsselung von Begriffen und einer benannten universalen Maschine.
• Rechnung von Aufbauten - Eine getippte Lambda-Rechnung mit Typen als erstklassige Werte
• Kartesianische geschlossene Kategorie - Eine Einstellung für die Lambda-Rechnung in der Kategorie-Theorie
• Kategorische abstrakte Maschine - Ein Modell der Berechnung, die auf die Lambda-Rechnung anwendbar

ist

• Logik von Combinatory - Eine Notation für die mathematische Logik ohne Variablen
• Isomorphismus des Currys-Howard - Die formelle Ähnlichkeit zwischen Programmen und Beweisen
• Bereichstheorie - Studie von bestimmtem posets das Geben denotational Semantik für die Lambda-Rechnung
• Einschätzungsstrategie - Regeln für die Einschätzung von Ausdrücken auf Programmiersprachen
• Ausführlicher Ersatz - Die Theorie des Ersatzes, wie verwendet, in β-reduction
• Formel von Harrop - Eine Art konstruktive logische solche Formel, dass Beweise Lambda-Begriffe sind
• Rechnung von Kappa - Eine Entsprechung der ersten Ordnung der Lambda-Rechnung
• Kleene-Rosser Paradox - Eine Demonstration, dass eine Form der Lambda-Rechnung inkonsequenter ist
• Ritter der Lambda-Rechnung - Eine halberfundene Organisation des LISPELNS und der Schema-Hacker
• Lambda-Würfel - Ein Fachwerk für einige Erweiterungen der getippten Lambda-Rechnung
• Rechnung des Lambdas-mu - Eine Erweiterung der Lambda-Rechnung, um klassische Logik zu behandeln
• Das Neuschreiben - Transformation von formulæ in formellen Systemen
• SECD Maschine - Eine virtuelle Maschine hat für die Lambda-Rechnung entwickelt
• Einfach getippte Lambda-Rechnung - Version (En) mit einem einzelnen Typ-Konstrukteur
• LAUFEN SIE combinator Rechnung - Ein rechenbetontes System SKI, das auf dem S, K und mir combinators gestützt ist
• System F - Eine getippte Lambda-Rechnung mit Typ-Variablen
• Getippte Lambda-Rechnung - Lambda-Rechnung mit getippten Variablen (und Funktionen)
• Universale Turing Maschine - Eine formelle Rechenmaschine, die zur Lambda-Rechnung gleichwertig

ist

• Unlambda - Eine esoterische funktionelle Programmiersprache, die auf der combinatory Logik gestützt ist

Weiterführende Literatur

• Abelson, Harold & Gerald Jay Sussman. Struktur und Interpretation von Computerprogrammen. Die MIT-Presse. Internationale Standardbuchnummer 0-262-51087-1.
• Hendrik Pieter Barendregt [ftp://ftp.cs.ru.nl/pub/CompMath.Found/lambda.pdf Einführung in die Lambda-Rechnung].
• Henk Barendregt, Der Einfluss der Lambda-Rechnung in der Logik und Informatik. Die Meldung der Symbolischen Logik, des Bands 3, der Nummer 2, Juni 1997.
• Barendregt, Hendrik Pieter, Der Typ Freie Lambda-Rechnung pp1091-1132 des Handbuches der Mathematischen Logik, Nordholland (1977) internationale Standardbuchnummer 0 7204 2285 X
• Cardone und Hindley, 2006. Geschichte der Lambda-Rechnung und Combinatory Logik. In Gabbay und Woods (Hrsg.). Handbuch der Geschichte der Logik, vol. 5. Elsevier.
• Kirche, Alonzo, Ein unlösbares Problem der elementaren Zahlentheorie, amerikanische Zeitschrift der Mathematik, 58 (1936), Seiten 345-363. Dieses Papier enthält den Beweis, dass die Gleichwertigkeit von Lambda-Ausdrücken im Allgemeinen nicht entscheidbar ist.
• Kleene, Stephen, Eine Theorie von positiven ganzen Zahlen in der formalen Logik, amerikanischen Zeitschrift der Mathematik, 57 (1935), Seiten 153-173 und 219-244. Enthält die Lambda-Rechnungsdefinitionen von mehreren vertrauten Funktionen.
• Landin, Peter, Eine Ähnlichkeit Zwischen dem Algol 60 und der Lambda-Notation der Kirche, den Kommunikationen des ACM, vol. 8, Nr. 2 (1965), Seiten 89-101. Verfügbar von der ACM Seite. Eine klassische Zeitung, die Wichtigkeit von der Lambda-Rechnung als eine Basis für Programmiersprachen hervorhebend.
• Larson, Jim, Eine Einführung in die Lambda-Rechnung und das 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 an Übungen. Zeichen für einen Kurs im Mathematischen Logik-MSc an der Universität von Manchester.
• de Queiroz, Ruy J.G.B. (2008) Auf Verminderungsregeln, Bedeutung als der Gebrauch und Probetheoretischer Semantik. Studia Logica, 90 (2):211-247. Eine Zeitung, die eine formelle Untermauerung der Idee von der 'Bedeutung gibt, ist Gebrauch', der, selbst wenn basiert auf Beweisen es von der probetheoretischen Semantik als in der Dummett-Prawitz Tradition verschieden ist, da es die Verminderung als die Regeln nimmt, die Bedeutung geben.

Monografien/Lehrbücher für Studenten im Aufbaustudium:

• Morten Heine Sørensen, Paweł Urzyczyn, Vorträge auf dem Isomorphismus des Currys-Howard, Elsevier, 2006, internationale Standardbuchnummer 0-444-52077-5 sind eine neue Monografie, die die Hauptthemen der Lambda-Rechnung von der Vielfalt ohne Typen, zu am meisten getippten Lambda-Rechnungen, einschließlich neuerer Entwicklungen wie reine Typ-Systeme und der Lambda-Würfel behandelt. Es bedeckt subtippende Erweiterungen nicht.

• Deckel-Lambda-Rechnungen von einer praktischen Typ-Systemperspektive; einige Themen wie abhängige Typen werden nur erwähnt, aber das Subschreiben ist ein wichtiges Thema.

Einige Teile dieses Artikels basieren auf dem Material von FOLDOC, der damit verwendet ist.

Links

• Achim Jung, eine kurze Einführung in die Lambda-Rechnung - (PDF)
• David C. Keenan, um eine Spottdrossel zu analysieren: Eine grafische Notation für die Lambda-Rechnung mit der belebten Verminderung
• Raúl Rojas, eine Tutoreinführung in die Lambda-Rechnung - (PDF)
• Peter Selinger, Vortrag-Zeichen auf der Lambda-Rechnung - (PDF)
• L. Allison, Einige rechtskräftige λ-calculus Beispiele
• Georg P. Loczewski, die Lambda-Rechnung und ++
• Bret Victor, Alligator-Eier: Ein Rätsel-Spiel, das auf der Lambda-Rechnung basiert

ist

• Lambda-Rechnung auf der Website von Safalra
• LCI Lambda-Dolmetscher ein einfacher noch der mächtige reine Rechnungsdolmetscher
• Lambda-Rechnung verbindet sich auf dem Äußersten Lambda
• Mike Thyer, Lambda-Zeichner von Trickfilmen, ein grafisches Java applet das Demonstrieren alternativer Verminderungsstrategien.
• Eine Einführung in die Lambda-Rechnung und das Schema, durch Jim Larson