Part 2 · 1 chapters · ~8 min

ASTs

Concrete versus abstract syntax, designing AST node types as discriminated unions, positions on every node, tree-walking passes and the visitor pattern, AST explorers (astexplorer.net, the TypeScript and Babel ASTs), codemods as AST transformations, and tree-walking interpreters.

Trees as discriminated unions

code

// from src/parser.ts: every node is a tagged object with its position
export type Expr =
  | { k: 'num'; value: number } & Pos
  | { k: 'bool'; value: boolean } & Pos
  | { k: 'var'; name: string } & Pos
  | { k: 'unary'; op: string; e: Expr } & Pos
  | { k: 'binary'; op: string; l: Expr; r: Expr } & Pos
  | { k: 'call'; name: string; args: Expr[] } & Pos;

// a tree-walking interpreter is one function over the union
function evaluate(e: Expr, env: Map<string, number>): number {
  switch (e.k) {
    case 'num': return e.value;
    case 'var': return env.get(e.name)!;
    case 'binary': { const a = evaluate(e.l, env), b = evaluate(e.r, env);
      return e.op === '+' ? a + b : e.op === '-' ? a - b : e.op === '*' ? a * b : Math.trunc(a / b); }
    default: throw new Error(`not handled: ${e.k}`);
  }
}

The same AST machinery powers codemods (Big-company Backend P3 used jscodeshift), linters (ESLint rules are AST visitors), formatters (Prettier prints the AST back out) and bundlers (BYO P7).

SOURCE, TOKENS, TREE

print(fib(i)) as the BYO compiler sees it

swipe the figure sideways, or tap expand for full screen

1/4

concrete text

Source code contains punctuation needed only to parse it: brackets, semicolons.

text with punctuationneeded for parsing only