Цикл Гекса

В прошлом уроке свиток научился просить провод и часы из Сундука. Внутри он всё ещё тот, что мы собрали в уроке 30: объект с замыканием run, которое зовёт run вложенного свитка. Этот урок о том, почему такой Гекс не переживёт настоящую ночь на Магистрали, и как переделать его, чтобы длина свитка перестала иметь значение, а ответ провода можно было ждать, не останавливая подвал.

Сто тысяч карточек

Вот свиток Ринцвальда без провода: сто тысяч шагов, каждый прибавляет единицу. Гекс тот, что получился на этапе 3.

import * as IO from './IO';

let scroll: IO.IO<number> = IO.succeed(0);
for (let i = 0; i < 100_000; i++) scroll = IO.flatMap(scroll, (n) => IO.succeed(n + 1));

console.log(IO.runSync(scroll));

RangeError: Maximum call stack size exceeded
    at Object.run (IO.ts:35:18)
    at Object.run (IO.ts:35:23)
    at Object.run (IO.ts:35:23)

Трасса сокращена, в настоящей тысячи одинаковых строк. Строка 35 этапа 3 это const exit = self.run(context); внутри flatMap. Запусти тот же свиток на тысяче шагов, и он ответит 1000, на десяти тысячах ответит 10000. Где-то дальше он ломается, а где, зависит от того, где он исполняется: у Node граница между десятью и двадцатью тысячами, у браузера своя.

Дело не в Гексе и не в свитке. Каждый flatMap этапа 3 это замыкание, которое зовёт run своего self и ждёт ответа. Сто тысяч flatMap, вложенных друг в друга, это сто тысяч вызовов, которые стоят друг у друга на плечах: внешний ждёт внутреннего, тот ждёт следующего. Каждый ждущий вызов занимает место на стеке вызовов, а стек у движка маленький. Свиток хранил «что делать потом» в самих вызовах, и длина записи превратилась в глубину вызовов.

Магистраль за ночь передаёт больше ста тысяч кадров. Повтор, который ждёт ответа и пробует снова, это тоже flatMap за flatMap. Гекс, который падает на длине, башне не годится.

Свиток деревом

Пондер предлагает перестать хранить продолжение в вызовах. Пусть свиток будет не функцией, которая что-то делает, а данными, которые описывают, что сделать. Каждая операция Гекса становится карточкой с ярлыком:

import type * as Exit from './Exit';

type Instruction =
  | { readonly _op: 'Succeed'; readonly value: unknown }
  | { readonly _op: 'Sync'; readonly thunk: () => unknown }
  | { readonly _op: 'Fail'; readonly cause: Exit.Cause<unknown> }
  | { readonly _op: 'FlatMap'; readonly self: Instruction; readonly f: (a: unknown) => Instruction }
  | { readonly _op: 'Catch'; readonly self: Instruction; readonly f: (e: unknown) => Instruction };

Это размеченное объединение из урока 07, только тег зовут _op, а не _tag. Карточка инструкции ничего не делает сама. FlatMap хранит вложенный свиток и функцию, которая скажет, что делать с его успехом, но ничего не зовёт. Свиток Ринцвальда становится деревом из ста тысяч карточек FlatMap, вложенных друг в друга, и построить такое дерево ничего не стоит: это сто тысяч объектов, а не сто тысяч вызовов.

Снаружи свиток остаётся таким же. Тесты прошлых этапов знают только succeed, flatMap, catch и runSync, и им всё равно, что внутри. Поэтому тип свитка закрывает начинку:

export interface IO<out A, out E = never, out R extends string = never> {
  readonly '~geks': { readonly A: A; readonly E: E; readonly R: R };
}

Поля ~geks у значения нет, оно только несёт A, E и R в типе, как бренды из урока 14. Аннотации out из урока 13 говорят, что свиток только отдаёт: свиток, который ничего не просит, годится туда, где разрешено просить провод.

Перевод с Ук

Первая попытка написать succeed по-новому:

export interface IO<out A, out E = never, out R extends string = never> {
  readonly '~geks': { readonly A: A; readonly E: E; readonly R: R };
}

type Instruction =
  | { readonly _op: 'Succeed'; readonly value: unknown }
  | { readonly _op: 'Sync'; readonly thunk: () => unknown };

export const succeed = <A>(value: A): IO<A> => ({ _op: 'Succeed', value });

IO.ts(9,51): error TS2353: Object literal may only specify known properties, and '_op' does not exist in type 'IO<A, never, never>'.

Строка 9, колонка 51: поле _op в литерале объекта. TS2353 это проверка лишних полей: объект пишут прямо в место, где ждут IO<A>, а у IO<A> есть только ~geks, и _op для него лишнее. Компилятор прав: снаружи свиток не обязан выглядеть как карточка, в этом и смысл закрытого типа. Внутри модуля карточку и свиток связывают две функции-переходника с приведением as unknown as: одна выдаёт карточку за свиток, другая обратно. Это единственное место, где модуль говорит компилятору «поверь мне», и оно стоит рядом с тем, кто знает правду.

Муравей со стопкой

Исполняет карточки цикл исполнения. В Гексе это муравей: он берёт верхнюю карточку, делает, что на ней написано, а «что делать потом» носит на спине стопкой. Стопка это обычный массив, стек продолжений, и живёт он в куче, где места на миллионы элементов.

• FlatMap кладёт на стопку рамку «по успеху позови f» и берёт в руки вложенный self.
• Catch кладёт рамку «по провалу позови f» и тоже берёт self.
• Succeed это готовый ответ. Муравей снимает рамки со стопки, пока не найдёт рамку успеха, зовёт её функцию и берёт в руки свиток, который она вернула.
• Fail снимает рамки до рамки провала. Дефект Die рамку провала пропускает: catch ловит только ожидаемые ошибки, как на этапе 2.
• Стопка пуста, а в руках ответ: свиток кончился.

Вот как муравей проходит маленький свиток flatMap(flatMap(succeed(2), n => succeed(n + 1)), n => sync(() => n * 10)):

Глубина вызовов не растёт: функция цикла не зовёт сама себя, она крутится в одном while. Сто тысяч flatMap это сто тысяч рамок в массиве, и Гекс их снимает одну за другой.

Пройди цикл сам. Переключатель делает второй шаг провальным: посмотри, как Fail снимает рамки успеха, не зовя их, пока не дойдёт до рамки catch.

Сундук тоже переезжает в цикл. provideService становится карточкой Provide: муравей кладёт на стопку рамку «верни прежний Сундук», кладёт сервис в Сундук и берёт вложенный свиток. Когда тот кончится, успехом или провалом, рамка вернёт Сундук каким был, и сервис не утечёт к соседям.

Под капотом

Ждущий вызов на стеке держит адрес возврата, свои аргументы, локальные переменные и служебные поля движка. Движок отводит под стек фиксированный кусок памяти, обычно около мегабайта, потому что стек нужен быстрым и непрерывным. Рамка в нашем массиве это маленький объект с ярлыком и одной функцией, а массив растёт в куче, пока хватает памяти. Мы не сэкономили работу, мы перенесли её туда, где для неё есть место.

Этот приём старше Effect. В функциональных языках его зовут трамплином: функция не вызывает следующую, а возвращает её циклу, и цикл прыгает дальше. У настоящего Effect под капотом такой же цикл со стеком, только сложнее: его муравей ещё и время от времени уступает трубку другим муравьям, чтобы один длинный свиток не занял весь подвал. Об этом раздел EF7.

Колокольчик

У Гекса этапа 3 была ещё одна беда, менее заметная: он умел только синхронное. Провод Магистрали отвечает не сразу, и муравей должен уметь стоять у трубки и ждать звонка, не держа подвал.

Для этого в Гексе появляется карточка Callback. На ней записана функция register: муравей зовёт её и отдаёт ей resume, «позвони, когда будет ответ». Дальше муравей уходит: цикл кончается, стопка остаётся лежать. Когда кто-то зовёт resume с продолжением свитка, цикл запускается снова с той же стопкой и тем же Сундуком.

import * as IO from './IO';

const bell = IO.callback<string>((resume) => {
  console.log('муравей ждёт у колокольчика');
  setTimeout(() => resume(IO.succeed('динь')), 100);
});

const scroll = IO.flatMap(bell, (sound) => IO.sync(() => `услышал: ${sound}`));

void IO.runPromise(scroll).then((line) => console.log(line));
console.log('runPromise вернулся сразу');

муравей ждёт у колокольчика
runPromise вернулся сразу
услышал: динь

runPromise запускает цикл и отдаёт промис, который разрешится, когда стопка опустеет. sleep(ms) это тот же колокольчик с таймером. register может вернуть отменялку, у sleep она чистит таймер; пользоваться ей Гекс научится в боссе.

Две тонкости колокольчика проверяют тесты. Первая: звонок считается один, второй и дальнейшие вызовы resume Гекс пропускает. Вторая: если resume позвали прямо внутри register, синхронно, муравей не должен запускать новый цикл изнутри старого. Иначе сто тысяч мгновенных ответов снова превратились бы в сто тысяч вложенных вызовов. Поэтому цикл помнит, внутри ли он ещё register, и если да, берёт ответ в руки и едет дальше.

А runSync на свитке с колокольчиком ждать не может: он синхронный, и ответа к его концу ещё нет. Гекс говорит об этом дефектом:

Error: свиток ждёт ответа: запускай его через runPromise

Где тут дыра

import * as IO from './IO';

const relayed = (frames: number): IO.IO<number> =>
  frames === 0 ? IO.succeed(0) : IO.map(relayed(frames - 1), (n) => n + 1);

console.log(IO.runSync(relayed(1000)));
console.log(IO.runSync(relayed(100_000)));

1000
RangeError: Maximum call stack size exceeded
    at relayed (relayed.ts:4:41)
    at relayed (relayed.ts:4:41)
    at relayed (relayed.ts:4:41)

На тысяче работает, на ста тысячах падает, и Гекс тут ни при чём: в трассе нет ни одной строки цикла, только relayed. Чтобы построить свиток на сто тысяч, relayed(100000) сначала зовёт relayed(99999), и так до нуля. Стек кончается, пока свиток записывают, до того как Гекс увидел первую карточку. Цикл спасает исполнение, а запись Ринцвальда рекурсивная сама по себе.

Лечится тем, что рекурсия переезжает внутрь flatMap: следующий кусок свитка строится, только когда муравей до него дошёл.

const relayed = (frames: number): IO.IO<number> =>
  IO.flatMap(IO.succeed(frames), (left) =>
    left === 0 ? IO.succeed(0) : IO.map(relayed(left - 1), (n) => n + 1),
  );

console.log(IO.runSync(relayed(1000)));
console.log(IO.runSync(relayed(100_000)));

1000
100000

Теперь relayed(100000) возвращает одну карточку FlatMap и больше ничего не зовёт. Остальное построит муравей, по куску за шаг, и каждый кусок он строит, держа на стопке рамки, а не на стеке вызовы.

Гекс, этап 4

Гекс перестраивается целиком: свиток становится деревом инструкций, а исполняет его цикл со стопкой продолжений и колокольчиком для ответов, которые придут потом. IO.ts пишется заново, но снаружи ничего не меняется: тесты всех прошлых этапов идут вместе с новыми, на ста тысячах шагов. Тексты ошибок и правила колокольчика в карточке заказа.

const scroll = IO.catch(
  IO.flatMap(IO.fail('обрыв'), (n: number) => IO.succeed(n + 1)),
  (error) => IO.succeed('поймал: ' + error),
);

Практика

Глубже в архиве

Колокольчик Гекса это колбэк, а запуск цикла заново из resume это та же идея, что очередь задач и цикл событий самого JavaScript. Как движок ждёт таймеры и сеть, не останавливая страницу, разбирает урок «Колбэки и цикл событий», а как поверх этого устроены промисы и async, урок «Как устроена асинхронность».

Дальше

Свиток Ринцвальда проходит все сто тысяч кадров, муравей стоит у колокольчика и не держит подвал. Пондер переписывает на доску сводку башни из прошлого урока:

export const checkTower: IO.IO<string, WireError, 'Wire' | 'Clock'> = IO.flatMap(
  IO.service(Wire),
  (wire) =>
    IO.flatMap(wire.read, (frames) =>
      IO.flatMap(IO.service(Clock), (clock) =>
        IO.map(clock.now, (now) => `${now}: кадров ${frames.length}`),
      ),
    ),
);

Как записать свиток сверху вниз и заставить компилятор самому собрать ошибки и нужды всех шагов, разберём в следующем уроке.