TinySCHEME のソースを読む -1 セルの構造

TinySCHEME は scheme 実装の一つで、コード量は 4千行程度である。R5RS の大部分の仕様が実装されており、学習のためにソースを読む機会があったので記録しておく。

TinySCHEME のソースはインデントが統一されていなかったり、数字と演算子の間の空白が極端に少なかったりと、可読性はあまり高いとは言えないので、私は整形してから読んだ。
文中、ファイル名を明示せず行数が出てくるものは全て scheme.c のものである。それ以外のファイルについてはファイル名を明示してある。

TinySCHEME のソースを読む -1　セルの構造
TinySCHEME のソースを読む -2　シンボル、環境
TinySCHEME のソースを読む -3　TinySCHEME の処理エンジン
TinySCHEME のソースを読む -4　トップレベルからの処理の流れ
TinySCHEME のソースを読む -5　define の例
tsdbg TinyScheme 用デバッグ extension

セル

ischeme-private.h の 44 行目からセルの定義がある。

struct cell {
    unsigned int _flag;
    union {
        struct {
            char   *_svalue;
            int   _length;
        } _string;
        num _number;
        port *_port;
        foreign_func _ff;
        struct {
            struct cell *_car;
            struct cell *_cdr;
        } _cons;
    } _object;
};

_flag により、_object ユニオンのどの要素を使うかが決定される。

_flag には、110 行目から定義がある enum scheme_types と:

enum scheme_types {
    T_STRING=1,
    T_NUMBER=2,
    T_SYMBOL=3,
    T_PROC=4,
    T_PAIR=5,
    T_CLOSURE=6,
    T_CONTINUATION=7,
    T_FOREIGN=8,
    T_CHARACTER=9,
    T_PORT=10,
    T_VECTOR=11,
    T_MACRO=12,
    T_PROMISE=13,
    T_ENVIRONMENT=14,
    T_LAST_SYSTEM_TYPE=14
};

132 行目から define されている以下のマクロが入る：

    #define T_SYNTAX      4096
    #define T_IMMUTABLE   8192
    #define T_ATOM       16384

主要なフラグで、かつ T_STRING のようにあからさまに意味が明白なものを省いて簡単に説明すると、
T_PROC は opdefines.h で定義されているオペレーションで、かつ名前を持つものに対して付与される。round, +, -, *, /, car, cdr, cons などである。
T_PAIR はコンスセルを表す。
T_CLOSURE は、コード（プログラム）と環境がそれぞれ car, cdr に格納されたセルを表す。ユーザ定義関数や lambda 式は T_CLOSURE で表される。
T_CONTINUATION は継続を表すものだろうが良く調査していない。
T_FOREIGN は外部ライブラリで定義された関数に対して付与される。(TinySCHEME に外部ライブラリを読み込む機能があり、C で書いた処理を scheme から呼び出すことが出来る)
T_PROMISE については未調査、
T_ENVIRONMENT は環境を表す。

T_SYNTAX は if や define, lambda などのシンボルに対して付加される。
T_IMMUTABLE は変更不可能なセルに対して付加される。
T_ATOM は、そのままの意味で、アトムのセルに対して付加される。

尚、cell へのポインタとして、以下の型が定義されている：

    typedef struct cell *pointer;

セルの確保

557 行目の alloc_cellseg() で確保される。セルは 5000 個の連続したセルを一つの単位とし、確保される。この5000個のセルの単位をセグメントという。
セグメントは cell_seg という配列で管理される。起動直後、セグメントは 3 つ (= 15,000セル）用意されるが、必要に応じて最大 10 個まで拡張される。

新しいセルが必要な場合、745 行目の get_cell() が呼ばれ、まだ利用されていないセルを返す。

もしセグメントに十分なセルが無い場合、get_cell() はガベージコレクションを試みるが、それでも足りなさそうな場合( gc を行っても、現在のセグメント数 * 8 より、空きセルが少ない場合）は新たなセグメントが allocate され、cell_seg に代入される。
cell_seg[] に代入される各セグメントは、アドレス順にソートされる。これは、TinySCHEME の vector が連続したセル領域を（配列として、場合によってはセグメントをまたいで）必要とするためである。