Skip to content

About

No description, website, or topics provided.

Resources

Stars

2 stars

Watchers

0 watching

Forks

Repository files navigation

EffectSystem

エフェクトシステムの考え方を言語によらない形で整理し、Koka / Effekt / Unison / OCaml / Polysemy / PureScript Run のエフェクトハンドラーを 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.PriorArt

limit のエンジン名は 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 --watch

output/ のリンクはサイトのルートを基準にしているので、ファイルを直接開かず、--watch を使うか、HTTP サーバーで配信して表示してください(例: python -m http.server --directory output)。

fsdocs は XML コメントの <code> をすべて F# として色付けします。Koka や OCaml のコードの色は目安として見てください。

エフェクトシステムとは

エフェクトシステムは、計算を「何をしたいか」と「それをどう実現するか」に分ける仕組みです。計算は操作を要求するだけで、その意味は計算を囲むハンドラーが決めます。ハンドラーは要求と一緒に「計算の残り」を受け取るので、例外、非同期、ジェネレーターのような制御の仕組みも同じ枠組みで書けます。

図1 エフェクトの仕組み

左は 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 系の位置づけ)。

Algebraic Effects と Extensible Effects

どちらも上のモデルの実現方法です。前者は言語やランタイムに組み込まれることが多く、操作を呼ぶと制御がすぐハンドラーへ移るように見えます。後者は木をライブラリのデータとして持ち、後から解釈します。

後者では継続が暗黙で 1 回だけ再開されるとよく説明されますが、それは interpret のような API の性質で、方式の制約ではありません。実際、Run の runChoose は継続を 2 回呼び、runExcept は 1 回も呼びません(確認の詳細)。

ZIO 系の位置づけ

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# で実現する場合の課題と解決

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# にはモデルを直接書くための機能がいくつか欠けています。以下、課題ごとに解決と代償を示します。

課題 1: 継続を取り出す手段がない

OCaml の perform や Koka の resume の土台である限定継続が .NET にはなく、スタックを切り替えることも複製することもできません。そこで継続の置き場所を 3 通り用意しました。

図2 継続の置き場所

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)。

課題 2: 操作の答えの型を表せない

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 は呼び出しごとに局所モジュールで新しい操作を作れますが、型で探す方式では同じことができません(能力で探す方式なら混ざりません)。

課題 3: 高カインド型がない

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/ に実装しています。

課題 4: 行多相がない

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 で行多相をどこまで模倣できるかは検証レポートにあります。

課題 5: 直接スタイルで書けない

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)。

課題 6: スタックが伸びる

末尾で再開するだけのハンドラーでも、素直に書くと「ハンドラー → 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 にしているのはこのためです。

課題 7: マルチショットと可変状態

継続のクロージャを何度呼んでも、そこに捕捉された可変状態は複製されません。F# には次の落とし穴があり、テストで挙動を固定しています。

  • let mutable: クロージャに捕捉されると暗黙に参照セルになるので、eff の中で使うと再開をまたいで共有されます。分岐ごとに独立なら [1; 1] になる計算が [1; 2] になります。状態はエフェクトか引数で持ってください。
  • for: 列挙子は可変なので、そのまま使うと再開のたびに壊れます。eff の For は先に不変リストへ変換しています。そのため無限列は扱えません。
  • finally: 再開ごとに走り、再開されずに捨てられた経路では走りません。確実に走らせるには Eff.ctlK の k.Discontinue で再開します。Koka は再開せずに終わった ctl の節から自動で巻き戻すので、ここは Koka と違います(設計軸の継続の寿命)。

課題 8: 失敗と中断を分けられない

モデルの「継続を呼ばない」は、失敗の種類を区別しません。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 でも処理できます。計算の書き方は変わりますが、宣言は変わりません。

万能の 1 つにまとめず、小さなエンジンを並べる

.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 回に限られます。ヒープに置くなら再開は何回でもできますが、計算はコンピュテーション式で書くことになります。
  • 操作をどう探すか。 型で探すと記述は短いですが、検査は実行時になります。能力で探すと引数が増えますが、検査はコンパイル時になります。

図3 設計空間の地図

横軸は再開の回数、縦軸はハンドラーの付け忘れを検出する時期です。白い枠が元の言語、青い枠が 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 コスト、止まっている計算のメモリ、スタックの計測 両方

参考文献

実装の確認に使ったソースコードと、その他の論文は移植ノートの参考文献に、ZIO の詳しい出典は検証レポートの参考文献に、Orsak と FIO の出典はその参考文献にあります。

ライセンス

MIT です。ただし、XML コメントと文書に引用した記事とマニュアルのコードの権利は、それぞれの著作者にあります。

About

No description, website, or topics provided.

Resources

Stars

2 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages