>>604
マークフラグは別テーブルでできると思う。

>>606
603じゃないけど
typedef struct _cell {
　struct _cell *car;
　struct _cell *cdr;
} cell;
#define atomp(p) (1&(p))
#define cellp(p) !atomp(p) // pairp
#define car(p) (p)->car
#define cdr(p) (p)->cdr

数値を即値(30bit)にするとかの場合はもう1bit使って、
#define fixnump(p) (3&(long)(p)==3)
#define fixnum_value(p) ((long)(p)>>2)
#define make_fixnum_value(p) (cell *)(((p)<<2)|3)
とか。