UnlambdaでVMを実装する(後編)
Esolang Advent Calendar 2016 3日目の記事です。
今回は、前編で説明したデータ構造を使って、どうやってEsolang VMの実行をシミュレートするUnlambdaプログラムを構成するかを解説します。
実装方針
まずいくつかのコンセプトを説明します。
VMの状態
実行中のVMの「状態」を表すデータ構造を定義します。といっても単なるリストで、
[regs, memory, add, sub, eq, lt, load, store, putc, getc]
という形をしています。最初の要素regs
はレジスタの値のリストで、[PC, A, B, C, D, BP, SP]
の順に並んでいます。2番目の要素memory
は前編で説明したメモリを表す2分木です。3番目以降の要素は「ライブラリルーチン」で、コンパイルされたコードはこれらの関数を呼び出して計算を実行します。(前編で説明したincなどはサイズが小さいので、コンパイルするときに毎回埋め込んでいます。)
命令の実行
VMは命令を実行するごとに、レジスタやメモリの状態が変化していきます。しかし関数型言語であるUnlambdaにはデータ構造を破壊的に書き換える方法は存在しません。 そこで今回の実装では、VMの各命令を「VMの状態を引数に取り、命令実行後の新しいVMの状態を返す」関数として実現します。
メインループ
プログラムの実行は初期状態のVMからはじめて、以下を繰り返すことで実現できます。
前回、メモリは2分木で表現されていることを説明しましたが、プログラムもPCの値から関数へのマッピングと考えられるので、メモリと同様に2分木で表現します。(データ領域のメモリとは別の木になります。)命令のフェッチはメモリのロードと同じように、この2分木をPCのアドレスを使って辿ることで実現できます。
プログラムの中でジャンプ命令が実行されると、PCの値が書き換わったVMの状態が返ってくるので次のループではジャンプ先のPCが参照されます。そうでない場合は、2番目のステップでPCに1が足されているので直後の命令が実行されます。
ELVMバックエンドの作成
それでは、実際のELVMバックエンドのコードを見ていきます。
プログラム全体の構造
Unlambdaコード生成の起点となる関数がtarget_unlです。
最初のunl_emit_tick(2)
は関数適用演算子`
を2つ出力するだけです。その後unl_emit_core
, unl_emit_text
, unl_emit_data
の3つの関数を順に呼んでいます。つまりプログラム全体は``<core><text><data>
となり、coreにtextとdataを適用した形になります。
命令をUnlambdaにコンパイルする
unl_emit_text関数はELVM IR形式の命令列をUnlambdaの関数へとコンパイルして出力します。
ELVMのコード領域の表現はちょっと変わっていて、基本ブロック内の複数の命令がひとつのPC(プログラムカウンタ)に入っています。基本ブロック内の命令列I1, I2, ..., In
をそれぞれ関数にコンパイルしたものをf1, f2, ..., fn
とすると、あるVMの状態vm
から基本ブロック実行後の状態vm'
を得る関数は以下のように書けます。
vm' = fn(...(f2(f1(vm))))
Unlambdaバックエンドでは基本ブロックごとにひとつの関数(上のf1, f2, ..., fn
の合成関数)を生成して、プログラム全体はそれらの関数のリストとして出力します。このリストがVM Coreに渡されると2分木に展開され、メインループで使用されます。
基本ブロックのコンパイル
基本ブロックのコンパイルはunl_emit_chunk関数で行います。ELVM IR命令I1, I2, ..., In
は連結リストとして引数instに渡されますが、出力はfn, ..., f2, f1
の順で書き出したいのでまずリストを反転しています。それぞれの命令のコンパイルはunl_emit_op
関数で行い、全体の式は
compose(fn, (..., compose(f2, f1)))
という形になります。composeは関数を合成する関数で、compose(f,g)(x) = f(g(x))
になります。
命令のコンパイル
unl_emit_op関数はELVM IRの命令ひとつをUnlambdaの関数に変換して出力します。
例として、putc A
(レジスタAの値を文字として出力)という命令がどのようにコンパイルされるか見てみましょう。
命令はVMの状態を引数にとり、新しいVMの状態を返す関数としてコンパイルするのでした。putc命令はVMの状態を変更しないので、文字を出力したら渡されたVMをそのまま返せば良さそうです。文字の出力は、VM coreに含まれるライブラリ関数のひとつlib_putcにレジスタの値を渡せば出力してくれます。
というわけで、出力すべき関数の輪郭はこうなります。
組み込み関数k
は引数2つを取り1つ目を返すので、この式全体はvm
を返すことになります*1。
λvm. ((k vm) (lib_putc regA))
ライブラリ関数はVM構造体に含まれていて、lib_putc
はVM構造体をリストとして見たとき9番目の要素になります。また、regA
というのはレジスタAの値で、レジスタリストはVM構造体の先頭要素、レジスタAはレジスタリストの2番目の要素です。したがって上の式は以下のように書き換えできます。
λvm. ((k vm) ((nth 8 vm) (nth 1 (car vm))))
nth
はリストの0から数えてn番目を取り出す関数です。
(nth n lst)
はnのチャーチ数c(n)を使うと、((c(n) cdr lst) ->car)
と書けます。つまりlstにcdrをn回適用した後、carをとる操作です。->car
は"後置car"で、単なるkコンビネータです。nth
を展開すると、上の式は以下のようになります。
λvm. ((k vm) (((c(8) cdr vm) ->car) ((c(1) cdr (car vm)) ->car)))
carやcdrなどの基本的な関数、24以下の数のチャーチ数などはunl.cの先頭付近にUnlambdaのコード片として定義されています。あとはこの式からラムダ抽象を取り除いて(Un-lambdaして)やれば、Unlambdaの組み込み関数のみを使った形にできます。
ラムダ抽象を取り除く
ラムダ式をUnlambdaの式に変換するには、前編の冒頭で紹介した記事にも記載されている4つの規則を適用します。
規則1: λx.(M N) ≡ ((s λx.M) λx.N) 規則2: λx.x ≡ i # 式M の中で x が自由変数として現れないとき 規則3: λx.M ≡ (k M) 規則4: λx.(M x) ≡ M
どうしてこうなるのか、という説明はこちらをどうぞ。
これを先ほどの式に適用して変数vm
に対するラムダ抽象を取り除き、カッコをUnlambdaの適用演算子`
に置き換えると以下のようになります。コメントはunl.cで該当部分を出力している関数です。
``s # case PUTC: k # case PUTC: ``s # unl_lib_putc ``s # unl_lib_putc -> unl_emit_lib `c(8) # unl_lib_putc -> unl_emit_lib cdr # unl_lib_putc -> unl_emit_lib `k # unl_lib_putc -> unl_emit_lib ->car # unl_lib_putc -> unl_emit_lib ``s # unl_emit_value -> unl_getreg -> unl_nth_begin ``s # unl_emit_value -> unl_getreg -> unl_nth_begin `k # unl_emit_value -> unl_getreg -> unl_nth_begin `c(1) # unl_emit_value -> unl_getreg -> unl_nth_begin cdr # unl_emit_value -> unl_getreg -> unl_nth_begin car # unl_emit_value -> unl_getreg `k # unl_emit_value -> unl_getreg -> unl_nth_end ->car # unl_emit_value -> unl_getreg -> unl_nth_end
car, cdr, c(n)などは実際にはunl.c先頭付近で定義されているskiのみからなる文字列が出力されます。unl.cではラムダ式の生成→ラムダ抽象の除去というステップを経ずに直接コードを生成しているため読みにくいですが、上で考えたラムダ式に対応する関数が出力されています。
以上 putc A
のコード出力を例に説明しましたが、ほかの命令も似たような考え方でUnlambdaの関数にコンパイルできます(レジスタの書き換えとかちょっと面倒ですが)。
データ領域のコンパイル
target_unl
に渡されるModule
構造体のdata
メンバには、メモリの初期値が0番地から順に入っています。unl_emit_data関数は各番地の値をUnlambdaでの数値表現(24要素のリスト)に変換し、Unlambdaのリストとして出力します。このリストはVM coreへの引数となり、初期化ルーチンによってメモリの2分木表現へと展開されます。
VM core
unl_emit_core関数は固定の共通コードを出力します。共通コードはひとつの関数になっていて、unl_emit_text
が出力した関数のリストとunl_emit_data
が出力したデータ領域のリストを引数に取り、以下の処理を実行します。
固定コードは全体で50KBほどで、そのうちgetc, putc用のライブラリ関数は単純な繰り返しが多いのでunl.c内で生成しています。それ以外の部分(5.5KB)はunlcore.hに文字列として書かれています。
まとめ
この記事では前後編の2回に分けて、UnlambdaでELVM IRのプログラムをどのように実行するか解説してきました。ポイントをまとめると、
- Unlambdaではすべては関数、ペアやリストといったデータ構造も関数で表現する。
- 数値は24要素のリストで表現する。
- メモリは2分木で表現する。破壊的書き換えはできないので、メモリに書き込むと新しい2分木が生成される。
- VMの命令は、VMの状態を引数にとり新しい状態を返す関数にコンパイルされる。
こうして並べてみるといかにも遅そうですが、実際最初のバージョンはBrainfuckの10倍くらい遅くて、最適化してだいぶマシになりましたがまだBrainfuckより遅いです。ELVMのセルフホストのテスト (check_selfhost.sh) が終わるのに20日(!)かかりました。
Unlambda以外の関数型esolangでバックエンドを作る際も、ここで紹介した考え方の多くは適用できるはずです。ELVMバックエンド作成チュートリアルとして、@hak7a3さん(TeXバックエンド作者)の記事や@Linda_ppさん(Vim scriptバックエンド作者)の記事も参考になります。皆さんもぜひお気に入りのesolangでELVMバックエンドを作ってみて下さい。