Продолжения в 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