UnlambdaでVMを実装する(前編)

Esolang Advent Calendar 2016 2日目の記事です。

ELVMにUnlambdaバックエンドを実装して、C言語のプログラムをUnlambdaに変換できるようにした話です。ちょっと長くなったので2回に分けました。

Unlambdaとは

UnlambdaはBrainfuckの関数型版とでもいうべき言語で、関数適用演算子`s, k, iなど少数の組み込み関数だけを使ってプログラムを書きます。

Unlambdaには変数すら無いので直接プログラミングするのは厳しくて、普通はラムダ式を使ってプログラムを書いて、あとからラムダを取り除く(だからUn-lambdaなのですね)変換をかけてやります。とはいえ、組み込み関数とその簡単な組み合わせで何ができるのか把握しておくと、小さくて速いプログラムが書けます。

Unlambda言語について - Qiita

この記事自体はUnlambdaを知らなくても、若干の関数型言語の知識があれば読めると思います。

ELVMとは

ELVMはesolang用のコンパイラ基盤で、高級言語(現在はC言語のみ)から各種のesolang用コードに変換できます。Cコンパイラ自体をコンパイルしてBrainfuckで動くCコンパイラを作ったり、Unlambdaで動くviを作ったりできます。

仕組みについてはid:shinichiro_hさんの記事スライドが詳しいですが、C言語のプログラムを一旦ELVM IRと呼ばれる単純な仮想マシンの命令列にコンパイルして、ELVM IRからBrainfuckやUnlambdaなどのターゲット言語に変換します。

仮想マシンの仕様はここにありますが、概要としては

  • 24bitレジスタ6つ
  • 24bitアドレスのメモリ。ひとつのメモリセルに24bitの値を格納できる
  • 使える命令は mov, add, sub, load, store, setcc, jcc, putc, getc, exit

という感じです。esolangで実装しやすいように非常に単純な仕様になっています。

Unlambdaでデータ構造を表現する

さてレジスタとかメモリとか言われても、Unlambdaには関数しかありません。組み込みの整数すらありません。なんとか関数を使ってさまざまなデータ構造を表現する必要があります。

ペア

最も基本的なデータ構造として、2つの値を保持するペアを考えます。これはUnlambda言語のサイトにも書かれていますが、cons, car, cdr の3つの関数で実現できます。

# ペア <x, y> を作る
cons = λxyf.fxy = ``s``s`ks``s`kk``s`ks``s`k`sik`kk

# ペア <x, y> から x を取り出す
car = λp.p(λxy.x) = ``si`kk

# ペア <x, y> から y を取り出す
cdr = λp.p(λxy.y) = ``si`k`ki

consはx, y, fの3つの引数を取り、fxyを適用する関数です。普通はxyのみをまず適用してペアを作り、fは値を取り出すときにcarかcdrによって与えられます。

carは引数pを取り、p(λxy.x)を適用します。(λxy.x)は引数を2つとり、1つ目の引数を返す関数です*1pはconsで作ったペアなので、consのf(λxy.x)を入れるとペアの最初の要素が返ってくるのがわかると思います。同様にcdrはペアの2つ目の要素を取り出します。

リスト

リストはペアを使って作ることができます。要素 e1, e2, ..., en を持つリストは以下のように表現します。

[e1, e2, ..., en] = (cons e1 (cons e2 (... (cons en v)...)))

Lispでリストを作るときと同じですね。リストの終端にはUnlambdaの組み込み関数vを使います。

数値

Unlambdaでの数値表現の定石はチャーチ数ですが、大きな数を使うと遅くなってしまうため、24ビット整数を扱う必要があるELVMには向いていません。

そこで数値の表現としては24要素のリストを使い、各要素はUnlambdaの組み込み関数を使って、`kiで0のビット、kで1のビットを表すことにします。要素は下位ビットから並べます。例えば3の2進表現は11なので、以下のように表現できます。

[k, k, `ki, ..., `ki]  # 24要素のリスト
= (cons k (cons k (cons `ki (... (cons `ki v)...))))

ELVMのシンプルな仕様のおかげで、必要な算術演算は数個だけ(add, sub, eq, lt)です。

例: inc関数

数値を扱う処理の例として、数値に1を加える関数incの実装を見てみましょう。(ELVMにはincやdecといった命令はありませんが、スタック操作などでインクリメント/デクリメントが多用されるため専用の処理を用意しています。)説明のため、記法や変数名は変えてあります。

incRec = cons (λt. (cons `ki) (t incRec))
              (cons k)
inc n = n incRec

…意味がわかりませんね。ペアや数値の関数としての表現をフル活用して最適化しているため分かりづらくなっています。読み解いてきましょう。

主な処理は再帰関数incRecのほうに書かれていて、incは与えられた数値にincRecを適用しているだけです。(数値は関数で表現されているので適用できるのです。)数値nがリスト[b1, b2, ..., b24]だとすると、inc n[b1, b2, ..., b24] incRecになります。リストはペアで表現されているので、これはつまり(cons b1 (cons b2 ...)) incRecと同じです。

さてペアもまた関数で表現されているのでした。cons x y f = f x yなので、上の式の一番外側のconsを展開するとincRec b1 (cons b2 ...)になります。incRecの定義を展開すると、

(cons (λt. (cons `ki) (t incRec)) (cons k)) b1 (cons b2 ...)

となります。複雑になってきましたがもう少し辛抱してください。さらに先頭のconsを展開すると以下のようになります。

(b1 (λt. (cons `ki) (t incRec)) (cons k)) (cons b2 ...)

b1はincの引数nの最下位ビットで、0なら`ki、1ならkです。もしb1が`kiなら、`kiは引数を2つ取り2つ目の引数を返すので、

(cons k) (cons b2 ...)

となり、これがincの結果になります。リスト[`ki, b2, ..., b24][k, b2, ..., b24]になったので、元の数より1大きい数になっていることがわかります。

次にb1がkの場合を考えます。kは引数を2つ取り1つ目の引数を返す関数なので、b1を適用した結果は

(λt. (cons `ki) (t incRec)) (cons b2 ...)

になります。ラムダ式を適用してt(cons b2 ...)を代入すると、

(cons `ki) ((cons b2 ...) incRec)

となり、これは最下位ビットが`kiつまり0で、2番目以降のビット列をintRecで1加算したもの、つまり繰り上がりの処理です。こちらも元の数に1を足した結果になることがわかります。これで大体うまくいきそうですが、再帰の終了条件らしきものがありません。nのすべてのビットが1だった場合何が起こるのでしょうか?

リストの終端はvを使って表すのでした。これを上の式に当てはめると、最上位ビットb24が1だった場合の再帰の最終段は

(cons `ki) (v incRec)

となり、(v incRec)vですからそれ以上の再帰は起こらず、結果として24個の要素すべてが`kiのリスト、つまり数値0が返ります。

このように、ちょっとトリッキーでしたがちゃんと24ビット整数に1を加える処理になっていることがわかります。

メモリ

ELVMは24ビットアドレスのメモリ空間を持ち、各アドレスには24ビットの数値を格納できます。 メモリもペアを使って表現しますが、今度はリストではなく2分木を使います。

メモリ全体は高さ24の完全2分木になります。メモリを参照するときはアドレスを1ビットずつ見ていき、0なら左の子、1なら右の子を辿っていきます。メモリに値を格納するときは、根から対象アドレスの経路にあるノードのみが書き換えられ、他のノードは再利用されるのでそれほど効率は悪くありません。関数型データ構造というやつですね。

ちなみに初期化時のメモリは左の子と右の子が同じノードを指すDAGになっていて、値が書き込まれた部分だけが本当の2分木になります。多くのプログラムはメモリを目一杯使わないので、これでUnlambdaインタプリタの消費メモリ量を節約できます。

前編のまとめ

今回はELVM Unlambdaバックエンド実装の下準備として、様々なデータ構造を関数のみを使って実現する方法を解説しました。inc関数の処理を詳しく見ることで、すべてが関数であるUnlambdaでプログラミングするときの雰囲気を感じていただけたと思います。

明日の後編ではいよいよUnlambdaバックエンドの実装を見ていきます。

*1:これはUnlambdaの組み込み関数 k そのものです。