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

1. 導入

関数型プログラミング [[22](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference22)] の世界にモナドが導入された当初から、モナドは一般に合成しないと理解されてきた [[14](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference14),[29](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference29),[34](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference34)]。さまざまな「モナド合成」がモッジの「モナド射」[[23](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference23)] というアイデアに基づいて探求されてきた。いくつかの初期の設計 [[4](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference4),[5](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference5),[6](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference6),[29](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference29),[30](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference30)] はリャンら [[18](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference18)] によって、現在の Haskell の最先端となっている「モナド変換子ライブラリ」(MTL) (mtl-2.1.2) へと拡張された。

モナド変換子は、プログラマがモナドを多くのモナド変換子を通して集めて、単純なモナディックな作用の「層」を組み合わせて作用を生み出せるようにするフレームワークだ。作用を有する演算はさまざまな方法で合成しうるので、階層化するたびにプログラマは手動で、基底の、あるいは基本のモナドの演算がどのように現在の変換子まで「持ち上げ (lift)」られるかを表明する。（このアイデアは、フィリンスキ [[7](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference7),[8](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference8)] によって別の視点からより深く探求されている。）モナド変換子の標準の実装において、それぞれの層は長いスタックの中で積み上がるというオーバーヘッドがある（議論については [§4](拡張可能作用 ― モナド変換子に取って代わるもの 4#section4) を参照）。また、階層化は静的に決定され、プログラムの異なる個所において動的に変えることは簡単でない。最も重要なのは、いくつかの実用的な状況で、ある作用を他の作用の上へと完全に静的に階層化するのを避けることで望ましい意味論が得られる場合、作用が交替 (interleave) される必要があるということだ。

ゆえに、その人気とは裏腹に、モナド変換子のフレームワークは根本的に限界があるのだ。（これらの制限について [§5](拡張可能作用 ― モナド変換子に取って代わるもの 5#section5) で例を使いながら再び考察する。）モナド変換子の代わりのアプローチはいくつか存在する [[12](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference12),[19](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference19)]。その中でも私たちの研究と最も関係があるのは「拡張可能表示的言語仕様 (extensible denotational language specifications)」(EDLS) というカートライトとフェライセン [[3](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference3)] による、モナド変換子の元論文 [[18](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference18)] とほぼ同時期に発展したアプローチである。基本的なアイデアは、作用をやりとり (interaction) としてモデル化することである――変更可能な変数を更新し、例外を投げ、ファイルに書き込むようなプログラムの断片は、「支配者 (authority)」に「リクエスト」を送るのだ。そのリクエストは行おうとしているアクションを説明し、リクエストした側を再開するための「差出人住所 (return address)」あるいは継続を持っている。元の EDLS フレームワークでは、この支配者、つまりリクエストをリソースの変形として解釈するものは、ユーザーのプログラムの一部ではない（ちょうど、オペレーティングシステムのカーネルがユーザーのプロセスの一部でなく、Haskell で IO アクションの解釈器がユーザーのプログラムの一部でないのと同じである。）。この大域的な外部の支配者は、すべてのリソース（ファイル、メモリなど）を管理している――リクエストを解釈し、場合によっては、それをリクエストした側の代理で実行してその後リクエストした側に結果を渡して継続させ、場合によっては返事をするのを拒否するのだ。このアプローチの根本的な利点は、特に意味がなければ、作用を合成する順序を指定する必要は全くなく、単独の、静的に定まった作用の合成の順番を捧げる必要もないことだ。一方で欠点は、(i) 大域的な外部の支配者は拡張するのが難しく、(ii) 作用がカプセル化されておらず、(iii) 計算の作用が型に反映されていない、という点である。

自由モナド [[32](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference32)] とヒューとヒンツェの項代数のアプローチ [[9](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference9),[10](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference10)] に部分的に感化されつつ、私たちは以上の3つの問題に立ち向かっていく。

私たちは、中心的な、柔軟でない支配者を、分配された、自動的に拡張可能な、ユーザープログラムの一部である「役人」に置き換える。代数的ハンドラについての既存の研究 [[1](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference1),[25](拡張可能作用 ― モナド変換子に取って代わるもの 9#reference25)] に従って、私たちはそれぞれの部分的な（一部のリソースを支配し、一部のリクエストを解釈する）支配者をハンドラと呼ぶ。各ハンドラは、プログラムのクライアントの支配者であると同時に、クライアント自体でもある――ハンドラは、理解できないリクエストを受け取ったら、「上流 (upstream)」のハンドラにそのリクエストを渡すのだ。
第二に、そしてもっと重要なことに、私たちは、どの作用が計算の中で現在有効なのかを追跡するような、表現力のある型と作用のシステムを発展させる。このシステムは、現在の作用の順序付けられていないコレクションを持っている、オープンな和 (open union)（型で指標付けされた関手の余積 (a type-indexed coproduct of functors)）を保持している。各ハンドラのアクションは、ハンドルされていた作用を削除することで型に反映されているので、型システムが、プログラムがどこにも「ぶら下がった (dangling) 作用」を持たないことを保証している。

私たちの主要な貢献は以下の四つである。

MTL の構文を元につくられた、作用を好きな順番で組み合わせ、さらに標準的なモナド変換子のアプローチでは成しえなかった方法で交替する (interleave) することができる、ユーザーレベルの作用のフレームワーク。このシステムはありふれた拡張を用いた Haskell ライブラリであると分かるだろう――開発者は、既存のプログラムに最小限の構文上の変更を加えるだけで、すぐにこのシステムを使い始めることができるかもしれない。
実際のプログラムで微妙なバグを生む、モナド変換子の表現上の問題についての、詳細な分析。
作用ハンドラシステムの中心にある、拡張可能で、定数時間で動く、オープンな和型 (open union type) の、今までになかった実装。
新しいオープンな和型を中心に作られた、プログラムを通して作用を動的に追加、使用、削除する仕組みを提供するシステム。つまり、MTL に基づいた現在の Haskell のアプローチよりもずっと表現力のある作用のシステムを生み出したのだ。

要約すると、最終的な設計は、モナド変換子と EDLS を改良していて、型システムで正確に追跡される作用のやりとりを、より柔軟なものにしている。完全な Haskel の実装を、説明と肩慣らしの例とともに、http://okmij.org/ftp/Haskell/extensible/ で見ることができる。［[付録](拡張可能作用 ― モナド変換子に取って代わるもの付録)にソースコード一覧がある。］私たちは関係する部分を抜粋しながら、論文全体を通じてこのコードを参照する。［なお、Hackage に上がっているバージョンは https://hackage.haskell.org/package/extensible-effects で見られる。］

この論文のこれ以降の構造は以下の通りである。まず、様々な小さい例を使って、プログラマレベルのインターフェースを紹介する、拡張可能作用フレームワークの高水準な「ツアー」から始めよう ([§2](拡張可能作用 ― モナド変換子に取って代わるもの 2#section2))。次のセクション ([§3](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3)) では、完全な意味論を提供し、実装の重要な要素を説明する。そして [§4](拡張可能作用 ― モナド変換子に取って代わるもの 4#section4) で、私たちの設計が MTL 全体をシミュレートできるということを確認し、さらに [§5](拡張可能作用 ― モナド変換子に取って代わるもの 5#section5) では高度な例を使って、私たちの設計が MTL の表現性を超えているということを実証する。