Task Representation and Domain-Specific Primitives

The $n$-th problem is to solve all Hanoi instances up to instance $n$. Following our general rule, we represent the dynamic environment for task $n$ on the $n$-th task tape, allocating $n+1$ addresses for each peg, to store the order and the sizes of its current disks, and a pointer to its top disk (0 if there isn't one).

We represent pegs $S,A,D$ by numbers 1, 2, 3, respectively. That is, given an instance of size $n$, we push onto data stack ds the values $1, 2, 3, n$. By doing so we insert substantial, nontrivial prior knowledge about the fact that it is useful to represent each peg by a symbol, and to know the problem size in advance. The task is completely defined by $n$; the other 3 values are just useful for the following primitive instructions added to the programming language of Section A: Instruction mvdsk() assumes that $S,A,D$ are represented by the first three elements on data stack ds above the current base pointer $cs[cp].base$ (Section A.1). It operates in the obvious fashion by moving a disk from peg $S$ to peg $D$. Instruction xSA() exchanges the representations of $S$ and $A$, xAD() those of $A$ and $D$ (combinations may create arbitrary peg patterns). Illegal moves cause the current program prefix to halt. Overall success is easily verifiable since our objective is achieved once the first two pegs are empty.

Back to OOPS main page