EmacsLispのデータ構造

Schemeインタプリタを作成する流れになったので色々処理系を見て回っていたのだが、EmacsLispのデータ構造の取り方が一番良い様に思えた。XSLisp等で行っている方法は極限までリソースが無い状況では有効だと思えるが、それ以外の場面ではあまり有効とは思えない。「入力システムが動くScheme処理系」というのがそもそもの動機なので、GUIが動く程度のリソースは有ると仮定して良いと思う。ここではメモも兼ねてEmacsLispのデータ構造の取り方について書いてみることにする。

EmacsLispのデータ構造の定義はsrc/lisp.hに集約されている。一番重要なのは union Lisp_Object である。その定義を見てみよう。以下lisp.hより抜粋。

/* These are default choices for the types to use.  */
#ifdef _LP64
#ifndef EMACS_INT
#define EMACS_INT long
#define BITS_PER_EMACS_INT BITS_PER_LONG
#endif
#ifndef EMACS_UINT
#define EMACS_UINT unsigned long
#endif
#else /* not _LP64 */
#ifndef EMACS_INT
#define EMACS_INT int
#define BITS_PER_EMACS_INT BITS_PER_INT
#endif
#ifndef EMACS_UINT
#define EMACS_UINT unsigned int
#endif
#endif

#ifndef GCTYPEBITS
#define GCTYPEBITS 3
#endif

/* These values are overridden by the m- file on some machines.  */
#ifndef VALBITS
#define VALBITS (BITS_PER_EMACS_INT - GCTYPEBITS)
#endif


typedef
union Lisp_Object
  {
    /* Used for comparing two Lisp_Objects;
       also, positive integers can be accessed fast this way.  */
    EMACS_INT i;

    struct
      {
	enum Lisp_Type type : GCTYPEBITS;
	EMACS_INT val  : VALBITS;
      } s;
    struct
      {
	enum Lisp_Type type : GCTYPEBITS;
	EMACS_UINT val : VALBITS;
      } u;
  }
Lisp_Object;

32bit環境の場合、GCTYPEBITS == 3, VALBITS == 29になる。つまり、Lisp_Objectは 29bit の値と 3bit の型情報で成り立っているという事だ。enum Lisp_Typeは次のように定義されている。型情報は 3bit しか持てない為、8種類の型までしか現せない。次に注目したいのは、次の4つのマクロである(lisp.hより抜粋)。

#define TYPEMASK ((((EMACS_INT) 1) << GCTYPEBITS) - 1)
#define XTYPE(a) ((enum Lisp_Type) (((EMACS_UINT) (a)) & TYPEMASK))\
#define XSET(var, type, ptr)					\
    (eassert (XTYPE (ptr) == 0), /* Check alignment.  */	\
     (var) = ((EMACS_INT) (type)) | ((EMACS_INT) (ptr)))
#define XPNTR(a) ((EMACS_INT) ((a) & ~TYPEMASK))

TYPEMASKについては分かるだろう。XTYPE(a)については、a にはLisp_Object型を渡って来るので下位 3bit、つまり型情報を取り出している。同じくXPNTRは上位 29bitを取り出している。しかし、気になるのは "XPNTR" という名前で有る。PNTR !?。その謎は XSET で明らかになる。

XSETはまず、XTYPE(ptr)の下位3bitが 000 で有ることをチェックしている。XSETは次のように用いられる。

(in src/lisp.h)
#define XSETCONS(a, b) XSET (a, Lisp_Cons, b)

(in src/alloc.c)
Lisp_Object
pure_cons (car, cdr)
     Lisp_Object car, cdr;
{
  register Lisp_Object new;
  struct Lisp_Cons *p;

  p = (struct Lisp_Cons *) pure_alloc (sizeof *p, Lisp_Cons);
  XSETCONS (new, p);
  XSETCAR (new, Fpurecopy (car));
  XSETCDR (new, Fpurecopy (cdr));
  return new;
}

つまりまっさらのポインタがptrに渡され、その下位3bitが常に0で有るという事実は、「Emacsにおけるすべてのデータは8bitにアラインメントされている」という事を示している。そして空いた下位3bitを型情報を格納する為に使用しているという事だ。

ここまで分かるとLisp_Objectは「ポインタと型情報」を持った構造体で有るといえる。言い替えるとC版「スマートポインタ」じゃないですか。あのModern C++ Designとかでごにょごにょやっている。これを考えた＆Cでやっちゃうストールマン先生偉い。思い付いても誰もあんな大規模なソフトでやらないよぉ...

これをやるとCons CellがLisp_Object * 2で 8byte になったりしてメモリ節約になります。ただしまだGC用のデータを持たせる必要が有りそうですけど。GCについてはまだ何のアルゴリズムを使用するか決めてません。