Machines with Memory - Models of Computation: Exploring the Power of Computing - page 113

The meaning of each instruction should be clear except possibly for the CONTINUE and
JUMP. If the program reaches a CONTINUE statement other than the last CONTINUE, it
executes the following instruction. If it reaches the last CONTINUE statement, the program
halts.
The jump instructions R j JMP + N i ,R j JMP − N i ,JMP + N i ,andJMP − N i cause a
break in the program sequence. Instead of executing the next instruction in sequence, they
cause jumps to instructions with labels N i . In the first two cases these jumps occur only when
the content of register R j is zero. In the last two cases, these jumps occur unconditionally.
The instructions with JMP + (JMP ) cause a jump to the closest instruction with label N i

above (below) the current instruction. The use of the suffixes + and

−

−

permit the insertion of
program fragments into an existing program without relabeling instructions.
A RAM program is a finite sequence of assembly language instructions terminated with
CONTINUE. A valid program is one for which each jump is to an existing label. A halting
program is one that halts.

TWO RAM PROGRAMS We illustrate this assembly language with the two simple programs
shown in Fig. 3.19 . The first adds two numbers and the second uses the first to square a
number. The heading of each program explains its operation. Registers R 0 and R 1 contain the
initial values on which the addition program operates. On each step it increments R 0 by 1 and
decrements R 1 by 1 until R 1 is 0. Thus, on completion, the value of R 0 is its original value
plus the value of R 1 and R 1 contains 0.
The squaring program uses the addition program. It makes three copies of the initial value
x of R 0 and stores them in R 1 ,R 2 ,andR 3 . It also clears R 0 .R 2 will be used to reset R 1 to x
after adding R 1 to R 0 .R 3 is used as a counter and decremented x times, after which x is added
to zero x times in R 0 ;thatis, x 2 is computed.

R 0 R 0 ← R 0 + R 1 Comments R 0 ← Comments

R 2 ← Copy R 0 ( x )toR 2 N 0 R 1 JMP N 1 End if R 1 =0 R 0

−

R 3 ← Copy R 0 ( x )toR 3

INC R 0 Increment R 0 R 0

DEC R 1 Decrement R 1 CLR R 0 Clear the contents of R 0

R 1 ← Copy R 2 ( x )toR 1 JMP + N 0 Repeat N 2 R 2

N 1 CONTINUE

R 0 ← R 0 + R 1

N 0 R 1 JMP − N 1

INC R 0
DEC R 1
JMP + N 0
N 1 CONTINUE
DEC R 3

Decrement R 3

R 3 JMP − N 3 End when zero

Add x to R 0 JMP + N 2

N 3 CONTINUE
Figure 3.19 Two simple RAM programs. The first adds two integers stored initially in registers
R 0 and R 1 , leaving the result in R 0 . The second uses the first to square the contents of R 0 ,leaving
the result in R 0 .