Needed 1+1, Built a Functional Programming Language

table of contentsTHE DATA STRUCTURES ASSIGNMENTWe can add vars to this. It wouldn’t be a big changeActually implementing it in CArena AllocatorMaking the Env TableUPGRADING THE MEMORY ALLOCATORBUILDING THE GARBAGE COLLECTORWhat to expect in the next partsWhat have we achieved so far?WAIT. BUT DOES IT EVALUATE 1+1 I was given a data structures problem of converting an arithmetic expression into a binary tree. Naturally, I decided to build an evaluator. A few days later I implemented closures, a garbage collector, a custom memory allocator, a REPL, an FFI, and a whole bunch of other stuff in C. graphLang THE DATA STRUCTURES ASSIGNMENT The problem was: Evaluate 1 + 1 + 1 to 3 using a binary tree. How do we get there? Well, we first form our tree for 1+1+1 (+) / \ (+) (1) / \ (1) (1) The operator becomes the root, with its two operands as children. Now let’s evaluate this tree. First, we evaluate the root’s left operand. It’s another + expression, so we have to collapse it down to a value before the outer + can execute. (+) / \ (2) (1) Then we evaluate again. (3) <--- that's our result We just performed the equivalent of (+ (+ 1 1) 1) | v (+ 2 1) | v (3) But notice what the evaluator had to know to do this: what + means. One way to represent this is to make every operation a different case in our expression type: Expr ::= Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr | Val But what do these different cases actually represent? And does the evaluator really need to know the difference between Add and Sub? Then I started implementing our sum types. And when I looked at the structure: Add: Expr x Expr → Expr Sub: Expr x Expr → Expr Mul: Expr x Expr → Expr Div: Expr x Expr → Expr They all take two expressions and produce one expression. So why should the evaluator care whether the operation is Add, Sub, Mul, or Div? Seems like it doesn’t. So now we can just represent our expression as: Expr ::= Func Expr Expr | Val The evaluator doesn’t need to know what a function does. It only needs to know how to apply one. We can add vars to this. It wouldn’t be a big change Should be a tiny addition, no problem whatsoever. I mean variables are just a hash table lookup that gives you an Expr. Oh wait. C doesn’t have built-in hash tables. hmmm.（´-`）.｡oO( … ) Let’s just implement a hashtable. It’s a small change! m9(・∀・) Soo…how does that work? I never implemented it before. I look it up on Google like a caveman and find this amazing text. How to implement a hash table (in C) So now we just got a little change in the Expr: Expr ::= Func Expr Expr | Val | Var Would you look at that! We have variables now that can be passed to functions once evaluated. Just like (+ 1 1) Actually implementing it in C Alright then, time to code in C with this plan. Seems simple enough. Just a tagged union. typedef enum { LITERAL, VAR, FUNC, } NodeType; struct Node { struct Node *left; struct Node *right; union { int literal; char *var; char *func; } data; NodeType type; }; Right now the mem size of each ( assuming 64 bit system) is: +------------------------+----------+ | Field | Size | +------------------------+----------+ | Left Pointer | 8 bytes | | Right Pointer | 8 bytes | | Data | 8 bytes | | Type | 4 bytes | | Padding | 4 bytes | +------------------------+----------+ | Total | 32 bytes | +------------------------+----------+ 32 Bytes might not seem like a lot, but we gotta think about how this is being used. For evaluating 1+1, we would need 3 nodes. 1 for the operator 2 for the operands That would be 32 x 3= 96 bytes to evaluate 1+1. But here’s the thing. On my system, when you malloc() a node, it adds metadata, which takes up 16 bytes of memory! Bringing our total per node to 32 (node size) + 16 (malloc header) = 48 bytes! So for our 3 nodes to evaluate a (+) we would need 144 bytes! And notice we’re going to be doing a lot of little individual allocations. We need a better way to allocate these nodes. We clearly need a custom allocator. So, I look up what allocator we can use, again like a caveman, and I decide I will be writing an Arena Allocator. Arena Allocator The idea of an arena allocator is pretty simple. All you do is take a big chunk of memory at the start, allocate stuff yourself, and then at the end just free the entire block. So my arena allocator would just be: #define SIZE 1024 Node arena[SIZE] And when we allocate a node, we can just keep track of the top using. int top = 0; When we want to allocate a node, we just return. &arena[top++]; I wrote the allocator and defined a C function to allocate nodes: Node *allocNode(); It was great! Now moving on to actually calling the functions. Then I realized We can store vars and funcs in the same environment! That means functions can just be values too (°◇°) Remember the hashtable we created earlier? It’s time to upgrade it. Making the Env Table In the Env table we are storing two things. Vars and functions.