#define TAG_MASK 0x3
#define PAIR_TAG 0
#define FIXNUM_TAG 1
#define OBJECT_TAG 2

struct pair_t;
struct object_t;
struct vtable_t;

typedef union cell_t {
	struct pair_t* p;
	ptrdiff_t n;
	struct object_t* o;
} cell;

struct pair_t {
	cell car;
	cell cdr;
};

struct object_t {
	struct vtable_t* meta;
};

#define OBJECT_META struct vtable_t* meta

struct gc_stackroot {
	void** root;
	struct gc_stackroot* next;
};

extern struct gc_stackroot* gc_stack_roots;

#define GC_PUSH_PAIR(v) struct gc_stackroot _gcsr_##v;  _gcsr_##v.root = (void**)&v;  _gcsr_##v.next = gc_stack_roots;
#define GC_PUSH_OBJ(v) struct gc_stackroot _gcsr_##v;  _gcsr_##v.root = (void**)((unsigned char*)&v + OBJECT_TAG); _gcsr_##v.next = gc_stack_roots;
#define GC_POP(v)  gc_stack_roots = _gcsr_##v.next;

void* gc_alloc(size_t size);

void error(const char* msg);

struct vtable_t {
	OBJECT_META;
};

struct method_t {
	OBJECT_META;
	struct object_t* name;
};

enum registers {
};

struct machine_t {
	cell reg[NUM_REGISTERS];
};

void error(const char* msg) {
	fprintf(stderr, "%s\n", msg);
	exit(1);
}



/* GC implementation */

#define GC_HEAPSIZE 1024*1024
#define GC_TOO_BIG  (GC_HEAPSIZE/8)

void gc_collect();

struct gc_stackroot* gc_stack_roots = 0;

void* gc_broken_heart = 0; /* if first word in x points to gc_broken_heart, second word points to the actual object */

unsigned char* gc_heap = 0;
unsigned char* gc_new  = 0;
unsigned char* gc_top = 0;

void* gc_alloc(size_t size) {
	void* ret;
	if (size < sizeof(struct pair_t))
		error("allocation too small");
	else if (size > GC_TOO_BIG)
		error("allocation too big");
	else if (gc_top + size > gc_heap + GC_HEAPSIZE)
		gc_collect();
	ret = gc_top;
	gc_top += size;
	return ret;
}

void gc_collect() {
	unsigned char* scan;
	unsigned char* free;
	unsigned char* old;
	struct gc_stackroot* root;
	scan = gc_new;
	free = gc_new;

	/* step 1: relocate all roots */
	for (root = gc_stack_roots; root; root = root->next) {
		if (IS_PAIR(root->root)) {
		}
		else {
		}
	}

	/* step 2: scan new */
	{
	}

	/* step 3: flip */

	gc_heap = 
}