拡張可能作用 ― モナド変換子に取って代わるもの 3 - shiatsumat/fp-papers GitHub Wiki

3. 拡張可能作用フレームワーク

これから、[図1](拡張可能作用 ― モナド変換子に取って代わるもの 2#fig1) のインターフェースの実装を提示し、設計上の鍵となる選択を説明する。これは以下のように構成されている。[§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) では単一の作用 Reader Int を実演することで私たちのアプローチを支えている基本の概念を紹介する。そして、[§3.2](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-2) ではこのアプローチを一般化して固定だが任意の作用をハンドルし、[§3.4](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-4) ではもう一歩進んで、このアプローチを一般化して多くの、任意の作用をハンドルする（これは [§3.3](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-3) で説明するオープンな和を使うことで達成された）。それ以降のセクションでは私たちのフレームワークを更に別の例を使って実演し、その表現性と効率性をモナド変換子と比較する。

3.1 コルーチンとのやりとりとしての読み取り作用

私たちのアプローチへのやさしい導入として、一つの、もっとも単純な作用を実装する――環境から動的に固定された Int の値を取得する作用である。私たちは作用を、クライアントと作用ハンドラ、あるいは支配者の間の通信から生じるものと見なす。このクライアント-ハンドラ間の通信は、一般的なクライアント-サーバー間の通信モデルから逸脱していないので、容易にコルーチンとしてモデル化できるだろう――計算はリクエストを送り、返事を待って保留し、ハンドラはリクエストを待って、ハンドルできる時はハンドルし、クライアントを再開させる。私たちはそうしたコルーチンを実装するために継続モナドを使う。

newtype Eff a = Eff {runEff :: forall w. (a -> VE w) -> VE w}

instance Monad Eff where
    return x = Eff $ \k -> k x
    m >>= f  = Eff $ \k -> runEff m (\v -> runEff (f v) k)

data VE w r = Val w | E (Int -> VE w)

ask :: Eff Int
ask = Eff (\k -> E k)

admin :: Eff w -> VE w
admin (Eff m) = m Val

runReader :: Eff w -> Int -> w
runReader m e = loop (admin m) where
  loop :: VE w -> w
  loop (Val x) = x
  loop (E k)   = loop (k e)

型 Eff a は、多相的な w の返事の型 (VE w)（これは Value-Effect（値-作用）の略であり、データを構成する2つの型を表している）へと実体化された制御作用を実行する計算の型である。返事の型は、計算が値 (選択肢 (alternative) (Val w)) を生むか、Int 環境を読めというリクエストを送るということを表している。このリクエストは、再開されれば、計算を継続し、その計算は別の (VE w)型の返事を再帰的に生む（あるいは発散する）。この関数 admin は値を期待する初めの継続と共にコルーチンを開始する。この値は、計算が発散しない限り、必ず最終的な結果となる。

ハンドラ runReader はコルーチンを開始し、そのステータスを確かめる。もしコルーチンが返事を送れば、結果が帰ってくる。もしコルーチンが環境の現在の値を尋ねるリクエストを送れば、その値 e は返ってくる。演算 ask は現在の値を環境から以下のように読み出すリクエストを送る――現在の継続（「差出人住所 (return address)」）を取得し、リクエストにそれを含め、runReader が最終的な返事を生むために呼び出す Int -> VE w の関数を構成する。

残りの Reader の演算は local であるが、これは変化した環境の中で計算を実行するものである（Reader モナドの local を参照）。

local :: (Int -> Int) -> Eff w -> Eff w
local f m = do
  e0 <- ask
  let e = f e0
  let loop (Val x) = return x
      loop (E k)   = loop (k e)
  loop (admin m)

一方で、local は runReader のように Reader リクエストをハンドルしなければならないが、他方で、local は修正する環境の値を取得するために Reader リクエストを送らなければならない。結果として、local の型は、runReader の型と違って、Reader 作用を取り除くことを約束しない。（註：ここでは local は runReader を使って簡単に書くことができる。[§3.4](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-4) の完全なライブラリにおいて、2つの関数は別々に実装される必要がある。なぜなら、runReader は完全なハンドラとして、 Reader 作用の層が取り除けるように最上部に来ることを強制するが、local はそうではないからである。）

3.2 任意の作用に対するコルーチン

これから、フレームワークを拡張して別の作用も扱えるようにしていく。例えば、ブール値の例外をモデル化する――例外の値を、差出人住所を指定しないリクエストとして送るのである（これは、再開されることを期待しないからである）。そうした例外を投げるコルーチンのステータスを表す型はこのように表現できる。

data VEex w = Val w | E Bool

もしそうではなく任意のリストから要素を非決定論的に選びたいのならば、リストと返り値アドレスを含むリクエストを送り、一つの要素が返ってくることを期待する。

data VEch w = Val w | forall a. E [a] (a -> VEch w)

Reader、選択、Exc のリクエストを出すコルーチンのステータスの型を調べると、ステータスが、常に通常の終了のための選択肢 (alternative) Val w と、リクエストを持つ何らかの形の選択肢 E を含んでいることを見て取れる。リクエストは通常、差出人住所を (t -> VE efftct w) という形で含んでいる。ここで、期待される返事の型 t は、リクエストと結果の型 (VE effect w) に依存している、コルーチンのステータスを表す型である。このアプローチを抽象化すると、コルーチンのステータスのための一般的な型が明らかになる。

data VE w r = Val w | E (r (VE w r))

型変数 r :: * -> * は特定のリクエストを表す。例えば、[§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) の Reader リクエストは r を (Reader e) と実体化する：

newtype Reader e v = Reader (e -> v)

作用の「型」が実際には、リクエストの型からコルーチンのステータスの型を構成する、種 * -> * の型構成子 (type constructor) であるというと、驚くかもしれない。しかしこのことは、リクエストの型の再帰的な性質――オープンな再帰型であること――からただちに従う。次のセクションで説明するこの型は、私たちに任意の作用を組み合わせることを許してくれる。

この豊かな型を使えば、[§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) のモナドコルーチンライブラリを任意のリクエストへと容易に一般化できる。

newtype Eff r a = Eff {runEff :: forall w. (a -> VE w r) -> VE w r}

instance Monad (Eff r)

send :: (forall w. (a -> VE w r) -> r (VE w r)) -> Eff r a
send f = Eff $ \k -> E (f k)

admin :: Eff r w -> VE w r
admin (Eff m) = m Val

このコルーチンモナドは、コルーチンが送る可能性のあるリクエストの型 r によって指標付けされている。関数 send はこれらのリクエストを送り出して、返事を待つ。この関数は現在の計算を保留したもの k（型 a -> VE w r の差出人住所）を取得し、k をユーザーの指定したリクエスト生成関数 f に渡して（型 r (VE w r) の）リクエスト本体を取得し、それをリクエスト E と組み合わせ、待っている admin に渡す。このコルーチンライブラリは、オープンな和（[§3](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3) を参照）と共に、私たちの作用のシステム全体の基盤を作っている。コードの残りの部分はさまざまな作用（モナド）を実装しているだけで、すべてユーザーが書くことができる。以下、そのような作用を2つ説明する（[§5.4](拡張可能作用 ― モナド変換子に取って代わるもの 5#section5-4) では更に別の例を取り上げる）。

一つ目のモナドの例は、Identity モナドに似ている。これは、要素を全く含まずリクエストを全く送らない純粋な計算を表す。私たちは Void を「リクエストの無い」型とする。この型は構成子 (constructor) が無いので、リクエストは何も出せない。

data Void v -- 構成子無し

run :: Eff Void w -> w
run m = case admin m of Val x -> x

関数 run は純粋な計算のハンドラとして働き、結果を返す。run の型は、作用は存在できず、リクエストは期待されていない、ということを表している。つまり純粋な計算だけが実行できるのだ。

[§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) の環境を読み取る作用は、一般化されたコルーチンライブラリを使って以下のように実装し直すことができる。

newtype Reader e v = Reader (e -> v)

ask :: Eff (Reader e) e
ask = send Reader

runReader :: forall e w. Eff (Reader e) w -> Eff Void w
  loop :: VE w (Reader e) -> Eff Void w
  loop (Val x)        = return x
  loop (E (Reader k)) = loop (k e)

runReader の型注釈は、(Reader e) のリクエストを送るかもしれない計算を受けとり、それらのリクエストを完全にハンドルする、ということを表している。結果は、ハンドルされていないものが何も残っていない純粋な計算である。

このように定義された Eff Reader は MTL の Reader モナドと全く同じように使える。

t1 :: Eff (Reader Int) Int
t1 = ask `add` return (1 :: Int)

t1 の推論された型は、t1 を作用のある計算として裏切っている。型検査器はこれを run することを妨げる。計算はリクエストを送りうるので、まずはそれがハンドルされなければならないのである。

t1r :: Eff Void Int
t1r = runReader t1 10

推論された型は t1r が純粋であるということを表しているので、run t1r は上手く型付けされ、評価すると最終的な結果 11 が生まれる。

3.3 オープンな和型

一般的な、単一作用のシステムを扱ってきたが、これから単一の計算により多くの作用を含めることに焦点を移していこう。作用 r を実行するために、計算はその型のリクエストをハンドラに送る、ということを思い出してほしい。そうした計算の型 Eff r a はありうるリクエストの型 r によって指標付けされている。ゆえに、リクエスト r1 と r2 を実行する計算は、型 r1 または r2のリクエストを送るかもしれない。したがって、リクエスト自体は r1 と r2 の直和 (disjoint union) または和 (sum) なのである。もしプログラマが自由に新しいリクエストの型を付け足せるならば、この和はまさに拡張可能である――つまりオープンな和なのだ。私たちのオープンな和は型で指標付けされた直和である [[15](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference15),[28](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference28)]。和型に反映されていない値を射影する (project) のは確実に失敗することがわかっているので、静的に拒絶されるのである。

私たちの設計するオープンな和は抽象的である。拡張可能フレームワークのユーザーには以下のようなインターフェースが見える。

type Union r :: * -> * -- 抽象的

infixr 1 :>
data ((a :: * -> *) :> b)

class Member (t :: * -> *) r

inj :: (Functor t, Member t r) => t v -> Union r v
prj :: (Functor t, Member t r) => Union r v -> Maybe (t v)
decomp :: Union (t :> r) v -> Either (Union r v) (t v)

このフレームワークは（種 * -> * の型を持つ）リクエストのためにオープンな和を用いている。オープンな和は、この和に入っているかもしれないリクエストの型の集合 r によって型が定められている。これらの集合は以下のように構成される――Void は空集合を表し、t :> r は集合 r に t を挿入する。私たちは、型レベルの表明 (assertion)（メンバの無い型クラス）Member t r も提供する。これは、集合 r がリクエスト t を含んでいるということを、r の構造を明示せずに表明するために使う。

3つの関数 inj. prj, decomp についても説明していこう。入射 (injection) inj は型 t のリクエストを受け取り、それを和 r に付け足す。制約 Member t r は t が和の一員であることを保証している。（Functor の制約については [§3.4](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-4) で説明している。）射影 (projection) proj は逆のことをする。型 t の値を持っているかもしれない型 Union (t :> r) の値が与えられると、交わりの無い分解 (orthogonal decomposition) decomp は、値がそのリクエスト型 t を持っているかどうかを定める。もしそうであれば、それを返す。そうでなければ和の値は、より制限の強い、t の無い型 Union r へとキャストされる。ゆえに decomp は Union r を2つの交わりの無い「空間」へと分解する。1つは特定の型 t であり、もう1つは t の無い r である。この演算は私たちのオープンな和を以前の設計 [[18](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference18),[32](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference32)] と違うものとする。私たちは、和を拡張できるだけでなく、縮めることもできるのだ。この分解は私たちのオープンな和を、OCaml の拡張可能多相変数 (extensible polymorphic variants) とも違うものにする。演算 inj はリクエストを送るのに使われ、prj と decomp はリクエストをハンドルするのに使われる（[§3.4](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-4) で実演している）。

実装の内部はユーザーには見えない。ユーザーにはそれぞれ区別できない実装のアプローチがいくつかある。私たちは HList [[15](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference15)] に似ている実装を提示する。これが簡単なまとめである。（註：実装の全体を知りたければ、付属するソースコードの中の [OpenUnion1.hs](拡張可能作用 ― モナド変換子に取って代わるもの付録#appendixb) を見よ。［少し異なる実装として、[OpenUnion2.hs](拡張可能作用 ― モナド変換子に取って代わるもの付録#appendixc), [OpenUnion3.hs](拡張可能作用 ― モナド変換子に取って代わるもの付録#appendixd) も参考になるだろう。］）

data Union r v where
  Union :: (Functor t, Typeable1 t) => Id (t v) -> Union r v

newtype Id x = Id x -- gcast1 のため

instance Functor (Union r) where ...

inj :: (Functor t, Typeable1 t, Member t r) =>
       t v -> Union r v
inj x = Union (Id x)

prj :: (Functor t, Typeable1 t, Member t r) =>
       Union r v -> Maybe (t v)
prj (Union v) | Just (Id x) <- gcast1 v = Just x
prj _ = Nothing

decomp :: Typeable1 t =>
          Union (t :> r) v -> Either (Union r v) (t v)
decomp (Union v) | Just (Id x) <- gcast1 v = Right x
decomp (Union v) = Left (Union v)

Union r v の型の実装は本質的に Dynamic と同じであり、ゆえに inj と prj の型注釈に制約 Typeable1 t が付いている。和に属するリクエストの集合である型変数 r は、幽霊型変数 (phantom parameter) である。この和の実装は、ユーザーからは直接アクセスできない。データ構成子 Unionはエクスポートされていないのである。演算 inj, proj, decomp だけが、ユーザーがオープンな和を扱うことのできる唯一の手段なのである。r は幽霊であるので、型クラス (Member t r) は実際いかなるメンバも必要としない。Member は閉じた型クラスでもあり（上に書かれた2つの型クラスが全てである）、オープンな和のユーザーがこのクラスのインスタンスを作ることは決して無い。ここでの Member は重複を許していて、同じリクエストに対するハンドラを重ねることができる。重複は無害である。リクエストは動的に一番近いハンドラによってハンドルされる。あと3行加えると重複は避けられる（[[15](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference15)] を参照せよ）。

Member はコンパイル時のみの制約で、gcast1 は2つの Typeable.TypeRep の要素を比べるだけで良いので、inj と prj の実行時間は（和の大きさについて）定数時間である。対照的に、かつて開発されたオープンな和のライブラリ [[18](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference18),[32](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference32)] の入射と射影は線型時間であった。

3.4 拡張可能作用ライブラリの全体像

これから拡張可能作用のライブラリの全体像を提示しよう。コアは Eff モナドとオープンな和の上に築かれている。作用とそのやりとりの定義はすべてユーザーによってなされる。Reader、例外、非決定論などの作用は一般的なので、私たちは例として実装し（[図2](拡張可能作用 ― モナド変換子に取って代わるもの 3#fig2) を参照せよ）、さらに利便性のためにいくつかのヘルパー関数を作っておいた。

図2. 拡張可能作用のライブラリ

-- 純粋なコードを実行しながらの、リクエストの送受信

data VE w r = Val w | E (Union r (VE w r))

admin :: Eff r w -> VE w r
send  :: (forall w. (a -> VE w r) -> Union r (VE w r)) -> Eff r a

run :: Eff Void w -> w
run m = case admin m of Val x -> x

-- 認識できないリクエストをリレーするためのヘルパー関数

handle_relay :: Typeable1 t =>
                Union (t :> r ) v -> (v -> Eff r a) ->
                (t v -> Eff r a) -> Eff r a
handle_relay u loop h = case decomp u of
  Right x -> h x
  Left u  -> send (\k -> fmap k u) >>= loop

interpose :: (Typeable1 t, Functor t, Member t r) =>
             Union r v -> (v -> Eff r a) ->
             (t v -> Eff r a) -> Eff r a
interpose u loop h = case prj u of
  Just x -> h x
  _      -> send (\k -> fmap k u) >>= loop

-- 読み取り作用

newtype Reader e v = Reader (e -> v)
    deriving (Typeable, Functor)

ask :: (Typeable e, Member (Reader e) r) => Eff r e
ask = send (inj . Reader)

runReader :: Typeable e =>
             Eff (Reader e B r ) w -> e -> Eff r w
runReader m e = loop (admin m) where
  loop (Val x) = return x
  loop (E u) =
    handle_relay u loop (\(Reader k) -> loop (k e))

local :: (Typeable e, Member (Reader e) r) =>
         (e -> e) -> Eff r a -> Eff r a

-- 例外

newtype Exc e v = Exc e
    deriving (Functor, Typeable)

throwError :: (Typeable e, Member (Exc e) r) => e -> Eff r a
throwError e = send (\_ -> inj $ Exc e)

runError :: Typeable e =>
            Eff (Exc e :> r) a -> Eff r (Either e a)

catchError :: (Typeable e, Member (Exc e) r) =>
              Eff r a -> (e -> Eff r a) -> Eff r a

-- 非決定論

data Choose v = forall a. Choose [a] (a -> v)

choose :: Member Choose r => [a] -> Eff r a
makeChoice :: Eff (Choose :> r) a -> Eff r [a]

-- トレース（デバッグ用）

data Trace v = Trace String (() -> v)

trace :: Member Trace r => String -> Eff r ()

runTrace :: Eff (Trace :> Void) w -> IO w

ライブラリの全体像は、[§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) の例をオープンな和を使って複数の作用を扱えるように拡張したものに、似ている。オープンな和はデータ型 VE w r に明示されている。送られたリクエストの型は Union r であるが、これはハンドルされた計算のステータスを表している。

まずは Reader 作用を見よう。リクエストの型 Reader は [§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) のものと同じである。送り手、つまり現在の環境の値を ask する（尋ねる）演算は、今度は和にリクエストの値を inj する（注入する）のである。この型は、単一作用のフレームワークの時から変化した ask の型に反映されている。Reader ハンドラはヘルパー関数 handle_relay を使って任意のリクエストを扱う。一般的に、リクエストは適当なハンドラが見つかるまで、あるハンドラから次のハンドラへと渡されていく。リクエストを分析し、その型をハンドラが分かるか調べ、分からなかったリクエストをさらに別のハンドラへ送る、というパターンは非常に一般的なので、私たちはこのパターンを関数 handle_relay へと具体化する。このヘルパー関数はライブラリ全体で使われている。この変種、interpose は、リレーの間にリクエストの型を「縮め」ない関数であり、local のような、同じリクエストの送り手でもあるようなハンドラによって使われている。

Reader ハンドラの脱糖衣化した (desugared) バージョンは以下の通りである。

runReader :: Typeable e =>
             Eff (Reader e :> r) w -> e -> Eff r w
runReader m e = loop (admin m) where
  loop (Val x) = return x
  loop (E u)   = case decomp u of
    Right (Reader k) -> loop (k e)
    Left u -> send (\k -> fmap k u) >>= loop

[§3.1](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-1) のように、返り値の型は、Reader e のリクエストは全て完全にハンドルされるということを示している――runReader 計算は r によって表された別のリクエストを持つかもしれないが。runReader ハンドラは先ほどと同様に、admin を使ってクライアントの計算のステータスを取得し、分析して、起こりうる3つの場合を処理する。

もしクライアントが完結していれば、結果が返される。
もしクライアントがリクエストを送ったら、私たちはそれが Reader リクエストかどうか確かめる。もしそうであれば、クライアントは動的環境における現在の値と共に再開される。クライアントは終了してもいいし、別のリクエストを送ってもいいので、私たちは loop するのである。
もし送られたリクエストが Reader で無かったら、私たちはそれを再び別のハンドラに送る。そのハンドラ u は、差出人住所、つまり型 t -> VE w (Reader e :> r) の保留 (suspension) を保持していなければならない。リクエストを再び送るときには、runReader は自分の保留 k を取得する（型は VE w (Reader e :> r) -> VE w' r である）。私たちはどうにかして、2つの保留を合成して t -> VE w' r 型のものを作らなければならない。runReader のハンドラが再開させれば、runReader のクライアントは再開する。

問題は、u が何なのかも（具体的な型すらも）分からないなかで、どのように k をリクエスト uのどこかにある保留と合成するかである。すべてのリクエストは種 * -> * の型構成子によって表されるということを思い出してほしい。リクエストの型全体は、型構成子を必要な計算のステータスの型に適用することによって、取得される。ここでの例において、知られていない別のリクエストの型全体は Union r (VE w (Reader e :> r)) である。runReader 自身の保留と合成することにより、型 Union r (VE w r) のリクエストが生まれる。k はまさに型 VE w (Reader e :> r) を持っているので、Union r が関手であり fmap k u が使えるならば、この問題は解決されるのである。型構成子 Union r はそれぞれのリクエストの型の関手である。このことは [§3.3](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3-3) の inj と prj に Functor t の制約が必要だということを証明している。Union r は関手なので、VE r はその関手によって導かれた自由モナド (free monad) である。ゆえに、Eff r モナドは余密度モナド (codensity monad) と自由モナドの組み合わせのようにも見える。

他の作用やそのハンドラも Reader のパターンに従っている。例外作用 Exc は、送り手が再開されることを期待していないので、より扱いやすい。例外の回復 catchError は local によく似ている――例外ハンドラは例外を再び投げうるのである。非決定論作用 Choose も馴染みがある。私たちは choose を、与えられたリストから値を非決定論的に選び出すための原始的な演算（Choose 作用の送り手）とする。馴染みの mplus と mzero は choose によって自明に表現できる。Choose 作用のハンドラ makeChoice は全ての成功した選択の結果のリストを生み出す。今のところハンドラは List モナドのように深さ優先探索を使っていて単純である。プログラマーはより洗練された探索戦略を使って自分のハンドラを書くことができる。Choose にリクエストを送る計算はさまざまなハンドラによってハンドルできるのである。