Как Лямбда-исчисление является специфическим типом системы письменности?

13

Теперь мы видим , что церковь была связана с в Просто типизированных лямбда - исчислению . Действительно, кажется, что он объяснил Лямбда-исчисление Простого Типа, чтобы уменьшить недопонимание о Лямбда-исчислении.

Теперь, когда Джон Маккарти создал Лисп - он основал его на лямбда-исчислении . По его собственному признанию, он опубликовал «Рекурсивные функции символьных выражений и их вычисление на машине, часть I» . Вы можете прочитать это здесь .

Теперь мы знаем, что в основе Mathematica лежит Lisp-подобная система , но вместо того, чтобы основываться исключительно на лямбда-исчислении, она основана на системе переписывания терминов .

Здесь автор заявляет:

Mathematica - это система переписывания терминов, более общая концепция, чем лямбда-исчисление, стоящее за Лиспом.

Похоже, что лямбда-исчисление является небольшой частью гораздо более общей категории. (Довольно откровенно, как мысль, это было больше основополагающей концепции). Я пытаюсь прочитать больше об этом, чтобы получить некоторое представление об этом.

Мой вопрос: как Lambda Calculus является специфическим типом системы письменности?

Hawkeye
источник

Ответы:

15

Ответ зависит от того, что вы подразумеваете под термином переписать систему .

Когда это было введено, концепция Term Rewrite Systems , или TRSes, описывала то, что сейчас называется TRSes первого порядка , что является просто набором правил вычисления вида

lr

lr

t:= x  f(t1,,tn)

xfΣfΣ

Var(r)Var(l)

β

(λx.t) ut[u/x]
λxtλ

SKΣ={S, K,app}

app(app(K,x),y)x
app(app(app(S,x),y),z)app(app(x,z),app(y,z))

Есть еще одно, более интуитивное кодирование, которое включает лямбда-термины с индексами де Брюина и явными подстановками, но я не буду здесь вдаваться в подробности.


λ

t := x(t1,,tn)  f(x11xi11.t1,,x1nxinn.tn)

fΣxjitiabs(x.t)λx.t

βηβ

Поэтому левые стороны ограничены некоторым хорошим подмножеством, часто «паттернами Миллера». Обобщается ряд результатов для случая первого порядка, хотя есть несколько неприятных сюрпризов.

λ βη

λβ

app(abs(x.y(x)),z)y(z)

Довольно приличный обзор определений и основных результатов дан Nipkow и Prehofer здесь .

Коди
источник