Wie ist Lambda Calculus eine bestimmte Art von Term Writing System?

12

Jetzt können wir sehen, dass Church mit dem einfach getippten Lambda-Kalkül in Verbindung gebracht wurde . Tatsächlich scheint er den einfach getippten Lambda-Kalkül erklärt zu haben, um Missverständnisse über den Lambda-Kalkül zu vermeiden.

Jetzt, als John McCarthy Lisp kreierte, basierte er es auf dem Lambda-Kalkül . Dies hat er selbst zugegeben, als er "Rekursive Funktionen symbolischer Ausdrücke und ihre maschinelle Berechnung, Teil I" veröffentlichte . Sie können es hier lesen .

Jetzt wissen wir, dass Mathematica im Kern ein Lisp-ähnliches System ist , das jedoch nicht nur auf dem Lambda-Kalkül basiert, sondern auf einem System zur Umschreibung von Begriffen .

Hier stellt der Autor fest:

Mathematica ist im Grunde ein System zur Umschreibung von Begriffen ... ein allgemeineres Konzept als der Lambda-Kalkül hinter Lisp.

Es scheint, dass der Lambda-Kalkül ein kleiner Teil einer viel allgemeineren Kategorie ist. (Ganz aufgeschlossen als Gedanke, dies war eher ein grundlegendes Konzept). Ich versuche mehr darüber zu lesen, um eine Perspektive zu bekommen.

Meine Frage ist: Wie ist Lambda Calculus eine bestimmte Art von Term Writing-System?

lambda-calculus term-rewriting-systems lisp Falkenauge
quelle

14

Die Antwort ist, es kommt darauf an, was Sie mit Term Rewrite System meinen .

Als es eingeführt wurde, beschrieb das Konzept von Term Rewrite Systems , oder TRSes, was jetzt TRSes erster Ordnung genannt wird , was einfach ein Satz von Berechnungsregeln des Formulars ist

l \to r

$l\rightarrow r$

wobei und sind Terme erster Ordnung der Form $l$ $r$

t := x ∣ f (t_{1}, \dots, t_{n})

$t :=\ x\ \mid\ f(t_1,\ldots,t_n)$

wobei eine Variable ist und ein Funktionssymbol von einem willkürlichen genommen, aber fester Menge , die angerufene Signatur , die auch eine Anzahl von Argumenten für jede fixiert . $x$ $f$ $\Sigma$ $f\in\Sigma$

Es gibt ein paar gemeinsame Beschränkungen Regeln auferlegt, zB , aber wir brauchen hier nicht in sie zu gehen. $\mathrm{Var}(r)\subseteq\mathrm{Var}(l)$

$\beta$

(λ x . t) u \to t [u / x]

$(\lambda x. t)\ u \rightarrow t[u/x]$

λ

$\lambda$

x

$x$

t

$t$

λ

$\lambda$

$SK$ $\Sigma=\{S,\ K, \mathrm{app}\}$

a p p (a p p (K, x), y) \to x

$\mathrm{app}(\mathrm{app}(K,x),y)\rightarrow x$

a p p (a p p (a p p (S, x), y), z) \to a p p (a p p (x, z), a p p (y, z))

$\mathrm{app}(\mathrm{app}(\mathrm{app}(S, x), y), z)\rightarrow \mathrm{app}(\mathrm{app}(x, z),\mathrm{app}(y, z))$

Es gibt eine andere, intuitivere Codierung, die Lambda-Terme mit de Bruijn-Indizes und expliziten Substitutionen umfasst, auf die ich hier jedoch nicht näher eingehen werde.

$\lambda$

t := x (t_{1}, \dots, t_{n}) ∣ f (x_{1}^{1} \dots x_{i_{1}}^{1} . t_{1}, \dots, x_{1}^{n} \dots x_{i_{n}}^{n} . t_{n})

$t\ :=\ x(t_1,\ldots, t_n)\ \mid\ f(x^1_1\ldots x^1_{i_1}.t_1,\ldots,x^n_1\ldots x^n_{i_n}.t_n)$

$f\in\Sigma$ $x^i_j$ $t_i$ $\mathrm{abs}(x.t)$ $\lambda x.t$

$\beta\eta$ $\beta$

Daher sind die linken Seiten auf eine nette Untergruppe beschränkt, oft die "Miller-Muster". Eine Reihe von Ergebnissen für den Fall erster Ordnung verallgemeinern, obwohl es einige böse Überraschungen gibt.

$\lambda$ $\beta$ $\eta$

$\lambda$ $\beta$

a p p (a b s (x . y (x)), z) \to y (z)

$\mathrm{app}(\mathrm{abs}(x.y(x)),z)\rightarrow y(z)$

Einen recht ordentlichen Überblick über die Definitionen und Grundergebnisse geben hier Nipkow und Prehofer .

Cody
quelle

3

Diese Präsentation von Beckman und Meijer behandelt die Lambda-Rechnung, das Umschreiben von Begriffen und erwähnt Mathematica. Ich denke, es beantwortet die Frage auf intuitive Weise: https://channel9.msdn.com/Series/Beckman-Meijer-Overdrive/Beckman-Meijer-Overdrive-The-Lambda-Calculus-and-Food-Nutrition

ajw
quelle

Wie ist Lambda Calculus eine bestimmte Art von Term Writing System?

Antworten: