🦋

代数的エフェクトを言語でサポートするKokaでLisp処理系を実装してみる

2024/06/18に公開

effect

koka

tech

https://github.com/yubrot/kokalisp

導入

Kokaというプログラミング言語があります。強い静的型付けの関数型プログラミング言語で、大きな特徴としてエフェクト型とハンドラを言語でサポートしていることが挙げられます。言語名が日本語の「効果」に由来しています。

以前からエフェクトのサポートがある言語を触ってみたいと思っていたので、今回KokaでSECDマシン風のVMを用いるLisp処理系の実装を試みました。本記事はLisp処理系の実装を通したKokaの感想になります。

筆者はプログラミング言語を学ぶときには、Lisp処理系を作るということをしばしば行います。何度かLisp処理系を作っているうちに、処理系のデザインの共通化やテストスイートの再利用といったこともやっていて、今回作成したKokalispもその一例になりました。この取り組みについては以前の記事をご参照ください。

実装は yubrot/kokalisp にあります。

Kokaのエフェクト以外

Kokaは汎用プログラミング言語で、基本的なプログラムの構造はOCamlやStandardMLに似ています。プログラムの主な構成要素はデータ型と関数で、例えばsamples/basic/rbtree.kkを見ると、

type tree<a> のような代数的データ型の宣言があり、
fun insert(t : tree<a>, k : int, v : a) : tree<a> のような関数があり、...

といった部品でプログラムを記述することがわかります。類似のプログラミング言語の経験があれば、公式ドキュメントのA Tour of Kokaを読めばとりあえず書き始められます。Kokalispでエフェクトがほぼ出てこないコードの例としてkokalisp/kokalisp/sexp.kkを見てみると、そのコードはOCaml実装のocalisp/lib/sexp.mlのものとよく似ています。

Kokaはエフェクト以外についてはまったく平凡...というわけでもなく、Minimal but Generalを標榜して、言語仕様はなるべく小さくしつつ、しかし直交性・汎用性の高い言語機能を備えようとしています。特に構文面での工夫で、関数の取り回しの良さを底上げしている印象です。

Dot notation
- s.encode(3) のような式は常に関数適用 encode(s, 3) の糖衣構文。 struct 宣言時に自動定義されるフィールドへのアクセサも、この糖衣構文を前提とした単なる関数
Trailing lambda
- 匿名関数は fn(<args>) { <body> } と記述するが...
- 関数呼び出しの最後の引数の匿名関数は、括弧の外側に後置できる: for(1, 10) fn(i) { i.println }
- 匿名関数が引数を取らない場合 fn() を省略できる: repat(10) { println("hi") }
With statements
- Haskellの do やScalaの for 式に似た糖衣構文
- 関数を最後の引数として渡すパターンが頻出であることに注目して、そのパターンをフラットに書けるようにする
Brace elision
- インデントによってカーリーブレイス {} が補完される

この中でもDot notationは特に攻めた仕様ですね (オーバーロードどう解決するんだろう等が課題になってくる)。標準ライブラリもこれらの機能を念頭に置いたであろう作りになっていて、例えばKokaでは while が制御構造ではなく関数として定義されていますが、これは通常の関数ながら Trailing lambda, brace elision によって以下のように使用できます:

var i := 0
// while(fn() { i < 10 }, fn() { println("hello"); ... }) 相当
while { i < 10 }
  println("hello")
  i := i + 1

Kokaのエフェクト

副作用とエフェクト型

Kokaでは、関数がなんらかの副作用を伴い得るとき、それがエフェクト型としてその関数の型に表れます。関数の定義において、返り値の型の手前に表記されたものがエフェクト型です。

// total は空のエフェクト型、なんのエフェクトも伴わないことを示す
fun square1(x : int) : total int
  x * x

// totalは省略できる
fun square1'(x : int) : int
  x * x

// exn は言語標準の例外を発しうることを示すエフェクト型
fun square2(x : int) : exn int
  if x < 0 then throw("negative argument")
  x * x

// 複数のエフェクト
fun square3(x : int) : <exn, console> int
  println("some console output: " ++ x.show) // コンソールへの副作用を伴う
  if x < 0 then throw("negative argument")
  x * x

副作用の有無を明示的に型でトラックすることができています。先ほど取り上げたwhile 関数も、引数に取っている条件部分や本体部分の関数型にエフェクトの記述が伴っています。 <div|e> となっているのは、繰り返しが終わらなければこの関数が制御を返さないためですね。 div はdivergenceの略、 e はエフェクト型変数です。

型注釈に明示的にエフェクト型を書くのは面倒そうに思われますが、Kokaではwildcard _ を用いることで部分的にコンパイラの推論に任せるような型注釈も記述できます。Kokalispの実装ではトップレベルの定義はエフェクト型も基本的に明示するようにしましたが、これを _ に置き換えてみてもおおむね推論任せで問題なさそうでした (推論では難しそうだったのは st<h> など)。

副作用を明示的に扱う道具というと、HaskellのIOモナドが思い浮かびます。Kokaでも最大公約数的なエフェクト型がioという名前で定義されていたりします (<ndet, console, net, fsys, ui, div, exn, st<global>> 相当のエイリアス)。モナドによる表現ではアクションの合成は全て明示的で、 >>=, fmap, mapM, ... といった演算子を活用しますが、Kokaでは一般的な命令型プログラミング言語のようにプログラムを記述し、その中でエフェクトの作用点を制御したいときには関数型を用いることになります。

細かい感想: 個別の言語組み込みのエフェクトについて

div: 計算が停止するか? コンパイラの停止性の計算は非常に限定的なので、標準ライブラリでも停止性の計算のためのマーカーとして使われるpretend-decreasingが結構出てくる。トラックしてくれて嬉しくないということはないが、これだとまだコード上のノイズが大きくて、divを気にしない運用もありそうだなという印象
exn: 例外。Kokaでは match のパターン漏れがある場合も即座にコンパイルエラーとならず例外を伴い得る式という扱いになり、 exn エフェクトが関数の型に含まれないことで初めてコンパイルエラーとなる。この扱い自体は良いが exn はもう少し細分化されていてほしい
- Kokaの標準ライブラリには alias pure = <exn, div> というエイリアスがあり、これがHaskellの純粋関数に相当する
st<h>: st<h> は <read<h>, write<h>, alloc<h>> 相当のエイリアスで、ステートフルな関数を意味し、 ref<h, int> のようなミュータブルな参照を読み書きできる。Haskellでいう ST に相当するが、ステートが関数に閉じていればこれらエフェクト型は関数には付かないように推論されるのでローカルステートを割と気軽に扱える

ユーザ定義のエフェクトとハンドラによる制御フローの拡張

エフェクト型は一般的な副作用専用のものではなく、ユーザが独自にエフェクトを定義することができます。例えばKokalispでは、標準の例外 exn が持てるデータが message : string 固定で都合が悪かったので、独自に raise エフェクトを定義しています:

// エフェクト raise<a> を定義
pub effect raise<a>
  ctl raise(x : a) : b

// raise オペレータを使用しているので、関数のエフェクト型に raise<int> が付く
fun some-func(x : int) : raise<int> int
  if x < 0 then raise(x)
  x + 1

ハンドラを定義することで、エフェクトに対する具体的な振る舞いを与えることができます (以下の例は実際の実装より少し型を簡略化しています):

// raise<l> を either<l, r> に変換する
pub fun either(action : () -> raise<l> r) : either<l, r>
  with handler
    ctl raise(l) Left(l)
  Right(action())

// 例外 raise<l> を raise<m> にマップする
pub fun map(map-fn : l -> raise<m> m, action : () -> <raise<l>, raise<m>> r) : raise<m> r
  with handler
    ctl raise(l) raise(map-fn(l))
  action()

ハンドラは限定継続に相当する resume をファーストクラスの関数として受け取るため、限定継続でできて型システムと矛盾しないことはおおよそできるはずです...多分。上の例では resume を使わないことでハンドラの外までの大域脱出として機能しています。

エフェクトによるコルーチンの実装例

「おおよそできるはず」としましたが不安だったので、一つ例として、再開可能な手続き...コルーチンを実装してみました:

effect yield<a>
  ctl yield(x : a) : ()

// 継続 () -> <yield<a>, st<h>, div | e> () を状態とする参照
alias coroutine<h, a, e> = ref<h, () -> <yield<a>, st<h>, div | e> ()>

fun coroutine/create(action : () -> <yield<a>, st<h>, div | e> ()) : alloc<h> coroutine<h, a, e>
  ref(action)

fun coroutine/continue(c : coroutine<h, a, e>) : <st<h>, div | e> maybe<a>
  handle !c
    raw ctl yield(a)
      // yieldされたら継続(resume)を参照にセットして、yieldされた値を返す
      set(c) { rcontext.resume-shallow(()).ignore }
      Just(a)
    return(_)
      Nothing

fun test-producer()
    println("A")
    yield(12)
    println("B")
    yield(34)
    println("C")
    yield(56)
    println("D")

pub fun test-yield()
  val c = coroutine/create(test-producer)
  fun consume(step : int)
    println("--- step " ++ step.show ++ " ---")
    match coroutine/continue(c)
      Just(x) ->
        println("got " ++ x.show)
        consume(step + 1)
      Nothing ->
        println("done.")
  consume(0)

resume の代わりに rcontext.resume-shallow を使用していること等詳細は割愛しますが、以下のような出力順 (手続きの流れ) となり、手続きの中断と再開が実現できていることがわかります。

--- step 0 ---
A
got 12
--- step 1 ---
B
got 34
--- step 2 ---
C
got 56
--- step 3 ---
D
done.

resume を活用した例として、標準ライブラリにあるstd/text/parseがあります。これはHaskellのmegaparsec等で知られるパーサコンビネータです。パーサコンビネータですが、その文脈はモナドではなくエフェクトとして表現されているので、モナドによるパーサコンビネータのコードで頻出の map, flatMap といった演算子が出てきません。

// Scalisp: Scalaのcats-parseによる数値のパーサの例
// *> による連結や、 map(_.toDouble) のような P[T] から P[S] への変換といった文脈上の計算が明示的に表れる
val number: P[Double] =
  val digits = P.charIn(digit).rep.void
  val frac = P.string(".") *> digits.?
  val exp = P.charIn("eE") *> P.charIn("-+").? *> digits
  (digits *> frac.? *> exp.?).string.map(_.toDouble)

// Kokalisp: std/text/parseによるパーサの例
// (++) はKokaの標準的な文字列結合演算子、 to-float64 も string -> float64
fun number() : parse float64
  fun digits() chars-are("digit", is-digit).string
  fun frac() pstring(".") ++ digits()
  fun exp() one-of("eE").string ++ one-of-or("+-", '+').string ++ digits()
  (digits() ++ optional("", frac) ++ optional("", exp)).to-float64

実装はどうなっているのか、ハンドラの実装を見ると、 resume を複数回呼ぶことで選択を実現していることがわかります。

細かい感想

APIの練度にcats-parseとはだいぶ差がありつつ、エフェクトの作用点を意識したいパーサの例は、モナドで明示的に書けるほうがわかりやすいかもしれない...? 構文的な問題だろうか?
巷のプログラミング言語では、このような制御フローに関わるエフェクトはそれぞれ個別に言語仕様として取り入れられる場合が多いので、それをこのようにユーザ定義・利用できるのはとても面白い。しかし、これまた巷のプログラミング言語は、そういった言語機能はそれぞれをよく検討し、うまく併用できるように注意深く導入してきているはずで、制御フローに関わるようなエフェクトをユーザが気軽に定義できてどれぐらい活用できるのか、できて良いのか、みたいな感覚もある
- 言語仕様をシンプルにできるというのはそれだけで魅力的ではある
Kokalispの実装におけるユーザ定義のエフェクトは raise 以外は次の節のようなエフェクトの活用が主だったので、エフェクトの表現力をフルに活用したユースケースをもっと見たい

抽象としてのエフェクト

ここまでエフェクト型とハンドラの表現力に注目してきましたが、「平易な」手続きの抽象としてもエフェクトは有効です。Kokaでは、末尾で必ず一回 resume を呼び出すオペレーション、つまりオペレータの利用側から見て、通常の関数呼び出しのように計算の結果が返ってきて制御が戻るオペレーションをTail-Resumptive Operationsと呼び、これが頻出である^[1]ことから専用の構文を用意しています。これは糖衣構文として機能しつつ、コンパイラによる最適化のための情報としても活用できるとしています。

// ctl ではなく fun を使うと...
with handler
  fun op(<args>) { <body> }

// 以下と等価となる
with handler
  ctl op(<args>) { val f = fn() { <body> }; resume(f()) }

やや恣意的な例になりますが、依存性の注入(Dependency Injection)のようなパターンをエフェクトで置き換えることができます。
ロギングのために Logger を、イベント発行のために EventPublisher を、設定値の読み出しのために Configuration を、...といった調子に依存を引数として取る代わりに、それら依存による手続きを直接エフェクトで表現します。

pub effect log
  fun log-error(msg : string) : ()
  fun log-warn(msg : string) : ()
  fun log-info(msg : string) : ()

pub effect evpub
  fun publish-event(ev : application-event) : ()

pub effect config
  val config : application-configuration

// ロギング、イベントの発行、設定値の読み込みなどはオペレータを介す
fun some-application-usecase(input : string, ...)
  log-info("logs something")
  publish-event(...)
  some-function(input, config.some.option)

// ブートコードはそれぞれのエフェクトのハンドラを与える
fun main()
  with default-logger
  with default-event-publisher
  with val config = read-config(...)
  some-application-usecase(...)

細かい感想

KokalispもベースとしているRosetta Lispシリーズは、プログラミング言語自体を学ぶことに集中するために実装が全体的に純粋関数で書かれていて、このパターンでもエフェクトを活用する機会は相対的に乏しかった気がするが、このパターンは普段のアプリケーション開発を想像するとかなり有用だろうと思う
このように振る舞いとエフェクトを分離できるからといって、全てをエフェクトにするかというとそれは違うだろうという感覚があり、エフェクトの文脈と値の文脈の使い分けが難しくなりそう...とか感じた
- この話は制限された fun オペレータに限らない。例えばKokalispの実装では、 raise<l> r と either<l, r> の使い分け、切り替えのポイントといったところに迷った感覚がある

結び

Kokalispの実装は、コンパイラのバグをいくつか踏みつつなんとかRosetta Lispのテストを全てパスするまで実装することができました。実際にKokaの型システムのサポートの下でコードを書くことで、エフェクトとハンドラのサポートがあるとどういうことができるのかというのを感じることができました。一方で、それをフルに活用できた感覚はなかったりします。例えばKokalispでは複合的なエフェクトの活用はほぼありませんし、ユーザ定義のエフェクトの利用も限定的です。引き続き気が向いたときに追っていきたいかなと思います。^[2]

その他読み物

「エフェクト」という概念自体は最近浸透してきていて、ちらほら目にする気がします。

脚注

むしろほとんどのオペレーションは実践的にはTail-resumptiveだろうとしている ↩︎
今のところあまり追ってないがMulticore OCamlとかで色々実践的な活用例とかが出てこないかな ↩︎

導入

Kokaのエフェクト以外

Kokaのエフェクト

副作用とエフェクト型

細かい感想: 個別の言語組み込みのエフェクトについて

ユーザ定義のエフェクトとハンドラによる制御フローの拡張

細かい感想

抽象としてのエフェクト

細かい感想

結び

その他読み物

Discussion