scheme VMをCで書く

オブジェクトの表現

二つの型(vm_data型とvm_obj構造体)を使っている．

vm_data型にはprimitiveな型や定数，そしてオブジェクトへの参照を入れる． 保守的なGCとか大変そうなので，1ワードの中にタグを含めることにした． 下位ビットで判定する． 単純にtypedef intptr_t vm_data;としている．

整数       ....00  上位30bitで符号付き整数を表現
文字       .00000  上位8bitで表現
true       .00101
false      .01001
nil        .01101
undefined  .10101
ボックス   ....10  vm_dataへの参照
vm_obj     ....11  vm_objへの参照

vm_obj構造体は，その他もろもろのオブジェクトを入れる． こんな感じで，文字列，シンボル，クロージャ，ペア，スタックオブジェクト を表現する．

struct vm_obj
{
	unsigned char tag;
	union{
		char *string;
		char *symbol;
		vm_data *closure;
		struct {
			vm_data *p;
			int size;
		} stack;
		struct {
			vm_data *car;
			vm_data *cdr;
		} pair;
	} u;
};

実行

コンパイラまでは，以前と同じものを使う． とりあえず，パイプで受け渡しするようにしている． compile.scmはschemeで書いたscheme->バイトコードのコンパイラ， vmはCで書いたVM． 不格好だが，こんな感じで実行する． replはまだない．

echo '(+ 1 2 3)' | ./compile.scm | ./vm
あるいは，
cat source.scm | ./compile.scm | ./vm

コールフレーム

可変な引数をとる必要があることから引数のサイズをスタックに積むか，もしくはもう一つ レジスタを増やすかということで，後者を選択した． 可変な引数をとれるようになった． 一番下にend-of-frameというタグを積んでいるのは，スタックをヒープに退避させるときに 戻りアドレスを調べて必要があると思ったから．

|  引数1                | < argp
|   :                   |
|  引数n                |
|  前のフレームポインタ | < frame pointer
|  前のargポインタ      |
|  前のclosure          |
|  戻りアドレス         |
|  TAG: end-of-frame    |
|-----------------------|

組み込み関数

組み込み関数を，どこまでコンパイル時に展開するのかを決めないといけない． 今は，引数が1つだけの関数であれば直接accumulatorに対して命令を実行して， 2引数以上の場合は通常の関数呼び出しと同じ手順(スタックにすべての引数を積み， closureオブジェクトを作る)を踏んでいる．

最後に今動くコードの例を載せておく． これからはなにかかっこいいGCを実装したい．

(letrec ([reverse (lambda (in out)                                             
                   (if (null? in) 
                    out 
                    (reverse (cdr in) (cons (car in) out))))]
         [makelist (lambda (x) 
           (if (= x 0)
            (cons 0 '())
            (cons x (makelist (- x 1)))))])
 (reverse (quote (1 #t a b c (1 2 "helloworld"))) ()))

Tweet