SECDV Schemeを実装する - ヒープがサポートすべき型の洗い出し

ちょっと考えたけど、vectorとpairだけ先行実装するよりも、最初から全部の型を用意してしまった方が簡単そうな気がしてきた。というわけで、型階層を設計して実装すべき型を洗い出す。
(SECDVをホストSchemeのヒープシステムで動かしたり、これから実装していくようなfixnumヒープエミュレータ上で動かすことには意義があるが、pairやvectorだけをエミュレートする環境には単に需要が無い。)

図の左端、グレー地にしている部分が、R7RS Schemeで求められている型となる(R7RS 3.2 Disjointness of types)。ただ、これらの述語(プレディケート; 型判別のための手続き)を全て単一の型として実装する必要は無い。例えば、boolean?はtrue?とfalse?に分割すれば、(define (boolean? x) (or (true? x) (false? y)))と定義できる。true?やfalse?はR7RSには無く、SECDVの独自拡張ということになる。(単に (define (false? x) (eq? x #f))だし。)
型は、ポインタを含まない型であるZone0、Zone1とポインタを含みGCが追跡する必要がある(= マークビットを含む必要がある)ヒープオブジェクトに分割する。
Zone0オブジェクトは、実体がシステム上で唯一であるようなオブジェクトに使用する。例えば、eof-objectは何種類も必要無いため、特定のfixnumを1つ割り当てれば十分ということになる。null?は専用のオブジェクトとなる。Schemeでは、空リストは独立した型/実体として扱うのが普通で、リストの拡張とはしていない。
Zone1オブジェクトは、実体が整数で識別されなければならないオブジェクトに使用する。今回は"短い整数"を意味するfixnumをZone1に含めている。charはchar→integer手続きの結果となる整数で識別できる。...fixnumをココに入れたら"fixnum以外のオブジェクトをfixnumで表現するにはどうすれば良いの？"問題が生じるが、適当に切り詰めるか拡張すれば良い。今回はホストSchemeのfixnumを2個連結してオブジェクトを表現するためのfixnumとして使用することにした。
ヒープオブジェクトは更にポインタ追跡が必要なものと、ポインタ追跡が必要ないものの2種類に分けられる。
number?オブジェクトは、intptrnum?、flonum?、bignum?に分割できる。今回はratnumやcomplexは一旦スキップする。intptrnum?は今回のSECDVに固有のもので、ポインタを格納するのに十分な長さの整数を表現する。一般的な多倍長整数であるbignum?と違ってそれなりのパフォーマンスが要求され頻出なので今回は分けてみることにした。
symbol?はちょっと悩みどころで、どうせfixnumで表現できないような個数のシンボルをinternすることは無いので、オープンアドレスなハッシュとしてZone1オブジェクトに入れてしまうという手も有るような気がしている。ヒープオブジェクトとするとuninternedなシンボルを表現する余地も生まれるが、シンボル1つあたりのオーバヘッドは増加する(し、指されているオブジェクトのマークビットを立て、sweep処理でvisitするコストがGC毎に掛かる)。
simple-struct?はnmoshでも使用しているvector?が成立しないベクタで、構造体の表現に使用する。Scheme標準の型では、portとdefine-record-typeした型で必要になる - ベクタをつかってportを表現すること自体は可能だが、"R7RS 3.2 Disjointness of types"にあるように、port?が成立するオブジェクトではvector?が成立してはいけないということになっている。このため、"vector?が成立しないがベクタ同等に扱えるオブジェクト"を別に用意する必要がある。
今回、最初の実装ではstring、bignum、bytevectorやflonumはホストSchemeの手続きをそのまま使用する。このため、ヒープオブジェクトで使用する"ポインタ"は"ホストSchemeオブジェクトを格納したベクタのインデックス"で表現されることになる。今回ターゲットにしているBASIC等の簡易言語にはポインタが無いが、そこで使用される表現に非常に近いものとなる。