fp2-effects.tex

%! suppress = MissingLabel

Ранее мы признали работу со сложностью главной задачей программиста, а построение встроенных языков~--- основным инструментом её решения (\ref{subsec:interpreters-rules}).
В данной главе мы рассмотрим понятие эффекта.
Оно тесно связано со встроенными языками и даст нам лучшее понимание, когда их конструировать, что это даёт, и с чем нужно быть осторожным.

Для реализации встроенных языков мы предпочли shallow embedding в форме tagless final (\ref{subsec:tagless-final}), который максимально переиспользует возможности мета-языка и позволяет давать различные интерпретации одной программе.
Далее мы исследовали процесс вычисления и извлекли понятие продолжения (\ref{sec:continuations}).
Оказалось, что tagless final языки, которые мы строили вокруг монад, можно выразить через продолжения удобнее и проще (\ref{subsubsec:god-cont},\ \ref{subsubsec:monadic-reflection}).
В этой главе мы поймём, как это поможет решить expression problem (\ref{subsec:expression-problem}) до конца.

С историческо-философской перспективы, теория эффектов является прочным мостом между функциональной и императивной парадигмами программирования.
Они возникли порознь как Машина Тьюринга и $\lambda$-исчисление Чёрча, и оставались довольно изолированными школами мысли довольно долгое время.
Это стало меняться в последние 30 лет, и мы стали понимать, как эти два мира дополняют друг друга.
Теория эффектов до сих пор является крайне горячей темой\footnote{\href{https://youtu.be/m821Vz8N_bo?si=HQTDfs52vYKaBcqJ}{(youtube) The Evolution of Effects --- Nickolas Wu.}}\footnote{\url{https://github.com/yallop/effects-bibliography}}.

\subsection{Понятие эффекта} \label{subsec:about-effects}

Начнём разговор от обратного, со свойства чистоты.
\vocab{Чистая функция} обладает следующими свойствами:
\begin{itemize}
    \item Её результат всегда одинаков при одинаковом наборе аргументов (никак более нетривиально не зависит ни от чего более);
    \item Её единственный наблюдаемый результат --- её возвращаемое значение.
\end{itemize}

% todo obsidian What is a purely functional language?

В целом стиль программирования с использованием чистых функций приветствуется, так как он обладает множеством хороших свойств.
Так, про них можно удобно рассуждать с помощью equational reasoning; всё, что нужно для понимания кода, явно написано в этом коде; классические системы типов хорошо работают, предоставляя полноту абстракции, качественную документацию и частичную спецификацию\ldots
Также известно, что всё можно записать с помощью чистых вычислений, даже работу с IO~\cite{jones2001tackling}.

Однако, используя только чистые функции, всё приходится делать вручную.
В случае с IO (с состоянием аналогично) --- передавать результирующий мир в аргументы раз за разом:
\begin{minted}{haskell}
    getList :: Int -> World -> (World, [Int])
    getList n w | n == 0 = (w, [])
                | otherwise =
      let (w', x) = getInt w in
      let (w'', xs) = getList (n - 1) w' in
      (w'', x : xs)
\end{minted}

Таким образом, код из чистых функций заполнен несущественными церемониями, за которыми не видно бизнес-логики и сути.
Чтобы сосредоточиться на важных деталях, нужно делегировать весь этот bookkeeping стороннему коду, замести неинтересные детали под ковёр.
Тогда код выше можно будет переписать, например, следующим образом:
\begin{minted}{haskell}
    getList :: Int -> IO [Int]
    getList n | n == 0 = pure []
              | otherwise = do
      x <- getInt
      xs <- getList (n - 1)
      return (x : xs)
\end{minted}

Абстрактную сущность, которой мы будем делегировать несущественные для данного фрагмента бизнес-логики детали, мы будем называть \vocab{контекстом исполнения (execution context)}\footnote{\url{https://okmij.org/ftp/Computation/having-effect.html} \label{lab:having-effect}}.
А \vocab{эффектом}~--- взаимодействие функции с контекстом исполнения, которое происходит с помощью вызова \vocab{effect-операций} (например, \texttt{getInt} из примера выше)\footnote{Также эффектом иногда называют функцию перехода в dataflow-анализе~\cite{moller2012static}. По сути, она как раз описывает изменение контекста.}. % todo Effect systems revisited—control-flow algebra and semantics % todo Data-flow analyses as effects and graded monads
Так, на контекст исполнения можно смотреть как на сервер, которому функция-клиент шлёт запросы и получает ответы (см.\ рис.\ \ref{fig:effect-server}).
В этой модели такая функция может нарушать оба свойства чистых функций.

\begin{figure}
    \centering
    \includegraphics[width=0.5\textwidth]{figs/effects}
    \caption{Эффекты как клиент-серверное взаимодействие.}
    \label{fig:effect-server}
\end{figure}

На практике этим контекстом является интерпретатор (встроенного) языка, а effect-операциями --- его конструкции.
Если язык является встроенным, то говорят о \vocab{пользовательских (user-defined) эффектах}.
Так мы снова возвращаемся к задаче построения модульных интерпретаторов (\ref{subsec:expression-problem}).
К тому же, реализация вычислительного контекста также может делегировать реализацию некоторой функциональности другому контексту исполнения, и так далее.
Получаем уже знакомую нам башню интерпретаторов (\ref{subsubsec:interpreters-tower}).

Рассмотрим некоторые примеры вычислительных контекстов и операций:
\begin{itemize}
    \item Контекст --- подсистема управления памятью, \texttt{modify} --- effect-операция: контекст для нас поддерживает состояние ячеек памяти;
    \item Контекст~--- хендлер исключения, \texttt{throw MyException}~--- effect-операция: контекст за нас определяет, как ошибка будет обрабатываться (обратите внимание, что тут управление не возвращается терму);
    \item Контекст~--- настройки инъекции зависимостей, запрос функциональности~--- effect-операция: контекст за нас определяет реализацию функциональности, которой нам пользоваться\footnote{Существует термин \vocab{contextual polymorphism}~--- код в разных контекстах может иметь различное поведение.}.
    Как мы увидим далее, этот и подобные простые эффекты можно реализовать просто и эффективно (см.\ \ref{subsubsec:evidence-passing}).
\end{itemize}

\begin{task}
    Приведите ещё примеры вычислительных контекстов и операций.
\end{task}

Когда мы говорим про standalone язык, на котором мы программируем (например, Haskell), любое наше действие в программе исполняется им.
То есть, например, сложение --- effect-операция?
В таком случае разумно выделить подмножество конструкций языка, достаточно ``интересных'', чтобы считать, что они порождают эффект.

Какие конструкции языка считать ``интересными''?
Заметим, что с одной стороны это хорошо, что эффекты скрывают от нас некоторую сложность, позволяя сосредоточиться на других вещах.
С другой стороны, это же и плохо, ведь мы эту сложность перестаём наблюдать, а она пронизывает наш код, поддерживает неявные зависимости между его частями.
Таким образом, эффекты требуют дополнительной аккуратности со стороны программиста\footnote{\href{https://youtu.be/_nG09Z_tdUU?si=lo9It6299rsB1vAr}{(youtube) Kris Jenkins --- Side-Effects Are The Complexity Iceberg.}}.
Соответственно, именно такие непростые конструкции и стоит считать ``интересными''.
Как минимум точно стоит считать ``интересными'' конструкции, использование которых выводит функцию из категории чистых.
Также, это могут быть операции, делающие сложные нелокальные модификации потока управления (поддерживаемого интерпретатором в виде продолжения).

В конечном итоге выбор ``интересных'' конструкций зависит от задачи и перспективы разработчика\footref{lab:having-effect}.
Так, конструкции, влияющие на произвольные наблюдаемые свойства кода, как, например, терминируемость или вычислительная сложность, могут мотивировать считать рекурсивные вызовы или долгие операции эффектами.

Далее мы научимся отслеживать и контролировать использование эффектов на уровне типов с помощью систем эффектов (см.\ далее\ \ref{sec:effect-systems}).

\subsection{Хендлеры эффектов} \label{subsec:effect-handlers}

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

Основная идея хендлеров эффектов довольно проста.
Вводится языковая конструкция \texttt{handle}, позволяющая задать вычислительный контекст для определённого скоупа, предоставляющий реализации effect-операций.
Также вводится конструкция \texttt{perform}, позволяющая вызвать effect-операцию (отправить запрос контексту).
Каждая операция имеет набор параметров, а также ``обратный адрес'', продолжение места вызова, в который она вернёт результат.
Например, на экспериментальном языке Koka\footnote{\url{https://koka-lang.github.io/koka/doc/index.html}} контекст, предоставляющий некоторую константу, может быть реализован следующим образом (\texttt{resume}~--- имя продолжения места вызова, \texttt{perform} вставляется неявно):
\begin{minted}{cpp}
    with handler
      ctl ask() resume(21)
    ask() + ask()
\end{minted}

Если ближайший контекст нужный запрос обработать не может, запрос делегируется внешнему контексту, и так пока подходящий контекст не будет найден.
На этой идее основывается модульность интерпретаторов, заданных хендлерами.

% todo историческая справка

% todo больше впечатляющих примеров

% todo ссылка на простой туториал по хендлерам
% todo https://www.eff-lang.org/handlers-tutorial.pdf

\subsubsection{Хендлеры через ограниченные продолжения}

Как мы уже видели ранее, различные эффекты можно реализовывать с помощью доступа к текущему продолжению (\ref{subsubsec:god-cont}, \ \ref{subsubsec:monadic-reflection}).
Хендлеры эффектов дополняют эту идею тем, что используют ограниченные продолжения, чтобы передавать управление различным интерпретаторам (хендлерам).

Известно, что классические операторы манипуляции ограниченными продолжениями, monadic reflection и хендлеры эффектов выразимы друг через друга~\cite{forster2017expressive}.

\subsubsection{Эффективная реализация хендлеров} \label{subsubsec:evidence-passing}

В общем виде скорость работы \texttt{perform} определяется скоростью захвата и восстановления ограниченных продолжений.
Однако, существует класс операций, которые можно реализовать гораздо эффективнее.

Если мы посмотрим на реализацию операции \texttt{ask}, то мы увидим, что она последним действием вызывает продолжение, возвращая управление вызвавшему коду.
Такие операции называют \vocab{tail-resumptive}, они очень сильно напоминают обычные функции, за исключением того, что их реализации определяются контекстом (хендлером).
Таким образом, tail-resumptive операции можно реализовать как неявную передачу словаря функций от хендлера к \texttt{perform}, и тем самым избежать дорогих манипуляций продолжениями~\cite{xie2020effect}\footnote{Хендлеры tail-resumptive операций напоминают co-pattern-matching и, соответственно, объекты (см.\ \ref{subsubsec:data-codata}).}.

\subsubsection{Встроенные хендлеры как явная клиент-серверная коммуникация} \label{subsubsec:extensible-effects}

Чтобы лучшим образом понять семантику хендлеров, реализуем язык с хендлерами как встроенный в Haskell.
Начнём с варианта, предложенного Олегом Киселёвым, максимально прямолинейно кодирующего идею клиент-серверной коммуникации терма и контекста~\cite{kiselyov2013extensible}.

Начнём с эффекта \texttt{ask}, запрашивающего числа у контекста.
Зададим тип данных сообщений к контексту, это либо конечный результат вычисления, либо запрос \mintinline{haskell}{Ask}, содержащий ``обратный адрес''~--- текущее продолжение:
\begin{minted}{haskell}
    data Message res = Val res | Ask (Int -> Message res)
\end{minted}

Продолжения будем собирать в специализированный \mintinline{haskell}{Monad Cont} с подходящим response type (см.~\ref{subsubsec:monad-cont}, \ \ref{subsubsec:god-cont}):
\begin{minted}{haskell}
    newtype Eff res = Eff
      { runEff :: forall res' . (res -> Message res') -> Message res' }
\end{minted}

Тогда эффект \texttt{ask} реализуется просто как ``отправка'' запроса \mintinline{haskell}{Ask} с текущим продолжением:\footnote{Ранее мы аналогично реализовывали генераторы, см.\ \ref{subsubsec:generators-coroutines}.}
\begin{minted}{haskell}
    ask :: Eff Int
    ask = Eff \k -> Ask k
\end{minted}

Хендлер мы реализуем как ``сервер'', который в цикле обрабатывает запросы, пока вычисление не пришлёт конечный результат:
\begin{minted}{haskell}
    run :: Eff res -> Message res
    run comp = runEff comp Val

    runReader :: Eff res -> Int -> res
    runReader comp env = loop (run comp)
      where
        loop = \case
          Val res -> res
          Ask k -> loop (k env)
\end{minted}

Наконец, мы можем писать effectful код:
\begin{minted}{haskell}
    exampleReader :: Int -> Int
    exampleReader = runReader do
      x <- ask
      y <- ask
      pure (x + y)
\end{minted}
Монада \mintinline{haskell}{Eff} превратит его в ленивый список сообщений:
\begin{minted}{haskell}
    exampleReader :: Int -> Int
    exampleReader = loop $
      Ask \x ->
      Ask \y ->
      Val (x + y)
\end{minted}

\subsubsection{Расширяемые сообщения и пересылка} \label{subsubsec:extensible-messages}

Абстрагируем тип сообщений по ``форме'' запросов, которые в них могут участвовать (см.\ \ref{subsubsec:functor-fixpoint}):
\begin{minted}{haskell}
    data Message effs res = Val res | Request (effs (Message effs res))
\end{minted}

Предыдущий тип сообщений получается передачей следующего функтора формы:
\begin{minted}{haskell}
    newtype Reader env msg = Ask (env -> msg)
\end{minted}

\begin{task}
    Убедитесь, что \mintinline{haskell}{Message (Reader Int) res} эквивалентно предыдущему типу сообщений.
\end{task}

Копроизведение функторов формы является функтором формы (см.\ \ref{subsubsec:functor-coprod}):
\begin{minted}{haskell}
    data (eff |> effs) a = L (eff a) | R (effs a)
\end{minted}

Теперь операция \texttt{ask} допускает существование других типов запросов \texttt{effs}:
\begin{minted}{haskell}
    ask :: Eff (Reader env |> effs) env
    ask = Eff \k -> Msg $ L $ Ask k
\end{minted}

Новый хендлер обрабатывает только часть запросов, остальные пересылает хендлеру выше (скомпозировав правильным образом продолжения):
\begin{minted}{haskell}
runReader
  :: forall effs env res . Functor effs
  => Eff (Reader env |> effs) res
  -> env -> Eff effs res
runReader comp env = loop (run comp)
  where
    loop :: Request (Reader env |> effs) res -> Eff effs res
    loop = \case
      Val res -> pure res
      Msg (L (Ask k)) -> loop (k env)
      Msg (R unknownReq) -> do
        response <- Eff \k -> Msg (fmap k unknownReq)
        loop response
\end{minted}

Заметьте, что в результирующем домене остались непроинтерпретированные эффекты.
Конечный домен получится применением всех необходимых интерпретаторов.
Так решается stable denotations problem (\ref{subsec:expression-problem}).

\subsubsection{Свободные монады} \label{subsubsec:free-monads}

Чтобы получить полноценное решение более простым и минималистичным образом, перейдём к самой классической реализации хендлеров через свободные монады.
Для начала обсудим сами свободные монады.

Рассмотрим некоторую алгебраическую структуру, например, моноид (нейтральный элемент и ассоциативная бинарная операция).
По произвольному множеству $X$ можно построить некоторый моноид $M(X)$ наиболее ``экономичным'' образом~--- \vocab{свободный моноид}.
Это делается следующим образом: к множеству $X$ добавляют деревья выражений с операциями моноида:
\begin{minted}{haskell}
    data M x = Element x | Mempty | Mappend (M x) (M x)
    instance Monoid (M x) where
      mempty = Mempty
      mappend l r = Mappend l r
\end{minted}
Ещё только нужно организовать новое множество таким образом, чтобы в нём не было одинаковых с точки зрения алгебры деревьев (например, \mintinline{haskell}{Mappend Mempty Mempty} и \mintinline{haskell}{Mempty}).
В случае моноида в этом случае можно выбрать тип списка:
\begin{minted}{haskell}
    type M x = [x]
    instance Monoid (M x) where
      mempty = []
      mappend = (++)
\end{minted}

Свободные монады строятся аналогично свободным моноидам.
Используем определение монады как функтора с операциями \texttt{pure} и \texttt{join}.
Тогда по произвольному функтору $F$ можно получить монаду $Free(F)$ (покажем это с помощью эквивалентного определения монад из Haskell):
\begin{minted}{haskell}
    data Free f a = Pure a | Join (f (Free f a))
    instance Functor f => Monad (Free f) where
      return = Pure
      Pure x >>= k = k x
      Join f >>= k = Join (fmap (>>= k) f)
\end{minted}

Переименуем конструкторы:
\begin{minted}{haskell}
    data Term sig var = Var var | Op (sig (Term sig var))
    (>>=) :: Term sig var -> (var -> Term sig var') -> Term sig var'
    data MonoidSig subtree = Mempty | MAppend subtree subtree -- (Bool -> subtree)
\end{minted}
Это не что иное, как кодирование алгебраических термов над сигнатурой \texttt{sig} и переменными из множества \texttt{var}.
А монадическое связывание~--- это подстановка.

\subsubsection{Хендлеры через свободные монады} \label{subsubsec:free-monad-handlers}

Заметим, что следующие типы изоморфны: \mintinline{haskell}{Message} $\iso$ \mintinline{haskell}{Free} $\iso$ \mintinline{haskell}{Term}.
Хендлеры в классическом виде как раз и возникли в процессе изучения того, как описывать эффекты в виде алгебраических структур~\cite{bauer2018algebraic}\footnote{\href{https://www.youtube.com/watch?v=vPVMXLJVylU&list=PLt7hcIEdZLAkebYy70DdBDm2qLrw7ptfp}{(youtube) What is algebraic about algebraic effects and handlers --- Andrej Bauer.}}.

Вместо переменных мы будем хранить чистый результат вычисления, а сигнатуры будем записывать в виде $P\times (A \to K)$, где $P$~--- параметр операции, а $A$~--- результат операции, по которому хендлер выбирает нужный подтерм-продолжение для возобновления вычисления:
\begin{minted}{haskell}
    data Comp effs res = Res res | Op (effs (Comp effs res))
    data Reader env comp = Ask () (env -> comp)
    data State s comp = Get () (s -> comp) | Put s (() -> comp)
\end{minted}

Реализация \mintinline{haskell}{Monad Comp} будет как раз композировать продолжения для нас в \mintinline{haskell}{do}-нотации:
\begin{minted}{haskell}
    ask = Op (Ask () (\e -> Val e)
    example = do
      x <- ask
      y <- ask
      pure (x + y)
    -- ?$\alpha\beta$?-эквивалентно
    example =
      Op (Ask () (\x ->
      Op (Ask () (\y ->
      Res (x + y)))))
\end{minted}

Хендлер также просто сворачивает список операций.
Операции, которые он не умеет обрабатывать, он оставляет в дереве.
Чтобы пропустить неизвестную операцию и интерпретировать поддерево (продолжение), используется \texttt{fmap}:
\begin{minted}{haskell}
    runReader
      :: Functor effs => Comp (Reader env |> effs) res -> env -> Comp effs res
    runReader comp env = case comp of
      Res res -> Res res
      Op (L (Ask () k)) -> runReader (k env) env
      Op (R other) -> Op (fmap (`runReader` env) other)
\end{minted}

\begin{task}
    Постройте пример вычисления из \mintinline{haskell}{Reader} и \mintinline{haskell}{State}.
    Какое дерево получится после интерпретации одного из эффектов?
\end{task}

Как обычно, свёртку можно обобщить в виде катаморфизма:
\begin{minted}{haskell}
    handle
      :: Functor effs => (res -> d) -> (effs d -> d) -> Comp effs res -> d
    handle val alg = \case
      Pure res -> val res
      Op eff -> alg $ fmap (handle val alg) eff
\end{minted}
Теперь в реализации продолжение (поддерево) уже проинтерпретировано в нужный домен:
\begin{minted}{haskell}
    runReader
      :: Functor effs => Eff (Reader env |> effs) res -> env -> Eff effs res
    runReader = handle (\res _env -> pure res) \case
      L (Ask k) -> \env -> k env env
      R other -> \env -> Op (fmap ($ env) other)
\end{minted}

Когда хендлеры реализуют как built-in возможность в языке, нужно принять дизайн-решение, в предоставляемом продолжении текущий эффект уже проинтерпретирован, или нет.
Первый вариант называют \vocab{deep handlers}, второй~--- \vocab{shallow handlers}, они выразимы друг через друга~\cite{hillerstrom2018shallow}.

К сожалению, поскольку различные варианты эффектов упорядочены как на уровне термов, так и на уровне типов, нам нужна операция, превращающая вычисление от меньшего количества эффектов в вычисление с большим:
\begin{minted}{haskell}
    liftF :: Functor effs => Comp effs res -> Comp (eff |> effs) res
    liftF = \case
      Pure x -> Pure x
      Op effs -> Op $ R $ liftF <$> effs

    example :: Comp (Reader Int |> State Int) ()
    example = do
      env <- ask
      liftF (put env)
\end{minted}
От порядка можно избавиться с помощью классов типов~\cite{swierstra2008data} (\ref{subsubsec:open-structs}).

Можно заметить, что помимо большого количества аллокаций, использование \mintinline{haskell}{Monad Free} может приводить к квадратичной сложности кода из-за линейных проходов в каждом bind'е.
Существуют различные альтернативные схемы кодирования~\cite{ploeg2014reflection, kiselyov2015freer}.

Свободные монады находят и другие, правда, аналогичные применения: trampolining~\cite{bjarnarson2012stackless} и пайплайны~\cite{kiselyov2012iteratees}~\cite[chapter 14]{bragilevsky-haskell}.

\subsubsection{Приложения хендлеров} \label{subsubsec:handler-applications}

Рассмотрим хендлеры tail-resumptive операций, обращающиеся с продолжениями тривиальным образом.
Они нужны для распространения значений и функциональности вниз по стеку.
Как мы обсуждали ранее~\ref{subsubsec:evidence-passing}, такие хендлеры аналогичны наличию динамических свободных переменных или неявных аргументов функций~\ref{subsubsec:ad-hoc-implicits}, и, вместе с ними, рекордов или анонимных классов~\ref{subsubsec:data-codata}.

Среди нетривиальных сценариев использования продолжений выделим следующие:
\begin{itemize}
    \item Продолжение можно не вызвать, так, можно реализовать механизм исключений.
    Однако, на практике продолжения могут содержать логику финализации ресурсов.
    В этом случае всё равно нужна какая-то специальная обработка~\footnote{\url{https://koka-lang.github.io/koka/doc/book.html\#sec-resource}}.
    \item Можно вызвать несколько раз для эмуляции недетерминизма.
    Это ограничивает использование эффективных мутабельных продолжений~\ref{subsec:efficient-cps}~\cite{leijen2018algebraic}\footnote{\url{https://koka-lang.github.io/koka/doc/book.html\#sec-multi-resume}}, а также требует нетривиальной обработки при работе с ресурсами.
    \item Можно вызвать не сразу.
    Это нужно для реализации изменяемого состояния, генераторов и корутин.
    Для изменяемого состояния это слишком дорого.
    Генераторы~--- хорошее применение, но built-in реализация генераторов может быть эффективнее за счёт экономии аллокаций продолжений (создаётся сразу \mintinline{kotlin}{Iterator})\footnote{\url{https://csharpindepth.com/Articles/IteratorBlockImplementation}}.
    Реализация корутин поверх хендлеров даёт возможность пользователям писать собственные планировщики, что самое котируемое применение хендлеров на данный момент~\cite{sivaramakrishnan2021retrofitting, phipps2023continuing}. % todo
\end{itemize}

\subsubsection{Трансформеры монад} \label{subsubsec:monad-transformers}

В классической реализации хендлеров через свободные монады~\ref{subsubsec:free-monad-handlers}, каждый хендлер порождает промежуточное дерево из непроинтерпретированных операций.
Естественным образом возникает желание дефорестировать~\ref{subsubsec:deforestation-fusion} эти промежуточные деревья.
Можно пойти до конца и полностью избавиться от свободных монад и функторов сигнатур~\cite{wu2015fusion}.
Так, мы фактически получим tagless final shallow embedding~\ref{subsec:tagless-final}, другое популярное решение expression (stable denotations) problem~--- \vocab{трансформеры монад}~\cite{liang1995monad,jones1995functional}\footnote{\url{https://hackage.haskell.org/package/mtl}}.
В целом эти подходы, равносильны по выразительности, однако могут иметь на практике различные особенности встраивания в язык~\cite{schrijvers2019monad}.
Однако, в отличие от трансформеров, хендлеры можно сделать удобной built-in возможностью языка.

% todo show some hint how deforestation gives monad transformers
% todo lift - monad morphism
% todo ContT, lift = (>>=)

\subsubsection{Алгебраичность и эффекты высших порядков} \label{subsubsec:algebraicity-higher-order}

В начале нулевых появилась идея описывать effect-операции не монадами сразу, а алгебраически, с помощью сигнатур и уравнений~\cite{plotkin2002notions, bauer2018algebraic}.
Эффекты в этом формализме являются композируемыми по построению, как композируемы сигнатуры алгебраических теорий (конкатенация сигнатур~--- сигнатура~\ref{subsubsec:extensible-messages}), так мы имеем расширяемый синтаксис.
Однако, на операции накладывается ограничение в виде \vocab{свойства алгебраичности}~--- операция коммутирует с продолжением и ``всплывает'' наверх:
\[
    E[op(v, k)] \equiv op(v, \lambda x\ldotp E[k(x)])
\]
Соответствующие эффекты называют \vocab{алгебраическими}.

В нашей реализации (\ref{subsubsec:free-monad-handlers}) ограничение на алгебраичность можно увидеть следующим образом.
У нас сигнатуры операций являются функторами по своим продолжениям.
Этим пользуются как монадическое связывание для накапливания продолжений, так и хендлеры для интерпретации продолжений неизвестных операций.

Многие полезные эффекты являются алгебраическими, но не все.
Например, поимка исключений \texttt{catch} не является алгебраической операцией, так как её сигнатура запишется следующим образом:
\begin{minted}{haskell}
    data Catch e comp = Catch { try :: comp, onExn :: (e -> comp), next :: comp }
\end{minted}
В таком случае единственная разумная реализация функтора будет работать, в том числе, и с вложенными продолжениями, и вся программа, в результате работы bind, окажется внутри блока \texttt{try}.

Иначе говоря, \point{алгебраические эффекты не могут принимать другие effectful вычисления в качестве аргументов}.
Как раз, чтобы моделировать \texttt{catch}, и были оригинально предложены хендлеры~\cite{plotkin2013handling}\footnote{Несмотря на то, что алгебраические эффекты~--- это просто класс ``хороших'' операций, часто при их упоминании подразумевают хендлеры эффектов.}.
Таким образом, у хендлеров две задачи: ограничивать скоуп некоторой функциональности и интерпретировать эффекты.
Однако, как мы знаем, порядок хендлеров определяет результирующий домен и, соответственно, семантику.
В то же время задача ограничения скоупа фиксирует позицию хендлера, что ограничивает выразительность и делает некоторые домены недоступными.

Операции, не удовлетворяющие свойству алгебраичности, соответствуют \vocab{эффектам высших порядков (higher-order effects)}, которы могут принимать другие effectful вычисления в качестве аргументов.
Существуют встраивания хендлеров таких эффектов и обширный набор исследований на тему~\cite{wu2014effect}\footnote{\url{https://github.com/fused-effects/fused-effects}}\footnote{\href{https://youtu.be/vfDazZfxlNs?si=3o1zkoL8GsmezMtU}{(youtube) Building Haskell Programs with Fused Effects --- Patrick Thomson}}~\cite{yang2022structured}.

Ключ к эффектам высших порядков состоит в возможности исполнять эффекты вычислений-аргументов в контексте тех хендлеров, которые доступны на колсайте эффекта высших порядков~\cite{van2022handling}.
Это связано с другой идеей, bidirectional effects, позволяющей реализации операции порождать эффекты на своём колсайте (например, бросать там исключения), что крайне необходимая на практике возможность~\cite{zhang2020handling}\footnote{\url{https://effekt-lang.org/docs/concepts/bidirectional}}.

% todo больше (впечатляющих) примеров

% todo how algebraicity of operations powers such instance declarations?
% todo about MTL n^2 instance problem
%\begin{minted}{haskell}
%    instance (MonadTrans t, MonadReader e m) => MonadReader e (t m) where
%      asks = lift . asks
%
%    Catch comp (e -> comp) (a -> comp)
%
%    catch :: m a -> (e -> m a) -> (a -> m r) -> m r
%\end{minted}

% todo неубедительно про смысл алгебраичности (это вроде нужно чтобы индуцировались монады по этому всему)


% todo compare open type families & extensible interpreters

% todo Polymorphic Symmetric Multiple Dispatch with Variance
% todo \textit{multimethods}
%    Languages with \textit{multimethods}, like Common Lisp’s CLOS, Dylan, and Julia do support adding both new types and operations easily.
%    What they typically sacrifice is either static type checking, or separate compilation.

% todo ZIO, TS Effect

% todo call-by-push value and how it is related to effects

% todo порядок интерпретаторов и interleaving of effects

% todo abstracting definitional interpreters, github semantics (в домашку это)

% todo break и continue в домашку

% todo куда-нибудь про супермонады и скалу