Extensible Effects はモナド変換子に対する救世主になり得るか？ konn-san.com

モナドの合成と効率性：モナドスタック = 委譲関係

一番目。モナド合成による効率性の低下問題について。EE がモナド変換子と根本的に異なるのが、全ての計算を一つのモナドの中で行うことだ。この中心的な役割を果すモナドは、原著では Eff モナドと呼ばれている。

一つのモナドの中で行うといっても、一つの超万能なモナドがあってその中で操作をするという訳ではない。それではモナドの旨味がなくなってしまう。ではどうするのか？EE の基本的な考え方は、副作用とはクライアントとハンドラの相互作用だ という物だ。一つ一つのアクションは、それを処理出来るハンドラへのリクエストとして見る事が出来る。例えば、ask は大域環境を持つ計算を司るハンドラへのリクエストと見れるし、IO 計算なんかは正に外部との入出力を行うハンドラへの命令と見ることが出来る。

そこで EE では、Eff モナドの型パラメタとして、「実行に必要な副作用ハンドラの一覧」をタグとして持たせている。そして、そのリクエストを処理するハンドラが今までの runStateT や runMaybeT に当たる。ハンドラは自分の処理できるコマンドを全て処理して、処理し終えた印としてタグを取り除く。これを繰り返していって、最終的にピュアな計算か、IO や ST のような基盤モナドの計算までに辿り着いたら、run や runLift で結果を取り出す。これが EE の基本的な戦略だ。

ちょっとわかりづらいかもしれない。これは、（著者の五年前くらいで止まっている知識を総動員すれば）OOP でいう Chain of Responsibility パターンを Haskell で実現したものになっている。EE は、モナド変換子のモナドスタックを、委譲関係のチェーンとして捉え直したものとも云うことが出来るのだ。例えば、StateT Int Maybe なら State Int :> Try :> Void という委譲関係のチェーンだし、WriterT [String] (ReaderT Int IO) なら Writer [String] :> Reader Int :> Lift IO というチェーンになる（:> は左から右に委譲関係がある、という風に読めばよい）。

直観的には、runReader なり runState なりを噛ませる度に、それぞれのハンドラが処理出来る命令を「処理」して、出来ないものはそのまま残しておくことになる。下位のハンドラへ処理を流すのに、結局ハンドラの数だけ使ってしまいそうな気がするが、EE ではこれを継続渡し形式を使ったコルーチンとして実現しているため、結果的にはハンドラ数に依存しない定数時間で処理が可能になるそうだ²。

副作用の合成順：Open Union

次に2. モナドを合成する順番によって、計算の意味が変わってくる について。上の説明だけでは、「モナドスタックを一つのモナドの中に押し込めただけで、結局階層になってるんじゃないの？」という突っ込みが成立しうる。確かに、runReader などを呼んで実際に計算を実行する際には階層は確定していることになる。しかし、EE がモナド変換子と大きく異なるのは、Open Union という考え方を用いていることだ。

どういうことか？それを説明するために、各函数のシグネチャを見てみよう。

-- | Computation with the global environment (corresponds to Reader)
ask       :: (Typeable e, Member (Reader e) r) => Eff r e
local     :: (Typeable e, Member (Reader e) r) => (e -> e) -> Eff r a -> Eff r a
runReader :: Typeable e => Eff (Reader e :> r) w -> e -> Eff r w

-- | computation which may fail (corresponds to MaybeT)
failure   :: Member Try r => Eff r a
recover   :: Member Try r => Eff r a -> Eff r a -> Eff r a
runTry    :: Eff (Try :> r) a -> Eff r (Maybe a)

-- | Computation with underlying monad
lift      :: (Monad m, Typeable1 m, MemberU2 Lift (Lift m) r) => m a -> Eff r a
runLift   :: (Typeable1 m, Monad m) => Eff (Lift m :> Void) a -> m a

-- | evaluate @Eff@ to pure value.
run       :: Eff Void a -> a

この函数を見ると、runHoge 系の函数以外は、Member Hoge r という型制約を使って記述されていることがわかる。これは、「r の中の何処かに Hoge という副作用のタグが含まれいてる」という意味の制約だ。:> は型レベルのリストと見做すことが出来るので、その中に Hoge が入っているかどうか？という判定だと思えばよい。このように、ask や failure などの「副作用を持った」函数は単にそのチェーンの中に必要な副作用が含まれていることしか要求しないのだ。これは、モナド変換子を使う際に MonadReader や MonadPlus クラスを使ったやり方と似ていると云えば似ているが、このような仕組みにしたことで、3. 一々 lift を行う必要がある という問題が解決されている。モナドの階層は、各函数のレベルで見ればあくまでもフラットで対等なものなので、いちいち lift を呼ぶ必要がないのだ。もっとも、最終的に IO や STM、ST といった値を計算するようなモナドを合成したい場合はあるが、そのときは liftIO と同じ要領で上の lift を呼ぶことになる。だが、こうした基底モナドの命令を呼び出す場合を別にすれば、合成された他の副作用を呼ぶときに一々 lift をつける必要がなくなる。

どういう事か？例えば、余りよい設計とは云えないが、ReaderT Int (Reader String) a のような例を考えてみよう。EE で対応するのは Eff (Reader Int :> Reader String :> Void) a という型になる。例えば、従来のモナド変換子を用いた方法では、次のように書くことになる：

action :: ReaderT Int (Reader String) (Int, String)
action = do
  int <- asks (*2)
  str <- lift (asks reverse)
  return (int, str)

つまり、「一個下」の文字列の環境を取り出すのに、ここでは lift を使う必要があった。だが、EE ではこれは次のように簡単に書ける：

action :: (Member (Reader Int) r, Member (Reader String) r) => Eff r (Int, String)
action = do
  int <- asks (*2)
  str <- asks reverse
  return (int :: Int , str :: String)

面倒な lift が消えて、どちらも asks だけになっている！ただ、値を返す際にそれぞれの値に型注釈をしている。これは、asks の型の曖昧性をなくすためで、int や str がどの Reader に向けての命令なのかをハッキリさせるためだ。このような簡単なプログラムだと注釈を書く必要があったが、現実的なもっと長いプログラムであれば、こういった型は推論により確定できるようになるだろうから、余り問題にはならない。それに、型の注釈は簡単に書けるが、lift は階層の数だけ書かなくてはいけなくて、ReaderT Int (ReaderT String (ReaderT (Int, Bool) (ReaderT Env IO))) a みたいな型があったら、いったいどこの値を取り出すのに何回 lift を書けばいいのかパッとみよくわからないだろう。EE では、そういったことを考える必要性はない。

ここで、あるていど使っているひとは疑問に思うかもしれないことがある。それは、「ReaderT Int (Reader Int) a のように同じ型の状態を持つ Reader が重なってるような状況をどう表現するの？」ということだ。これには、お馴染の newtype ハックを使えばよい。そもそも、こういった型の設計はプログラムとして余りたちのいいものではないし、それぞれの環境の意味をハッキリさせる意味でも、それぞれを newtype で包むべきだ。

newtype Page = Page Int deriving (Show, Eq, Ord, Num, Integral)
newtype Line = Line Int deriving (Show, Eq, Ord, Num, Integral)

lineLen :: Int
lineLen = 40

linePerPage :: Int
linePerPage = 40

currentPos :: (Member (Reader Page) r, Member (Reader Line) r) => Eff r Int
currentPos = do
  Page p <- ask
  Line l <- ask
  return (p * linePerPage * lineLen + lineLen * l)

こうすれば、 lift も要らないし、パターンマッチの所で型が確定するので、型注釈も要らない。

また、上のコードを見て気付くひとは気付くかもしれないが、多少の柔軟性を犠牲にすれば、Eff 型を mtl の MonadReader や MonadState のインスタンスにすることも簡単に出来る。こうした準備をしておけば、mtl の API を使って実質的に EE を使ったプログラムが掛ける。また、mtl から EE への移行を本格的にしようと思っても、コードに殆んど手を入れる必要はない。型注釈の所を書き換えて、lift を取り除いたりすれば大抵の場合ちゃんと動くようになる。EE はモナド変換子とは本質的には異なる実装ではあるが、ユーザの側では殆んど変更なしで採り入れることが出来るのだ。

この lift と関連して、モナド変換子のアプローチにはもう一つ限界がある。それは、セマンティクスが柔軟ではないということだ。その例を見てみよう（以下、論文からの例）。

問題設定は簡単だ。ここでは、非決定計算とエラー処理とを組み合わせることにしよう。非決定的にリストの計算を進めて、途中で 5 より大きな数が出て来たらそこで処理を中断することにしよう：

newtype TooBig = TooBig Int deriving (Show, Eq, Ord)

instance Error TooBig

choice :: MonadPlus m => [a] -> m a
choice = msum . map return

ex2 :: MonadError TooBig m => m Int -> m Int
ex2 m = do
  v <- m
  if (v > 5)
  then throwError (TooBig v)
  else return v

ghci> runIdentity (runErrorT (runListT (ex2 (choice [5,7,1]))))
Left (TooBig 7)

ghci>  runIdentity  (runErrorT (runListT (ex2 (choice [5,4,1]))))
Right [5,4,1]

ところで、ここでお上の都合で「やっぱり 7 以下の数は大きくないんじゃね？」ということになったとする。そこで、例外をキャッチして、 7 以下だったら処理を再開するようにしてみよう。

exRec :: MonadError TooBig m => m Int -> m Int
exRec m = catchError m handler
  where
    handler (TooBig n) | n <= 7 = return n
    handler e = throwError e

ghci> runIdentity (runErrorT (runListT (exRec (ex2 (choice [5,4,1])))))
Right [5,4,1]

ghci> runIdentity (runErrorT (runListT (exRec (ex2 (choice [5,7,1])))))
Right [7]

おや……？最後の計算では、[5,7,1] が返って欲しいのに [7] しか返ってきていない。なんでだろう！

これは、この函数の型が ListT (ErrorT TooBig Identity) [Int] であって、ErrorT がより底の方にあるからだ。つまり、例外 TooBig 7 が飛んだ時点で、上に重ねられていた非決定計算としての ListT での演算は忘れ去られてしまうのだ！

どうしよう……と悩んで、じゃあ ErrorT TooBig を二重に張り巡らせたらどうだろう？という気分になったとしよう：

ErrorT TooBig (ListT (ErrorT TooBig Identity)) a

一旦非決定計算上の各ブランチで例外を見てあげて、それからそれを下の基盤に近いほうのエラーモナドに伝播してやろうと云う戦略をとる訳だ：

runErrorRelay :: MonadError e m => ErrorT e m a -> m a
runErrorRelay m = runErrorT m >>= check
  where
    check (Right x) = return x
    check (Left e) = throwError e

ghci> runIdentity (runErrorT (runListT (runErrorRelay  (exRec (ex2 (choice [5, 7, 1]))))))
Right [5]

えーーーこれどういうことなの……。何で 5 だけ残るの……。

よぉく考えてみよう。ex2 のコードを見ると、一番最初に v <- m としてアクションの値を取り出している。でも、今このコードでの m は「ErrorT TooBig (ListT (ErrorT TooBig Identity)) Int」 という型の、一番左の ErrorT TooBig に包まれた値なのだ。ここで使われている MonadPlus のインスタンスは、ListT ではなく、ErrorT a に対するインスタンスなのだ。これを本来非決定計算の文脈に持っていきたいのだから、ここで lift を使わなくてはいけないことがわかる：

ex1 :: Monad m => m Int -> ErrorT TooBig m Int
ex1 m = do
  v <- lift m
  if v > 5 then throwError (TooBig v) else return v

ghci> runIdentity (runErrorT (runListT (runErrorRelay  (exRec (ex2 (choice [5, 7, 1]))))))
Right [5,7,1]

や、やっと動いた……。

これは、モナド変換子が本質的に抱える限界を表している例だ。では、これを EE を使って書いてみよう。

ex2 :: Member (Exc TooBig) r => Eff r Int →Eff r Int
ex2 m = do
  v <- m
  if v > 5 then throwError (TooBig v) else return v

runErrBig :: Eff (Exc TooBig :> r) a -> Eff r (Either TooBig a)
runErrBig m = runError m

exRec :: Member (Exc TooBig) r => Eff r Int -> Eff r Int 
exRec m = catchError m handler
  where 
    handler (TooBig n) | n <= 7 = return n 
    handler e = throwError e

ghci> run (runErrBig (makeChoice (exRec (ex2 (choose [5,7,1])))))
Right [5,7,1]

lift なんて書く必要もないし、また型の部分以外は、mtl で書いたプログラムと殆んど変わっていないことがわかるだろう。このように、EE は継続渡しを基本として、最終的に一つのモナドとして実行されるフラットな設計になっているので、直観的にモナドの効果を組み合わせることが出来るのだ。

階層を超えた副作用

ここまでの例で、「単純に階層構造を委譲関係と捉えたもの」という訳ではないことがわかったという。更に、EE では階層を超えた副作用のハンドリングが出来る。つまり、モナド変換子の4. モナドの合成順は固定されてい、途中で入れ替えることができない という限界を乗り越えることが出来るのだ。

この解説を書くつもりでいたのだが、段々面倒になってきたので詳細は論文を参照して欲しい。論文では、大域環境とコルーチン的な副作用を合わせもったプログラムを書こうとしている。まず、全体でひとつの環境を共有した状態でスタートするが、各スレッドの中で環境が変更されたら、その環境は以後外から切り離されるような仕組みを作りたいとする。詳しい説明は面倒だしちゃんと理解出来ていないのでここでは書かないが、実は、モナド変換子を使った方法ではこのようなプログラムは書けない。理由は論文を参照してほしい。しかし、EE を使うとこのような処理も書けるようになるらしい。