Unlambdaインタプリタを作った

Unlambda esolang

Unlambdaインタプリタの性能を気にする人というのもあまりいないと思いますが、ELVMをセルフビルドすると何日もかかったり、AtCoderをUnlambdaで解いてみたら時間制限が厳しかったという話を見て、まあ速いインタプリタあるといいよねと思っていました。

Unlambdaの高速なインタプリタといえばEmil Jeřábek氏のunl.cがあり、公式のc-refcntインタプリタの50〜100倍も高速です。 ただこのインタプリタはコードが結構複雑で、これを改造して何かを作るというのは大変です（unlambda-dcのときにやろうとして断念しました…）。

というわけで自作のインタプリタをいちから書いてみました。

https://github.com/irori/unlambda

ベンチマーク

以下の3つのプログラムで、unl.cと実行時間を比較しました。

結果です。unl.cより1.6倍～2.2倍速いようです。

プログラム unl.c 自作インタプリタ
adventure 0.72s 0.41s
lisp 2.05s 1.28s
elvm-8cc 44.3s 20.1s

ちなみにELVMはBrainfuck（付属のbfoptを使ったとき）より速くなりました。Unlambdaはやればできる子。

実装

ソースコードはC言語で600行ほどで、そのうち半分くらいがメモリ管理コードです。以下、工夫した点を紹介します。

ガベージコレクション

Unlambdaプログラムの実行中に作られるオブジェクトグラフは循環しないので、参照カウンタでメモリ管理ができます。実際、多くの（GCを持たない言語で実装された）Unlambdaインタプリタは参照カウンタ方式を採用しています。

しかしUnlambdaの実行では頻繁にオブジェクトの生成・破棄が繰り返されるので、参照カウンタの操作は結構なオーバーヘッドになります。またunl.cがしているように、参照カウンタの操作を省略できるところは省略したり、カウンタが1のときはオブジェクトを上書きして再利用するなどの最適化を入れるとコードが複雑化してしまいます。

今回実装したインタプリタでは世代別GCを採用しました。新世代はオブジェクト256k個分の領域を2つ用意してコピーGCを行い、このマイナーGCを2回生き延びたオブジェクトは旧世代領域に移動します。旧世代領域がいっぱいになると、メジャーGCとして全体に対してマークスイープGCを行います。

Unlambdaで世代別GCは非常に有効で、プログラムにもよりますが、マイナーGCで99%以上のオブジェクトを回収できることが多いです。全体の実行時間に占めるGCの割合も1%程度に抑えられました。

世代別GCでは通常、旧世代領域から新世代領域への参照を追跡するためにライトバリアが必要になります。ですがこのインタプリタでは一旦作られたオブジェクトが書き換わることはないため、旧世代から新世代への参照は発生しません。ライトバリアが不要なので、評価器ではGCのことをあまり気にせずコードを書けます（コピーGCでアドレスが変わる点は注意が必要ですが）。

コンビネータの置き換え

※ 以下の説明はUnlambdaやLazy Kなどでプログラムを書いたことがないとわかりにくいかもしれません。

Unlambdaの組み込み関数Sは、引数を関数適用の両辺に分配する働きをします。例えば、`fgという式の中で外から渡される値xを使いたいとき、元の式を``Sfgに書き換えてやると、xが渡されたとき```Sfgx→``fx`gxとなり、fとgの両方にxを渡す形にできます。fやgがもっと複雑な式で、その部分式でxを使いたい場合は同様の変換をfやgにも行えばいいわけです。

実際はfとgの両方でxが必要になることはあまりなくて、どちらか一方では値を捨てたくなることが多いです。そんなときは組み込み関数Kの出番です。fの中でxが不要であれば、``Sfgのfを`Kfに置き換えて、``S`Kfgにします。これに値xを渡すと、```S`Kfgx → ```Kfx`gx → ``f`gxとなり、xはgだけに渡ります。同様にgの中でxが不要であれば、gを`Kgに書き換えると、```Sf`Kgx → ``gx``Kgx → ``fxgとなり、xはfだけに渡されます。

これらの場合のSとKの働きを1ステップで実行するコンビネータを考えることができて、B, Cコンビネータとして知られています。

  ```Bfgx = ```S`Kfgx = `f`gx
  ```Cfgx = ```Sf`Kgx = ``fxg

これらはUnlambdaの組み込み関数ではないのでプログラムを書くときには使えませんが、インタプリタ内部でSとKの組み合わせをこれらの「軽い」コンビネータに置き換えることで高速化を図れます。

具体的には、Sに第1引数あるいは第2引数が与えられた時点で、それがKの部分適用（引数ひとつを与えられた状態）であればBまたはCに置き換えます。式の評価の結果書き換え可能な形になることもあるので、構文解析時にパターンマッチするだけでは不十分です。

今回実装したインタプリタでは、BとCに加えて以下のT, Vコンビネータへの置き換えもしています。（Unlambdaの組み込み関数vとは別物です）

  ``Txy = ```SI`Kxy = `yx
  ```Vxyz = ```S`Tx`Kyz = ``zxy

Tは第2引数を第1引数に適用するコンビネータで、Vへの置き換えの中間段階として導入しました。VはUnlambdaでオブジェクトのペアを表現するときによく使われる表現 (cons) です。ペアをS, K, Iの組み合わせでなく単一のオブジェクトとして表せるため、メモリの節約になります。特にELVMでUnlambdaにコンパイルされたプログラムは非常に多くのペアを作るためこの最適化が有効で、ELVMのセルフビルドをするとunl.cでは2.6GBのメモリが必要だったのが、1.2GB程度で済むようになりました。

  1. make unl を実行すると生成される8cc.c.eir.unlを使用↩