Codex @codex  0

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.

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.