S式の要素の実装方法を考える - Scheme VM を書く

経緯

C++ でVM を書きはじめたところ S式を統一的に扱う仕組みの必要性を感じたので考える。

前実装の反省点

即値/定数オブジェクトをサポートしなかったので数値計算などが遅い。
処理系内部で使うデータ構造（例：リスト、ベクタ）などを STL 互換のものにしてしまった。
- 内部構造もできる限り S式で取り扱った方がいろいろな場面で有利であることに気づいた。（例: quote / print）

S式の登場人物

number（即値）
char（即値）
vecor
string
symbol
pair
true （定数）
false （定数）
nil （定数）
eof （定数）
undefined （定数）
unbound （定数）

満たすべき要件

最小のオブジェクトは 32bit に納める
pair/vector に格納する場合は ScmObj などベースクラスのインスタンスとして入れる
即値と定数とポインタの混在
登場人物に関連する操作をまとめる
- マクロにしがちだが、なんとか手続きやテンプレートにしたい

迷い

C++ のクラス機能とどう折り合いをつけるか
- 全部構造体ベースという選択肢もゼロではない

Gauche が採用している手法

大先輩 Gauche の手法を調べる。

全てのオブジェクトは ScmObj (typedef struct ScmHeaderRec *ScmObj;) としてアクセスできる。

typedef struct ScmHeaderRec {
    ScmByte *tag;                /* private.  should be accessed
                                    only via macros. */
} ScmHeader;

僕の環境でこれは 32bit 。

このデータを整数として扱い、以下の判定でおおざっぱにオブジェクトの種類を分類する。

下位bit	型	メモ
00	pointer	pair やヒープに確保されたポインタを指す
01	fix num	サイズは30bit
010	charcter	サイズは29bit
0110	#f, #t, '(), eof-object, undefined
1110	pattern variable	マクロのexpandで使われているらしい
11	下位2bitをマスクするとScmClassへのポインタ	pair以外でヒープ確保されたオブジェクトは構造体の先頭にこのデータを持つ

下位4bit は必ずオブジェクト情報に使われることから new/malloc で allocate されるポインタは 2byte align 以上であることが必要。

ScmClassとは？
CとSchemeの双方から呼び出せるクラスシステム。
クラスを定義したり、インスタンス化したり、インスタンスの手続きを呼び出すことができる。

例えば文字列を表す ScmString も ScmClass の仕組みでビルトインクラスとして定義されている。
ただしクラスでは

ScmClassPrintProc print;
ScmClassCompareProc compare;
ScmClassSerializeProc serialize;
ScmClassAllocateProc allocate;

などの手続きが実装されているだけで

実際に文字列がどのように定義されるか？
文字列の作成

などは以下のように別の場所で定義される。

typedef struct ScmStringPointerRec {
    SCM_HEADER;  /* クラス情報 */
    int length;
    int size;
    const char *start;
    int index;
    const char *current;
} ScmStringPointer;

Gauche のクラスシステムの仕組みは

C++ のクラスの仕組み相当のもの
Scheme から動的にクラスを定義できる仕組み

の2つを含んでいるように見える。

ちなみにある ScmObj が string? を満たすかは以下のように判定される

下位2bit が 0 であること
- => ヒープに確保されたオブジェクトであることが分かる。
ScmObj->tag を取り出す
~~ScmClass Scm_StringClass 構造体の先頭から3byte目の1byte 分を tag として取り出す。~~→コメント欄参照
上記2つが等しいこと

Gauche の仕組みを調べて分かったこと

C++ のクラスの仕組みを使うと静的にしかクラスを定義できなくなる。
つまり Scheme から動的にクラスを作るみたいなことができなくなる。

正確には C で定義されたクラスと Scheme で定義されたクラスを一貫性を持って取り扱えなくなるのかな。
なので Scheme 側に Scheme で独自のクラスシステムを作ってそこだけで幸せに暮らすならこの手法をとる必要はない。

Mona の Scheme にクラスシステムが必要か

カーネルリソースを全てオブジェクトとしてマッピングしたいので必要。
ただし今は、どこのレイヤーでオブジェクトを実装するかが朧ろげにしか見えていない。

現時点での方針

オブジェクトで即値/定数/ヒープオブジェクトを混在させる方法は Gauche と同じ方法で実装する
Gauche の ScmClass 相当機能は機能を削って、C++ のクラス機能で実装する

String の実装を考えてみる

ScmObj としてアクセスされる String は

struct {
   SCM_HEADER;
   ScmString* str;
};

のように定義する。
String の実体は ScmString で、これは C++ のクラス

class ScmString : public ScmHeapObject

ベースクラスに ScmHeapObject を指定する。
ScmHeapObject ではオブジェクトの外部表現を返す手続きなど、各種オブジェクトに共通の操作のインターフェースが定義されている。

という感じで進めようと思う。
頭の中がずっともやもやしていたので2時間ほど時間をとって考えたらすっきりした。
もやもやを抱えながら他の実装をすると、実装に確信が持てず効率が悪いので今後はもやもやを発見したらすぐに対処しよう。