🔗

Algebraic Effects と Extensible Effects：6つの言語で学ぶエフェクトシステムの違いと共通点

に公開
Haskell
PureScript
関数型言語
OCaml
Effect
tech

この記事では、様々な言語におけるエフェクトシステムを比較してみることで、それぞれの特徴や違いを知り、共通のエッセンスを知ることを目指します。
と偉そうなことを書きましたが、ただ単に私が興味のあるものを横並びで比較したいからやる、実際はそれがモチベーションです。

言語やライブラリは私が最近興味を持ったものをチョイスしています。
現存するあらゆる言語のエフェクトシステムを網羅的に比較するわけではありません。

比較対象は以下です。

  • Koka
  • Effekt
  • Unison
  • OCaml
  • Haskell
  • PureScript

興味が広がって対象を増やした結果かなり長くなってしまいました。
なので興味あるところだけ目次から飛んで見てもらうといいかもしれません。

エフェクトシステムとは

この記事で扱うエフェクトシステムは、 Algebraic Effects & Handlers と、 Extensible Effects の二つとします。

それぞれの概要をざっくりと説明しておきます。
そんなことよりコードが見たいんだよって人は目次からスッ飛ばしてください。

まず両者に共通的な概念を説明します。

エフェクト

両者ともに名前にEffectが含まれていることからわかるように両者ともエフェクトという概念を扱います。
エフェクトとは、すごーくざっくり説明すると、何らかの操作の集まり、です。
例えば、Stateというエフェクトは次のように値を取得するgetと値を設定するputという操作の集まりと考えられます。

{\mathrm{State}=\{\mathrm{get, put}\}}
「なんだそんなものか」と思うかもしれませんが、そんなものです。
ここで重要なのは、エフェクトに定義される操作は、「こういうことをするよ」というシグネチャに過ぎないというところです。
具体の関数ではありません。

また、複数のエフェクトを合成して使うことができます。

各言語やライブラリごとにエフェクトの表現方法は異なりますが、抽象的には同じものを指します。

ハンドラー

ハンドラーとはエフェクトを解釈するものです。
エフェクトに定義された操作はシグネチャに過ぎないので、どこかで実装を与えてやらねばなりません。
エフェクトに具体的な実装を与えることを解釈といい、それを実現する関数がハンドラーです。

Algebraic Effects & Handlersには名前にもハンドラーが出てきます。
Extensible Effectsの方は名前にハンドラーというキーワードが含まれていませんが、エフェクトの解釈自体は必要です。

ざっくりとはこんな感じです。

題材

同じことをそれぞれのエフェクトシステムでどう実現するのかを比較したいので、題材が必要ですね。

ということで題材として次を考えます。

  • askエフェクトと操作
    これにより何かを取り出せます。
  • emitエフェクトと操作
    これにより何かを発することができます。
  • ask,emitエフェクトそれぞれのハンドラー
    これにより具体的な処理が与えられます。
  • ask,emit両方を用いる関数
  • 上記の関数に対してハンドラーによる解釈を与えて実行する関数

askとemit両方を用いる関数を『疑似言語』で書くとこのような関数になります。

function askEmit() : effect<ask, emit> {
  value = ask()
  emit(value)
}

askで取り出した値を、emitに渡しています。
また関数のシグネチャで、この関数がaskとemitというエフェクトに依存していることを明示しています。
askで取り出す方法や、取り出せる値はaskのハンドラーに依存します。
emitによって何が起こるかもemitのハンドラーに依存します。

適当なハンドラーを用いてaskEmitを使う関数を疑似言語で書くとこのようになります。

function useAskEmit() {
  useEffect {
    askEmit()
  } with handler {
    askHandler
    emitHandler
  }
}

ここで例えば、askHandlerが"Hello"という固定値を返すハンドラーで、
emitHandlerが受け取った値を標準出力するハンドラーだった場合、
ask()の結果である"Hello"がemitで標準出力されることになります。
同じaskEmitを実行するにしても、ハンドラーを変えることで実装を切り替えることが可能になります。
本番ではネットワーク経由で値を取得するものを、テストのときはモックに切り替えるとか、ですね。

この題材を使って各言語でコードを書いてみます。
注意点として、糖衣構文で短く書ける場合でも比較しやすくするため敢えてそのまま書いていたり、補足説明のため省略しないで書いていたりします。
つまり各言語でのベストを目指したものではありません。
もっと良い描き方、表現方法があるはずなので、気になった方は深掘っていただけたらと思います。

ということで、先に進めましょう。

Algebraic Effects & Handlers

Algebraic Effects & Handlersは、直訳すると代数的エフェクトとハンドラーで、『例外処理の一般化』や『再開できる例外』などと説明されることもあります。
例外処理の一般化とは、エフェクトとハンドラを使って、例外処理も実現することができる、という意味です。非同期処理なども同じ枠組みで統一的に記述することができるため、（非同期や例外用の）専用の構文が無くなる分シンプルになります。（専用の構文がある方が良いか、統一的に扱える方が良いかは、何を重視するかによって変わりそうです）
またハンドラーの処理において直接的（あるいは選択的に）に継続を扱えるため、例外を処理する際に大域を脱出するだけでなく、続きの処理を再開することもできます。再開できる例外、というのはそういう意味です。

ちなみにこの代数的エフェクトの代数的とは何なのか、は説明しだすと長くなるのでこの記事では割愛し、別の記事に書きます。

では具体的な言語のコードを見ていきましょう。

Koka

Kokaは公式ページでは『エフェクト型とハンドラーを備え、厳密に型指定された関数型スタイル言語』と書かれております。

現在のv3は研究用の言語で、プロダクションコードでの採用は現実的ではありません。

エフェクト

エフェクトの定義には専用の構文があり、このようになります。

effect ask<a>
  ctl ask() : a

effect emit<a>
  ctl emit(v : a) : ()

これはaskエフェクトに操作としてask関数が定義されていることを表しています。
今回の例ではask関数のみ定義されていますが、複数の操作を定義できます。
<a>は任意の型aを表します。
ask関数は引数が無くa型の値を返すという定義になります。
一方emit関数はa型の値を引数にとり、Unit型(()のこと)の値を返すという定義になります。
ctlは、この関数が継続の制御を可能としていることを表しています。
常に継続を呼ぶ場合は、funと書きます。
ctlとした場合は、後述しますがresumeという関数で明示的に継続を呼ぶことになります。

ハンドラー

続いてハンドラーの定義です。

fun ask-handler(value : a, action : () -> <ask<a>|e> r) : e r
  with ctl ask() resume(value)
  action()

fun emit-handler(action : () -> <emit<string>,console|e> r) : <console|e> r
  with ctl emit(message)
    println("Emit " ++ message)
    resume(())
  action()

ask-handlerは普通の関数として定義されています。

この関数を理解するために、Kokaの関数定義について簡単に説明します。

  • 関数定義はざっくりと fun 関数名(引数) : 結果の型 というようになっている。
  • 結果の型はすべて何らかのエフェクトを持つ何らかの型となっている。
    （何もエフェクトを持たない結果を返す関数は全域関数と呼ばれ、エフェクトを書く部分を省略できる）
  • エフェクトは行(<>)に列挙される。複数のエフェクトa,b,cを使用する場合、<a,b,c>と書く。
  • エフェクトが一つしかない場合<>内に書かなくてよい。
  • eというエフェクトを別のエフェクトlで拡張するために、<l|e>という表記法を使用できる。

上記をもとに、<ask<a>|e> rやe rを以下で分解して説明します。

  • ask<a>は、型パラメーターaを持つaskエフェクト型
  • <ask<a>|e>は、エフェクトask<a>でエフェクト行eを拡張したエフェクト行
  • <ask<a>|e> rは、上記のエフェクト行<ask<a>|e>を持つ型r
  • e rは上記のeのみが残されたエフェクトを持つ型r

ここからask-handlerの引数のaction : () -> <ask<a>|e> rは、Unit型の値を引数にとり、上で説明したask<a>が含まれるエフェクト行を持つr型の値を返す関数であることがわかります。
関数の実装部分を見ると

with ctl ask() resume(value)
action()

となっておりますが、with〜で書かれている部分が、エフェクトの解釈を行なっている部分になります。
ここではask<a>エフェクトの操作askの解釈を行なっています。
継続の処理を表すresume関数にa型の値valueを渡しています。
ここでもしresumeを使わずに直接valueを返した場合、継続の処理は呼び出されず、エフェクトを使う処理を脱出してしまうため、resumeを使っています。
ちなみに処理の末尾で必ずresumeを使うことがわかっている場合は、操作やハンドラーによる定義の際ctlでなくfunと定義することができ、その場合はresumeを省略できます。
withの次の行にエフェクトを使用する処理（今回はaction()）を書いていますが、このactionが使用しているエフェクトの解釈をwith〜で行なっているわけです。
この解釈を行うことで結果の型からask<a>部分が消去されて、eが残ります。
だからask-handlerの結果の型はe rなのです。

この関数がわざわざ<xxx|e>の形でエフェクト行eを拡張しているのは、ask<a>以外のエフェクトを使用する可能性がある関数を渡せるようにするためです。
このように書かないと、厳密にask<a>エフェクトのみを使用する関数しか渡せなくなるのですが、今回はaskとemitを合わせて使うため、こういった指定が必要なわけです。

まとめるとask-handlerは、ask<a>を含む任意の複数のエフェクトを使用する関数を渡すことができて、それらのうち、ask<a>だけを解釈して消し去った新しいエフェクトを返す関数ということです。

emit-handlerは、ask-handlerが読めれば大体読めるはずです。
標準出力を使うためconsoleエフェクトが使われています。

エフェクトを使用する関数

では、次にaskとemit両方のエフェクトを使う関数です。

fun ask-emit() : <ask<a>, emit<a>, console> ()
  println("Start")
  val v = ask()
  emit(v)
  println("End")

標準出力のためのconsoleエフェクトを含めた三つのエフェクトを使っているため<ask<a>, emit<a>, console>というエフェクト行になっています。
題材で示した通り、askから取得した値をemitに渡しているだけです。

エフェクトの解釈

最後にこのask-emitに対してハンドラーによる解釈を与えて使用する関数です。

pub fun example-ask-emit()
  with ask-handler("Ask Value")
  with emit-handler()
  ask-emit()

ask-emit()の上の行にwithでさきほど定義したハンドラーを書いています。
こうすることでask-emitが返す<ask<a>, emit<a>, console> ()のask<a>はask-handlerによる解釈で消去され、emit<a>はemit-handlerによる解釈で消去され、consoleだけが残り、console ()が返されます。

この関数を実行すると、次のように標準出力されます。

Start
Emit Ask Value
End

処理フロー

エフェクトにハンドラーによる解釈を与えて実行したときの処理フローをざっくり説明します。

まず、説明のため、以下の糖衣構文脱糖します。

with ask-handler("Ask Value")
with emit-handler()
ask-emit()

これを脱糖すると次になります。

ask-handler("Ask Value", fn ()
  emit-handler(fn ()
    ask-emit()
  )
)

更にハンドラーの中のwithもすべて脱糖して展開するとこうなります（長い）。

(handler {
  ctl ask() 
    resume("Ask Value")
}) fn () {
  (handler {
    ctl emit(message)
      println("Emit " ++ message)
      resume(())
  }) fn () {
    println("Start")
    val v = ask()
    emit(v)
    println("End")
  }
}

つまり、実はハンドラーは組み込みの関数handlerを使っており、更に複数のハンドラーを使った場合、このように入れ子状になるわけです。

この処理の流れを強引に可視化してみました。

文章で書くとこのような感じです。

  1. askを呼び出すと、askのハンドラーに制御が移る
  2. askの呼び出し以降の処理を継続としてresumeで再開できるので、これに"Ask Value"を渡して処理を再開
  3. 渡ってきた"Ask Value"を使ってemitを呼び出すと、emitのハンドラーに制御が移る
  4. emitの呼び出し以降の処理を継続としてresumeで再開できるので、値を標準出力した後、継続を再開する

最初の方に書いた通り説明のため操作をctlで定義していますが、代わりにfunを使うとresumeを省略でき(その場合必ず末尾再開となる)るのですが、ドキュメントによるfunの方がはるかに効率的なようです。

継続の扱い

Kokaのエフェクトにおいて、継続はマルチショット継続という継続になります。
マルチショット継続は何度でも呼び出し、再開できる継続のことです。
対して、1ショット継続という継続もあり、こちらは一度のみ再開できます。

例えば先程のask-handlerにおいてresumeを二回呼んでみます。

fun ask-handler(value : a, action : () -> <ask<a>|e> r) : e r
  with ctl ask()
    resume(value)
    resume(value)
  action()

すると出力はこのようになります。

Start
Emit Ask Value
End
Emit Ask Value
End

これはこの時点の継続が以下のようになっているからですね。

emit(v)
println("End")

次はemit-handlerでresumeを二回呼んでみます。

fun emit-handler(action : () -> <emit<string>,console|e> r) : <console|e> r
  with ctl emit(message)
    println("Emit " ++ message)
    resume(())
    resume(())
  action()

すると出力はこのようになります。

Start
Emit Ask Value
End
End

これはこの時点での継続がこうなっているからです。

println("End")

おまけ(再開可能な例外の例)

再開可能な例外の例

『再開できる例外』の話が気になった方向けに、再開可能な例外の例を作ってみましょう。

エフェクトはこのようにします。
再開するかどうかをneed-resumeで直接的に制御できるようにします。

effect resumable-exn
  ctl throw-resumable(message : string, need-resume : bool) : ()

ハンドラーはこうします。
基本的にメッセージは表示し、needが真のときのみ継続を再開します。

fun try-resumable(action : () -> <resumable-exn,console|e> ()) : <console|e> ()
  with ctl throw-resumable(message, need-resume)
    println(message)
    if need-resume then resume(())
  action()

使用例は次のように自然数の減算とします。
結果が自然数じゃなくなる場合、1以上のデフォルト値が指定されていたら再開し、そうでなければ再開しないようにします。

fun subtract-natural-number(x : int, y : int, default : int = 0) : resumable-exn int
  val result = x - y
  if result <= 0 then
    throw-resumable(x.show ++ " - " ++ y.show ++ " は自然数じゃないよ", default >= 1)
    default
  else
    result

実行例はこうします。
最初のパターン以外は結果が負の値になりますが、最後のパターンは1以上のデフォルト値が指定されています。

pub fun example-subtract-natural-number()
  println("------------")
  println("2 - 1")
  try-resumable
    println("結果: " ++ subtract-natural-number(2, 1).show)
  println("------------")
  
  println("------------")
  println("2 - 3")
  try-resumable
    println("結果: " ++ subtract-natural-number(2, 3).show)
  println("------------")

  println("------------")
  println("2 - 3")
  try-resumable
    println("結果: " ++ subtract-natural-number(2, 3, 1).show)
  println("------------")

結果はこうなります。
二番目のパターンでは結果: という出力がされていません。
再開しなかったため、継続の処理であるprintlnが呼ばれなかったからです。

------------
2 - 1
結果: 1
------------
------------
2 - 3
2 - 3 は自然数じゃないよ
------------
------------
2 - 3
2 - 3 は自然数じゃないよ
結果: 1
------------

この例は実用的とは言い難いですが、このように再開を制御することができます。

Effekt

次はEffektです。
公式では

A language with lexical effect handlers and lightweight effect polymorphism

と謳っています。
字句的なエフェクトハンドラーと、軽量で多相なエフェクトを持つ言語、という意味でしょうか。

また『Effekt is a research-level language』とも書かれており、Kokaと同じく、Production利用は難しそうです。
ただ、こちらはFFIの仕組みを用意しており、Kokaよりは実用に近いかもしれません。

エフェクト

エフェクトの定義ですが、Effektではエフェクトをinterfaceで定義します。

interface Ask[A] {
  def ask(): A
}

interface Emit[A] {
  def emit(value: A): Unit
}

操作は関数としてdefで定義します。
複数の操作を定義することもできます。
Ask[A]やEmit[A]の[A]は型パラメーターで、このインタフェースが汎用的であることを示しています。
このAは、ask関数の戻り値の型やemit関数の引数の型として使われています。
Kokaでは()と書いていたUnit型が、EffektではそのままUnitと書かれていますね。
書きっぷりは異なるものの、Kokaとそう大きくは変わらないことがわかるかと思います。

ハンドラー

では次にハンドラーです。

def askHandler[R, A](a : A) { action: () => R / Ask[A] }: R / {} = {  
  try {  
    action()  
  } with Ask[A] {  
    def ask() = resume(a)  
  }
}

def emitHandler[R] { action: () => R / Emit[String] }: R / {} = {
  try {
    action()
  } with Emit[String] {
    def emit(value: String) = resume(println("Emit " ++ value))
  }
}

Effektではtry withのtryのブロックでエフェクトを使用し、withのブロックでそのエフェクトを解釈します。
関数の定義はざっくりと
def 関数名[使用する型パラメーター](引数) { ブロックを渡す場合ブロックの定義 } : 戻り値の型 / {戻り値のエフェクトを列挙したもの}
という形になっています。
文法は異なるものの概ねKokaで見たような感じです。

Kokaとは異なり、resumeを省略して継続を呼び出すことができません。

また、Kokaのように拡張されたエフェクトのような表現をする必要がありません。

エフェクトを使用する関数

AskエフェクトとEmitエフェクトの両方を使う関数はこちらです。

def askEmit[A](): Unit / { Ask[A], Emit[A] } = {
  println("Start")
  val v = do ask[A]()
  do emit(v)
  println("End")
}

エフェクトの解釈

最後に上記の関数とハンドラーを使う関数です。

def exampleAskEmit() = {
  with askHandler("Ask Value")
  with emitHandler
  askEmit[String]()
}

def main() : Unit / {} = {
  exampleAskEmit()
}

実行するとこのように標準出力されます。

Start
Emit Ask Value
End

処理フロー

処理フローとしては、Kokaと同じく、askなどの操作が呼び出されたときにハンドラーが呼ばれる流れになります。
継続を呼び出して処理を再開するという流れも同じです。

継続の扱い

エフェクトにおける継続ですが、EffektもKokaと同じくマルチショット継続です。
例として継続を複数回呼んでみます。

def askHandler[R, A](a : A) { action: () => R / Ask[A] }: R / {} = {  
  try {  
    action()  
  } with Ask[A] {  
    def ask() = {
      resume(a)
      resume(a)
    }
  }
}

def emitHandler[R] { action: () => R / Emit[String] }: R / {} = {
  try {
    action()
  } with Emit[String] {
    def emit(value: String) = {
      println("Emit " ++ value)
      resume(())
      resume(())
    }
  }
}

この場合出力はこうなります。

Start
Emit Ask Value
End
End
Emit Ask Value
End
End

Unison

次はUnisonです。
Githubを見てみると

Unison is a statically-typed functional language with type inference, an effect system, and advanced tooling. It is based around a big idea of content-addressed code, in which function are identified by a hash of their implementation rather than by name, and code is stored as its AST in a database

と書かれています。
Unisonは、型推論やエフェクトシステム、および高度なツールを備えた静的型付け関数型言語だといっています。
また、関数が名前ではなく実装のハッシュによって識別され、コードがデータベースにASTとして格納されるという、コンテンツアドレスコードの大きなアイデアに基づいているとのことですが、ここは他の言語との大きな違いですね。

UnisonにはUCM(UnisonCodebaseManager)というコードベースを管理する機構があり、UCMはsqlite(今のところ)を用いてローカル環境でコードベースの管理を行います。
このデータベースが、上記でいうデータベースになります。

管理の単位は、最上位にprojectがあり、projectに紐づく形でbranchがあります。
このproject/branchに対してコードを追加したり更新したり削除といった管理を行います。

UCMはucmコマンドで起動するREPLで、コードの変更の検知をしてくれ、自動でREPLにロードまで行われ関数が実行できます。
ただし、コードベースへの追加を行っていないと、ucmを終了したタイミングでロードされたものは失われます。

コードベースの共同所有は、Unisonが提供しているUnison Shareというプラットフォームで行うようです。
Githubを使って従来通りのファイルベースでの管理も行えるようです。
（言語の設計的にはUnison Shareを使うのがよいのでしょうが、コードをモノレポで管理している場合などは、あまり分散させたくないでしょうから悩ましいですね）

また、このUnison Shareを眺めてみるとhttpのライブラリがあったりして、KokaやEffektと比べてより実用に近い印象を受けます。

とまぁ、説明はこの辺にして、本筋に戻りましょう。

エフェクト

まずエフェクトの定義です。
Unisonではエフェクトをabilitiesと呼ぶので、abilityの定義を見ます。

unique ability Ask a where
  ask : a

unique ability Emit a where
  emit : a -> ()

ability宣言の中にaskやemitといった操作が定義されています。
操作は複数定義することができます。
Ask aやEmit aのaは型パラメーターです。

ハンドラー

次にハンドラーの定義です。

ask.handler : a -> Request {e, Ask a} r -> {e} r
ask.handler v = cases
  { a }            -> a
  { Ask.ask -> k } -> handle k v with ask.handler v

emit.handler : Request {e, Emit Text} r -> {e, IO, Exception} r
emit.handler = cases
  { a }                  -> a
  { Emit.emit msg -> k } -> handle
    printLine("Emit " ++ msg)
    k ()
  with emit.handler

こちらはKokaやEffektとは様相が大分異なりますね。

関数のシグネチャは
関数名: 引数1の型 -> 引数2の型 -> 返り値の型
となっています。

つまりask.handlerの引数はa型と、Request {e, Ask a} r型で、戻り値の型は{e} rです。

Requestの{}にはこのRequestが使用する可能性のあるabilityを列挙します。
eは任意のabilityです。Ask a以外のablitityが含まれていることを示しています。
このように任意のエフェクトeが含まれていたり、それを含む{e, Ask a}からAsk aが解釈後に取り除かれて{e}が返されるというのは、Kokaに近いですね。

本体を見てみましょう。

ask.handler v = cases
  { a }            -> a
  { Ask.ask -> k } -> handle k v with ask.handler v

casesは
このようなmatch文

isEmpty x = match x with  
  [] -> true  
  _ -> false

をこのように書けるようにするものです。

isEmpty2 = cases  
  [] -> true  
  _ -> false

つまりRequest {e, Ask a} rのパターンマッチになっています。

次にこの部分です。

{ a }            -> a
{ Ask.ask -> k } -> handle k v with ask.handler v

まず先にhandle ~~ with ~~の部分を説明します。
handleの後にabilitiesを使う処理を書きます。
そしてwithの後に使用したabilitiesの解釈の処理を書きます。

次にkですが、これは継続の処理です。
KokaやEffektでは、継続の処理を実行するのにresume関数を用いていました。
一方UnisonにおけるRequestのパターンマッチでは、kが継続となって渡されてくるのです。

処理の流れはこのようになります。
1.{ Ask.ask -> k }のパターンマッチに対する処理で、継続kにvが渡されます。
2.k vの結果はabilitiesを使用する処理になり、その結果をwithのあとのハンドラーで再帰的に処理します。
3.{ a }のパターンマッチでは最終的に作られた純粋な値にマッチします。

KokaやEffektとは大分ハンドラーの実装の雰囲気が異なるものの継続という概念は共通して登場しますね。

エフェクトを使用する関数

では、エフェクト(abilities)を使う処理です。
これはKokaやEffektとあまり変わらずわかりやすい。

composed.emitAsk : '{Emit a, Ask a, IO, Exception} ()
composed.emitAsk = do
  printLine("Start")
  askValue = Ask.ask
  Emit.emit askValue
  printLine("End")

エフェクトの解釈

で、上記を使う関数がこちらです。

composed.runEmitAsk : '{IO, Exception} ()
composed.runEmitAsk = do
  handle
    handle composed.emitAsk()
    with ask.handler "Ask Value"
  with emit.handler

複数のハンドラを使う場合、このようにネストしなければならないようです。

実行すると結果はこのようになります。

Start
Emit Ask Value
End

  ()

処理フロー

UnisonもKokaやEffektと同じような処理の流れになります。
Unisonの場合は操作を呼び出したとき、unison-requestという構造体(Request {e, Ask a} rみたいなやつ)が作られ、ハンドラーに渡ってくるという違いがありますが、流れは大きくは変わらないでしょう。
エフェクトを解釈して実行するコードは脱糖した場合のKokaのコードのようですね。

継続の扱い

エフェクト（abilities）における継続は、マルチショット継続です。
例えばask.handlerをこのように書き換えて二回継続を再開させてみます。

ask.handler : a -> Request {e, Ask a} r -> {e, IO, Exception} r
ask.handler v = cases
  { a }            -> a
  { Ask.ask -> k } ->
    _ = handle k v with ask.handler v
    handle k v with ask.handler v

すると実行結果はこのようになります。

Start
Emit Ask Value
End
Emit Ask Value
End

  ()

OCaml

OCamlはこれまで挙げてきた言語の中では一番メジャーな言語だと思います。
OCamlではエフェクトとハンドラーはEffect handlersと呼ばれており、OCaml 5から導入されたようです。

エフェクト

OCamlのエフェクトですが、操作の集まりを定義するという部分では他の言語と共通していますが、その集まりに名前をつけるような定義の仕方をしません。
エフェクトを表す構造を作り、そこに操作を表す関数を持たせることはできるので、表現としては操作の集合に名前をつける（ような表現をする）ことはできます。

それには一工夫必要なので、この節ではより基本的な定義の仕方を説明します。
とはいえ気になる方もいるでしょうから、最後の方で発展した例をお見せします。

ということで基本的な定義を見てみましょう。
まずこのような型を定義します。

(* open Effect しておけば Effect. の部分は省略して単に t と書ける *)
type _ Effect.t += Ask : string Effect.t

type _ Effect.t += Emit : string -> unit Effect.t

OCamlでのエフェクトの定義はExtensible variant types(拡張可能なバリアント型)と呼ばれる型を利用しています。
OCamlのバリアント型は代数的データ型の一種なのですが、拡張可能なバリアント型は一度定義したバリアント型を後から拡張することができます。
Effect.tがその拡張可能なバリアント型で、+= Ask～でAsk : string Effect.tを追加しています。
これはAskがstring Effect.t型の値を返すという意味です。
string Effect.tは文字列をともなうエフェクトの型です。

type _ Effect.tの_はAskコンストラクタが独自の型パラメータを持てるようにするためのものです。'aだろうが'bだろうが何でもいいので_としています。
この部分に操作を`+=で連結することで操作の集まりを表現できます。

ちなみに拡張可能バリアント型はEffect handlers導入以前から存在していたもので、既存の仕組みを利用したわけですね。

次にエフェクトを実行する関数を定義します。

let ask () : string = perform Ask

let emit (value: string) : unit = perform (Emit value)

このperformは拡張可能バリアントで定義したエフェクトを使う関数で、このようにヘルパー関数を用意するのが一般的のようです。

ハンドラー

次はハンドラーです。
長いのでまずaskのハンドラーだけ書きます。

let run_ask (f: unit -> 'a) ~(env: string) : 'a =  
  match_with f ()  
  { retc = Fun.id;
    exnc = raise;
    effc = (fun (type b) (eff: b Effect.t) ->
      match eff with
      | Ask -> Some (fun (k: (b, _) continuation) ->
          continue k env)
      | _ -> None)
  }

fが先ほど定義したエフェクトを実行している関数になります。
他の言語と異なり、ここにエフェクトの型は現れません。
~(env: string)の~は、引数をラベル付き引数にするものです。
match_withに渡しているレコードは、ハンドラーレコードというもので、ここがハンドラーの本体といってもいいでしょう。
それぞれのフィールドの意味はこうなります。

  • retc: 値が正常に返された場合の処理
  • exnc: 例外が発生した場合の処理
  • effc: エフェクトが実行された場合の処理

retcには値をそのまま返してほしいので恒等関数Fun.idを指定して、exncには(例外を握りつぶさないで)例外を発生させてほしいのでraiseを指定しています。
effcがエフェクトのパターンマッチを行う処理です。
ここだけ抜粋します。

effc = (fun (type b) (eff: b Effect.t) ->
  match eff with
  | Ask -> Some (fun (k: (b, _) continuation) ->
      continue k env)
  | _ -> None)

effcフィールドは、option型の値を返すことになっているため、SomeやNoneを返しています。
Someの中身だけ見てみましょう。

fun (k: (b, _) continuation) -> continue k env

k: (b, _) continuationはb型を入力とし、任意の型を出力とする継続を表す型です。
continue k envは、envをkに渡すことで継続kを再開させます。

ここまでわかったところで次はemitのハンドラーです。

let run_emit (f: unit -> 'a) : 'a =
  match_with f ()
  { retc = Fun.id;
    exnc = raise;
    effc = (fun (type b) (eff: b Effect.t) ->
      match eff with
      | Emit value -> Some (fun (k: (b, _) continuation) ->
          Printf.printf "Emit %s\n" value;
          continue k ())
      | _ -> None)
  }

パターンマッチの箇所を見ると、valueの値を標準出力させてから、継続を再開していることがわかると思います。

エフェクトを使用する関数

では続いてこれらのエフェクトを使う関数です。

let ask_emit () =
  printf("Start\n");
  let value = ask () in
  emit value;
  printf("End\n")

これは拍子抜けするほど簡単ですね。
型としてはunit -> unitとなっており、上述した通りエフェクトの型は出てこないです。
（そういうものみたいです）

エフェクトの解釈

最後に、上記の関数とハンドラーを使う関数を見ます。

let example_ask_emit_simple () =
  run_ask (fun () -> run_emit ask_emit) ~env:"Ask Value"

run_emitした後の結果を返すような関数をrun_askに渡しており、run系の関数がネストするような形になっています。

実行結果はこうなります。

Start
Emit Ask Value
End
- : unit = ()

上述した通りask_emitはどのエフェクトに依存しているかという情報を持たないため、次のようにemitエフェクトのみ解釈してaskエフェクトの解釈が残っている状況でも実行できてしまいます。

let example_ask_emit_simple () =
  run_emit ask_emit

この場合は例外が投げられます。

Fatal error: exception Stdlib.Effect.Unhandled(Effects.Ask_simple.Ask)

処理フロー

代わり映えしない説明になりますが、これまでの言語とほぼ同じ流れを辿ります。
performを実行するとハンドラーに制御が移り、継続を再開することで処理が進んでいきます。
異なる点としては、型でチェックがされていないので、対応するハンドラーがない状態でもエフェクトの解釈が行えてしまう点です。
エフェクトに対応するハンドラーが見つからない場合は例外が投げられます。

継続の扱い

OCamlのエフェクトにおける継続は1ショット継続となります。
継続を複数回再開するコードはコンパイルエラーにはなりませんが、実行時例外が投げられます。

例えば次のようにコードを書き換えてみます。

let run_ask (f: unit -> 'a) ~(env: string) : 'a =  
  match_with f ()  
  { retc = Fun.id;
    exnc = raise;
    effc = (fun (type b) (eff: b Effect.t) ->
      match eff with
      | Ask -> Some (fun (k: (b, _) continuation) ->
          continue k env;
          continue k env)
      | _ -> None)
  }

let example_ask_emit_simple () =
  printf("--------\n");
  run_ask (fun () -> run_emit ask_emit) ~env:"Ask Value";
  printf("--------\n")

これを実行すると、次のように、Continuation_already_resumedという例外が投げられてプログラムが終了します（二回目の--------が表示されずに終了している）。

--------
Start
Emit Ask Value
End
Fatal error: exception Stdlib.Effect.Continuation_already_resumed

おまけ(特定の型に依存しないエフェクトとハンドラーなど)

特定の型に依存しないエフェクトとハンドラー

参考までに特定の型に依存しないエフェクトとハンドラーも書いておきます。

まずはaskのエフェクトとハンドラーです。

ask
module type ASK = sig
  type t

  val ask : unit -> t

  val run : (unit -> 'a) -> env:t -> 'a
end

module Ask (S : sig type t end) : ASK with type t = S.t = struct
  type t = S.t

  type _ Effect.t += Ask : t Effect.t

  let ask () : t = perform Ask

  let run (f: unit -> 'a) ~(env: t) : 'a =  
    match_with f ()  
    { retc = Fun.id;  
      exnc = raise; 
      effc = (fun (type b) (eff: b Effect.t) ->  
        match eff with  
        | Ask -> Some (fun (k: (b,_) continuation) ->  
            continue k env)  
        | _ -> None)  
    }
end

ASKはモジュールの型です。インタフェースみたいなものだと考えてください。

その下のAskはファンクターと呼ばれるもので、これにより次のように特定の型に依存したモジュールを生成することができるようになります。

module StringAsk = Ask (struct type t = string end)

このようにすると、type _ Effect.t += Ask : t Effect.tのtがstringになるわけですね。
このモジュール周りの部分以外は、本文でお見せしたものと変わらないことがわかるでしょう。

emitの方もいきましょう。

emit
module type EMIT = sig
  type t
  val emit : t -> unit
  val run : (unit -> 'a) -> (t -> unit) -> 'a
end

module Emit (S : sig type t end) : EMIT with type t = S.t = struct
  type t = S.t

  type _ Effect.t += Emit : t -> unit Effect.t

  let emit (value: t) : unit = perform (Emit value)

  let run (f: unit -> 'a) (handler: t -> unit) : 'a =
    match_with f ()
    { retc = Fun.id;
      exnc = raise;
      effc = (fun (type b) (eff: b Effect.t) ->
        match eff with
        | Emit value -> Some (fun (k: (b, _) continuation) ->
            handler value;
            continue k ())
        | _ -> None)
    }

end

続いてエフェクトを使うコードです。

module StringAsk = Ask (struct type t = string end)
module StringEmit = Emit (struct type t = string end)

let ask_emit () =
  printf("Start\n");
  let value = StringAsk.ask() in
  StringEmit.emit value;
  printf("End\n")

let example_ask_emit () =
  StringAsk.run (fun () ->
    StringEmit.run ask_emit (fun value -> Printf.printf "Emit %s\n" value)
  ) ~env:"Ask Value"
DeepなハンドラーとShallowなハンドラー

余談ですが、ハンドラーはDeepとShallowに分けられます。
複数回エフェクトが実行されたとき、その分だけ解釈を行う必要があるのですが、Deepが自動で同じハンドラーを使ってくれるのに対し、Shallowは自分で制御する必要があります。
これまでの例はすべてDeepなハンドラーでした。
askのハンドラーをShallowにしてみるとこのようになります。

Shallow版
let run (f: unit -> 'a) ~(env: t) : 'a =
  let rec loop : type a r. t -> (a, r) continuation -> a -> r =
    fun e k x ->
      continue_with k x
      {
        retc = Fun.id;
        exnc = raise;
        effc = (fun (type b) (eff: b Effect.t) ->
          match eff with
          | Ask -> Some (fun (k: (b, r) continuation) ->
              loop e k e
            )
          | _ -> None
        )
      }
  in
  loop env (fiber f) ()

おまけ2(操作をまとめたものとしてStateエフェクトを表現する例)

Stateエフェクト

↑のおまけで紹介したmoduleを利用して、操作getとputを持つStateエフェクトを定義してみます。

(* こういうデフォルトのハンドラー ( ('a,'b) handler ) を作っておくと毎度同じものを書かないで済む *)
let default_handler =
  { retc = Fun.id;
    exnc = raise;
    effc = fun (type c) (_ : c Effect.t) -> None }

module type STATE = sig
  type t
  val get : unit -> t
  val put : t -> unit
  val run : (unit -> 'a) -> init:t -> 'a
end

module State (S : sig type t end) : STATE with type t = S.t = struct
  type t = S.t

  type _ Effect.t += Get : t Effect.t | Put : t -> unit Effect.t

  let get () = perform Get

  let put value = perform (Put value)

  let run f ~init =
    let rec loop : type a r. t -> (a, r) continuation -> a -> r =
      fun state k x ->
        continue_with k x
        { default_handler with
          effc = (fun (type b) (eff: b Effect.t) -> 
            match eff with
            | Get -> Some (fun (k: (b, r) continuation) ->
                loop state k state)
            | Put value -> Some (fun (k: (b, r) continuation) ->
                loop value k ())
            | _ -> None
          )
        }
      in
      loop init (fiber f) ()
end

このようにすれば、操作の集まりを名前付きで扱えます。

Stateを使う関数を用意します。

let example () =
  let value = StringState.get() in
  Printf.printf "Got value: %s\n" value;
  
  StringState.put ("<<<" ^ value ^ ">>>");

  let new_value = StringState.get() in
  Printf.printf "Got new value: %s\n" new_value

単位値をgetして標準出力した後、加工した値をputし、もう一度getして標準出力しているだけです。

これを次の関数で実行してみます。

let exec_example () =
  StringState.run example ~init:"Hello, world!"

するとこのようになります。

Got value: Hello, world!
Got new value: <<<Hello, world!>>>

Extensible Effects

Extensible EffectsとしてはHaskellとPureScriptの二つの言語の例を見ます。
Algebraic Effects & Handlers が言語自体に組み込まれていたのに対し、Extensible EffectsによるエフェクトとハンドラーはHaskellやPureScriptには組み込まれておらず、ライブラリによって提供されます。

Haskell

Haskellの場合はライブラリの選択肢が多いのですが、この記事ではPolysemyを使います。

エフェクト

エフェクトの定義はこのようになります。

data Ask v m a where
  Ask :: Ask v m v

data Emit v m a where
  Emit :: v -> Emit v m ()

ask :: Member (Ask v) r => Sem r v
ask = send Ask

emit :: Member (Emit v) r => v -> Sem r ()
emit = send . Emit

Polysemyでのエフェクトは次のように定義します。

  • AskやEmitといったGADTs（一般化された代数的データ型）で操作の集合を定義（この例はGADTsの名前と同じ名前の操作を定義していますが、当然別の名前の操作を定義できます）
  • askやemitなどのエフェクト型の値を生成する関数を定義

askやemitが返しているSem r vやSem r ()などがエフェクト型で、MemberによってAskやEmitなどのエフェクトを含んでいるという制約が与えられています。

ハンドラー

次はエフェクトを解釈するハンドラーです。

runAsk :: v -> Sem (Ask v ': r) a -> Sem r a
runAsk value = interpret $ \case
  Ask -> pure value

runEmit :: (Member (Embed IO) r) => Sem (Emit String ': r) a -> Sem r a
runEmit = interpret $ \case
  Emit a -> embed $ putStrLn a

Sem (Ask v ': r) a -> Sem r aの部分を見てください。
Sem (Ask v ': r) aとSem r aを比べてみると、Ask vが消えています。
このようなエフェクトが解釈されて消去されるというのはAlgebraic Effects & Handlersで見た言語と同じですね。
次のエフェクトを解釈して実際の処理を行う部分は、パターンマッチで実装されており、Unison言語と近いものを感じます。

interpret $ \case
  Ask -> pure value

一方でこのinterpretとcaseによるハンドラーの実装では継続が出てきません。
が、実際はinterpretの中で継続は使われています。

interpretの実装

interpretで使われるinterpretHに継続kが登場する

interpretH
    :: (∀ rInitial x . e (Sem rInitial) x -> Tactical e (Sem rInitial) r x)
       -- ^ A natural transformation from the handled effect to other effects
       -- already in 'Sem'.
    -> Sem (e ': r) a
    -> Sem r a
interpretH f (Sem m) = Sem $ \k -> m $ \u ->
  case decomp u of
    Left  x -> k $ hoist (interpretH f) x
    Right (Weaving e s d y v) -> do
      fmap y $ usingSem k $ runTactics s d v (interpretH f . d) $ f e

Ask -> pure valueでは、pure valueのpureによってvalueを持つ新しいエフェクトを生成して返しています（エフェクトだがAskは消去されている）。

エフェクトを使用する関数

AskとEmitの両方のエフェクトを使う関数はこちらです。
Membersにエフェクトを列挙する形になっています。

askEmit :: Members '[Ask String, Emit String, Embed IO] r => Sem r ()
askEmit = do
  embed $ print "Start"
  v <- ask
  emit v
  embed $ print "End"

エフェクトの解釈

askEmitを使う関数はこうです。

exampleAskEmit :: IO ()
exampleAskEmit = do
    runM
  . runAsk "Ask Value"
  . runEmit
  $ askEmit

実行結果はこうなります。

Start
Ask Value
End

処理フロー

Extensible Effectsの場合、Algebraic Effects & Handlersで見てきたものとは異なる処理の流れになります。

まず、エフェクトを使う関数askEmitが返してくるのはMembers '[Ask String, Emit String, Embed IO] r => Sem r ()という型になっています。
これはエフェクトによる制約がついたSem r ()型です。
実際にコードを見てみましょう。

askEmit :: Members '[Ask String, Emit String, Embed IO] r => Sem r ()
askEmit = do
  embed $ print "Start"
  v <- ask
  emit v
  embed $ print "End"

実装でaskが返しているのもMember (Ask v) r => Sem r vという型です。
emitも同じようにSem型を返します。
つまり、操作を呼んでもこの時点でハンドラーに制御は移らないというわけです。
なので、askEmitを呼んだ時点では何も実行は行われません。
askEmitからは「こういう流れで操作が呼び出されるよ」という流れが『データ構造』として表現されたものが返され、そのデータ構造をもとに後からハンドラーで解釈していくのです。
(do以降は糖衣構文になっていますが、実際は継続ベースのモナドであるSemのbindの処理が呼ばれていて、そこで構造化されていっている。だからこのdoの中はすべてSemの文脈である。)

更に各ハンドラーの型を見ると、これもまたSem型の値を返してくることがわかります。

runAsk :: v -> Sem (Ask v ': r) a -> Sem r a
runAsk value = interpret $ \case
  Ask -> pure value

これは雑に説明すると、引数で渡したエフェクトを解釈して対応する処理が埋めこまれた新しい（解釈前のエフェクトを消した）エフェクト型を返すものになっています。
つまりこれもまた処理を実行するのではなく、データです。

ここまでを踏まえてあらためてaskEmitを使う関数をもとに流れを説明します。

exampleAskEmit :: IO ()
exampleAskEmit = do
    runM
  . runAsk "Ask Value"
  . runEmit
  $ askEmit

これは関数合成として書かれており、ベタに書くとこうなります。
runM (runAsk "Ask Value" (runEmit askEmit))

runMはrunM :: Monad m => Sem '[Embed m] a -> m aという定義になっており、Embedエフェクトのみを含むSemを実際のモナドとして実行する関数です。
なのでrunMを呼ぶ前までにEmbedエフェクトを除くすべてのエフェクトの解釈を済ませておく必要があり、このような順序になっています。

具体の流れはこのようになります。

  1. runEmit askEmitによる解釈でEmitエフェクトを処理するハンドラーを持つ新しいSemを構築
  2. runAskによる解釈では、1のSemを元に、更にAskエフェクトを処理するハンドラーを持つ新しいSemを構築
  3. runMによる解釈で、ようやく実際の実行が開始される。ここでこれまでSemに溜め込まれていた処理が一気に実行される(Embedエフェクトの処理も含む)。

以上なのですが、Algebraic Effects & Handlersとは処理フローが異なることがおわかりいただけたでしょうか。

この違いは、言語自体が備えているエフェクトの機構を利用できるAlgebraic Effects & Handlersと、言語自体にはエフェクトの機構がなく既存のものを利用した実装パターンであるExtensible Effectsの違いからきています。

継続の扱い

ハンドラーの箇所で説明した通り、継続はライブラリ側のコードで扱われており、自動で一度だけ再開されます。
つまり1ショット継続です。
継続は暗黙的に処理されるので、再開しないことを選択することはできません。

PureScript

PureScriptではrunというライブラリを使います。

エフェクト

エフェクトの定義はこうなっています。

data AskF v a = Ask (v -> a)

derive instance functorAskF :: Functor (AskF v)

type ASK v r = (ask :: AskF v | r)

_ask :: Proxy "ask"  
_ask = Proxy  

ask :: forall v r. Run (ASK v + r) v
ask = lift _ask (Ask identity)

data EmitF v a = Emit v a

derive instance functorEmitF :: Functor (EmitF v)

type EMIT v r = (emit :: EmitF v | r)

_emit :: Proxy "emit"
_emit = Proxy

emit :: forall v r. v -> Run (EMIT v + r) Unit
emit a = lift _emit (Emit a unit)

一番定義が複雑です。
言語だったりライブラリだったりの制約で準備が多いのですが、一旦ここだけ見ればいいと思います。

data AskF v a = Ask (v -> a)

ask :: forall v r. Run (ASK v + r) v
ask = lift _ask (Ask identity)

data EmitF v a = Emit v a

emit :: forall v r. v -> Run (EMIT v + r) Unit
emit a = lift _emit (Emit a unit)

HaskellのPolysemyの定義に大分近いです。
Polysemyの場合はGADTsでしたが、こちらは普通の代数的データ型を定義します。
当然操作として複数の値コンストラクタを定義できます。

これらの型を使ってaskやemitなどの「エフェクト型を作る」関数を定義するのもPolysemyとそう変わらないですね。
Run (ASK v + r) vやRun(EMIT v + r) Unitなどがエフェクトの型です。
+ rというのは別のエフェクトと合わせて使えるように拡張可能にしている部分です。
この拡張のあたりは、多相バリアント型を使って実現しています。
バリアント型というとOCamlのエフェクトを思い出します（あっちは拡張可能なバリアント型で多相バリアント型とは別ですが）。

型について、もう少し説明を加えます。

AskF v aやEmitF v aのaは操作の結果の型です。

Ask (v -> a)がv -> aという関数になっているのは、この操作がv型の任意の値を返せるようにするためです。
エフェクト型を生成しているaskのlift _ask (Ask identity)の部分を見ると恒等関数identityが使われており、渡された値がそのまま返されるようになっています。
このidentityは、ハンドラーでエフェクトの解釈を行うときに利用されます。
ちなみにaskでエフェクト型の値を生成するタイミングでは何の値を使うかわからないため、ここで具体的な値を入れておくことはできないです。
なんか難しいですが、「まぁそういうもの」と覚えてしまえば使うことはできます。

一方Emit v aが単なるaとなっているのは、この操作は何か意味のある結果を返すものではないため、常にUnit型の固定値を返せばよいからです。
emit関数のlift _emit (Emit a unit)のEmit a unitでUnit型の値を返すunit関数が使われているのはそういうことです。

ハンドラー

では次はハンドラーを見てみます。

runAsk :: forall v r. v -> Run (ASK v + r) ~> Run r
runAsk value = interpret (on _ask handleAsk send)
  where
  handleAsk :: AskF v ~> Run r
  handleAsk (Ask next) = pure (next value)

runEmit :: forall r. Run (EMIT String + EFFECT + r) ~> Run (EFFECT + r)  
runEmit = interpret (on _emit handleEmit send)  
  where  
  handleEmit :: EmitF String ~> Run (EFFECT + r)  
  handleEmit (Emit message next) = do  
    liftEffect $ log ("Emit " <> show message)  
    pure next

シグネチャを見るとRun (ASK v + r) ~> Run rのようにASKエフェクトが消去されて返されているのがわかるかと思います。

解釈の部分では、Polysemyと同じようにパターンマッチを行っています。
Ask nextのnextは定義を見るとdata AskF v a = Ask (v -> a)となっており、v -> aという関数でした。ここでいうv型の値はvalueなのでv -> a型の関数nextに渡せるわけです。
ask関数を見返してみると、このv -> aはidentityですね。
なのでvalueがそのまま返される関数となります。
それをpureで（Askエフェクトが消去され、この結果の値を持つ）新しいエフェクト型として返しています。

runEmitの方も同様です。
処理中で標準出力するため、EFFECTというエフェクトが必要で、これはそのまま残ります。
それがRun (EMIT String + EFFECT + r) ~> Run (EFFECT + r)の部分です。

エフェクトを使用する関数

AskとEmitを使う関数はこうです。
特に説明するところはありません。

askEmit :: forall r. Run (ASK String + EMIT String + EFFECT + r) Unit
askEmit = do
  liftEffect $ log "Start"
  v <- ask
  emit v
  liftEffect $ log "End"

エフェクトの解釈

上記の関数を使う関数がこちらです。
askEmitのエフェクトをハンドラーで解釈していっています。

exampleAskEmit :: Effect Unit  
exampleAskEmit =   
  askEmit  
    # runAsk "Ask Value"
    # runEmit
    # runBaseEffect

これはベタで書くとrunBaseEffect (runEmit (runAsk "Ask Value" askEmit))となります。
Haskellと同じようにも書けます（関数合成の演算子は異なりますが）。

exampleAskEmit :: Effect Unit  
exampleAskEmit =
        runBaseEffect
    <<< runAsk "Ask Value"
    <<< runEmit
    $ askEmit

runBaseEffectはRun ( effect ∷ Effect ) a → Effect aという定義になっており、エフェクトがEffectだけになったときに使うことができます。
これはRunによるエフェクト型をPureScript組み込みのEffect型（HaskellでいうIOにあたるもの）に変えるものです。

実行結果はこうなります。

Start
Emit "Ask Value"
End

処理フロー

PureScriptのRunもHaskellのPolysemyと同様、操作askやemitを呼んだタイミングで実際の処理は実行されず、実行されるのはrunBaseEffectを呼んだタイミングとなります。
実現の仕組みというか実装はHaskellのPolysemyとは全然違いますが、こういった流れについては変わらないため、あらためて説明はしませんが、以前Runの処理フローについて詳細に解説した記事を書いたので、もし関心があったらこちらをお読みください。
https://zenn.dev/funnycat/articles/230f7fa0d11739

継続の扱い

Polysemyと同じく継続はライブラリ側で一度だけ再開される1ショット継続となっています。

比較

ここからは、ここまで見てきたものをまとめてみることで比較をしていきます。

エフェクトの定義

ask

askエフェクトの定義を比べてみます。

Koka
effect ask<a>
  ctl ask() : a
Effekt
interface Ask[A] {
  def ask(): A
}
Unison
unique ability Ask a where
  ask : a
OCaml
type _ Effect.t += Ask : string Effect.t

let ask () : string = perform Ask
Haskell(Polysemy)
data Ask v m a where
  Ask :: Ask v m v

ask :: Member (Ask v) r => Sem r v
ask = send Ask
PureScript(Run)
data AskF v a = Ask (v -> a)

derive instance functorAskF :: Functor (AskF v)

type ASK v r = (ask :: AskF v | r)

_ask :: Proxy "ask"  
_ask = Proxy  

ask :: forall v r. Run (ASK v + r) v
ask = lift _ask (Ask identity)

最初から専用の構文が用意されているKoka,Effekt,Unisonといった言語が直接的にエフェクトを定義できるのに対し、後からエフェクトを導入したOCamlやHaskell,PureScriptは元からある仕組みをうまく利用してエフェクトを定義可能にしています。

emit

Koka
effect emit<a>
  ctl emit(v : a) : ()
Effekt
interface Emit[A] {
  def emit(value: A): Unit
}
Unison
unique ability Emit a where
  emit : a -> ()
OCaml
type _ Effect.t += Emit : string -> unit Effect.t

let emit (value: string) : unit = perform (Emit value)
Haskell(Polysemy)
data Emit v m a where
  Emit :: v -> Emit v m ()

emit :: Member (Emit v) r => v -> Sem r ()
emit = send . Emit
PureScript(Run)
data EmitF v a = Emit v a

derive instance functorEmitF :: Functor (EmitF v)

type EMIT v r = (emit :: EmitF v | r)

_emit :: Proxy "emit"
_emit = Proxy

emit :: forall v r. v -> Run (EMIT v + r) Unit
emit a = lift _emit (Emit a unit)

所感はemitもaskと同じです。

ハンドラーの定義

ハンドラーの定義も比べてみましょう。

ask

Koka
fun ask-handler(value : a, action : () -> <ask<a>|e> r) : e r
  with ctl ask() resume(value)
  action()
Effekt
def askHandler[R, A](a : A) { action: () => R / Ask[A] }: R / {} = {  
  try {  
    action()  
  } with Ask[A] {  
    def ask() = resume(a)  
  }
}
Unison
ask.handler : a -> Request {e, Ask a} r -> {e} r
ask.handler v = cases
  { a }            -> a
  { Ask.ask -> k } -> handle k v with ask.handler v
OCaml
let run_ask (f: unit -> 'a) ~(env: string) : 'a =  
  match_with f ()  
  { retc = Fun.id;
    exnc = raise;
    effc = (fun (type b) (eff: b Effect.t) ->
      match eff with
      | Ask -> Some (fun (k: (b, _) continuation) ->
          continue k env)
      | _ -> None)
  }
Haskell(Polysemy)
runAsk :: v -> Sem (Ask v ': r) a -> Sem r a
runAsk value = interpret $ \case
  Ask -> pure value
PureScript(Run)
runAsk :: forall v r. v -> Run (ASK v + r) ~> Run r
runAsk value = interpret (on _ask handleAsk send)
  where
  handleAsk :: AskF v ~> Run r
  handleAsk (Ask next) = pure (next value)

ハンドラーの方は、やってることは対応するエフェクトに解釈を与えて消去した新しいエフェクトを返すということで、シグネチャ的には同じようなことが書かれてているのですが、実装は大分各言語によって色が違うように見えます。

Kokaはシンプルですね。ctlやfunによって継続を明示的に扱うかを制御できるのが特徴的です。

Effektはtry～withという構文から、「Algebraic Effects & Handlersとは一般化された例外である」と考える思想を感じました。tryブロックの中でエフェクトを使い、withブロックの中でハンドリングするというのは、似た構文を持つ言語の経験者の認知負荷を下げるかもしれません。

Unisonはパターンマッチを使っているのですが、{ a }というパターンが何なのかであったり、継続kが渡ってくるパターンにおいて自分で再帰部分を書いたりと、若干難易度が高めな印象です。

OCamlはエフェクトの型が出てこないのが特徴的です。
パターンマッチの部分でUnisonやHaskell,PureScriptとの共通性があります。

HaskellのPolysemyもパターンマッチするタイプですね。

PureScriptのRunもパターンマッチではありますが、Polysemyとの差分としてnextのような関数が登場してきてます。

emit

Koka
fun emit-handler(action : () -> <emit<string>,console|e> r) : <console|e> r
  with ctl emit(message)
    println("Emit " ++ message)
    resume(())
  action()
Effekt
def emitHandler[R] { action: () => R / Emit[String] }: R / {} = {
  try {
    action()
  } with Emit[String] {
    def emit(value: String) = resume(println("Emit " ++ value))
  }
}
Unison
emit.handler : Request {e, Emit Text} r -> {e, IO, Exception} r
emit.handler = cases
  { a }                  -> a
  { Emit.emit msg -> k } -> handle
    printLine("Emit " ++ msg)
    k ()
  with emit.handler
OCaml
let run_emit (f: unit -> 'a) : 'a =
  match_with f ()
  { retc = Fun.id;
    exnc = raise;
    effc = (fun (type b) (eff: b Effect.t) ->
      match eff with
      | Emit value -> Some (fun (k: (b, _) continuation) ->
          Printf.printf "Emit %s\n" value;
          continue k ())
      | _ -> None)
  }
Haskell(Polysemy)
runEmit :: (Member (Embed IO) r) => Sem (Emit String ': r) a -> Sem r a
runEmit = interpret $ \case
  Emit a -> embed $ putStrLn a
PureScript(Run)
runEmit :: forall r. Run (EMIT String + EFFECT + r) ~> Run (EFFECT + r)  
runEmit = interpret (on _emit handleEmit send)  
  where  
  handleEmit :: EmitF String ~> Run (EFFECT + r)  
  handleEmit (Emit message next) = do  
    liftEffect $ log ("Emit " <> show message)  
    pure next

ハンドラーに関しても所感はaskと同じです。

合成されたエフェクトを使う関数

Koka
fun ask-emit() : <ask<a>, emit<a>, console> ()
  println("Start")
  val v = ask()
  emit(v)
  println("End")
Effekt
def askEmit[A](): Unit / { Ask[A], Emit[A] } = {
  println("Start")
  val v = do ask[A]()
  do emit(v)
  println("End")
}
Unison
composed.emitAsk : '{Emit a, Ask a, IO, Exception} ()
composed.emitAsk = do
  printLine("Start")
  askValue = Ask.ask
  Emit.emit askValue
  printLine("End")
OCaml
let ask_emit () =
  printf("Start\n");
  let value = ask () in
  emit value;
  printf("End\n")
Haskell(Polysemy)
askEmit :: Members '[Ask String, Emit String, Embed IO] r => Sem r ()
askEmit = do
  embed $ print "Start"
  v <- ask
  emit v
  embed $ print "End"
PureScript(Run)
askEmit :: forall r. Run (ASK String + EMIT String + EFFECT + r) Unit
askEmit = do
  liftEffect $ log "Start"
  v <- ask
  emit v
  liftEffect $ log "End"

この部分は、一番差がない部分なのではないでしょうか。
特に実装内容に関しては各言語ともにかなり似ています。

エフェクトに解釈を与えて使う関数

Koka
pub fun example-ask-emit()
  with ask-handler("Ask Value")
  with emit-handler()
  ask-emit()
Effekt
def exampleAskEmit() = {
  with askHandler("Ask Value")
  with emitHandler
  askEmit[String]()
}
Unison
composed.runEmitAsk : '{IO, Exception} ()
composed.runEmitAsk = do
  handle
    handle composed.emitAsk()
    with ask.handler "Ask Value"
  with emit.handler
OCaml
let example_ask_emit_simple () =
  run_ask (fun () -> run_emit ask_emit) ~env:"Ask Value"
Haskell(Polysemy)
exampleAskEmit :: IO ()
exampleAskEmit = do
    runM
  . runAsk "Ask Value"
  . runEmit
  $ askEmit
PureScript(Run)
exampleAskEmit :: Effect Unit  
exampleAskEmit =   
  askEmit  
    # runAsk "Ask Value"
    # runEmit
    # runBaseEffect

ここも比較的似た感じです。
Algebraic Effects & Handlersの言語の方はOCaml以外は専用の構文が用意されており、ハンドラーを用いてエフェクトを解釈しているのがぱっと見でわかります。
UnisonやOCamlのハンドラーはエフェクトが増えていったときネストが増えていくことになります。
Extensible Effectsの方は専用の構文はありませんが、runXXXのような命名をすることで、エフェクトを使用していることを示せるのではないでしょうか。

処理フロー

Algebraic Effects & Handlersを採用する言語では、エフェクトの操作を呼び出したときに、その時点の処理の続きを継続として捕捉してハンドラーに渡し、すぐさまハンドラーが呼び出されていました。
一方Extensible Effectsの方では、操作の呼び出しの連なりからなる処理の流れ自体をデータ構造として表現し、あとから解釈を重ねて最終処理を実行したそのタイミングで、対応するハンドラーが呼び出されます。

継続の扱い

Algebraic Effects & Handlers側の言語では、継続を明示的に扱うことができました。
またKoka,Effekt,Unisonはマルチショット継続で、継続を複数回再開することができました。
OCamlは継続を明示的に扱えますが、1ショット継続でした。
一方HaskellのPolysemyとPureScriptのRunによるExtensible Effectsでは、継続は暗黙的に利用されており、かつ1ショット継続でした。

まとめ

Algebraic Effects Extensible Effects
エフェクトの定義 最初からエフェクトを想定して作られた言語は専用の構文がある。そうでない場合は既存の構文を利用して定義する。 代数的データ型と通常の関数によって定義する。
操作の呼び出し 即ハンドラーに制御が移る 処理の流れを表すデータ構造が(一つ前の流れの構造に)加わる
ハンドラーがやること 操作のパターンマッチと実際の処理および継続の再開(しなくてもよい) 対応するエフェクトを解釈して除去した新しい型のエフェクトを返す。操作のパターンマッチおよび実際の処理は、通常のモナドに変換する最後の解釈の際に行われる
継続 明示的に扱える 暗黙的に扱われる
継続の再開 Koka,Effekt,Unisonは複数回可能。OCamlは一度のみ。明示的に扱えるので再開しないこともできる。 自動で一度だけ再開される

あとは

  • 合成されたエフェクトを使用する関数はどれも似ている。
  • 解釈を与える部分も専用の構文の有無や構文の違いはあれ、比較的同じように書ける。

といった感じでしょうか。

さいごに

私の興味による偏りはご容赦いただくとして、いくつかの言語でのエフェクトシステムの比較を行ってみました。
それぞれ構文の違いや、実現の方法は違えど、エフェクトやハンドラーといった概念に共通性があることが見て取れたのであれば幸いです。

個人的な感想

  • Kokaはエフェクトとハンドラーを素直に表現できてよい。書き味としては一番よかったです。
    　これで本番環境用のプログラムが開発できたら、と思います。
  • Effektはtry～withという構文が、他の言語からのコンバート的な意味ではわかりやすいのかもしれない。ただ個人的にはtryというキーワードは他の言語の例外処理を想起してしまい用途がそっちに引っ張られないかなぁとか、状態を扱うのもtryの中でするのか？みたいな他の言語を知っているがゆえのギャップを感じました。
  • Unisonは大分独特だが、実用を目指していそうで、期待できる。ハンドラーを使用するところにKokaのような糖衣構文があると嬉しいかもしれない。
  • OCamlは既存の言語に新しくエフェクトとハンドラーの仕組みが加わっており、最初からエフェクトありきで設計された言語と比べると、複雑度が高いように感じましたが、それは私がOCaml初心者だということが影響してそうです。既にOCamlを習得済みの方であれば知っている部分との差分に過ぎないので大分印象が変わりそうです。また、元の言語仕様を維持しつつ後から言語としてエフェクトを使えるようにするのはとても大変だったのではないかと思います。
  • Haskellでは今回Polysemyを取り上げたが、他にも色々ライブラリはあり、同じ言語の中での選択肢が多いのは楽しい。一方で選択肢が多い故にどれを使えばいいのかわからなくて困る、ということもありそう。最初のうちは何が違うのかもわからないでしょうし。また、PolysemyというよりExtensible Effectsについてですが既存の言語機能でエフェクトシステムを実現できるアイデアをよく思いついたな、と。最初概念を知った時は感動したものです。
  • PureScriptのrunは個人的にエフェクトを知るきっかけになったライブラリであり、思い入れは一番あります。ただ他と比べてみると難しいと感じました。やりたいことに対して一定お約束のコードを書くことになるのですが、なぜそうするのか？がわかりづらいですね。公式のサンプルを見て真似てみれば動いたりしますが、細かい説明はなかったりするのでそこは自力で理解するしかない。ある程度素養がある人向けのライブラリなのかも（私はここから入ったので大分苦労した）。なんか悪いことばかり書いてるみたいですが、これもPureScriptの言語的制約の中でよく実現したなと驚嘆せざるを得ません。

以上、とてもとても長くなりましたが、終わりになります。
飛ばし読みした方も、全部読んで下さった方もありがとうございました。

Discussion