How does a computer evaluate an expression?
You type 1 + 2 * 3 and get 7. But to a computer, that's just a string of characters -- it has no idea what + or * means. So how does it figure it out? It turns out the answer involves one of the most elegant ideas in computer science.
See the characters, not the string
To you, 1 + 2 * 3 is obvious. To a computer, it's just nine characters: 1, , +, , 2, , *, , 3. It doesn't know that + means "add" or that * means "multiply."
The first step is tokenization: scanning the characters and grouping them into meaningful chunks called tokens. Think of it like reading -- you don't process one letter at a time, you recognize whole words. That's what the tokenizer does: it turns a stream of characters into a list of meaningful pieces.
The problem: which operation goes first?
Now we have tokens, but we've hit a wall. Look at 1 + 2 * 3. If we just go left to right -- add first, then multiply -- we get 9. But the correct answer is 7, because multiplication should happen before addition.
A flat list of tokens doesn't capture this. The tokens just say "number, plus, number, times, number" -- there's nothing in that list that tells us which operation to do first. We need a data structure that can represent priority. And that's exactly what a tree gives us.
(1 + 2) * 3 = 9
Left-to-right without precedence
1 + (2 * 3) = 7
Multiplication binds tighter
| Precedence | Operators | Associativity |
|---|---|---|
| Highest | ! - (unary) | Right |
* / % | Left | |
+ - | Left | |
< <= > >= | Left | |
== != | Left | |
&& | Left | |
|| ?? | Left | |
?: (ternary) | Right | |
| Lowest | |> (pipe) | Left |
The tree: where it all clicks
Here's the key insight: in a tree, deeper nodes get computed first. If we put 2 * 3 deeper than + 1, multiplication automatically happens before addition. We don't need special rules during evaluation -- the structure itself encodes the order of operations.
This is called an Abstract Syntax Tree (AST). The parser's entire job is to read the flat token list and build this tree, placing higher-priority operations deeper. Once you have the tree, the hard problem of "what order?" is already solved. Try changing the expression below -- notice how * and / always sit deeper than + and -.
Walking the tree to get an answer
Now comes the satisfying part. We have a tree -- how do we get a number out of it? Start at the bottom. The leaves are just values: 1, 2, 3. They're already "solved."
Then work upward. Each operator node looks at the values its children produced and computes a result. * sees 2 and 3, produces 6. Then + sees 1 and 6, produces 7. The final answer bubbles up to the root. Hit play to watch it happen.
The same idea scales to everything
So far we've only seen numbers and arithmetic. But real expressions have variables, function calls, conditions, even pipelines like items |> filter(active). Does the tree idea still work?
It does -- beautifully. Every new feature just adds a new kind of node. A ternary ?: becomes a node with three children. A pipe |> becomes a node where the left child feeds into the right. The rule never changes: deeper nodes get computed first, and results bubble up. Hover over a node to see exactly which part of the expression it represents.
Why compute what you already know?
Imagine evaluating x + 2 * 3 a million times with different values of x. Every single time, the evaluator walks down to 2 * 3, multiplies them, and gets 6. But that subtree has no variables -- the answer is always 6. Why keep recomputing it?
This is constant folding: the compiler walks the tree before evaluation and looks for subtrees where every leaf is a literal. When it finds one, it evaluates it on the spot and replaces the entire subtree with a single number. The tree gets smaller, and the evaluator has less work to do -- for free, on every future run.
Try it yourself
Characters become tokens. Tokens become a tree. The tree encodes priority. Walking the tree produces the answer. And the compiler shrinks the tree before you even start. That's the whole pipeline -- and it all runs live in the Playground.