The Abstract Syntax Tree

From S-Expressions to Real Tree Nodes

So far, "the AST" has been implicit — tuples or S-expression strings good enough for debugging. Now you'll give it real structure: a small hierarchy of node types that the rest of the interpreter (and eventually the compiler) will operate on directly.

The Four Expression Node Types

Every expression your parser can produce reduces to one of exactly four shapes:

This is the same shape your parser has been building all along — you're just giving it named classes instead of tuples, which matters because the evaluator (next) needs to dispatch on node type, and named classes make that dispatch explicit rather than positional.

The Visitor Pattern, or Just isinstance

Two common designs for walking a tree of these node types:

1. Type dispatch (simplest for a first interpreter): a function with a chain of isinstance checks, one per node type.
2. Visitor pattern: each node type has an accept(visitor) method that calls back into a type-specific visit_Binary, visit_Unary, etc. This scales better once you have multiple tree-walkers (a printer, an evaluator, a resolver, a compiler), because adding a new walker doesn't require touching the node classes at all — only adding a new visitor class.

For a small interpreter, isinstance dispatch is perfectly fine and easier to read:

Truthiness and Dynamic Typing

Your language needs a rule for what counts as "true" in a boolean context. The classic Lox-style rule: everything is truthy except false and nil. Notably, 0 and "" (empty string) are truthy — unlike Python or JavaScript, where 0 and "" are falsy. This is a deliberate simplicity choice, and it's exactly the kind of small-but-consequential design decision that a language implementer has to make explicit and document, because it silently affects every if and logical operator downstream.

+ Does Double Duty

The + operator here needs to support both numeric addition (1 + 2) and string concatenation ("hello" + " world"). That means the evaluator needs a runtime type check on both operands before deciding which behavior to apply — and a sensible runtime error (not a Python TypeError leaking through) when someone mixes types, e.g. 1 + "two". This is your first taste of a runtime error as distinct from a scan-time or parse-time error: the code is syntactically valid, but fails when it's actually evaluated, so the error must be caught during tree-walking, not during parsing.