Модель вычислений: thunk, WHNF и ленивость

Ленивость это не флажок оптимизации, а модель вычислений. До сих пор мы пользовались её следствиями на веру: бесконечные списки из урока 01, ранний выход и ленивый foldl из урока 05. Сегодня заглядываем под капот. Граф редукции, thunk, WHNF против NF, sharing, seq и $!. Отсюда выводится всё остальное: почему именно foldl копит память, как работает строгий аккумулятор и что такое space leak.

Идея

В уроке 01 ты разобрал стратегию: Haskell редуцирует в нормальном порядке, то есть сначала подставляет аргумент, не вычисляя его, и считает только когда результат действительно понадобится. Там же был обещан тёмный угол. Пришли за ним.

Начнём с картинки, которая всё держит. Программа на Haskell это не последовательность шагов, а одно большое выражение. Вычислить его значит редуцировать: упрощать по шагу, пока не останется значение. Но выражение это не дерево, а граф: если одно подвыражение названо и используется дважды, в графе это один узел, на который смотрят два места.

Пока узел не понадобился, он лежит неподсчитанным. У этого отложенного узла есть имя.

Это thunk: коробка с рецептом вычисления, а не с готовым блюдом. Любой аргумент функции, любой элемент списка, любой let, всё это по умолчанию рождается thunk-ом. Считать начинаем, только когда снаружи кто-то требует значение. Это требование называют форсированием (forcing).

Возникает вопрос: до какой степени форсировать? Не всегда нужно считать до конца. И тут прячется самое полезное различие урока.

ghci> let pair = (1 + 2, 3 + 4)

Чтобы узнать, что pair это пара (а не, скажем, undefined), достаточно довести его до внешнего конструктора (,). Содержимое 1 + 2 и 3 + 4 при этом считать не обязательно: оно остаётся двумя thunk-ами внутри пары. Такая частично вычисленная форма, до первого конструктора снаружи, называется WHNF, слабая головная нормальная форма.

А NF, полная нормальная форма, это когда thunk-ов не осталось вовсе, выражение вычислено до самого дна.

Разница между WHNF и NF это весь сегодняшний урок в одном кадре. Запусти первый пресет в виджете и пройди по шагам: видно, как форсирование сначала добирается до пары (WHNF), и только потом, если кто-то просит, лезет внутрь компонентов (NF).

Держи эту модель в голове: граф из thunk-ов, форсирование по запросу, две глубины готовности. Дальше только применяем её к реальному коду.