Следующей осенью я начинаю курс по информатике для студентов, но я не могу понять λ-исчисление в контексте функционального программирования. Возможно, я полностью неверно истолковываю это, но, исходя из этого определения из Стэнфордской энциклопедии философии, это просто еще одно обозначение функций.
Если это как раз то, почему это выгодно использовать λ-исчисление над регулярной функцией нотацией для вычисления алгоритма времени выполнения?
Ответы:
В области компьютерных наук мы хотим анализировать и понимать исходный код с математической строгостью. Это единственный способ доказать интересные свойства (такие как завершение) с абсолютной уверенностью. Для этого нам нужен язык с очень четко определенным значением для каждой конструкции.
Теоретически это может быть любой язык с хорошей формальной семантикой . Но чтобы сделать вещи менее сложными и менее подверженными ошибкам, лучше использовать язык, который настолько прост, насколько это возможно, но все же способен выразить любую программу (т. Е. Завершен ли Тьюринг ). Для рассуждений об императивном коде существуют машины Тьюринга . Но для рассуждений о функциональном программировании существует калькуляция.λ
Базовый калькулятор похож на функциональный язык программирования, но с большим количеством «багажа». Не важно, чтобы это был хороший язык для написания программ, или чтобы он был эффективным. Просто это просто и выразительно. Например, нам не нужны циклы, потому что мы можем имитировать их с помощью рекурсии. И нам не нужны функции с несколькими параметрами, поскольку мы можем имитировать их с помощью Curry .λ
Теперь в какой-то момент вы можете захотеть доказать свойства конструкций, которые не являются частью базового (нетипизированного) вычисления. Вот почему компьютерные ученые расширили его в разных направлениях на протяжении многих лет. Например, для рассуждения о системах типов существует множество вариаций типизированных λ- вычислений .λ λ
источник
Есть много преимуществ использования Lisp или функционального программирования, и время выполнения алгоритма вычисления - только одна из возможностей (хотя было бы полезно, если бы вы упомянули ссылку для этого). поскольку его функциональная запись уже используется, иногда определение формул для времени выполнения с помощью индукционных или рекуррентных отношений может иметь более сильное или более очевидное отношение к исходному коду. Упрощены и другие виды анализа алгоритма.
Другое главное преимущество - синтаксическая простота. парсеры для других языков очень сложны, но парсеры Lisp очень просты. так что Лисп - отличный язык для изучения теории парсинга.
Другим ключевым аспектом является анализ программного обеспечения в большей степени с логической или математической точки зрения / взгляда, чем с точки зрения «компьютерной науки».
как указывает другой ответ, Лисп - это рекурсия, а не итерация, а рекурсия лежит в основе CS.
[1] Структура и интерпретация компьютерных программ, Абельсон и Суссман
источник