Just $ A sandbox

プログラミングと計算機科学とかわいさ

処理の切り替えとFreezeパターン

以下、Objectというとメソッドと適当な引数を与えると自分自身を返したり返さなかったりするデータ型、またはobjectiveのObjectということにしておきます。

newtype Object xs = Object { runObject :: forall a. Methods xs a -> ctx (Object xs) a }

さてオブジェクトを実行し続けて、あるタイミングで別の処理に切り替えたいということはままある。一番よくある例ではあるタイミングでオブジェクトが死ぬ、死んだらオブジェクトを破棄する処理に移行する、みたいなことがしたい、とか。

そのままオブジェクトを丸ごと破棄してGCに回収させればよいのであれば何も考えなくていいんだけれど、大抵の場合は後処理があり、後処理には死ぬ直前のオブジェクトからデータを拾ったり、ということはまぁあるよねと。

おそらく一番簡単なのは isDead フラグをオブジェクトの内部状態として持たせておいて isDead を毎回確認するというもので、これは意外と悪くないのだけれどフラグが必要なため内部状態が1つ増えるわけである。

管理する内部状態が増え、しかもこのようなものが全てのオブジェクトに生えることを許すわけにはいかないのでこれをやめたい。で、特定のタイミングで処理を切り替えたい場合には、次のようなFreezeパターンを使ってみるのがいいんじゃないかという提案。

data Freeze w a = Freeze w a | Keep w

_Frozen :: Lens' (Freeze w a) w

名前の通り、普通の値は Keep に入れて、死んだオブジェクトあるいは一旦処理を切りたい時に Freeze に入れる。これを実際にオブジェクトを定義する時に使うときには例えば次のようにする。

newtype FreezeT w m a = FreezeT { runFreezeT :: m (Freeze w a) }

op'switch :: Object xs -> FreezeT (Object xs) m a

--

runAndKill :: Object xs -> (Object xs -> m r) -> (Object xs -> DeleteFlag -> m r) -> m r
runAndKill obj update kill = do
  obj' <- op'run obj

  fw <- runFreezeT $ op'switch obj'
  case fw of
    Freeze o a -> kill o a
    Keep o -> update o

  where
    op'run :: Object xs -> m (Object xs)

例えばオブジェクトを一旦Freezeさせてから特定のタイミングで再初期化して復活させる、みたいなこともあると思うのでそういうこともやってみよう。

-- 初期化
op'initialize :: args -> m (Object xs)

-- run -> switchを繰り返す
-- switchは死んだかどうかのチェックに使う
op'run :: Object xs -> m (Object xs)
op'switch :: Object xs -> FreezeT (Object xs) m a

-- 死んだobjectを復活させる
op'reset :: Object xs -> a -> args -> Object xs

-- 死んだobjectを破棄する
op'delete :: Object xs -> a -> m ()

--

runObject args = do
  obj0 <- op'initialize args
  (obj,a) <- mainloop obj0
  op'delete obj a

  where
    mainloop objN = do
      objN' <- op'run objN

      fw <- runFreezeT $ op'switch objN'
      case fw of
    Freeze w a | breakMainLoop -> return (w,a)
    Freeze w a -> mainloop $ op'reset w a args
    Keep w -> mainloop w

こういう感じで、「一旦止めて」「特定のタイミングで別の処理に切り替える」みたいなことがしたいときは便利なんじゃなかろうか。

最近思いついて使っているので共有。

Notions of Computations and Effects

前回のeffect systemに対するボヤキ、あるいは予言が色んな人に読まれたみたいなので興味がある人が一定数いるならeffect systemの紹介記事をちゃんと書こうと思った次第。

というわけでmonadを前提としてプログラミング言語的な見方と圏論的な見方を通してeffectに関するお話をしてみます。

注意 以下のプログラムはHaskellに寄せたオレオレsyntaxで実際にそういう実装があるわけじゃないので注意してください。実際の実装されている言語の話は最後に少しします。

programming with effects

effectは通常type-and-effect-systemと呼ばれるようにある意味で一種の型システムのようなものです。型システムがプログラムの入力と出力の値を見積もる仕組みだったのに対し、エフェクトシステムはプログラムを実行した際に「起きうる」エフェクトをコンパイラが見積もる仕組みだと思ってください。

で、これだけだと「つまりどういうこと?」ってなると思いますが、「エフェクトって何」って質問は「モナドって何」という質問と本質的に同じなので具体的には答えようがありません。というわけで例を見ましょう。

具体例

exception

-- exc effectの例
excHead :: List a -> {Exceptions [EmptyListError]} a
excHead [] = raise EmptyListError
excHead (x:xs) = x

これはエフェクトとして例外エフェクトを考えた場合です。{} の部分がエフェクトです。

ノリはEither monadやException monadと同じようなものでしょう。しかし、エフェクトは 暗黙的に計算されるので プログラム中で x と書いた部分は自然に {Exceptions} a 型の値になっています。

つまりエフェクトというのは自由に増やしてよく、subtypingのときのようにいつでも {es} a -> {es ++ es'} a のようなルール(coerce rule)が成り立ちます。

state

もう少し複雑な例をやりましょう。state effectは get, put というoperationを持っているエフェクトです。

-- get :: {State S} S
-- put :: S -> {State S} ()
addState :: Int -> {State Int} ()
addState n = put (get + n)

は〜めっちゃ簡単やんけ〜

io関連

Haskellではあらゆる「非純粋」をIOという謎の巨大モナドで隠蔽していましたが、エフェクトシステムではもう少し細かく制御することが可能です(もう少し細かく制御してもHaskellほどの煩わしさは出てきません)

readFileAndPrint :: FilePath -> {FileIO, Console} ()
readFileAndPrint path = print (readFile path) where
  print :: String -> {Console} ()
  readFile :: FilePath -> {FileIO} String

print . readFile としても型が合うことに注目してください。先程も言ったようにこれはエフェクトの暗黙的な計算によるものです。

effect handler

effectを発生させる関数はあちこちにあるので使いまくってるとどんどこ増えていくのでは、と思うかもしれませんが一般にeffectを減らすeffect handlerというものが存在します。(monadに対するrunMonadTみたいなやつ)

catExceptions :: List ({Exception} a) -> List a
catExceptions [] = []
catExceptions (x:xs) =
  handle x of
    value <a> -> a : catExceptions xs
    <raise -> k> -> catExceptions xs

syntaxは適当なのでノリで理解してもらうことにして、 {Exception} a 型の値が raise で作られたものか、あるいは普通の値なのかで場合分けが出来ます。そしてこのhandlerは必ずしも頭部だけではなく深部のoperationも同様にhandleできます。

divAllAndSum :: List Real -> Real -> Real
divAllAndSum xs t = calc where
  div :: Real -> Real -> {Exception DivideByZeroError} Real

  calc =
    -- map (\x -> x `div` t) xsの中で起きうるエラーをまとめてキャッチ
    handle (map (\x -> x `div` t) xs) of
      value <xs> -> sum xs
      <raise DivideByZeroError -> _> -> -1

で、まぁ「これってただの try..catch.. やんけ!」と思うと思いますがそのとおりで、effect handlerとは単なるtry-catchのeffectへの一般化です。

ちなみに説明してませんが本当はoperationをキャッチする時に k みたいな継続がやってきてこれを使って、operationが発生したときの途中のプログラムを受け取ってごにょごにょとかできるんですがまぁ今はスルーで

effect systemとは

さてeffect systemの例をいくつか見て雰囲気を味わったところでeffectの説明をしましょう。

さて「モナドって何」という質問には、(それが初学者に対する適切な説明かはともかく)「returnとbindがある型クラスです」という答えがあるのでそういう説明をすると、エフェクトとは次のような型クラスです。

class Effect e where
  return :: a -> {} a
  (>>=) :: {e} a -> (a -> {e'} b) -> {e ++ e'} b
  coerce :: e ⊆ e' => {e} a -> {e'} a

  -- もちろん満たすべき等式とかあるけど
  -- そのへんはあとで述べるよ

モナドと一緒やんけ!」と思うと思いますがそもそもここでのeffectとはモナドをちょこっと拡張しただけのものなのでそりゃそうです。で、上に述べたeffect systemはこのeffectの計算(e ++ e' とか e ⊆ e' とか)を全てコンパイラがやってくれるので基本的にプログラマーは気にしなくて良いです。

やったぜ。

implicit vs explicit

さて上の定義は実は色んなことが隠蔽されており、そもそもコンパイラがやってくれるって何だよ、とかeffectに入ってる構造は何やねんみたいな話になります。で、上の方式は実はimplicit effect systemと呼ばれるもので、要はeffectの本当の姿は全て隠蔽して見せていました。

要はML等の言語では A -> B と書いたらこれはHaskellでいうところのIOモナドが隠蔽されており、実際には A -> IO B の意味である、とちょうど同じように、上ではエフェクトが属する本来のモナドが隠蔽されています。

というわけで、本当の定義としては、エフェクトシステムとはモナドに添字のついたモノであり、次のような型クラスを満たすものです。

class EffectedMonad T where
  return :: a -> T{} a
  (>>=) :: T{e} a -> (a -> T{e'} b) -> T{e ++ e'} b
  coerce :: e ⊆ e' => T{e} a -> T{e'} a

ここで Tモナドの一般化です。(e を固定するごとに T{e}モナドになる、 わけではない ので注意)これを満たす T を適当に固定して、その T 部分を隠蔽すると上の例に出てくるような言語を定義することができるようになります。

graded monad

上に見たような EffectedMonadモナドに見えるけど T{e}モナドじゃない、と言いました。で当然このような構造にも名前がついており、 graded monad とか E-monad (Eはeffect category)とか言ったりします。

定義 graded monad T とは、preordered monoid E から [C,C] へのlax monoidal functorのことである。

monadとは 1 から [C,C] へのlax monoidal functorであったことを思い出せば自然にモナドの拡張になっています。

上でのcoerce ruleとは E のpreorderがmappingされたもの。

これで少しはスッキリ出来たんじゃないでしょうか。

実装の話

実装は次のようなものがあります。

後まぁまだまだあるはず。エフェクトの扱いが違ったりできることと出来ないことがあったりなかったりして割と言語ごとにノリが違うし、特にデファクトっぽい雰囲気のはないので興味ある人は色々やってみるといいんじゃないでしょうか。

Haskellにおける実装

せっかくHaskeller向けにあれこれ書いたのでHaskellの実装の話も。

この辺ちょい追記

さて上にも書いたとおりeffect systemはmonadの一般化なので、monadしか扱えないHaskellで完全な実装を書くのは不可能または激しく使いづらくなります。以下に述べる実装はそれを無理やりモナドに落としてそれっぽくしたのでまともなeffect systemだと思って(上に述べたような挙動を試そうとすると)GHCが文句を言ってきたり、普通のeffect systemならコンパイラがやってくれるエフェクトの計算とか推論を自力でやらされたりして大変です。

  • extensible-effects, freer-effects: 実はexteffはエフェクトシステムの部分的な実装と見ることが出来ます。freerはexteffの改良版でパフォーマンスもめっちゃ良くなってるので今ならこっちがおすすめ(freerよりfreer-effectsの方がいいらしい?)
  • extensible: extensible recordライブラリだったはずなんだけどいつの間にか同じノリでeffect systemの実装が生えていた。解説がこの辺とかにある
  • effect-monad: 上の EffectMonad (graded monad)を直接実装したライブラリ。どう見ても使いやすそうじゃない。

その他細々したこと

  • graded monadに興味ある人は論文を読んでくれ
  • 上では微妙に避けたけれどeffect handlerを定義するためにはeffect自体に制限的なものが必要になるのでそんなほいほい入れていいようなものでもないです
  • というか、割といくつかの言語では自分でeffectを新たに定義できるようになっていて、それがeffect handlerといい感じでアレがアレしてるんですが一言で言えるほど簡単な話じゃないと思う。
  • graded monadでじゃあ具体的にこういうeffect systemはどうやって考えるんですか、って思った人はやってみればいいんじゃないでしょうか。今なら論文になります。
  • というかeffect system関連今ならなんでも論文になるから論文書きたい人はやればいいんじゃないでしょうか。実装も意味論も未解決問題山積みですよ。

おわり

Free Monadic Parser

動機

Haskellでは * -> * カインドを持つデータ型からFreeモナド(Operational)を使って5秒でDSLが作れることは有名だけど、 そうやって作ったDSLスクリプトとして外部ファイルから読み込むようなことがしたいこともあるかもしれない。 そういう時にわざわざパーサーを頑張って1から書くのはしんどいし、うまい具合にやってくれてもいいのだろうか、という話。

結論から言うとある程度うまい具合にできます

Freeモナドについて

FreeモナドはFreeなので特別なprimitive operationは定義されていないから、モナドのoperationだけをパースすることを考えればいい。 つまり、

ex = do
  Con1 x y
  t <- Con3 a b c
  Con4 t

のようなものがパースできればよさそうなことがわかる。 本来はモナドで定義可能な関数(whenとか)は使えるようにするべきなのかもしれないけど今回は面倒なのでパス。

さて、do式では好きな変数にbindすることができて、実体は適当な型の値がそこには束縛されている。 それを上手くパースして適当なデータ型に押し込める必要がある。

そこで、データ型の定義をする際に、実際に来るべき型とリファレンス(変数名)をどちらも取れるようにしておくことにしよう。

例えば上の例では Con4 がIntを受け取るとしたい場合、コードでは

Con4 :: ref Int Var -> DSL ()

のように定義することにする。 ref は後で具体的に適当な型が来るが、今は Int, Var のいずれも来る可能性があることを示していると思えば十分だと思う(=Var= はString)。

例: Add-Double計算機

一番下に今回使うコードを貼っておくので見てもらうとして、いくつか抜粋して解説をする。

例として、次のような命令を持つDSLを考えよう。

data DSL ref a where
  Add :: ref Int Var -> DSL ref ()
  Double :: DSL ref ()
  Get :: DSL ref Int
  Print :: DSL ref ()

これは内部に1つのIntを持つ計算機で、加算、内部の値を2倍、内部の値を取得、内部の値を出力できる。 ただし型を見ると分かるとおり、 Add は普通に値を受け取ることもできれば、 Get で取得して束縛したreferenceを渡すこともできる。

これのパーサーを書き、さらにそれのインタープリターをFreeモナドを使って書くことを考えよう。 従来なら DSL と同じような(ただしreferenceを保持する等の微妙な違いがある)Syntaxに沿ったデータ型を作ってパーサーを書いていたけれど、それをやめて上の DSL だけでパーサーもインタープリターも書いてしまうことにする。

パーサー

いきなり上のパーサーを書いてしまう。

pDSL :: Parser [Syntax (DSL Either)]
pDSL = fromConParsers $ 
  [ pbind padd
  , pbind pduplicate
  , pbind pget
  , pbind pprint
  ]

  where
    padd = do
      symbol "Add"
      choice $ fmap try $
    [ Add . Left . fromInteger <$> integer
    , Add . Right <$> some letter <* newline
    ]
    pduplicate = (\_ -> Double) <$> symbol "Double"
    pget = (\_ -> Get) <$> symbol "Get"
    pprint = (\_ -> Print) <$> symbol "Print"

ここではtrifecta(persecみたいなもの)を使っているけれど、 DSL の各コンストラクタを fromConParsers に渡していることだけ分かればOK。 fromConParsers はコンストラクタのパーサーからFreeモナドのパーサーを作るやつ。

実際は、bind syntax x <- Get みたいなのをパースするんだけどあまり細かいことは気にしなくていいと思う。 パーサーでは色々型やらなんやらをごまかして書いたので、インタープリターを書くためには少しだけトリックが必要になる。

Value Universe

上でも述べたけれどreferenceを受け取ることを常に考える必要があり、さらにそれらには型がついているので、型が合わない操作を許容するわけにはいかない。 例えば x : String のときに Add x を解釈することは出来ないので、つまりどんな型が来るかも込みでインタープリターを書く必要がある。

ただし当然どんな型が来るべきかはコンパイル時には決定できないので、結論としてこのDSLが取りうる値を全て含んだ型を作ることになる。

今回のDSL(), Int しかないので、それを含んだ型を定義する。

data BindVal = VU () | VInt Int

Resolver

インタープリターを書くためには、次のようなことを気にする必要がある。 コンストラクタごとに、どうやって上のValue Universe(BindVal のこと)に変換するかを指定する必要がある。 それと、上でも述べたreferenceの解決を行いたい。つまり、今は Add : ref Int Var -> DSL ref () なるコンストラクタがあるけれど、 Add (varX)Add 10 みたいに変換する機構が必要になる。

ここでは、Resolverという型クラスを用意した。

class Resolver dsl where
  type ValUniv dsl :: *
  toValue :: dsl Either a -> (a -> ValUniv dsl)
  resolve :: M.Map Var (ValUniv dsl) -> dsl Either a -> dsl Const a

ValUnivDSLのコンストラクタが取りうる値を全て集めた型で、今の場合は BindVal になる。 toValue は、各コンストラクタをどうやって ValUniv に変換するかを指定する。 resolve は、 dsl Eitherdsl Const に変換する。ここで先程の Add を思い出すと、 Add (Either Int Var)Add (Const Int Var) 、つまり Add Int に変換すれば良いことが分かる。

resolve は現在束縛されている変数とその値のMapも引数にあるので、これを使って Add (Right ref) はMapからrefに対応する値を引っ張ってくるだけでよい。

このResolverのinstanceを書けば、欲しかったFreeモナドのデータが得られるので、最後はインタープリター部分を書けばOK。

interpret

インタープリターは適当に書けば良い。 DSL Const が来るので、bindの問題はなく、ただの値が入ったコンストラクタを受け取って動くものを書くだけでいい。

interpret :: Skeleton (DSL Const) () -> IO ()
interpret = go 0 where
  go :: Int -> Skeleton (DSL Const) () -> IO ()
  go st skel = case debone skel of
    (Add (Const n) :>>= next) -> go (st + n) (next ())
    (Double :>>= next) -> go (st * 2) (next ())
    (Get :>>= next) -> go st (next st)
    (Print :>>= next) -> print st >> go st (next ())
    Return _ -> return ()

動かす

Print
Add 10
Print
n <- Get
Double
m <- Get
Print
Add n
Add m
Print

みたいな文字列を渡すとパースしてインタープリットして動くプログラムが得られる。

やったね!

エラーハンドリングについて

型エラー、つまり x: String のとき Add x などと書くものは、上でのresolveできっちりキャッチできる。 上のresolveではMapから値を引っ張ってくるが、引っ張ってきたデータに Int 以外の値が入っている場合は、パースした文字列で型エラーが起きていることが分かるので適当なエラーを書けば良い。

補足

今はモナドの構文としてbind x <- f しか使えないけれど、他にletやifやらもちゃんとサポートするのもありだと思う。

また注意として、上の方法では常にValue Universeが必要になるので返す型が多相になったり複雑になったりするとまた考えないといけないことが出てくるかもしれない。 あんまりちゃんと考えてないけど実用したいときは注意。

コード