Лямбда-исчисление и история ФП
ФП появилось не из лямбда-исчисления Чёрча, а из прикладной задачи Маккарти на Fortran. Связь с λ обнаружена задним числом. Машина Тьюринга — модель императива (запись на бумаге), а λ-исчисление — модель функционального.
Машина Тьюринга = императив
Тьюринг говорит, что вот как думает математик: он берёт листок и на нём что-то пишет, сохраняет промежуточные результаты, потом снова пишет, считает.
Императивное программирование — это когда мы на листике что-то считаем.
Запись на бумаге = переменная. Перезапись = присваивание. Алгоритм шагов = программа.
Архитектура фон Неймана
Известная статья 1960-х: «не слишком ли мы много сейчас думаем об архитектуре фон Неймана».
Первые компьютеры строили инженеры под прикладные задачи (расчёт траекторий, шифрование). Им сказали: «надо чтобы самолёт летел, пулемёт стрелял». Теория λ-исчисления их не интересовала.
Маккарти и условное выражение
Маккарти писал на Fortran шахматную программу. Ему захотелось написать что-то вроде условного выражения — получить значение в зависимости от истинности условия.
// Маккарти хотел не оператор if/else, а expression:
const result = condition ? valueA : valueB;
// вместо:
// if (condition) { doA; } else { doB; }
Нам не нужны процедуры с наборами действий. Мы всё можем описать функциями, возвращающими значение. Так появилось ФП.
Fortran → Pascal → LISP
| Язык | Эволюция |
|---|---|
| Fortran | subroutine с возвратом и без |
| Pascal | разделение function / procedure |
| LISP (Маккарти) | только функции, всё — expression |
Связь с λ обнаружена задним числом
Я слушал десятки лекций на YouTube, которые мне говорили, что лямбда-исчисление является базой функционального программирования. Оно является, но эта связь была обнаружена задним числом.
Это случайно так получилось.
Что такое λ-исчисление
λ-исчисление Чёрча (1930-е) — формальная система для построения и применения функций. Основа теории вычислимости. Всё там — функции и применение функций. Нет состояния, нет циклов.
Параллельно с машиной Тьюринга — две эквивалентные модели вычислимости.
Чистый ФП-стиль в λ-духе
const inc = x => x + 1;
const add = (a, b) => a + b;
const mul = (a, b) => a * b;
const iif = (cond, t, f) => cond ? t : f;
const loop = (cond, body) => cond ? (body, loop(cond, body)) : null;
Все операторы заменены функциями. Программа — только объявление и вызов функций.
Можно написать любую программу только на функциях. Но синтаксис будет не очень удобным.
ФП ≠ функциональные компоненты React
Функциональное программирование построено не поверх концепций "чистая функция, иммутабельность". Эти концепции — естественно вытекающие свойства из того, что мы оперируем функциями как математическими функциями.
Лямбда-исчисление — мать всего программирования. Разговор только про то, как выстраивать и оперировать абстракциями.
Декларативность под капотом — императив
Декларативный код всегда содержит под капотом императивный. V8 преобразует функции в более низкоуровневые операторы. Процессор преобразует инструкции в микроинструкции.
Десятки слоёв эмуляции одной абстракции через другую. Вопрос только в том, какой синтаксис удобен для написания бизнес-логики.
Связанные темы
Ресурсы
- Лекция Брагилевский + : bUwCRiED4Uo
- Архивная часть 6 (операторы через функции): 0ldgoRKoTuo