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