Learning how the programming language sausage is made
For the past five years, I’ve been writing code almost every day, building apps, debugging bugs, and, like most developers, occasionally wondering: how does this all actually work under the hood? I could recite terms like “parsing” and “bytecode” if you asked, but in all honesty, they were just fuzzy ideas floating in a mental fog. I had never truly seen what it looks like to turn source code into something a machine understands.
That changed when I read Crafting Interpreters by Robert Nystrom. I followed along and built out jlox, a tree-walk interpreter for a simple scripting language called Lox. It was a deep, humbling, and wildly rewarding journey, like stepping behind the curtain of a magic show I’d been watching my whole career.
This post distills some of what I learned.
From specification to implementation
A programming language consists of two key components: specification and implementation.
The specification is the “what.” It defines how the language functions and what it looks like. It outlines:
- Syntax – how you write code
- Semantics – what the code is supposed to mean
- Whether the language is statically or dynamically typed
- How memory management and garbage collection work
The spec acts like a blueprint for writing instructions. It’s abstract, machine-independent, and focused entirely on describing how a program should behave.
Take JavaScript, for example. It’s defined by the ECMAScript specification. The spec tells us how for loops behave, how functions are declared, and what Array.prototype.map() should do—but it doesn’t prescribe how browsers or engines like V8 or SpiderMonkey should execute those behaviors.
Once you’ve defined the spec, you can begin working on the implementation—the “how.” This is the process of turning source code into machine-executable instructions. There are many strategies for this. You can interpret or compile the language, or both. Many real-world implementations do some form of both, and the line between the two is often blurry, long enough topic for another post.
At the end of the day, implementing a programming language means writing a program that reads source code and produces behavior. This program is known as the language engine, and like all programs, it’s written in another programming language.
What learning about this drilled into me was that writing a language isn’t some otherworldly task—it’s just another program that:
- Reads input (source code)
- Analyzes it (parsing, etc.)
- Decides what to do (evaluate, compile, etc.)
Building a tree-walk interpreter
One of the simplest ways to implement a programming language is by building a tree-walk interpreter. This type of interpreter walks through the abstract syntax tree (AST) that represents the structure of the source code and directly executes it. It’s straightforward to implement, especially for small languages, and offers a great way to understand how programming languages work under the hood.
To build such an interpreter, you typically go through three main stages:
- Scanning
- Parsing
- Evaluation
Each of these stages builds on the previous one. Let’s walk through them step by step.
Scanning
Scanning, also known as tokenization or lexical analysis, is the process of reading the raw source code (a sequence of characters) and converting it into a series of tokens. A token is a meaningful unit in the language, such as an identifier, number, operator, or keyword.
For example, consider this line of code:
a >= 10
A scanner would produce the following tokens:
- IDENTIFIER(“a”)
- GREATER_EQUAL(">=")
- NUMBER(“10”)
These tokens are easier to process than raw text because they are structured and labeled. The scanner typically uses regular expressions or finite automata to recognize patterns in the character stream and group them into tokens.
Parsing
Parsing, also known as syntax analysis, is the process of taking the flat list of tokens produced by the scanner and organizing them into a structured, tree-like representation called the Abstract syntax tree (AST).
While the scanner understands what each token is (e.g., “this is a number”, “this is an operator”), the parser understands how those tokens fit together according to the rules of the language.
An AST is a hierarchical structure that represents the grammatical structure of the code. Unlike raw tokens or source text, the AST captures the meaningful relationships between different parts of the code.
For example, a >= 10, would be represented by the following AST:
≥
/ \
a 10
From my experience, constructing the grammar is often the trickiest part. It’s especially tricky when dealing with things like operator precedence, associativity, and recursive constructs like function calls or nested expressions. This is where iterative experimentation comes in: you often start with examples of valid code, then try to write rules that capture those examples, tweak them when edge cases fail, and test the resulting AST to ensure it reflects the correct structure.
Evaluating the AST (Tree walking)
Once the AST is built, the interpreter walks through it to evaluate the program. This step is where the semantics of the language come into play, what the program means and what it does.
This is called tree walking because the interpreter recursively visits each node in the AST. Each node corresponds to some operation: for example, evaluating a number, retrieving a variable’s value, applying an operator, or executing a statement.
For the a >= 10 example, the interpreter would:
- Look up the value of a in the environment.
- Compare it to the value 10.
- Return true or false based on the result.
Tree-walk interpreters are easy to implement and debug. However, they are relatively slow compared to bytecode interpreters or compiled languages because they involve a lot of recursive function calls and indirect interpretation.