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   STRING
  56 };
  57
  58 struct Closure;
  59 typedef struct Closure Closure;
  60 struct Closure
  61 {
  62   Environment* closed;
  63   Object (*call)(EnvironmentPool*, Environment*, size_t, Object*);
  64 };
  65
  66 union Instance
  67 {
  68   bool boolean;
  69   Closure closure;
  70   int32_t integer;
  71   const char* string;
  72 };
  73
  74 struct Object
  75 {
  76   Type type;
  77   Instance instance;
  78 };
  79
  80 const Object TRUE = {
  81   BOOLEAN,
  82   { true }
  83 };
  84
  85 const Object FALSE = {
  86   BOOLEAN,
  87   { false }
  88 };
  89
  90 struct EnvironmentNode
  91 {
  92   const char* key;
  93   Object value;
  94   EnvironmentNode* next;
  95 };
  96
  97 struct Environment
  98 {
  99   bool mark;
 100   bool live;
 101
 102   Environment* parent;
 103   EnvironmentNode* root;
 104 };
 105
 106 void Environment_initialize(Environment* self, Environment* parent)
 107 {
 108   self->parent = parent;
 109   self->root = NULL;
 110
 111   // We are currently only ever initializing environments at the beginning of running functions, so
 112   // for now at least we can assume that we want it to be live immediately.
 113   self->live = true;
 114 }
 115
 116 void Environment_deinitialize(Environment* self)
 117 {
 118   EnvironmentNode* next;
 119   for(EnvironmentNode* node = self->root; node != NULL; node = next)
 120   {
 121     next = node->next;
 122     free(node);
 123   }
 124 }
 125
 126 void Environment_setLive(Environment* self, bool live)
 127 {
 128   self->live = live;
 129 }
 130
 131 void Environment_mark(Environment* self)
 132 {
 133   if(self == NULL) return;
 134   if(self->mark) return; // Prevents infinite recursion in the case of cycles
 135
 136   self->mark = true;
 137
 138   Environment_mark(self->parent);
 139
 140   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 141   {
 142     switch(node->value.type)
 143     {
 144       case BOOLEAN:
 145       case INTEGER:
 146       case STRING:
 147         break;
 148
 149       case CLOSURE:
 150         Environment_mark(node->value.instance.closure.closed);
 151         break;
 152
 153       default:
 154         assert(false);
 155     }
 156   }
 157 }
 158
 159 // This need not be thread safe because environments exist on one thread only
 160 void Environment_set(Environment* self, const char* const key, Object value)
 161 {
 162   EnvironmentNode* node = malloc(sizeof(EnvironmentNode));
 163   node->key = key;
 164   node->value = value;
 165   node->next = self->root;
 166   self->root = node;
 167 }
 168
 169 Object Environment_get(Environment* self, const char* const symbol)
 170 {
 171   for(EnvironmentNode* node = self->root; node != NULL; node = node->next)
 172   {
 173     // We can compare pointers because pointers are unique in the SYMBOL_LIST
 174     if(node->key == symbol)
 175     {
 176       return node->value;
 177     }
 178   }
 179
 180   if(self->parent != NULL)
 181   {
 182     return Environment_get(self->parent, symbol);
 183   }
 184
 185   // TODO Handle symbol errors
 186   assert(false);
 187 }
 188
 189 # define POOL_SIZE 64
 190 struct EnvironmentPool
 191 {
 192   int8_t freeIndex;
 193   bool allocatedFlags[POOL_SIZE];
 194   Environment environments[POOL_SIZE];
 195   EnvironmentPool* overflow;
 196 };
 197
 198 EnvironmentPool* EnvironmentPool_construct();
 199 void EnvironmentPool_initialize(EnvironmentPool*);
 200 void EnvironmentPool_deinitialize(EnvironmentPool*);
 201 void EnvironmentPool_destruct(EnvironmentPool*);
 202
 203 EnvironmentPool* EnvironmentPool_construct()
 204 {
 205   EnvironmentPool* result = malloc(sizeof(EnvironmentPool));
 206   EnvironmentPool_initialize(result);
 207   return result;
 208 }
 209
 210 void EnvironmentPool_initialize(EnvironmentPool* self)
 211 {
 212   self->overflow = NULL;
 213   self->freeIndex = 0;
 214
 215   for(size_t i = 0; i < POOL_SIZE; i++)
 216   {
 217     self->allocatedFlags[i] = false;
 218     self->environments[i].live = false;
 219   }
 220 }
 221
 222 void EnvironmentPool_deinitialize(EnvironmentPool* self)
 223 {
 224   // We can assume if this is being called, none of the Environments are live
 225   for(int8_t i = 0; i < POOL_SIZE; i++)
 226   {
 227     if(self->allocatedFlags[i]) Environment_deinitialize(&(self->environments[i]));
 228   }
 229
 230   EnvironmentPool_destruct(self->overflow);
 231 }
 232
 233 void EnvironmentPool_destruct(EnvironmentPool* self)
 234 {
 235   if(self == NULL) return;
 236   EnvironmentPool_deinitialize(self);
 237   free(self);
 238 }
 239
 240 void EnvironmentPool_GC(EnvironmentPool* self)
 241 {
 242   // Unmark all the environments
 243   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 244   {
 245     for(int8_t i = 0; i < POOL_SIZE; i++)
 246     {
 247       current->environments[i].mark = false;
 248     }
 249   }
 250
 251   // Mark live enviroments and environments referenced by live environments
 252   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 253   {
 254     for(int8_t i = 0; i < POOL_SIZE; i++)
 255     {
 256       if(current->environments[i].live)
 257       {
 258         Environment_mark(&(current->environments[i]));
 259       }
 260     }
 261   }
 262
 263   // TODO We never free pools until the very end--we could free a pool if two pools are empty
 264   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 265   {
 266     for(int8_t i = POOL_SIZE - 1; i >= 0; i--)
 267     {
 268       if(!current->environments[i].mark && current->allocatedFlags[i])
 269       {
 270         Environment_deinitialize(&(current->environments[i]));
 271         current->allocatedFlags[i] = false;
 272         current->freeIndex = i;
 273       }
 274     }
 275   }
 276 }
 277
 278 Environment* EnvironmentPool_allocate(EnvironmentPool* self)
 279 {
 280   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 281   {
 282     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 283     {
 284       if(!current->allocatedFlags[current->freeIndex])
 285       {
 286         current->allocatedFlags[current->freeIndex] = true;
 287         return &(current->environments[current->freeIndex]);
 288       }
 289     }
 290   }
 291
 292   EnvironmentPool_GC(self);
 293
 294   EnvironmentPool* previous;
 295   for(EnvironmentPool* current = self; current != NULL; current = current->overflow)
 296   {
 297     for(; current->freeIndex < POOL_SIZE; current->freeIndex++)
 298     {
 299       if(!current->allocatedFlags[current->freeIndex])
 300       {
 301         current->allocatedFlags[current->freeIndex] = true;
 302         return &(current->environments[current->freeIndex]);
 303       }
 304       else
 305       {
 306         previous = current;
 307       }
 308     }
 309   }
 310
 311   previous->overflow = EnvironmentPool_construct();
 312   return EnvironmentPool_allocate(previous->overflow);
 313 }
 314
 315 Object integerLiteral(int32_t literal)
 316 {
 317   Object result;
 318   result.type = INTEGER;
 319   result.instance.integer = literal;
 320   return result;
 321 }
 322
 323 Object stringLiteral(const char* literal)
 324 {
 325   Object result;
 326   result.type = STRING;
 327   result.instance.string = literal;
 328   return result;
 329 }
 330
 331 // TODO Make this conditionally added
 332 Object operator$negate(Object input)
 333 {
 334   assert(input.type == INTEGER);
 335
 336   Object result;
 337   result.type = INTEGER;
 338   result.instance.integer = -input.instance.integer;
 339   return result;
 340 }
 341
 342 {% for id in infix_declarations %}
 343 Object operator${{ id.name }}(Object left, Object right)
 344 {
 345   assert(left.type == {{ id.in_type.upper() }});
 346   assert(right.type == {{ id.in_type.upper() }});
 347
 348   Object result;
 349   result.type = {{ id.out_type.upper() }};
 350   result.instance.{{ id.out_type.lower() }} = left.instance.{{ id.in_type.lower() }} {{ id.operator }} right.instance.{{ id.in_type.lower() }};
 351   return result;
 352 }
 353 {% endfor %}
 354
 355 {% if 'pow' in builtins %}
 356 Object builtin$pow$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
 357 {
 358   assert(argc == 2);
 359
 360   Object base = args[0];
 361   Object exponent = args[1];
 362
 363   assert(base.type == INTEGER);
 364   assert(exponent.type == INTEGER);
 365
 366   Object result;
 367   result.type = INTEGER;
 368   result.instance.integer = pow(base.instance.integer, exponent.instance.integer);
 369   return result;
 370 }
 371
 372 Object builtin$pow = { CLOSURE, (Instance)(Closure){ NULL, builtin$pow$implementation } };
 373 {% endif %}
 374
 375 {% if 'print' in builtins %}
 376 Object builtin$print$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
 377 {
 378   for(size_t i = 0; i < argc; i++)
 379   {
 380     Object output = args[i];
 381     switch(output.type)
 382     {
 383       case BOOLEAN:
 384         fputs(output.instance.boolean ? "true" : "false", stdout);
 385         break;
 386
 387       case CLOSURE:
 388         // TODO Print something better
 389         printf("<Closure>");
 390         break;
 391
 392       case INTEGER:
 393         printf("%" PRId32, output.instance.integer);
 394         break;
 395
 396       case STRING:
 397         // Using fwrite instead of printf to handle size_t length
 398         printf("%s", output.instance.string);
 399         break;
 400
 401       default:
 402         assert(false);
 403     }
 404   }
 405
 406   // TODO Return something better
 407   return FALSE;
 408 }
 409
 410 Object builtin$print = { CLOSURE, (Instance)(Closure){ NULL, builtin$print$implementation } };
 411 {% endif %}
 412
 413 {% for function_definition in function_definition_list %}
 414 Object user${{function_definition.name}}$implementation(EnvironmentPool* environmentPool, Environment* parent, size_t argc, Object* args)
 415 {
 416   assert(argc == {{ function_definition.argument_name_list|length }});
 417
 418   Environment* environment = EnvironmentPool_allocate(environmentPool);
 419   Environment_initialize(environment, parent);
 420
 421   {% for argument_name in function_definition.argument_name_list %}
 422   Environment_set(environment, "{{ argument_name }}", args[{{ loop.index0 }}]);
 423   {% endfor %}
 424
 425   {% for statement in function_definition.statement_list[:-1] %}
 426   {{ generate_statement(statement) }}
 427   {% endfor %}
 428
 429   Object result = {{ generate_statement(function_definition.statement_list[-1]) }}
 430
 431   Environment_setLive(environment, false);
 432   return result;
 433 }
 434
 435 {% endfor %}
 436 int main(int argc, char** argv)
 437 {
 438   EnvironmentPool* environmentPool = EnvironmentPool_construct();
 439   Environment* environment = EnvironmentPool_allocate(environmentPool);
 440   Environment_initialize(environment, NULL);
 441
 442   // TODO Use the symbol from SYMBOL_LIST
 443   {% for builtin in builtins %}
 444   Environment_set(environment, "{{ builtin }}", builtin${{ builtin }});
 445   {% endfor %}
 446
 447   {% for statement in statements %}
 448   {{ generate_statement(statement) }}
 449   {% endfor %}
 450
 451   Environment_setLive(environment, false);
 452   EnvironmentPool_destruct(environmentPool);
 453   return 0;
 454 }