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