W jaki sposób Lambda Calculus jest specyficznym rodzajem systemu pisania terminów?

13

Teraz widzimy, że Kościół był związany z tym po prostu wpisane rachunek lambda . Rzeczywiście wydaje się, że wyjaśnił on prosty typ rachunku Lambda, aby zmniejszyć nieporozumienia dotyczące rachunku Lambda.

Teraz, gdy John McCarthy stworzył Lisp - oparł go na rachunku Lambda Calculus . Jest tak, jak sam przyznał, kiedy opublikował „Rekurencyjne funkcje wyrażeń symbolicznych i ich obliczanie przez maszynę, część I” . Możesz to przeczytać tutaj .

Teraz wiemy, że rdzeniem Mathematiki jest system podobny do Lispa , ale zamiast opierać się wyłącznie na rachunku Lambda, opiera się na systemie przepisywania terminów .

Tutaj autor stwierdza:

Mathematica to zasadniczo system przepisywania terminów ... bardziej ogólna koncepcja niż Rachunek Lambda za Lisp.

Wygląda na to, że Rachunek Lambda jest niewielką częścią znacznie bardziej ogólnej kategorii. (Dość otwierające oczy jako myśl była to bardziej podstawowa koncepcja). Próbuję przeczytać o tym więcej, aby uzyskać na to trochę perspektyw.

Moje pytanie brzmi: w jaki sposób Lambda Calculus jest specyficznym rodzajem systemu pisania terminów?

lambda-calculus term-rewriting-systems lisp

— Sokole Oko
źródło

15

Odpowiedź brzmi: to zależy od tego, co rozumiesz pod pojęciem Term Rewrite System .

Kiedy została wprowadzona, koncepcja Term Rewrite Systems , czyli TRSes, opisywała to, co nazywa się teraz TRSes pierwszego rzędu , który jest po prostu zbiorem reguł obliczeniowych formy

l \to r

$l\rightarrow r$

$l$ $r$

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

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

$x$ $f$ $\Sigma$ $f\in\Sigma$

$\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))$

Jest jeszcze jedno, bardziej intuicyjne kodowanie, które obejmuje warunki lambda z indeksami de Bruijna i wyraźnymi podstawieniami, ale nie będę się tutaj zajmował.

$\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$

Dlatego lewe boki są ograniczone do jakiegoś ładnego podzbioru, często „wzorów Millera”. Uogólnia się szereg wyników dla sprawy pierwszego rzędu, choć jest kilka paskudnych niespodzianek.

$\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)$

Całkiem przyzwoity przegląd definicji i podstawowych wyników podają tutaj Nipkow i Prehofer .

— cody
źródło

3

Ta prezentacja Beckmana i Meijera omawia rachunek lambda, przepisywanie terminów i wspomina Mathematica. Myślę, że odpowiada na to pytanie w intuicyjny sposób: https://channel9.msdn.com/Series/Beckman-Meijer-Overdrive/Beckman-Meijer-Overdrive-The-Lambda-Calculus-and-Food-Nutrition

— ajw
źródło