Stack Machines and Machine Language

So far, the work has been about evaluation: given an expression, find its value. A natural next question is how that skill connects to translating programs into machine language. The answer is less surprising than it first seems. Instead of computing the value of an expression directly, a program could produce a list of machine language instructions that would compute that value. Both approaches start from the same expression, so the real question becomes what those instructions look like and how the structure of an expression can be used to produce them.

Think of the expression as a set of nested operations. The operation that is applied last sits near the top of the tree, and the smaller pieces it works on hang beneath it. A number has nothing beneath it, while an operator has the parts it acts on as its children. Seen this way, the grouping of an expression becomes visible. In the written form, parentheses are needed to show which part is computed first. In the tree, the shape already says so, and no parentheses are needed.

In this diagram, the plus node sits below the multiply node because the sum must be formed before it is multiplied by 2. The leaves, which hold the numbers 3, 4, and 2, have no children. If you read the tree from its leaves up to the root, you follow the order in which the operations must be carried out. This bottom-up reading is the key idea that makes the tree useful for generating instructions.

The source names two kinds of stack operations: push a number, and apply a + operation. A stack machine works with a stack of values. A push operation places a number onto the stack. An apply operation takes values from the stack, performs an operation on them, and leaves a result behind. A complete instruction list is simply a sequence of these operations, executed in order.

The next step is to connect the tree to the instructions. Use the same tree as before, for (3 + 4) multiplied by 2. Read it bottom-up. The deepest operations are formed first, so the first numbers to be pushed are the leaves under the plus node. Then the plus is applied. The 2 is pushed, and finally the multiply is applied. The list can be read straight off the tree's structure.

Notice that the emitted list is a traversal of the tree in which each operator is written only after its two subtrees have been written. The plus is emitted only after 3 and 4, and the multiply only after the plus and the 2. Because a parent operator needs the results of both of its children, this is the only order in which the instructions can be correct. The list is a generated illustration of the idea, not a record of any particular program's output. It shows that each apply appears only after the operands it consumes.

The stack diagram below follows the same instruction list one step at a time. Watch what is on the stack after each instruction, and notice which values are removed and which are added.

At the apply + step, the two values 3 and 4 are removed and the single value 7 is left behind. At the apply * step, the values 7 and 2 are removed and 14 remains. The stack never holds more than two values at once in this run, and it ends with exactly one value, which is the result of the expression.

A flat text such as (3 + 4) * 2 forces the reader to remember which parts are grouped and which operations come first. The tree removes that burden. The grouping is already recorded in the shape of the structure, so a translator can walk the tree and emit instructions without re-deriving precedence or parentheses from the text. The source also notes that SimpleParser3.java can both evaluate an expression and print the stack machine operations for evaluating that same expression, offering the value and the instructions side by side.