Одна из самых эзотерических тем в программировании и computer science это продолжения (continuations), ограниченные продолжения (delimited continuations) и continuation-passing style. Я попытаюсь раскрыть эту тему понятным для обычного программиста языком. Предполагается, что обычный программист знаком с понятиями функции/подпрограммы, не боится термина фрейм вызова (stack frame), а также имеет базовое знание языка Scheme, хотя бы на уровне первых глав SICP.

Одним из первых средств декомпозиции программ и повторного использования кода были подпрограммы. Для работы подпрограммы требовались переданные ей вызывающей стороной параметры, локальные, ненужные вне подпрограммы переменные, а также информация, куда передать управление, когда подпрограмма закончит свое выполнение. Ранние реализации хранили все это в глобальных переменных, но после того, как придумали рекурсию, в памяти могло оказаться несколько экземпляров вызова одной и той же подпрограммы, такой подход пришлось пересматривать. Удобно считать, что все эти данные сгруппированы в один, вообще говоря виртуальный, объект, называемый фреймом вызова, который создается при каждом запуске подпрограммы. Его часто называют фреймом стека, потому что самый популярный подход - хранить его в стеке. Это не совсем корректно, но пока рассмотрим такой подход подробнее. CISC (и многие RISC) процессоры поддерживают специальные инструкции для работы со стеком. В других RISC процессорах такие инструкции легко заменяются простыми последовательностями нескольких примитивных инструкций. Вызывающая сторона помещает параметры вызова в стек, потом в стек помещается адрес возврата и управление передается подпрограмме (на многих процессорах для этого есть специальная инструкция call, на других это делается несколькими инструкциями). Подпрограмма аллокирует в стеке пространство под локальные переменные и сохраняет значения регистров, для которых их неизменяемость гарантируется соглашением о вызове, таким образом завершая формирования фрейма вызова. То, что фрейм частично формируется вызывающей, а частично вызываемой стороной уже дает повод считать этот объект виртуальным. В дополнение, современные соглашения о вызове часто предполагают передачу параметров в регистрах, что еще добавляет виртуальности. На некоторых процессорах соглашение предполагает передачу и адреса возврата в регистре, который подпрограмма сама может при необходимости поместить в стек. При завершении подпрограммы она сама убирает локальные переменные и использует адрес возврата для передачи управления обратно (на многих процессорах для этого есть специальная инструкция ret). Разработчики языка C ради реализации семейства функций похожих на printf приняли решение, на мой взгляд ошибочное, поддержать передачу различного количества аргументов одной и той же функции. В этом случае подпрограмма не имеет информации о том, сколько аргументов надо убрать из стека при возврате, и утилизация аргументов возложена на вызывающую сторону (хотя в VAX количество переданных параметров также сохраняется в стек и фрейм удаляется целиком самой подпрограммой).

Когда последней операцией подпрограммы является вызов какой-нибудь подпрограммы (возможно, себя самой), то манипуляции с фреймом вызова позволяют провести важную оптимизацию - Tail Call Optimization (TCO). Первая подпрограмма может сама чистить стек, сформировать параметры вызова второй, а в качестве адреса возврата передать ей то, что получила сама. Эта оптимизация важна, так как позволяет на ограниченном стеке производить неограниченное количество рекурсивных вызовов. Реализация TCO требует, чтобы подпрограмма имела информацию о количестве переданных параметров. В языках, поддерживающих RAII, таких как C++ и Rust возможность или невозможность TCO не всегда очевидна - даже если последним оператором в тексте подпрограммы является вызов другой, компилятор после него может вставить вызовы деструкторов локальных объектов.

Фрейм вызова можно хранить не в стеке, а аллокировать в куче, как это сделано, например, в Stackless Python. Такой подход позволяет эффективнее реализовать многопоточность (не требуется следить за стеками каждой нити), упрощает реализацию TCO и, как позже будет видно, продолжений.

TCO дает возможность реализовать конечный автомат, кодируя состояние тем, какая функция сейчас работает. Переход в новое состояние реализуется просто вызовом соответствующей функции. Данные, связанные с обработкой предыдущего состояния более не актуальны и удаляются вместе с фреймом вызова. Адрес возврата, с точки зрения низкоуровневой реализации, можно рассматривать как дополнительный аргумент подпрограммы. Более того, фрейм вызова предыдущей подпрограммы можно восстановить исходя из стека, то есть можно абстрагироваться от способа передачи параметров и сказать, что он передается неявно, в большинстве реализаций через регистр.

Принято считать, что явное лучше неявного. Что будет, если мы предоставим коду подпрограммы доступ к этим аргументам? Так как адрес возврата вместе с родительским фреймом вызова нужны для того, чтобы продолжить работу программы после завершения подпрограммы, назовем эту пару continuation!

Такая возможность реализована в языке Scheme. В реальной жизни продолжения нужны не часто, поэтому данный аргумент виден не во всех функциях, а передается специальной функцией call-with-current-continuation, или сокращенно call/cc.

Welcome to Racket v6.3.
> (call-with-current-continuation display)
#<continuation>

display - это функция, печатающая свой аргумент. Мы видим, что ей передан аргумент особого типа, но ведет он себя как функция.

(call/cc (lambda (k) (k 1) (display "Not executed")))
1

Вызов продолжения ведет себя как нелокальный возврат, переданный ей аргумент будет возвращен из создавшего ее вызова call/cc.

((call/cc (lambda (k) (display (call/cc k)) (display "It run. ") display)) "twice ")
twice It run. twice

Может показаться странным, что twice напечаталось 2 раза. Что здесь произошло? Первый вызов call/cc передал в lambda продолжение. Второй передал в первое продолжение (напомню, что это выглядит как нелокальный возврат из call/cc) новое. После первого выхода из первого call/cc новому продолжению передается строка "twice ". И это приводит к выходу из второго call/cc обратно в lambda! Второй call/cc возвращает это строку, которая и печатается первым вызовом display, после чего lambda продолжает свое выполнение как ни в чем не бывало, о чем свидетельствует вывод "It run. ". И завершается наша lambda возвратом из первого call/cc уже во второй раз. Теперь возвращается функция display, которая вызывается также с аргументом "twice ".

Для чего нужны все эти сложности, кроме как для затруднения чтения кода? call/cc достаточно универсальная конструкция. С ее помощью сравнительно легко и безопасно реализуются исключения, итераторы и кооперативная мультизадачность. Правда, в racket сама call/cc не слишком эффективна и более производительная реализация исключений встроена в сам язык. Возможность несколько раз вызвать продолжение позволяет красиво реализовать недетерминированные вычисления, делая вид что функция может возвращать множество результатов. Более высокоуровневые "алгебраические эффекты" для в наиболее полном виде требуют поддержки продолжений. В математике продолжения возникают в лямбда-мю исчислении, которое применяется в логике и исследованиях по семантике естественных языков.

Конечно, трактовка данных, необходимых для выхода из подпрограммы, как обычных параметров, это существенное упрощение. Для реализации продолжений приходится прибегать к тем или иным трюкам и компромисам. Для сохранения эффективности и совместимости с внешними библиотеками на бинарном уровне в продолжение можно просто переместить стек, частично или даже полностью (при необходимости учитывая размещенные там типы данных, например может потребоваться обновление счетчиков ссылок), а при его использовании, копировать все обратно на стек. Если вызов реализуется не с помощью непрерывного в памяти стека, а в виде аллокируемого на куче списка, продолжение будет содержать ссылку на элемент в этом списке. Но если runtime поддерживает замыкания, продолжение можно реализовать как замыкание, содержащее все необходимое чтобы выполнить остаток программы. Такой стиль компиляции так и называется, Continuation Passing Style или просто CPS. Примеры исходного кода, и кода эквивалентного после преобразование в CPS:

(define (f x) x)
(define (g x) 1)
(define (main) (g (f 2)))

(define (f k x) (k x))
(define (g k x) (k 1))
(define (main k) (f (lambda (tmp) (g k tmp)) 2))

В такой программе подпрограммы как бы не завершаются, пока не отработает вся программа. Чтобы такой стиль не вызвал переполнение стека, runtime должен обеспечивать TCO или компилятор должен эмулировать его с помощью батута.

> (require racket/control)
> (+ 1 (reset (* 2 (shift k (k (k 5))))))
21

Код внутри reset как бы выворачивается наизнанку и попадает в shift под именем, заданным первым параметром макроса.