Kombinationslogik

Kombinationslogik ist eine Notation, um die Notwendigkeit zu beseitigen quantifiziert Variablen in Mathematische Logik. Es wurde von vorgestellt von Moses Schönfinkel^[1] und Haskell Curry,^[2] und wurde in jüngerer Zeit in verwendet Informatik als theoretische Berechnungsmodell und auch als Grundlage für die Gestaltung von Funktionale Programmiersprachen. Es basiert auf Kombinatoren die von vorgestellt wurden durch Schönfinkel 1920 mit der Idee, eine analoge Möglichkeit zu bieten, Funktionen aufzubauen und Variablen zu entfernen - insbesondere in Prädikatlogik. Ein Kombinator ist ein Funktion höherer Ordnung Das benutzt nur Funktionsanwendung und früher definierte Kombinatoren, um ein Ergebnis aus seinen Argumenten zu definieren.

In Mathematik

Die Kombinationslogik war ursprünglich als "prä-logisch" gedacht, die die Rolle von klarstellen würde Quantifizierte Variablen in der Logik, im Wesentlichen durch Eliminieren. Eine andere Möglichkeit, quantifizierte Variablen zu eliminieren, ist Quine's Prädikatfunk -Logik. Während Ausdruckskraft von kombinatorischer Logik übersteigt typischerweise die von Logik erster Ordnung, die ausdrucksstarke Kraft von Prädikatfunk -Logik ist identisch mit der der Ersten Ordnung (Logik erster Ordnung (Quine 1960, 1966, 1976).

Der ursprüngliche Erfinder der Kombinationslogik, Moses Schönfinkel, veröffentlichte nach seinem ursprünglichen Papier von 1924 nichts über kombinatorische Logik. Haskell Curry entdeckte die Kombinatoren wieder, während er als Ausbilder bei arbeitete Princeton Universität Ende 1927.^[3] In den späten 1930er Jahren, Alonzo -Kirche und seine Schüler von Princeton erfanden einen konkurrierenden Formalismus zur funktionalen Abstraktion, die Lambda -Kalkül, was sich als beliebter als kombinatorische Logik erwies. Das Ergebnis dieser historischen Eventualitäten war, dass fast alle Arbeit Haskell Curry und seine Schüler oder von Robert Feys in Belgien. Curry und Feys (1958) und Curry et al. (1972) Umfrage Die frühe Geschichte der Kombinationslogik. Für eine modernere Behandlung der kombinatorischen Logik und des Lambda -Kalküls siehe das Buch von Barendregt,^[4] welches die überprüft Modelle Dana Scott In den 1960er und 1970er Jahren für kombinatorische Logik entwickelt.

Im Computer

Im InformatikKombinationslogik wird als vereinfachtes Modell von verwendet Berechnung, benutzt in Computerbarkeitstheorie und Beweistheorie. Trotz seiner Einfachheit erfasst die Kombinationslogik viele wesentliche Merkmale der Berechnung.

Kombinationslogik kann als Variante der angesehen werden Lambda -Kalkül, in denen Lambda -Ausdrücke (dargestellt funktionelle Abstraktion) durch einen begrenzten Satz von ersetzt werden Kombinatoren, primitive Funktionen ohne freie Variablen. Es ist leicht, Lambda -Ausdrücke in Kombinatorausdrücke zu verwandeln, und die Verringerung der Kombinator ist viel einfacher als die Lambda -Reduktion. Daher wurde die Kombinationslogik verwendet, um einige zu modellieren Nicht-Strikt Funktionelle Programmierung Sprachen und Hardware-. Die reinste Form dieser Ansicht ist die Programmiersprache Unambda, deren alleinige Primitive die S- und K -Kombinators sind, die mit Zeicheneingang/Ausgang erweitert werden. Obwohl Unambda keine praktische Programmiersprache hat, ist es von einem theoretischen Interesse.

Kombinationslogik kann eine Vielzahl von Interpretationen erhalten. Viele frühe Papiere von Curry zeigten, wie man Axiom -Sets für herkömmliche Logik in kombinatorische Logikgleichungen übersetzt (Hindley und Meredith 1990). Dana Scott In den 1960er und 1970er Jahren zeigten, wie man heiratet Modelltheorie und Kombinationslogik.

Zusammenfassung des Lambda -Kalküls

Lambda Calculus befasst sich mit Objekten, die genannt werden Lambda, die durch die folgenden drei Formen von Strings dargestellt werden können:

• ${\ displayStyle v}$
• ${\ displaystyle \ lambda v.e_ {1}}$
• ${\ displayStyle (e_ {1} e_ {2})}$

wo ${\ displayStyle v}$ ist ein variabler Name, der aus einem vordefinierten unendlichen Satz von variablen Namen stammt, und ${\ displayStyle e_ {1}}$ und ${\ displayStyle e_ {2}}$ sind lambda-terms.

Bedingungen der Form ${\ displaystyle \ lambda v.e_ {1}}$ werden genannt Abstraktionen. Die Variable v wird genannt formaler Parameter der Abstraktion und ${\ displayStyle e_ {1}}$ ist der Karosserie der Abstraktion. Der Begriff ${\ displaystyle \ lambda v.e_ {1}}$ repräsentiert die Funktion, die, die auf ein Argument angewendet wird, den formalen Parameter bindet v zum Argument und berechnet dann den resultierenden Wert von ${\ displayStyle e_ {1}}$- Das heißt, es kehrt zurück ${\ displayStyle e_ {1}}$mit jedem Auftreten von v ersetzt durch das Argument.

Bedingungen der Form ${\ displayStyle (e_ {1} e_ {2})}$ werden genannt Anwendungen. Aufruf oder Ausführung von Anwendungsmodellfunktionen: Die Funktion wird durch dargestellt ${\ displayStyle e_ {1}}$ ist aufgerufen zu werden, mit ${\ displayStyle e_ {2}}$ als Argument, und das Ergebnis wird berechnet. Wenn ${\ displayStyle e_ {1}}$ (manchmal genannt das Applicand) ist eine Abstraktion, der Begriff kann seinreduziert: ${\ displayStyle e_ {2}}$, das Argument, kann in den Körper von durchgesetzt werden ${\ displayStyle e_ {1}}$ anstelle des formalen Parameters von ${\ displayStyle e_ {1}}$und das Ergebnis ist ein neuer Lambda -Begriff, der ist Äquivalent zum alten. Wenn ein Lambda -Term keine Teiler der Form enthält ${\ displayStyle ((\ lambda v.e_ {1}) e_ {2})}$ dann kann es nicht reduziert werden und soll in sein Normale Form.

Der Ausdruck ${\ displayStyle e [v: = a]}$ repräsentiert das Ergebnis der Begriff E und alle freien Ereignisse von ersetzen v darin mit a. So schreiben wir

${\ displayStyle ((\ lambda v.e) a) \ rightarrow e [v: = a]}$

Durch Konvention nehmen wir ${\ displayStyle (ABC)}$ als Abkürzung für ${\ displayStyle ((ab) c)}$ (d. h. Anwendung ist links assoziativ).

Die Motivation für diese Definition der Reduktion besteht darin, dass sie das wesentliche Verhalten aller mathematischen Funktionen erfasst. Betrachten Sie beispielsweise die Funktion, die das Quadrat einer Zahl berechnet. Wir könnten schreiben

Das Quadrat von x ist ${\ displayStyle x*x}$

(Verwenden "${\ displayStyle *}$"Um Multiplikation anzuzeigen.) x Hier ist der formaler Parameter der Funktion. Um das Quadrat für ein bestimmtes Argument zu bewerten, sagen wir es 3, setzen wir es anstelle des formalen Parameters in die Definition ein:

Das Quadrat von 3 ist ${\ displayStyle 3*3}$

Um den daraus resultierenden Ausdruck zu bewerten ${\ displayStyle 3*3}$Wir müssten unser Wissen über die Multiplikation und die Zahl 3. zurückgreifen. Da jede Berechnung lediglich eine Zusammensetzung der Bewertung geeigneter Funktionen zu geeigneten primitiven Argumenten ist, reicht dieses einfache Substitutionsprinzip aus, um den wesentlichen Mechanismus der Berechnung zu erfassen. Darüber hinaus in Lambda -Kalkül, Vorstellungen wie '3' und '${\ displayStyle *}$'kann ohne extern definierte primitive Operatoren oder Konstanten dargestellt werden. Es ist möglich, Begriffe in Lambda Calculus zu identifizieren, die, wenn sie angemessen interpretiert werden, wie die Nummer 3 und den Multiplikationsoperator q.v. Kirchenkodierung.

Es ist bekannt, dass Lambda -Kalkül in Bezug Turing -Maschinen); Das heißt, jede Berechnung, die in einem dieser anderen Modelle erreicht werden kann, kann in Lambda -Kalkül und umgekehrt ausgedrückt werden. Laut dem These der KircheBeide Modelle können jede mögliche Berechnung ausdrücken.

Es ist vielleicht überraschend, dass Lambda-Calculus jede denkbare Berechnung darstellen kann, die nur die einfachen Funktionen der Funktionsabstraktion und Anwendung basierend auf der einfachen textuellen Substitution von Begriffen für Variablen anhand der einfachen textuellen Ersatzbegriffe darstellen kann. Noch bemerkenswerter ist jedoch, dass eine Abstraktion nicht einmal erforderlich ist. Kombinationslogik ist ein Modell des Berechnungsmittels, der dem Lambda -Kalkül entspricht, jedoch ohne Abstraktion. Der Vorteil davon ist, dass die Bewertung der Ausdrücke im Lambda -Kalkül sehr kompliziert ist, da die Substitutionssemantik mit großer Sorgfalt spezifiziert werden muss, um variable Erfassungsprobleme zu vermeiden. Im Gegensatz dazu ist die Bewertung der Ausdrücke in der kombinatorischen Logik viel einfacher, da es keinen Substitutionsbegriff gibt.

Kombinatorische Berechnung

Da die Abstraktion die einzige Möglichkeit ist, Funktionen im Lambda -Kalkül herzustellen, muss etwas sie im kombinatorischen Kalkül ersetzen. Anstelle von Abstraktion liefert Kombinationsrechnung eine begrenzte Reihe von primitiven Funktionen, aus denen andere Funktionen erstellt werden können.

Kombinatorische Begriffe

Ein kombinatorischer Begriff hat eine der folgenden Formen:

Syntax	Name	Beschreibung
x	Variable	Ein Zeichen oder eine Zeichenfolge, die einen kombinatorischen Begriff darstellt.
P	Primitive Funktion	Eines der Kombinatorsymbole I, K, S.
(M n)	Anwendung	Anwendung einer Funktion auf ein Argument. M und N sind kombinatorische Begriffe.

Die primitiven Funktionen sind Kombinatorenoder Funktionen, die, wenn sie als Lambda -Begriffe angesehen werden, nein enthalten freie Variablen.

Um die Notationen zu verkürzen, ist eine allgemeine Konvention das ${\ displayStyle (e_ {1} e_ {2} e_ {3} ... e_ {n})}$, oder auch ${\ displayStyle e_ {1} e_ {2} e_ {3} ... e_ {n}}$bezeichnet den Begriff ${\ displayStyle (... ((e_ {1} e_ {2}) e_ {3}) ... e_ {n})}$. Dies ist dieselbe allgemeine Übereinkommen (links-assoziativität) wie bei mehreren Anwendungen im Lambda-Kalkül.

Verringerung der Kombinationslogik

In der Kombinationslogik verfügt jeder primitive Kombinator mit einer Reduktionsregel der Form

(P x₁ ... x_n) = E

wo E ist ein Begriff, der nur Variablen aus dem Satz erwähnt {x₁ ... x_n}. Auf diese Weise verhalten sich primitive Kombinatoren als Funktionen.

Beispiele für Kombinatoren

Das einfachste Beispiel eines Kombinators ist I, der Identitätskombinator, definiert durch

(I x) = x

für alle Begriffe x. Ein weiterer einfacher Kombinator ist K, die ständige Funktionen erzeugt: (K x) ist die Funktion, die für jedes Argument zurückgibt xAlso sagen wir

((K x) y) = x

für alle Begriffe x und y. Oder nach der Übereinkommen für mehrere Anwendungen,

(K x y) = x

Ein dritter Kombinator ist S, was eine verallgemeinerte Version der Anwendung ist:

(S x y z) = ((x z (y z))

S gilt x zu y nach dem ersten Ersatz z in jeden von ihnen. Oder einen anderen Weg, wie x wird angewendet auf y Innerhalb der Umgebung z.

Gegeben S und K, I selbst ist unnötig, da es aus den anderen beiden gebaut werden kann:

((S k k) x))

= (S k k x)

= (K x (K x))

= x

für jede Begriff x. Beachten Sie zwar ((((S k k))x) = ((I x) für jeden x, (S k k) selbst ist nicht gleich zu I. Wir sagen, die Begriffe sind Erweitert gleich. Die Erweiterungsgleichheit erfasst den mathematischen Begriff der Gleichheit der Funktionen: zwei Funktionen sind gleich Wenn sie immer die gleichen Ergebnisse für die gleichen Argumente erzielen. Im Gegensatz dazu erfassen die Begriffe selbst zusammen mit der Verringerung der primitiven Kombinatoren den Begriff vonintensionale Gleichheit von Funktionen: dass zwei Funktionen sind gleich Nur wenn sie identische Implementierungen haben bis zu Die Expansion primitiver Kombinatoren. Es gibt viele Möglichkeiten, eine Identitätsfunktion zu implementieren. (S k k) und I sind unter diesen Wegen. (S k s) ist noch ein anderer. Wir werden das Wort verwenden Äquivalent Um die Erweiterungsgleichheit anzuzeigen, reservieren gleich für identische kombinatorische Begriffe.

Ein interessanterer Kombinator ist der Fixpunktkombinator oder Y Kombinator, mit dem die Implementierung verwendet werden kann Rekursion.

Vollständigkeit der S-K-Basis

S und K kann zusammengesetzt werden, um Kombinatoren zu produzieren, die erweitert gleich sind irgendein Lambda -Begriff und damit durch die These der Kirche zu jeder rechenbaren Funktion. Der Beweis ist, eine Transformation vorzustellen, T[], Das einen willkürlichen Lambda -Term in einen äquivalenten Kombinator umwandelt.

T[] Kann wie folgt definiert werden:

1. T[x] => x
2. T[(E₁ E₂)] => (T[E₁] T[E₂])
3. T[λx.E] => (K T[E]) (wenn x tritt nicht frei in E)
4. T[λx.x] => I
5. T[λx.λy.E] => T[λx.T[λy.E]] (wenn x tritt frei in E)
6. T[λx. (E₁ E₂)] => (S T[λx.E₁] T[λx.E₂]) (wenn x tritt frei in E₁ oder E₂)

Beachten Sie, dass T[] Wie angegeben ist keine gut typische mathematische Funktion, sondern vielmehr ein Begriff Rewriter: Obwohl es schließlich einen Kombinator liefert, kann die Transformation zwischen den Vermittlungsausdrücken erzeugen, die weder Lambda-Begriffe noch Kombinatoren über Regel (5) sind.

Dieser Prozess ist auch als bekannt als Abstraktionsentscheidung. Diese Definition ist erschöpfend: Jeder Lambda -Ausdruck unterliegt genau einer dieser Regeln (siehe Zusammenfassung des Lambda -Kalküls Oben).

Es hängt mit dem Prozess von zusammen Klammerabstraktion, was einen Ausdruck nimmt E Erstellt aus Variablen und Anwendung und erzeugt einen Kombinatorausdruck [x] e, in dem die Variable x nicht frei ist, so dass [x]Ex = E hält. Ein sehr einfacher Algorithmus für die Abstraktion der Klammer wird durch Induktion auf der Struktur von Ausdrücken wie folgt definiert:^[5]

1. [x]y: = K y
2. [x]x: = I
3. [x] (E₁ E₂): = S[x]E₁) ([x]E₂)

Die Abstraktion der Klammer induziert eine Übersetzung von Lambda-Termen zu Kombinatorausdrücken, indem Lambda-Abbindungen unter Verwendung des Bracket-Abstraktionsalgorithmus interpretiert werden.

Umwandlung eines Lambda -Terms in einen äquivalenten kombinatorischen Term

Zum Beispiel werden wir den Lambda -Term konvertieren λx.λy. (y x) zu einem kombinatorischen Begriff:

T[λx.λy. (y x)]

= T[λx.T[λy. (y x)]] (bis 5)

= T[λx. (S T[λy.y] T[λy.x])] (bis 6)

= T[λx. (S i T[λy.x])] (von 4)

= T[λx. (S i (K T[x]))]] (von 3)

= T[λx. (S i (K x))] (durch 1)

= (S T[λx. (S i)] T[λx. (K x)]) (bis 6)

= (S (K (S i)) T[λx. (K x)]) (durch 3)

= (S (K (S i)) (S T[λx.K] T[λx.x])) (bis 6)

= (S (K (S i)) (S (K k k) T[λx.x])) (durch 3)

= (S (K (S i)) (S (K k k) I)) (von 4)

Wenn wir diesen kombinatorischen Begriff auf zwei beliebige Begriffe anwenden x und y (Indem Sie sie in einer Warteschlangengefühle von rechts in den Kombinator füttern), nimmt dies wie folgt ab:

(S (K (S I)) (S (K K) I) x y)

= (K (S I) x (S (K K) I x) y)

= (S I (S (K K) I x) y)

= (I y (S (K K) I x y))

= (y ((S (K K) I x y))

= (y ((K K x (I x) y)))

= (y ((K (I x) y)))

= (y ((I x))

= (y x)

Die kombinatorische Darstellung, (S (K (S i)) (S (K k k) I)) ist viel länger als die Darstellung als Lambda -Begriff, λx.λy. (y x). Dies ist typisch. Im Allgemeinen die T[] Die Konstruktion kann eine Lambda -Länge erweitern n zu einem kombinatorischen LängebegriffΘ(n³).^[6]

Erläuterung des T[] Transformation

Das T[] Transformation ist motiviert durch den Wunsch, Abstraktion zu beseitigen. Zwei Sonderfälle, Regeln 3 und 4, sind trivial: λx.x ist eindeutig gleichbedeutend mit I, und λx.E ist eindeutig äquivalent zu (K T[E]) wenn x erscheint nicht kostenlos in E.

Die ersten beiden Regeln sind ebenfalls einfach: Variablen konvertieren auf sich selbst, und Anwendungen, die in kombinatorischen Begriffen zulässig sind, werden in Kombinatoren konvertiert, indem einfach der Applicand und das Argument in Kombinatoren konvertiert werden.

Es sind Regeln 5 und 6, die von Interesse sind. Regel 5 besagt einfach, dass wir zuerst seinen Körper in einen Kombinator umwandeln und dann die Abstraktion beseitigen müssen, um eine komplexe Abstraktion in einen Kombinator umzuwandeln. Regel 6 beseitigt tatsächlich die Abstraktion.

λx. (E₁ E₂) ist eine Funktion, die ein Argument nimmt, sagen wir aund ersetzt es in den Lambda -Begriff (E₁ E₂) anstelle von x, nachgeben (E₁ E₂) [x: = a]. Aber ersetzen a hinein (E₁ E₂) anstelle von x ist genauso wie das Ersetzen in beide E₁ und E₂, so

(E₁ E₂) [x: = a] = ((E₁ [x: = a] E₂ [x: = a]))

(λx. (E₁ E₂) a) = ((((λx.E₁ a) (λx.E₂ a))

= (S λx.E₁ λx.E₂ a)

= ((((S λx.E₁ λx.E₂) a)

Nach Extensionalgleichheit,

λx. (E₁ E₂) = (S λx.E₁ λx.E₂)

Daher einen Kombinator zu finden, der gleich äquivalent zu finden ist λx. (E₁ E₂) Es reicht aus, einen Kombinator zu finden, der äquivalent zu ((S λx.E₁ λx.E₂) und

(S T[λx.E₁] T[λx.E₂])

Offensichtlich passt die Rechnung. E₁ und E₂ jeweils streng weniger Anwendungen als ((E₁ E₂), so dass die Reursion in einem Lambda -Term ohne Anwendungen enden muss - entweder eine Variable oder einen Begriff des Formulars λx.E.

Vereinfachungen der Transformation

η-Reduktion

Die von der erzeugten Kombinatoren T[] Transformation kann kleiner gemacht werden, wenn wir die berücksichtigen η-Reduktion Regel:

T[λx. (E x)] = T[E] (wenn x ist nicht frei in E)

λx. (E x) ist die Funktion, die ein Argument nimmt, xund wendet die Funktion an E dazu; Dies entspricht erweitert der Funktion E selbst. Es reicht daher aus, um sich umzuwandeln E kombinatorische Form.

Unter Berücksichtigung dieser Vereinfachung wird das obige Beispiel:

  T[λx.λy. (y x)]

= ...

= (S (K (S i)) T[λx. (K x)]))

= (S (K (S i)) K) (durch η-Reduktion)

Dieser Kombinator entspricht dem früheren, längeren:

(S (K (S i)) K x y)

= (K (S i) x (K x) y)

= (S i (K x) y)

= (I y (K x y))

= (y (K x y))

= (y x)

In ähnlicher Weise die Originalversion der T[] Transformation transformierte die Identitätsfunktion λf.λx. (f x) hinein (S (S (K s) (S (K k k) I)) (K i)). Mit der η-Reduktionsregel, λf.λx. (f x) wird in transformiert in I.

Ein-Punkte-Basis

Es gibt ein Punkte-Basen, von denen jeder Kombinator ausgeht werden kann irgendein Lambda -Begriff. Das einfachste Beispiel für eine solche Grundlage ist {X} wo:

X ≡ λx.((xS)K)

Es ist nicht schwer zu überprüfen, dass:

X (X (X X)) =^β K und

X (X (X (X X))) =^β S.

Seit {K, S} ist eine Basis, darunter {{X} ist auch eine Grundlage. Das Jota Programmiersprache verwendet X als alleiniger Kombinator.

Ein weiteres einfaches Beispiel für eine Punktbasis ist:

X' ≡ λx.(x K S K) mit

(X' X') X' =^β K und

X' (X' X') =^β S

Tatsächlich gibt es unendlich viele solcher Basen.^[7]

Kombinators B, C.

Zusätzlich zu S und K, SchönfinkelDas Papier enthielt zwei Kombinatoren, die jetzt genannt werden B und C, mit den folgenden Reduktionen:

(C f g x) = ((((f x) g)

(B f g x) = ((f (g x))

Er erklärt auch, wie sie wiederum mit nur mit Verwendung ausgedrückt werden können S und K:

B = (S (K s) K)

C = (S (S (K (S (K s) K)) S) (K k k))

Diese Kombinatoren sind äußerst nützlich, wenn sie Prädikatlogik oder Lambda -Kalkül in Kombinatorausdrücke übersetzen. Sie wurden auch von benutzt von Curryund viel später von David Turner, dessen Name mit ihrer rechnerischen Verwendung in Verbindung gebracht wurde. Mit ihnen können wir die Regeln für die Transformation wie folgt erweitern:

1. T[x] ⇒ x
2. T[(E₁ E₂)] ⇒ (T[E₁] T[E₂]))
3. T[λx.E] ⇒ (K T[E]) (wenn x ist nicht frei in E)
4. T[λx.x] ⇒ I
5. T[λx.λy.E] ⇒ T[λx.T[λy.E]] (wenn x ist frei in E)
6. T[λx. (E₁ E₂)] ⇒ (S T[λx.E₁] T[λx.E₂]) (wenn x ist in beiden frei E₁ und E₂)
7. T[λx. (E₁ E₂)] ⇒ (C T[λx.E₁] T[E₂]) (wenn x ist frei in E₁ aber nicht E₂)
8. T[λx. (E₁ E₂)] ⇒ (B T[E₁] T[λx.E₂]) (wenn x ist frei in E₂ aber nicht E₁)

Verwendung B und C Kombinators, die Transformation vonλx.λy. (y x) sieht aus wie das:

   T[λx.λy. (y x)]

= T[λx.T[λy. (y x)]]]

= T[λx. (C T[λy.y] x)] (nach Regel 7)

= T[λx. (C I x)]

= (C I) (η-Reduktion)

= ${\ displaystyle \ mathbf {c} _ {*}}$ (Traditionelle kanonische Notation: ${\ displaystyle \ mathbf {x} _ {*} = \ mathbf {xi}}$)

= ${\ displaystyle \ mathbf {i} '}$ (Traditionelle kanonische Notation: ${\ displaystyle \ mathbf {x} '= \ mathbf {cx}}$)

Und in der Tat, (C I x y) reduziert sich auf (y x):

(C I x y)

= (I y x)

= (y x)

Die Motivation hier ist das B und C sind begrenzte Versionen von S. Wohingegen S Nimmt einen Wert ein und ersetzt ihn sowohl in den Applicand als auch in sein Argument, bevor er die Anwendung ausführt. C führt den Substitution nur im Applicand aus, und B Nur im Argument.

Die modernen Namen für die Kombinatoren kommen von Haskell Curry's Doktorarbeit von 1930 (siehe B, C, K, W System). Im SchönfinkelDas Originalpapier, was wir jetzt nennen S, K, I, B und C wurden genannt S, C, I, Z, und T beziehungsweise.

Die Verringerung der Kombinatorgröße, die sich aus den neuen Transformationsregeln ergibt, kann auch ohne Einführung erreicht werden B und C, wie in Abschnitt 3.2 von.^[8]

Cl_K gegen Cl_I Infinitesimalrechnung

Es muss eine Unterscheidung zwischen den gemacht werden Cl_K Wie in diesem Artikel und der beschrieben Cl_I Infinitesimalrechnung. Die Unterscheidung entspricht der zwischen λ_K und das λ_I Infinitesimalrechnung. Im Gegensatz zum λ_K Kalkül, das λ_I Kalkül beschränkt die Abstraktionen auf:

λx.E wo x hat mindestens ein freies Ereignis in E.

Infolgedessen Kombinator K ist im λ nicht vorhanden_I Kalkül oder in der Cl_I Infinitesimalrechnung. Die Konstanten von Cl_I sind: I, B, C und S, die eine Grundlage bilden, von der alle Cl_I Begriffe können komponiert werden (Modulo -Gleichheit). Jedes λ_I Der Term kann in eine gleiche Umgebung umgewandelt werden Cl_I Kombinator nach Regeln ähnlich denen, die oben für die Umwandlung von λ vorgestellt wurden_K Begriffe in Cl_K Kombinatoren. Siehe Kapitel 9 in Barendregt (1984).

Rückwärtsumwandlung

Die Umwandlung L[] Von kombinatorischen Begriffen bis hin zu Lambda ist trivial:

L[I] = λx.x

L[K] = λx.λy.x

L[C] = λx.λy.λz. (x z y)

L[B] = λx.λy.λz. (x (y z))

L[S] = λx.λy.λz. (x z (y z))

L[(E₁ E₂)] = (L[E₁] L[E₂]))

Beachten Sie jedoch, dass diese Transformation nicht die inverse Transformation einer der Versionen von ist T[] Das haben wir gesehen.

Unentschlossenheit des kombinatorischen Kalküls

A Normale Form ist ein kombinatorischer Begriff, bei dem die primitiven Kombinatoren, die auftreten, nicht auf genügend Argumente angewendet werden, um vereinfacht zu werden. Es ist unentscheidbar, ob ein allgemeiner kombinatorischer Term eine normale Form hat. Ob zwei kombinatorische Begriffe äquivalent sind usw. Dies entspricht der Unentschlossenheit der entsprechenden Probleme für Lambda -Begriffe. Ein direkter Beweis ist jedoch wie folgt:

Erstens der Begriff

Ω = (S I I (S I I))

hat keine normale Form, weil sie sich nach drei Schritten auf sich selbst reduziert, wie folgt:

   (S I I (S I I))

= (I (S I I) (I (S I I)))

= (S I I (I (S I I)))

= (S I I (S I I))

Und eindeutig kann keine andere Reduktionsreihenfolge den Ausdruck kürzer machen.

Nehmen wir nun an N waren ein Kombinator zur Erkennung normaler Formen, so dass

$oder {\ text {sonst.}} \ end {cases}}}$

(Wo T und F die konventionelle darstellen Kirchenkodierungen von wahr und falsch, λx.λy.x und λx.λy.y, in kombinatorische Logik umgewandelt. Die Kombinationsversionen haben T = K und F = (K I).))

Nun lass

Z = (C (C (B N (S I I)) Ω) I)

Betrachten Sie nun den Begriff (S I I Z). Tut (S I I Z) eine normale Form haben? Dies tut es nur dann, wenn das folgende auch folgt:

   (S I I Z)

= (I Z (I Z))

= (Z (I Z))

= (Z Z)

= (C (C (B N (S I I)) Ω) I Z) (Definition von Z)

= (C (B N (S I I)) Ω Z I)

= (B N (S I I) Z Ω I)

= (N (S I I Z) Ω I)

Jetzt müssen wir uns bewerben N zu (S I I Z). Entweder (S I I Z) hat eine normale Form oder nicht. Wenn es tut Haben Sie eine normale Form, dann verringert sich der Vorstehende wie folgt:

   (N (S I I Z) Ω I)

= (K Ω I) (Definition von N)

= Ω

aber Ω tut nicht Haben Sie eine normale Form, also haben wir einen Widerspruch. Doch wenn (S I I Z) tut nicht Haben Sie eine normale Form, der Vorstehende nimmt wie folgt ab:

   (N (S I I Z) Ω I)

= (K I Ω I) (Definition von N)

= (I I)

= I

was bedeutet, dass die normale Form von ((S I I Z) ist einfach I, ein weiterer Widerspruch. Daher der hypothetische Normalform-Kombinator N kann nicht existieren.

Das kombinatorische Logikanalogon von Reis Satz sagt, dass es kein vollständiges nicht triviales Prädikat gibt. EIN Prädikat ist ein Kombinator, der bei Anwendung entweder zurückgibt T oder F. Ein Prädikat N ist nicht trivial Wenn es zwei Argumente gibt A und B so dass N A = T und N B = F. Ein Kombinator N ist Komplett wenn NM hat eine normale Form für jedes Argument M. Das Analogon von Rice's Theorem besagt, dass jedes vollständige Prädikat trivial ist. Der Beweis dieses Satzes ist ziemlich einfach.

Aus diesem Unentschiedenheitstheorem folgt unmittelbar, dass es kein vollständiges Prädikat gibt, das zwischen Begriffen mit normaler Form und Begriffen unterscheiden kann, die keine normale Form haben. Daraus folgt, dass es gibt nein Vollständiges Prädikat, sagen Sie gleich, so dass:

(GLEICH A b) = T wenn A = B und

(GLEICH A b) = F wenn A ≠ B.

Wenn gleich existieren, dann für alle A, λx.(GLEICH x a) müsste ein vollständiges nicht triviales Prädikat sein.

Anwendungen

Kompilierung der funktionalen Sprachen

David Turner benutzte seine Kombinators, um die implementieren SASL -Programmiersprache.

Kenneth E. Iverson gebrauchte Primitive basierend auf Currys Kombinators in seinen J Programmiersprache, ein Nachfolger zu Apl. Dies ermöglichte das, was Iverson nannte stillschweigende ProgrammierungDas heißt, die Programmierung in funktionellen Ausdrücken, die keine Variablen enthalten, sowie leistungsstarke Tools für die Arbeit mit solchen Programmen. Es stellt sich heraus, dass in jeder APL-ähnlichen Sprache mit benutzerdefinierten Operatoren eine stillschweigende Programmierung möglich ist.^[9]

Logik

Das Curry -Howard Isomorphismus impliziert eine Verbindung zwischen Logik und Programmierung: jeder Beweis eines Satzes von intuitionistische Logik entspricht einer Reduzierung eines typisierten Lambda -Terms und umgekehrt. Darüber hinaus können Theoreme mit Funktionstypsignaturen identifiziert werden. Insbesondere entspricht eine typisierte Kombinationslogik a Hilbert -System in Beweistheorie.

Das K und S Kombinatoren entsprechen den Axiomen

AK: A → (B → A),

WIE: (A → (B → C)) → (((A → B) → (A → C)),

und Funktionsanwendung entspricht der Ablösungsregel (Modus Ponens)

MP: aus A und A → B schließen B.

Der Kalkül, der aus besteht aus AK, WIE, und MP ist vollständig für das implizite Fragment der intuitionistischen Logik, die wie folgt gesehen werden kann. Betrachten Sie den Satz W von allen deduktiv geschlossenen Formeln, die von bestellt wurden Aufnahme. Dann ${\ displayStyle \ Langle W, \ subseteq \ rangle}$ ist eine intuitionistische Kripke -Rahmenund wir definieren ein Modell ${\ displayStyle \ vdash}$ in diesem Rahmen von

${\ displayStyle x \ vdash a \ iff a \ in X.}$

Diese Definition folgt den Bedingungen zur Zufriedenheit von →: einerseits, wenn ${\ displayStyle x \ vdash a \ bis b}$, und ${\ displayStyle y \ in W}$ ist so, dass ${\ displayStyle y \ supseteq x}$ und ${\ displayStyle y \ vdash a}$, dann ${\ displayStyle y \ vdash b}$ von modus ponens. Andererseits, wenn ${\ displaystyle x \ nicht \ vdash a \ bis b}$, dann ${\ displayStyle x, a \ nicht \ vdash B}$ bis zum Abzugstheoremsomit die deduktive Schließung von ${\ displaystyle x \ cup \ {a \}}$ ist ein Element ${\ displayStyle y \ in W}$ so dass ${\ displayStyle y \ supseteq x}$, ${\ displayStyle y \ vdash a}$, und ${\ displayStyle y \ nicht \ vdash B}$.

Lassen A Seien Sie jede Formel, die im Kalkül nicht nachweisbar ist. Dann A gehört nicht zur deduktiven Schließung X des leeren Satzes also ${\ displayStyle x \ nicht \ vdash a}}$, und A ist nicht intuitionistisch gültig.

Siehe auch

• Applicative computing systems
• B, C, K, W System
• Kategorische abstrakte Maschine
• Kombinatorische kategoriale Grammatik
• Explizite Substitution
• Fixpunktkombinator
• Graph Reduktionsmaschine
• Lambda -Kalkül und Zylinderalgebra, andere Ansätze zur Modellierung der Quantifizierung und Eliminierung von Variablen
• Ski -Kombinatorrechnung
• Supercombinator
• Einen Spottdrossel verspotten

Verweise

Weitere Lektüre

• Barendregt, Hendrik Pieter (1984). Der Lambda Calculus, seine Syntax und Semantik. Studien zur Logik und die Grundlagen der Mathematik. Vol. 103. North Holland. ISBN 0-444-87508-5.
• Curry, Haskell B.; Feys, Robert (1958). Kombinationslogik. Vol. I. Amsterdam: North Holland. ISBN 0-7204-2208-6.
• Curry, Haskell B.; Hindley, J. Roger; Seldin, Jonathan P. (1972). Kombinationslogik. Vol. II. Amsterdam: North Holland. ISBN 0-7204-2208-6.
• Field, Anthony J.; Harrison, Peter G. (1998). Funktionelle Programmierung. Addison-Wesley. ISBN 0-201-19249-7.
• Hindley, J. Roger; Meredith, David (1990), "Haupttypschemen und Kondensatablösung", Zeitschrift für symbolische Logik, 55 (1): 90–105, doi:10.2307/2274956, JStor 2274956, HERR 1043546, S2CID 6930576
• Hindley, J. R.; Seldin, J. P. (2008). λ-Kalkulus und Kombinators: Eine Einführung. Cambridge University Press.
• Paulson, Lawrence C. (1995). Grundlagen der funktionalen Programmierung. Universität von Cambridge.
• Quine, W. V. (1960). "Variablen weg erklären". Verfahren der American Philosophical Society. 104 (3): 343–347. JStor 985250. Nachdruck als Kapitel 23 von Quine's Ausgewählte Logikpapiere (1966), S. 227–235
• Schönfinkel, Moses, 1924, "Über Die Baateine ​​der Mathematischen Logik, "übersetzt als" auf den Bausteinen der mathematischen Logik "in Von Frege nach Gödel: Ein Quellbuch in der mathematischen Logik, 1879–1931, Jean van Heijenoort, ed. Harvard University Press, 1967. ISBN0-674-32449-8. Der Artikel, der die Kombinationslogik gründete.
• Smullyan, Raymond, 1985. Einen Spottdrossel verspotten. Knopf. ISBN0-394-53491-3. Eine sanfte Einführung in die kombinatorische Logik, die als eine Reihe von Freizeitpuzzles unter Verwendung von Vogelbeobachtungsmetaphern dargestellt wird.
• ______, 1994. Diagonalisierung und Selbstreferenz. Oxford University Press. Die Kapitel 17–20 sind eine formellere Einführung in die Kombinationslogik mit besonderem Schwerpunkt auf Fixpunktergebnissen.
• Sørensen, Morten Heine B. und Paweł Urzyczyn, 1999. Vorträge über den Curry -Howard -Isomorphismus. Universität Kopenhagen und Universität Warschau, 1999.
• Wolfengagen, V. E. (2003). Kombinatorische Logik in der Programmierung: Berechnungen mit Objekten durch Beispiele und Übungen (2. Aufl.). Moskau: "Center Jurinfor" Ltd. ISBN 5-89158-101-9.
• Wolfram, Stephen (2021). Kombinatoren: Eine hundertjährige Ansicht. Wolfram Media. ISBN 978-1-57955-043-1. e ISBN978-1-57955-044-8. Eine Feier der Entwicklung von Kombinators, hundert Jahre nach ihrer Einführung von durch Moses Schönfinkel 1920.

Externe Links

• Stanford Encyclopedia of Philosophy: "Kombinationslogik" durch Katalin Bimbó.
• 1920–1931 Currys Blocknotizen.
• Keenan, David C. (2001) "Zum Zerlegen eines Mockingbird: Eine grafische Notation für den Lambda -Kalkül mit animierter Reduzierung."
• Rathman, Chris, "Kombinatorvögel."Ein Tisch destilliert einen Großteil der Essenz von Smullyan (1985).
• Ziehen Sie 'n' Drop -Kombinatoren. (Java Applet)
• Binärer Lambda -Kalkül und Kombinationslogik.
• Kombinatorischer Logik -Reduktions -Webserver