SECDV Schemeを考える - VM命令セット
前回( http://d.hatena.ne.jp/mjt/20170505/p1 )はVMで使用するレジスタと実行時の用法を考えた。今回はVMの根幹になるVM命令セットを決める。
今回のVMのコンセプトとして:
- ゲームのスクリプティングに使うので多少は効率的 - 少くとも元のSECDR Scheme程度には効率的なはず
- BASICやシェルスクリプトでVMを実装する気になる程度には単純 - コンパイラは多少は複雑で良い(どうせSchemeで実装するため)
というものがあるので、効率性のためにいくらか複雑になってしまう点は諦めることにした。
23命令..多いのか少いのかは何とも言えない。
線型に引数スタックを構築するSECDR Schemeと異なり、SECDVでは引数スタックをFRAME命令を使用して明示的に確保する必要がある。例えば、"(proc a b c d)"のような呼び出しは、引数4つを格納するために"FRAME 4"命令で始まることになる。
RECV/RECVM命令は、CALLまたはCALLM命令によって呼び出された先で引数が格納された S レジスタから環境 E に移し替る。SECDR SchemeではAP/TAP命令によって直接環境 E が生成される( https://gist.github.com/okuoku/3f2e469497bbf12575e8#file-gistfile1-scm-L83 )が、SECDVでは呼び出しプロトコルが複数存在する( http://d.hatena.ne.jp/mjt/20170505/p1 )ため、calleeの先頭で明示的に環境 E を構築させる。
BINDおよびLEAVE命令はlet構文を直接サポートするためのもので、クロージャ/プリミティブの呼び出しを行わない点が異なる。対応する命令はSECDR Schemeには存在しない。
CALL/CALLM/TCALL/TCALLM命令はVレジスタにロードされているオブジェクトをS上のフレームを使用して呼出す。Tail Callは、Dumpレジスタにステートをpushしないことで実現する。
RET命令はDumpレジスタに保存されていたS、E、Cの各レジスタを復元する。これはSECDR Schemeと同様 https://gist.github.com/okuoku/3f2e469497bbf12575e8#file-gistfile1-scm-L111 。
JMP/BRV命令はアドレスを指定したジャンプになっている。SECDR Schemeでは、VMの実行するコードはS式であり、かつ、分岐はクロージャの呼出である(= 元のSchemeソースと表現力が同等である)ため無条件ジャンプは不要となっている(SECDR Schemeでは、call/ccはVM命令でない)。SECDVではVMの実行するコードをvectorとしたため、コードを1列に並べる必要がある。コードを1列に並べるには、どうしても"読み飛ばし"によって不連続なコードフローを表現する手段が必要になる。
LD命令は環境 E から値をロードする。これはSECDR Schemeと同様( https://gist.github.com/okuoku/3f2e469497bbf12575e8#file-gistfile1-scm-L68 )。可変長引数の場合の変換はRECVM命令で事前に行われるため、SECDR SchemeのTLD命令に相当する命令は存在しない。
グローバル変数をロードするためのLDG命令はシンボル1つだけを取るSECDR Scheme( https://gist.github.com/okuoku/3f2e469497bbf12575e8#file-gistfile1-scm-L74 )に比べて、モジュール番号も取るように変更してみた。本当に必要なのかどうかはなんとも言えない。
定数ロードはLDC(命令ストリーム付属ライブラリからのロード)、LDI(命令ストリームからの直接ロード)、LDN(未定義値のロード)、LDNN(値の無効化)と4種類も用意している。LDNおよびLDNN命令は、set!の直後に未定義値を返すために使用される。2種類存在するのはwhen/unless構文がR7RSでは未定義値を1つ返す必要があるため。nmoshでは未定義値としてゼロ個の値を戻すため未定義値の処理も両方配慮する必要がある。(1個の未定義値についてはLDC命令で代替できるが、LDC命令は多値を直接設定できないためゼロ個の値をワンアクションで返すことができない -- このため、一種のintrinsicとしてVM命令を用意してしまうことにした)
LDV命令は、Vレジスタに多値をロードするために使用される。というか、Vレジスタに多値を格納するためには、基本的に一旦引数スタックに内容を積みLDV命令でロードするしかなく、それ以外ではVレジスタは1値を指すことになる。SECDVなんて名前にしておいて。。LDNN命令は"FRAME 0; LDV"の2命令と等価となる。
ストア命令はST命令とMOV命令の両方が存在する。ST命令は環境 E を変更し、MOV命令は引数スタックを変更する。SECDR SchemeではMOVに相当する命令は無く、PUSHCONS命令( https://gist.github.com/okuoku/3f2e469497bbf12575e8#file-gistfile1-scm-L135 )を使用して引数スタックを線型に構築する。MOV命令は通常CALLやLDの直後に来るため、CALL+MOVのような合成命令を用意した方が効率的かもしれない。
NOP命令は冷静に考えてみると不要な気がする。
SECDR SchemeではVMの各レジスタを継続として保存する命令SAVE( https://gist.github.com/okuoku/3f2e469497bbf12575e8#file-gistfile1-scm-L137 )が存在するが、SECDVでは仕様から省いた。その替わり、プリミティブを通常のSchemeプリミティブとVMステートを直接参照/変更できるものの2つに分け、細かい処理はプリミティブとして実装できるように配慮する。
アセンブラ構文
というわけで、これらの命令を処理する
を今後は用意していく。とりあえず、Scheme上でVMを試作するにあたって、いきなりfixnumのvectorを命令ストリームとして採用するのはコンパイラのデバッグ上面倒なので、S式で表現できるアセンブラ入力構文を考える。fixnumのvectorを使用する場合は逆アセンブラも作る方が良さそうだが、最初はそこをサボりたい。
S式を使用したアセンブラ構文としては、Web Assemblyが提案してちょっと話題になった:
This format will use S-expressions (avoiding syntax bikeshed discussions) to express modules and definitions while allowing a linear representation for the code in function bodies.
実際にこのS式アセンブリの(OCamlで書かれた)処理系 https://github.com/WebAssembly/spec/tree/2fa62739e6dc81797bbbac3eb9028b368b55bf42/interpreter が有り、https://github.com/AndrewScheidecker/WAVM/blob/ed25c1517a19a73df7059dadd8a6450cd897c41c/Test/fuzz/loop.wast 等に実際のコードも有る。
Web AssemblyのS式表現では、命令ストリーム中にラベルを置くことはできず、blockやif、loopとして明示的に区切る必要がある。SECDVのアセンブラがこの表現で十分なのかは検討する必要が有りそう。
