= Solution
Fix `sub` to mean $S,u,v\mapsto S,u-v$. If the depth-minimizing order evaluates the right operand $f$ before the left operand $e$, the <stack> ends in $S,f,e$, so ordinary `sub` would compute the wrong sign. Two possible <instruction set architecture> extensions are:
* Add `swap`, with $S,u,v\mapsto S,v,u$. After computing $f$ and then $e$, use `swap; sub` to obtain $e-f$. One general <zero-address instruction> handles every noncommutative binary operation and is useful elsewhere, but each reversed evaluation needs an extra instruction and extra execution time. It can be implemented without an additional operand <stack> slot.
* Add reverse-operand variants, such as `rsub` with $S,u,v\mapsto S,v-u$, and analogously reverse division and other required operations. After computing $f$ and then $e$, a single `rsub` obtains $e-f$. This avoids the extra executed `swap`, but requires more opcodes and decoder support, usually one reverse form for each affected operation.
Both preserve the same peak operand <stack> bound:
$$
\boxed{\text{deeper child first; use either operand swapping or a reverse-operand opcode.}}
$$
The first trades extra dynamic instructions for a smaller instruction set; the second trades a larger instruction set for fewer executed instructions. Neither extension makes order-sensitive <side effects> safe to reorder.
Back to article page
