Пример вычисления (простая β‑редукция):
$(\lambda x.\lambda y.x)ab\equiv ((\lambda x.\lambda y.x)a)b$
1. Подстановка по $x$: $(\lambda x.\lambda y.x)a\to \lambda y.a$.
2. Применение к $b$: $(\lambda y.a)b\to a$.
Итого выражение сворачивается в $a$.
Как это связано с функциональными языками, замыканиями и рекурсией — кратко:
- Модель: лямбда‑исчисление формализует вычисление как абстракции (функции) и применение (β‑подстановка). Концепции first‑class функций и высших порядков в функциональных языках напрямую берутся из лямбда‑исчисления.
- Замыкания: в лямбда‑исчислении функция может иметь свободные переменные; при фактическом создании функции (например, $(\lambda x.\lambda y.x+y)5\to \lambda y.5+y$) свободные переменные фиксируются. В реализациях это представляют как замыкание — код функции плюс окружение значений для её свободных переменных. Пример:
$(\lambda x.\lambda y.x+y)5\to \lambda y.5+y$ — замыкание хранит $x=5$.
- Рекурсия и фикс‑точка: лямбда‑исчисление не требует именованных функций — рекурсия достигается через оператор фикс‑точки. Пример классического Y‑комбинатора:
$Y=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$.
Для любой функции $f$ выполняется:
$Yf\to f(Yf)$,
то есть $Yf$ — фикс‑точка $f$, дающая рекурсивное поведение. (Важное замечание: классический $Y$ корректен при ленивой оценке; в строгих языках применяют модификации или встроенную поддержку фикс‑точки/именованных функций.)
Вкратце: лямбда‑исчисление — математический каркас, от которого происходят базовые принципы функциональных языков; замыкания и механизмы рекурсии — практические реализации этих принципов в рантайме и синтаксисе.