8 /* Some terminology used in function names:
9 * - initialize: These functions take a pointer and potentially some other arguments, and use those
10 * to initialize the value pointed to by self. Initialize functions DO NOT allocate the function,
11 * so they can be used to initialize stack-allocated variables.
12 * - construct: This allocates a value for a pointer, initializes it, and returns it. This is for
13 * heap-allocated values. It may be as simple as allocating the memory, calling an initialize, and
15 * - deinitialize: These functions dereference or free any objects pointed to by the self pointer's
16 * value, but they don't actually free the self pointer. This is useful for stack-allocated objects
17 * which point to heap-allocated objects.
18 * - destruct: This dereferences or frees memory pointed to by the self argument, and all the
19 * pointers on the self argument.
22 {% for standard_library in standard_libraries %}
23 #include <{{standard_library}}>
27 typedef enum Type Type;
29 typedef union Instance Instance;
31 typedef struct Object Object;
32 struct EnvironmentNode;
33 typedef struct EnvironmentNode EnvironmentNode;
35 typedef struct Environment Environment;
36 struct EnvironmentPool;
37 typedef struct EnvironmentPool EnvironmentPool;
39 typedef struct Stack Stack;
41 const char* const STRING_LITERAL_LIST[] = {
42 {% for string_literal in string_literal_list %}
43 "{{ string_literal }}",
47 const char* const SYMBOL_LIST[] = {
48 {% for symbol in symbol_list %}
66 typedef struct Closure Closure;
70 Object (*call)(EnvironmentPool*, Environment*, size_t, Stack*, const unsigned long, jmp_buf);
74 typedef struct List List;
82 struct StringConcatenation;
83 typedef struct StringConcatenation StringConcatenation;
86 typedef struct Structure Structure;
89 size_t reference_count;
91 const char** symbol_list;
101 StringConcatenation* string_concatenation;
102 const char* string_literal;
103 Structure* structure;
112 const Object builtin$true = { BOOLEAN, (Instance)(bool){ true } };
113 const Object builtin$false = { BOOLEAN, (Instance)(bool){ false } };
114 const Object builtin$nil = { VOID, { 0 } };
116 struct StringConcatenation
118 size_t referenceCount;
123 Object List_construct(size_t allocate)
125 Object* items = malloc(sizeof(Object) * allocate);
126 Object result = { LIST, (Instance)(List){ allocate, 0, items } };
130 void List_append(Object* list, Object item)
132 assert(list->type == LIST);
134 if(list->instance.list.allocated == list->instance.list.length)
136 list->instance.list.allocated *= 2;
137 list->instance.list.items = realloc(
138 list->instance.list.items,
139 sizeof(Object) * list->instance.list.allocated
143 list->instance.list.items[list->instance.list.length] = item;
144 list->instance.list.length++;
147 Object List_get(Object* list, Object index)
149 assert(list->type == LIST);
150 assert(index.type == INTEGER);
152 return list->instance.list.items[index.instance.integer];
161 void Stack_initialize(Stack* self)
166 Stack* Stack_construct()
168 Stack* result = malloc(sizeof(Stack));
169 Stack_initialize(result);
173 void Stack_destruct(Stack* self)
178 bool Stack_any(Stack* self)
180 return self->length > 0;
183 void Stack_push(Stack* self, Object item)
185 assert(self->length < 256);
186 self->items[self->length] = item;
190 Object Stack_pop(Stack* self)
192 assert(self->length > 0);
194 return self->items[self->length];
197 Object Object_rereference(Object self)
208 case STRING_CONCATENATION:
209 self.instance.string_concatenation->referenceCount++;
213 self.instance.structure->reference_count++;
221 Object Structure_construct(size_t length, const char** symbol_list, Object* value_list)
223 Structure* structure = malloc(sizeof(Structure));
224 structure->reference_count = 1;
225 structure->length = length;
226 structure->symbol_list = malloc(sizeof(const char*) * length);
227 structure->value_list = malloc(sizeof(Object) * length);
229 // TODO Don't allow assignment of mutable structures, as this screws up reference counting
230 for(size_t i = 0; i < length; i++)
232 structure->symbol_list[i] = symbol_list[i];
233 structure->value_list[i] = Object_rereference(value_list[i]);
236 Object result = { STRUCTURE, (Instance)structure };
241 Object Structure_get(Object* self, const char* symbol)
243 assert(self->type == STRUCTURE);
245 for(size_t i = 0; i < self->instance.structure->length; i++)
247 if(self->instance.structure->symbol_list[i] == symbol)
249 return self->instance.structure->value_list[i];
256 struct EnvironmentNode
260 EnvironmentNode* next;
269 EnvironmentNode* root;
272 void Environment_initialize(Environment* self, Environment* parent)
274 self->parent = parent;
277 // We are currently only ever initializing environments at the beginning of running functions, so
278 // for now at least we can assume that we want it to be live immediately.
282 void Object_deinitialize(Object* self)
298 for(size_t i = 0; i < self->instance.list.length; i++) {
299 Object_deinitialize(&(self->instance.list.items[i]));
302 free(self->instance.list.items);
305 case STRING_CONCATENATION:
306 self->instance.string_concatenation->referenceCount--;
308 if(self->instance.string_concatenation->referenceCount == 0)
310 Object_deinitialize(&(self->instance.string_concatenation->left));
311 Object_deinitialize(&(self->instance.string_concatenation->right));
312 free(self->instance.string_concatenation);
317 self->instance.structure->reference_count--;
319 if(self->instance.structure->reference_count == 0)
321 for(size_t i = 0; i < self->instance.structure->length; i++)
323 Object_deinitialize(&(self->instance.structure->value_list[i]));
325 free(self->instance.structure->symbol_list);
326 free(self->instance.structure->value_list);
327 free(self->instance.structure);
336 typedef uint32_t StackSnapshot;
338 StackSnapshot Stack_takeSnapshot(Stack* self)
340 return (StackSnapshot) self->length;
343 void Stack_rewind(Stack* self, StackSnapshot snapshot)
345 while(self->length > snapshot)
347 Object item = Stack_pop(self);
348 Object_deinitialize(&item);
352 void Environment_deinitialize(Environment* self)
354 EnvironmentNode* next;
355 for(EnvironmentNode* node = self->root; node != NULL; node = next)
358 Object_deinitialize(&(node->value));
363 void Environment_setLive(Environment* self, bool live)
368 void Environment_mark(Environment* self)
370 if(self == NULL) return;
371 if(self->mark) return; // Prevents infinite recursion in the case of cycles
375 Environment_mark(self->parent);
377 for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
379 switch(node->value.type)
388 Environment_mark(node->value.instance.closure.closed);
397 // This need not be thread safe because environments exist on one thread only
398 void Environment_set(Environment* self, const char* const key, Object value)
400 EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
403 node->next = self->root;
407 Object Environment_get(Environment* self, const char* const symbol)
409 for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
411 // We can compare pointers because pointers are unique in the SYMBOL_LIST
412 if(node->key == symbol)
418 if(self->parent != NULL)
420 return Environment_get(self->parent, symbol);
423 // TODO Handle symbol errors
427 # define POOL_SIZE 64
428 struct EnvironmentPool
431 bool allocatedFlags[POOL_SIZE];
432 Environment environments[POOL_SIZE];
433 EnvironmentPool* overflow;
436 EnvironmentPool* EnvironmentPool_construct();
437 void EnvironmentPool_initialize(EnvironmentPool*);
438 void EnvironmentPool_deinitialize(EnvironmentPool*);
439 void EnvironmentPool_destruct(EnvironmentPool*);
441 EnvironmentPool* EnvironmentPool_construct()
443 EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
444 EnvironmentPool_initialize(result);
448 void EnvironmentPool_initialize(EnvironmentPool* self)
450 self->overflow = NULL;
453 for(size_t i = 0; i < POOL_SIZE; i++)
455 self->allocatedFlags[i] = false;
456 self->environments[i].live = false;
460 void EnvironmentPool_deinitialize(EnvironmentPool* self)
462 // We can assume if this is being called, none of the Environments are live
463 for(int8_t i = 0; i < POOL_SIZE; i++)
465 if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
468 EnvironmentPool_destruct(self->overflow);
471 void EnvironmentPool_destruct(EnvironmentPool* self)
473 if(self == NULL) return;
474 EnvironmentPool_deinitialize(self);
478 void EnvironmentPool_GC(EnvironmentPool* self)
480 // Unmark all the environments
481 for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
483 for(int8_t i = 0; i < POOL_SIZE; i++)
485 current->environments[i].mark = false;
489 // Mark live enviroments and environments referenced by live environments
490 for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
492 for(int8_t i = 0; i < POOL_SIZE; i++)
494 if(current->environments[i].live)
496 Environment_mark(&(current->environments[i]));
501 // TODO We never free pools until the very end--we could free a pool if two pools are empty
502 for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
504 for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
506 if(!current->environments[i].mark && current->allocatedFlags[i])
508 Environment_deinitialize(&(current->environments[i]));
509 current->allocatedFlags[i] = false;
510 current->freeIndex = i;
516 Environment* EnvironmentPool_allocate(EnvironmentPool* self)
518 for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
520 for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
522 if(!current->allocatedFlags[current->freeIndex])
524 current->allocatedFlags[current->freeIndex] = true;
525 return &(current->environments[current->freeIndex]);
530 EnvironmentPool_GC(self);
532 EnvironmentPool* previous;
533 for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
535 for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
537 if(!current->allocatedFlags[current->freeIndex])
539 current->allocatedFlags[current->freeIndex] = true;
540 return &(current->environments[current->freeIndex]);
549 previous->overflow = EnvironmentPool_construct();
550 return EnvironmentPool_allocate(previous->overflow);
553 Environment* Environment_construct(EnvironmentPool* environmentPool, Environment* parent)
555 Environment* environment = EnvironmentPool_allocate(environmentPool);
556 Environment_initialize(environment, parent);
560 Object integerLiteral(int32_t literal)
563 result.type = INTEGER;
564 result.instance.integer = literal;
568 Object stringLiteral(const char* literal)
571 result.type = STRING_LITERAL;
572 result.instance.string_literal = literal;
576 {% if 'pow' in builtins %}
577 Object builtin$pow$implementation(
578 EnvironmentPool* environmentPool,
582 const unsigned long line,
585 // Must unload items in reverse order
586 Object exponent = Stack_pop(stack);
587 Object base = Stack_pop(stack);
589 assert(base.type == INTEGER);
590 assert(exponent.type == INTEGER);
593 result.type = INTEGER;
594 result.instance.integer = pow(base.instance.integer, exponent.instance.integer);
598 Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
601 Object builtin$negate$implementation(
602 EnvironmentPool* environmentPool,
606 const unsigned long line,
611 Object argument = Stack_pop(stack);
613 assert(argument.type == INTEGER);
615 Object result = (Object){
617 (Instance)(int32_t) (-argument.instance.integer)
622 Object builtin$negate = { CLOSURE, (Instance)(Closure){ NULL, builtin$negate$implementation } };
624 {% for op in ['lt', 'gt', 'lte', 'gte', 'eq', 'neq'] %}
625 Object builtin${{ op }}$implementation(
626 EnvironmentPool* environmentPool,
630 const unsigned long line,
635 Object right = Stack_pop(stack);
636 Object left = Stack_pop(stack);
638 assert(left.type == INTEGER);
639 assert(right.type == INTEGER);
642 if(left.instance.integer < right.instance.integer)
643 {% elif op == 'gt' %}
644 if(left.instance.integer > right.instance.integer)
645 {% elif op == 'lte' %}
646 if(left.instance.integer <= right.instance.integer)
647 {% elif op == 'gte' %}
648 if(left.instance.integer >= right.instance.integer)
649 {% elif op == 'eq' %}
650 if(left.instance.integer == right.instance.integer)
651 {% elif op == 'neq' %}
652 if(left.instance.integer != right.instance.integer)
659 return builtin$false;
662 Object builtin${{ op }} = { CLOSURE, (Instance)(Closure){ NULL, builtin${{ op }}$implementation } };
665 Object builtin$concat$implementation(
666 EnvironmentPool* environmentPool,
670 const unsigned long line,
675 Object right = Stack_pop(stack);
676 Object left = Stack_pop(stack);
679 case STRING_CONCATENATION:
688 case STRING_CONCATENATION:
696 StringConcatenation* concatenation = malloc(sizeof(StringConcatenation));
697 concatenation->referenceCount = 1;
698 concatenation->left = Object_rereference(left);
699 concatenation->right = Object_rereference(right);
701 Object result = { STRING_CONCATENATION, (Instance)concatenation };
704 Object builtin$concat = { CLOSURE, (Instance)(Closure){ NULL, builtin$concat$implementation } };
706 Object builtin$add$implementation(
707 EnvironmentPool* environmentPool,
711 const unsigned long line,
716 Object right = Stack_pop(stack);
717 Object left = Stack_pop(stack);
719 assert(left.type == INTEGER);
720 assert(right.type == INTEGER);
722 Object result = (Object){
724 (Instance)(int32_t) (left.instance.integer + right.instance.integer)
729 Object builtin$add = { CLOSURE, (Instance)(Closure){ NULL, builtin$add$implementation } };
731 Object builtin$subtract$implementation(
732 EnvironmentPool* environmentPool,
736 const unsigned long line,
741 Object right = Stack_pop(stack);
742 Object left = Stack_pop(stack);
744 assert(left.type == INTEGER);
745 assert(right.type == INTEGER);
747 Object result = (Object){
749 (Instance)(int32_t) (left.instance.integer - right.instance.integer)
754 Object builtin$subtract = { CLOSURE, (Instance)(Closure){ NULL, builtin$subtract$implementation } };
756 Object builtin$multiply$implementation(
757 EnvironmentPool* environmentPool,
761 const unsigned long line,
766 Object right = Stack_pop(stack);
767 Object left = Stack_pop(stack);
769 assert(left.type == INTEGER);
770 assert(right.type == INTEGER);
772 Object result = (Object){
774 (Instance)(int32_t) (left.instance.integer * right.instance.integer)
779 Object builtin$multiply = { CLOSURE, (Instance)(Closure){ NULL, builtin$multiply$implementation } };
781 Object builtin$integer_divide$implementation(
782 EnvironmentPool* environmentPool,
786 const unsigned long line,
791 Object right = Stack_pop(stack);
792 Object left = Stack_pop(stack);
794 assert(left.type == INTEGER);
795 assert(right.type == INTEGER);
797 if(right.instance.integer == 0)
799 fprintf(stderr, "DivisionByZeroError on line %zu\n", line);
800 longjmp(parentJump, 1);
803 Object result = (Object){
805 (Instance)(int32_t) (left.instance.integer / right.instance.integer)
810 Object builtin$integer_divide = { CLOSURE, (Instance)(Closure){ NULL, builtin$integer_divide$implementation } };
812 Object builtin$modular_divide$implementation(
813 EnvironmentPool* environmentPool,
817 const unsigned long line,
822 Object right = Stack_pop(stack);
823 Object left = Stack_pop(stack);
825 assert(left.type == INTEGER);
826 assert(right.type == INTEGER);
828 if(right.instance.integer == 0)
830 fprintf(stderr, "DivisionByZeroError on line %zu\n", line);
831 longjmp(parentJump, 1);
834 Object result = (Object){
836 (Instance)(int32_t) (left.instance.integer % right.instance.integer)
841 Object builtin$modular_divide = { CLOSURE, (Instance)(Closure){ NULL, builtin$modular_divide$implementation } };
843 Object builtin$field$implementation(
844 EnvironmentPool* environmentPool,
848 const unsigned long line,
853 Object right = Stack_pop(stack);
854 Object left = Stack_pop(stack);
856 assert(left.type == STRUCTURE);
857 assert(right.type == STRING_LITERAL);
859 Object result = (Object){
861 (Instance)(int32_t) (left.instance.integer % right.instance.integer)
866 Object builtin$field = { CLOSURE, (Instance)(Closure){ NULL, builtin$field$implementation } };
868 Object builtin$get$implementation(
869 EnvironmentPool* environmentPool,
873 const unsigned long line,
878 Object right = Stack_pop(stack);
879 Object left = Stack_pop(stack);
881 return List_get(&left, right);
883 Object builtin$get = { CLOSURE, (Instance)(Closure){ NULL, builtin$get$implementation } };
885 {% if 'print' in builtins %}
886 Object builtin$print$implementation(
887 EnvironmentPool* environmentPool,
891 const unsigned long line,
895 Stack_initialize(&reverse_stack);
897 for(size_t i = 0; i < argc; i++)
899 Stack_push(&reverse_stack, Stack_pop(stack));
902 while(reverse_stack.length > 0)
904 Object output = Stack_pop(&reverse_stack);
908 fputs(output.instance.boolean ? "true" : "false", stdout);
912 // TODO Print something better
917 printf("%" PRId32, output.instance.integer);
920 case STRING_CONCATENATION:
921 Stack_push(stack, output.instance.string_concatenation->left);
922 builtin$print$implementation(NULL, NULL, 1, stack, line, parentJump);
923 Stack_push(stack, output.instance.string_concatenation->right);
924 builtin$print$implementation(NULL, NULL, 1, stack, line, parentJump);
928 // Using fwrite instead of printf to handle size_t length
929 printf("%s", output.instance.string_literal);
939 Object_deinitialize(&output);
942 // TODO Return something better
943 return builtin$false;
946 Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
948 {% for function_definition in function_definition_list %}
949 {{ function_definition }}
952 int main(int argc, char** argv)
954 EnvironmentPool* environmentPool = EnvironmentPool_construct();
955 Environment* environment = EnvironmentPool_allocate(environmentPool);
956 Environment_initialize(environment, NULL);
959 Stack* stack = &stackMemory;
960 Stack_initialize(stack);
963 if(setjmp(jump) != 0)
965 fprintf(stderr, "\tin __main__\n");
967 while(Stack_any(stack))
969 Object item = Stack_pop(stack);
970 Object_deinitialize(&item);
972 Environment_setLive(environment, false);
973 EnvironmentPool_destruct(environmentPool);
975 // TODO We would like to return something nonzero here, but that messes up Valgrind so we couldn't catch memory leaks
979 // TODO Use the symbol from SYMBOL_LIST
980 {% for builtin in builtins %}
981 Environment_set(environment, "{{ builtin }}", builtin${{ builtin }});
984 Environment_set(environment, "true", builtin$true);
985 Environment_set(environment, "false", builtin$false);
986 Environment_set(environment, "__add__", builtin$add);
987 Environment_set(environment, "__subtract__", builtin$subtract);
988 Environment_set(environment, "__multiply__", builtin$multiply);
989 Environment_set(environment, "__integer_divide__", builtin$integer_divide);
990 Environment_set(environment, "__modular_divide__", builtin$modular_divide);
991 Environment_set(environment, "__negate__", builtin$negate);
992 Environment_set(environment, "__concat__", builtin$concat);
993 Environment_set(environment, "__field__", builtin$field);
994 Environment_set(environment, "__get__", builtin$get);
996 {% for op in ['lt', 'gt', 'lte', 'gte', 'eq', 'neq'] %}
997 Environment_set(environment, "__{{ op }}__", builtin${{ op }});
1000 {% for statement in statements %}
1004 Environment_setLive(environment, false);
1005 EnvironmentPool_destruct(environmentPool);