// HACKER NEWS — CYBERSECURITY
Needed 1+1, built a functional programming language
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 problem was:
Evaluate 1 + 1 + 1 to 3 using a binary tree.
The operator becomes the root, with its two operands as children.
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.
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:
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: