Какой тип лямбда-исчисления был бы Lisp свободно примером?

Question

Я пытаюсь лучше понять, как типы вступают в игру в исчислении лямбда. По общему признанию, многие вещи типа теории над моей головой. Lisp - это динамически типизированный язык, который примерно соответствует нетипизированному лямбда-исчислению? Или есть какой-то «динамически типизированный лямбда-исчисление», о котором я не знаю?

Answer 1

Lisp - это динамически типизированный язык, который примерно соответствует нетипизированному расчету лямбда?

Да, но только грубо. В «чистом» нетипизированном лямбда-исчислении все кодируется как функции. (Вы можете google для популярной «Церковной кодировки» и менее популярной «кодировки Скотта».) Lisp имеет нефункциональные данные, такие как атомы и числа и т. Д., Поэтому это будет считаться «нетипизированным лямбда-исчислением, расширенным константами».

Другое важное различие заключается в порядок оценки. Правила сокращения терминов лямбда-исчисления весьма недетерминированы. (Существует теорема, теорема Церковно-Россера, которая гласит, что до тех пор, пока все заканчивается, порядок оценки не имеет значения.) На практике лямбда-термины обычно уменьшаются с использованием крайней отдаленной или обычной «нормальной» редукции, потому что если любой стратегия сокращения завершается, это делает. Это очень отличается от Lisp, который всегда оценивает аргументы в нормальной форме перед выполнением бета-редукции. Этот порядок оценки называется «вызов по значению».

Таким образом, Lisp соответствует нетипизированное исчисление лямбда по заданному значению с константами.

Answer 2

John McCarthy представил LISP в his April, 1960 paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Следующий пункт со страницы 6:

e. Функции и формы. Обычно в математике - вне математической логики - использовать слово «функция» неточно и применять ее к формам , таким как y + x. Поскольку мы в дальнейшем вычисляем выражения для функций, , нам нужно различие между функциями и формами и обозначение для выражения этого различия. Это различие и обозначение его описания от , которое мы отклоняем тривиально, дано Церковью [3].
...
3. ЦЕРКОВЬ ЦЕРКВИ, ИЗЛУЧЕНИЕ ЛИМБИОННОГО ПРЕОБРАЗОВАНИЯ (Принстонский университет Press, Princeton, N. J., 1941).

Wikipedia article on lambda-calculus имеет историю церковных публикаций. Документ 1941 года, на который ссылается Маккарти, по-видимому, относится к напечатанному лямбда-исчислению, что противоречит введению в статью Википедии.

Ключевое слово lambda в Lisp можно понимать как относящееся к лямбда-исчислению только по аналогии. Выражение лямбда Lisp представляет собой тип anonymous function.

Answer 3

Lisp не является «лямбда-исчислением», я не знаю, что такое «лямбда-исчисление».

Если вы хотите идентифицировать лямбда-исчисления там типа системы, то Lisp является его собственным, конечно. Ключевое слово lambda в любом lisp до Scheme, безусловно, претенциозно, и после Scheme есть место, чтобы сказать, что это так.Просто использование «func» было бы более скромным. Lisp - это процессор списков в основном, а не «лямбда-исчисление»

Я также написал довольно обширную статью об этом, когда попытался продемонстрировать, почему A: термин «функциональное программирование» не имеет смысла и B: почему говорение о " лямбда-исчисление, а не „системы типа“ так же:

http://blog.nihilarchitect.net/archives/289/on-functional-programming/

Кроме того, имейте в виде, что в Лиспе, все функции в действии один аргументе и могут быть только у списков как их аргументы.