エフェクトシステムの考え方を言語によらない形で整理し、Koka / Effekt / Unison / OCaml / Polysemy / PureScript Run のエフェクトハンドラーを F# で再現したサンプルです。学習と設計検討のためのもので、本番向けのライブラリではありません。
- エフェクトシステムとは: 特定の言語によらないモデル
- F# で実現する場合の課題と解決
- サンプルの設計思想
- 方式の選び方
- 構成
関連する文書は次のとおりです。
- docs/porting-notes.md: 元資料の読解、エンジンごとの実装、各言語との対応、実測値、制限
- docs/row-polymorphism-report.md: SRTP で行多相をどこまで模倣できるかの検証
- docs/zio-report.md: Scala の ZIO とモデルの対応、F# のコードに活用できるものの検証
- docs/orsak-fio-report.md: F# の Orsak と FIO との比較、このプロジェクトに取り込めるものの検証
- API ドキュメント: XML コメントから生成します。型の設計思想はここにあります(生成のしかた)
.NET SDK 10 が必要です。
# 記事とマニュアルの例をすべて実行する
dotnet run --project samples/EffectSystem.Samples
# テスト (Release で動かすときは -c Release を付ける)
dotnet run --project tests/EffectSystem.Tests
# コストの計測
dotnet run -c Release --project samples/EffectSystem.Samples -- bench
# スタックの限界の計測 (1 MB のスタックで動かします。溢れるとプロセスごと落ちます)
dotnet run -c Release --project samples/EffectSystem.Samples -- limit direct-ctl 100000
# Orsak と FIO で書いた例を実行する
dotnet run --project samples/EffectSystem.PriorArtlimit のエンジン名は plain-recursion、direct-fn、direct-ctl、freer-fn、freer-ctl、freer-left、freer-fold、freer-try、freer-alternate、freer-tail-do です。samples/EffectSystem.PriorArt にも bench、parked、limit があります(使い方)。
fsdocs で、XML コメントから API ドキュメントを生成します。この README と docs/ の文書もサイトに含まれます。プロジェクトのビルドはスクリプトが行います。
dotnet tool restore
# output/ に生成する
dotnet fsi scripts/build-docs.fsx
# 生成して http://localhost:8901 で表示する (編集も反映されます)
dotnet fsi scripts/build-docs.fsx --watchoutput/ のリンクはサイトのルートを基準にしているので、ファイルを直接開かず、--watch を使うか、HTTP サーバーで配信して表示してください(例: python -m http.server --directory output)。
fsdocs は XML コメントの <code> をすべて F# として色付けします。Koka や OCaml のコードの色は目安として見てください。
エフェクトシステムは、計算を「何をしたいか」と「それをどう実現するか」に分ける仕組みです。計算は操作を要求するだけで、その意味は計算を囲むハンドラーが決めます。ハンドラーは要求と一緒に「計算の残り」を受け取るので、例外、非同期、ジェネレーターのような制御の仕組みも同じ枠組みで書けます。
左は ask() で止まった計算で、琥珀の部分が継続、つまり計算の残りです。中央の番号の順に、操作を要求し、残りを値として渡し、答えを持って再開します。呼ばれた側が呼び出し元の残りを値として受け取るところが、普通の関数呼び出しとの違いです。右は同じハンドラーの本体を 5 通りに書いたときの時間の流れで、下段はハンドラーを重ねるごとに操作が消えていく様子です。図は Deep ハンドラーだけを描いています。
以下、この図の各要素を順に定義します。
「エフェクトシステム」は狭い意味では、計算が起こしうる効果を型で追跡する型システムを指します(Lucassen & Gifford 1988)。ここでは操作とハンドラーの仕組み全体を指す広い意味で使い、型による追跡は設計軸の 1 つとして扱います。
操作は「A を渡すと、いずれ B が返ってくる」という要求です。エフェクトは操作の集まりです。どちらもシグネチャだけで、実装を持ちません。
op : A ⇝ B
Ask V = { ask : () ⇝ V }
Emit V = { emit : V ⇝ () }
State S = { get : () ⇝ S, put : S ⇝ () }
エフェクト E を使って R を返す計算は、次のどちらかの状態にあります。
Comp(E, R) = return(r) r : R を返して終わった
| op(a, k) op を引数 a で要求して止まっている
k : B → Comp(E, R) は答えを受け取った後の計算の残り (継続)
つまり計算は、操作を節とする木です。
プログラム 木
v = ask() ask((), λv.
emit(v) emit(v, λ_.
return v return(v)))
計算をつなげると、木の葉に次の計算が接ぎ木されます。
return(r) >>= f = f(r)
op(a, k) >>= f = op(a, λb. k(b) >>= f)
「代数的」は、計算を「操作を演算記号とする項」、つまりこの木として扱う見方に由来します。2 行目の等式は、そのような操作が満たす性質で、後続の計算が操作の内側へ分配されることを表しています(Plotkin & Power 2003)。
ハンドラーは、この木を畳み込んで別の計算へ変える関数です(Plotkin & Pretnar 2009)。
handle H (return(r)) = H.return(r)
handle H (op(a, k)) = H.op(a, λb. handle H (k(b))) H が op を扱うとき
= op(a, λb. handle H (k(b))) 扱わないときは外側へ転送する
H.op が受け取る第 2 引数が resume と呼ばれるものです。これを呼ぶと、止まっていた計算が再開します。
型で見ると、ハンドラーは扱ったエフェクトを消します。すべて消えた計算だけが実行できます。
handle H : Comp(E ∪ F, R) → Comp(F, R')
run : Comp(∅, R) → R
Hask = { ask(_, k) = k("x") }
Hemit = { emit(m, k) = print(m); k(()) }
program = ask((), λv. emit(v, λ_. return(v)))
handle Hask program
→ handle Hask emit("x", λ_. return("x")) k("x") で再開した
→ emit("x", λ_. return("x")) Hask は emit を扱わないので転送した。ask は消えた
handle Hemit emit("x", λ_. return("x"))
→ print("x"); return("x") emit も消えた
run return("x") = "x"
program は ask がどこから値を取るのか、emit が何をするのかを知りません。Hask を固定値に、Hemit をリストへの蓄積に差し替えれば、program を変えずにテストできます。
ハンドラーが継続 k をどう使うかによって、まったく別の機能になります。専用の構文に見えていたものが、同じ仕組みの使い方の違いとして説明できます。
k の使い方 |
得られる機能 | ハンドラーの形 | サンプル |
|---|---|---|---|
| 呼ばない | 例外、早期脱出 | raise(e, _) = return(Error e) |
KokaStyle.fs の tryResumable |
| 末尾で 1 回 | 依存性の注入、Reader | ask(_, k) = k(v) |
KokaStyle.fs の askHandler |
| 途中で 1 回 | 前後処理、トランザクション | op(a, k) = 前処理; r = k(b); 後処理; r |
Advanced.fs の transaction |
| 状態を渡しながら 1 回 | State | get(_, k) = λs. k(s)(s) |
Advanced.fs の runState |
| 保存して後で | ジェネレーター、非同期、スケジューラー | yield(v, k) = Cons(v, k) |
OCamlManual.fs の invert、run |
| 複数回 | 非決定計算、バックトラック | choose(_, k) = k(true) ++ k(false) |
Advanced.fs の runAll |
Scala の ZIO は、この表のうち末尾で 1 回の行だけを利用者に開き、複数回を除く残りの 4 行をランタイムの命令として持ちます(対応表)。継続を利用者に渡さないので、中断の最中でも後始末を保証できます(課題 8)。
外側のハンドラーが捕捉する継続には、内側のハンドラーが含まれます。そのため順序を変えると結果が変わります。
program = b = choose(); s = get(); put(s + 1); return (b, s)
handle NonDet (handle State(0) program) → [((true, 0), 1), ((false, 0), 1)] 分岐ごとに状態が複製される
handle State(0) (handle NonDet program) → ([(true, 0), (false, 1)], 2) 分岐をまたいで状態が共有される
モナド変換子の積み順と同じ現象です。順序は欠陥ではなく、計算の意味を選ぶ手段になります(Advanced.fs の stateInsideNonDet、stateOutsideNonDet)。
順序が意味を持つのは、継続を複製したり、保存したり、捨てたりするハンドラーがあるときです。別々の操作を扱うハンドラーが末尾で 1 回再開するだけなら、順序を変えても結果は変わりません。ZIO の provide が層を渡す順序を問わないのも、サービスがすべてこの形なので成り立ちます(確認)。
ここまでのモデルは共通で、実装によって次の点が異なります。
| 軸 | 選択肢 | 決まること |
|---|---|---|
| 操作の意味を決めるもの | 利用者のハンドラー / ランタイムの命令(利用者は末尾で 1 回の操作だけを定義する) | 利用者が継続を扱う操作を定義できるか。ランタイムの命令にすると定義はできないが、継続が 1 回で終わることを前提に後始末と中断を保証できる |
| 継続の表現 | スタックの断片 / ヒープ上のデータ / ヒープ上の可変配列 | 再開の回数とコスト。スタックは複製しなければ安価だが 1 回限りで、データなら何回でも再開できる。可変配列はスタックの深さに縛られないが、複製しないので 1 回限り |
| 継続の寿命 | ハンドラーの節の中 / 値として持ち出せる | 再開されなかった継続の後始末を言語が行えるか。節の中なら、節が終わった時点で再開されていないと分かるので、巻き戻して finally を走らせられる(Koka の ctl)。持ち出せるなら、再開するか例外で再開するかは利用者の責任になる(Koka の raw ctl、OCaml、このリポジトリのエンジン) |
| ハンドラーの範囲 | Deep / Shallow | 継続にハンドラーを含むか。Deep は handle H (k(b)) を渡し、Shallow は k(b) を渡す。Shallow なら次の操作の前にハンドラーを替えられる |
| ハンドラーの探し方 | 動的(最も近いもの)/ 字句(能力) | 同じ種類のハンドラーが重なったときの呼び先 |
| 静的検査 | 型で追跡 / 能力のスコープ / なし | ハンドラーの付け忘れを検出する時期 |
| 計算の書き方 | 直接 / モナド | 普通の関数のまま書けるか |
既存の言語とライブラリは、この空間の中の点として位置づけられます。6 言語の列は記事とマニュアルに、ZIO の列はドキュメントとソースによります(ZIO の検証)。
| 軸 | Koka | Effekt | Unison | OCaml | Polysemy | Run | ZIO |
|---|---|---|---|---|---|---|---|
| 操作の意味を決めるもの | 利用者のハンドラー | 利用者のハンドラー | 利用者のハンドラー | 利用者のハンドラー | 利用者のハンドラー | 利用者のハンドラー | ランタイムの命令 |
| 再開の回数 | 多 | 多 | 多 | 1(実行時検査) | API による | API による | 1(利用者には渡らない) |
| ハンドラーの範囲 | Deep | Deep | 手で再インストール | Deep / Shallow | Deep | Deep / 手書き | Deep に当たる(サービス) |
| 探し方 | 最も近いもの | 字句(能力) | 最も近いもの | 最も近いもの | 最も近いもの | 最も近いもの | 最も近いもの(型タグ) |
| 静的検査 | あり | あり | あり | なし | あり | あり | あり(R) |
| 書き方 | 直接 | 直接 | 直接 | 直接 | do 記法 | do 記法 | for 内包表記 |
操作の意味をランタイムの命令が決めるのは ZIO だけです(ZIO 系の位置づけ)。
どちらも上のモデルの実現方法です。前者は言語やランタイムに組み込まれることが多く、操作を呼ぶと制御がすぐハンドラーへ移るように見えます。後者は木をライブラリのデータとして持ち、後から解釈します。
後者では継続が暗黙で 1 回だけ再開されるとよく説明されますが、それは interpret のような API の性質で、方式の制約ではありません。実際、Run の runChoose は継続を 2 回呼び、runExcept は 1 回も呼びません(確認の詳細)。
Scala の ZIO と、それに倣った F# の Orsak と FIO を、ここでは ZIO 系と呼びます。設計軸の上では、操作の意味をランタイムの命令が決め、利用者が定義できるのは末尾で 1 回の操作(ZIO のサービス、Orsak の提供者インターフェイス、FIO で引数として渡す能力)だけ、という点にあります。継続が利用者に渡らないので、再開されない継続の後始末も、複数回の再開による二重の解放も、利用者が気にする必要はありません。ZIO と FIO の実行系は、これを前提に中断の最中でも後始末を保証します(課題 8)。継続をどこまで利用者に開くと後始末の責任がどう移るかは、ZIO の検証にあります。
ZIO は、型の追跡(R と E)、末尾で 1 回の利用者の操作、底の実行系(ファイバー、中断、後始末)の 3 つの層に分けられます。Orsak は型の層を .NET の Task の上に、FIO は底の実行系を受け継いだもので、どちらも F# での実現なので、上の表には入れていません(層ごとの比較)。このリポジトリの Rio と Zio も ZIO と同じ型の層を持ちますが、底が Freer なので継続まで開けてしまい、ZIO 系の保証は持てません。
F# には限定継続も GADT も高カインド型も行多相もありませんが、エフェクトハンドラーの意味論は標準の F# だけで再現できます。記事の 6 言語の例とマニュアルの例は、出力まで一致する形で動きます(差は 1 点だけで、移植ノートに記録しています)。
先に、モデルと F# の対応を示します。Freer エンジンがモデルに最も近い実装です。
| モデル | F# |
|---|---|
操作 ask : () ⇝ V |
Effect<'v> を実装する Ask<'v> |
計算 Comp(E, R) |
Eff<'a>(E は型に現れない) |
return(r) / op(a, k) |
Pure r / Impure(op, k) |
>>= |
eff { } の let! |
| 操作の要求 | Eff.perform Ask |
H.op(a, k) |
Eff.ctl (fun op resume -> ...) |
H.return |
Eff.handleWith の第 1 引数 |
handle H |
Eff.handle [ ... ] |
run |
Eff.run |
continue と pure は F# の予約語(FS0046)なので、API は resume と ret にしています。
open EffectSystem
open EffectSystem.Freer
type Ask<'v> =
| Ask
interface Effect<'v>
let program: Eff<string> =
eff {
let! (name: string) = Eff.perform Ask
return "Hello, " + name
}
program
|> Eff.handle [ Eff.ctl (fun (_: Ask<string>) resume -> resume "world") ]
|> Eff.run
// "Hello, world"F# にはモデルを直接書くための機能がいくつか欠けています。以下、課題ごとに解決と代償を示します。
OCaml の perform や Koka の resume の土台である限定継続が .NET にはなく、スタックを切り替えることも複製することもできません。そこで継続の置き場所を 3 通り用意しました。
3 つの列は、同じ計算が操作で止まったときの様子で、琥珀が継続の実体です。「普通の関数」と「何回でも」が同じ列にないことが、F# で方式が 1 つにまとまらない理由です。
| 方式 | 継続の置き場所 | 計算の書き方 | 再開の回数 | 代償 |
|---|---|---|---|---|
| Direct | 専用スレッドのスタック | 普通の関数 | 1 回 | ファイバーごとにスレッドを 1 本使う |
| Freer | ヒープ上のクロージャ | eff { } |
何回でも | 計算が Eff<'a> になり、呼び出し元にも波及する |
| Async one-shot | Async の継続 |
async { } |
1 回 | 計算が Async<'a> になり、操作はメソッドとして渡す |
Direct はスレッド間で実行権を手渡しして、同時に動くスレッドを常に 1 つに保ちます。スレッドのスタックは複製できないので、再開が 1 回に限られます。OCaml がワンショットである理由と同じ制約が、F# でも同じ形で現れます。
Async.FromContinuations の (ok, err, cancel) はそのまま継続に使えます。ok が OCaml の continue、err が discontinue に当たり、2 回目の呼び出しは FSharp.Core が例外にします。cancel は自動では呼ばれないので、止まっている間の中断に応じるには、トークンに登録して自分で呼びます(AsyncOneShot.fs の capture)。
OCaml の type _ Effect.t += Ask : string Effect.t は、後から足せるバリアントと GADT の組み合わせです。F# の判別共用体は閉じていて、GADT もありません。
答えの型だけを持つ印のインターフェイスを用意し、判別共用体に実装させることで解決しました。
type Effect<'a> =
interface
end
type Ask<'v> =
| Ask
interface Effect<'v>
type Emit<'v> =
| Emit of 'v
interface Effect<unit>- インターフェイスなので、誰でも後から操作を足せます。
- .NET のジェネリクスは実行時に残るので、
Ask<string>とAsk<int>は別の操作として区別できます。OCaml で functor が必要だった場面が 1 行で済みます。 - ハンドラーの分岐は
ctl<'E, 'x, 'r when 'E :> Effect<'x>>という形で受けます。'Eが決まれば答えの型'xが決まり、resumeの型も決まります。
内部には obj と unbox が残りますが、perform と ctl の中に閉じ込めているので、利用者はキャストを書きません。
代償: 操作の網羅性は検査されません。F# の関数はランク 2 多相を引数に取れないので、OCaml の effc のように 1 つの match にまとめられず、分岐のリストになります。また、型が同じ操作はすべて同じ操作として扱われるので、要素型が同じ invert を入れ子にすると、外側の操作を内側のハンドラーが受けてしまいます。OCaml は呼び出しごとに局所モジュールで新しい操作を作れますが、型で探す方式では同じことができません(能力で探す方式なら混ざりません)。
Haskell の Free f は任意の Functor を、Polysemy の Sem r はエフェクトのリストを型引数に取ります。いずれも型コンストラクターを型引数に渡す機能が前提ですが、F# にはありません。
木の型を Eff<'a> の 1 つに固定して解決しました。節には操作を obj として入れるので、エフェクトの和も Functor の定義も要りません。
type Eff<'a> =
| Pure of 'a
| Impure of effect: obj * resume: (Result<obj, exn> -> Eff<'a>)
| Delayed of (unit -> Eff<'a>)
| Bound of BindNode<'a>resume が Result を受け取るのは、値だけでなく例外でも再開するためです。Delayed と Bound は課題 6 で使います。
FSharpPlus の Free<'F<'T>, 'T> は SRTP で高カインド型を模倣する別解で、比較のため src/EffectSystem.Plus/ に実装しています。
Koka の <ask<a>, emit<a> | e> はハンドラーを被せるたびに 1 つ消えますが、F# に行はありません。これがエフェクト安全性に関わる最大の課題です。
| 方式 | 検査の仕組み | 付け忘れの結果 | 制限 |
|---|---|---|---|
| Freer 単体 | なし | Eff.run で実行時に Unhandled |
|
| Capability | 能力を値として引数で受ける | 能力がないので呼び出せない | 引数が増える。ハンドラーの外へ持ち出した能力は実行時に Unhandled |
| Rio | インターフェイス制約 | FS0193 | 行は最後にまとめて閉じる。途中で消すには残りの行を転送クラスに列挙する。IAsk<int> と IAsk<string> を同時に要求できない |
| RecordEnv | メンバー制約 | FS0001 | 行は最後にまとめて閉じる。環境を型変数のまま扱う関数には inline が要る |
| StaticRow | 幽霊型のスロット | FS0001 | 1 段ずつ消えるが、エフェクトの追加で全シグネチャが変わる |
要点は、行とは「必要なものの一覧」だということです。その値を渡すことにすれば、スコープが行と同じ役割を果たします。これは Effekt の能力渡しと同じ考え方です。
// def askHandler[R, A](a : A) { action: () => R / Ask[A] }: R / {} = {
// try { action() } with Ask[A] { def ask() = resume(a) }
// }
let askHandler (a: 'a) (action: IAsk<'a> -> Eff<'r>) : Eff<'r> =
reset (fun prompt ->
action
{ new IAsk<'a> with
member _.Ask() = shift prompt (fun resume -> resume a) })能力の引数を省きたいときは Rio を使います。注釈がなくても、必要なエフェクトの一覧が型として推論されます。
let askEmitRow (out: Log) =
rio {
out "Start"
let! v = ask ()
do! emit v
out "End"
}
// val askEmitRow:
// out: Log -> Rio<'a,unit> when 'a :> IEmit<'b> and 'a :> IAsk<'b>F# の Orsak も同じ符号化を使っていて、推論される型もコンパイル時の検査も Rio と同じになります(確認)。
計算の途中で行の一部を消すときは、Rio.provideSome で子の計算を包み、消す能力と残りの行を転送クラスに書きます(EffektStyle.fs の localAsk)。ZIO の provideSomeLayer[R0] が残りの行を型引数で受けるのと同じ形です。残りは列挙するしかなく、Koka の <ask|e> のように開いたままにはできません(確認)。
環境のクラスを書きたくないときは RecordEnv を使います。インターフェイス制約を SRTP のメンバー制約に置き換えると、レコードをそのまま環境にできます。
let inline ask () : Rio< ^R, 'v> when ^R: (member Ask: IAsk<'v>) =
Rio(fun env -> (^R: (member Ask: IAsk<'v>) env).Ask())
// AppEnv のクラスも転送も要らない。
askEmit out |> Rio.run {| Ask = ask; Emit = emit |}フィールドの名前がラベルの役割を果たすので、IAsk<int> と IAsk<string> も名前を分ければ同時に要求できます。ただし、行を 1 段ずつ消す手段にはなりません。SRTP で行多相をどこまで模倣できるかは検証レポートにあります。
Freer の計算はモナドなので、perform (Xchg 0) + perform (Xchg 1) のように式の途中で操作を呼べません。コンピュテーション式の let! で 1 つずつ束縛します。普通の関数のまま書く必要があるときは Direct を使います。
一方、Koka と Effekt の with 糖衣はそのまま再現できます。with h は h (fun cap -> 残り) の糖衣なので、Bind を関数適用にしたビルダーで同じ形になります。
// with askHandler("Ask Value")
// with emitHandler
// askEmit[String]()
handlers {
let! ask = askHandler "Ask Value"
let! emit = emitHandler out
return! askEmit ask emit out
}
|> Eff.run能力の寿命も同じ形で書けます。能力を作ってスコープの終わりに解放するハンドラーを重ねると、依存の共有と逆順の解放が得られます(EffektStyle.fs の scoped)。
末尾で再開するだけのハンドラーでも、素直に書くと「ハンドラー → resume → 次のハンドラー」と操作の回数だけ呼び出しが積まれます。F# の .tail 呼び出しは Debug では既定で無効で、頼れません。
Freer では再開を Delayed で包み、Eff.run のループへ戻すトランポリンにしました。継続を受け取らない Eff.fn は、答えをその場で渡して進みます。これは自己末尾呼び出しなので、コンパイラがループにします。どちらも Tailcalls=false の Debug ビルドで、1 MB のスタックで 100 万回の操作が完走します。
bind が左にネストする計算にも手当てが要ります。モデルの等式 op(a, k) >>= f = op(a, λb. k(b) >>= f) をそのまま再帰で書くと、再開のたびにネストをたどるので、操作 1 回のコストが深さに比例し、スタックも伸びます。そこで bind は節 Bound を作るだけにして、進めるときにループの中で右へ付け替えました(実装)。型整列キューなしで操作 1 回のコストが深さに比例しなくなり、1 MB のスタックで深さ 100 万が完走します(実測)。
ただし、入れ子の try は別です。F# の try は最初の区間しか覆えないので、操作のたびに全段の try を掛け直します。コストとスタックが入れ子の深さに比例し、1 MB のスタックでは 2 千段で溢れます。
末尾の do! は、この節も作りません。do! m は末尾にあっても既定では Bind になるので、do! で再帰すると節が深さの分だけ残ります。F# 10 のコンパイラは、ビルダーに ReturnFromFinal があれば末尾の return! と do! をそれへ脱糖します(FS-1330)。m をそのまま返すようにして、再帰してもメモリが増えないようにしました。try の中は末尾として扱われないので、例外の捕捉は変わりません。
Direct にはトランポリンが使えないので、Koka の ctl と fun の区別を持ち込みました。末尾再開と決まっている Deep.fn はエンジン内のループで答えを返すのでスタックが伸びません。Deep.ctl は .tail に依存し、Tailcalls=false では 5,000 回の操作で溢れました。Directory.Build.props で Tailcalls=true にしているのはこのためです。
継続のクロージャを何度呼んでも、そこに捕捉された可変状態は複製されません。F# には次の落とし穴があり、テストで挙動を固定しています。
let mutable: クロージャに捕捉されると暗黙に参照セルになるので、effの中で使うと再開をまたいで共有されます。分岐ごとに独立なら[1; 1]になる計算が[1; 2]になります。状態はエフェクトか引数で持ってください。for: 列挙子は可変なので、そのまま使うと再開のたびに壊れます。effのForは先に不変リストへ変換しています。そのため無限列は扱えません。finally: 再開ごとに走り、再開されずに捨てられた経路では走りません。確実に走らせるにはEff.ctlKのk.Discontinueで再開します。Koka は再開せずに終わったctlの節から自動で巻き戻すので、ここは Koka と違います(設計軸の継続の寿命)。
モデルの「継続を呼ばない」は、失敗の種類を区別しません。ZIO は失敗を、型に現れる予期したエラー、型に現れないプログラムの誤り(欠陥)、外から止められたこと(中断)の 3 種類に分けます(分類)。
「継続を呼ばない」形は、リソースを持つ計算では finally を飛ばします。
| 表し方 | 失敗の型 | finally |
サンプル |
|---|---|---|---|
| 継続を呼ばない | 操作の型 | 走らない | Advanced.fs の finallySkippedWhenAbandoned |
Discontinue で再開する |
exn |
走る | Advanced.fs の finallyWithDiscontinue |
計算の結果に Result を持つ |
'E |
走る | ZioStyle.fs の exampleEnsuring |
外から止める中断は、モデルの外にあります。F# の Async はトークンで中断できますが、親が終わっても子は走り続け、中断を遅らせる標準の手段がなく、同時の失敗は 1 つしか残らず、finally の例外は本体の例外を消します(比較)。
ZIO は継続を利用者に渡さず、1 回で終わることを前提にして、これらを保証しています。同じ形を F# へ写した単一スレッドの試作でも同じ意味論が動きますが(試作)、複数回の再開と、利用者が定義する制御を諦めることになります。利用者に継続を渡す設計では、後始末と中断の保証はハンドラーの規律に頼ることになり、複数回の再開では資源を何回解放するかが定まりません。本体は利用者に継続を渡すことを主題にしているので、この形は入れていません(ZIO 系の位置づけ)。
F# の FIO は、この形をマルチスレッドで実装したライブラリです。比べた 11 の場面のうち 7 つで ZIO と同じ結果になり、違いは中断したファイバーの結果を後始末より先に返すことと、失敗を 1 つの値で記録することから来ます(比較)。
このほかに踏んだ問題(FSharpPlus の Coproduct が実行時に落ちる件、Async の継続がスレッドプールへ回される件)は移植ノートに記録しています。
操作はシグネチャに過ぎない、というモデルの考え方をそのまま型にしました。Ask<'v> は Effect<'a> にしか依存しないので、同じ型を Direct でも Freer でも処理できます。計算の書き方は変わりますが、宣言は変わりません。
.NET にはスタックを複製する手段がないので、直接スタイルとマルチショットを同時には得られません。トレードオフが原理的なものなら、1 つの API の裏に隠すよりも、選べる形で並べるほうが理解の助けになります。
Effect<'a> 操作の宣言
├─ Direct 161 行 スレッドのスタックに継続を置く
└─ Freer 186 行 ヒープ上のクロージャに継続を置く
├─ Capability + Rio 58 行 型ではなく能力で操作を探す
│ └─ RecordEnv (サンプル) レコードを環境にする
└─ StaticRow (サンプル) 幽霊型で行を表す
Effect<'a> を使わない別系統
├─ Async one-shot (サンプル) 操作はメソッド、継続は Async のもの
└─ FSharpPlus Free 66 行 操作は Functor、PureScript Run の形
行数はコメントと空行を除いたものです。どれも一度に読み切れる大きさに抑えています。Capability が短いのは、Freer に「型の代わりに目印で探す」分岐を 1 つ足すだけで実現できるからです。
サンプルは言語ごとにファイルを分け、元のコードを XML コメントとしてすぐ上に置いています。API ドキュメントにも同じ形で載ります。名前も ctl、fn、resume、retc / exnc / effc、matchWith、interpret、handlers のように元の言語に合わせ、並べて読めるようにしました。
/// <summary>ask に固定値で答えるインタープリター。</summary>
/// <remarks>
/// <code lang="haskell"><![CDATA[
/// runAsk :: v -> Sem (Ask v ': r) a -> Sem r a
/// runAsk value = interpret $ \case
/// Ask -> pure value
/// ]]></code>
/// </remarks>
let runAsk (value: 'v) (m: Eff<'a>) : Eff<'a> =
m |> Eff.handle [ Eff.interpret (fun (_: Ask<'v>) -> Eff.ret value) ]GADT がない以上、どこかにキャストは必要です。それを perform と分岐の生成関数に集め、利用者のコードには出さないようにしました。
ビルド設定で結果が変わるエンジンは信頼しにくいので、Freer はトランポリンとループで .tail への依存をなくしました。依存が残る Direct の ctl については、依存していることと限界の実測値を明記しています。
- 期待値には、記事とマニュアルに掲載された実行結果をそのまま使います。
- コンパイルエラーになるという主張は tests/compile-fail/ のスクリプトで検証します。通るスクリプトを対照群として並べ、狙いどおりの理由で失敗していることを確かめます。
- FSharpPlus、Orsak、FIO の挙動のような外部の事実もテストで固定し、版を上げて変わったら分かるようにしています。
- 計測のコマンドもリポジトリに入れ、数値を再現できるようにしています。
EffectSystem 本体は FSharp.Core だけに依存します。FSharpPlus は別プロジェクト、Expecto はテストだけで使います。継続の操作には判別共用体と関数で足りるので、FSharpPlus は必須にしていません。比較のために使う Orsak と FIO も、samples/EffectSystem.PriorArt/ に分けています。
本番向けのライブラリではないので、次の点は実装していません。必要になれば、まずここから手を入れることになります。
- 外からの中断とリソースの保証(複数回の再開と、利用者が定義する制御を諦めることになる。課題 8)。F# では FIO が実装している
- Direct のスレッドプール化と、再開されなかったファイバーの後始末。FIO のファイバーはスレッドプールの上で動くが、継続を利用者に渡さないので、Direct の
performは写せない - SRTP による行の型レベル探索(開いた行を注釈できず、コンパイル時間が行の深さに対して指数的に伸びる。理由の詳細)
F# では設計軸を独立に選べるわけではなく、次の 2 つが残りを強く規定します。
- 継続をどこに置くか。 スタックに置くなら直接スタイルになりますが、再開は 1 回に限られます。ヒープに置くなら再開は何回でもできますが、計算はコンピュテーション式で書くことになります。
- 操作をどう探すか。 型で探すと記述は短いですが、検査は実行時になります。能力で探すと引数が増えますが、検査はコンパイル時になります。
横軸は再開の回数、縦軸はハンドラーの付け忘れを検出する時期です。白い枠が元の言語、青い枠が F# の方式で、★がアプリケーションの既定です。灰色の矢印は位置を保って写せたもの、赤は写すと位置が変わるもの、緑は実装の上に積む関係を表します。設計軸の表に入れた ZIO は描いていません。利用者の操作が末尾で 1 回に限られるので、この 2 つの軸には ZIO 系の利点(中断と後始末の保証)が現れないためです(ZIO 系の位置づけ)。
Koka、Unison、Polysemy を Freer へ写すと、行多相がないので検査を失って下へ落ちます。失った検査は、Freer の上に Capability や StaticRow を積むと戻ります。普通の関数で書きたいなら左下の Direct しかなく、検査と複数回の再開の両方を諦めることになります。
| 目的 | 方式 | 理由 | 対応する言語 | 操作 1 回の目安 |
|---|---|---|---|---|
| アプリケーションの既定 | Capability + Rio | ハンドラーの付け忘れがコンパイルエラーになる。マルチショットも使える | Effekt | Capability は約 130 ns、Rio は約 170 ns |
| Rio の環境のクラスを書きたくない | RecordEnv | レコードをそのまま環境にできる。操作だけを inline にして、組み上げた計算は名前付きレコードで閉じる |
Effekt | 約 170 ns(Rio と同じ) |
| 継続を直接扱うライブラリ、学習 | Freer | Koka / Unison / Polysemy の書き方をすべて写せる | Koka / Unison / Polysemy | fn は約 60 ns、ctl は約 130 ns |
既存の async コードに組み込む |
Async one-shot | FSharp.Core だけで書け、タスクごとにスレッドを消費しない | OCaml の意味論 | 約 350 ns(最速経路の値) |
| 関数の色を変えられない、OCaml の例をそのまま動かしたい | Direct | 普通の関数のまま perform できる唯一の方式。ファイバーごとにスレッドを 1 本使う |
OCaml | 約 400〜500 ns(生成は約 80 µs) |
| すでに FSharpPlus を使っていて、変換子へ解釈したい | FSharpPlus Free | Free.fold で任意のモナドへ畳み込める。それ以外では勧めない(理由) |
PureScript Run | 同じ条件で測っていない |
測定の条件と幅は移植ノートにあります。
Capability でも、末尾で 1 回再開するだけの操作なら shift は要りません。能力のメソッドで Eff.ret を返せば継続を取り出さずに済み、reset もなくせます。コストは約 25 ns まで下がります(EffektStyle.fs の askHandlerDirect)。ただし区切りがなくなるので、ハンドラーの外へ持ち出した能力は Unhandled にならず、そのまま答えを返します。
このリポジトリは学習用です。同じことを本番でしたいときの F# の選択肢には Orsak と FIO があります。Orsak は Rio の環境に型付きの失敗を足して Task の上で動かすので、既存の非同期のコードに組み込みやすく、操作 1 回は Rio と同じ桁です。FIO は ZIO と同じ中断、後始末、構造化並行性を持ちます。どちらも、利用者が定義できるのは末尾で 1 回の操作だけで、複数回の再開は持ちません(位置づけ、比較)。
行に載せる価値があるのは、局所的で、消す演算子があり、型で追う意味があるものです。トランザクションやリクエストの文脈が当たります。サービスの実装が使う依存はコンストラクターで渡し、時刻やログのようにどこでも使う低レベルのものは載せません。ZIO も実際の使用からこの基準に落ち着いています(根拠)。
| パス | 内容 |
|---|---|
| src/EffectSystem/Core.fs | 操作の印 Effect<'a> と共通の例外 |
| src/EffectSystem/Freer.fs | Freer エンジン |
| src/EffectSystem/Direct.fs | Direct エンジン(Deep / Shallow) |
| src/EffectSystem/Capability.fs | 能力渡し、Rio、handlers |
| src/EffectSystem.Plus/RunStyle.fs | FSharpPlus の Free を使った Run の移植 |
| tests/EffectSystem.Tests/Tests.fs | 記事とマニュアルの出力を期待値にしたテスト |
| tests/EffectSystem.Tests/PriorArtTests.fs | Orsak と FIO のサンプルの出力と、ライブラリの挙動のテスト |
| tests/compile-fail/ | コンパイルエラーになることを確かめるスクリプトと対照群 |
| docs/porting-notes.md | 元資料の読解、エンジンごとの実装、各言語との対応、実測値、制限 |
| docs/row-polymorphism-report.md | SRTP で行多相をどこまで模倣できるかの検証 |
| docs/zio-report.md | Scala の ZIO とモデルの対応、F# のコードに活用できるものの検証 |
| docs/orsak-fio-report.md | F# の Orsak と FIO との比較、このプロジェクトに取り込めるものの検証 |
| docs/figures/ | この README の図(手書きの SVG) |
| scripts/build-docs.fsx | fsdocs でサイトを生成するスクリプト。テンプレートは docs/_template.html |
samples/EffectSystem.Samples/ の内容は次のとおりです。
| ファイル | 内容 | エンジン |
|---|---|---|
| KokaStyle.fs | Koka の写し | Freer |
| EffektStyle.fs | Effekt の写し、字句スコープ、Rio、行の局所処理、能力の寿命 | Capability |
| UnisonStyle.fs | Unison の写し | Freer の view |
| OCamlStyle.fs | 記事の OCaml の写し | Direct |
| OCamlManual.fs | マニュアル 12.24 の全例 | Direct |
| PolysemyStyle.fs | Polysemy の写し | Freer の interpret |
| PureScriptStyle.fs | PureScript Run の写し | FSharpPlus Free |
| AsyncOneShot.fs | Async の継続で書いたスケジューラー、止まっている間の中断 |
Async.FromContinuations |
| StaticRow.fs | 行を 1 段ずつ消す幽霊型 | Freer |
| RecordEnv.fs | レコードを環境にするメンバー制約 | Capability |
| Advanced.fs | State と NonDet、ジェネレーター、finally、トランザクション |
Freer |
| ZioStyle.fs | ZIO の失敗の型 E の写し、Orsak の and! |
Freer |
| Bench.fs | コストとスタックの計測 | すべて |
samples/EffectSystem.PriorArt/ は、F# の先行例をライブラリのまま使うサンプルです。
| ファイル | 内容 | ライブラリ |
|---|---|---|
| OrsakStyle.fs | 記事の askEmit、スコープで書くトランザクション、and! で失敗を合わせる |
Orsak 0.7.0 |
| FioStyle.fs | 記事の askEmit、中断でも rollback するトランザクション、親子の寿命、中断不可の領域 | FSharp.FIO 0.5.0-beta |
| Bench.fs | コスト、止まっている計算のメモリ、スタックの計測 | 両方 |
- funnycat, Algebraic Effects と Extensible Effects:6つの言語で学ぶエフェクトシステムの違いと共通点
- OCaml マニュアル 12.24 Effect handlers
- Lucassen, Gifford, Polymorphic Effect Systems, POPL 1988
- Plotkin, Power, Algebraic Operations and Generic Effects, Applied Categorical Structures, 2003
- Plotkin, Pretnar, Handlers of Algebraic Effects, ESOP 2009
- Brachthäuser, Schuster, Ostermann, Effects as Capabilities, OOPSLA 2020
- F# RFC FS-1330: Support tailcalls in computation expressions
- ZIO のドキュメント
- F# の先行例: Orsak(
Effect<'r, 'a, 'e>)、FIO(ファイバーの実行系)。動かして比べた結果はOrsak と FIO の検証にあります
実装の確認に使ったソースコードと、その他の論文は移植ノートの参考文献に、ZIO の詳しい出典は検証レポートの参考文献に、Orsak と FIO の出典はその参考文献にあります。
MIT です。ただし、XML コメントと文書に引用した記事とマニュアルのコードの権利は、それぞれの著作者にあります。