Ik had 1+1 nodig, dus ik bouwde een functionele programmeertaal

Een paar dagen later had ik in C closures, een garbage collector, een eigen memory allocator, een REPL, een FFI en een heleboel andere zaken geïmplementeerd. Welkom bij graphLang.

De opdracht voor datastructuren

Het probleem was als volgt: bereken $1 + 1 + 1 = 3$ met behulp van een binaire boom.

Hoe pakken we dit aan? Eerst vormen we de boom voor $1+1+1$:

   (+)
  /   \
(+)   (1)
/ \
(1) (1)

De operator wordt de wortel (root), met de twee operanden als kinderen. Nu evalueren we deze boom. Eerst evalueren we de linker operand van de wortel. Dit is opnieuw een + expressie, dus we moeten deze eerst reduceren tot een waarde voordat de buitenste + kan worden uitgevoerd.

   (+)
  /   \
 (2)   (1)

Daarna evalueren we opnieuw:

   (3)  <--- dit is ons resultaat

In feite hebben we het volgende gedaan: (+ (+ 1 1) 1) → (+ 2 1) → (3)

De abstractie van functies

Om dit te doen, moet de evaluator weten wat + betekent. Eén manier om dit te representeren is door elke operatie als een aparte case in ons expressietype te definiëren:

• Expr ::= Add Expr Expr
• | Sub Expr Expr
• | Mul Expr Expr
• | Div Expr Expr
• | Val

Maar wat representeren deze verschillende cases nu echt? Moet de evaluator echt het verschil weten tussen Add en Sub? Wanneer ik naar de structuur keek, zag ik het volgende:

• Add: Expr x Expr → Expr
• Sub: Expr x Expr → Expr
• Mul: Expr x Expr → Expr
• Div: Expr x Expr → Expr

Ze nemen allemaal twee expressies en produceren één expressie. Waarom zou de evaluator er dus toe doen of de operatie Add, Sub, Mul of Div is? Dat lijkt niet relevant. We kunnen onze expressie dus vereenvoudigen naar:

Expr ::= Func Expr Expr | Val

De evaluator hoeft niet te weten wat een functie doet; hij hoeft alleen te weten hoe hij een functie moet toepassen.

Variabelen toevoegen

Ik dacht dat het toevoegen van variabelen een kleine aanpassing zou zijn. Variabelen zijn immers gewoon een lookup in een hashtabel die een Expr teruggeeft.

Er was echter één probleem: C heeft geen ingebouwde hashtabellen. Dus besloot ik er zelf een te implementeren. Hierdoor veranderde de definitie van Expr opnieuw:

Expr ::= Func Expr Expr | Val | Var

Nu hebben we variabelen die, eenmaal geëvalueerd, aan functies kunnen worden doorgegeven, net als in (+ 1 1).

Implementatie in C

Tijd om dit plan in C om te zetten. Ik heb gekozen voor een 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;
};

Geheugenanalyse

Op een 64-bit systeem is de grootte van een node als volgt:

Veld	Grootte
Left Pointer	8 bytes
Right Pointer	8 bytes
Data	8 bytes
Type	4 bytes
Padding	4 bytes
Totaal	32 bytes

32 bytes lijkt niet veel, maar voor het berekenen van $1+1$ hebben we drie nodes nodig (één voor de operator, twee voor de operanden), wat neerkomt op $32 \times 3 = 96$ bytes.

Het probleem is dat malloc() op mijn systeem metadata toevoegt van 16 bytes per allocatie. Dat brengt het totaal per node naar $32 + 16 = 48$ bytes. Voor drie nodes hebben we dus 144 bytes nodig. Omdat we veel kleine individuele allocaties doen, is een custom allocator noodzakelijk. Ik heb daarom gekozen voor een Arena Allocator.

De Arena Allocator

Het idee van een arena allocator is simpel: je reserveert aan het begin één groot blok geheugen, beheert de allocaties zelf, en maakt aan het einde het hele blok in één keer vrij.

#define SIZE 1024
Node arena[SIZE]
int top = 0;

// Bij allocatie:
&arena[top++];

Ik schreef de allocator en definieerde een C-functie Node *allocNode(). Terwijl ik dit deed, realiseerde ik me dat we variabelen en functies in dezelfde omgeving kunnen opslaan. Dat betekent dat functies zelf ook waarden kunnen zijn.

De Omgevingstabel (Env Table) maken

In de Env-tabel slaan we variabelen en functies op. Voor de evaluator is een functie simpelweg iets dat argumenten consumeert en een resultaat produceert.

Aanvankelijk dacht ik dat functies gewoon pointers naar C-functies konden zijn. Maar dat creëerde een probleem: hoe kunnen gebruikers hun eigen functies schrijven? Een gebruiker die code typt, bouwt een AST (Abstract Syntax Tree), geen native C-functiepointer.

Als functies alleen native C-pointers zijn, worden ze "opaque" (ondoorzichtig). Als een functie een andere functie teruggeeft, moet de evaluator die nieuwe functie kunnen verwerken. Een C-pointer is echter niet iets waar de evaluator doorheen kan lopen.

Closures

Ik had een type node nodig dat zegt: "Ik ben een functie, maar mijn code is geen C-pointer; het is deze boom hier."

Dit is de representatie van een closure. In plaats van een black-box C-functie, is een closure een node in onze graaf. Deze bevat aan de ene kant de parameter en aan de andere kant de boom van operaties (het lichaam).

Door van een functie een echte node te maken, kunnen we deze doorgeven, teruggeven vanuit andere functies en stap voor stap evalueren. Gebruikers kunnen nu dus zelf functies definiëren zonder C-code aan te raken.

De implementatie in C vereist dat de omgeving namen mapt naar nodes:

typedef struct EnvEntry {
    char *key;
    Node *val;
    struct EnvEntry *next;
} EnvEntry;

Ik heb de Node structuur uitgebreid om closures en native functies te ondersteunen:

struct Node {
    struct Node *left;
    struct Node *right;
    union {
        int literal;
        char *var;
        int index;
        char *call;
        struct Node *closure;
        struct Node *nativeFunc;
    } data;
    NodeType type;
};

• Native function: een opaque C-implementatie.
• Closure: een grafische representatie op taalniveau.

De geheugenallocator upgraden

Met de Arena Allocator, de Env-tabel en de evaluator was ik klaar om mijn eerste programma te draaien. Ik koos voor de Fibonacci-reeks en typte fib(5).

Het programma crashte onmiddellijk.

De reden was simpel: fib(5) genereerde 13.000 nodes, terwijl mijn allocator slechts 1024 nodes kon bevatten. De oplossing lijkt een dynamische array (realloc), maar dat zou alle bestaande pointers in het geheugenblok verbreken als het blok wordt verplaatst, wat leidt tot een segfault.

De Chunk Allocator

In plaats van één blok te laten groeien, heb ik gekozen voor een Chunk Allocator. Hierbij worden meerdere blokken aan elkaar gekoppeld in een gelinkte lijst. Wanneer een blok vol is, wordt er een nieuw blok gealloceerd zonder dat de bestaande data verplaatst hoeft te worden.

typedef struct Chunk {
    Node nodes[CHUNK_SIZE];
    struct Chunk *next;
} Chunk;

Na deze upgrade werkte fib(5) en gaf het correct het resultaat 5 terug. Maar er was iets vreemds: het programma gebruikte 1,32 MB RAM voor een simpele operatie. Bij fib(10) steeg dit naar 40 MB.

Een benchmark voor fib(40) liet zien dat het geheugengebruik opliep tot meer dan 12 GB voordat het programma crashte door een Out Of Memory (OOM) fout. Dit komt doordat fib(40) ongeveer 1,3 miljard nodes genereert. Bij 48 bytes per node is dat een enorme hoeveelheid data die nooit wordt vrijgegeven.

De Garbage Collector bouwen

Om dit op te lossen, moest ik een garbage collector (GC) bouwen om nodes te verwijderen die niet langer bereikbaar zijn.

Wanneer we bijvoorbeeld $1+1+1$ evalueren, reduceren we delen van de boom naar een literal. De oude kinderen van die node zijn dan niet meer bereikbaar, maar blijven in de allocator staan.

Mark-and-Sweep

Ik heb een mark-and-sweep garbage collector geïmplementeerd:

1. Mark-fase: De GC start bij de wortels (roots) en markeert elke node die nog bereikbaar is. Zodra een node is gereduceerd tot een literal, worden de pointers naar de kinderen op null gezet, zodat de GC ze niet meer kan bereiken.
2. Sweep-fase: De GC loopt door alle chunks. Nodes die niet gemarkeerd zijn, worden toegevoegd aan een freeList.

Wanneer er een nieuwe node nodig is, kijkt het systeem eerst in de freeList om geheugen te hergebruiken voordat er een nieuwe node uit de huidige chunk wordt gealloceerd.

Het resultaat: Het geheugengebruik voor fib(40) daalde van 12 GB naar 1,7 MB.

Er bleef echter één probleem over: fib(40) duurde 6 minuten om te berekenen. Dit komt omdat de mark-and-sweep GC een "stop-the-world" collector is en het algoritme inherent exponentieel is.

Wat kun je verwachten in volgende delen

Ik heb besloten dit project op te splitsen in delen. In toekomstige teksten behandel ik:

• Hoe ik het snelheidsprobleem heb aangepakt met TCO (Tail Call Optimization) en betere evaluatie.
• De implementatie van een lexer en parser.
• De implementatie van een FFI en een REPL.
• De overstap van pointer-dereferencing.
• Het toevoegen van lambda-functies en lokale variabelen.
• De overstap naar een Cheney’s copying collector.

Wat hebben we tot nu toe bereikt?

Tot nu toe is het volgende gerealiseerd:

• Inzicht dat het expressietype een Algebraic Data Type kan zijn.
• Inzicht dat variabelen en functies in feite beide gewoon data zijn.
• Een graph-evaluator die de huidige node muteert na evaluatie.
• Een Environment Table via een custom hashtabel.
• Een custom chunk-allocator voor de nodes.
• Een mark-and-sweep garbage collector om geheugenlekken te voorkomen.

In feite heb ik een Graph Reduction engine gebouwd.

Wacht, kan het nu 1+1 berekenen?

Ja... dat kan het nu. Volgens graphLang is $1+1$ inderdaad 2! (´･ω･`)