UnlambdaでVMを実装する（後編）

ELVM Unlambda esolang

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からはじめて、以下を繰り返すことで実現できます。

  • 現在のVMの状態におけるPCレジスタの値を使ってコード領域を参照し、対応する関数を得る
  • PCに1を加えた新しい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が出力したデータ領域のリストを引数に取り、以下の処理を実行します。

  • コードと初期データを2分木に展開する
  • レジスタリスト、メモリ、ライブラリルーチンを含む最初のVM構造体を作る
  • VMの初期状態からメインループを開始する

固定コードは全体で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バックエンドを作ってみて下さい。

*1:Haskellなどの文法に馴染みがないと読みにくいと思いますが、第１引数がvmで第２引数が (lib_putc regA) です。