Random-access stored-program machine
The Random Access Stored Program (RASP) machine is an abstract machine model used in theoretical computer science for the purposes of algorithm development and algorithm complexity theory.
The RASP is a Random Access Machine (RAM) model that, unlike the RAM, has its program in its registers together with its input. Thus the RASP is to the RAM as the Universal Turing machine is to the Turing machine; and it is an example of the von Neumann architecture whereas the RAM is an example of the Harvard architecture.
The RASP is closest of all the abstract models to the common notion of computer. Unlike actual computers the RASP model usually has a very simple instruction set, greatly reduced from those of CISC and even RISC processors to the simplest arthmetic, "move", and "test/jump" instructions.
Together with the Register machine , the RAM, and the pointer machine the RASP makes up the four sequential machine models, called this to distinguish them from the parallel machine models [cf van Emde Boas (1990)].
Informal definition: Random Access Stored Program model (RASP)
[The following is a rough cut, a work in progress]
The RASP is a Universal Turing Machine (UTM) "built on" a RAM chassis.
The reader will remember that the UTM is a Turing machine with a "Universal" finite-state table of instructions that can interpret any well-formed "program" written on the tape as a string of Turing 5-tuples, hence its universality. While the classical UTM model expects to find Turing 5-tuples on its tape, any program-set imaginable can be put there given that the Turing machine expects to find them -- given that its finite-state table can interpret them and convert them to the desired action. Along with the program, printed on the tape will be the input data/parameters/numbers (usually to the program's right), and eventually the output data/numbers (usually to the right of both, or intermingled with the input, or replacing it). The "user" must position the Turing machine's head over the first instruction, and the input must be placed in a specified place and format appropriate to both the program-on-tape and the finite-state machine's instruction-table.
The RASP mimics this construction: it places the "program" and "data" in the holes (registers). But unlike the UTM the RASP proceeds to "fetch" its instructions in a sequential manner, unless the conditional test sends it elsewhere.
A point of confusion: two sets of instructions: Like the UTM, the RASP model has two sets of instructions -- the state machine table of instructions (the "interpreter") and the "program" in the holes. The two sets do not have to be drawn from the same set.
The following example moves the contents of hole (register) #18 to hole (register) #19, erasing contents of #18 in the process.
| PC | IR | ||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 19 | 5 | H | n | ||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n |
As the RASP machine interprets the instructions, what exactly will its state machine be doing? Tradition divides its actions into two major "phases" called Fetch and Execute. We will observe below that there are "sub-phases" within these two major phases. There is no agreed-to convention; every model will require its own precise description.
Fetch phase: The state machine has access to all the registers, both directly and indirectly. So it adopts #1 as "the program counter" PC. Upon start it expects to find a number in #1PC -- the number of the first instruction (#5). Using a "sub-routine" the state machine copies the pointed-to instruction into #2. This is a bit arduous. The state machine indirectly decrements the pointed-to instruction-hole while directly incrementing (empty) instruction holes #2. During the "parse" phase it will restore the sacrificed instruction-hole by sacrificing the count in #2.
The point of this demonstration: that life would be much easier if the state machine had access to two kinds of indirect copy: copy indirect from i and direct to j, copy direct from i and indirect to j.
The following example shows what happens during the state-machine's "fetch" phase. The state-machine's operations are listed on the far-left column. Observe that at the end (step 11) the instruction hole #5 is empty while hole #2 contains the number 3 that represents the first instruction JE:
| PC | |||||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 19 | 5 | H | n | ||||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| 1 | fetch_instr: | JZi 1,parse | 5 | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 2 | DCRi 1 | 5 i | [2] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| 3, 4 | INC 2; J *-2 | 5 | [1] | 2 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 5 | JZi 1,parse | 5 i | 1 | [2] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 6 | DCRi 1 | 5 i | 1 | [1] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 7,8 | INC 2; J *-2 | 5 | [2] | 1 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 9 | JZi 1,parse | 5 i | 2 | [1] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 10 | DCRi 1 | 5 i | 2 | [0] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 11,12 | INC 2; J *-2 | 5 | [3] | 0 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 13 | JZi 1,parse | 5 i | 3 | [0]! | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 14 | parse_instr: | etc |
Parse phase: Now that the state machine has the number of the instruction (e.g. 3 = JZ) in hole #2 -- now called "the instruction register" IR -- it procedes to decrement the number until the IR is empty while at the same time using the indirect INCi to reconstruct the instruction in hole #5.
If the IR hole #2 were empty before decrement then the instruction would be 0 = HALT, and the machine would jump to its "HALT" routine. After the first decrement, if the hole were empty the instruction would be INC, and the machine would jump to insruction "inc_routine". After the second decrement, the empty hole would represent DEC, and the machine would jump to the "dec_routine". After the third decrement, the hole is indeed empty, and this causes a jump to the "JZ_routine" routine. If an unexpected number were still in the IR, then the machine would have detected an error and could HALT (for example).
Observe that the state-machine's first action of the "execute" phase of the "JZ_routine" is to increment the PC hole #1. This, in essence, moves "the pointer" (head) to the next hole #6.
| PC | IR | ||||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 19 | 5 | H | n | ||||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| 14 | parse: | JZ 2,halt | 5 | [3] | 0 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||
| 15 | Dec 2 | 5 | [2] | 0 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 16,17 | INCi 1; J *-2 | 5 i | 2 | [1] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 18 | JZ 2,dec_routine: | 5 | [2] | 1 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 19 | DEC 2 | 5 | [1] | 1 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 20,21 | INCi 1; J *-2 | 5 i | 1 | [2] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 22 | JZ 2,inc_routine | 5 | [1] | 2 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 23 | DEC 2 | 5 | [0] | 2 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 24,25 | INCi 1; J *-2 | 5 i | 0 | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 26 | JZ 2,JZ_routine: | 5 | [0]! | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | halt: | HALT | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| -- | inc_routine: | etc. | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| -- | dec_routine: | etc. | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| -- | JZ_routine: | etc. | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n |
Execute phase, JZ_routine: Now the finite state machine knows what instruction to execute; indeed it has jumped to the JE "Jump if Empty" sequence of instructions. The JZ instruction has 2 operands -- (i) the number of the hole to test, and (ii) the address to go to if the test is successful (the hole is empty).
(i) Operand fetch -- which hole to test for empty?: Analogous to the Instruction-fetch phase, the finite state machine moves the contens of the hole pointed to by the PC, i.e. hole #6 into #2. It then uses the contents of hole #2 to point to the hole to be tested for zero, i.e. hole #18. Hole #18 contains n pebbles. So there are two eventualities (ia), hole #18 is empty, (ib) hole #18 is not empty.
(ia): If hole #18 is empty then the state machine jumps to (ii) Operand fetch -- jump-to address.
(ib): If hole #18 is not empty then the state machine can skip (ii) Operand fetch. It simply increments twice the PC hole #1 and then unconditionally jumps (go-to) to the instruction-fetch phase.
(ii) Operand fetch -- jump-to address. If the hole #18 is empty, the state machine would proceed to move the contents of hole #8 (it contains the address) to both the PC #1 and to #2. It would then Move the contents of #2 to #8, thus restoring the operand. Now the PC #1 holds jump-to address,so the state machine will unconditionally go to the instruction fetch phase.
| PC | IR | ||||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 19 | 5 | H | n | ||||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| 27 | JZ_routine | INC 1 | [6] | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||
| 28 | JZi 1, jump | 6 i | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 29 | INC 2 | 6 | [2] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 30,31 | DECi 1; J *-2 | 6 i | 2 | 3 | [17] | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | repeat 27-31 until <6> = 0 | 6 i | [18] | 3 | [0]! | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | test hole: | JZi 2,jump | 6 | 18 i | 3 | 0 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | [n] | |||||
| -- | no_jump: | Move <2> , <<1>> | 6 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||
| -- | INC 1 | [7] | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | INC 1 | [8] | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | JUMP to instruction_fetch | 8 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 1 | fetch_instr: | JZi 1,parse | 8i | 0 | 3 | 18 | 15 | [2] | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||
| -- | etc | ||||||||||||||||||||
| -- | jump: | Move <<1>> , <2> & <3> | 7i | [15] | [15] | 3 | 18 | [0] | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||
| -- | Move <3> , <<1>> | 7i | 15 | [0] | 3 | 18 | [15] | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||
| -- | Clear #1 | [0] | 15 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | Move #2 to #1 | [15] | [0] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| -- | JUMP to instruction_fetch | 15 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | ||||||
| 1 | fetch_instr: | JZi 1,parse | 15i | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | [0] | n | |||||
| -- | etc |
Alternate finite-state machine instruction sets
The article Register machine discusses alternate instruction sets in more detail. The two most primitive are the following:
- { INC h; DEC h; JZ h,xxx }
- { INC h; CLR h; JE ha=hb,xxx }
The second set closely resembles the Peano axioms and is useful for certain proofs related to undecidability.
An effective expanded set of finite-state instructions is the Shepherdson-Sturgis model:
- { INC h; DEC h; COPY a,b; CLR h; JE h,xxx; J xxx }
Indirection adds the following instructions:
- { INCi h; DECi h; COPY << a >> , < b >; COPY < a >,<< b >>; CLRi h; JEi h,xxx; Ji h }
COPY: Perhaps the most useful of the added instructions. As illustrated above, had the RAM's state machine been equipped with a pair of "move" instructions, or better yet a pair of COPY instructions, its life as a RASP would have been much easier. The brackets are used here to reduce confusion:
- COPY <<a>>, <b>
- Use the contents of a as the pointer to the "source" register s, and copy the contents of the source register s to b
- COPY <a>, <<b>>
- Use the contents of b as the pointer to the "destination" register d, and copy the contents of a to the destination register d
These two, together with the direct COPY are adequate:
- COPY <a> to <b>
As will be discussed below, because the state machine is bounded, in the abstract models use of an "immediate" COPY of a constant from the state machine's instructions into a register presents a problem, i.e. this is not allowed:
- COPY k to <b>
CLR h: The example RASP had need of a "clear-to-zero" instruction. Without this instruction the finite state machine must count down a register until it is empty; this requires three instructions: (JE h,xxx; DCR h; Jump *-2 ) and requires 3*h steps to do.
Unconditional jump: Without a specific instruction, unconditional jump is achieved by setting a particular register always empty and testing it.