Что делает исчисление Lambda актуальным для изучения?

Question

Следующей осенью я начинаю курс компьютерных наук, но я не могу понять λ-Calculus в контексте функционального программирования. Я могу неверно истолковать это полностью, но на основе этого определение Из Стэнфордской энциклопедии философии это просто еще одна нотация для функций.

Если это является Только это, почему выгодно использовать λ-calculus по сравнению с регулярными функциями, чтобы рассчитать время выполнения алгоритма?

Answer 1

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

Теоретически это может быть любой язык с хорошим Формальная семантика. Анкет Но чтобы сделать вещи менее сложными и менее склонными к ошибкам, лучше использовать язык, который как можно проще, но все же способен выразить любую программу (т.е. Тьюринг завершен) Для рассуждения об императивном кодексе, есть Тьюринговые машины. Анкет Но для рассуждений о функциональном программировании есть $ lambda $ -calculus.

Основной $ lambda $ -calculus похож на функциональный язык программирования, но с большим количеством «багажа». Не важно, чтобы это был хороший язык для на самом деле писать программы, и что это будет эффективным языком. Просто это просто и выразительно. Например, нам не нужны петли, потому что мы можем имитировать их с рекурсией. И нам не нужны функции с несколькими параметрами, так как мы можем имитировать их с помощью Карри.

Теперь, в какой-то момент вы можете доказать свойства конструкций, которые не являются частью основных (невысоких) $ lambda $ -calculus. Вот почему компьютерные ученые расширили его в разных направлениях за эти годы. Например, к рассуждению о типовых системах существует множество вариаций напечатано $ лямбда $ -calculi.

Answer 2

Как ни странно, много книг говорят о $ lambda $ calculus без упоминания LISP или же Схема, современные языки программирования, основанные на нем, оставляя студентов, к сожалению, с идеей, что его старые и абстрактные и в основном теоретические. Изучение LISP или схемы может быть большим углом, чтобы помочь понять исчисление $ lambda $.

Если это является Только это, почему выгодно использовать λ-calculus по сравнению с регулярными функциями, чтобы рассчитать время выполнения алгоритма?

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

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

Другим ключевым аспектом является анализ программного обеспечения больше из логичный или же математический Объектив/вид, а не «компьютерная научная» перспектива.

Как указывает другой ответ, LISP - это рекурсия, а не итерация, а рекурсия очень лежит в основе CS.

Больше выступая за «$ lambda $ -View» и детали можно найти в [1], бесплатно онлайн и полуфинальный реф.

[1] Структура и интерпретация компьютерных программ, Abelson & Sussman