Skip to the content.

継続

文献を紐解くと、 継続とは「これから行われるであろう計算をパッケージ化したもの」とある。

出典: なんでも継続

継続は一般的な概念であるがここではHaskellの継続渡しスタイルとCont Monadについて説明する

継続渡しスタイル

-- Another junior Haskell programmer
fac 0 = 1
fac n = n * fac (n-1)

-- Continuation-passing Haskell programmer
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)

fac = facCps id

出典: The Evolution of a Haskell Programmer

Contモナド

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

継続による計算の効率化

継続を使って短絡評価が実装できる

prod :: (Eq a, Num a) => [a] -> a
prod l = (`runCont` id) $ callCC (\k -> loop k l)
    where
    loop _ []     = return 1
    loop k (0:_)  = k 0
    loop k (x:xs) = do
        n <- loop k xs
        return (n * xs)

shift/reset

-- shift/reset for the Cont monad
shift :: ((a -> Cont s r) -> Cont r r) -> Cont r a
shift e = Cont $ \k -> e (return . k) `runCont` id
 
reset :: Cont a a -> Cont r a 
reset e = return $ e `runCont` id

出典: MonadCont done right

Symmetric Lambda Calculs

値(1 -> X)と継続(Y -> 0)は双対

Filinski, Andrzej. Declarative continuations and categorical duality. Univ., 1989.

米田埋め込み

The Yoneda embedding is familiar in category theory. The continuation passing transform is familiar in computer programming. They’re the same thing! Why doesn’t anyone ever say so?

出典: The Continuation Passing Transform and the Yoneda Embedding

CPSへの変換は米田埋め込みに対応している

cps :: forall a b r. (a -> b) -> ((b -> r) -> (a -> r))
cps = flip (.)

出典:CPS(継続渡し方式)変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ

論理学での継続

CPS変換は、二重否定による古典論理の直観主義論理への埋め込みにあたる。

出典: 継続渡しスタイル - Wikipedia