Продолжения в Haskell

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

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

Программирование в стиле продолжений


Для начала, посмотрим что такое продолжение и программирование в стиле продолжений.

Обычные функции:

square :: Int -> Int
square x = x*x

incr :: Int -> Int
incr x = x+1

func :: Int -> Int
func x = square (incr x)


А теперь в стиле продолжений:

square_cps :: Int -> (Int -> r) -> r
square_cps x k = k (x*x)

incr_cps :: Int -> (Int -> r) -> r
incr_cps x k = k (x+1)

func_cps :: Int -> (Int -> r) -> r
func_cps x k = incr_cps x $ \inc ->
               square_cps inc $ \sq ->
               k sq

Теперь функции кроме непосредственно аргументов принимают на вход функцию, которая будет применена к результату. Это и есть продолжение.
С помощью продолжений мы можем соединять функции, что и происходит в func_cps. Сначала выполняется incr_cps, и её результат «попадает» в продолжение (\inc -> ...), потом вызывается square_cps чей результат передаётся продолжению (\sq -> ...), который наконец отдаётся самому внешнему продолжению k.

Продолжения здесь имеют тип (Int -> r) так как не обязательно, что продолжение вернёт Int.
Например, чтобы вывести результат на консоль, мы можем передать print в качестве продолжения:

main = func_cps 5 print

Монада Cont


Можно заметить некоторые закономерности в стиле продолжений.
К примеру, простые функции, такие как square_cps и incr_cps, мы объявляли похожим образом:

function ... = \k -> k (...)

А соединяли мы их так:

fun1 ... $ \r1 ->
fun2 ... $ \r2 -> ...

Всё это напоминает нам о монадах, первый пример похож на return, а второй на >>=.

Введём монаду Cont как:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Но почему (a -> r) -> r?
Дело в том, что когда мы писали функции в стиле продолжений, каждая функция брала дополнительный параметр, продолжающий вычисление.
Если мы «заполним» функцию в стиле продолжений аргументами (до самого продолжения), её тип будет (a -> r) -> r, где a — тип результата функции, если бы мы просто возвратили его, без передачи продолжению, а r — тип результата, который вернёт продолжение:

> :t square_cps 5
square_cps :: (Int -> r) -> r


Попробуем сделать Cont монадой.

instance Monad (Cont r) where
    return n = Cont $ \k -> k n
    ...

return n — это Cont который сразу применяет n к продолжению, которое он получил.

    m >>= f  = Cont $ \k -> runCont m (\a -> runCont (f a) k)

m >>= f — это Cont который запускает (runCont просто «распаковывает» Cont, освобождая функцию) m с продолжением (\a -> runCont (f a) k), которое может быть получит результат вычисления, и присвоит его a (а может и не получит, ведь функция может проигнорировать продолжение). Потом, a будет применено к f, чтобы получить другой Cont, который, в свою очередь, будет запущен с самым внешним продолжением k.

Перепишем нашу программу с использованием монады Cont:

square_Cont :: Int -> Cont r Int 
square_Cont x = return (x*x)

incr_Cont :: Int -> Cont r Int
incr_Cont x = return (x+1)

func_Cont :: Int -> Cont r Int func_Cont x = do inc <- incr_Cont x sq <- square_Cont inc return sq

main = runCont (func_Cont 5) print

Теперь всё выглядит намного понятней.

Перейдём к функциям, работающим с Cont.

callCC


Начнём с простого примера:

square :: Int -> Cont r Int
square n = callCC $ \k -> k (n*n)


Что за бесполезная функция? Больше похоже будто это просто синоним для конструктора Cont.
Но всё не так просто. Посмотрим на тип callCC:

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

По настоящему, callCC берёт функцию, которая принимает другую функцию, типа (a -> Cont r b), а возвращает Cont r a. То есть, k (n*n) в нашем примере имеет тип Cont r Int.
Для чего можно использовать callCC? Например, для быстрого выхода из функции:

import Control.Monad (when)

hehe :: Int -> Cont r String
hehe n = callCC $ \exit -> do
    let fac = product [1..n]
    when (n > 7) $ exit "OVER 9000"
    return $ show fac

main = do n <- fmap read getLine
          runCont (hehe n) putStrLn

Опробуем нашу программу:

> main
3
6
> main
10
OVER 9000


Эта программа вычисляет факториал, и если он оказывается больше 9000, возвращает сообщение «OVER 9000», а если нет, то просто его значение.
Здесь мы использовали exit как return в императивных языках — он прервал вычисление и вывел другой результат.

Также возможно использование вложенных callCC-блоков:

bar :: String -> Cont r String
bar s = do
    callCC $ \exit1 -> do
        let ws = words s
            names = foldl (\a c -> a ++ ", " ++ c) (head ws) (tail ws)
        r' <- callCC $ \exit2 -> do
            when (null ws) $ exit1 "No people"
            when (length ws == 1) $ exit2 "There is "
            return "There are: "
        return $ r' ++ names

main = do ns <- getLine
          runCont (bar ns) putStrLn

Попробуем:

> main

No people
> main
Bob
There is Bob
> main
Bob Alice
There are: Bob, Alice


Если список имён пустой, то вызываем exit1 "No people", «перепрыгивая» через внутренний блок.
Если человек один, используем «There is », если их много, то «There are: ».
Заметьте, что когда вычисление доходит до return в callCC-блоке, то результат возвращается как обычно.

Так как же реализована функция callCC? Давайте посмотрим:

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

Начинается она по обычному, с оборачивания функции в стиле продолжений в Cont. Потом (f (\a -> Cont $ \_ -> k a)) запускается с продолжением k.
(\a -> Cont $ \_ -> k a) — это функция, которая берёт что-то и возвращает Cont, игнорирующий своё продолжение и использующий k взамен.

Проследим как это работает:

square n = callCC $ \k -> k (n*n)
= Cont $ \k' -> runCont ((\k -> k (n*n)) (\a -> Cont $ \_ -> k' a)) k'
= Cont $ \k' -> runCont ((\a -> Cont $ \_ -> k' a) (n*n)) k'
= Cont $ \k' -> runCont (Cont $ \_ -> k' (n*n)) k'
= Cont $ \k' -> (\_ -> k' (n*n)) k'
= Cont $ \k' -> k' (n*n)


Всё как мы и ожидали. Рассмотрим случай посложнее:

hehe :: Int -> Cont r String
hehe n = callCC $ \exit -> do
    let fac = product [1..n]
    when (n > 7) $ exit "OVER 9000"
    return $ show fac
= callCC $ \exit -> (when (n > 7) $ exit "OVER 9000") >> (return $ show (product [1..n])) -- Здесь я убрал let для простоты
= Cont $ \k -> runCont ((\exit -> (when (n > 7) $ exit "OVER 9000") >> (return $ show (product [1..n]))) (\a -> Cont $ \_ -> k a)) k
= Cont $ \k -> runCont ((when (n > 7) $ (\a -> Cont $ \_ -> k a) "OVER 9000") >> (return $ show (product [1..n]))) k
= Cont $ \k -> runCont ((when (n > 7) $ (Cont $ \_ -> k "OVER 9000")) >> (return $ show (product [1..n]))) k

Когда when сработает, он вернёт (Cont $ \_ -> k "OVER 9000"). Этот Cont не использует своё продолжение, значит и остальная часть кода не выполнится.

getCC


Функции getCC и getCC' позволяют нам «добыть» текущее продолжение и использовать его чтобы вернуться в предыдущее состояние программы.
Например:

foo :: Int -> Cont r String
foo s = do (i, back) <- getCC' s
           when (i < 20) $ back (i*2)
           return $ show i

foo удваивает свой аргумент пока он не станет больше или равным 20.

> runCont (foo 5) id
"20"
> runCont (foo 3) id
"24"
> runCont (foo 2) id
"32"


(i, back) <- getCC' s — присваивает i значение s и создаёт «ссылку» на это место.
back (i*2) — возвращается в прошлое состояние, но с i равной i*2.

Всё это сильно напоминает goto, правда здесь мы можем перемещаться только в прошлые состояния.

Функция getCC' объявлена так:

getCC' ::  t -> Cont r (t, t -> Cont r a)
getCC' x0 = callCC (\c -> let f x = c (x, f) in return (x0, f))

Попробуем разобраться. Начнём её упрощать:

getCC' x0 = Cont $ \k -> runCont ((\c -> let f x = c (x, f) in return (x0, f)) (\a -> Cont $ \_ -> k a)) k
= Cont $ \k -> runCont (let f x = (\a -> Cont $ \_ -> k a) (x, f) in return (x0, f)) k
= Cont $ \k -> runCont (let f x = Cont $ \_ -> k (x, f) in return (x0, f)) k
= Cont $ \k -> runCont (let f x = Cont $ \_ -> k (x, f) in Cont $ \k' -> k' (x0, f)) k
= Cont $ \k -> let f x = Cont $ \_ -> k (x, f) in k (x0, f)


Функция f применяет пару из своего аргумента и себя к внешнему (getCC'-шному) продолжению, и оборачивает это в Cont.
А k (x0, f) — применяет пару из аргумента getCC' и f к внешнему продолжению.
Когда мы вызываем f в другом месте, он возвращает Cont, использующий не текущее продолжение, а то, которое было текущим для getCC'. Таким образом, мы как-бы возвращаемся в прошлое состояние.

Также, у getCC' есть «младший брат» — getCC, но он полезен только с ContT (трансформер для Cont):

import Control.Monad (when)
import Control.Monad.Cont

getCC :: MonadCont m => m (m a)
getCC = callCC (\c -> let x = c x in return x)

foo ::  ContT () IO ()
foo = do back <- getCC
         liftIO $ putStr "Do you want to coninue? [y/n] "
         a <- liftIO $ getLine
         when (a == "y" || a == "Y") $ back

main = runContT foo return

> main
Do you want to coninue? [y/n] y
Do you want to coninue? [y/n] y
Do you want to coninue? [y/n] n
>


Программа будет спрашивать у пользователя разрешения на продолжение, пока он не ответит «n».
Отсюда видно, что getCC только позволяет вернуться в прошлое состояние, но не даёт возможности передать аргументы.

Где мне использовать Cont?


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

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

Список используемых материалов


Continuation passing style
Goto in Haskell
Making Haskell programs faster and smaller
Поделиться публикацией
Похожие публикации
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 20
    +4
    http://horna.org.ua/books/All_About_Monads.pdf

    > Abuse of the Continuation monad can produce code that is impossible to understand and maintain.
      0
      Было бы классно, если бы имелся какой-нибудь веб-фреймворк для Haskell, использующий продолжения (Is anyone using delimited continuations to do web development in Haskell?)

      Продолжения – шикарная вещь для удобного и быстрого построения веб-логики и интерфейса приложения, сохраняющего состояния. В этом плане себя прекрасно показывает веб-сервер языка Racket.
        0
        Не могли бы вы пояснить, что такого шикарного предлагают продолжения веб-разработке?
          +1
          Можно записать логику с показом множества форм как обычную последовательность действий. Примерно так:

          Начинаем нечто
          call-cc form1
          продолжаем имея результаты form1
          call-cc form2
          продолжаем уже и с form2

          framework обеспечивает возврат после form1/form2.

            –2
            Я с веб-разработкой не очень знаком, можно каким-нибудь более простым языком?
            0
            ПФП #7, страница 130. Лучше читать статью с начала.
              0
              Понятно.

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

              > мы не можем нарастить производительность системы добавлением нового сервера с балансировкой веб-запросов в кластере. Потому что все запросы клиента в пределах одной пользовательской сессии должны попадать на ту машину, где она была создана.
                0
                Некоторые фреймворки (ЕМНИП в racket) пропихивают продолжения через кукисы, как вы без продолжений будете делать то же с промежуточными данными формы.
            +1
            Stateful веб-приложения — зло. Стейты интерфейса на продолжениях не исключение. Не нужно городить такой слой абстракций, аукнется.
              +1
              А в чём их проблема?
                0
                Если коротко: использование stateful архитектуры влечет за собой не оправданное в большинстве случаев усложнение архитектуры.

                Протокол http по своей натуре stateless. Для имитации сеансового общения с состоянием (сессии) в любом случае приходится делать хаки. Это или проставление специального хедера с идентификатором сессии, либо специальное поле в передаваемых данных, ну или конечно же встроенный механизм на основе кук. Однако нужно понимать, что это скорее для исключительных ситуаций, где без стейта уже никак, например авторизация пользователя. Не зря же существует вообще REST-архитектура.

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

                Одно дело, если имеем в виду толстое интерпрайзное приложение, в котором до черта многостраничных форм, то тут да, наверное стоит приложение сделать stateful и настравивать репликацию сессий на выбранном аппсервере. Но тут уже сложившийся набор технологий.
                  0
                  Хм… 80% приложений даже в теории никогда не должны вырасти за пределы возможностей одной машины. Кроме того никто не отменял вертикального масштабирования.
              +2
              Авторитет, безусловно нельзя считать особым аргументом, но вот, что говорит Снойман, автор Yesod (одного из заметных вебных фреймворков на хаскеле)
                0
                Все правильно он пишет: продолжения противоречат REST. Нужен или не нужен REST, вопрос уже другой и каждый в зависимости от своих условий должен выбрать сам.
              +1
              Не понял. В выражении callCC $ \k -> k (чёнибудь) k имеет тип (a -> Cont r b), то есть возвращает продолжение со входом отличным от чёнибудь. При этом возвращаемое замыканием значение имеет тип Cont r a. То есть тип чёнибудь. Получается что типы построенного с помощью k продолжения и продолжения, которое будет возвращено (пипец, мне бы хоть окурочек от того косяка, что это породил) отличаются. Как такое может получиться?
                0
                Понял, никто не мешает как-то манипулировать с тем что пришло из продолжения. По способности выедать время хаскель рвёт любую игру как тузик грелку.
                –1
                После прочтения хочется воскликнуть: о Боже, ну зачем так усложнять простую вещь?
                  0
                  Нет. Ну а к чему минус? Вот смотрите, вызовам с продолжениям в руководстве по lisp уделена пара страничек. И этого достаточно, чтобы понять и пользоваться. В Haskell же монады, мозговыворачивательные ограничения на типы и т.д. Какой смысл в этом? Я вот действительно не понимаю. Тем более, что если судить по Real World Haskell это всё нисколько не упрощает программирование, а только запутывает его. So why so overcomplicated?
                  0
                  square_Cont :: Int -> Cont r Int
                  -- square_Cont x = return (x*x)
                  square_Cont = return . join (*)
                  
                  incr_Cont :: Int -> Cont r Int
                  -- incr_Cont x = return (x+1)
                  incr_Cont = return . (+1)
                  
                  func_Cont :: Int -> Cont r Int
                  {-
                  func_Cont x = do inc <- incr_Cont x
                                   sq <- square_Cont inc
                                   return sq
                  -}
                  func_Cont = (square_Cont =<<) . incr_Cont
                  


                  > Эта программа вычисляет факториал, и если он оказывается больше 9000, возвращает сообщение «OVER 9000», а если нет, то просто его значение.
                  Эта программа возвращает строку «OVER 9000» для n > 7, а для остальных n возвращает строку с n!..

                  foo :: Int -> Cont r String
                  foo s = do (i, back) <- getCC' s
                             when (i < 20) $ back (i*2)
                             return $ show i
                  


                  А зачем тут String?
                  Что такое getCC' и откуда?
                    0
                    Как я вижу, Вы сделали некоторые функции короче. Конечно можно и так, но цель моего «развёрнутого» кода в том, что можно проследить взаимосвязь между использованием продолжений как обычных функций, и как монад.
                    Сравните:
                    func_cps :: Int -> (Int -> r) -> r
                    func_cps x k = incr_cps x $ \inc ->
                                   square_cps inc $ \sq ->
                                   k sq
                    
                    и
                    func_Cont :: Int -> Cont r Int
                    func_Cont x = do inc <- incr_Cont x
                                     sq <- square_Cont inc
                                     return sq
                    

                    Да, эта программа не учитывает само значение факториала, просто для n>7 факториал больше 9000.

                    String тут потому, что в конце мы возвращаем show i, т.е. строковое представление числа.

                    getCC' — это вариант getCC, с помощью которого можно ещё и передать состояние. Грубо говоря, getCC' возвращает нам пару из текущего состояния вычисления (число в данном случае) и функции, которая берёт новое состояние и возвращает вычисление в заданную точку (как goto). В статье есть больше про getCC и getCC' + объяснение как они работают.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое