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

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

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

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

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

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

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

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

標準出力のためのconsoleエフェクトを含めた三つのエフェクトを使っているため, emit, 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が返す, emit, console> ()のaskはask-handlerによる解釈で消去され、emitはemit-handlerによる解釈で消去され、consoleだけが残り、console ()が返されます。

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

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

(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")
  }
}

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

Start
Emit Ask Value
End
Emit Ask Value
End

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

Start
Emit Ask Value
End
End

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

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

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

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("------------")

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

次は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()
}

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

処理フロー

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

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

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

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

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

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

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

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"

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エフェクトを表現する例)

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

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

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

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

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の中で継続は使われています。

interpretH
    :: (∀ rInitial x . e (Sem rInitial) x -> Tactical e (Sem rInitial) r x)
       
       
    -> 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

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

処理フロー

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エフェクトの定義を比べてみます。

effect aska>
  ctl ask() : a

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

unique ability Ask a where
  ask : a

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

let ask () : string = perform Ask

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

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

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

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

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

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

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

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

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

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

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

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

def askHandler[R, A](a : A) { action: () => R / Ask[A] }: R / {} = {  
  try {  
    action()  
  } with Ask[A] {  
    def ask() = resume(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

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

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

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

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

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

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

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

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

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と同じです。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ショット継続でした。

まとめ

あとは

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

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

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

個人的な感想

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

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