Journey 05 TypedAST

Chapter 5: TypedAST

November - December 2025 - When Cons cells stopped being cute

The Problem with Cons

The Lisp-style approach was elegant. It was also a mess to work with:

// What is this?
var thing = ((Cons)expr).Head;
var otherThing = ((Cons)((Cons)expr).Tail).Head;
var yetAnother = ((Cons)((Cons)((Cons)expr).Tail).Tail).Head;

// Car, Cdr, Cadr, Caddr, Cadddr...
// I've made a huge mistake

Everything was object. No type safety. No IDE autocomplete. Just casting and praying.

When I was prototyping, it was fine. When we hit 100+ PRs, it was not fine.

The Solution

Strongly-typed AST nodes:

// Before: mystery box
Cons(Symbol("let"), Cons(Symbol("x"), Cons(Cons(Symbol("+"), ...))))

// After: actual types
public record LetDeclaration(
    string Name,
    Expression? Initializer,
    bool IsConst
) : Declaration;

public record BinaryExpression(
    Expression Left,
    BinaryOperator Operator,
    Expression Right
) : Expression;

var node = new LetDeclaration(
    Name: "x",
    Initializer: new BinaryExpression(
        Left: new NumberLiteral(1),
        Operator: BinaryOperator.Add,
        Right: new NumberLiteral(2)
    ),
    IsConst: false
);

You can see what it is. The IDE knows what it is. The compiler catches mistakes.

The Migration

This wasn't a weekend rewrite. It was 20+ PRs spanning weeks:

• PRs #183-203: Systematic migration from Cons to TypedAST
• Each PR converted a set of constructs
• Both paths ran in parallel with feature flags
• Tests validated both implementations matched

The final blow:

Commit e9647072: "Replace cons-based transformer with TypedAST"

The Evaluator Before/After

// Before: Pattern matching on symbols
if (head == JsSymbols.Let)
    return EvaluateLet(cons, env);
if (head == JsSymbols.If)
    return EvaluateIf(cons, env);
if (head == JsSymbols.Function)
    return EvaluateFunction(cons, env);

// After: Pattern matching on types
switch (node)
{
    case LetDeclaration let:
        return EvaluateLet(let, env);
    case IfStatement ifStmt:
        return EvaluateIf(ifStmt, env);
    case FunctionDeclaration func:
        return EvaluateFunction(func, env);
    // Compiler warns if cases are missing!
}

Nice, right? The compiler became my friend instead of my enemy.

The Node Hierarchy

// Base types
public abstract record Node;
public abstract record Expression : Node;
public abstract record Statement : Node;
public abstract record Declaration : Statement;

// Expressions
public record NumberLiteral(double Value) : Expression;
public record StringLiteral(string Value) : Expression;
public record Identifier(string Name) : Expression;
public record BinaryExpression(...) : Expression;
public record CallExpression(...) : Expression;

// Statements
public record BlockStatement(IReadOnlyList<Statement> Body) : Statement;
public record IfStatement(...) : Statement;
public record WhileStatement(...) : Statement;
public record ForStatement(...) : Statement;

// Declarations
public record VariableDeclaration(...) : Declaration;
public record FunctionDeclaration(...) : Declaration;
public record ClassDeclaration(...) : Declaration;

Clean. Obvious. Maintainable.

What Broke

Nothing!

That's the point of running both paths in parallel. Every test passed on both implementations before we removed the old code.

Is parallel implementation more work? Yes. Does it prevent production disasters? Also yes.

Performance?

Slightly better, actually:

• No more boxing/unboxing for every expression
• Direct field access instead of cons cell traversal
• Better cache locality (fewer pointer chases)

Not a huge win, but every bit helps.

The Lisp Spirit Lives On

We lost the Cons cells but kept the Lisp philosophy:

• Pattern matching on node types (basically just Lisp special forms)
• Recursive descent evaluation
• Environment chains for scoping
• Closures capture their lexical environment

So, the TypedAST is basically just a Lisp evaluator in a type-safe trench coat. :-)

Lessons

1. Prototypes should be throwaway - Cons cells were great for prototyping, bad for production
2. Types are documentation - Self-documenting code is real
3. Parallel migration works - Run both, compare, then switch
4. C# records are perfect for AST - Immutable, pattern-matchable, concise

In short: the migration took weeks. It was worth every hour.

---

Previous: Chapter 4: Test262 Next: Chapter 6: Source Generators - Making the compiler do the boring work

//Roger