Карта эффект-систем

В прошлых уроках мы выбрали для прикладного кода ReaderT-паттерн и классы-способности. Это рабочая лошадка, но не единственная школа мысли. Есть целое семейство подходов, где эффект это данные: программа не выполняется, а строится как значение, и отдельная функция, интерпретатор, решает, что эти данные значат. На этой идее стоят free-монады, библиотеки polysemy и effectful, рантайм Effect.ts из раздела 25 и даже эффект-хендлеры, встроенные в OCaml 5. Сегодня построим всё руками: выведем free-монаду из телетайпа, напишем три интерпретатора одной программы, соберём кооперативный планировщик из двадцати строк чистого кода, упрёмся в цену этой красоты, переизобретём freer и только потом откроем карту библиотек. В финале выберем стек для проекта 3 и честно его аргументируем.

Зачем эффекту быть значением

Класс-способность из урока про mtl-стиль выглядел так:

class Monad m => MonadRentals m where
  reserveCopy :: CopyId -> MemberId -> m (Either RentalError Reservation)

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

Эффект не первоклассный. Программа из методов класса растворяется в инстансе в момент написания. Её нельзя взять в руки как значение: распечатать план действий перед выполнением, собрать список SQL-запросов на аудит, прогнать в режиме dry-run, переиграть с другим вводом. Метод вызвался, эффект случился, всё.

Интерпретация приколочена к типу. Какой инстанс компилятор найдёт по типу носителя m, та интерпретация и будет. Одна на тип, выбирается на этапе компиляции. Захотел выполнить ту же программу дважды по-разному в одном тесте, заводи второй носитель-newtype.

Знакомая цена. Квадрат инстансов из урока про mtl и вся машинерия вокруг него никуда не делись: каждый новый эффект это класс плюс пачка пробросов.

Идея, которая чинит все три пункта сразу, называется алгебраическими эффектами: операция объявляется отдельно от смысла, а смысл назначает обработчик. Несколько языков встроили её прямо в ядро: OCaml 5 с его perform и эффект-хендлерами, Koka, Unison, исследовательский Eff. В Haskell для этого не нужно менять язык: достаточно ADT, функций высшего порядка и GADT из прошлого урока. Поэтому план такой: построим механизм руками, от первого конструктора до планировщика, и тогда вся карта библиотек прочитается как набор инженерных ответов на вопросы, которые ты сам успеешь себе задать.

Эффект как данные

Ты уже дважды видел главный ход этого урока. В уроке про IO мы выяснили, что IO a это не выполнение, а значение-рецепт, которое исполняет рантайм. А в уроке про eval ты написал интерпретатор целого языка: AST как данные, eval как смысл. Free-монада это те же два шага, только язык мы придумываем сами, и он состоит ровно из тех операций, которые нужны нашей программе.

Возьмём самый маленький полезный язык: телетайп, который умеет печатать строку и читать строку.

{-# LANGUAGE DeriveFunctor #-}

data TeletypeF next
  = PrintLine String next
  | ReadLine (String -> next)
  deriving Functor

Разглядывай параметр next, в нём вся соль: это что делать дальше. У PrintLine продолжение лежит рядом со строкой: напечатай и переходи к next. У ReadLine интереснее: следующий шаг зависит от того, что прочитали, поэтому next спрятан под функцией String -> next. Эта функция и есть продолжение: дай мне прочитанную строку, и я скажу, что будет дальше. В OCaml 5 такое продолжение в момент perform захватывает рантайм, выкусывая кусок стека. Нам рантайм не нужен: продолжение это обычное поле в конструкторе.

deriving Functor пишет за нас инстанс, где fmap трогает только next: подменить продолжение, не трогая саму инструкцию. Эта мелочь сейчас выстрелит.

Free: монада даром

Одна инструкция это ещё не программа. Программа это цепочка: напечатай, потом прочитай, потом в зависимости от ответа напечатай ещё. Нужен тип, который умеет нанизывать TeletypeF друг на друга и где-то заканчиваться с результатом:

data Free f a
  = Pure a                -- программа кончилась, вот результат
  | Step (f (Free f a))   -- одна инструкция, внутри которой остаток программы

Прочитай тип Step медленно: f (Free f a) это инструкция, у которой в позиции next живёт остаток программы. Рекурсия в точности как у списка, только вместо хвоста [a] хвост спрятан внутри функтора. В библиотеке free этот конструктор называется Free, как и сам тип; мы назвали его Step, чтобы не путаться.

Это free-монада, и слово free тут значит даром: монаду для неё не нужно придумывать, она пишется один раз для любого функтора f:

instance Functor f => Functor (Free f) where
  fmap g (Pure a)  = Pure (g a)
  fmap g (Step fx) = Step (fmap (fmap g) fx)

instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure g  <*> x = fmap g x
  Step fg <*> x = Step (fmap (<*> x) fg)

instance Functor f => Monad (Free f) where
  Pure a  >>= k = k a
  Step fx >>= k = Step (fmap (>>= k) fx)

Смотри, что делает >>=: он ничего не выполняет. Дошёл до листа Pure a, заменил его на дерево k a. Не дошёл, провалился глубже через fmap. Это буквально конкатенация программ: к дереву слева подклеили дерево справа. Сравни с >>= твоей мини-IO из урока про IO-монаду в разделе CS: там была та же механика, только инструкции были приколочены гвоздями. Free обобщает её на любой набор инструкций.

Минутка теории категорий. Можно пропустить, но жалко. У слова free в математике один строгий смысл на все конструкции с этим именем: свободный моноид, свободная группа, свободная монада. Есть забывающий функтор: из любой монады он делает просто функтор, потеряв pure и >>=. Free идёт в обратную сторону: по функтору достраивает монаду, причём самым экономным из возможных способов, ничего не вычисляя и не склеивая, а просто записывая каждую инструкцию и каждый >>= в дерево. На языке категорщика это левое сопряжённое к забывающему функтору, и для категорщика фраза про свободность свободной монады звучит как масло масляное: это определение, а не теорема.

Зачем тебе эта оптика? Она объясняет, почему трюк с интерпретаторами, на котором стоит весь этот урок, вообще работает. Левое сопряжённое добавляет структуру, не добавляя смысла: в дереве Free f a нет ни одного уравнения сверх монадных законов, никто заранее не решил, что значит PrintLine. Поэтому алгебра эффектов (набор инструкций) и интерпретатор разделены не доброй волей автора библиотеки, а самим построением: смыслу просто негде жить, кроме как снаружи. Заметь при этом, насколько такая картинка далека от повседневной: даже сильный практик видит в Free f a тип с двумя конструкторами и пишет по нему рекурсию, а не разглядывает сопряжение. Обе картинки верны, просто вторая объясняет, почему первая не могла сложиться иначе. В дивном новом мире, где код за тебя пишет нейросеть, можно ворчать, что такие абстракции уже никому не сдадутся. Может и так. Но само разделение, программа-данные отдельно, смысл отдельно, переживёт моду: ты встретишь его в Effect.ts, в эффект-хендлерах OCaml и везде, где чужую программу нужно сначала разглядеть и только потом запустить.

Осталось завести вспомогательные конструкторы. Помощник liftF поднимает одну инструкцию в программу из одного шага:

liftF :: Functor f => f a -> Free f a
liftF cmd = Step (fmap Pure cmd)

printLine :: String -> Free TeletypeF ()
printLine s = liftF (PrintLine s ())

readLine :: Free TeletypeF String
readLine = liftF (ReadLine id)

В readLine продолжением стало id: прочитанная строка и есть результат шага. И теперь, раз Free TeletypeF это монада, нам бесплатно достаётся do-нотация:

hello :: Free TeletypeF String
hello = do
  printLine "Как тебя зовут?"
  name <- readLine
  printLine ("Привет, " <> name <> "!")
  pure name

Выглядит как обычный императивный код. Но запусти это в GHCi, и ничего не произойдёт: hello это значение. Вот оно же без сахара, дерево как есть:

hello =
  Step (PrintLine "Как тебя зовут?"
    (Step (ReadLine (\name ->
      Step (PrintLine ("Привет, " <> name <> "!")
        (Pure name))))))

do-нотация просто собрала конструкторы в матрёшку. Обрати внимание на лямбду \name -> ...: всё, что после readLine, живёт внутри продолжения и не существует, пока кто-то не передаст туда строку. Программа-как-данные, в самом буквальном смысле.

Интерпретатор владеет продолжением

Данные лежат, смысла у них нет. Смысл назначает интерпретатор: функция, которая сворачивает дерево. Боевой вариант переводит инструкции в настоящее IO:

runIO :: Free TeletypeF a -> IO a
runIO (Pure a)                  = pure a
runIO (Step (PrintLine s next)) = putStrLn s >> runIO next
runIO (Step (ReadLine k))       = getLine >>= runIO . k

Структурная рекурсия, как sum по списку. А вот тестовый интерпретатор, и в нём ни капли IO: входные строки берём из списка, напечатанные складываем в аккумулятор:

runPure :: [String] -> Free TeletypeF a -> ([String], a)
runPure _ (Pure a) = ([], a)
runPure ins (Step (PrintLine s next)) =
  let (outs, a) = runPure ins next in (s : outs, a)
runPure ins (Step (ReadLine k)) = case ins of
  i : rest -> runPure rest (k i)
  []       -> runPure [] (k "")

ghci> runPure ["Алёша"] hello
(["Как тебя зовут?","Привет, Алёша!"],"Алёша")

Готовый assert для hspec, без моков, без подмены инстансов, без IORef. Программа одна, смыслов уже два. Прокрути оба в виджете и обрати особое внимание на третий таб:

Третий таб, dryRun, демонстрирует право интерпретатора, о котором стоит сказать вслух. Продолжение k это поле в конструкторе, и интерпретатор волен делать с ним что угодно:

• вызвать один раз, как runIO и runPure: обычное выполнение;
• не вызывать вовсе, как dryRun на ReadLine: остаток программы не материализуется и не выполняется. Это механика исключений: throw именно так и устроен в эффект-системах, инструкция без вызова продолжения;
• отложить и вызвать позже, сохранив в очередь: это планировщик, он следующим разделом;
• вызвать несколько раз с разными аргументами: недетерминизм, переберём все варианты ввода. До этого дойдём на freer.

В туториале по эффектам OCaml ровно эти четыре сюжета составляют главы: восстановимые ошибки, генераторы, планировщик, состояние. Там обработчик получает продолжение от рантайма, и оно one-shot: возобновить можно не больше одного раза, иначе рантайму пришлось бы копировать стек. Наше продолжение это чистая функция, и таких ограничений у неё нет. Запомни эту разницу, она ещё сыграет.