限定継続 - haskell-shoen

限定継続

継続を扱うインターフェイスの一つ。多くの場合、shiftとresetというプリミティブからなる。理解を容易にするため、明示的に継続を型で扱うような例を紹介する。

code:haskell

shift :: Prompt r -> ((m a -> m r) -> m r) -> m a

reset :: (Prompt a -> m a) -> m a

resetは、Prompt a型の値を作成し、関数に渡す。Prompt aは、結果としてaを返すような計算の存在を示唆する。

shiftは、ごくごく単純化して言えば脱出関数を作成する。どこへ脱出するかはresetで作成したPromptによって参照する。

脱出関数によって飛ばした未来は、resetの最後に再生する。

code:haskell

test = do

y <- reset $ \tag -> do

putStrLn "Before shift"

r <- shift tag $ \k -> do

putStrLn "Before continuation"

p <- k (putStrLn "Returning a result" >> pure 42)

putStrLn "After continuation"

pure p

putStrLn "After shift"

pure r

print y

出力は以下のようになる。

code:text

Before shift

Before continuation

Returning a result

After shift

After continuation

Haskellによる実装としてCC-delcontがあり、計算を細かく分割して線形リストとして扱うことによってこのような柔軟な操作を実現した。

Schemeのような処理系レベルのサポートとは無縁だったが、2020年2月22日に転機が訪れる。GHCのRTSを少々変更することにより限定継続をGHCのプリミティブとして提供するプロポーザルが提出された。

code:haskell

prompt#

:: forall (a :: Type)

. (State# RealWorld -> (# State# RealWorld, a #))

-> State# RealWorld -> (# State# RealWorld, a #)

control0#

:: forall (a :: Type) (r :: RuntimeRep) (b :: TYPE r)

. (((State# RealWorld -> (# State# RealWorld, b #))

-> State# RealWorld -> (# State# RealWorld, a #))

-> State# RealWorld -> (# State# RealWorld, b #)

非常に見づらい型だが、IOモナドにするとシンプルである。

code:haskell

unsafePrompt :: IO a -> IO a

unsafeControl0 :: ((IO b -> IO a) -> IO a) -> IO b

TBD: shiftとcontrol0の違い

これを応用すると、中身はIOモナドであり、例外処理や並行処理に融通が効くという性質を残しながら、計算を中断し保存できるコルーチンの性質も付与するという常識破りな真似ができるようになる(fumieval/coroutine)。