Содержание
Независимо от Алонзо Чёрча другой учёный из Принстона, Алан Тьюринг делал усилия в аналогичном направлении. Он разработал другую формальную систему (которую сейчас называют машиной Тьюринга) и с ее помощью пришёл к тем же самым выводам, что и Алонзо. Позже Алан показал, что машина Тьюринга и лямбда-исчисление эквивалентны по мощности.
В лямбда-исчислении каждое лямбда-выражение представляет собой некоторую функцию от одного аргумента. Этот аргумент в свою очередь есть пара («функция-параметр».«функция-значение»), а λ означает «отобразить». Примеры:
“f(x) = x” := λ x. x тождественная функция
“f(x) = c” := λ x. c постоянная функция со значением c для любого аргумента
“f(x) = x+2” := λ x. x+2 функция «прибавить два»
“f(x, y) = x-y” := λ x y. x-y функция вычитания
Как обычно, имя связанных формальных параметров особого значения не имеет. Определяются правила преобразования лямбда-выражений (правила обозначаются греческими буквами α, β и η). Эти правила формализуют переход между различными записями одной и той же функции (термин «одна и та же функция» в интуитивном понимании). Например:
(λ x y. x-y) 5 2 — (λ y. 5-y) 2 — 5-
Выдержка из текста
Праотцом функционального программирования можно считать Алонзо Чёрча. Он разработал формальную систему, названную лямбда-исчислением. Эта система была на самом деле языком программирования для воображаемой машины. Язык был основан на функциях, которые принимали функции в качестве параметров и возвращали функции в качестве результата. Функции обозначались греческой буквой λ, откуда и название. Используя эту формальную систему, Алонзо смог исследовать следующие вопросы — Если бы у нас была машина бесконечной вычислительной мощности, какие задачи мы бы смогли решать? Могли бы мы их решать автоматически? Могли ли некоторые задачи остаться неразрешимыми и почему? Могли ли разные машины с разной архитектурой быть равными по мощности?
Список использованной литературы
При написании использовались Википедия и справка Microsoft по ФП.