A programming language can feel like a black box: text enters, behavior emerges, and a compiler or runtime somehow bridges the gap. The fastest way to replace that mystery with a concrete mental model is not to read the implementation of a production language. It is to build a deliberately tiny one.

We will create Pebble, an expression language implemented in TypeScript. Pebble has numbers, booleans, arithmetic, comparisons, variables, anonymous functions, calls, and if/else. That is enough machinery to expose the important boundaries: characters become tokens, tokens become an abstract syntax tree, and the tree is evaluated inside a lexical environment. Functions will be real closures, not substituted strings.

Here is a complete Pebble program:

text
let makeAdder = fn(x) {
  fn(y) { x + y }
};
let add10 = makeAdder(10);
let answer = add10(32);
if (answer == 42) { answer } else { 0 };

The implementation is small enough to reason about, but its architecture scales conceptually to larger interpreters.

From source text to a runtime value

An interpreter is a sequence of representations. Each stage removes accidental detail and adds structure needed by the next stage.

flowchart LR S["Source characters"] --> L["Lexer"] L --> T["Token stream"] T --> P["Pratt parser"] P --> A["Abstract syntax tree"] A --> E["Evaluator"] N["Lexical environment"] --> E E --> V["Runtime value"] subgraph X["AST for add10 32"] C["Call"] --> I["Name add10"] C --> G["Argument 32"] end

The lexer knows that answer is one identifier and == is one operator. It does not know whether answer has been declared. The parser knows that multiplication binds more tightly than addition. It does not know whether operands are numbers. The evaluator resolves names and applies runtime rules.

Keeping those responsibilities separate makes failures precise:

Stage Input Output Example failure
Lexing Characters Tokens Unexpected character @
Parsing Tokens AST Missing ) after arguments
Evaluation AST and environment Value Undefined name total

Note

Pebble interprets an AST directly. “Interpreted” does not mean “unparsed,” and “compiled” does not mean “native machine code.” Parsing is useful in both designs; the difference is what happens after the front end builds a structured program.

Tokens and a lexer with source locations

A token carries a category, the original text, and a source span. Keeping locations from the beginning is essential: reconstructing them after parsing is unreliable.

ts
export type Span = {
  start: number;
  end: number;
  line: number;
  column: number;
};

export type TokenKind =
  | 'number' | 'identifier' | 'let' | 'fn' | 'if' | 'else'
  | 'true' | 'false' | 'leftParen' | 'rightParen'
  | 'leftBrace' | 'rightBrace' | 'comma' | 'semicolon'
  | 'plus' | 'minus' | 'star' | 'slash' | 'bang'
  | 'equal' | 'equalEqual' | 'bangEqual'
  | 'less' | 'lessEqual' | 'greater' | 'greaterEqual' | 'eof';

export type Token = {
  kind: TokenKind;
  lexeme: string;
  span: Span;
  numberValue?: number;
};

const keywords: Record<string, TokenKind> = {
  let: 'let', fn: 'fn', if: 'if', else: 'else',
  true: 'true', false: 'false',
};

The lexer advances monotonically through the source. Whitespace changes positions but emits no token. A digit begins a number; a letter or underscore begins an identifier; punctuation is handled directly. Two-character operators use one character of lookahead.

ts
export class Lexer {
  #offset = 0;
  #line = 1;
  #column = 1;

  constructor(readonly source: string) {}

  scan(): Token[] {
    const tokens: Token[] = [];
    while (true) {
      while (/\s/.test(this.#peek())) this.#advance();
      if (this.#atEnd()) break;
      tokens.push(this.#nextToken());
    }
    tokens.push(this.#token('eof', this.#offset, this.#line, this.#column));
    return tokens;
  }

  #nextToken(): Token {
    const start = this.#offset;
    const line = this.#line;
    const column = this.#column;
    const char = this.#advance();

    if (/\d/.test(char)) {
      while (/\d/.test(this.#peek())) this.#advance();
      if (this.#peek() === '.' && /\d/.test(this.#peek(1))) {
        this.#advance();
        while (/\d/.test(this.#peek())) this.#advance();
      }
      return this.#token('number', start, line, column, Number(this.source.slice(start, this.#offset)));
    }

    if (/[A-Za-z_]/.test(char)) {
      while (/[A-Za-z0-9_]/.test(this.#peek())) this.#advance();
      const text = this.source.slice(start, this.#offset);
      return this.#token(keywords[text] ?? 'identifier', start, line, column);
    }

    const single: Partial<Record<string, TokenKind>> = {
      '(': 'leftParen', ')': 'rightParen', '{': 'leftBrace', '}': 'rightBrace',
      ',': 'comma', ';': 'semicolon', '+': 'plus', '-': 'minus',
      '*': 'star', '/': 'slash',
    };
    const singleKind = single[char];
    if (singleKind) return this.#token(singleKind, start, line, column);

    const pairs: Record<string, [TokenKind, TokenKind]> = {
      '!': ['bang', 'bangEqual'], '=': ['equal', 'equalEqual'],
      '<': ['less', 'lessEqual'], '>': ['greater', 'greaterEqual'],
    };
    const pair = pairs[char];
    if (pair) {
      const kind = this.#peek() === '=' ? (this.#advance(), pair[1]) : pair[0];
      return this.#token(kind, start, line, column);
    }

    throw new LanguageError('lex', `Unexpected character ${JSON.stringify(char)}`, {
      start, end: this.#offset, line, column,
    });
  }

  #peek(distance = 0): string { return this.source[this.#offset + distance] ?? '\0'; }
  #atEnd(): boolean { return this.#offset >= this.source.length; }
  #advance(): string {
    const char = this.source[this.#offset++] ?? '\0';
    if (char === '\n') { this.#line++; this.#column = 1; }
    else this.#column++;
    return char;
  }
  #token(kind: TokenKind, start: number, line: number, column: number, numberValue?: number): Token {
    return { kind, lexeme: this.source.slice(start, this.#offset), numberValue,
      span: { start, end: this.#offset, line, column } };
  }
}

The sentinel \0 makes lookahead at end-of-input harmless. A production lexer may support Unicode identifiers, strings, comments, and numeric separators, but those features should extend the token contract rather than leak character handling into the parser.

Grammar, AST, and Pratt precedence

Before writing parser code, write the language down. Pebble uses semicolons for top-level statements and lets a block end in a value-producing expression.

text
program     -> statement* EOF
statement   -> "let" IDENT "=" expression ";" | expression ";"
block       -> "{" ("let" IDENT "=" expression ";")* expression "}"
expression  -> prefix (binary expression | "(" arguments? ")")*
prefix      -> NUMBER | "true" | "false" | IDENT
             | ("-" | "!") expression | "(" expression ")"
             | "fn" "(" parameters? ")" block
             | "if" "(" expression ")" block "else" block
arguments   -> expression ("," expression)*
parameters  -> IDENT ("," IDENT)*

The AST records meaning, not punctuation. Parentheses affect grouping but do not need their own node.

ts
export type Statement =
  | { kind: 'let'; name: string; value: Expression; span: Span }
  | { kind: 'expression'; expression: Expression; span: Span };

export type Block = { bindings: Extract<Statement, { kind: 'let' }>[]; result: Expression; span: Span };

export type Expression =
  | { kind: 'number'; value: number; span: Span }
  | { kind: 'boolean'; value: boolean; span: Span }
  | { kind: 'name'; name: string; span: Span }
  | { kind: 'prefix'; operator: 'minus' | 'bang'; right: Expression; span: Span }
  | { kind: 'binary'; operator: TokenKind; left: Expression; right: Expression; span: Span }
  | { kind: 'if'; condition: Expression; then: Block; otherwise: Block; span: Span }
  | { kind: 'function'; parameters: string[]; body: Block; span: Span }
  | { kind: 'call'; callee: Expression; arguments: Expression[]; span: Span };

A recursive-descent parser is a natural fit for statements, blocks, functions, and if. Expressions are trickier because precedence and associativity interact. Pratt parsing solves that with binding powers. The left and right powers below make binary operators left-associative; calls bind most tightly.

Form Left/right binding power Example grouping
==, != 1 / 2 a == (b < c)
<, <=, >, >= 3 / 4 (a + b) < c
+, - 5 / 6 (a + b) - c
*, / 7 / 8 (a * b) / c
Prefix -, ! right 9 -(f(x))
Call (...) left 11 (make(1))(2)
ts
const infixPower: Partial<Record<TokenKind, readonly [number, number]>> = {
  equalEqual: [1, 2], bangEqual: [1, 2],
  less: [3, 4], lessEqual: [3, 4], greater: [3, 4], greaterEqual: [3, 4],
  plus: [5, 6], minus: [5, 6], star: [7, 8], slash: [7, 8],
};

class Parser {
  #current = 0;
  constructor(readonly tokens: Token[]) {}

  parseExpression(minimumPower = 0): Expression {
    let left = this.#parsePrefix();

    while (true) {
      if (this.#check('leftParen')) {
        if (11 < minimumPower) break;
        left = this.#finishCall(left);
        continue;
      }

      const power = infixPower[this.#peek().kind];
      if (!power || power[0] < minimumPower) break;
      const operator = this.#advance();
      const right = this.parseExpression(power[1]);
      left = { kind: 'binary', operator: operator.kind, left, right,
        span: mergeSpans(left.span, right.span) };
    }
    return left;
  }

  #parsePrefix(): Expression {
    const token = this.#advance();
    switch (token.kind) {
      case 'number': return { kind: 'number', value: token.numberValue!, span: token.span };
      case 'true': return { kind: 'boolean', value: true, span: token.span };
      case 'false': return { kind: 'boolean', value: false, span: token.span };
      case 'identifier': return { kind: 'name', name: token.lexeme, span: token.span };
      case 'minus': case 'bang': {
        const right = this.parseExpression(9);
        return { kind: 'prefix', operator: token.kind, right, span: mergeSpans(token.span, right.span) };
      }
      case 'leftParen': {
        const expression = this.parseExpression();
        this.#consume('rightParen', "Expected ')' after expression");
        return expression;
      }
      case 'fn': return this.#parseFunction(token.span);
      case 'if': return this.#parseIf(token.span);
      default: throw this.#error(token, 'Expected an expression');
    }
  }
}

#parseFunction consumes a comma-separated identifier list and a block. #parseIf consumes a parenthesized condition, two blocks, and the required else. #finishCall parses zero or more comma-separated expressions. These are ordinary recursive-descent methods; Pratt parsing is needed only where precedence decides when recursion stops.

Warning

Do not encode precedence by repeatedly rearranging an already-built tree. Define it once in the parser. The AST should be correct when it leaves the front end, so every later consumer sees the same grouping.

Evaluation, environments, and runtime values

The evaluator walks the AST. Its values are deliberately narrower than JavaScript values, preventing host-language coercion from silently defining Pebble semantics.

ts
export type RuntimeValue = number | boolean | Closure;

export type Closure = {
  kind: 'closure';
  parameters: string[];
  body: Block;
  environment: Environment;
};

export class Environment {
  readonly #values = new Map<string, RuntimeValue>();
  constructor(readonly parent?: Environment) {}

  define(name: string, value: RuntimeValue): void {
    if (this.#values.has(name)) throw new Error(`Name '${name}' is already defined`);
    this.#values.set(name, value);
  }

  get(name: string, span: Span): RuntimeValue {
    if (this.#values.has(name)) return this.#values.get(name)!;
    if (this.parent) return this.parent.get(name, span);
    throw new LanguageError('runtime', `Undefined name '${name}'`, span);
  }
}

Name lookup starts in the current environment and follows parent links outward. A block creates a child environment, so local bindings do not escape. Shadowing can be allowed by defining the same name in a child, while duplicate names in one scope remain an error.

ts
export function evaluate(expression: Expression, environment: Environment): RuntimeValue {
  switch (expression.kind) {
    case 'number': case 'boolean': return expression.value;
    case 'name': return environment.get(expression.name, expression.span);
    case 'prefix': {
      const right = evaluate(expression.right, environment);
      if (expression.operator === 'minus') return -expectNumber(right, expression.span);
      return !expectBoolean(right, expression.span);
    }
    case 'binary': {
      const left = evaluate(expression.left, environment);
      const right = evaluate(expression.right, environment);
      return evaluateBinary(expression.operator, left, right, expression.span);
    }
    case 'if': {
      const condition = expectBoolean(evaluate(expression.condition, environment), expression.condition.span);
      return evaluateBlock(condition ? expression.then : expression.otherwise, environment);
    }
    case 'function':
      return { kind: 'closure', parameters: expression.parameters,
        body: expression.body, environment };
    case 'call': {
      const callee = evaluate(expression.callee, environment);
      if (!isClosure(callee)) throw new LanguageError('runtime', 'Only functions can be called', expression.callee.span);
      if (callee.parameters.length !== expression.arguments.length) {
        throw new LanguageError('runtime',
          `Expected ${callee.parameters.length} arguments but received ${expression.arguments.length}`,
          expression.span);
      }
      const callEnvironment = new Environment(callee.environment);
      callee.parameters.forEach((name, index) =>
        callEnvironment.define(name, evaluate(expression.arguments[index]!, environment)));
      return evaluateBlock(callee.body, callEnvironment);
    }
  }
}

function evaluateBlock(block: Block, parent: Environment): RuntimeValue {
  const local = new Environment(parent);
  for (const binding of block.bindings) {
    local.define(binding.name, evaluate(binding.value, local));
  }
  return evaluate(block.result, local);
}

The remaining top-level bridge is intentionally plain. A program evaluates statements from left to right in one environment. A let statement defines a binding after its initializer succeeds, and an expression statement replaces the program’s current result. Pebble can either require at least one expression statement or introduce a unit value; this version requires an expression so every successful program has a value.

ts
export function evaluateProgram(statements: Statement[]): RuntimeValue {
  const global = new Environment();
  let result: RuntimeValue | undefined;

  for (const statement of statements) {
    if (statement.kind === 'let') {
      global.define(statement.name, evaluate(statement.value, global));
    } else {
      result = evaluate(statement.expression, global);
    }
  }

  if (result === undefined) {
    throw new Error('A program must contain an expression statement');
  }
  return result;
}

run(source) is now only composition: construct a Lexer, pass its tokens to Parser.parseProgram(), then call evaluateProgram. None of those layers reaches backward. In particular, the evaluator never inspects source strings, and the lexer never imports AST types. This one-way dependency is more than tidiness: it permits parser tests to use hand-written tokens, evaluator tests to use hand-written trees, and a future compiler to consume the same AST without retaining the evaluator.

evaluateBinary should explicitly require numbers for arithmetic and ordering, reject division by zero if that is Pebble’s policy, and define equality without JavaScript coercion. For example, 1 == true is an error or false, never a host-dependent surprise. Central helpers such as expectNumber and expectBoolean keep those rules consistent.

The evaluator is tree-walking: visiting a loop-free AST of nn nodes costs O(n)O(n) excluding function calls, while environment lookup costs O(d)O(d) in a simple parent chain of lexical depth dd. Real engines often resolve each name to a lexical slot before execution, replacing repeated string lookup with indexed access.

Lexical scope makes closures work

The crucial line in function evaluation is environment. A function value retains the environment where the function was created, not where it is later called. That pair of code plus captured environment is a closure.

When makeAdder(10) runs, the call environment binds x to 10. Evaluating the nested fn(y) creates a closure that points back to that environment. The outer call returns, but the environment remains reachable through the closure. Later, add10(32) binds y in a new child scope; lookup finds y nearby and x in the captured parent.

text
global: makeAdder, add10
                  |
                  v
captured call: x = 10
                  ^
                  |
new call: y = 32  -> evaluates x + y

Dynamic scope would instead search the caller’s environment. It can look simpler because functions need not capture anything, but behavior then depends on the call path rather than the source nesting. Most modern general-purpose languages choose lexical scope because a function’s free variables can be understood where it is defined.

Tip

Draw environment chains when debugging closure behavior. If a free variable resolves incorrectly, ask which environment the function captured, which environment the call created, and whether block evaluation inserted another child scope.

Mutation would add complexity. Captured variables must then refer to shared storage cells rather than copied values. Pebble avoids assignment, so bindings are immutable and closure identity stays straightforward. Adding recursion also needs a policy: define the function’s name before creating its closure, or introduce a dedicated recursive binding form.

Diagnostics, tests, and the road toward a compiler

All stages can report one error shape. A diagnostic should identify the phase, location, source line, and actionable expectation.

ts
export class LanguageError extends Error {
  constructor(
    readonly stage: 'lex' | 'parse' | 'runtime',
    message: string,
    readonly span: Span,
  ) {
    super(message);
  }
}

export function formatError(error: LanguageError, source: string): string {
  const line = source.split(/\r?\n/)[error.span.line - 1] ?? '';
  const caret = `${' '.repeat(Math.max(0, error.span.column - 1))}^`;
  return `${error.stage} error at ${error.span.line}:${error.span.column}: ${error.message}\n${line}\n${caret}`;
}

The parser should report the token it actually saw and the construct it expected. For an interactive REPL, synchronize after a parse error at ; or } so one mistake does not suppress every later diagnostic. Runtime errors should carry the span of the operation, not merely the current token, because tokens are gone by then.

Tests should cross stage boundaries as well as isolate them:

ts
import { describe, expect, it } from 'vitest';
import { run } from '../src/run.js';

describe('Pebble', () => {
  it('honors precedence', () => {
    expect(run('1 + 2 * 3;')).toBe(7);
  });

  it('captures lexical bindings', () => {
    expect(run(`
      let makeAdder = fn(x) { fn(y) { x + y } };
      let add10 = makeAdder(10);
      add10(32);
    `)).toBe(42);
  });

  it('does not use caller scope', () => {
    expect(() => run(`
      let f = fn() { missing };
      let caller = fn() { let missing = 1; f() };
      caller();
    `))
      .toThrow("Undefined name 'missing'");
  });

  it('reports arity errors', () => {
    expect(() => run('let id = fn(x) { x }; id();'))
      .toThrow('Expected 1 arguments but received 0');
  });
});

The third test places missing only in the caller’s local scope. A dynamically scoped language would find it, while Pebble correctly follows the environment captured by f and reports an undefined name. Language semantics live in explicit choices like this, not in whichever behavior happens to fall out of the host implementation.

Once the core is stable, extensions become focused changes:

Extension Front-end change Runtime change
Strings String token and literal AST node Concatenation and string equality
Assignment Assignment grammar and AST node Mutable cells and environment update
Arrays Literal and index syntax Array value, bounds policy
Native functions Usually none Host callable value and capability boundary
Bytecode AST-to-instruction compiler Operand stack, call frames, virtual machine

A compiler can reuse the lexer, parser, AST, spans, and many semantic checks. Instead of recursively evaluating the tree, it emits bytecode, WebAssembly, or machine instructions. A bytecode VM pays compilation cost once, then dispatches compact instructions; a JIT collects runtime evidence and specializes hot paths. The front end answers “what program was written?” while interpretation or code generation answers “how will it run?”

Takeaways

  • A language implementation is a pipeline of explicit representations: source, tokens, AST, and runtime values.
  • Lexers classify characters and preserve spans; parsers enforce grammar and precedence; evaluators enforce runtime semantics.
  • Pratt parsing keeps expression precedence in one small table while recursive descent handles larger grammatical forms naturally.
  • Runtime values should be defined by the guest language, not inherited accidentally from JavaScript coercion.
  • Lexical environments and captured definition-time environments are the mechanism behind closures.
  • Diagnostics are part of language design. Preserve locations early and attach runtime failures to AST spans.
  • Focused tests for precedence, scope, calls, and errors protect semantics more effectively than snapshots of internal trees.
  • Interpreters and compilers can share the same front end. Building the tiny interpreter reveals exactly where a future VM or compiler would begin.