Lazy evaluation: стратегии, thunks, fusion, generators

В уроке 05 ты увидел стримы и async-итераторы. В уроке 08 разобрал Effect-TS с его ленивой Effect<A, E, R>. В уроке 16 написал hylo, который “разворачивает и сворачивает” структуру одним проходом без явной материализации. Все три темы это разные грани одной идеи: lazy evaluation.

Сегодня мы разберёмся, какие бывают стратегии вычисления, как работает thunk-машинерия Haskell, что такое WHNF и пространственные утечки, как Stream Fusion даёт haskell-коду асимптотику быстрее ручной, и как это всё переносится на JS/TS через generators, Iterator Helpers и Effect Stream. Это последний урок FP-серии: после него ты прочитаешь Haskell без подсказок и увидишь, почему Promise это eager, а Task lazy.

Три стратегии: value, name, need

Когда функция вызывается с аргументом, у языка есть выбор: что делать с этим аргументом до того, как зайти в тело.

Call-by-value (CBV): аргумент вычисляется полностью до вызова. Это привычная семантика из C, Java, Python, JS:

const f = (x: number, y: number): number => x; // y игнорируется
f(1, expensive()); // expensive() всё равно посчитается

expensive() вычисляется, даже если результат f его не использует. Это просто, но иногда расточительно.

Call-by-name (CBN): аргумент подставляется в тело функции как есть и вычисляется каждый раз, когда к нему обращаются:

// псевдокод: f с CBN
const fName = (x: () => number, y: () => number): number => x() + x();
fName(() => 1 + 2, () => expensive()); // y() не вызывается, x() вызывается дважды

Хорошо: expensive() не считается, если не нужно. Плохо: x посчитается дважды, хоть и одинаковое значение.

Call-by-need (CBNeed): улучшение CBN, аргумент вычисляется лениво, но результат кешируется. Первое обращение к x запускает вычисление, второе возвращает кеш. Это мемоизированный lazy. Это и есть стратегия Haskell.

В TypeScript нет нативного call-by-need, но он легко эмулируется руками:

type Lazy<A> = () => A;

const lazy = <A>(f: () => A): Lazy<A> => {
  let computed = false;
  let value: A;
  return () => {
    if (!computed) {
      value = f();
      computed = true;
    }
    return value;
  };
};

const expensive = lazy(() => {
  console.log('considered expensive');
  return 42;
});

expensive(); // печатает "considered expensive", возвращает 42
expensive(); // ничего не печатает, возвращает 42

Это и есть thunk: отложенное вычисление с встроенной мемоизацией.

Haskell как канон lazy: thunks, WHNF, normal form

В Haskell каждое значение это либо ещё не посчитанный thunk, либо уже посчитанное WHNF, либо Normal form.

WHNF означает: верхний конструктор (или лямбда, или примитив) известен, дочерние позиции могут быть thunk-ами. Например, у списка x:xs известно, что это cons, но x и xs могут быть thunk-ами. Этого достаточно для большинства pattern-match-ов.

Pattern matching форсирует до WHNF. Если в коде написано

case xs of
  []     -> 0
  (x:_) -> 1

то xs форсируется до WHNF (надо узнать, пустой список или нет), но x остаётся thunk-ом. Это даёт возможность работать с потенциально бесконечными структурами: take 10 [1..] пишется буквально и работает, потому что [1..] это thunk, развёртываемый по требованию.

В TypeScript аналог это паттерн с Lazy<A>: верхняя структура видна (мы знаем, что это Lazy), но значение разворачивается только при force().

Space leaks и strict-эволюция

Lazy не бесплатен. Главная проблема: space leak, накопление непосчитанных thunk-ов. Классика Haskell:

foldl (+) 0 [1..1000000]
-- строит thunk: (((0 + 1) + 2) + 3) + ... + 1000000
-- и только в конце разворачивает, переполняя стек

Решение это foldl' (со штрихом), строгий вариант, форсирующий аккумулятор на каждом шаге:

foldl' (+) 0 [1..1000000]
-- на каждом шаге: forced acc, считается + new, forced снова
-- работает в константной памяти

В Haskell есть несколько способов “сделать строго”:

• seq a b форсирует a до WHNF, потом возвращает b. Базовый кирпич strict-программирования.
• $! это f $! x означает “посчитай x до WHNF, потом примени f”.
• BangPatterns (!x) в pattern: форсирует переменную сразу при matching.
• deepseq идёт глубже WHNF: разворачивает всю структуру.

В современном Haskell принят паттерн “lazy by default, strict where proven needed”. Каждый strict-оператор обоснован: либо профилирование показало leak, либо алгоритмически нужна нагрузка на каждом шаге (например, в foldl' для аккумуляции суммы).

В JavaScript ситуация обратная: всё eager по умолчанию. Space leaks у нас бывают по другой причине: захват переменных в замыкания, event-listener-ы, неосвобождённые таймеры. Это не “leak от lazy”, это leak от удержания ссылок.