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

Question

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

Answer 1

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

Да, но только примерно. В «чистом» нетипедном исчислении Lambda все кодируется как функции. (Вы можете Google для популярного «церковного кодирования» и менее популярного «кодирования Скотта».) У LISP есть нефункциональные данные, такие как атомы и числа и тому подобное, так что это будет считаться «нетипированным расчетом лямбды, продленным с константами».

Еще одно важное отличие - в Порядок оценки. Анкет Правила снижения терминов лямбда-калькулуса очень неэтерминирование. (Существует теорема, теорема церкви-россера, в которой говорится, что до того, как все заканчивается, порядок оценки не имеет значения.) Любые Стратегия сокращения завершается, что это делает. Это сильно отличается от LISP, который всегда оценивает аргументы в отношении нормальной формы, прежде чем делать бета-восстановление. Этот порядок оценки называется «Call по значению».

В итоге LISP соответствует нетипированное, вызовов по цене лямбда.

Answer 2

Джон Маккарти представил LISP в Его статья в апреле 1960 года «Рекурсивные функции символических выражений и их вычисления по машине, часть I». Анкет Следующий абзац с стр. 6:

е - Функции и формы. Обычно в математике - вне математической логики - неточно использовать слово «функция» и применять его к таким формам, как Y² + x. Поскольку мы позже рассчитым с выражениями для функций, нам нужно различие между функциями и формами и обозначения для выражения этого различия. Это различие и обозначение для описания его, от которого мы тривиально отклоняются, дается церковью [3].
...
3. A. Church, Calculi of Lambda-Conversion (издательство Принстонского университета, Принстон, Нью-Джерси, 1941).

А Википедия статья о лямбда-калькулусе имеет историю церковных публикаций. В статье 1941 года, на который ссылается Маккарти, кажется, о напечатано Lambda-Calculus, противоречащий введению статьи Википедии.

А lambda Ключевое слово в LISP можно понимать, чтобы ссылаться на Lambda-Calculus только посредством аналогии. Выражение Lisp Lambda - это тип анонимная функция.

Answer 3

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

Если вы хотите идентифицировать Lambda Calculi по системе типа, то LISP, конечно, является своей собственной. Ключевое слово «лямбда» в любой схеме LISP, безусловно, претенциозно, и после схемы тоже есть место, чтобы сказать, что это так. Просто использование «func» было бы более скромным. LISP - это процессор списка в основном, а не «исчисление лямбды»

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

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

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