Чем хороши свободные монады

Предлагаю читателям «Хабрахабра» перевод статьи «Why free monads matter».

Интерпретаторы

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

• скомпилировать и выполнить его;
• непосредственно запустить с помощью традиционного интерпретатора;
• сжать и архивировать;
• просто оставить его в покое.

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

Язык будет включать всего три команды:

• output b — распечатать b на терминале
• bell — активировать системный динамик
• done — конец исполнения

Мы представим его в виде синтаксического дерева, в котором последующие команды будут листьями предыдущих:

data Toy b next =
       Output b next
     | Bell next
     | Done

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

-- output 'A'
-- done
Output 'A' Done :: Toy Char (Toy a next)

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

-- bell
-- output 'A'
-- done
Bell (Output 'A' Done) :: Toy a (Toy Char (Toy b next))

К счастью, чтобы использовать любое количество экземпляров Toy и при этом сохранять тип, мы можем поступить следующим образом:

data Cheat f = Cheat (f (Cheat f))

Тип Cheat определяет последовательность функторов, которая заканчивается конструктором Done. К приятному удивлению, Haskell уже содержит подобный тип:

data Fix f = Fix (f (Fix f))

Fix означает «the fixed point of a functor» (неподвижная точка функтора). Вооружившись Fix, мы можем переписать наши программы:

Fix (Output 'A' (Fix Done))              :: Fix (Toy Char)
Fix (Bell (Fix (Output 'A' (Fix Done)))) :: Fix (Toy Char)

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

Давайте попробуем решить эту проблему. Наша процедура завершается, но мы не готовы вызывать Done, вместо этого мы будем выбрасывать исключение, чтобы вызывающая процедура могла обработать его и продолжить исполнение:

data FixE f e = Fix (f (FixE f e)) | Throw e

Функция-обработчик будет выглядеть следующим образом:

catch (Fucntor f) => FixE f e1 -> (e1 -> FixE f e2) -> FixE f e2
catch (Fix x) f = Fix (fmap (flip catch f) x)
catch (Throw e) f = f e

Для того, чтобы использовать её нужно сделать Toy экземпляром класса Functor:

instance Functor (Toy b) where
    fmap f (Output x next) = Output x (f next)
    fmap f (Bell     next) = Bell     (f next)
    fmap f  Done           = Done

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

data IncompleteException = IncompleteException
-- output 'A'
-- throw IncompleteException
subroutine = Fix (Output 'A' (Throw IncompleteException))
           :: FixE (Toy Char) IncompleteException
-- try {subroutine}
-- catch (IncompleteException) {
--     bell
--     done
-- }
program = subroutine `catch` (_ -> Fix (Bell (Fix Done))) :: Fix (Toy Char) e

Монада Free. Часть 1

Мы с гордостью упаковываем «улучшенный» Fix и публикуем на Hackage под именем fix-impoved, после чего обнаруживаем, что используется он не совсем так как мы предполагали: пользователи вместо исключений передают нормальные значения. Да как они смеют! Исключения только для исключительных ситуаций! Что за болваны!
… хотя, неизвестно кто есть кто, потому что наш FixE уже реализован и называется Free:

data Free f r = Free (f (Free f r)

instance (Functor f) => Monad (Free f) where
    return = Pure
    (Free x) >>= f = Free (fmap (>>= f) x)
    (Pure r) >>= f = f r

return — наш Throw и (>>=) — catch. Пользователи разумно применяли исключения для передачи нормальных значений.
Замечательный аспект haskell — это бесплатная возможность использования do-нотации для любых монад. Но для того, чтобы использовать do-нотацию с командами нашего языка, нам нужно поменять их типы с Toy b на Free (Toy b). Выглядеть это будет так:

output :: a -> Free (Toy a) ()
output x = Free (Output x (Pure ()))

bell :: Free (Toy a) ()
bell = Free (Bell (Pure ()))

done :: Free (Toy a) r
done = Free Done

Заметили общий паттерн?

liftF :: (Functor f) => f r -> Free fr
liftF command = Free (fmap Pure command)

output x = liftF (Output x ())
bell     = liftF (Bell     ())
done     = liftF  Done

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

subroutine :: Free (Toy Char) ()
subroutine = output 'A'

program :: Free (Toy Char) r
program = do
        subroutine
        bell
        done

Именно здесь начинается магия. Наша программа в do-нотации — это чистые данные, которые мы можем интерпретировать. Новички часто ассоциируют монады с внешними эффектами, но код выше лишь генерирует данные. Мы можем показать это, написав функцию, которая будет переводить их в строковое представление:

showProgram :: (Show a, Show r) => Free (Toy a) r -> String
showProgram (Free (Output a x)) =
    "output " ++ show a ++ "n" ++ showProgram x
showProgram (Free (Bell x)) =
    "belln" ++ showProgram x
showProgram (Free Done) =
    "donen"
showProgram (Pure r) =
    "return " ++ show r ++ "n"

и запустим её

>>> putStr (showProgram program)
output 'A'
bell
done

Похоже мы только что написали наш первый интерпретатор. Мы можем использовать его, чтобы проверить, что наша монада подчиняется некоторым законам:

pretty :: (Show a, Show r) => Free (Toy a) r -> IO ()
pretty = putStr . showProgram

>>> pretty (output 'A')
output 'A'
return ()

>>> pretty (return 'A' >>= output)
output 'A'
return ()

>>> pretty (output 'A' >>= return)
output 'A'
return ()

>>> pretty ((output 'A' >> done) >> output 'C')
output 'A'
done

>>> pretty (output 'A' >> (done >> output 'C'))
output 'A'
done

Обратите внимание как Done «проглатывает» все команды, следующие за ней. Я включил Done в Toy только для иллюстрации. В большинстве случаев нам не нужен подобный конструктор, а достаточно поведения, обеспечиваемого Pure, то есть возможности продолжения исполнения, однако могут быть исключения.

Мы также можем написать интерпретатор в его традиционном значении:

ringBell :: IO () -- возможно, есть библиотеки, реализующие это

interpret :: (Show b) => Free (Toy b) r -> IO ()
interpret (Free (Output b x)) = print b  >> interpret x
interpret (Free (Bell     x)) = ringBell >> interpret x
interpret (Free  Done       ) = return ()
interpret (Pure r) = throwIO (userError "Improper termination")

Монаде Free неважно как вы собираетесь её использовать.

Многозадачность

Предположим, что у нас есть два монадических «потока» и мы хотим чередовать шаги их выполнения. В случае IO монады, мы бы могли использовать forkIO, просто запуская их параллельно, однако, что если нам нужно сделать то же самое для State или даже Cont монад. Можно попробовать представить поток как список монадических действий:

type Thread m = [m ()]

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

data Thread m r = Atomic (m (Thread m r)) | Return r

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

atomic :: (Monad m) => m a -> Thread m a
atomic m = Atomic $ liftM Return m

Теперь нужно сделать Thread монадой: мы «притворимся», что склеиваем два потока, но сохраняя при этом атомарность каждого шага, чтобы в дальнейшем была возможность чередовать их с шагами других потоков:

instance (Monad m) => Monad (Thread m) where
         return = Return
         (Atomic m) >>= f = Atomic (liftM (>>= f) m)
         (Return r) >>= f = f r

Используя это, мы можем создавать потоки, состоящие из атомарных шагов:

thread1 :: Thread IO ()
thread1 = do
        atomic $ print 1
        atomic $ print 2

thread2 :: Thread IO ()
thread2 = do
    str <- atomic $ getLine
    atomic $ putStrLn str

Все что осталось сделать, это реализовать чередование двух потоков, сохранив атомарность отдельных шагов. Давайте напишем простейшую реализацию:

interleave :: (Monad m) => Thread m r -> Thread m r -> Thread m r
interleave (Atomic m1) (Atomic m2) = do
    next1 <- atomic m1
    next2 <- atomic m2
    interleave next1 next2
interleave t1 (Return _) = t1
interleave (Return _) t2 = t2

Теперь нам нужно научиться запускать результирующие потоки:

runThread :: (Monad m) => Thread m r -> m r
runThread (Atomic m) = m >>= runThread
runThread (Return r) = return r

>>> runThread (interleave thread1 thread2)
1
[[Input: "Hello, world!"]]
2
Hello, world!

Магия! Мы только что реализовали простейшую систему управления потоками. Попробуйте теперь использовать её с чистой монадой State.

Монада Free. Часть 2

Если вы были внимательны, то могли заметить, что Thread — это завуалированный Free и atomic — liftF. Этот пример хорошо демонстрирует насколько близки свободные монады и списки. В самом деле, сравните определения Free и List:

data Free f r = Free (f (Free f r)) | Pure r
data List a   = Cons  a (List a  )  | Nil

Другими словами, мы можем думать о свободной монаде как о списке функторов. Конструктор Free ведет себя как Cons, добавляя функтор к списку и Pure — как Nil, символизируя пустой список (отсутсвие функторов).

Если List — это список значений и свободная монада — это список функторов, что произойдет, если эти функторы сами будут значениями:

type List' a = Free ((,) a) ()

List' a
= Free ((,) a) ()
= Free (a, List' a) | Pure ()
= Free a (List' a) | Pure ()

Получается обыкновенный список.

Таким образом, список — это частный случай монады Free. Тем не менее, [] как экземпляр класса Monad отличается от List' a (т.е. Free ((,) a)). В монаде List' a, join (прим. перев.: видимо, имеется в виду bind) ведет себя как (++) и return — как []. Вы можете думать о монаде List' a как о необычном способе конкатенации значений, используя do-нотацию.

Когда вы думаете о свободной монаде как о списке, многие вещи становятся более очевидными. Например, liftF представляется списком с единственным элементом, создающим свободную монаду, содержащую один функтор:

singleton x = Cons x Nii -- x:[] или [x]
liftF x = Free (fmap Pure x)

Аналогично, функция interleave — это слияние списков:

merge (x1:xs1) (x2:xs2) = x1:x2:merge xs1 xs2
merge xs1 [] = xs1
merge [] xs2 = xs2

-- на самом деле больше напоминает:
-- [x1] ++ [x2] ++ interleave xs1 xs2
interleave (Atomic m1) (Atomic m2) = do
next1 <- liftF m1
next2 <- liftF m2
interleave next1 next2
interleave a1 (Return _) = a1
interleave (Return _) a2 = a2

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

Это не совпадение, что Free монады схожи со списками. При рассмотрении теории категории, можно понять, что и те, и другие являются свободными объектами, где списки — это свободные моноиды, а Free монады — это свободные монады.

Интерпретаторы. Продолжение

В первой части я представил концепцию использования свободных монад в интерпретаторах, но потенциал этой идеи намного больше, чем может показаться — она не ограничена компиляторами и форматированным выводом. В качестве примера, предположим вы решили превзойти Notch с его идеей игры 0x10c, написав игру с возможностью программирования в ней на haskell. Вы хотите позволить игрокам запускать их программы, но при этом ограничить полный доступ к IO монаде. Каковы ваши действия?

Вы бы могли использовать оригинальный дизайн haskell, в котором вывод был бы представлен как список запросов ко внешнему миру и ввод — как список ответов, полученных из него:

main :: [Response] -> [Request]

Тип Request — это перечисление всех действий, которые вы можете совершить, а Response — полученные результаты. Для нашей игры набор запросов мог бы быть следующим:

data Request =
     Look Direction
   | ReadLine
   | Fire Direction
   | WriteLine String

… и набор ответов:

data Response=
     Image Picture     -- ответ на Look
   | ChartLine String  -- ответ на Read
   | Succeed Bool      -- ответ на Write

Можно с уверенность заявить, что такой подход не сработает. У нас нет никакого явного соответствия между запросами и ответами (у Fire и вовсе нет ответа), и совершенно неясно, что произойдет, если мы попытаемся получить ответ прежде, чем отправим запрос.

Давайте попробуем установить это соответствием объединив эти типы в один:

data Interaction next =
    | Look Direction (Image -> next)
    | Fire Direction next
    | ReadLine (String -> next
    | WriteLine String (Bool -> next)

У каждого конструктора есть поля, которые игроку нужно заполнить (параметры запросы). Игрок также может передавать функции, которые интерпретатор применит к полученным ответам. Вы можете думать о типе Interaction, как о контракте между программистом и интерпретатором для каждого отдельного шага.

Без труда можно сделать Interaction экземпляром класса Functor:

instance Functor Interaction where:
     fmap f (Look dir g) = Look dir (f . g)
     fmap f (Fire dir x) = Fire dir (f x)
     fmap f (ReadLine g) = ReadLine (f . g)
     fmap f (WriteLine s g) = WriteLine s (f . g)

На самом деле нет необходимости делать это самостоятельно. GHC предоставляет расширение DeriveFunctor, которое позволяет просто написать:

data Interaction ... deriving (Functor)

И достичь желаемого результата.
Как и раньше, мы можем создать список действий, используя монаду Free:

type Program = Free Interaction

С этим типом, игрок может написать простую программу:

easyToAnger = Free $ ReadLine $ s -> case s of
     "No" -> Free $ Fire Forward
           $ Free $ WriteLine "Take that!" (_ -> easyToAnger)
     -    -> easyToAnger

Теперь эта программа может быть запущена, возможно путем ее конвертации в гипотетическую монаду Game:

interpret :: Program r -> Game r
interpret prog = case prog of
    Free (Look dir g) -> do
        img <- collectImage dir
        interpret (g img)
    Free (Fire dir next) -> do
        sendBullet dir
        interpret next
    Free (ReadLine g) -> do
        str <- getChatLine
        interpret (g str)
    Free (WriteLine s g) ->
        putChatLine s
        interpret (g True)
    Pure r -> return r

Так как мы используем Free монаду, можем угостить игрока синтаксическим сахаром, позволив ему писать программы в do-нотации:

look :: Direction -> Program Image
look dir = liftF (Look dir id)

fire :: Direction -> Program ()
fire dir = liftF (Fire dir ())

readLine :: Program String
readLine = liftF (ReadLine id)

writeLine :: String -> Program Bool
writeLine s = liftF (WriteLine s id)

Теперь игроку будет удобнее писать программы:

easyToAnger :: Program a
easyToAnger = forever $ do
    str <- readLine
    when (str == "No") $ do
        fire Forward
        _ <- writeLine "Take that!"
        return ()

В двух словах, мы предоставили игроку язык взаимодействия, который ограничивает его возможные действия, и в то же время сохранили синтаксический сахар и плюшки haskell. За нами же осталась полная свобода интерпретации программ игроков. Для примера, если бы я собрался выпустить завтра патч, который бы изменял игровой мир (и haskell имел механизмы горячей замены кода), я бы мог подменить интерпретатор, не прерывая при этом выполнение программ игроков.

Free монады. Часть 3

Свободная монада — лучший друг интерпретатора. Она «освобождает интерпретатор» насколько это возможно и при этом сохраняет необходимый минимум, чтобы оставаться монадой.

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

Выражение «освобождать интерпретатор» насколько это возможно" звучит как задача оптимизации, которую можно перефразировать как:

Какая монада наиболее гибкая для интерпретации, при условии, что это все еще монада

На самом деле, детальное рассмотрение понятия «свободы», при заданных ограничениях ведет к определению свободного объекта в теории категории, где это понятие формализовано. Свободная монада — это «наиболее свободный» объект, являющийся монадой.

Автор: vobo

Источник