= Interpreter arithmetic trace
Use the <compilation arithmetic example> with input $x=7$. An <abstract syntax tree> <interpreter> first reads `x`, obtains $2+3=5$, forms $7\cdot5=35$, and finally computes $35-4=31$. Interpreting the folded <abstract syntax tree> skips the <addition> but gives the same result. The compiled <stack machine> instructions instead produce the following trace; the top of the <stack> is written on the right:
``
instruction stack after instruction
initial []
LOAD x [7]
PUSH 5 [7, 5]
MUL [35]
PUSH 4 [35, 4]
SUB [31]
``
\Image[/interpreter-tree-stack-trace.png]
{title=Execution of `x*(2+3)-4` at $x=7$: the original <abstract syntax tree> and the folded <stack machine> instructions both give $31$}
{id=image-interpreter-tree-stack-trace}
The order in `SUB` is essential: reversing its two popped operands would give $4-35=-31$. The same stored instruction sequence works for input $x=-2$, yielding $(-2)\cdot5-4=-14$, without repeating <parsing> or <constant folding>. An <abstract syntax tree> <interpreter> can likewise reuse its already-parsed tree. Reusing a representation is therefore useful to both approaches; it does not itself distinguish <compilation> from interpretation.
The pleasing part is that a nested <rooted tree> and a flat instruction sequence express the same computation. The <structural induction> in the <compilation arithmetic example> connects them by a precise <stack> property. This tiny language always terminates and has no <side effects>; richer <programming language semantics> require a correctness argument that also accounts for failures, externally visible actions, and possible nontermination.
Back to article page
