DEV Community: Pranav Desai

Needed 1+1, Built a Functional Programming Language

Pranav Desai — Thu, 17 Sep 2026 16:49:53 +0000

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.

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.

But what are functions?
As far as our evaluator is concerned, it is a thing
that consumes arguments on one side and spits out a
result on the other.

    (func node)
    /         \
 (arg 1)    (arg 2)

The initial idea was that they would just be pointers to C
funcs. Seems simple enough.

But there is a huge problem with this: how do
users write their own functions?

But there's another problem.

When a user types code into our language, it can't magically become a native C function pointer. It can only build an AST (a tree of nodes).

If functions are just C pointers, they immediately become opaque values.
What happens when a function returns another function? We need to be able to put that function back into the graph and evaluate it later. But a C function pointer isn't something our evaluator can walk through.

Thus we need a type of node that tells the evaluator
"Hey, I am a function, but my code isn't a C
pointer; it is this tree right here."
It needs to store the body of the function as a tree, so the evaluator can evaluate it over multiple steps. And for our purposes, that is our closure representation.

Instead of a black-box C function, a closure is an
actual node in our graph. It holds the parameter on
one side, and the tree of operations (the body) on
the other.

         (closure)
         /        \
 (parameter)      (body)
                 /      \
              (math)  (literal)

(technically closures also have an environment, but we haven't gotten to local vars yet)

By making the function an actual node, we can pass it
around, return it from other functions, and evaluate
it step-by-step whenever we want!

Now we have functions users can define themselves without ever touching the C code!!!

Alright then, let's actually implement this in C. So what do we need?

If variables and functions are both values, the environment needs to map names to nodes.
So now we can create our env entry as

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

Now our hash table maps the names (key) to the Node * which is the value.

But what is val?

Val is a Node! But our Node doesn't know about closures or native functions yet.
So let's add those to our node definition from before.

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;
};

nativeFuncs are nodes representing our C funcs, while closures are user-defined funcs composed of nodes

native function = opaque C implementation
closure = language-level graph representation

SO. We have assembled our pieces:

A Memory Allocator
An Environment table that holds our vars, c funcs and user-defined funcs
An evaluator that walks down the program and applies functions

Let's execute our first program!!

Right now we don't have a lexer/parser yet, so we can just hand-construct our AST.

What better program to test than the fibonacci sequence!

So I wrote the program. Typed in fib(5).

and...

IT CRASHED

UPGRADING THE MEMORY ALLOCATOR

Why? Because our fib(5) spawned 13k nodes. But our allocator size is only 1024 nodes total!
You might think "Okay, it's obvious: reallocate the block and grow the size. Have it be a dynamic array"
And that's exactly where the problem lies. The thing is, all of our nodes are pointing to each other inside this memory block.
When we realloc it with an increased size, it might get moved to a new memory address.
Completely breaking all of our pointers and causing a segfault!
How do we tackle this problem?

Instead of growing one allocator, we can just chain multiple blocks together!

We can build a linked list of our allocated blocks. When we run out of space in one block, we just allocate a new one and point to it! We don't have to move any data!

This is called a chunk allocator! Each of our blocks is a chunk that stores the memory, and we chain them together like a linked list with a next pointer.

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

We can keep track of the first chunk and the chunk we're currently allocating from.

We have:

A Chunk Memory Allocator (new)
An Environment table that holds both our vars, c funcs and user-defined funcs
An Evaluator that just walks down the program recursively and reduces them using env lookup

Let's execute our first program again

and...

It works!

We get the result 5! 3+2 is 5.

But something weird happened. It was using 1.32 mb of memory.
That's weird, because fib(5) isn't a complex operation.

So I ran fib(10)
It took 40 mb of RAM!!
Okay, well that's weird.
So I had to test it out. I ran a benchmark.

RAM (GB) vs fib(n)

12.29 GB ┤  
11.34 GB ┤                               ╭───
10.40 GB ┤                        ╭──────╯
 9.45 GB ┤                  ╭─────╯
 8.51 GB ┤              ╭───╯
 7.56 GB ┤             ╭╯
 6.62 GB ┤            ╭╯
 5.67 GB ┤           ╭╯
 4.73 GB ┤         ╭─╯
 3.78 GB ┤        ╭╯
 2.84 GB ┤       ╭╯
 1.89 GB ┤      ╭╯
 0.95 GB ┤     ╭╯
 0.00 GB ┼─────╯
         -----------------------------------
         5    10        20                  40

Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing.

Why? Because it spawns approximately 1.3 Billion nodes.

At 48 bytes per node, that's ~62.4 GB worth of node allocations.

The problem is...

We're allocating nodes but never freeing them once their use is over.

To tackle this problem, I had to build a garbage collector.

BUILDING THE GARBAGE COLLECTOR

What does it mean to collect garbage?

Basically, we need to get rid of nodes that the program can no longer reach.

When we evaluate 1+1+1 the evaluator does this:

1. Builds the ast
```
(+)
/ \
(1) (+)
/ \
(1) (1)
```
1. Evaluates left. Left is already a literal. Moves on to right.
1. Right is a function. So it gets evaluated first. And we mutate the tree.

      (+)
      / \
    (1) (2)

But what happens to the two 1s?

They are left sitting in the allocator! They aren't freed until the end of the program!

What we need our garbage collector to do is start from our roots and mark every node that can still be reached.

Now if you notice, when we've reduced a node to a literal, its old children are no longer reachable through that node!

What we could do is, once we mutate to a literal, just null out both children. Then the garbage collector can never reach those old nodes from this part of the graph.

This is called the mark phase. The garbage collector starts from its roots and marks every node it can reach.

Once marking is done, we have the garbage collector go through our chunks and just check if a node is not marked and add it to a linked list called the freeList.

Now when we need a new node, we can reuse one of those nodes instead of allocating another one.

If freeList is empty, only then do we allocate a new node from the current chunk.
Otherwise, we just pop the head and reuse that memory.

This lets us recycle our nodes effectively!!

Let's run the benchmark after applying the gc:

  RAM w/ GC (MB) vs fib(n)
      1.7200 MB ┼
      1.5886 MB ┤                               ╭───
      1.4571 MB ┤                          ╭────╯
      1.3257 MB ┤                    ╭─────╯
      1.1942 MB ┤               ╭────╯
      1.0628 MB ┤             ╭─╯
      0.9314 MB ┤            ╭╯
      0.7999 MB ┤          ╭─╯
      0.6685 MB ┤         ╭╯
      0.5371 MB ┤       ╭─╯
      0.4056 MB ┤      ╭╯
      0.2742 MB ┤     ╭╯
      0.1427 MB ┤ ╭───╯
      0.0113 MB ┼─╯
                 -----------------------------------
                 5    10        20                40

LOOK AT THAT! Our ram usage went down from 12 GIGABYTES -> 1.7 MEGABYTES for fib(40)

That's insane.

But the thing is not yet solved.

fib 40 took 6 MINUTES to evaluate

Why?

The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector.

And the algorithm we're running is inherently exponential.

So we've fixed our memory problem.

But now we have a performance problem.

We can tackle both of these issues.

We can implement a concurrent garbage collector
And we can do something about how we're evaluating fib itself

What to expect in the next parts

This has gone on long enough, so I decided to split it into parts.

how I tackled the speed issue with TCO and better evaluation
implemented a lexer/parser
implemented an FFI...
implemented a REPL
switched from pointer dereferencing...
brought scuffed encapsulation into C
implemented lambda functions
added local vars
set up stuff for a Cheney's copying collector

What have we achieved so far?

Realized our expression type can be an Algebraic Data Type.
Then realized the actual variants are the kinds of data: funcs, vars, literals
Then realized vars and funcs aren't really two different things but both are just data
Implemented a graph evaluator which mutates the current node after eval
Implemented an Environment Table using a custom hashtable
Implemented a custom chunk allocator to allocate our nodes
Realized we were keeping around a ton of garbage and implemented a mark-and-sweep garbage collector

Overall, I built a Graph Reduction engine

WAIT. BUT DOES IT EVALUATE 1+1

Yeah... I mean, now it does.

1+1 is in fact 2 according to graphLang! (´･ω･`)

Anyhow, there's a bunch more stuff I didn't cover here. It's all in the repo.

I cured my adhd with ai.

Pranav Desai — Thu, 28 May 2026 04:52:29 +0000

(not literally, did fix the developer kind tho)

the problem was i had too many projects.
and i needed to manage my day properly and i didnt want to use
obsidian or notion or any of the current tools because its just too much work
i had to spend time outta my day to work into these systems and waste brain power on
just planning. i didnt want to do that at all, also didnt work because forcing yourself to write down
a notion board is genuinly the hardest thing possible. i mean you spend like 40 hours just crafting your board

you would be larping productivity basically.
(i used notion once for an internship about a week was just spent making the board
we didnt even use it because the planning was being done in like google docs and sheets
and someone had to move all the plans to notion just to look productive, its not worth it)
productivity software should not be a bottleneck of productivity

so i decided the best kind of productive software is the one that works with you not against you.
i looked into what i was doing the time i was not programming. and i realized i was just spending my time
talking to gemini/claude about my projects and during these sessions i would come up with new ideas and features
once i got this i would go and update my planning docs.
also these tools would lock you into their echosystems pretty hard.
obsidian being a markdown file only tool is something that i took inspiration from.

it was a very ineffecient system. and the problem was i spent half my time
re explaining to the llms about the project even in the same chat.

this also ruined my workflow. i basically live in the terminal. my entire workflow is around neovim and a bunch of terminal
tools. the only reason i was leaving the terminal was to talk to llms which took me out of the workflow

to combat this i tried using ollama and llama.cpp. self hosting was great, the lightweight models responded instantaneously
but ollama cli and llama.cpp cli were lacking of a good interface and a workflow.
so i looked into tui wrappers of these projects. when i used them i noticed none of them were really treating themselves like
terminal applications properly. they were trying to be gui applications in a terminal which defeats the whole purpose.

so now the solution was clear. i needed:

a terminal native tui interface for ollama
something lightweight so it doesnt hogg up resources
creates 0 friction
reduces my thinking need.
portable format
works well with the shell terminal

and so i came up with qlog, short for quick log.

the first thing i wanted to nail in qlog was the input system.
lotta tui tools create these input fields which are janky they are not feature rich because honestly, a single team working on
a whole tui app cant put enough dedicated time into an input system alone as much as say neovim or emacs devs put into it. they will
not have the huge echosystem that comes with these other tools.
so, i reffered to the old texts. when in doubt reffer to philosophy.
and, we got to the unix philosophy. do one thing and one thing well.
why write a scuffed input implementation when you can hand it off to your $editor
this let me write my prompts in the comfort of neovim with all my plugins and hand crafted config
and honestly this is what i was expecting with the tui tools. they dont leverage the power of the terminal enough.

the next thing i wanted was a good way to build a prompt.
so i added two key things that makes qlog infinitely powerful.
file injection and command piping.

[[filepath]] lets you inject any file you want into your prompt
{{command}} lets you pass in any command's output directly into your prompt these two features essentially give you the full power of your terminal in your tui ollama interface why spend time copying std out when you can just exec command inside your prompt. why spend time copying the contents of a file when you can inject it with filepath

Next thing I wanted was
An agenda planner. once I had a conversation about a project, an llm would read the whole chat and write a good
technical doc in markdown format so it was really portable(you could cat it or less and it would be nice)

Once I had all my project technical docs and progresses I could talk to the llm and it would plan out my day and
produce an Agenda doc. This agenda doc was also stored as a readme and you could access it with a cli command.
You could just drop the cli command into your zshrc or bashrc and you would get reminded of your agenda.

and honestly by this time qlog stopped feeling like an ai app and more of a shell utility which is exaclty what
you would want a productivity tool to be, you want it to be invisible. the more time you are spending trying to think of productivtiy
that much time you are not being productive

The project has an MVP rn (ikik ironic that the project to fix my projects is unfinished)
But honestly, qLog could help me complete qLog. bootstrapping productivity.

Here's the github for those who want to check it out:
https://github.com/PranavDesai-Git/qLog