iroriの日記スマートフォン用の表示で見るiroriの日記この広告は、90日以上更新していないブログに表示しています。VMの実行をシミュレートするUnlambdaプログラムを構成するかを解説します。coreまとめ実装方針まずいくつかのコンセプトを説明します。実行中のVMの「状態」を表すデータ構造を定義します。getc]という形をしています。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_dataの3つの関数を順に呼んでいます。プログラム全体は``<core><text><data>となり、coreにtextとdataを適用した形になります。IR形式の命令列をUnlambdaの関数へとコンパイルして出力します。ELVMのコード領域の表現はちょっと変わっていて、基本ブロック内の複数の命令がひとつのPC(プログラムカウンタ)に入っています。fnとすると、あるVMの状態vmから基本ブロック実行後の状態vm'を得る関数は以下のように書けます。fnの合成関数)を生成して、プログラム全体はそれらの関数のリストとして出力します。Coreに渡されると2分木に展開され、メインループで使用されます。基本ブロックのコンパイル基本ブロックのコンパイルはunl_emit_chunk関数で行います。f1の順で書き出したいのでまずリストを反転しています。f1)))という形になります。f(g(x))になります。IRの命令ひとつをUnlambdaの関数に変換して出力します。A(レジスタAの値を文字として出力)という命令がどのようにコンパイルされるか見てみましょう。命令はVMの状態を引数にとり、新しいVMの状態を返す関数としてコンパイルするのでした。putc命令はVMの状態を変更しないので、文字を出力したら渡されたVMをそのまま返せば良さそうです。coreに含まれるライブラリ関数のひとつlib_putcにレジスタの値を渡せば出力してくれます。いうわけで、出力すべき関数の輪郭はこうなります。組み込み関数kは引数2つを取り1つ目を返すので、この式全体はvmを返すことになります*1。regA))ライブラリ関数はVM構造体に含まれていて、lib_putcはVM構造体をリストとして見たとき9番目の要素になります。regAというのはレジスタAの値で、レジスタリストはVM構造体の先頭要素、レジスタAはレジスタリストの2番目の要素です。したがって上の式は以下のように書き換えできます。vm))))nthはリストの0から数えてn番目を取り出す関数です。->car)と書けます。lstにcdrをn回適用した後、carをとる操作です。->carは"後置car"で、単なるkコンビネータです。nthを展開すると、上の式は以下のようになります。->car)))carやcdrなどの基本的な関数、24以下の数のチャーチ数などはunl.cの先頭付近にUnlambdaのコード片として定義されています。あとはこの式からラムダ抽象を取り除いて(Un-lambdaして)やれば、Unlambdaの組み込み関数のみを使った形にできます。ラムダ抽象を取り除くラムダ式をUnlambdaの式に変換するには、前編の冒頭で紹介した記事にも記載されている4つの規則を適用します。Mどうしてこうなるのか、という説明はこちらをどうぞ。これを先ほどの式に適用して変数vmに対するラムダ抽象を取り除き、カッコをUnlambdaの適用演算子`に置き換えると以下のようになります。コメントはunl.cで該当部分を出力している関数です。c(n)などは実際にはunl.c先頭付近で定義されているskiのみからなる文字列が出力されます。unl.cではラムダ式の生成→ラムダ抽象の除去というステップを経ずに直接コードを生成しているため読みにくいですが、上で考えたラムダ式に対応する関数が出力されています。コード出力を例に説明しましたが、ほかの命令も似たような考え方でUnlambdaの関数にコンパイルできます(レジスタの書き換えとかちょっと面倒ですが)。データ領域のコンパイルtarget_unlに渡されるModule構造体のdataメンバには、メモリの初期値が0番地から順に入っています。unl_emit_data関数は各番地の値をUnlambdaでの数値表現(24要素のリスト)に変換し、Unlambdaのリストとして出力します。coreへの引数となり、初期化ルーチンによってメモリの2分木表現へと展開されます。coreunl_emit_core関数は固定の共通コードを出力します。共通コードはひとつの関数になっていて、unl_emit_textが出力した関数のリストとunl_emit_dataが出力したデータ領域のリストを引数に取り、以下の処理を実行します。putc用のライブラリ関数は単純な繰り返しが多いのでunl.c内で生成しています。それ以外の部分(5.5KB)はunlcore.hに文字列として書かれています。IRのプログラムをどのように実行するか解説してきました。ポイントをまとめると、Unlambdaではすべては関数、ペアやリストといったデータ構造も関数で表現する。数値は24要素のリストで表現する。メモリは2分木で表現する。破壊的書き換えはできないので、メモリに書き込むと新しい2分木が生成される。VMの命令は、VMの状態を引数にとり新しい状態を返す関数にコンパイルされる。して並べてみるといかにも遅そうですが、実際最初のバージョンはBrainfuckの10倍くらい遅くて、最適化してだいぶマシになりましたがまだBrainfuckより遅いです。終わるのに20日(!)かかりました。Unlambda以外の関数型esolangでバックエンドを作る際も、ここで紹介した考え方の多くは適用できるはずです。scriptバックエンド作者)の記事も参考になります。皆さんもぜひお気に入りのesolangでELVMバックエンドを作ってみて下さい。