code.kerkeslager.com Git - fur/blob - templates/program.c

   1 #include <assert.h>
   2 #include <inttypes.h>
   3 #include <stdbool.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 /* Some terminology used in function names:
   8  * - initialize: These functions take a pointer and potentially some other arguments, and use those
   9  *   to initialize the value pointed to by self. Initialize functions DO NOT allocate the function,
  10  *   so they can be used to initialize stack-allocated variables.
  11  * - construct: This allocates a value for a pointer, initializes it, and returns it. This is for
  12  *   heap-allocated values. It may be as simple as allocating the memory, calling an initialize, and
  13  *   returning it.
  14  * - deinitialize: These functions dereference or free any objects pointed to by the self pointer's
  15  *   value, but they don't actually free the self pointer. This is useful for stack-allocated objects
  16  *   which point to heap-allocated objects.
  17  * - destruct: This dereferences or frees memory pointed to by the self argument, and all the
  18  *   pointers on the self argument.
  19  */
  20
  21 {% for standard_library in standard_libraries %}
  22 #include <{{standard_library}}>
  23 {% endfor %}
  24
  25 enum Type;
  26 typedef enum Type Type;
  27 union Instance;
  28 typedef union Instance Instance;
  29 struct Object;
  30 typedef struct Object Object;
  31 struct EnvironmentNode;
  32 typedef struct EnvironmentNode EnvironmentNode;
  33 struct Environment;
  34 typedef struct Environment Environment;
  35 struct EnvironmentPool;
  36 typedef struct EnvironmentPool EnvironmentPool;
  37
  38 const char* const STRING_LITERAL_LIST[] = {
  39 {% for string_literal in string_literal_list %}
  40   "{{ string_literal }}",
  41 {% endfor %}
  42 };
  43
  44 const char* const SYMBOL_LIST[] = {
  45 {% for symbol in symbol_list %}
  46   "{{ symbol }}",
  47 {% endfor %}
  48 };
  49
  50 enum Type
  51 {
  52   BOOLEAN,
  53   CLOSURE,
  54   INTEGER,
  55   LIST,
  56   STRING,
  57   VOID
  58 };
  59
  60 struct Closure;
  61 typedef struct Closure Closure;
  62 struct Closure
  63 {
  64   Environment* closed;
  65   Object (*call)(EnvironmentPool*, Environment*, size_t, Object*);
  66 };
  67
  68 struct List;
  69 typedef struct List List;
  70 struct List
  71 {
  72   size_t allocated;
  73   size_t length;
  74   Object* items;
  75 };
  76
  77 union Instance
  78 {
  79   bool boolean;
  80   Closure closure;
  81   int32_t integer;
  82   List list;
  83   const char* string;
  84 };
  85
  86 struct Object
  87 {
  88   Type type;
  89   Instance instance;
  90 };
  91
  92 const Object builtin$true = { BOOLEAN, (Instance)(bool){ true } };
  93 const Object builtin$false = { BOOLEAN, (Instance)(bool){ false } };
  94 const Object builtin$nil = { VOID, { 0 } };
  95
  96 Object List_construct(size_t allocate)
  97 {
  98   Object* items = malloc(sizeof(Object) * allocate);
  99   Object result = { LIST, (Instance)(List){ allocate, 0, items } };
 100   return result;
 101 }
 102
 103 void List_append(Object* list, Object item)
 104 {
 105   assert(list->type == LIST);
 106
 107   if(list->instance.list.allocated == list->instance.list.length)
 108   {
 109     list->instance.list.allocated *= 2;
 110     list->instance.list.items = realloc(
 111       list->instance.list.items,
 112       sizeof(Object) * list->instance.list.allocated
 113     );
 114   }
 115
 116   list->instance.list.items[list->instance.list.length] = item;
 117   list->instance.list.length++;
 118 }
 119
 120 Object List_get(Object* list, Object index)
 121 {
 122   assert(list->type == LIST);
 123   assert(index.type == INTEGER);
 124
 125   return list->instance.list.items[index.instance.integer];
 126 }
 127
 128 struct EnvironmentNode
 129 {
 130   const char* key;
 131   Object value;
 132   EnvironmentNode* next;
 133 };
 134
 135 struct Environment
 136 {
 137   bool mark;
 138   bool live;
 139
 140   Environment* parent;
 141   EnvironmentNode* root;
 142 };
 143
 144 void Environment_initialize(Environment* self, Environment* parent)
 145 {
 146   self->parent = parent;
 147   self->root = NULL;
 148
 149   // We are currently only ever initializing environments at the beginning of running functions, so
 150   // for now at least we can assume that we want it to be live immediately.
 151   self->live = true;
 152 }
 153
 154 void Environment_deinitialize(Environment* self)
 155 {
 156   EnvironmentNode* next;
 157   for(EnvironmentNode* node = self->root; node != NULL; node = next)
 158   {
 159     next = node->next;
 160
 161     switch(node->value.type)
 162     {
 163       case BOOLEAN:
 164       case CLOSURE:
 165       case INTEGER:
 166       case STRING:
 167       case VOID:
 168         break;
 169
 170       case LIST:
 171         free(node->value.instance.list.items);
 172         break;
 173
 174       default:
 175         assert(false);
 176     }
 177
 178     free(node);
 179   }
 180 }
 181
 182 void Environment_setLive(Environment* self, bool live)
 183 {
 184   self->live = live;
 185 }
 186
 187 void Environment_mark(Environment* self)
 188 {
 189   if(self == NULL) return;
 190   if(self->mark) return; // Prevents infinite recursion in the case of cycles
 191
 192   self->mark = true;
 193
 194   Environment_mark(self->parent);
 195
 196   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 197   {
 198     switch(node->value.type)
 199     {
 200       case BOOLEAN:
 201       case INTEGER:
 202       case STRING:
 203       case VOID:
 204         break;
 205
 206       case CLOSURE:
 207         Environment_mark(node->value.instance.closure.closed);
 208         break;
 209
 210       default:
 211         assert(false);
 212     }
 213   }
 214 }
 215
 216 // This need not be thread safe because environments exist on one thread only
 217 void Environment_set(Environment* self, const char* const key, Object value)
 218 {
 219   EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
 220   node->key = key;
 221   node->value = value;
 222   node->next = self->root;
 223   self->root = node;
 224 }
 225
 226 Object Environment_get(Environment* self, const char* const symbol)
 227 {
 228   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 229   {
 230     // We can compare pointers because pointers are unique in the SYMBOL_LIST
 231     if(node->key == symbol)
 232     {
 233       return node->value;
 234     }
 235   }
 236
 237   if(self->parent != NULL)
 238   {
 239     return Environment_get(self->parent, symbol);
 240   }
 241
 242   // TODO Handle symbol errors
 243   assert(false);
 244 }
 245
 246 # define POOL_SIZE 64
 247 struct EnvironmentPool
 248 {
 249   int8_t freeIndex;
 250   bool allocatedFlags[POOL_SIZE];
 251   Environment environments[POOL_SIZE];
 252   EnvironmentPool* overflow;
 253 };
 254
 255 EnvironmentPool* EnvironmentPool_construct();
 256 void EnvironmentPool_initialize(EnvironmentPool*);
 257 void EnvironmentPool_deinitialize(EnvironmentPool*);
 258 void EnvironmentPool_destruct(EnvironmentPool*);
 259
 260 EnvironmentPool* EnvironmentPool_construct()
 261 {
 262   EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
 263   EnvironmentPool_initialize(result);
 264   return result;
 265 }
 266
 267 void EnvironmentPool_initialize(EnvironmentPool* self)
 268 {
 269   self->overflow = NULL;
 270   self->freeIndex = 0;
 271
 272   for(size_t i = 0; i < POOL_SIZE; i++)
 273   {
 274     self->allocatedFlags[i] = false;
 275     self->environments[i].live = false;
 276   }
 277 }
 278
 279 void EnvironmentPool_deinitialize(EnvironmentPool* self)
 280 {
 281   // We can assume if this is being called, none of the Environments are live
 282   for(int8_t i = 0; i < POOL_SIZE; i++)
 283   {
 284     if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
 285   }
 286
 287   EnvironmentPool_destruct(self->overflow);
 288 }
 289
 290 void EnvironmentPool_destruct(EnvironmentPool* self)
 291 {
 292   if(self == NULL) return;
 293   EnvironmentPool_deinitialize(self);
 294   free(self);
 295 }
 296
 297 void EnvironmentPool_GC(EnvironmentPool* self)
 298 {
 299   // Unmark all the environments
 300   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 301   {
 302     for(int8_t i = 0; i < POOL_SIZE; i++)
 303     {
 304       current->environments[i].mark = false;
 305     }
 306   }
 307
 308   // Mark live enviroments and environments referenced by live environments
 309   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 310   {
 311     for(int8_t i = 0; i < POOL_SIZE; i++)
 312     {
 313       if(current->environments[i].live)
 314       {
 315         Environment_mark(&(current->environments[i]));
 316       }
 317     }
 318   }
 319
 320   // TODO We never free pools until the very end--we could free a pool if two pools are empty
 321   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 322   {
 323     for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
 324     {
 325       if(!current->environments[i].mark && current->allocatedFlags[i])
 326       {
 327         Environment_deinitialize(&(current->environments[i]));
 328         current->allocatedFlags[i] = false;
 329         current->freeIndex = i;
 330       }
 331     }
 332   }
 333 }
 334
 335 Environment* EnvironmentPool_allocate(EnvironmentPool* self)
 336 {
 337   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 338   {
 339     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 340     {
 341       if(!current->allocatedFlags[current->freeIndex])
 342       {
 343         current->allocatedFlags[current->freeIndex] = true;
 344         return &(current->environments[current->freeIndex]);
 345       }
 346     }
 347   }
 348
 349   EnvironmentPool_GC(self);
 350
 351   EnvironmentPool* previous;
 352   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 353   {
 354     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 355     {
 356       if(!current->allocatedFlags[current->freeIndex])
 357       {
 358         current->allocatedFlags[current->freeIndex] = true;
 359         return &(current->environments[current->freeIndex]);
 360       }
 361       else
 362       {
 363         previous = current;
 364       }
 365     }
 366   }
 367
 368   previous->overflow = EnvironmentPool_construct();
 369   return EnvironmentPool_allocate(previous->overflow);
 370 }
 371
 372 Object integerLiteral(int32_t literal)
 373 {
 374   Object result;
 375   result.type = INTEGER;
 376   result.instance.integer = literal;
 377   return result;
 378 }
 379
 380 Object stringLiteral(const char* literal)
 381 {
 382   Object result;
 383   result.type = STRING;
 384   result.instance.string = literal;
 385   return result;
 386 }
 387
 388 // TODO Make this conditionally added
 389 Object operator$negate(Object input)
 390 {
 391   assert(input.type == INTEGER);
 392
 393   Object result;
 394   result.type = INTEGER;
 395   result.instance.integer = -input.instance.integer;
 396   return result;
 397 }
 398
 399 {% for id in infix_declarations %}
 400 Object operator${{ id.name }}(Object left, Object right)
 401 {
 402   assert(left.type == {{ id.in_type.upper() }});
 403   assert(right.type == {{ id.in_type.upper() }});
 404
 405   Object result;
 406   result.type = {{ id.out_type.upper() }};
 407   result.instance.{{ id.out_type.lower() }} = left.instance.{{ id.in_type.lower() }} {{ id.operator }} right.instance.{{ id.in_type.lower() }};
 408   return result;
 409 }
 410 {% endfor %}
 411
 412 {% if 'pow' in builtins %}
 413 Object builtin$pow$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
 414 {
 415   assert(argc == 2);
 416
 417   Object base = args[0];
 418   Object exponent = args[1];
 419
 420   assert(base.type == INTEGER);
 421   assert(exponent.type == INTEGER);
 422
 423   Object result;
 424   result.type = INTEGER;
 425   result.instance.integer = pow(base.instance.integer, exponent.instance.integer);
 426   return result;
 427 }
 428
 429 Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
 430 {% endif %}
 431
 432 {% if 'print' in builtins %}
 433 Object builtin$print$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
 434 {
 435   for(size_t i = 0; i < argc; i++)
 436   {
 437     Object output = args[i];
 438     switch(output.type)
 439     {
 440       case BOOLEAN:
 441         fputs(output.instance.boolean ? "true" : "false", stdout);
 442         break;
 443
 444       case CLOSURE:
 445         // TODO Print something better
 446         printf("<Closure>");
 447         break;
 448
 449       case INTEGER:
 450         printf("%" PRId32, output.instance.integer);
 451         break;
 452
 453       case STRING:
 454         // Using fwrite instead of printf to handle size_t length
 455         printf("%s", output.instance.string);
 456         break;
 457
 458       case VOID:
 459         printf("nil");
 460         break;
 461
 462       default:
 463         assert(false);
 464     }
 465   }
 466
 467   // TODO Return something better
 468   return builtin$false;
 469 }
 470
 471 Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
 472 {% endif %}
 473 {% for function_definition in function_definition_list %}
 474 {{ function_definition }}
 475 {% endfor %}
 476
 477 int main(int argc, char** argv)
 478 {
 479   EnvironmentPool* environmentPool = EnvironmentPool_construct();
 480   Environment* environment = EnvironmentPool_allocate(environmentPool);
 481   Environment_initialize(environment, NULL);
 482
 483   // TODO Use the symbol from SYMBOL_LIST
 484   {% for builtin in builtins %}
 485   Environment_set(environment, "{{ builtin }}", builtin${{ builtin }});
 486   {% endfor %}
 487
 488   {% for statement in statements %}
 489   {{ statement }}
 490   {% endfor %}
 491
 492   Environment_setLive(environment, false);
 493   EnvironmentPool_destruct(environmentPool);
 494   return 0;
 495 }