型付ポインタ

2014年、明けましておめでとうございます。
新しい年になりましたので、早速Lispインタプリタを実装始めてみました。
実装にはC言語を利用しています。

ポインタの話

Lispは動的型付言語なのでポインタに型を持たせる必要があります。
現在の計算機だと物理アドレスやOSの仮想アドレスに
型が無いのは仕方ないですが、
残念ながらC言語のポインタにも実行時型情報は付きません。

Lispオブジェクトの組み込み型は多くても数十程度なので、
アドレス値の一部を利用して型情報を埋め込みましょう。
ついでにGC用のマーカーを1bit入れておいています。

static_assert( sizeof(void*) == 64 );
union LispPointer {
  void* p;
  struct { s64_t int64 : 62; };
  struct { u64_t uint64 : 62; };
  struct {
    u64_t addr : 60;
    u8_t type : 3;
    u8_t flag : 1;
  };
};

const union LispPointer LP_NIL = { NULL; };

#define LP_ADDR(p) ((void*)(p.addr << 4))
#define LP_FLAG(p) (p.flag)
#define LP_TYPE(p) (p.type)

#define LP_TYPE_WORD 1
#define LP_TYPE_CONS 0
#define LP_TYPE_SYMBOL 2
#define LP_TYPE_MISC 4
#define LP_TYPE_FREE 6

#define LP_IS_NIL(p) (p==LP_NIL)
#define LP_IS_WORD(p) (p.type&LP_TYPE_WORD)
#define LP_IS_PAIR(p) (!LP_IS_NIL(p) && p.type==LP_TYPE_CONS)
#define LP_IS_SYMBOL(p) (p.type==LP_TYPE_SYMBOL)
#define LP_IS_MISC(p) (p.type==LP_TYPE_MISC)
#define LP_IS_FREE(p) (p.type==LP_TYPE_FREE)

struct LispCell {
  union LispPointer car, cdr;
};

WORDは良く使う型なので、埋め込みで使えるようにしています。
ただし型チェック用のビットとGC用のビットで2bit使うので、62bit整数型になります。
最大値と最小値が少し減るのでオーバーフローには注意です。
最終的にはCommon Lisp同様bignumサポートする想定です。

参照先のメモリセルですが、64bitマシン想定で、
アドレス領域は16バイトアライメントとして考えています。
その際に下位4bitが空くため、型チェック用に利用しています。

typeは3bitにしていますが、必要そうならあと1bit追加するかもしれないです。
その際、typeを1bit増やして32バイトアライメントにするとか、
GC用のbitを廃止してMark&SweepからCopy方式に切り替えるなど、
やり方が色々あるのでどうしようかというところです。

とはいっても、最初からアロケータ&GCに凝りすぎると、
いつまでたっても処理系が完成しなくなってしまうので、
実行時効率よりも実装しやすさを優先する予定です。

最終的な設計としても、
ユーザ側でGCを実装できるような仕様にする予定です。