A Simple Computer

Treasure Hunt in the Pigeon House

I hope my readers are familiar with the children's game of "Treasure Hunt". This is often played at the birthday parties of elementary school children and it goes like this:
  1. The players are given a note with an instruction such as: "Go to the big tree in front of the house, and look at where the trunk divides, 4 feet above the ground".
  2. When they go to the tree, the players will find another note directing them to some other place, such as "behind the coinbox of the pay telephone on the corner of Saint Mary's Lane".
  3. Eventually, the last note tells where a prize may be collected.
This is essentially the same kind of instructions that make up a computer program. In our first computer example, the reader gets to play the role of the "Central Processing Unit", the part of the computer that performs the instructions in the program.

Imagine a bookshelf divided into 100 small cubbyholes, each identified with a number. Starting from number 1 in the upper lefthand corner, the first row has compartments 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. The next row continues with 11, 12, and so on. In each compartment, we can put a piece of paper with a number or an instruction. Now, let us set up the compartments as follows:

Cell numberContents
1Take next instruction from cell 21
26
321
446
5396
6134
758
893
90
100
110
120
130
140
150
160
170
180
190
200
21Copy the number in cell 2 to cell 20
22Put Zero in cell 19
23Put 3 in cell 18
24Using cell 18 as the number of a cell, add the number in that cell to cell 19.
25Add 1 to the number in cell 18
26Subtract 1 from the number in cell 20
27If cell 20 is not zero, take next instruction from cell 24
28Copy the number in cell 19 to cell 17
29Divide the number in cell 17 by the number in cell 2
30STOP
If you follow the instructions, starting with cell 1, then when you stop, you should have

748 is the sum of the six numbers in cell 3 through cell 8, and 124 2/3 is the average of those numbers. But actually, this is a general program to take the sum and average of any set of numbers. Like all programs, it has user instructions:
  1. You put the number of numbers to average in cell 2, and then
  2. in cell 3 and following, you put the numbers to be averaged.
  3. Start performing the instructions in cell 1
  4. Wait for the program top STOP
  5. Read the SUM in cell 19
  6. Read the AVERAGE in cell 17
Like all programs, this one has limitations. Can you see what the limitations are ?

(Answer: The program can work on no more than 15 numbers.)

Well, the computer you are using at school is a little more user- friendly than this, but basically, that is what it does.

The Model A Computer

We will do the next several exercises using this computer. Let's call it model A. As we go along, we will come up with a detailed description of its operation.

The model A computer has 1000 data/program cells, numbered from 1 to 1000.

Each cell can hold a number with up to 6 digits.

Programs always start executing instructions in cell 1.

Each instruction can mention up to 2 addresses, numbers of cells used as data in computation. Programs consist of the following instructions:
JUMP cell1Take next instruction from cell1
JUMP (cell1)Take next instruction from the cell with the number indicated by the number in cell1.
MOVE cell1, cell2Copy a data value from one cell to another. After the operation, cell1 is unchanged.
MOVE #number, cell2Put a value (a small integer value) into the cell mentioned.
MOVE (cell1), cell2Using the number in cell1 as a pointer to a cell, put the contents of that cell into cell2. Only cell2 is changed
ADD cell1, cell2Add the number in cell1 to the number in cell2, leaving the result in cell2.
ADD #number, cell2Add a small number to cell2.
ADD (cell1), cell2Using the number in cell1 as a pointer to a cell, add the contents of that cell to cell2, leaving the result in cell2.
SUB cell1, cell2Subtract the number in cell1 from the number in cell2, leaving the result in cell2.
SUB #number, cell2Subtract a small number from cell2.
SUB (cell1), cell2Using the number in cell1 as a pointer to a cell, subtract the contents of that cell from cell2, leaving the result in cell2.
MUL cell1, cell2Multiply the number in cell2 by the number in cell1, leaving the result in cell2.
MUL #number, cell2Multiply call2 by a small number.
MUL (cell1), cell2Using the number in cell1 as a pointer to a cell, multiply cell2 by the contents of that cell, leaving the result in cell2.
DIV cell1, cell2Divide the number in cell2 by the number in cell1, leaving the result in cell2.
DIV #number, cell2Divide a small number into cell2.
DIV (cell1), cell2Using the number in cell1 as a pointer to a cell, divide the contents of that cell into cell2, leaving the result in cell2.
JZERO cell1, cell2If cell1 is zero, jump to cell2, otherwise continue with the next instruction
JZERO (cell1), cell2If the cell pointed to by cell1 is zero, jump to cell2, otherwise continue with the next instruction
JNZERO cell1, cell2If cell1 is not zero, jump to cell2, otherwise continue with the next instruction
JNZERO (cell1), cell2If the cell pointed to by cell1 is not zero, jump to cell2, otherwise continue with the next instruction
JNEG cell1, cell2If cell1 is less than zero, jump to cell2, otherwise continue with the next instruction
JNEG (cell1), cell2If the cell pointed to by cell1 is less than zero, jump to cell2, otherwise continue with the next instruction
STOPProgram is complete
In addition, the following commands can be used to stuff data into cells before the program starts:
DATA valueThe cell contains the indicated number
TEXT "abcd"The cell contains the indicated 4 letters as data

We can now write the program from before in the concise form:
Cell numberContents
1JUMP 21
2DATA 6
3DATA 21
4DATA 46
5DATA 396
6DATA 134
7DATA 58
8DATA 93
9DATA 0
10DATA 0
11DATA 0
12DATA 0
13DATA 0
14DATA 0
15DATA 0
16DATA 0
17DATA 0
18DATA 0
19DATA 0
20DATA 0
21MOVE 2,20
22MOVE #0,19
23MOVE #3,18
24ADD (3),19
25ADD #1,18
26SUB #1,20
27JNZERO 20,24
28MOV 19,17
29DIV 2,17
30STOP

Data Representation

Up to this point, I have avoided talking about exactly how numbers and text are stored in the machine. This is because early machines very fairly different from each other, and I wanted to focus on what they had in common. But we can't dodge it forever, and some of it is useful to think about early.

All practical computers today use binary numbers inside. In school, we call this base-2 numbers, as opposed to our everyday base-10 numbers. Some early computers used a form of base-10 numbers known as BCD (Binary Coded Decimal). But often, we find that binary numbers are too cumbersome to write (too many digits) and for convenience they may be written in base-8 (octal) or base-16 (hexadecimal or hex). Here is a handy comparison table:
Decimal     Binary      Octal  Hex 
00000 0000 0000 0000000
10000 0000 0001 0001001
20000 0000 0010 0002002
30000 0000 0011 0003003
40000 0000 0100 0004004
50000 0000 0101 0005005
60000 0000 0110 0006006
70000 0000 0111 0007007
80000 0000 1000 0010008
90000 0000 1001 0011009
100000 0000 1010 001200A
110000 0000 1011 001300B
120000 0000 1100 001400C
130000 0000 1101 001500D
140000 0000 1110 001600E
150000 0000 1111 001700F
160000 0000 1000 0020010
170000 0000 1001 0021011
...... ... ...
640000 0100 0000 0100040
...... ......
10230011 1111 1111 17773FF
...... ......
40951111 1111 1111 7777FFF

This table shows how numbers were stored in a machine where each cell can hold 12 binary digits, or 12 bits. As you can see, this allows us to store numbers up to 4096. There have been some machines that used 12 bits as their word size, most famously the PDP-8 minicomputer from Digital Equipment corporation, the first computer that could be sold for less than $10,000. We said above, that the model A can store 6-digit numbers, so it must use more than 12 bits; in fact it would probably be a 24-bit machine. But we could do all the same things with a 12-bit machine; we would just say that it takes 2 cells to store a number. There is another reason that I propose a larger word size: The instructions have to fit in a cell, and many of the instructions need to be able to contain the addresses of two cells. Since I said that the model A has 1000 cells, we need at least 10 bits for an address. If the MOVE instruction was the only one allowed to have two addresses, that would make 24 bits the smallest practical word size. But with the instruction set outlined above, we need to be able to hold

Since I have used 19 operation codes at this point, we need at least 5 bits for an operation code. That means the minimum word size is 10+10+2+5 = 27 bits. I will choose 32 bits, divided as follows:

One more thing about numbers to think about: We need to be able to accomodate negative numbers. We also want to be able to accommodate numbers that are not whole numbers. And we need to have a way to catch the situation when a multiplication produces numbers that don't fit in a cell (because they are too large).

Negative numbers are simple: The highest digit is reserved to say "this is a negative number". Then we just continue counting down past 0.
DecimalBinaryOctalHex
20470111 1111 111137777FF
10230011 1111 111117773FF
...... ......
640000 0100 00000100040
...... ......
10000 0000 00010001001
00000 0000 00000000000
-11111 1111 11117777FFF
-20481000 0000 00004000800

Working on non-whole numbers is harder. In fact, very small and inexpensive computers (like the one that controls your microwave oven or the engine in your car) do not have instructions and circuits to do it. Larger computers use a representation called floating point to hold numbers of a greater range with less precision. (You will eventually get bored with this detail; when you do, skip forward to Input and Output.) In the model A computer, this works as follows:

The data cell is divided in three parts:
Sign BitAs with whole numbers, the top bit indicates whether this is a positive or a negative number.
ExponentThe next 7 bits indicate roughly how large the number is. This is a scale factor from -63 to +63 indicating a power of two that the mantissa must be multiplied by in order to get the real number. The exponent value of -64 is reserved to say that the number is invalid. All operations that fail because they deliver numbers outside of the usable range will return a value with the illegal exponent to prevent continuing the calculation with wrong values.
MantissaThe actual value (to be scaled according to the exponent part. Since we took away 8 bits for sign and exponent, we are left with about 9 digits of precision.
Because a floating point number looks just like a whole number with a different value, the program needs to keep track of which cells contain which kind of numbers, and in fact we need differnt instructions to add, subtract, multiply and divide for floating point numbers; we also need instructions to convert between whole numbers and floating point numbers.
FADD cell1, cell2Add the number in cell1 to the number in cell2, leaving the result in cell2.
FADD (cell1), cell2Using the number in cell1 as a pointer to a cell, add the contents of that cell to cell2, leaving the result in cell2.
FSUB cell1, cell2Subtract the number in cell1 from the number in cell2, leaving the result in cell2.
FSUB (cell1), cell2Using the number in cell1 as a pointer to a cell, subtract the contents of that cell from cell2, leaving the result in cell2.
FMUL cell1, cell2Multiply the number in cell2 by the number in cell1, leaving the result in cell2.
FMUL (cell1), cell2Using the number in cell1 as a pointer to a cell, multiply cell2 by the contents of that cell, leaving the result in cell2.
FDIV cell1, cell2Divide the number in cell2 by the number in cell1, leaving the result in cell2.
FDIV (cell1), cell2Using the number in cell1 as a pointer to a cell, divide the contents of that cell into cell2, leaving the result in cell2.
FLOAT cell1Convert the whole number in cell1 to floating point
FLOAT (cell1)Convert the whole number in cell1 to floating point

It is now time to confess that we cheated in the program above: When we computed the average, we divided a whole number into the sum, and came out with a fraction. As you can see above, this will not work, and we have to convert the sum to floating point before dividing. The revised program follows:
Cell numberContents
1JUMP 21
2DATA 6
3DATA 21
4DATA 46
5DATA 396
6DATA 134
7DATA 58
8DATA 93
9DATA 0
10DATA 0
11DATA 0
12DATA 0
13DATA 0
14DATA 0
15DATA 0
16DATA 0
17DATA 0
18DATA 0
19DATA 0
20DATA 0
21MOVE 2,20
22MOVE #0,19
23MOVE #3,18
24ADD (3),19
25ADD #1,18
26SUB #1,20
27JNZERO 20,24
28MOVE 19,17
29FLOAT 17
30FLOAT 2
31FDIV 2,17
32IFIX 2
33STOP

We also need to note that the average in cell 17 is now returned as a floating point number.

Input and Output

What we have covered so far, describes what computers were doing around 1949. While this was a great help in doing certain complicated mathematical computations, it was not simple to use. You will have noticed that there is no way to get things into and out of the computer. I said that we would "put this number into cell 2", but if you look at the instructions, the computer as described so far has no way to participate in this process. Early computers had a maintenance panel that allowed technicians to read the contents of each memory cell from a service panel, and to change the contents from there also. But this was slow and error prone. Our computer will be much more useful if we can type the numbers on a keyboard and get the program to write the results on a printing device. In fact, we can imagine it to look a bit like this PDP-1 from 1960 (which was in fact an 18-bit machine).

We will add a few instructions to allow input and output:

STATUS device, cell1 Read a status word from the device indicated into the memory cell named.

The following devices exist:
0 - switches and lamps
1 - teletype
2 - card reader
3 - line printer

The following information is defined for most devices:
NOTFOUND - the device does not exist, or is turned off
BADCOMMAND - you sent a bad command. All commands are being ignored. You must send a RESET command to make it work again.
NOTREADY - the device is there but needs some action before anything can be done with it. For example: No paper in printer. No cards in card reader. Output basket full.
INPUT_AVL - an input device has data ready for you to read.
OUTPUT_AVL - an oputput device is ready for you to send data to it.

READ device,cell1 Transfer one word from the device device indicated to the memory cell named.
WRITE device,cell1 Transfer one word of data from the memory cell to the device
COMMAND device,cell1 Send the command in cell1 to the device. The commands are different for each device.
As mentioned, each device is different, but they also have a lot in common. Let's examine them one at a time.

Switches and Lamps

This sounds boring, but is useful in two ways:

Basic Function

The machine has a control panel with a row of lamps, that can show bit for bit the contents of each cell in the machine. Writing to "lamps and switches" sets a pattern in these lights. It also has a row of switches; reading "lamps and switches" sets a memory cell to the pattern in these switches.

Commands and Status

The "lamps and switches" device is always ready, and ignores any commands.

Teletypewriter

Basic Function

The operator hits a key on the keyboard, and the next STATUS operation will show the INPUT_AVL bit. When the program does a READ operation, that single character is returned (using ASCII code). If READ is issued when no character is available, the program will wait with the TTYREAD lamp on the console turned on. All characters typed are immediately shown by the typewriter, without needing action by the program.

When the program does a WRITE, an ASCII character is sent to the typewriter, which has a small buffer. OUTPUT_AVL indicates whether there is room for another character in the buffer. If the program does a WRITE when the buffer is full, the program will wait with the TTYWRITE lamp on the console turned on.

Commands and Status

RESET clears the input and output buffers. WORDMODE sets a mode where a WRITE will transfer 4 bytes beginning with the leftmost 8 bits of the word. CHARMODE switches back to the normal mode where the 24 high bits are ignored.


Next: BASIC


Copyright 1999 Lars Poulsen, All Rights Reserved
These pages may be freely copied in their entirity only.
For other uses, please contact the author.