Capstone: Build a Programming Language

print(1 + 2 * 3) prints 9. Every arithmetic expression with mixed operators gives the wrong answer, consistently, and the same expression with explicit parentheses is fine.

The parser treats + and * as equal in binding power and associates left to right, so it builds (1 + 2) * 3. Nothing downstream is wrong: the evaluator is faithfully computing what the tree says.

Special-casing multiplication in the evaluator so it runs first. This produces the right answer for this expression and the wrong tree for every expression, and it breaks immediately on 2 * 3 + 4, on parenthesised subexpressions, and on anything that inspects the AST rather than evaluating it.

Fix the binding powers in the parser, then verify by printing the tree rather than the result. Add the standard mixed-operator cases to the test suite — including unary minus, which is the next one to break.

A program crashes deep inside evaluation with a null reference. The reported line is inside the interpreter, not inside the user’s program, and the actual mistake is a typo in an identifier three files away.

Names are being looked up at evaluation time rather than resolved in a pass. A name that never gets evaluated is never checked, so the error surfaces on the path that happens to run rather than at the declaration that is missing.

Catching the null and reporting "undefined variable" from the evaluator. It converts a crash into a message and leaves the real problem intact: the error still only appears when that path executes, so it still reaches production through any branch the tests do not cover.

Add a resolution pass that walks the whole tree before execution, binds every use to a declaration, and reports the unresolved ones with the span of the use and a suggestion from the names in scope.

Adding a number to a string produces something plausible and wrong — a concatenation where arithmetic was intended — and it propagates silently until a comparison much later behaves strangely.

There is no type checker. The evaluator coerces whatever it is given so that every operation succeeds, which means the program never fails at the point where it stopped making sense.

Adding a run-time check inside the addition operation that throws on mismatched operand kinds. It moves the failure earlier, which is an improvement, but it still only fires on the executed path — and it has now committed the language to checking at run time, which is a design decision made by accident.

Write the typing rules down, implement a checker pass over the annotated tree, and report the expected type, the found type and the span. Decide deliberately what remains a run-time check, and say so in the language documentation.

A function that returns a lambda works when the lambda is called immediately and returns nonsense when it is called later. In a loop, every closure produced sees the same final value.

The captured variable lives in the enclosing frame, and the frame is gone by the time the closure runs. The closure holds a reference to storage that has been reused.

Copying the captured values into the closure at creation. It fixes the crash and breaks mutation: a counter incremented through the closure no longer changes the original, and two closures over the same variable stop agreeing — a subtler bug that will be found much later.

Do closure conversion properly: move captured variables into a heap-allocated environment shared by the closure and the enclosing scope, and make the closure a pair of code pointer and environment. Then let escape analysis, later, put the environment back on the stack when it provably cannot escape.

A numeric loop that takes milliseconds in an established language takes seconds here. The profile is flat: no single function dominates, and the time is spread across the evaluator.

A tree-walking interpreter re-dispatches on node kinds every iteration and re-resolves names on every access. The work per operation is dominated by interpretation overhead, not by the operation.

Adding a cache to the evaluator — memoising node lookups, or caching resolved variables on the AST node. It buys a small constant factor, adds invalidation bugs the moment scopes are reused, and leaves the structural problem exactly where it was.

Compile to bytecode so the dispatch happens once per instruction instead of once per node, resolve names to slot indices at compile time, and then add the optimizations that remove instructions — because removing an instruction removes a dispatch.

A function with many live values compiles, but the generated code is dense with loads and stores, and it runs slower than the same function compiled with fewer locals.

More values are live simultaneously than there are physical registers, so the allocator is spilling — and it is choosing badly, spilling values used inside the loop rather than values used once outside it.

Increasing the number of registers the allocator may use, past what the target actually has. The generated code then references registers that do not exist, or clobbers ones the calling convention reserved, and the failure appears as memory corruption in the caller rather than as an error in the callee.

Fix the spill heuristic first: weight each value’s spill cost by the loop depth of its uses, so a value used every iteration outranks one used once. Then reduce pressure at the source — split the live range, rematerialize cheap values at their uses, and check whether an over-eager CSE created the pressure in the first place.

Each file compiles cleanly. Linking fails with an undefined symbol whose name only half resembles the function that was written, and a second attempt produces a duplicate-symbol error instead.

The two sides disagree about the symbol. One was compiled with a mangled name encoding parameter types and the other without; or the same generic body was emitted in both objects with strong linkage, so the linker sees two definitions of the same thing.

Renaming the function until the link succeeds. That silences the message and can leave the caller and callee disagreeing about the calling convention or the argument layout, which becomes a crash at run time that has nothing visibly to do with the rename.

Read the mangled name and decode it — the symbol says exactly what the compiler expected. Make the mangling scheme deterministic and shared, mark definitions that may be emitted more than once as mergeable, and add a link step to the test suite so this fails at build time rather than at deployment.

A function written once over a type parameter has to be compiled. Nothing in the front end says whether the body should be emitted once or once per instantiation, and the answer changes the runtime representation of every value it touches.

Erasure, reification and monomorphization are three different implementation strategies that the same source syntax hides. The choice determines whether values are boxed, whether calls inside the generic can be inlined, whether the type argument exists at run time, and how large the binary gets.

Monomorphizing everything because it produces the fastest code in the benchmark. Instantiation is transitive — a generic calling a generic multiplies — and compile time and binary size grow with it until the build becomes the problem, long after the decision is embedded in the ABI.

Decide from the language’s actual constraints and write the decision down. If binary size and compile time matter, erase and pay for boxing. If per-type speed matters, monomorphize and budget the code growth. If the type must be inspectable at run time, reify it and pay for the metadata.

A function needs to pause mid-body, return to its caller, and resume later at the same point with its locals intact. Nothing in the compiler’s model of a function supports this: a native frame is destroyed when it returns.

Suspension is not a function call. Every local live across a suspension point has to survive the frame going away, and the body has to become re-enterable at each of those points.

Running the body on a separate thread and blocking it at each suspension. It works for a demo and gives you one operating-system thread per pending operation, which is the exact cost the async design existed to avoid — and it silently changes the concurrency model of the language.

Lower the body to a state machine: one state per resume point, with every live-across-suspend local promoted to a field of a generated object. Accept the consequence — stack traces and lifetimes no longer match the source shape — and emit the debug metadata that lets a debugger reconstruct them.

A guard written to catch an overflow works in the debug build and is absent from the optimized one. The generated code jumps straight past the check, and the program corrupts memory instead of reporting an error.

The check is written in terms of an operation the language says is undefined on overflow, so the optimizer concluded the overflow cannot happen and the condition is always false. The check was removed as dead code, which is a legal transformation given that premise.

Lowering the optimization level for that file. The symptom goes away, the undefined behavior stays, and it will reappear the next time anything about the surrounding code changes — including in a different file after link-time optimization.

Rewrite the check so it does not depend on the undefined operation: test before the operation rather than after, or use the language’s checked or wrapping arithmetic. Run a sanitizer over the test suite to find the other places where the same pattern is hiding.