The tree and the instruction stream can implement the same language while storing intermediate values differently.
By the end: Trace a stack machine, preserve operand order, and explain how interpretation and compilation meet.
A tree-walking interpreter handles a literal by returning its value and a name by reading its binding. For a binary operation, our semantics evaluate the left subtree, then the right, then apply the operator. A recursive implementation can follow that definition directly.
The compiler performs a related traversal but emits instructions instead of computing the final result. It emits code for the left child, code for the right child, then the arithmetic instruction. The resulting stack bytecode makes the temporary storage and operation order explicit.
The tree evaluator and compiler perform related traversals with different outputs. For a binary node, the evaluator obtains the left value, obtains the right value, and applies the operation. The compiler instead emits instructions for the left child, then instructions for the right child, then the arithmetic instruction. This order is called postorder because a node's own operation follows its children. The compiler does not need to know the values of names to emit their LOAD instructions. The VM reads those values when it executes the code.
Take x * (y - 2). Compilation emits LOAD x, LOAD y, PUSH 2, SUB, MUL. Execution starts with an empty operand stack. Loading x pushes four; loading y pushes seven above it; pushing two makes the stack contain four, seven, two in bottom-first order. SUB consumes seven and two and replaces them with five. Four remains underneath while that right subtree finishes. MUL then consumes four and five and pushes twenty. The tree's nested structure has become a linear sequence plus explicit temporary storage.
The tree evaluator needs temporary storage too. After calculating the left child, its recursive invocation keeps that result while calculating the right child. In a typical implementation, host-language invocation state holds those pending values. The bytecode machine stores them on its operand stack instead. Neither representation eliminates the need to preserve a value until its consumer runs. This is why a tree picture and a stack trace can describe the same computation while appearing quite different. Compare the lifetime of the saved four, not just the final answer.
Parentheses affect the emitted sequence through the tree, even though no parenthesis instruction exists. For (x * y) - 2, multiplication happens before the final literal is pushed. Its code is LOAD x, LOAD y, MUL, PUSH 2, SUB, and the fixed environment gives twenty-six. For x * (y - 2), subtraction happens while x waits on the stack and the result is twenty. Both sequences contain five instructions. Equal length therefore says nothing about equivalent grouping or equal results; the consumer of each temporary matters.
Enter these two expressions in the execution view. Step until two instructions have completed, when both stacks contain four and seven. Predict what happens next before stepping again. The expression x * (y - 2) pushes two, reaching three stack entries; (x * y) - 2 multiplies immediately, leaving twenty-eight. Continue until each finishes, checking where the trees first demand different work. Changing the source replaces and resets the trace, so record the intermediate stacks or use the complete trace rather than trying to preserve two live player states at once.
| Completed step | x * (y - 2) | (x * y) - 2 |
|---|---|---|
| 1 | LOAD x → [4] | LOAD x → [4] |
| 2 | LOAD y → [4, 7] | LOAD y → [4, 7] |
| 3 | PUSH 2 → [4, 7, 2] | MUL → [28] |
| 4 | SUB → [4, 5] | PUSH 2 → [28, 2] |
| 5 | MUL → [20] | SUB → [26] |
SmallExpr specifies left-before-right operand evaluation, and this emitter follows it directly. An implementation of a richer language must respect whatever ordering that language requires, especially when operands can print, throw, or change shared state. Pure wrapping arithmetic sometimes permits alternative schedules with a suitable equivalence argument. That permission would come from semantic reasoning, not from the fact that addition is usually familiar. The current emitter does not search schedules or generate native instructions. It translates the accepted tree into this particular stack instruction language.
PUSH places a literal on the operand stack. LOAD reads a named value and pushes it. ADD, SUB, and MUL pop a right operand and then a left operand, compute the result, and push it. NEG pops one integer and pushes its wrapped negation. The stack is distinct from a call stack used for function invocations.
For 8 − 3, the stack becomes [8, 3] before SUB. Popping three first does not make it the left operand. Correct subtraction is eight minus three. Reversing the pop interpretation silently changes a noncommutative operation, even though addition examples may still appear correct.
A stack determines which value is removed next, but the instruction definition determines that value's role. After code for a binary expression has run, the right child's result is on top of the left child's result. SUB therefore pops the right operand first and the left operand second, then computes left minus right. Treating the first popped value as the left operand reverses subtraction. Addition and multiplication conceal that bug because exchanging their operands preserves the wrapped result.
For 8 - (3 - 1), the instruction sequence pushes eight, three, and one before its first subtraction. The top one is the right operand of the inner subtraction, and the three beneath it is the left operand. Their result two replaces both, leaving eight underneath. The second subtraction uses eight as left and two as right, producing six. For the left-associated source 8 - 3 - 1, the first SUB must occur before PUSH 1. That sequence produces five and then four. Correct pop roles cannot repair an incorrectly ordered emission.
Unary negation gives a useful contrast because it needs no left-versus-right distinction. NEG removes one integer and pushes its wrapped negative. For -(x - y), LOAD x and LOAD y first supply four and seven, SUB produces negative three, and NEG produces positive three. The stack height is unchanged by NEG because one value replaces one value. A leading minus in source is a unary operation in the parsed tree, not part of the lexer's decimal number token. This explains why the compiler emits a separate NEG instruction.
When reading a trace, state its orientation explicitly. The complete table lists stack values bottom first, while the execution picture places the topmost value first vertically. After pushing eight, three, and one, the table ends with one and the picture starts with one. These are two views of the same state. Labeling the end that pops prevents accidental reversal when copying between them. Stack entries are values, not source variables or permanent registers. A consumed result no longer needs its old entry, even if the same numeral appears again later.
Use the left-association preset and stop after the first SUB. The remaining stack must contain five, not negative five and not eight followed by two. Negative five would suggest reversed operand roles; eight followed by two belongs to the differently grouped expression. Now enter -(x - y) and predict both the intermediate negative three and the final positive three. The comparison diagnoses two independent responsibilities: emission chooses which values meet at an instruction, while execution applies that instruction to those values in its specified operand roles.
| Instruction for -(x - y) | Stack, bottom first | Effect |
|---|---|---|
| LOAD x | [4] | Append x’s value |
| LOAD y | [4, 7] | Append y’s value |
| SUB | [−3] | Left 4 minus right 7 |
| NEG | [3] | Replace −3 with its wrapped negative |
The operand stack here is not a call stack for SmallExpr function calls. This language has no calls. The host implementation can still use its own call stack while parsing, emitting, or evaluating trees. Larger virtual machines may keep invocation frames and operand storage in related arrays or entirely different structures. The conceptual distinction remains useful because one structure tracks pending arithmetic values and the other tracks active invocations. This trace does not demonstrate argument passing or a hardware calling convention.
Presets replace the whole source. Editing replaces the current calculation and resets any execution trace. Names: x = 4, y = 7, flag = true. Use ASCII - for subtraction and negation. Arithmetic is signed 32-bit wrapping; booleans are not numbers. See lesson 1 for the full grammar and editor bounds.
Type: int. Direct evaluation: 4. VM result: 4. Original instructions: 5; after folding: 1.
Completed 0 / 5: Before execution. Stack contents are shown below.
| Completed | Instruction | Stack, bottom first |
|---|---|---|
| 0 | Before execution | Empty |
| 1 | PUSH 8 | 8 |
| 2 | PUSH 3 | 8, 3 |
| 3 | SUB | 5 |
| 4 | PUSH 1 | 5, 1 |
| 5 | SUB | 4 |
| Completed operation | Operand stack, bottom first |
|---|---|
| PUSH 8 | 8 |
| PUSH 3 | 8, 3 |
| SUB | 5 |
Stack height supplies a simple invariant that can be checked without calculating values. PUSH and LOAD add one entry. NEG requires one entry and changes the height by zero. ADD, SUB, and MUL require two entries and reduce the height by one. Check the requirement before changing the height. Starting from zero, valid expression bytecode must never request more operands than are present and must finish with exactly one entry. Neither condition alone is sufficient: a sequence can avoid underflow yet leave several unrelated values.
A compiler correctness argument needs a stronger statement than the final count. Code for a well-typed expression should preserve any existing stack prefix and append exactly that expression's value. A literal pushes its value without touching the prefix. A name does the same after lookup. For a binary node, left-child code appends the left value. Right-child code preserves both the original prefix and that left value while appending its own result. The binary instruction then replaces just those two values with the required result. This argument follows the tree structure.
| Instruction stream | Height evidence | Additional result |
|---|---|---|
| PUSH 2; PUSH 3 | 0 → 1 → 2; no underflow | Reject: two final values |
| ADD | Needs 2; starts at 0 | Reject: underflow |
| PUSH true; NEG | Enough entries for NEG | Reject: boolean is not integer |
| PUSH 8; PUSH 3; SUB | 0 → 1 → 2 → 1 | Valid integer result 5 |
Apply the argument to x * (y - 2). During code for the right subtree, the saved four is part of the prefix that must remain unchanged. LOAD y and PUSH 2 append two entries, and SUB replaces only those entries with five. MUL finally consumes four and five because they are now the two operands belonging to the root. A broken instruction that clears the whole stack could return correct answers for tiny isolated expressions while violating this prefix property. Nested expressions would reveal the missing saved value.
Consider three malformed instruction streams as paper examples, not source inputs. PUSH 2 followed by PUSH 3 avoids underflow but finishes with two entries. A single ADD fails immediately because no operands exist. PUSH true followed by NEG has enough entries but violates the integer operand requirement. A height-only checker can distinguish the first two faults but cannot establish the third property. A typed verifier would also track the categories of entries. This VM performs dynamic checks and a final single-result check, not general bytecode verification.
Instruction totals can be derived from the tree. Every literal or name emits one instruction, every binary node emits one, and every unary node emits one. A binary expression tree with four leaves and no unary nodes has three binary nodes, so its code has seven instructions. Fully constant (2 + 3) * (4 - 1) matches that count before folding and becomes one PUSH afterward. Both versions leave one value, fifteen. The count change describes this VM representation. It does not measure elapsed time, dispatch cost, or native CPU work.
Audit a new input, x + -(y * 2), before running it. It has three leaves, two binary operations, and one unary operation, so expect six instructions. Its height trace is one, two, three, two, two, one after successive instructions. Numerically, the multiplication gives fourteen, negation gives negative fourteen, and addition gives negative ten. The maximum stack height is three even though six instructions execute. Instruction count is not a storage requirement, and final stack size does not describe intermediate boundaries.
| Instruction for x + -(y * 2) | Stack, bottom first | Height |
|---|---|---|
| Before execution | [] | 0 |
| LOAD x | [4] | 1 |
| LOAD y | [4, 7] | 2 |
| PUSH 2 | [4, 7, 2] | 3 |
| MUL | [4, 14] | 2 |
| NEG | [4, −14] | 2 |
| ADD | [−10] | 1 |
A successfully compiled expression leaves exactly one value on the operand stack. The lab records every instruction boundary and compares its VM result with a direct tree evaluator in tests. The instruction count is a teaching measure, not a prediction of native runtime cost.
SmallExpr is finite and effect-free, but larger virtual machines also need control flow, calls, exceptions, object storage, and runtime services. Bytecode verification can check properties before execution. A JIT may compile bytecode later, while still depending on the same language semantics and runtime representation.
Direct evaluation and bytecode execution provide two routes from an accepted tree to a value. Agreement is a useful check because the routes manage intermediate results differently. It is not a complete proof if both routes share a mistaken arithmetic helper or interpretation of an operator. For 8 - 3 - 1, independently deriving the left-associated result four tests more than agreement alone. A compiler test should check the emitted order as well as the final value, because commutative examples can conceal swapped operands or incorrectly grouped operations.
Wrapping arithmetic makes independent expectations especially useful. A host language's ordinary multiplication might not implement the required low-bit integer result for every possible operand. SmallExpr uses an integer multiplication operation with the required wrapping behavior. A separate modular-integer calculation can establish the expected negative 426,416,671 for the wrapping preset without depending on either execution route. Both routes must agree with that result. Bounded tests improve evidence without proving correctness for larger languages or other machine representations.
Folding changes the representation before execution while keeping the semantic obligation. For x * (2 + 3), original code loads x, pushes two, pushes three, adds, then multiplies. Folded code loads x, pushes five, then multiplies. With the fixed environment, both return twenty. The transformation removes two abstract instructions and reduces the peak operand stack from three entries to two. It does not replace x with four because this pass folds numeric literal subtrees, not environment bindings. Specializing to known bindings would be a different transformation with different assumptions.
This comparison supports exact statements about instruction count and stack entries, but no measured speed ratio. A VM implementation pays costs for dispatch, value representation, lookup, and other work. A native backend may combine operations, use registers, or impose target-specific operand restrictions. Compilation also costs time and storage. Therefore five instructions becoming three does not establish that execution takes three fifths as long. A timing claim needs an implementation, a workload, and controlled measurements. This lesson supplies a deterministic abstract trace rather than that performance experiment.
Read the execution display as instruction-boundary evidence. Its initial state has completed zero instructions and an empty stack. After one completion, the recorded stack already includes that instruction's effect. Pausing between visual transitions does not expose a processor's internal partial execution. Playback speed changes how quickly the states are presented, not the expression's arithmetic or the VM instruction count. Changing the source resets the trace because the instruction sequence has changed. The complete table provides the same boundaries without requiring you to follow animation timing.
For a final investigation, run x * (2 + 3) in the execution view and note the three-entry peak before ADD. Then inspect the same input in the folding comparison, where original and folded code remain visible together. Predict the folded stack sequence as four, then four and five, then twenty. Explain why each route is correct using the tree, operand roles, and wrapping rules rather than only the matching answer. You have established representation agreement for this example and exact abstract counts, not native-code generation, a universal equivalence proof, or a benchmark.
| Observation | Supported conclusion | Missing evidence for a stronger claim |
|---|---|---|
| Tree and VM return 20 | Agreement for this input | Independent expected values and wider tests |
| Folding changes 5 instructions to 3 | Two fewer instructions in this VM | Implementation-specific timing measurements |
| Peak stack changes 3 entries to 2 | One fewer abstract operand entry | Native register and byte-storage analysis |
| Faster playback reaches 20 sooner | Same states presented sooner | Any evidence of faster program execution |
Trace PUSH 8, PUSH 3, PUSH 1, SUB, SUB. What result does this code compute?
The first SUB combines the top two values, three and one.
| Step | Stack |
|---|---|
| PUSH 8 | 8 |
| PUSH 3 | 8, 3 |
| PUSH 1 | 8, 3, 1 |
| SUB | 8, 2 |
| SUB | 6 |
The stack goes [8], [8,3], [8,3,1], [8,2], then [6]. This code computes 8 − (3 − 1), not the left-associated source 8 − 3 − 1. A compiler for that source must emit the first SUB before pushing the final one.
A compiler emits PUSH 2, PUSH 3 for a single expression and stops. Why does the VM reject the program?
Check the expression contract at the end, not only individual instruction validity.
| Malformed situation | Broken invariant |
|---|---|
| Two values at the end | Exactly one expression result |
| ADD on an empty stack | Enough operands for instruction |
Both instructions are locally valid, but they leave two values. The expression contract requires exactly one result, so the emitted program is incomplete or malformed. Conversely, an arithmetic instruction with too few values fails through stack underflow.
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected passages on an operand-stack VM and operation order. Our six-instruction expression machine is not the book’s VM.
Selected passages on precedence, associativity, ambiguity, and recursive-descent parsing. Our operator set and integer semantics differ from Lox.