More than 3 years have passed since last update.

継続モナドについて

Haskell

Posted at 2020-06-03

継続モナド

　継続渡しスタイルの関数をモナドのインスタンスにしたもの。Haskellで書くと以下のようなもの。

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

　これを用いると、Haskellのモナドに対する手厚いサポートを受けながら、継続渡しスタイルの恩恵を受けることができる。

継続モナドとは？

　継続モナドのHaskellコードを再掲する。分かりやすくするため、基底モナドの部分を削っている。

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

　(a -> r) -> rは、継続渡しスタイルの関数を一般化した型だ。
　単にaと書けばいいところを、わざわざその値を使った関数を受け取って適用するところまで面倒を見ている。
　このような形で書くと、関数呼び出しを単にジャンプに置き換える最適化をすることができたり、不要なパターンマッチを減らすことができるなどの恩恵を受けられる場合がある。また、コンパイラが最適化の一環としてコードを継続渡しスタイルに変換することもあるらしい。

継続渡しスタイルとは？

　ところで、継続渡しスタイルとはなんだろう。
　まずは具体例を見ていこう。下は、(+)を継続渡しスタイルに直した関数だ。接頭辞cpsはcontinuation passing styleの略であり、継続渡しスタイルを意味している。

cpsSum :: Int -> Int -> (Int -> r) -> r
cpsSum m n f = f $ m + n

　通常の関数としての処理をした後に、それを使った処理（継続）fを適用する形になっている。その関数の呼び出し後の処理（継続）を受け取って、それを適用してやるところまで面倒を見るのが継続渡しスタイルの特徴だ。
　最も単純な形は、下のような値を継続渡しスタイルに直したものになるだろう。例えば、cpsSum 10 20という式の型は、(Int -> r) -> rとなる。

cpsVal :: (Int -> r) -> r
cpsVal f = f 30

　継続渡しスタイルで少し遊んでみよう。下のような、値を継続渡しスタイルの値に変換する関数を作成する。

mkCps :: a -> (a -> b) -> b
mkCps a f = f a

　これらを使って、継続渡しスタイルを使って値を作成する一連の流れを作ることができる。最後のidは何もしない継続であり、唯一継続渡しスタイルではない関数だ。

>>> cpsVal $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
33

　ところでこの継続渡しスタイル、ケラー脳を働かせて目を細めてみると、段々$が>>=に見えてこないだろうか？

継続渡しスタイルをモナドのインスタンスにする

　前置きはこの辺にして、ContTをモナドのインスタンスにしていこう。

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

instance Monad (ContT r m) where
    return a = ContT $ \f -> f a
    ContT a >>= f = ContT $ \g -> a $ \a' -> runContT (f a') g

　returnの中でやっていることは、まさに値を継続にする関数mkCpsだ。return = ContT . mkCpsと書き換えてもよい。
　bindの中では、古い継続aに関数fを適用して、それに新しい継続gを添えてやっている。a $ \a' -> ..のくだりは、継続渡しスタイルの例でも見た、ある継続に次の継続を継ぎ足してやるときのお決まりの構造だ。

　FunctorやApplicativeは面倒なので手抜きの実装をしてしまおう。これで正式にモナドのインスタンスになった。

instance Functor (ContT r m) where
    fmap = liftM

instance Applicative (ContT r m) where
    pure = return
    (<*>) = ap

　ついでにモナディックではない値を扱いやすくするエイリアスを作ろう。

type Cont r a = ContT r Identity a

cont :: ((a -> r) -> r) -> Cont r a
cont f = ContT' $ Identity . f . fmap runIdentity

runCont :: Cont' r a -> (a -> r) -> r
runCont c f = runIdentity $ runContT c (Identity . f)

継続モナドを使う

　継続渡しスタイルをモナドのインスタンスに落とし込むことが何を意味するかといえば、「値を継続渡しスタイルにする」「継続渡しスタイルの関数に継続渡しスタイルの関数を継ぎ足す」という継続渡しスタイルの特徴を、モナドのメソッドに抽出することができたということだ。
　上でやった継続渡しの例を、モナドを使って書き直してみよう。

-- 生の継続渡し
>>> cpsVal $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
33

-- 継続モナドを使った継続渡し
>>> runCont (cont cpsVal >>= \a -> cont (cpsSum a 1) >>= \b -> return (b + 2)) id
33

　見た目がそっくりであることが分かるだろう。というのも、やっていることが各継続渡しスタイルの関数をラップして、最後にラップを剥がすだけなのだ。returnはContT . mkCpsであるため、これを書き換えている。
　>>=で繋げているということは、do文で書き下せるということだ。下のコードは、上の継続モナドを使った継続渡しと全く同等のコードである。

>>> flip runCont' id $ do
>>>     a <- cont' cpsVal
>>>     b <- cont' $ cpsSum a 1
>>>     return $ b + 2
33

　継続渡しの読みづらさが消えて、慣れ親しんだ形になった。これで、慣れ親しんだ構文と継続渡しのメリットが両立されることになった。

継続モナドとリソース管理

　私は、継続モナドが最も役に立つ場面は、リソース管理だと思っている。ここでは継続モナドを用いたリソース管理方法を紹介しよう。
　ここでのリソース管理は、open/closeと対になった関数があって、openしたリソースはcloseしなければならないアレだ。一番わかりやすいのはファイル操作だろう。
　Haskellでは、ファイルのオープン/クローズは以下のような関数を使う。これを使って、オープンしたハンドルを間違いなく閉じる関数を考えよう。

openFile :: FilePath -> IOMode -> IO Handle
hClose :: Handle -> IO ()

　handleを使う処理を引数に抜き出せば、こんな関数になるはずだ。この関数を使えば、どの二つの関数が対になっているかを考える必要はないし、hCloseが間違いなく実行されることが保証される。

withFile :: FilePath -> IOMode -> (Handle -> IO ()) -> IO ()
withFile filePath mode processHandle = do
    handle <- openFile filePath mode
    processHandle handle
        `finally`
        hClose handle

　ところで、この関数は部分適用すると(Handle -> IO ()) -> IO ()という型になることが分かる。これは継続渡しの型そのものではないか！
　さっそく継続モナドを使ってファイルリソース管理を行う処理を書いてみよう。
　下は、継続モナドを使ってファイルコピーをする例だ。特別なことをしてるようには見えないが、二つのファイルを開き、そのいずれもが正しく閉じられることが保証されている。

copyFile :: String -> String -> ContT () IO ()
copyFile srcFilePath destFilePath = do
    hSource <- ContT $ withFile srcFilePath ReadMode
    hDest <- ContT $ withFile destFilePath WriteMode
    content <- liftIO $ hGetContents hSource
    liftIO $ hPutStr hDest content

　そういうわけで、System.IO.withFileには全く同じ関数が用意されている。他にも対になる関数でリソース獲得/解放を提供するライブラリはwith*という命名の関数を用意していることが多い。

継続モナドとcallCC

継続の破棄

　継続渡しスタイルの関数は、引数に渡された継続に値を詰めて流す。それでは、もし値を継続に渡さなかったらどうなるだろうか？

>>> mkCps (0 :: Int) $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
3
>>> const (0 :: Int) $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
0

　const 0は、引数に何をもらっても0を返す関数だ。すなわち、引数にどのような継続をもらっても0を返す。
　これは継続渡しスタイルの言い方をすれば、途中で継続を破棄してしまうということだ。これは、手続き的には関数の途中でreturnをしてしまったり、あるいは例外が投げられた時のような状況が連想される。
　Contモナドを使うコードでは、以下に対応する。constに渡した値が最終的な値となり、以降の継続が破棄される。

>>> flip runCont id $ do
>>>     n <- cont $ const 2
>>>     return $ 10 + n
2

　見ての通り、無条件に継続を破棄してしまうだけで、あまり役に立たない。そこで、現在の継続を渡して呼び出し、継続が終了した時点での継続を引き継ぐことができるような関数を考える。

callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT $ \g ->
    runContT (f $ ContT . const . g) g

　ContT . const . gの部分に、継続の破棄が表れている。gはcallCCを呼んだ後の継続であり、fの引数であるexitを呼びだした時にその時点で残りの継続を破棄する。
　さっそく使ってみよう。

>>> flip runCont id $ do
>>>     n <- callCC $ \exit -> do
>>>         exit 2
>>>         return 3
>>>     return $ n * 5
10

　exitの時点で継続を打ち切り、callCCの外へと処理が飛んでいるのが分かる。
　ここでconstを使ったらどうなるだろうか？

>>> flip runCont id $ do
>>>     n <- callCC $ \exit -> do
>>>         cont $ const 2
>>>         exit 3
>>>     return $ n * 5
2

　なるほどね。

継続の取り出し

　ところで、こんな化け物のような関数を定義することができる。

getCC :: ContT r m (ContT r m a)
getCC = callCC $ \exit ->
    let a = exit a
     in return a

　これを使うと、継続を取り出すことができる。取り出した継続は、文字通りその後の継続であるため、これを継続に加えると事実上のループを作ることができる。
　下は、標準入力から"bye"を受け取るまで処理を繰り返す例だ。

do  goto <- getCC
    line <- lift getLine
    lift $ putStrLn line
    when (line /= "bye")
        goto

　また、継続を実行した後の値を同時に返すように改変することができる。

getCC' :: a -> ContT r m (a, a -> ContT r m b)
getCC' a = callCC $ \exit ->
    let f b = exit (b, f)
     in return (a, f)

　これはより分かりやすい例を提供する。

do  (x, goto) <- getCC' 0
    lift $ print x
    when (x < 10) $
        goto $ x + 1

　継続渡しによるループからは、最適化された末尾再帰を直接実装しているような印象を受ける。
　このように、継続をオブジェクトとして引き回す力を持つcallCCは、MonadCont型クラスのメソッドにもなっている。

class MonadCont m where
    callCC :: ((a -> m b) -> m a) -> m a

まとめ

　継続渡しスタイルとそれをモナドにしたContT、これを利用したリソース管理の方法、そして継続という考え方の応用であるcallCCについて勉強した。継続は制御構造を一般化したもの（らしい）ので、条件分岐や例外、ループをも再現することができる。
　本当はreset/shiftについても書きたかったが、力尽きたのでここまで。

　それではさようなら。