multi-promptな限定継続 in Haskell (失敗編＆成功編)

multi-promptな限定継続の方が型がわかりやすい件について。

なんだかshift/resetの型付けはむつかしいなーと思っていた。
限定継続のOCaml実装を見てみたくて、Olegさんのdelimccライブラリとその論文を眺めていた。
こちらはmulti-promptな限定継続といい、複数の限定継続を同時に扱える体系の実装なのだけど、こちらの方が型が分かりやすかった。

理論的基礎はDybvig, Peyton Jones, Sabryの論文で、cc-delcontというHaskell版の実装がHackageにある。この実装も indexed monad ではなく普通のモナドなので型は理解しやすいはず。

これらのライブラリでは、 newPrompt, pushPrompt, withSubCont, pushSubCont の 4つのプリミティブを使う。また扱うデータ型も、「プロンプト(Prompt)」「部分継続(SubCont)」の2種類がある。

mutil-prompt 限定継続に関する私の理解

ざっくりとした説明

Prompt
- 複数の限定継続を区別するための識別子
SubCont
- 限定継続そのもの。呼び出すには pushSubCont を使う

newPrompt
- 新しいpromptを作る
pushPrompt p
- resetのようなもの。限定継続の開始地点をpでマークする。pushSubCont するとこのマークは消えちゃう。
withSubCont p f
- shiftのようなもの(ちょっと違うけど)。 pushPrompt pでマークした箇所まで大域脱出しつつ、そこまでの限定継続(SubCont)に f を適用する。
- 大域脱出したら pushPrompt pのマークは消えちゃう。マークがない状態で withSubCont すると実行時エラー。
pushSubCont k
- 限定継続kを表す関数を返す。

shiftと同じような挙動を得たい場合はpushSubCont k e のすぐ外でもういちど pushPrompt する。すると、呼び出した限定継続の中で次のwithSubContが使われて大域脱出した場合にもそこに戻ってきてくれる。

使ってみた

先の例(mapをひっくり返す)を CC-delim を使って焼き直してみた。
Promptを持って回るためにちょっとややこしくなってしまった。

{-# LANGUAGE NoMonomorphismRestriction #-}

import Control.Monad.CC
import Control.Monad.Identity (Identity)

-- 再帰的な限定継続を保持する型
data Iter a = 
    Iter (SubCont a Identity Int (Iter a), Int) -- 限定継続と，何か整数を保持 
  | End [Int] -- おわり

pam :: Prompt ans (Iter ans) -> [Int] -> CC ans [Int]
pam _  []     = return []
pam p0 (x:xs) = do
  y <- withSubCont p0 (\k -> return $ Iter (k, x))
  ys <- pam p0 xs
  return (y:ys)

expr :: CC ans (Prompt ans (Iter ans), Iter ans)
expr = do 
  p0 <- newPrompt
  it <- pushPrompt p0 $ do
    xs <- pam p0 [1,2,3]
    return (End xs)
  return (p0, it)
    
iter :: (Int -> Int) -> (Prompt ans (Iter ans), Iter ans) -> CC ans [Int]
iter _ (_,End xs)      = return xs
iter f (p0,Iter (k,x))  = do 
  it <- pushPrompt p0 (pushSubCont k (return $ f x))
  iter f (p0,it)

main = mapM_ print [runCC $ iter id =<< expr, runCC $ iter (*10) =<< expr]

Haskellなので promptを渡して回らないといけないのが面倒(implicit parameterを使えばいいけど…)。また pushPrompt を忘れると実行時エラーになるので、少し扱いに気を遣う。

うまくいかなかった版

こちらはNG. expr と iter を別の runCC に入れてしまった．

{-# LANGUAGE NoMonomorphismRestriction #-}

import Control.Monad.CC
import Control.Monad.Identity (Identity)

-- 再帰的な限定継続を保持する型
data Iter a = 
    Iter (SubCont a Identity Int (Iter a), Int) -- 限定継続と，何か整数を保持 
  | End [Int] -- おわり

pam :: Prompt ans (Iter ans) -> [Int] -> CC ans [Int]
pam _  []     = return []
pam p0 (x:xs) = do
  y <- withSubCont p0 (\k -> return $ Iter (k, x))
  ys <- pam p0 xs
  return (y:ys)

expr :: CC ans (Iter ans)
expr = do 
  p0 <- newPrompt
  pushPrompt p0 $ do
    xs <- pam p0 [1,2,3]
    return (End xs)
    
iter :: (Int -> Int) -> Iter a -> [Int]
iter _ (End xs)      = xs
iter f (Iter (k,x))  = runCC $ do 
  it <- pushSubCont k (return $ f x); -- (*) ここで 外からもってきた subcont を使ってるのが駄目
  return (iter f it)

CC-delcont の継続モナドは CC ans a という型をもち、 runCC :: (forall ans. CC ans a) -> a によって実行できるが、だがちょっと待って欲しい。いわゆるContモナドと違うのは、 answer type (Cont r a の r) がforall束縛されている点だ。この束縛おかげで CC ans a から aが取り出せている…ともいえるのだけど、今回のように runCC から帰ってきた部分継続(限定継続)を別の runCC の中から呼び出せないのだ！ (型変数の動く範囲が runCC で限定されているため, (*) の k の SubCont ans ...) の ans と unify できない)

~~shift/reset の感覚で使ったのがまずかった。ちゃんと multi-prompt っぽく複数の promptを使えば似たようなことはできるはずだ。。。~~