fp2-continuations.tex

%! suppress = EscapeHashOutsideCommand
%! suppress = MissingLabel

Продолжения с начала 60х не один раз возникали в литературе в различных формах и разнообразных приложениях~\cite{reynolds1993discoveries, landin1997histories}, пока в 70х Wadsworth не придумал общий термин и единую концепцию --- \vocab{continuation}\footnote{\url{https://en.wikipedia.org/wiki/Continuation}} --- ``the meaning of the rest of the program''.

Начальным толчком к размышлениям стал язык Algol 60, имевший нетривиальный механизм меток и прыжков.
Проблемой была как имплементация семантики, так и её денотационное описание вместе с трансляцией в лямбда-исчисление.
Действительно, как математически описать \texttt{goto}?
В каком домене искать семантику таких программ?
Как написать определяющий интерпретатор, отправляющий программу в этот домен?
Решением стала возможность сослаться на семантику остатка программы, продолжение, в определённой точке (например, на метке).

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

\subsection{Концепция продолжений}

Рассмотрим семантику выражения с операционной точки зрения, как последовательность шагов переписывания (см.\ \ref{subsubsec:semantics}).
Если внимательно рассмотреть каждый шаг, то мы обнаружим, что он состоит из двух этапов: поиска подвыражения (редекса), в котором можно сделать элементарный шаг вычислений, выполнение этого шага, и так далее\footnote{На самом деле вычислениям с продолжениями учат в начальных классах, когда рассказывают про вычисление выражений ``по действиям''.}.
Во время поиска редекса, выражение разбивается на две части (см.~\ref{fig:basic-continuation}):
\begin{itemize}
    \item Фокус --- подвыражение в котором ищем редекс;
    \item Продолжение --- остаток выражения с ``дыркой'', обозначающий место, куда нужно подставить результат шага вычислений.
\end{itemize}

\begin{figure}
    \centering
    \includegraphics[width=0.35\textwidth]{figs/cont-expr}
    \caption{Выражение разделяется на фокус (красный) и продолжение (синее), когда в фокусе удалось сделать шаг, они объединяются в новое выражение, для которого процесс повторяется.}
    \label{fig:basic-continuation}
\end{figure}

Как правило, продолжения существуют вне пользовательского кода как состояние интерпретатора, которому в каждый следующий момент времени нужно помнить, какой код и в каком состоянии исполнять дальше.
Однако, языки предоставляют пользователям множество конструкций, позволяющих управлять продолжениями (см.\ \ref{fig:exit-exceptions}):
\begin{itemize}
    \item Функция \mintinline{kotlin}|exit| выбрасывает продолжение программы целиком;
    \item Конструкция \mintinline{kotlin}|try-catch| позволяет выбросить часть продолжения до места поимки исключения и исполнить оставшееся;
    \item Конструкция \mintinline{kotlin}|return| позволяет восстановить исполнение в месте, где функция была вызвана;
    \item Конструкции \mintinline{kotlin}|break| и \mintinline{kotlin}|continue| восстанавливают продолжение после цикла и до\ldots
\end{itemize}

\begin{figure}
    \centering
    \begin{subfigure}[ht]{0.29\linewidth}
        \includegraphics[width=1\textwidth]{figs/cont-exit}
    \end{subfigure}
    \begin{subfigure}[ht]{0.7\linewidth}
        \includegraphics[width=1\textwidth]{figs/cont-try-catch}
    \end{subfigure}
    \caption{Конструкция \mintinline{kotlin}|exit| выбрасывает продолжение и программа останавливается, в то время как \mintinline{kotlin}{throw} выбрасывает лишь часть продолжения до ближайшего \mintinline{kotlin}{try-catch}.}
    \label{fig:exit-exceptions}
\end{figure}

\subsubsection{Reduction semantics}

Стиль задания операционной семантики через описание поиска примитивных (``\vocab{головных}'') редексов и их редукций называют \vocab{семантикой редукционных контекстов (reduction semantics)}\footnote{\url{https://en.wikipedia.org/wiki/Operational_semantics}}.
Как обычно, следуя Hutton's Razor, рассмотрим интерпретацию маленького простого язычка с вычитанием (несимметричная операция для проверки реализации):
\begin{minted}{haskell}
    data Expr = Const Int | Diff Expr Expr
\end{minted}

Для начала нам нужно определить синтаксис продолжений, ``выражений с дыркой''.
То есть с технической точки зрения продолжение --- это структура данных, содержащая всю необходимую информацию, чтобы продолжить исполнение (здесь~--- только остаток выражения):
\begin{minted}{haskell}
    data K
      = Hole         -- дырка ?$\boxempty$?
      | LDiff K Expr -- фокус пошел в левое подвыражение, запомнили правое
      | RDiff Int K  -- посчитали левое, фокус пошел вправо
\end{minted}

Зададим операцию разбиения выражения на фокус и продолжение:
\begin{minted}{haskell}
    split :: Expr -> (Expr, K)
    split e = case e of
      Const _ -> (e, Hole)
      Diff (Const _) (Const _) -> (e, Hole) -- примитивный редекс
      Diff (Const l) r ->                   -- левое подвыражение уже посчитано
        let (focus, k) = split r in         -- ищем редекс в правом
        (focus, RDiff l k)
      Diff l r ->                           -- ничего ещё не посчитано
        let (focus, k) = split l in         -- начинам с поиска редекса слева
        (focus, LDiff k r)

    ghci> split (Diff (Diff (Const 1) (Const 2)) (Const 3)) -- (1 - 2) - 3
    (Diff (Const 1) (Const 2), LDiff Hole (Const 3)) -- (1 - 2, ?$\boxempty$? - 3)
\end{minted}

Шаг примитивной редукции умеет только вычитать числа:
\begin{minted}{haskell}
    headReduction :: Expr -> Expr
    headReduction = \case
      Diff (Const l) (Const r) -> Const (l - r)
      e -> e
\end{minted}

После шага примитивной редукции нам понадобится подставить результат обратно в продолжение, чтобы из ``выражения с дыркой'' получить полноценное выражение, которое можно продолжить редуцировать:
\begin{minted}{haskell}
    plugIn :: Expr -> K -> Expr
    plugIn e k = case k of
      Hole -> e
      LDiff k' r -> Diff (e `plugIn` k') r
      RDiff l k' -> Diff (Const l) (e `plugIn` k')
\end{minted}
Как правило, подстановку терма $t$ в продолжение $E$ обозначают как $E[t]$.

Теперь мы можем определить полноценный шаг:
\begin{minted}{haskell}
    transition :: Expr -> Expr
    transition e =
      let (focus, k) = split e in    -- разбиваем на фокус и контекст
      headReduction focus `plugIn` k -- делаем вычисление в фокусе и подставляем
\end{minted}

Тода операционная семантика это развёртка списка промежуточных выражений:
\begin{minted}{haskell}
    eval :: Expr -> [Expr]
    eval = List.unfoldr \prev ->
      let next = transition prev in
      if prev == next then Nothing else Just (next, next)
\end{minted}

Можно заметить, что \texttt{split} и \texttt{plugIn} однозначно определяется по синтаксису продолжений и виду главных редукций, а \texttt{transition} и \texttt{eval} одинаковы для произвольного языка.
Поэтому семантику редукционных контекстов обычно задают как синтаксис продолжений, перечень главных редукций и единственное правило вывода --- шаг в контексте:\footnote{$\ominus$ тут обозначает синтаксический минус (ноду в дереве).}
%! suppress = EscapeAmpersand
\[
    \begin{array}{lrl}
        \text{Values}             & v & \Coloneqq \mathbb{Z}                                       \\
        \text{Terms}              & t & \Coloneqq v ~|~ t \ominus t                                \\
        \text{Evaluation context} & E & \Coloneqq \square ~|~ E \ominus t ~|~ \mathbb{Z} \ominus E \\
        \text{(diff)}             &   & v_1 \ominus v_2 \longrightarrow v_1 - v_2                  \\
        \text{step}               &   & \infer{E[t] \longrightarrow E[t']}{t \longrightarrow t'}
    \end{array}
\]

Существует стандартный инструмент PLT Redex\footnote{\url{https://redex.racket-lang.org/}} для описания и тестирования семантики в стиле редукционных контекстов.

\subsubsection{Continuation semantics} \label{subsubsec:continuation-semantics}

Запишем денотационную семантику нашего языка:
\begin{minted}{haskell}
    evalDirect :: Expr -> Int
    evalDirect = \case
      Const n -> n
      Diff l r -> evalDirect l - evalDirect r
\end{minted}

Перепишем денотационную семантику в стиле с явными продолжениями.
Но сначала поработаем с типом \mintinline{haskell}{K} и упростим работу с ним:
\begin{minted}{haskell}
    data K = Hole | LDiff K Expr | RDiff Int K
    -- ?$K = 1 + (K \times Expr) + (Int \times K) = 1 + (Expr + Int) \times K$?
    data Frame = LDiff Expr | RDiff Int
    type K = [Frame]
\end{minted}
Получили представление продолжения как стека фреймов.

Денотационную семантику будем записывать для домена \mintinline{haskell}{K -> Int}.
Такая разновидность денотационной семантики с явным представлением смысла остатка программы (в виде \mintinline{haskell}{K}) иногда называют \vocab{continuation semantics}.
А соответствующий стиль программирования с передачей продолжений --- \vocab{continuation passing style (CPS)}.

В нашем continuation semantics будет выглядеть как пара взаимно-рекурсивных функций:
\begin{minted}{haskell}
    evalK :: Expr -> K -> Int
    evalK e k = case e of
      Const n -> k `appK` n             -- выполняем остаток программы
      Diff l r -> evalK l (LDiff r : k) -- запоминаем дальше вычислить правое

    appK :: K -> Int -> Int
    appK k result = case k of
      [] -> result                                -- дальше делать нечего
      LDiff r : k' -> evalK r (RDiff result : k') -- идем вычислять вправо
      RDiff l' : k' -> k' `appK` (l' - result)    -- продолжаем на результате
\end{minted}
Тут мы снова спускаемся по выражению в поисках примитивного редекса (тут~--- константы), попутно запоминая, что нужно будет сделать после.

%\begin{figure}
%    \centering
%    \begin{tabular}{|c|c|}
%        \hline
%        Фокус         & Продолжение           \\
%        \hline
%        $(5 - 2) - 1$ & $\boxempty$           \\
%        $5 - 2$       & $\boxempty - 1$       \\
%        $5$           & $(\boxempty - 2) - 1$ \\
%        $2$           & $(5 - \boxempty) - 1$ \\
%        $2$           & $(5 - \boxempty) - 1$ \\
%        \hline
%    \end{tabular}
%\end{figure}

Первая рекурсивная реализация \texttt{evalDirect} не заботилась о продолжениях.
Однако, продолжения --- это неотъемлемая часть процесса вычисления, вычислителю нужно знать, что делать дальше в каждый момент.
На самом деле \texttt{evalDirect} лишь делегирует работу с продолжениями определяемого языка мета-языку, но каким образом?
Заметьте, что полученная в итоге реализация \texttt{evalK} хвостово-рекурсивна, а значит, может быть скомпилирована в цикл, не потребляющий стек вызовов. При этом \mintinline{haskell}{K} и есть стек.
Таким образом, в первом случае мы делали рекурсивные вызовы и продолжение аллоцировалось на (аппаратном) стеке мета-языка, а во втором случае мы самостоятельно аллоцируем стек в куче.

В случае, если стек мета-языка реализован поверх аппаратного, есть риск ошибки его переполнения.
Чтобы этого избежать, используется техника \vocab{trampolining}, которая как раз состоит в ручной аллокации продолжения в куче~\cite{ganz1999trampolined, bjarnarson2012stackless}.

Подобно тому как тип контекста зиппера можно вычислить как производную алгебраического представления соответствующего типа~\cite{huet1997zipper, mcbride2001derivative, abbott2003derivatives}, так можно вычислить тип продолжения свёртки~\cite{mcbride2008clowns}.

\subsubsection{Продолжения первого класса} \label{subsubsec:first-class-cont}

В примерах выше конструкции языка управляют продолжениями неявно (см.\ рис.\ \ref{fig:exit-exceptions}).
Однако, иногда вводят операторы, позволяющие явно оперировать продолжениями.
С их помощью можно реализовать как возможности манипуляции потоком управления вроде генераторов и корутин\footnote{\url{https://en.wikibooks.org/wiki/Haskell/Continuation_passing_style\#Example:_coroutines}}\footnote{\url{https://kotlinlang.org/api/core/kotlin-stdlib/kotlin.coroutines/suspend-coroutine.html}}, так и все остальные эффекты вроде состояния (см.\ далее\ \ref{sec:effects}).

\vocab{Продолжения первого класса (first-class continuations)} --- продолжения, которые представимы в программе в виде значений.
Учитывая, что продолжение имеет вакантное место ещё не вычисленного подвыражения, продолжения первого класса представляются функциями первого класса.

Чтобы получить в коде продолжение первого класса, нужно либо написать код в CPS, либо воспользоваться встроенным в язык оператором; таких операторов придумано великое множество~\cite[приложение A]{hillerstrom2022foundations}.
Например, $J$, \texttt{escape}~\cite{reynolds1972definitional}, \texttt{call/cc}\ldots

Для примера реализуем в языке операцию \texttt{Cont}, позволяющую захватить текущее продолжение.
Он будет принимать пользовательскую функцию и передавать в неё текущее продолжение от себя и до конца программы:
\[
    E[cont\ap f] \longrightarrow f\ap (\lambda x\ldotp E[x])
\]

Сначала расширим язык лямбда-исчислением:
\begin{minted}{haskell}
    data Expr
      = Const Int | Diff Expr Expr
      | Var String | Lam String Expr | App Expr Expr

    data Frame
      = LDiff Expr | RDiff Value
      | LApp Expr | RApp Value
      | SetEnv Env -- после исполнения замыкания возвращаем текущее окружение
\end{minted}

Реализация интерпретатора довольно прямолинейна.
Единственное, сейчас остаток программы представлен в виде линейного списка, который фактически обходится в цикле последовательно.
Нужно не забыть после исполнения тела замыкания восстановить изначальное окружение для исполнения продолжения:\footnote{Для удобства буддем передавать окружение неявным параметром.}
\begin{minted}[escapeinside=##]{haskell}
    evalK :: (?env :: Env) => Expr -> K -> Value
    evalK e k = case e of
      Const n -> k `appK` Number n
      Diff l r -> evalK l (LDiff r : k)
      Var name -> k `appK` (?env ! name)
      Lam name body -> k `appK` Closure name ?env body
      App f arg -> evalK f (LApp arg : k)

    appK :: (?env :: Env) => K -> Value -> Value
    appK k result = case k of
      [] -> result
      LDiff r : k' -> evalK r (RDiff result : k')
      RDiff l' : k' -> k' `appK` Number (unwrapNumber l' - unwrapNumber result)
      LApp arg : k' -> evalK arg (RApp result : k')
      RApp f : k' -> case f of
        Closure name env body ->
          let currEnv = ?env in
          let ?env = Map.insert name result env in
          evalK body (SetEnv currEnv : k')
        K env k'' ->
          let currEnv = ?env in
          let ?env = env in
          (k'' ++ SetEnv currEnv : k') `appK` result
        other -> error $ "Expected callable, got " <> show other
      SetEnv env : k' -> let ?env = env in k' `appK` result
      where
        unwrapNumber = \case
          Number n -> n
          other -> error $ "Expected number, got " <> show other
\end{minted}

Наконец, реализуем оператор \texttt{cont}:
\begin{minted}[escapeinside=##]{haskell}
    data Expr = ... | Cont Expr
    data Frame = ... | ContFrame

    evalK e k = case e of
       ...
       Cont f -> evalK f (ContFrame : k)

    appK k result = case k of
       ...
       ContFrame : k' -> [RApp result] `appK` K ?env k' -- переиспользуем ветку RApp
\end{minted}

Рассмотрим несколько примеров (обозначим \mintinline{haskell}{contLam name body = Cont (Lam name body)}, \mintinline{haskell}{(-.) = Diff}, \mintinline{haskell}{c = Const}, \mintinline{haskell}{v = Var} и \mintinline{haskell}{(@) = App}):
\begin{itemize}
    \item \mintinline{haskell}{c 10 -. contLam "k" (c 1)} --- выбросить продолжение и вернуть 1 ($k = 10 - \boxempty$);
    \item \mintinline{haskell}{c 10 -. contLam "k" (v "k" @ c 1)} --- $\step k\ap 1 \step 10 - 1 \step 9$;
    \item \mintinline{haskell}{c 10 -. contLam "k" (v "k" @ c 1 -. c 2)} --- $\step k \ap 1 - 2 \step 9 - 2 \step 7$;
    \item \mintinline{haskell}{c 10 -. contLam "k" (v "k" @ c 1 -. v "k" @ c 2)} --- $\step k \ap 1 - k \ap 2 \step 9 - 8 \step 1$.
\end{itemize}

Таким образом, мы получили язык, который позволяет пользователю в произвольном месте программы получить текущее продолжение в виде функции.

Возможность получить продолжение первого класса почти не предоставляется промышленными языками, так как это довольно опасный инструмент.
Действительно, если пользователь не вызовет продолжение, может не произойти закрытия ресурсов.
Если вызовет несколько раз, снова может произойти как некорректная работа с ресурсами, так и порча изменяемой памяти (продолжения, которые можно безопасно вызывать много раз называют \vocab{multi-shot}).
Подобные поведения можно исключать специальной обработкой таких ситуаций~\cite{muhcu2025multiple}, проверками времени компиляции (например, с помощью линейных типов) или времени исполнения.
Сейчас с активными исследованиями о внедрении хендлеров эффектов (см.\ далее\ \ref{sec:effects}) продолжения первого класса могут получить новый шанс.

\subsection{Продолжения своими руками} \label{subsec:functional-cps}

% todo higher-order CPS

Рассмотрим, как выглядит CPS в обычном коде, а не в контексте deep embedding.
Для этого мы, во-первых, перейдём к shallow embedding и будем сразу строить элементы целевого домена.
А во-вторых, рефункционализируем продолжения \mintinline{haskell}{K} и обобщим: вместо \mintinline{haskell}{K -> Int} будем использовать \mintinline{haskell}{forall r . (a -> r) -> r}, где \texttt{a -> r}~--- функциональное представление продолжения.

Такой CPS эксплуатирует следующий изоморфизм:
\begin{minted}{haskell}
    to :: a -> (forall r . (a -> r) -> r)
    to x k = k x

    from :: (forall r . (a -> r) -> r) -> a
    from comp = comp id
\end{minted}
Иначе говоря, вместо того, чтобы предоставить значение типа \texttt{a}, можно спросить у вызывающей стороны, как она собирается с этим значением работать \texttt{a -> r}, сделать это самостоятельно, и вернуть вызывающей стороне \texttt{r}.

Прикладным программистам этот изоморфизм знаком по технике использования callback'ов.
Теоретикам же известно, что он является частным случаем леммы Йонеды~\cite{hinze2010reason}.
Сравните CPS с интансом этой леммы в теории предпорядка (выше мы считали \texttt{a = Unit; b = a}):
\begin{gather*}
    a\to b \iso \forall r\ldotp (b\to r)\to (a\to r) \\
    a \le b \iff \forall r\ldotp (b \le r) \Rightarrow (a \le r)
\end{gather*}

Например, мы можем переписать факториал в CPS.
Заметьте, что код имеет доступ к продолжению первого класса (однако, пока никак нетривиально не использует его), при этом снова является хвостово-рекурсивным.
\begin{minted}{haskell}
    facCps :: Int -> (forall r . (Int -> r) -> r)
    facCps n k
      | n <= 1 = k 1
      | otherwise = facCps (n - 1) \res -> k (n * res)

    facCps 3 id ?$\step$? facCps 2 \res -> id (3 * res)
    ?$\step$? facCps 1 \res -> id (3 * (2 * res)) ?$\step$? id (3 * (2 * 1)) ?$\step$? 6
\end{minted}

\begin{task}
    Сколько функция \mintinline{haskell}|facCps| потребляет стековой памяти?
\end{task}

\subsubsection{Дефункционализация и аккумуляторы} \label{subsubsec:defunctionalization-cont}

Дефункционализируем продолжения в \texttt{facCps}.
Мы используем две функции высших порядков, \texttt{id} и \mintinline{haskell}{\res -> k (n * res)}, они дают нам два конструктора:
\begin{minted}{haskell}
    data K = Id | Times Int K
    -- ?$\iso$?
    type K = [Int]

    runK :: K -> Int
    runK = product

    facCps :: Int -> K -> Int
    facCps n k
      | n <= 1 = runK k
      | otherwise = facCps (n - 1) (snoc k n)

    facCps 3 [] ?$\step$? facCps 2 [3] ?$\step$? facCps 1 [3, 2] ?$\step$? runK [3, 2] ?$\step$? 3 * (2 * 1)
\end{minted}

Мы снова получили представление продолжения в виде стека фреймов.
А значит, интерпретатор \texttt{evalK} полученный нами ранее (\ref{subsubsec:continuation-semantics}) является CPS версией обычного интерпретатора, только с дефункционализированными продолжениями (они удобны для отладки~--- их можно распечатать, в отличие от функций Haskell).
Если расширить тот наш язык и написать на нём факториал, а потом сделать fusion или рефункционализацию (\ref{subsubsec:deforestation-fusion}) дерева программы и дерева продолжения, мы получим текущую реализацию факториала.
И в целом между различными стилями реализаций семантик можно построить соответствие (см.\ рис.\ \ref{fig:semantics-diagram}).

\begin{figure}
    \centering
    \includegraphics[width=0.6\textwidth]{figs/semantics-diagram}
    \caption{Связь между семантиками в различных стилях~\cite{danvy2008defunctionalized}.}
    \label{fig:semantics-diagram}
\end{figure}

Этой техникой можно пользоваться и в более сложных случаях, чтобы легко получать хвостово-рекурсивные (итеративные) реализации\footnote{\url{https://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html}}~\cite{gibbons2021continuation}\footnote{\href{https://youtu.be/8gnhaE2nmQ0?si=pEJX4jQteYmy7ZZn}{(youtube) Jeremy Gibbons - Continuation-passing style, defunctionalization, and associativity.}}.
В целом CPS и дефункционализация~--- это богатый источник различных рефакторингов (см.\ рис.\ \ref{fig:cps-refactorings}).

\begin{figure}
    \centering
    \includegraphics[width=0.8\textwidth]{figs/cps-defun-refactorings}
    \caption{Трансформации кода, основанные на CPS и де(ре)функционализации~\cite{danvy2006analytical}.}
    \label{fig:cps-refactorings}
\end{figure}

Теперь заметим, что операция умножения ассоциативна, а значит, можно \texttt{snoc} заменить на умножение, а продолжение представить одним числом.
Получим привычную реализацию факториала с аккумулятором:
\begin{minted}{haskell}
    facAcc :: Int -> Int -> Int
    facAcc n acc
      | n <= 1 = acc
      | otherwise = facAcc (n - 1) (acc * n)

    facAcc 3 1 ?$\step$? facAcc 2 (1 * 3) ?$\step$? facAcc 1 ((1 * 3) * 2) ?$\step$? (1 * 3) * 2 ?$\step$? 6
\end{minted}

Также, можно фреймы представить в виде эндоморфизмов и в качестве ассоциативной операции использовать композицию функций~\cite{ploeg2014reflection}\footnote{\url{https://wiki.haskell.org/Difference_list}}.

% todo можно ли не пользоваться тем, что единица нейтральная

\subsubsection{\mintinline{haskell}{Monad Cont}} \label{subsubsec:monad-cont}

Из-за CPS код потерял привычную структуру, при которой функции напрямую возвращают свои результаты (i.e. \vocab{direct style}).
При наличии большого количества вызовов трансформированных функций, код становится плохо читаемым (проблема известна как \vocab{callback hell}):
\begin{minted}{haskell}
    fibCps :: Int -> (forall r . (Int -> r) -> r)
    fibCps n k = if n <= 2 then k 1 else
      fibCps (n - 1) \res1 ->
      fibCps (n - 2) \res2 ->
      k (res1 + res2)
\end{minted}

Домен \mintinline{haskell}{(a -> r) -> r} можно сделать монадой и восстановить direct style код внутри \mintinline{haskell}{do}-нотации.
Заведём \mintinline{haskell}|newtype| обёртку для объявления инстансов:
\begin{minted}{haskell}
    newtype Cont r a = Cont { runCont :: (a -> r) -> r }
\end{minted}

Функтор добавляет пост-процессинг результату перед передачей в продолжение:
\begin{minted}{haskell}
    instance Functor (Cont r) where
      -- fmap :: (a -> b) -> ((a -> r) -> r) -> ((b -> r) -> r)
      fmap f (Cont comp) = Cont \k -> comp (k . f)
\end{minted}

Аппликатив просто передаёт значение продолжению:
\begin{minted}{haskell}
    instance Applicative (Cont r) where
      pure x = Cont \k -> k x
      (<*>) = ap
\end{minted}

Можно заметить, что монадическое связывание вторым аргументом тоже принимает продолжение, но ``маленькое'', до конца \mintinline{haskell}|do|-блока.
Таким образом, смысл реализации монадического связывания для \mintinline{haskell}{Cont}~--- это композиция ``маленького'' продолжения с ``большим'' продолжением, передаваемым снаружи:
\begin{minted}{haskell}
    instance Monad (Cont r) where
      (>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b
      Cont comp >>= k = Cont \k' -> comp \x -> runCont (k x) k'
\end{minted}

% todo примеры, какое продолжение большое, какое маленькое

Теперь мы можем писать линейный код, а монадическая машинерия сама конструирует продолжения и подкладывает в предыдущие вычисления:
\begin{minted}{haskell}
    fibCont :: Int -> Cont r Int
    fibCont n = if n <= 2 then pure 1 else do
      res1 <- fibCont (n - 1)
      res2 <- fibCont (n - 2)
      pure (res1 + res2)
\end{minted}

\begin{task}
    Оборвите вычисление, если \texttt{res1} больше \texttt{50}.
\end{task}

\begin{task}
    Оборвите вычисление как только общий результат стал больше 50.
\end{task}

Монада \mintinline{haskell}{Cont} даёт реализацию встроенного языка, в котором можно получить продолжение вычисления:
\begin{minted}{haskell}
    Cont :: ((a -> r) -> r) -> Cont r a
\end{minted}

Прикладным программистам такая техника написания CPS кода через монады знакома в виде концепций \mintinline{kotlin}{Future}/\mintinline{kotlin}{Promise}\footnote{\url{https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise}}\footnote{\url{https://github.com/promises-aplus/promises-spec/issues/94}}. % todo cite Barbara Liskov and Liuba Shrira. 1988. Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems. ACM SIGPLAN Notices   23, 7 (1988), 260–267.

\subsubsection{\texttt{call/cc}}

Самым известным классическим оператором, который использовали в Scheme для получения продолжений первого класса, является \vocab{\texttt{call/cc} (call with current continuation)}\footnote{\url{https://en.wikipedia.org/wiki/Call-with-current-continuation}}\footnote{\url{https://en.wikibooks.org/wiki/Haskell/Continuation_passing_style\#callCC}}.
Предоставляемое продолжение является \vocab{неограниченным (undelimited/abortive)}, так как оно содержит ``конец программы'' --- никакой код не будет исполняться после его вызова.
Неограниченные продолжения де-факто не совсем являются функциями, так как они не возвращают результата (он уже ``beyond the grave''). Следовательно, они также не композируются; точно так же странно композировать \texttt{abort} с \texttt{exit}\footnote{\url{https://okmij.org/ftp/continuations/undelimited.html}}\footnote{\url{https://okmij.org/ftp/continuations/against-callcc.html}}.
Они скорее являются ко-значениями: пока часть программы выполняется, они ожидают её результата~\cite{curien2000duality}.

Давайте сэмулируем \texttt{call/cc} в монаде \mintinline{haskell}{Cont}.
Захватить всё продолжение программы у нас не выйдет, так как оно собирается только в рамках \mintinline{haskell}{Cont}, но мы можем проигнорировать продолжение вызова захваченного продолжения:
\begin{minted}{haskell}
    callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
    callCC f = Cont \k -> runCont (f \x -> Cont \_ -> k x) k

    foo :: Int -> Cont r String
    foo x = callCC \k -> do
      let y = x ^ 2 + 3
      when (y > 20) $ k "over twenty" -- throws next line away
      pure (show $ y - 4)
\end{minted}

\subsection{Разграниченные продолжения (delimited continuations)} \label{subsec:delimited-cont}

В современной практике, как правило, используют продолжения не до конца программы, а только до определённой точки.
Их называют \vocab{ограниченными} или \vocab{разграниченными продолжениями}, \vocab{delimited} или \vocab{composable continuations}, \vocab{subcontinuations}\footnote{\url{https://www.cl.cam.ac.uk/teaching/2324/R277/handout-delimited-continuations.pdf}}\footnote{\href{https://youtu.be/TE48LsgVlIU?si=cBdUCzYwYWpwPkkh}{(youtube)  Keynote: Delimited Continuations, Demystified by Alexis King | Lambda Days 2023}.}.

Конструкции для работы с такими продолжениями парные: вводится оператор, ограничивающий текущее продолжение (мб имеющий метку); а также оператор захвата фрагмента текущего продолжения (мб до конкретного ограничителя с определённой меткой).
Таких операторов придумано много~\cite[приложение А]{hillerstrom2022foundations}, но они более-менее все сводятся друг к другу.

Например, работа с исключениями подразумевает использование двух конструкций: продолжение ограничивается с помощью \mintinline{kotlin}|try-catch|, а \mintinline{kotlin}|throw| выкидывает соответствующее частичное продолжение, не захватывая его (см.\ рис. \ref{fig:exit-exceptions}):
\[
    E_1[try\{E_2[throw(v)]\}catch(x) \{t\}] \to E_1[\subst{t}{x}{v}]
\]

Мы же рассмотрим универсальные операторы из~\cite{dyvbig2007monadic}.
Работа вводит следующий набор синтаксических конструкций (рис.~\ref{fig:prompt-syntax}) для работы с ограниченными продолжениями в дополнение к чистому call-by-value лямбда-исчислению:
\begin{itemize}
    \item $newPrompt$\footnote{Исторически в лиспах неограниченные продолжения были ограничены лишь REPL, отсюда название ограничений --- ``prompt''.} --- создаёт свежий идентификатор (метку) ограничения;
    \item $pushPrompt \ap p \ap e$ --- устанавливает ограничение с меткой $p$ и исполняет выражение $e$;
    \item $withSubCont\ap p\ap f$ --- захватывает частичное продолжение до ограничения с меткой $p$ и передаёт в функцию $f$, возвращает результат $f$ (рис.~\ref{fig:push-prompt});
    \item $pushSubCont\ap k \ap v$ --- исполняет композицию текущего продолжения и $k$ на значении $v$.
\end{itemize}

\begin{figure}
    \centering
    \includegraphics[width=0.75\linewidth]{figs/prompt-syntax}
    \caption{Синтаксис $\lambda$-исчисления с примитивами для работы с продолжениями.}
    \label{fig:prompt-syntax}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.7\linewidth]{figs/push-prompt}
    \caption{Пример работы \texttt{withSubCont}.}
    \label{fig:push-prompt}
\end{figure}

%\begin{figure}
%    \centering
%    \includegraphics[width=0.8\textwidth]{figs/dc-operational}
%    \caption{Операционная семантика.}
%    \label{fig:dc-operational}
%\end{figure}

Операторы ограниченных продолжений легко понять как \vocab{resumable exceptions}, исключения, которые можно поймать, а программу возобновить с того места, где исключение было выброшено (с некоторым значением).
Необычно то, что классические операторы ограниченных продолжений принимают код, работающий с частичным продолжением в месте ``кидания исключения'', а не в месте ``поимки''.
То есть блок обработки пишется не с \mintinline{kotlin}|catch|, а с \mintinline{kotlin}|throw|:

\begin{gather*}
    E_1[pushPrompt \ap p \ap \{E_2[withSubCont \ap p \ap f]\}] \to E_1[f \ap E_2]
    \\
    E_1[try\{E_2[throw \ap v]\} catch(x, k) \{t\}] \to E_1[\subst{\subst{t}{k}{\lambda y\ldotp E_2[y]}}{x}{v}]
\end{gather*}

\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{figs/dc-example}
    \caption{Пример выражения (результат --- $9$).}
    \label{fig:dc-example}
\end{figure}

\begin{task}
    Поредуцируйте пример рис.~\ref{fig:dc-example}.
\end{task}

\subsubsection{Реализация операторов}

Расширим язык\ \ref{subsubsec:first-class-cont} рассмотренными операторами для работы с ограниченными.
Для простоты вместо свежих меток промптов будем использовать имена, а вместо \texttt{pushSubCont} обычную аппликацию:
\begin{minted}{haskell}
    data Expr = ...| PushPrompt String Expr | WithSubCont String Expr
    data Frame = ... | PushPromptFrame String | WithSubContFrame String
\end{minted}

Поиск редексов расширяется очевидным образом:
\begin{minted}[escapeinside=##]{haskell}
    evalK :: (?env :: Env) => Expr -> K -> Value
    evalK e k = case e of
      -- ...
      PushPrompt promptName body -> evalK body (PushPromptFrame promptName : k)
      WithSubCont promptName f -> evalK f (WithSubContFrame promptName : k)
\end{minted}

Вся задача \texttt{PushPrompt} --- это застрять в продолжении в виде \texttt{PushPromptFrame}, но когда до него доходит исполнение, он просто игнорируется:
\begin{minted}[escapeinside=##]{haskell}
    appK :: (?env :: Env) => K -> Value -> Value
    appK k result = case k of
      -- ...
      PushPromptFrame _ : k' -> k' `appK` result
\end{minted}

Чтобы захватить фрагмент продолжения, нам нужна операция, которая найдёт первый промпт с соответствующим именем в продолжении и вернёт \vocab{subcontinuation} --- до этого промпта и \vocab{metacontinuation} --- после:
\begin{minted}[escapeinside=##]{haskell}
    splitByPrompt :: K -> String -> (K, K)
    splitByPrompt k targetPromptName = go [] k
      where
        go _ [] =  error $ "Prompt " ++ targetPromptName ++ " not found"
        go subcont (PushPromptFrame promptName : metacont)
          | promptName == targetPromptName = (subcont, metacont)
        go subcont (frame : metacont) = go (subcont ++ [frame]) metacont
\end{minted}

Теперь \texttt{WithSubCont} должен просто применить пользовательскую функцию к subcontinuation, но при этом не забыть дальше исполнить metacontinuation:
\begin{minted}[escapeinside=##]{haskell}
    appK :: (?env :: Env) => K -> Value -> Value
    appK k result = case k of
      -- ...
      WithSubContFrame promptName : k' ->
        let (subcont, metacont) = k' `splitByPrompt` promptName in
        (RApp result : metacont) `appK` K ?env subcont
\end{minted}

\begin{task}
    Поредуцируйте следующий пример:
    \begin{minted}[escapeinside=##]{haskell}
        exampleDelimited = let ?env = Map.empty in flip evalK [] $
          c 10 -. PushPrompt "p"
            (c 5 -. WithSubCont "p"
              (lam "k" $ v "k" @ c 1 -. v "k" @ c 3))
    \end{minted}
\end{task}

Многие классические операторы, например, \texttt{shift/reset}, \texttt{prompt/control} и т.д., можно получить, оставив фрейм промпта в subcontinuation или в metacontinuation в реализации \texttt{splitByPrompt}~\cite{dyvbig2007monadic}.

\subsubsection{В \mintinline{haskell}{Monad Cont}}

% todo Monads and composable continuations by Phill Wadler

Для примера реализуем два классических оператора для работы с ограниченными продолжениями --- \textbf{shift-reset}.
Воспользуемся продолжениями, собираемыми монадой \mintinline{kotlin}|Cont|.
\texttt{shift} просто захватывает текущее продолжение и передаёт его в пользовательское вычисление подобно \texttt{cont}:
\begin{minted}{haskell}
    shift :: ((a -> r) -> Cont r r) -> Cont r a
    shift f = Cont \k -> runCont (f k) id
\end{minted}
\texttt{reset} же в качестве продолжения вычислению-аргументу передаёт \texttt{id}, тем самым это вычисление не имеет доступа к продолжению после \texttt{reset} (в то время как продолжение самого Haskell запоминает, что после \texttt{comp} нужно исполнить \texttt{k}):
\begin{minted}{haskell}
    reset :: Cont a a -> Cont r a
    reset comp = Cont \k -> k (runCont comp id)
\end{minted}

\begin{task}
    Каким будет результат исполнения следующей функции:
    \begin{minted}{haskell}
        exampleShiftReset = flip runCont id $
          (1 +) <$> reset ((2 +) <$> shift \k -> pure (k 3 + k 5))
    \end{minted}
\end{task}

\subsection{Приложения продолжений} \label{subsec:cont-applications}

Продолжения полезны для понимания смысла программ, которые мы пишем каждый день (см.\ \ref{foot:the-lost-art-of-denotations}).
Кроме того, как мы увидим в этой главе, продолжения первого класса можно использовать как средство построения выразительных встроенных языков.

\subsubsection{Всё через продолжения} \label{subsubsec:god-cont}

Реализуем ряд полезных встроенных языков с помощью продолжений первого класса.
Чтобы получить доступ к продолжениям, воспользуемся shallow-embedded языком \mintinline{haskell}{Cont}\footnote{\url{https://blog.poisson.chat/posts/2019-10-26-reasonable-continuations.html}}.
Таким образом, будем работать с башней языков Haskell, \mintinline{haskell}{Cont}, X, где X --- рассматриваемый встроенный язык.

Начнём с тривиального встроенного императивного языка:
\begin{minted}{haskell}
    runIdentityC :: (forall r . Cont r a) -> a
    runIdentityC comp = runCont comp id

    exampleIdentity :: Int
    exampleIdentity = runIdentityC do
      x <- pure 4
      y <- pure 5
      pure (x + y)
\end{minted}

Реализуем язык с исключениями.
Для этого модифицируем первый типовый параметр \mintinline{haskell}{Cont}, \vocab{answer (response) type}\footnote{\url{https://wiki.haskell.org/Cont_computations_as_question-answering_boxes}}.
Функция \texttt{abort} игнорирует продолжение программы до \texttt{runExn}, которая завершает продолжение оборачиванием успешного результата в \mintinline{haskell}{Just}:
\begin{minted}{haskell}
    abort :: Cont (Maybe r) a
    abort = Cont $ const Nothing

    runExn :: (forall r . Cont (Maybe r) a) -> Maybe a
    runExn comp = runCont comp Just

    exampleExn :: Int -> Maybe Int
    exampleExn n = runExn do
      when (n < 0) abort
      pure (n + 1)
\end{minted}
Обратите внимание, что семантика операции обрыва вычисления полностью сосредоточена в функции \texttt{abort}, в то время как в \mintinline{haskell}{Monad Maybe} соответствующая функция бы отвечала лишь за конструирование элемента домена, а уже монадическое связывание~--- за работу с продолжениями.
Имея доступ к продолжениям первого класса, нам уже не нужно реализовывать монадическое связывание вручную.
Говорят, что для произвольного \texttt{m}, \mintinline{haskell}{Cont (m r) a} --- ``бесплатная'' реализация монады\footnote{\url{https://hackage.haskell.org/package/kan-extensions-5.2/docs/Control-Monad-Codensity.html}}.

Реализация работы с ошибками через возвращение специального результата (\mintinline{haskell}{Either} в Haskell, \mintinline{rust}{Result} в Rust, \mintinline{go}{nil} в Go\ldots) имеет монадическую семантику (условные ветвления на каждом выбрасывают только часть продолжения), в то время как полноценный механизм исключений имеет доступ ко всему ограниченному продолжению до соответствующего блока \mintinline{kotlin}{try-catch}, что напоминает нашу текущую реализацию.
С точки зрения количества синтаксического шума на уровне исходного кода, вариант с исключениями явно предпочтительнее, а вопрос типизации исключений мы рассмотрим далее (см.\ \ref{sec:effect-systems}).
С точки зрения производительности всё не так очевидно\footnote{\url{https://www.serpentine.com/2011/02/25/cps-is-great-cps-is-terrible/}}\footnote{\url{https://stackoverflow.com/questions/13835817/are-exceptions-in-c-really-slow}}, однако stack unwinding средствами рантайма как будто имеет большее пространство для оптимизаций.

Теперь попробуем вызвать продолжение несколько раз.
Получим язык с недетерминизмом (или backtracking).
Так, \texttt{choice} дважды продолжает остаток программы и аккумулирует все полученные результаты в списке:
\begin{minted}{haskell}
    choice :: Cont [r] Bool
    choice = Cont \k -> k True ++ k False

    runNondet :: (forall r . Cont [r] a) -> [a]
    runNondet comp = runCont comp (:[])

    exampleNondet :: Int -> [Int]
    exampleNondet n = runNondet do
      b <- choice
      if b then pure n else pure (n - 1)
\end{minted}

Удивительно, но имея только продолжения первого класса можно реализовать даже язык с изменяемой ячейкой памяти:
\begin{minted}{haskell}
    -- s -> (s, a) ~ ((s, a) -> r) -> (s -> r)
    -- ~ (a -> s -> r) -> (s -> r) ~ Cont (s -> r) a

    get :: Cont (s -> r) s -- (s -> s -> r) -> (s -> r)
    get = Cont \k s -> k s s

    put :: s -> Cont (s -> r) ()
    put s' = Cont \k _s -> k () s'

    runStateС :: (forall r . Cont (s -> r) a) -> s -> (a, s)
    runStateС comp = runCont comp (,)

    exampleState :: Int -> ((), Int)
    exampleState = runStateС do
      s <- get
      put (s + 1)
\end{minted}
Идея довольно простая: захват продолжения оставляет после себя функцию, в которую предыдущий вызов продолжения подкладывает текущее состояние.
И действительно, изменяемое состояние это просто фрагмент продолжения (например, аппаратного стека), к которому мы имеем непосредственный доступ на чтение и изменение.
Здесь же мы разместили в начале продолжения аппликацию, к которой, захватывая продолжение, прыгаем, чтобы получить аргумент и обновить её на новую.

\begin{task}
    Поредуцируйте пример выше, чтобы понять, как это работает.
\end{task}

Интуитивно могущество продолжений можно попробовать объяснить следующим образом: поддерживать продолжение~--- это основная обязанность системы исполнения языка; когда продолжения передаются пользователю, его код как бы вовлекается в деятельность runtime'а и становится его частью.

\subsubsection{The mother of all monads} \label{subsubsec:monadic-reflection}

В предыдущем параграфе (\ref{subsubsec:god-cont}) мы реализовали возможности классических монад в языке с продолжениями.
Сработает ли это для произвольной монады?
Оказывается, что да\footnote{\url{http://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/the-mother-of-all-monads}}\footnote{\url{https://blog.poisson.chat/posts/2019-10-26-reasonable-continuations.html}}~\cite{filinski1994representing}.

Вспомним, что монада --- это конструктор типа \texttt{m}, которым мы представляем денотацию вычисления.
Операции \texttt{pure} и \texttt{bind} позволяют создавать и композировать денотации.
Таким образом, мы имеем вычисления, представленные в виде first-class данных.

Если наш язык предоставляет продолжения первого класса (для примера возьмём \mintinline{haskell}{Cont (m r)} как такой язык), мы можем определить две операции: \texttt{reflect}~--- исполнить монадическое вычисление в языке с продолжениями и получить результат \texttt{a}; \texttt{reify}~--- по вычислению в языке с продолжениями получить денотацию\footnote{Для энергичного языка \texttt{reify} должна принимать thunk \texttt{(() -> a) -> m a}.}.
В Haskell можно это выразить как перегрузку этой пары функций для различных монад:
\begin{minted}{haskell}
    class MonadicReflection m where
      -- m a -> (a -> m r) -> m r
      reflect :: m a -> forall r . Cont (m r) a
      -- (forall r . (a -> m r) -> m r) -> m a
      reify :: (forall r . Cont (m r) a) -> m a
\end{minted}

Например, для домена \mintinline{haskell}{State} реализация будет выглядеть следующим образом:
\begin{minted}{haskell}
    newtype State s a = State { runState :: s -> (a, s) }

    instance MonadicReflection (State s) where
      reflect :: State s a -> (forall r . Cont (State s r) a)
      reflect comp = Cont \k -> State \s ->
        let (a, s') = runState comp s in
        runState (k a) s'

      reify :: (forall r . Cont (State s r) a) -> State s a
      reify comp = State $ runState (runCont comp (\x -> State (x,)))

    exampleStateReflection :: Int -> (Int, Int)
    exampleStateReflection = runState $ reify do
      x <- reflect get
      reflect $ put (x + 1)
      pure x
\end{minted}

% todo переписать через shift/reset

Интуитивно это можно понимать следующим образом: реализации bind на самом деле не важно, ей подаётся ``маленькое'' продолжение (собранное с помощью рассахаривания \mintinline{haskell}{do}-нотации), или ``большое'' продолжение, собранное мета-языком или монадой \mintinline{haskell}{Cont}.
И в принципе монады можно задавать через их вложение в монаду \mintinline{haskell}{Cont}\footnote{\url{https://blog.poisson.chat/posts/2019-10-27-continuation-submonads.html}}.

Таким образом, если язык поддерживает продолжения первого класса, можно в direct-стиле\footnote{\url{https://www.unison-lang.org/docs/fundamentals/abilities/for-monadically-inclined/}} реализовать функциональность произвольной монады, без \mintinline{haskell}{do}-нотации, аппликативных цепочек и прочего синтаксического шума\footnote{\url{http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html}}\footnote{\url{https://github.com/lampepfl/monadic-reflection/blob/main/TUTORIAL.md}}.
Позже мы увидим, что этот подход, в отличие от монад, нативно поддерживает композицию (\ref{sec:effects}), а также не накладывает ограничений на типизацию (\ref{sec:effect-systems}).
Отсюда возникает вопрос: а нужны ли нам теперь в программировании монады?

\subsubsection{Генераторы и корутины} \label{subsubsec:generators-coroutines}

Генераторы и корутины обычно определяют как вычисление, которое может быть остановлено и возобновлено снова в том же состоянии~\cite{moura2009revisiting}.
Корутины же обобщают генераторы и, как правило, используются как примитив асинхронного программирования в виде \texttt{async/await} или других языковых конструкций~\cite{elizarov2021kotlin}.
Различие синхронного и асинхронного программирования можно понимать так: в первом случае продолжениями управляет исключительно операционная система, а во втором --- средства языка.

Для примера реализуем генераторы.
В качестве результата генератора будем использовать ленивый список, итератор, закодированный в виде развёртки (см.\ \ref{subsec:all-unfolds}):
\begin{minted}{haskell}
    data Box f = forall s . Box s (s -> f s)
    data ListF a rec = Nil | Cons a rec
    type Iterator a = Box (ListF a)

    box2list :: Iterator a -> [a]
    box2list (Box s next) = case next s of
      Nil -> []
      Cons x s' -> x : box2list (Box s' next)
\end{minted}

Скрытым состоянием итератора будет ещё невыполненное продолжение.
Доступ к продолжению будем получать в монаде \mintinline{haskell}{Cont}, где в качестве response type возьмём \mintinline{haskell}{GenState}.
Так, операция \texttt{yield} останавливает вычисление и сохраняет продолжение в конструкторе \mintinline{haskell}{Yield}, а \texttt{makeGen} заканчивает данный генератор порождением конструктора \mintinline{haskell}{Stop}:
\begin{minted}{haskell}
    data GenState a = Stop | Yield a (() -> GenState a)

    makeGen :: Cont (GenState a) () -> Iterator a
    makeGen comp = Box
      (\() -> runCont comp (\() -> Stop))
      (\k -> case k () of
          Stop -> Nil
          Yield x k' -> Cons x k'
      )

    yield :: a -> Cont (GenState a) ()
    yield x = cont \k -> Yield x k
\end{minted}

Теперь мы можем писать код, последовательно порождающий множество результатов:
\begin{minted}{haskell}
    exampleGen :: [Int]
    exampleGen = it2list $ makeGen do
      yield 1
      yield 2
      yield 3
\end{minted}

\begin{task}
    Приведите вычисление \mintinline{haskell}{runCont exampleGen (\() -> Stop))} к нормальной форме.
\end{task}


% todo метапрограммирование и построение компиляторов

% todo paper delimited continuations in WebAssembly

% todo SPJ compiling without continuations

% todo The Essence of Compiling with Continuations W. Appel

% todo calculating correct compilers

% todo CEKT
% todo abstract machines

\subsection{Эффективная работа с продолжениями} \label{subsec:efficient-cps}

На практике для реализации генераторов и корутин требуется останавливать и продолжать программу, иначе говоря, захватывать продолжения.
Это нужно делать максимально эффективно.

% todo https://dl.acm.org/doi/10.1145/3385412.3385994

\subsubsection{Contiguous stack}

Продолжение представляется в виде аппаратного стека.
Как только требуется захватить продолжение, стек копируется в кучу (возможно, лениво)\footnote{\href{https://youtu.be/kwS3OeoVCno?si=c4MkSkmLHNeywPrZ}{(youtube) Иван Углянский - Java Project Loom.}}. % todo cite
То есть этот подход полностью полагается на поддержку со стороны рантайма языка.

\subsubsection{Сегментный стек} % todo cite

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

% todo стек как массив

\subsubsection{Finite state machine (FSM)}

Данная реализация подразумевает автоматическую CPS трансформацию пользовательского кода средствами компилятора.
Чтобы не аллоцировать большое количество замыканий, продолжения дефункционализируются и в рамках каждой функции представляются одним изменяемым объектом.
Так, состояние функции целиком один раз аллоцируется в куче, а возобновление кода тела функции в определённом месте реализовано как машина состояний~--- с помощью меток и прыжков\footnote{\url{https://github.com/Kotlin/KEEP/blob/master/proposals/coroutines.md\#state-machines} \label{note:kotlin-state}}.

Таким образом, например, реализованы корутины в Kotlin\footref{note:kotlin-state}, генераторы в C\#\footnote{\url{https://csharpindepth.com/Articles/IteratorBlockImplementation}}\ldots

Даже в таком виде CPS остаётся тяжеловесной трансформацией, способной замедлить исполнение кода на порядки.
Дело, в частности, в том, что переменные в таком подходе сложно размещать в регистрах (у функций много точек выходов и входов\footref{note:kotlin-state}), приходится постоянно записывать их в RAM --- производить \vocab{spilling}\footnote{\url{https://en.wikipedia.org/wiki/Register_allocation}}.

% todo объяснение через дефункционализацию

% todo плюсы минусы подводные камни каждого из них

% todo картинки

% todo in haskell native implementation

% todo rust continuations


% todo serializable continuations

% todo copy-and-patch-compilation. It does CPS to redirect control flow, but then patches the code to remove the CPS overhead https://arxiv.org/pdf/2011.13127