代数的エフェクトが必要な理由

• 代数的エフェクトは 再開可能な例外 のように制御フローを捕捉して処理する言語機能で、Ante の中核機能であり、Koka、Effekt、Eff、Flix のような研究言語でも中心的に使われている
• 同じ仕組みで ジェネレーター、例外、async、コルーチン、自動微分 をライブラリレベルで作ることができ、さらに効果多相のおかげで map のような関数も効果の種類に関係なく一度だけ書けばよい
• データベースアクセス、出力、ロギング、状態の受け渡しのような 依存性注入 とコンテキスト受け渡しをエフェクトに置き換えると、テスト用 mock、出力の収集、ログフィルタリングをハンドラーの差し替えで処理できる
• 関数シグネチャに can IO、can Print、can Fail のようなエフェクトが現れると、純粋性の保証、記録/再生、セキュリティ監査に有利だが、すでに許可されているエフェクトは意図せず既存のハンドラーへ伝播することがある
• 従来の弱点は 効率性への懸念 だったが、最近の言語では tail-resumptive エフェクト最適化、evidence passing、単一 resume 制限、ハンドラー特化によってコストを減らしている

---

代数的エフェクトの基本モデル

• 代数的エフェクトは effect handlers とも呼ばれ、「再開可能な例外」というモデルで理解できる
• Ante の擬似コードではエフェクト関数を宣言し、関数シグネチャにそのエフェクトを使えることを can で示す
  • say_message: Unit -> Unit のようなエフェクト関数を呼び出すと、エフェクトを「投げる」形になる
  • 呼び出し側の関数は foo () can SayMessage のように、そのエフェクトを使う可能性をシグネチャに表す
• handle 式は try/catch に似ており、エフェクトを捕捉し、resume 呼び出しで中断された計算を再開する
  • say_message ハンドラーが print "Hello World!" を実行したあと resume () を呼ぶと、元の計算が続行されて 42 を返す
• 「algebraic」という名前は大部分が歴史的に残っている用語で、実際には effect handlers のほうがより正確な表現に近いが、利用者に馴染みのある名前として代数的エフェクトという呼び方を使っている

ユーザー定義の制御フロー

• 代数的エフェクトは 複数の言語機能 をひとつの仕組みで実装できるようにする
  • ジェネレーター
  • 例外
  • async
  • コルーチン
  • 自動微分
• 効果多相は what color is your function 問題を軽減する
  • map (input: Vec a) (f: a -> b can e): Vec b can e は、入力関数 f がどんなエフェクト e を実行しても、map も同じエフェクトを実行すると表現している
  • 同じ map を stdout 出力、非同期関数呼び出し、ストリームの yield などと一緒に使える
  • 多くの effect handlers 言語ではエフェクト変数 e を省略できるため、馴染みのある map (input: Vec a) (f: a -> b): Vec b の形で書ける
• 例外は、エフェクト処理時に resume を呼ばない方法 で実装できる
  • Throw a エフェクトの throw: a -> never_returns を定義する
  • 0 で割る場合は throw "error: Division by zero!" を呼び、ハンドラーはメッセージを出力したあと計算を再開しない
• ジェネレーターは Yield a エフェクトの yield: a -> Unit で実装できる
  • ベクター要素を走査しながら yield elem を呼ぶ
  • filter ハンドラーは yield された値が条件を満たすなら再び yield x を呼び、resume () で次の要素へ進む
  • my_for_each ハンドラーは yield された値ごとに関数 f を実行し、resume () で処理を続ける
• 協調的スケジューラーも yield: Unit -> Unit エフェクトで作ることができ、ハンドラーが制御を受け取って別の関数実行へ切り替える
  • Effekt の scheduler サンプル がこのパターンを示している
• 複数のエフェクトは互いによく合成でき、この点が他のエフェクト抽象化より使いやすい利点として挙げられている

依存性注入とテスト容易性

• エフェクトは一般的なビジネスアプリケーションでも 依存性注入 に使える
• データベースオブジェクトを関数引数として直接渡す代わりに Database エフェクトを定義できる
  • 従来の形は business_logic (db: Database) (x: I32) のように DB オブジェクトを引数に取る
  • エフェクトベースの形では business_logic (x: I32) can Database となり、内部で query "..." を呼び出す
• 具体的なデータベースの選択は呼び出しスタック上位のハンドラーが担う
  • 本番 DB を別の DB に切り替えたり、テスト用 mock DB に置き換えたりできる
  • mock_database ハンドラーは query メッセージを無視し、常に DbResponse.Ok を返すように resume できる
• 出力もエフェクトとして扱えば、テスト中に stdout へ直接書かず文字列として収集できる
  • print_to_string ハンドラーは print msg 呼び出しを捕捉し、all_messages 文字列に改行付きで蓄積する
  • output_messages は実際の出力なしで戻り値 1234 とメッセージ文字列を検証できる
• ロギングは Log エフェクトと LogLevel を使って条件付き出力に変えられる
  • log_handler はメッセージのレベルが設定された基準以上なら print msg を呼び出す
  • foo () with log_handler Error はエラーログだけを出力する

よりクリーンな API とコンテキスト受け渡し

• 代数的エフェクトは、プログラムやライブラリ全体に渡される Context オブジェクト パターンをエフェクトで表現できる
• Use a エフェクトは状態エフェクトと見なせ、get: Unit -> a と set: a -> Unit を提供する
  • state ハンドラーは初期状態を保持し、get には現在のコンテキストを返し、set には新しいコンテキストへ更新する
  • 例の state 定義は所有権ルールを無視しており、実際の実装では Copy a 制約が必要になる可能性がある
• ベクター内に文字列を保存し、インデックスをキーのように渡す例はコンテキスト受け渡しコストを示している
  • エフェクトを使わないと push_string、get_string、append_with_separator、example などが strings を毎回引数で受け取らなければならない
  • エフェクトベースの実装では、プリミティブ操作である push_string と get_string が get/set を呼び出し、上位コードは strings を直接渡さなくてよい
• この方式は、内部のコンテキスト受け渡しをライブラリが隠蔽する場合に向いている
  • ライブラリ利用者はコンテキスト受け渡し方式の内部詳細を気にしなくてよい
  • 特定のコンテキスト型に縛られたくない場合は、必要な関数群をインターフェースとして抽象化できる

グローバル変数の置き換えと direct style

• 乱数生成やメモリアロケーションのように、見かけ上は無状態でも実際には状態が必要な API は、グローバル変数 の代わりにエフェクトで表現できる
• 乱数生成の例は Prng オブジェクトをプログラム全体で直接渡す必要がある負担を示している
  • グローバル Prng は便利だが、スレッドセーフ性が必要になるなどグローバル値の欠点が生じる
  • Random エフェクトの random: Unit -> U8 を使えば、利用者は上位の呼び出しスタックのどこかでハンドラーによる初期化だけを明示すればよい
  • その後 /dev/urandom や別の乱数源に切り替えるにはハンドラーだけ差し替えればよく、呼び出しスタックの残りのコードを変える必要はない
• メモリアロケーションも Allocate エフェクトで表現できる
  • allocate: (size: Usz) -> Alignment -> Ptr a
  • free: Ptr a -> Unit
  • ほとんどの呼び出しではグローバル allocator を使い、tight loop の中ではループ本体にハンドラーを追加して arena allocator に切り替えられる
• エフェクトは、専用の値で包んだ結果を渡す方式より direct style を可能にする
  • Maybe t を使う場合は and_then、map で成功パスをつないでいかなければならない
  • Rust の ? のような糖衣構文は、うまくいく経路に集中するための仕組みである
  • エフェクトベースの get_line_from_stdin (): String can Fail, IO と parse (s: String): U32 can Fail は、通常の逐次コードのように line = ...、x = ...、x * 2 と書ける
• 失敗処理は、ハンドラーを適用して成功パスから外れる形で扱える
  • get_line_from_stdin () with default "42" は Fail エフェクトをデフォルト値で処理する
• 異なるエラー型もエフェクト一覧として自然に合成される
  • LibraryA.foo (): U32 can Throw LibraryA.Error
  • LibraryB.bar (): U32 can Throw LibraryB.Error
  • my_function は Throw LibraryA.Error、Throw LibraryB.Error、Throw MyError をまとめて宣言できる
  • 繰り返しが長くなるなら AllErrors = can Throw ... のような型エイリアスを作れる
  • 同じ Throw String エフェクトは 1 つに統合され、分けたいなら MyError のようなラッパー型が必要になる

純粋性、再実行性、セキュリティ監査

• ほとんどの effect handlers 言語は、OCaml などの例外を除けば、副作用が起こりうる箇所にエフェクトを使う
  • Ante では can Print、can IO のように明示しなければ副作用を使えない
  • extern 定義はコンパイラが検査できないため、型定義を信頼する必要がある
  • デバッグモードでのみ IO エフェクトを実行し、リリースモードでのエフェクト安全性を保つ方式は計画中の機能である
• 一部の関数は入力として 純粋関数 を要求する
  • スレッド生成時には、生成されたスレッドが現在のスレッド所有ハンドラーを呼び出せてはならない
  • spawn_all (functions: Vec (Unit -> a pure)): Vec a can IO は純粋関数だけを受け取り、すべての関数をスレッドで実行して完了を待つ形である
• Software Transactional Memory(STM) は純粋関数を必要とする並行性手法である
  • 複数の関数を同時に実行している途中で、トランザクション中の値が別スレッドによって変更された場合、そのトランザクションを再開始する
  • Effekt の概念実証実装は effekt-stm にある
• 純粋性は、rr デバッグユーティリティに似た 記録/再生 の可能性を提供できる
  • record と replay の 2 つのハンドラーが main の出力する最上位エフェクト、通常は IO を処理する
  • record はエフェクト発生と結果を記録し、実際の処理のために組み込み IO ハンドラーへ再度引き上げる
  • replay は実際の IO を行わず、エフェクトログの結果を使う
  • デバッグビルドでデフォルト記録を有効にすれば決定論的デバッグが得られる
• 関数シグネチャ中のエフェクト一覧は、Capability Based Security に似た形でセキュリティ監査に役立つ
  • get_pi: Unit -> F64 なら、裏でこっそり IO をしていないと分かる
  • ライブラリ更新後に get_pi: Unit -> F64 can IO になった場合、呼び出し側の関数がすでに IO を要求していない限りコード上でエラーになる
  • 宣言するエフェクトは最小限にするのが望ましく、たとえば全体の IO より Print だけを宣言するほうがよい
  • 新しいエフェクト追加は semantic versioning を壊す変更として扱われる
  • 関連資料として Capability Based Security と Designing with Static Capabilities and Effects がある

限界と実装戦略

• エフェクトアプローチの限界の 1 つは、意図しない処理 が起こりうる点である
  • ある関数が新たに IO を必要とするようになっても、呼び出し側関数がすでに IO を許可していればエラーにならないことがある
  • Fail エフェクトも同様で、以前は失敗しなかったライブラリ関数が後から Fail しうるようになると、既存の Fail ハンドラーへ伝播する可能性がある
  • この動作は状況によっては問題ないが、デフォルト値の提供のように別個の処理を望んでいた場合には意図と異なることがある
• 従来の主要な欠点は 効率性への懸念 だったが、最近のエフェクトのコンパイル結果は大きく改善している
• 多くの代数的エフェクト言語は tail-resumptive エフェクトを通常のクロージャ呼び出しへ最適化する
  • tail-resumptive エフェクトとは、ハンドラーが最後に resume を呼ぶエフェクトである
  • 実際のエフェクトの大半がこれに当てはまり、本文の例の大部分もこのカテゴリに入る
  • 例外は resume をまったく呼ばないため、例外的なケースに分類される
• 言語ごとに最適化戦略も異なる
  • Koka は evidence passing を使い、エフェクトをハンドラーまで引き上げてランタイムなしで C にコンパイルする
  • Ante と OCaml は resume を最大 1 回しか呼べないよう制限している
    • この制限は非決定性のような一部のエフェクトを排除する
    • その代わり、リソース処理を単純化し、segmented stacks のような方式で内部 continuation をより効率的に実装できる
  • Effekt はハンドラーをプログラム内で完全に特化して除去する
    • この方式には、ほとんどの関数が second-class になるという制約がある
    • boxed 形式で first-class 関数を得て、pay-as-you-go 方式へ切り替えられる
    • 関連資料として Effekt captures ドキュメント と 論文 がある