2008-02-27

限定継続 in Haskell 98 by Oleg Kiselyov

Haskell

限定継続フェスタがあると聞きまして，私もちょっぴり勉強しています。 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記法でも書けそうだ。

2008-02-27

Delimited Continuation with do-notation

Haskell

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 を使うらしい。