What we're building: a small scripting language

A programming language is a pile of decisions stacked on top of each other, and the bottom-most decision is the language itself: what a program in it looks like, and what it is allowed to say. Everything downstream — the token types in the scanner, the shape of the AST, the arms of the evaluator’s big match — falls out of that decision. So this track starts by making it deliberately, on paper, before any Rust gets written.

This step finishes the design, not the code. By the end of the article there is a language called birch: a small, dynamically typed scripting language with variables, functions, closures, arrays, if and while. There is one Rust block at the end, a first look at the two enums the whole interpreter hangs off. The code that runs birch starts arriving in the next step, Scanning source into tokens, and takes the rest of the ten-step track. If you want the full itinerary first, the track overview lists every step.

What a birch program looks like

Here is the whole pitch in one program — a closure factory and a loop over an array, which is more than enough to see the language’s personality:

// birch — the language this track builds

fun makeCounter(start) {
  var n = start;
  fun count() {
    n = n + 1;
    return n;
  }
  return count;
}

var tick = makeCounter(0);
print tick();   // 1
print tick();   // 2

var names = ["ada", "grace", "hopper"];
var i = 0;
while i < len(names) {
  print "hello, " + names[i];
  i = i + 1;
}

Reading it, a few things should feel familiar rather than surprising. Braces group blocks. var declares a variable. fun declares a function, and functions are values — makeCounter returns an inner function that keeps using n after makeCounter has returned, which is a closure, and it works without any special ceremony. Arrays have a literal syntax, [1, 2, 3], and are indexed with square brackets. print and len are not keywords: they are ordinary builtin functions, which is why print tick(); needs the same semicolon any other statement needs.

That familiarity is a design choice, and the next section makes it explicit.

The grammar

Here is the complete grammar of birch, in the EBNF-ish notation the rest of the track uses. It fits on one screen, which is the point:

program      → declaration* EOF

declaration  → varDecl | funDecl | statement
varDecl      → "var" IDENT "=" expression ";"
funDecl      → "fun" IDENT "(" parameters? ")" block
statement    → exprStmt | ifStmt | whileStmt | returnStmt | block
exprStmt     → expression ";"
ifStmt       → "if" "(" expression ")" statement ("else" statement)?
whileStmt    → "while" "(" expression ")" statement
returnStmt   → "return" expression? ";" ;
block        → "{" declaration* "}"

expression   → assignment
assignment   → IDENT "=" assignment | logicOr
logicOr      → logicAnd ( "or" logicAnd )*
logicAnd     → equality ( "and" equality )*
equality     → comparison ( ( "!=" | "==" ) comparison )*
comparison   → term ( ( ">" | ">=" | "<" | "<=" ) term )*
term         → factor ( ( "+" | "-" ) factor )*
factor       → unary ( ( "*" | "/" | "%" ) unary )*
unary        → ( "!" | "-" ) unary | postfix
postfix      → primary ( "(" arguments? ")" | "[" expression "]" )*
primary      → NUMBER | STRING | "true" | "false" | "nil" | IDENT
             | "(" expression ")"
             | "[" elements? "]"
arguments    → expression ( "," expression )*
elements     → expression ( "," expression )*

The grammar has two halves, and the split does a lot of quiet work. Everything above the blank line is about statements — declarations, control flow, blocks. Everything below is about expressions — values, operators, calls. A statement does something; an expression produces something. The two only touch in one place: an expression followed by a semicolon is allowed as a statement (exprStmt), which is how tick(); counts as a line of code.

The operator rules are a precedence table in disguise. Each row binds tighter than the one above it, so 1 + 2 * 3 parses as 1 + (2 * 3) not (1 + 2) * 3, purely because factor sits below term in the grammar. When the Pratt parser arrives in the Pratt parser step, this ladder is exactly what it will replace — but writing the ladder first makes the problem concrete.

Why a statement language, not an expression language

Languages like Rust and ML make nearly everything an expression: an if produces a value, a block produces a value, even a match produces a value. Birch does not. An if is a statement; it runs one branch or the other and produces nothing. To get a value out of a decision, you assign inside the branches:

var label = "cold";
if temp > 20 {
  label = "warm";
}

This is the more conservative choice, and it is deliberate, for three reasons.

First, the implementation is what this track is actually teaching. A statement/expression split gives the interpreter two enums — one for statements, one for expressions — instead of one overloaded union where if sometimes has a value and sometimes does not. Two smaller enums with clean arms are easier to pattern-match over, and pattern matching over the AST is where Rust earns its keep in this track.

Second, the error messages stay honest. In an expression language, “this if-expression has branches of different types” is a real diagnostic with real subtleties. In birch, the question never comes up: a statement produces nothing, full stop. Step 8, the error-reporting step, has enough to do without inheriting that problem.

Third, most scripting languages people actually meet — JavaScript in its statement form, Lua, Python — work this way. A reader coming from those languages will find birch’s grammar saying exactly what they already expect.

Why dynamic typing, with exactly one number type

Birch has no type annotations. A variable can hold a number, then a string, then an array:

var x = 40 + 2;
x = "forty-two";
x = [x];

The type lives in the value, not the variable. That is the usual trade for a small language: it drops a whole layer (a checker pass) the track does not have room for, and it makes the evaluator’s job simple — every operation either makes sense for the values it is handed or fails at runtime with a message.

The interesting part is what “a number” means. Birch has exactly one number type, and it is a 64-bit float, the same choice Lua and JavaScript made. No integers, no distinction between 1 and 1.0. It sounds sloppy, but it buys something real: the interpreter’s Value enum gets one numeric variant instead of several, every numeric operation is one f64 operation, and the “0.1 + 0.2 is not exactly 0.3” conversation happens once, up front, instead of as a surprise in the middle of the evaluator. When Value shows up in the evaluator step, it will have five variants — number, string, bool, nil, array — plus one more that appears with functions.

Why braces, keywords, and no significant whitespace

The surface syntax — curly braces, var and fun as reserved words, semicolons required, whitespace meaningless — is the least fashionable set of choices on this page, and the most defensible for a ten-step track.

Semicolons make the grammar unambiguous without a rule that says “insert a semicolon wherever a newline probably ended a statement”. Automatic semicolon insertion is one of the genuinely hard corners of JavaScript’s grammar, and it would eat an entire step of this track for zero payoff. Requiring them costs the writer a character and saves the reader of the parser a week.

Keywords over sigils keep the lexer honest. var, fun, if, while, return, true, false, nil, and, or — each is a fixed word the scanner recognizes as a token kind, and there is no @, $, or := doing double duty. Step 2 will classify every token the scanner produces, and a language whose keywords are just words makes that classification a small, checkable table.

Significant whitespace (Python-style) was ruled out for the same reason: indentation blocks require the lexer to track a nesting stack across blank lines inside brackets, which is a famous source of edge cases. Braces move that complexity from the lexer into the parser, where the grammar already lives.

What the Rust side looks like from here

The grammar is a contract, and the first thing that cashes it in is the AST. Two kinds of node in the grammar, two enums in Rust. Here is the expression half, roughly as it will appear in Representing a program as a tree — one variant per primary/postfix/operator rule:

// the shape everything downstream hangs off
enum BinOp {
    Add,
    Sub,
    Mul,
    Div,
    Eq,
    Lt,
}

enum Expr {
    Number(f64),
    Str(String),
    Bool(bool),
    Nil,
    Variable(String),
    Array(Vec<Expr>),
    Binary { op: BinOp, lhs: Box<Expr>, rhs: Box<Expr> },
    Call { callee: Box<Expr>, args: Vec<Expr> },
    Index { obj: Box<Expr>, idx: Box<Expr> },
}

fn main() {
    // 1 + n, as a tree
    let expr = Expr::Binary {
        op: BinOp::Add,
        lhs: Box::new(Expr::Number(1.0)),
        rhs: Box::new(Expr::Variable(String::from("n"))),
    };

    match expr {
        Expr::Binary { op: BinOp::Add, .. } => println!("an addition"),
        Expr::Binary { .. } => println!("some other binary op"),
        _ => println!("not a binary op at all"),
    }
}

▶Run this in the Rust Playground

an addition

Notice what the grammar bought here. Every primary alternative became a variant. Box shows up exactly where the grammar is recursive in a non-trivial position — a binary operation contains two sub-expressions, which cannot be stored inline without making the enum infinitely sized. The postfix rule, which allows any number of calls and indexings in a row, became two variants used in a loop. And the evaluator, three steps from now, will be one match over Expr with one arm per variant. The grammar is the architecture; this article exists so the rest of the track can be checked against it.

What comes next

The next step, Scanning source into tokens, turns this design into its first running code: a lexer that reads birch source and produces tokens with line and column positions, which is the foundation every later error message stands on. Until then, the track overview is the map of the whole journey.