+struct StringConcatenation;
+typedef struct StringConcatenation StringConcatenation;
+
+struct Structure;
+typedef struct Structure Structure;
+struct Structure
+{
+ size_t reference_count;
+ size_t length;
+ const char** symbol_list;
+ Object* value_list;
+};
+
+union Instance
+{
+ bool boolean;
+ Closure closure;
+ int32_t integer;
+ List list;
+ StringConcatenation* string_concatenation;
+ const char* string_literal;
+ Structure* structure;
+};
+
+struct Object
+{
+ Type type;
+ Instance instance;
+};
+
+const Object builtin$true = { BOOLEAN, (Instance)(bool){ true } };
+const Object builtin$false = { BOOLEAN, (Instance)(bool){ false } };
+const Object builtin$nil = { VOID, { 0 } };
+
+struct StringConcatenation
+{
+ size_t referenceCount;
+ Object left;
+ Object right;
+};
+
+Object List_construct(size_t allocate)
+{
+ Object* items = malloc(sizeof(Object) * allocate);
+ Object result = { LIST, (Instance)(List){ allocate, 0, items } };
+ return result;
+}
+
+void List_append(Object* list, Object item)
+{
+ assert(list->type == LIST);
+
+ if(list->instance.list.allocated == list->instance.list.length)
+ {
+ list->instance.list.allocated *= 2;
+ list->instance.list.items = realloc(
+ list->instance.list.items,
+ sizeof(Object) * list->instance.list.allocated
+ );
+ }
+
+ list->instance.list.items[list->instance.list.length] = item;
+ list->instance.list.length++;
+}
+
+Object List_get(Object* list, Object index)
+{
+ assert(list->type == LIST);
+ assert(index.type == INTEGER);
+
+ return list->instance.list.items[index.instance.integer];
+}
+
+struct Stack
+{
+ uint16_t length;
+ Object items[256];
+};
+
+void Stack_initialize(Stack* self)
+{
+ self->length = 0;
+}
+
+bool Stack_any(Stack* self)
+{
+ return self->length > 0;
+}
+
+void Stack_push(Stack* self, Object item)
+{
+ assert(self->length < 256);
+ self->items[self->length] = item;
+ self->length++;
+}
+
+Object Stack_pop(Stack* self)
+{
+ assert(self->length > 0);
+ self->length--;
+ return self->items[self->length];
+}
+
+Object Object_rereference(Object self)
+{
+ switch(self.type)
+ {
+ case BOOLEAN:
+ case CLOSURE:
+ case INTEGER:
+ case STRING_LITERAL:
+ case VOID:
+ return self;
+
+ case STRING_CONCATENATION:
+ self.instance.string_concatenation->referenceCount++;
+ return self;
+
+ case STRUCTURE:
+ self.instance.structure->reference_count++;
+ return self;
+
+ default:
+ assert(false);
+ }
+}
+
+Object Structure_construct(size_t length, const char** symbol_list, Object* value_list)
+{
+ Structure* structure = malloc(sizeof(Structure));
+ structure->reference_count = 1;
+ structure->length = length;
+ structure->symbol_list = malloc(sizeof(const char*) * length);
+ structure->value_list = malloc(sizeof(Object) * length);
+
+ // TODO Don't allow assignment of mutable structures, as this screws up reference counting
+ for(size_t i = 0; i < length; i++)
+ {
+ structure->symbol_list[i] = symbol_list[i];
+ structure->value_list[i] = Object_rereference(value_list[i]);
+ }
+
+ Object result = { STRUCTURE, (Instance)structure };
+
+ return result;
+}
+
+Object Structure_get(Object* self, const char* symbol)
+{
+ assert(self->type == STRUCTURE);
+
+ for(size_t i = 0; i < self->instance.structure->length; i++)
+ {
+ if(self->instance.structure->symbol_list[i] == symbol)
+ {
+ return self->instance.structure->value_list[i];
+ }
+ }
+
+ assert(false);
+}
+
+struct EnvironmentNode
+{
+ const char* key;
+ Object value;
+ EnvironmentNode* next;
+};
+
+struct Environment
+{
+ bool mark;
+ bool live;
+
+ Environment* parent;
+ EnvironmentNode* root;
+};
+
+void Environment_initialize(Environment* self, Environment* parent)
+{
+ self->parent = parent;
+ self->root = NULL;
+
+ // We are currently only ever initializing environments at the beginning of running functions, so
+ // for now at least we can assume that we want it to be live immediately.
+ self->live = true;
+}
+
+void Object_deinitialize(Object* self)
+{
+ switch(self->type)
+ {
+ case BOOLEAN:
+ break;
+ case CLOSURE:
+ break;
+ case INTEGER:
+ break;
+ case STRING_LITERAL:
+ break;
+ case VOID:
+ break;
+
+ case LIST:
+ for(size_t i = 0; i < self->instance.list.length; i++) {
+ Object_deinitialize(&(self->instance.list.items[i]));
+ }
+
+ free(self->instance.list.items);
+ break;
+
+ case STRING_CONCATENATION:
+ self->instance.string_concatenation->referenceCount--;
+
+ if(self->instance.string_concatenation->referenceCount == 0)
+ {
+ Object_deinitialize(&(self->instance.string_concatenation->left));
+ Object_deinitialize(&(self->instance.string_concatenation->right));
+ free(self->instance.string_concatenation);
+ }
+ break;
+
+ case STRUCTURE:
+ self->instance.structure->reference_count--;
+
+ if(self->instance.structure->reference_count == 0)
+ {
+ for(size_t i = 0; i < self->instance.structure->length; i++)
+ {
+ Object_deinitialize(&(self->instance.structure->value_list[i]));
+ }
+ free(self->instance.structure->symbol_list);
+ free(self->instance.structure->value_list);
+ free(self->instance.structure);
+ }
+ break;
+
+ default:
+ assert(false);
+ }
+}
+
+void Environment_deinitialize(Environment* self)
+{
+ EnvironmentNode* next;
+ for(EnvironmentNode* node = self->root; node != NULL; node = next)
+ {
+ next = node->next;
+ Object_deinitialize(&(node->value));
+ free(node);
+ }
+}
+
+void Environment_setLive(Environment* self, bool live)
+{
+ self->live = live;
+}
+
+void Environment_mark(Environment* self)
+{
+ if(self == NULL) return;
+ if(self->mark) return; // Prevents infinite recursion in the case of cycles
+
+ self->mark = true;
+
+ Environment_mark(self->parent);
+
+ for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
+ {
+ switch(node->value.type)
+ {
+ case BOOLEAN:
+ case INTEGER:
+ case STRING_LITERAL:
+ case VOID:
+ break;
+
+ case CLOSURE:
+ Environment_mark(node->value.instance.closure.closed);
+ break;
+
+ default:
+ assert(false);
+ }
+ }
+}
+
+// This need not be thread safe because environments exist on one thread only
+void Environment_set(Environment* self, const char* const key, Object value)
+{
+ EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
+ node->key = key;
+ node->value = value;
+ node->next = self->root;
+ self->root = node;
+}
+
+Object Environment_get(Environment* self, const char* const symbol)