Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof / 6

A zero-address instruction has no explicit operand addresses, so its operands and result location must be implicit in the instruction set architecture. A stack machine supplies these naturally: operations remove their inputs from the top of an operand stack and push the result. A fixed-processor register design is logically possible, so “almost certainly” is appropriately weaker than a proof that only a stack machine could work.

Write the stack from bottom to top, with its top on the right. Let $S$ stand for any unchanged prefix. Suitable effects areThus add pops two operands and pushes one sum, reducing stack occupancy by one. The special const c instruction pushes its immediate constant and increases occupancy by one. Only const needs an explicit value in its encoding.

Use two zero-address instructions for indirect access to computer memory. Define load to replace the top memory address by the value at that address, and define store to pop a value followed by the address just beneath it:Both have no encoded address operand; the stack supplies it. If the known fixed memory addresses of the variables are $p_x,p_y$, implement the assignment withThe successive stack suffixes are $p_x$, then $p_x,p_y$, then $p_x,M[p_y]$, then empty. HenceThe surrounding stack is restored. Other store conventions are possible, but the operand order must be stated and used consistently.

A computed memory address is just another integer on the operand stack. For a pointer held at fixed address $p$, const p; load obtains the pointed-to address; another load obtains its contents. More generally, any expression that leaves an address on top may be followed by load, or may be retained beneath a computed value for store.

For an array whose base address is $b$ and whose element size is $w$ address units, the address of entry $i$ is $b+wM[p_i]$, where $p_i$ stores the index. Add zero-address instructions mul and dup, with dup mapping $S,p$ to $S,p,p$. A suitable sequence isThe first six instructions leave the element address $p=b+wM[p_i]$. The remaining suffix evolves aswith the final effectThe address is computed once and duplicated, so both accesses refer to the same array element. For unit-sized elements omit const w; mul. If the base address is itself held in a variable, replace const b by the instructions loading that variable's value. No instruction other than const requires an explicit operand.

Let $d_e=\mathrm{depth}(e)$ and $d_f=\mathrm{depth}(f)$ measure the extra operand stack space required from the current base, with each evaluation leaving one result. Evaluating $e$ first uses $d_e$ slots. Its result occupies one slot while evaluating $f$, so that stage uses $1+d_f$ slots. The final add reduces two slots to one. ThusBy commutativity of addition, choose the smaller of these two bounds. Evaluate the child of larger depth first. The optimum recurrence on a binary expression tree isAssign depth one to a literal or a simple already-addressable value, and compute the child depths recursively. If $d_e>d_f$, the depths are integers, so $d_e\ge 1+d_f$; evaluating $e$ first therefore attains $d_e$, while reversing the order needs $d_e+1$. If the depths are equal, whichever child goes second needs the extra retained-result slot. These lower bounds prove the recurrence is optimal for evaluating each child subtree without interleaving or spilling. Apply it at every node to minimize peak operand stack occupancy for the given binary expression tree; this is optimal stack evaluation of a binary expression tree.

This changes child evaluation order, not the parenthesization. For example, a chain-shaped binary expression tree can have depth two, whereas a balanced tree of eight leaves has depth four under this model. The reordering assumes expressions have no order-sensitive side effects or observable exceptions. Reassociating floating-point addition would require additional care because it can change floating-point rounding.

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:

Both preserve the same peak operand stack bound: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.