Продолжения и CPS: откуда взялись колбэки, генераторы и async/await

Вы пишете строчку:

const user = await fetchUser(id);
renderProfile(user);

И где-то в глубине рантайма происходит вот что: функция останавливается, а всё, что должно было выполниться после await — присваивание в user, вызов renderProfile, возврат из функции и всё, что стоит за ней в вызывающем коде, — упаковывается в объект и откладывается до момента, когда придёт ответ. Этот «весь оставшийся код» и есть продолжение (continuation). А приём, которым его делают явным значением, называется CPS — continuation-passing style.

Идея чисто лямбда-исчисленческая, ей полвека, и из неё выросли: колбэки в Node, промисы, async/await в JavaScript, C#, Rust и Python, генераторы, обработка исключений, ранний выход из цикла, call/cc в Scheme, алгебраические эффекты в OCaml 5, а также внутреннее устройство целого класса компиляторов. Разберём её от определения до стектрейсов в проде.

Что такое продолжение

Возьмём выражение и вычислим его в аппликативном порядке (https://courses.digitable.life/post/lambda-calculus/08-evaluation-strategies/):

1 + f 2 * 3

В момент, когда вычисляется f 2, «оставшаяся работа» полностью известна: получить значение v, умножить на 3, прибавить 1, отдать результат наружу. Запишем эту оставшуюся работу функцией:

k = λv. 1 + v * 3

Вот это k и есть продолжение подвыражения f 2 в данном контексте. Формально: если терм представим как E[M], где E — контекст вычисления (терм с дыркой), то продолжение M — это функция λv. E[v].

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

Программисту это знакомо в частных случаях:

Дисциплина CPS: функция, которая не возвращает

Обычная функция возвращает значение. Функция в CPS не возвращает ничего — она принимает дополнительный аргумент k и в конце вызывает его с результатом. Всё.

# прямой стиль
def add(a, b):
    return a + b

def square(x):
    return x * x

def f(x):
    return add(square(x), 1)

# тот же код в CPS
def add_k(a, b, k):
    return k(a + b)

def square_k(x, k):
    return k(x * x)

def f_k(x, k):
    return square_k(x, lambda s: add_k(s, 1, k))

Смотрите на f_k: порядок вычислений, который в прямом стиле был неявным (сначала square, потом add), теперь записан в структуре кода. Не осталось ни одного места, где нужно «вернуться и продолжить»: каждый вызов — последний в своей функции, то есть хвостовой.

Три свойства CPS-кода, которые стоит запомнить сразу:

1. Все вызовы хвостовые. Ни один вызов не ждёт результата — результат придёт в продолжение.
2. Порядок вычисления зафиксирован в терме. Ленивая, строгая, любая другая стратегия дадут один и тот же ответ.
3. Стек не нужен. Вернее, он переехал в кучу: цепочка замыканий-продолжений — это тот же стек, только в виде данных.

Правила преобразования

Преобразование, переводящее произвольный лямбда-терм в CPS, придумали Фишер и Плоткин в 1970-х. Обозначим [[M]] k — «терм M, вычисленный в CPS, с продолжением k». Правил ровно три — по одному на конструкцию языка (https://courses.digitable.life/post/lambda-calculus/01-syntax/):

[[x]]     k  =  k x                                   переменная уже значение
[[λx. M]] k  =  k (λx. λk'. [[M]] k')                 функция получает лишний параметр
[[M N]]   k  =  [[M]] (λm. [[N]] (λn. m n k))         сначала функция, потом аргумент

Третье правило — единственное содержательное, и в нём вся суть: чтобы вычислить аппликацию, надо сначала вычислить M (её продолжение — «получив m, вычисляй N»), затем N (её продолжение — «получив n, вызывай m с аргументом n и внешним продолжением k»). Поменяйте местами M и N в правиле — получите преобразование для языка, вычисляющего аргументы справа налево. Порядок вычисления перестал быть свойством интерпретатора и стал свойством преобразования.

Прогоним преобразование на конкретных термах (это вывод программы-транслятора, свежие имена генерируются автоматически):

[[(λx. x) y]] k  =  (λm1. (λn2. m1 n2 k) y) (λx. (λk3. k3 x))

[[f (g x)]] k    =  (λm1. (λm3. (λn4. m3 n4 (λn2. m1 n2 k)) x) g) f

Выглядит нечитаемо — так и есть, CPS-код не предназначен для чтения человеком. Зато посмотрите на структуру: ни одной аппликации, результат которой куда-то «возвращается». Только цепочка вызовов, каждый из которых передаёт управление дальше.

Транслятор, породивший строки выше, помещается в двадцать строк:

def V(x):    return ('var', x)
def L(x, b): return ('lam', x, b)
def A(m, n): return ('app', m, n)

counter = [0]
def fresh(prefix):
    counter[0] += 1
    return f'{prefix}{counter[0]}'

def cps(t, k):
    """[[t]] k — преобразование Фишера-Плоткина для вычисления по значению."""
    if t[0] == 'var':                       # [[x]] k = k x
        return A(k, t)
    if t[0] == 'lam':                       # [[λx.M]] k = k (λx.λk'. [[M]] k')
        kk = fresh('k')
        return A(k, L(t[1], L(kk, cps(t[2], V(kk)))))
    if t[0] == 'app':                       # [[M N]] k = [[M]] (λm. [[N]] (λn. m n k))
        m, n = fresh('m'), fresh('n')
        return cps(t[1], L(m, cps(t[2], L(n, A(A(V(m), V(n)), k)))))
    raise ValueError(t)

Сложность. Один проход по терму: O(n) по времени, результат линейно больше исходного — примерно втрое по числу узлов. Никаких проверок захвата имён не нужно: транслятор сам порождает свежие имена (m1, n2, k3), поэтому проблема из https://courses.digitable.life/post/lambda-calculus/02-variables-and-substitution/ не возникает.

Главная теорема: CPS убивает выбор стратегии

Вот ради чего это делалось теоретически. Гордон Плоткин в работе Call-by-name, call-by-value and the λ-calculus (Theoretical Computer Science, 1975) доказал: после CPS-преобразования терм ведёт себя одинаково при любой стратегии вычисления. Вычисляйте его по значению, по имени, лениво, в нормальном порядке — результат один и тот же.

Причина видна из правил: в CPS-терме единственный «выбор», который был у редуктора — какой редекс сократить первым, — уже сделан за него и записан в структуре. Помните пример из https://courses.digitable.life/post/lambda-calculus/08-evaluation-strategies/, где (λx. λy. y) Ω a завершался при нормальном порядке и зацикливался при аппликативном? После CPS-преобразования по значению он будет зацикливаться всегда, после преобразования по имени — завершаться всегда. Стратегия перестала быть свойством машины и стала свойством программы.

Отсюда практическое следствие, объясняющее половину компиляторов на свете: CPS — это промежуточное представление, в котором порядок вычисления явный, а все вызовы хвостовые. Компилятору с таким IR не нужно отдельно думать про порядок аргументов, про раскрутку стека и про то, куда вернуться. Именно так устроен SML/NJ (Эндрю Аппель, Compiling with Continuations, 1992), Guile, часть проходов в компиляторах Scheme и, с оговорками, современные JS-движки для async-функций.

Административные редексы и ANF

У наивного CPS есть неприятная черта: он порождает кучу редексов, которых не было в исходной программе. В выводе выше видно (λn2. m1 n2 k) y — это «применить продолжение к уже готовому значению», чистая бюрократия. Такие редексы называют административными, их сокращают отдельным проходом (или сразу пишут one-pass CPS-транслятор, который их не создаёт).

Флэнеган и соавторы в статье The Essence of Compiling with Continuations (PLDI 1993) показали, что если сократить все административные редексы, получится представление, изоморфное A-нормальной форме (ANF): каждое промежуточное значение получает имя через let, аргументы вызовов — только атомы.

// исходное выражение
f (g x) + h y

// ANF: всё промежуточное названо
let a = g x in
let b = f a in
let c = h y in
b + c

Узнаёте? Это буквально SSA-форма из компиляторов, только записанная через let вместо φ-функций. Эндрю Аппель написал об этом статью с говорящим названием SSA is Functional Programming (1998). Подробнее про IR и SSA — https://courses.digitable.life/post/compilers/06-intermediate-representation/.

Практика 1: рекурсия, которая не переполняет стек

Возьмём факториал. В прямом стиле он не хвостовой: после рекурсивного вызова остаётся умножение.

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)     # умножение ЖДЁТ возврата

В CPS «ожидание» становится явным замыканием:

def fact_cps(n, k):
    if n == 0:
        return k(1)
    return fact_cps(n - 1, lambda v: k(n * v))  # хвостовой вызов

print(fact_cps(10, lambda v: v))   # 3628800

Все вызовы теперь хвостовые — казалось бы, стек расти не должен. Но в Python (как и в JS до недавнего времени) нет устранения хвостовых вызовов, поэтому:

fact_cps(5000, lambda v: v)   # RecursionError: maximum recursion depth exceeded

Стек всё равно переполнится. Лечится это трамплином: функция вместо рекурсивного вызова возвращает «заявку» на вызов, а внешний цикл её исполняет.

def fact_tramp(n, k):
    if n == 0:
        return ('done', k, 1)
    return ('call', lambda: fact_tramp(n - 1, lambda v: k(n * v)))

def trampoline(thunk):
    step = thunk()
    while step[0] == 'call':      # рекурсия превратилась в цикл
        step = step[1]()
    return step[1](step[2])

Приём боевой: так реализованы Trampoline в Cats/Scalaz, IO в ZIO, рекурсивные интерпретаторы в Kotlin, обход глубоких деревьев в JS. Цена — аллокация замыкания на каждый шаг вместо кадра стека, а также потерянная трассировка (https://courses.digitable.life/post/functional-programming/04-recursion/ разбирает хвостовую рекурсию с практической стороны).

Практика 2: дефункционализация — от замыканий к машине состояний

Замыкание-продолжение lambda v: k(n * v) хранит ровно две вещи: число n и ссылку на предыдущее продолжение. А раз состояний конечное число видов, замыкание можно заменить структурой данных с тегом. Приём называется дефункционализацией, придумал его Джон Рейнольдс в Definitional Interpreters for Higher-Order Programming Languages (1972).

Дальше происходит фокус: раз продолжение — это структура, «применение продолжения» превращается в обычный цикл, и вся рекурсия исчезает.

def fact_defun(n):
    k = ('halt',)                 # продолжение как данные, а не как замыкание
    while n != 0:
        k = ('mul', n, k)         # строим цепочку продолжений
        n -= 1
    v = 1
    while k[0] != 'halt':         # «применяем» продолжения циклом
        v = k[1] * v
        k = k[2]
    return v

print(fact_defun(10))   # 3628800

Ни рекурсии, ни замыканий, ни стека — при этом это построчный потомок исходного fact. Мы прошли путь прямой стиль → CPS → дефункционализация → машина состояний, и это ровно то, что делает компилятор с вашей async-функцией: C# строит структуру-стейт-машину с полем state и полями под локальные переменные, Rust компилирует async fn в enum-генератор, Babel/regenerator переписывал async в switch по номеру состояния. Различаются детали, схема одна.

Практика 3: исключения — это второе продолжение

Пока у функции одно продолжение, она умеет только «идти дальше». Дайте два — получите обработку ошибок без единого try:

def div_cps(a, b, ok, err):
    if b == 0:
        return err('деление на ноль')
    return ok(a // b)

print(div_cps(10, 2, lambda v: f'ок: {v}', lambda e: f'ошибка: {e}'))  # ок: 5
print(div_cps(10, 0, lambda v: f'ок: {v}', lambda e: f'ошибка: {e}'))  # ошибка: деление на ноль

Это не педагогический пример, а описание того, как устроены три очень разные вещи:

• Node-колбэки (err, result) => … — два продолжения, слепленных в одно с проверкой первого аргумента.
• Promise.then(onOk, onErr) — два продолжения буквально, по одному на каждый исход.
• try/catch — установка аварийного продолжения на время выполнения блока; throw это вызов текущего аварийного продолжения вместо основного.

И то же самое с другой стороны: Either/Result — это те же два продолжения, только упакованные в значение и разбираемые сопоставлением с образцом (https://courses.digitable.life/post/functional-programming/10-error-handling/). Кодировка Чёрча для Either из https://courses.digitable.life/post/lambda-calculus/06-pairs-and-lists/ — λl. λr. … — это дословно «функция, принимающая два продолжения».

Первоклассные продолжения: call/cc и что за ним

Всё выше — про продолжения, которые создаёт компилятор. В Scheme их можно взять руками: оператор call-with-current-continuation (сокращённо call/cc) захватывает текущее продолжение и передаёт его функции как обычное значение.

;; ранний выход из вычисления: k — «выпрыгнуть с результатом»
(define (product xs)
  (call/cc
    (lambda (k)
      (let loop ((xs xs))
        (cond ((null? xs) 1)
              ((= (car xs) 0) (k 0))          ; встретили ноль — мгновенный выход
              (else (* (car xs) (loop (cdr xs)))))))))

(product '(1 2 0 3 4))   ; => 0, умножения не выполнялись

k здесь — обычное значение: его можно сохранить в переменную и вызвать позже или несколько раз, вернувшись в уже завершённое вычисление. На этом строятся генераторы, бэктрекинг, кооперативная многозадачность и веб-фреймворки с продолжениями (легендарный Seaside в Smalltalk хранил продолжение между HTTP-запросами, так что кнопка «назад» в браузере работала правильно сама собой).

Три уровня силы, которые полезно различать:

Ограниченные (delimited) продолжения — то, что действительно вошло в практику. Данви и Филински (Abstracting Control, 1990) предложили пару операторов shift/reset: reset ставит границу, shift захватывает продолжение до этой границы, а не до конца программы. Разница принципиальная: ограниченное продолжение — это функция, которая возвращает значение, его можно композировать. Из этой линии выросли алгебраические эффекты и обработчики эффектов в OCaml 5 и Koka — механизм, который позволяет написать async, генераторы, транзакции и мокирование ввода-вывода библиотекой, не трогая компилятор.

И ещё одна ниточка назад, к типам. В https://courses.digitable.life/post/lambda-calculus/09-typed-lambda/ мы отмечали, что закон Пирса ((A → B) → A) → A не доказуем конструктивно — и что Тимоти Гриффин в 1990-м показал: его населяет как раз call/cc. Это и есть точный смысл фразы «операторы управления — это классическая логика»: добавляя в язык первоклассные продолжения, вы добавляете в его логику закон исключённого третьего.

Драйвер корутин на генераторах Python, который делает ровно то, что делает event loop, — двадцать строк:

from collections import deque

queue = deque()                  # очередь готовых продолжений — микро-event loop

def later(value):
    """Имитация асинхронной операции: результат появится на следующем такте."""
    return ('await', value)

def spawn(gen, send_value=None):
    """Прокрутить корутину до следующего await и запланировать продолжение."""
    try:
        cmd = gen.send(send_value)
    except StopIteration as done:
        return done.value
    tag, value = cmd
    queue.append(lambda: spawn(gen, value))    # продолжение как задача в очереди

def run(gen):
    result = spawn(gen)
    while queue:
        result = queue.popleft()()
    return result

def fetch_user(uid):
    name = yield later(f'user-{uid}')
    return name

def main():
    a = yield from fetch_user(1)
    b = yield from fetch_user(2)
    return f'{a} и {b}'

print(run(main()))    # user-1 и user-2

Здесь видно всё сразу: yield отдаёт управление и сохраняет продолжение внутри объекта-генератора, очередь хранит отложенные продолжения, а run — это планировщик. Настоящие asyncio и Node-овский event loop устроены сложнее (таймеры, приоритеты, epoll), но по сути делают именно это (https://courses.digitable.life/post/typescript/04-concurrency/).

Цена: чем платит продакшн

Стектрейсы. Самая заметная в бою вещь. В CPS «кто меня вызвал» нигде не записано — есть только «кому отдать результат». Поэтому асинхронный код по умолчанию теряет трассировку: исключение всплывает не там, где логически возникло. Индустрия чинит это костылями: async stack traces в V8 (--async-stack-traces), ExceptionDispatchInfo в .NET, add_note и raise ... from в Python, span-контекст в трассировке (https://courses.digitable.life/post/sre/00-overview/ про наблюдаемость).

Аллокации и GC. Кадр стека освобождается бесплатно, замыкание в куче — нет. Наивный CPS означает аллокацию на каждый шаг вычисления. Компиляторы борются с этим анализом времени жизни, но полностью не побеждают: у ленивых и асинхронных языков это статья расходов номер один (https://courses.digitable.life/post/performance/00-overview/).

Читаемость. CPS-код нечитаем — это его свойство, а не недостаток вашего стиля. Именно поэтому исторический маршрут был: колбэки (человек пишет CPS руками) → промисы (CPS спрятан за объектом) → async/await (компилятор делает CPS сам, а человек снова пишет прямой стиль). Каждый шаг возвращал читаемость, не теряя асинхронности.

Отладка. Точка останова в CPS-коде почти бесполезна: локальные переменные разбросаны по замыканиям, а «шаг с обходом» уводит в планировщик. Это ровно та причина, по которой отладка асинхронного кода ощущается иначе.

Вывод для практики простой: писать CPS руками в прикладном коде не надо. Надо понимать его, чтобы читать чужие трассировки, объяснять поведение await в цикле, знать, откуда берётся RecursionError, и не удивляться, почему try/catch не ловит ошибку из колбэка.

Типичные ошибки и заблуждения

«CPS — это про асинхронность». Нет. CPS — про явный порядок вычисления и явное «что дальше». Асинхронность — самое заметное применение, но не единственное: Y-комбинатор, обход дерева, ранний выход и генераторы к асинхронности отношения не имеют.

«Раз все вызовы хвостовые, стек не переполнится». Только если рантайм устраняет хвостовые вызовы. В Python, JS (кроме Safari) и Java его нет — CPS без трамплина падает с переполнением ровно как обычная рекурсия.

«await блокирует поток». await не блокирует, а разрезает функцию: всё после него становится продолжением, а управление возвращается вызывающему. Ощущение «блокировки» возникает потому, что код выглядит последовательным — в этом и был смысл конструкции.

«Промис — это монада, и всё тут». Промис близок к монаде, но нарушает законы (например, Promise.resolve схлопывает вложенные промисы, из-за чего Promise<Promise<T>> не существует). Правильнее говорить: then — это связывание вычисления с продолжением (https://courses.digitable.life/post/functional-programming/08-monads/).

«Дефункционализация — экзотика из статей 1972 года». Это буквально то, во что компилируется каждая ваша async-функция и каждый Rust-генератор. Просто выполняет её компилятор, а не вы.

«try/catch вокруг вызова асинхронной функции ловит всё». Ловит только то, что случилось до первой точки останова, если вы забыли await. Аварийное продолжение устанавливается на текущий синхронный участок; асинхронная часть должна быть присоединена явно.

Упражнения

1. Переведите в CPS вручную (без транслятора): λx. f (g x). Сравните с выводом правила [[M N]].
2. Напишите в CPS функцию length для списка Python и объясните, почему в ней нет ни одного return с вычислением.
3. Функция fib в CPS требует двух рекурсивных вызовов. Напишите её и покажите, как выглядит продолжение второго вызова.
4. Почему [[M N]] k = [[N]] (λn. [[M]] (λm. m n k)) — тоже корректное преобразование? Чем оно отличается от приведённого в статье?
5. Реализуйте через два продолжения функцию find(xs, pred, ok, not_found) — поиск с ранним выходом. Что здесь играет роль break?
6. Ниже код на JavaScript. Что он напечатает и почему — при том, что try/catch на месте?

function run() {
  try {
    setTimeout(() => { throw new Error("бум"); }, 0);
  } catch (e) {
    console.log("поймали:", e.message);
  }
  console.log("конец run");
}
run();

7. Дефункционализируйте продолжение из вашей length (упражнение 2): замените замыкания структурой с тегом и превратите рекурсию в цикл.

Ответы

1. По правилу для абстракции: [[λx. f (g x)]] k = k (λx. λk'. [[f (g x)]] k'). Тело раскрываем правилом аппликации: [[f (g x)]] k' = [[f]] (λm. [[g x]] (λn. m n k')), где [[f]] c = c f, а [[g x]] c = c применённое к результату g x, то есть (λm'. (λn'. m' n' c) x) g. Итог: функция получает лишний параметр k', а внутри — цепочка «вычислить g x, потом позвать f, потом отдать k'». Ровно то же, что выдаёт транслятор.

2.

def length_cps(xs, k):
    if not xs:
        return k(0)
    return length_cps(xs[1:], lambda n: k(n + 1))

print(length_cps([1, 2, 3], lambda v: v))   # 3

return здесь только «передаёт управление» — вычисления n + 1 происходят внутри продолжения, то есть после того, как рекурсия дошла до дна. Это тот же приём, что в fact_cps: «отложенная работа» стала замыканием.

3.

def fib_cps(n, k):
    if n < 2:
        return k(n)
    return fib_cps(n - 1, lambda a:            # продолжение первого вызова —
           fib_cps(n - 2, lambda b: k(a + b)))  # запуск второго вызова

Продолжение второго вызова — lambda b: k(a + b) — замыкает a (результат первого) и внешнее k. Дерево вызовов превратилось в линейную цепочку замыканий: именно поэтому CPS так удобен для интерпретаторов и так прожорлив по памяти.

4. Корректно: это преобразование для языка, вычисляющего аргумент раньше функции (справа налево). Оба варианта дают одинаковый результат для термов без побочных эффектов и расходимостей, но различаются, когда порядок наблюдаем: если M печатает «первый», а N — «второй», варианты дадут разный вывод. Это и есть тот самый порядок, который в C и C++ до C++17 был unspecified, а в Java и C# зафиксирован слева направо.

5.

def find(xs, pred, ok, not_found):
    if not xs:
        return not_found()
    if pred(xs[0]):
        return ok(xs[0])            # ранний выход: зовём НЕ то продолжение,
    return find(xs[1:], pred, ok, not_found)   # которое ведёт дальше по списку

Роль break играет вызов ok вместо рекурсивного вызова: продолжение «остаток обхода» просто не вызывается и умирает. Все операторы раннего выхода — break, return, continue — устроены так же: отказ от текущего продолжения.

6. Напечатает конец run, а потом упадёт с необработанной ошибкой бум. try/catch устанавливает аварийное продолжение на время синхронного выполнения блока; setTimeout успевает лишь зарегистрировать колбэк и вернуть управление. Когда таймер сработает, стек уже другой, и никакого catch вокруг нет. Ровно та же ловушка — с забытым await внутри try.

7.

def length_defun(xs):
    k = ('halt',)
    while xs:                       # строим цепочку продолжений
        k = ('inc', k)
        xs = xs[1:]
    v = 0
    while k[0] != 'halt':           # применяем их циклом
        v, k = v + 1, k[1]
    return v

Замыкание lambda n: k(n + 1) не хранило ничего, кроме ссылки на следующее продолжение, поэтому тег ('inc', k) его полностью описывает. Получившаяся структура — это односвязный список, то есть тот же стек, только явный.

Мини-итог

• Продолжение — это «весь оставшийся код» в виде функции: если терм это E[M], то продолжение M есть λv. E[v].
• CPS — дисциплина, в которой функция не возвращает значение, а передаёт его дополнительному аргументу k. Преобразование задаётся тремя правилами и делается за один проход.
• После CPS все вызовы хвостовые, а порядок вычисления записан в самом терме — поэтому результат не зависит от стратегии (Плоткин, 1975).
• Сокращение административных редексов превращает CPS в ANF, а ANF — это то же самое, что SSA в компиляторах.
• Дефункционализация продолжений превращает замыкания в структуры с тегом, а рекурсию — в цикл. Это в точности то, во что компилируются async/await и генераторы.
• Два продолжения вместо одного дают обработку ошибок: try/catch, Node-колбэки, Promise.then(ok, err), Either — один и тот же приём.
• call/cc даёт продолжения первым классом (и вместе с ними — классическую логику), ограниченные продолжения shift/reset — их практичный вариант, доросший до алгебраических эффектов в OCaml 5.
• Плата: аллокации вместо кадров стека, потерянные трассировки, тяжёлая отладка. Поэтому CPS — работа компилятора, а не прикладного программиста.

Источники

• Gordon Plotkin. Call-by-name, call-by-value and the λ-calculus, TCS, 1975 — sciencedirect.
• John Reynolds. Definitional Interpreters for Higher-Order Programming Languages, 1972 — surface.syr.edu; там же дефункционализация.
• John Reynolds. The Discoveries of Continuations, LISP and Symbolic Computation, 1993 — история понятия, PDF.
• Cormac Flanagan et al. The Essence of Compiling with Continuations, PLDI 1993 — dl.acm.org.
• Andrew Appel. Compiling with Continuations, Cambridge University Press, 1992.
• Olivier Danvy, Andrzej Filinski. Abstracting Control, LFP 1990 — dl.acm.org.
• Timothy Griffin. A Formulae-as-Types Notion of Control, POPL 1990 — dl.acm.org.
• Daniel Friedman, Matthias Felleisen. The Little Schemer и Essentials of Programming Languages — лучший практический вход в продолжения.
• OCaml 5 Manual, Effect handlers — ocaml.org/manual/effects.html.
• MDN, Асинхронный JavaScript — developer.mozilla.org.

Что дальше

Мы посмотрели на бестиповую сторону: как убрать переменные и как сделать явным порядок. Осталась последняя большая тема трека — типы, которые умеют говорить «для любого». Именно из неё выросли дженерики в Java, C#, Rust, Go и TypeScript, и именно она объясняет, почему по сигнатуре <T>(x: T) => T можно доказать, что функция делает, ни разу не заглянув в её код.

System F: полиморфизм, дженерики и теоремы задаром