限定継続 in Haskell 98 by Oleg Kiselyov
限定継続フェスタ があると聞きまして,私もちょっぴり勉強しています。 Schemeには馴れていないし、僕のPCには処理系も入ってないので、Haskellでやります。
Olegさんの投稿 (http://www.mail-archive.com/haskell@haskell.org/msg20758.html ) から、Haskll98で動作する 限定継続の実装が手に入ります。浅井先生・亀山先生の型システムを実装したものらしいです。
細かいことはわかりませんが、モナドはわかるのでためしてみます。
$ ghci ShiftResetGenuine.hs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. [1 of 1] Compiling ShiftResetGenuine ( ShiftResetGenuine.hs, interpreted ) Ok, modules loaded: ShiftResetGenuine. *ShiftResetGenuine> flip unC id (reset (ret 1 `bind` (\x-> shift (\k->ret 2) `bind` (\y-> ret (x+y))))) 2 *ShiftResetGenuine> flip unC id (reset (ret 1 `bind` (\x-> shift (\k->k 2) `bind` (\y-> ret (x+y))))) 3 *ShiftResetGenuine>
素晴らしい。何が素晴らしいって、ちゃんと型推論がはたらく事です。
GHCのrebindable syntaxの機能を使えば do記法でも書けそうだ。
Delimited Continuation with do-notation
GHC で -fno-implicit-prelude オプションを与えると do記法を再定義できる。 上の Delimited Continuationをdo記法で書いてみた。 こんな感じかなあ
{- ghciかghcに -fno-implicit-prelude (GHC6.6以前?) か -XNoImplicitPrelude (GHC6.8以降?) を指定すること -} import ShiftResetGenuine import Prelude hiding ((>>=),(>>),return) m >>= f = m `bind` f m >> n = m >>= (\_ -> n) return x = ret x -- reset (+ 1 (shift k 2)) dtest1 = reset $ do x <- return 1 y <- shift $ \k -> return 2 return $ x+y -- reset (+ 1 (shift k (k 2))) dtest2 = reset $ do x <- return 1 y <- shift $ \k -> k 2 return $ x+y -- (cons 1 (reset (cons 2 (shift k -- (cons 3 (k (cons 4 '()))))))) dtest3 = do x <- reset $ do y <- shift $ \k -> do z <- k [4] return $ 3:z return $ 2:y return $ 1:x -- (+ 1 (reset (+ 2 (shift k -- (+ 3 (k 5) (k 1)))))) dtest4 = do x <- reset $ do y <- shift $ \k -> do z <- k 5 w <- k 1 return $ 3+z+w return $ 2+y return $ 1+x
実行してみる。
$ ghci -fno-implicit-prelude dcont.hs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. [1 of 2] Compiling ShiftResetGenuine ( ShiftResetGenuine.hs, interpreted ) [2 of 2] Compiling Main ( dcont.hs, interpreted ) Ok, modules loaded: Main, ShiftResetGenuine. *Main> flip unC id dtest1 2 *Main> flip unC id dtest2 3 *Main> flip unC id dtest3 [1,3,2,4] *Main> flip unC id dtest4 14 *Main>
一部の例はhttp://community.schemewiki.org/?composable-continuations-tutorial より。
注意: GHC 6.8では -XNoImplicitPrelude を使うらしい。