A course for beginners, using Computer/zero
This short tutorial is intended above all for people who know how to use a computer, but have never programmed one. If you have done some programming in a high-level computer language like BASIC, C, Smalltalk, or JavaScript, you will also benefit from it—although no such experience is assumed (except in the Appendix). Professional programmers and highly skilled amateurs are more than welcome to read it, but should be aware that it is not really for them. Nor is it designed as part of a formal course in computing or programming. It has been written in the belief that, since computers (desktops and smartphones, mainframes and computerized appliances) play a large part in our lives, it is desirable that more people should have some understanding of how they work and how they are programmed. I hope it will also be interesting in its own right.
You will probably find it most convenient to keep this page and the Computer/zero page open in different windows or different tabs, so that you can switch quickly between them. Readers who are using a mobile device should be aware that they can save a Computer/zero icon and then run it full-screen as though it were an installed app (although an internet connection will still be required each time they load it): navigate to the Computer/zero page using Safari on iOS or Chrome on Android, and tap ‘menu’ (Android) or ‘share’ (iOS) followed by ‘Add to home screen’. Since Computer/zero is itself a computer program, written in JavaScript, it will not work if your browser does not support JavaScript or has it turned off.
If you get stuck, and especially if you find a mistake, please email me and I shall do my best to help.
I
Imagine yourself sitting in a closed room. There are little boxes or pigeonholes on one wall, numbered zero, one, two, three, and so forth; and you are seated at a desk on which you can see a pencil, a large leather-bound volume with the word Instructions picked out in gold on the spine, and three tiny exercise books, one blue, one green, and one red. You look at the first page of the blue exercise book, and you read the number 0. This means you must go over to the pigeonholes and look in the box marked Zero. In it you find a piece of paper on which is written another number—let us say, 35. So you copy ‘35’ into your green exercise book; and in the blue exercise book you tear out the page with 0 written on it and write down the next number, 1. Next you take the Instructions book and look up what 35 means. Under ‘35’ you find written: ‘Go back to the pigeonholes, look at the piece of paper in box number three, and write down the number you find there in your red exercise book.’ The number in box three turns out to be 2: so you pick up the red exercise book and write down 2.
Next you turn back to the blue exercise book. The number you find written there is 1—so you go over to the pigeonholes and look in box number 1. It contains a piece of paper with ‘100’ written on it: so you copy down ‘100’ into your green exercise book, update your blue book so that it now says 2, and go back to the desk. Instructions tells you that ‘100’ means ‘Go over to the pigeonholes; find the number written in box 4; add it to the number you have in your red exercise book; and write the answer down in the red exercise book.’ The number in box 4 is another 2: you add this to the 2 that you already have written in your red book, and write down ‘4’.
Now you look once again in the blue book. It says 2: so over you go to the pigeonholes once again, find box 2, read the number ‘224’, copy it into your green book; change the blue book to say 3, and look up ‘224’ in Instructions. It says simply ‘Stop’. Congratulations! Your labours are, for the time being, at an end.
While they lasted, however, you and the various objects in the room were functioning as an accurate imaginary model of a computer. It was an imaginary computer, not a real one, because you weren’t actually in the room with the exercise books and the boxes; but, if you had been, it would have been a real computer, quite as real as the computer you are using to read this page. As a matter of empirical fact, computers are usually made of miniature transistors etched onto flakes of silicon—but they don’t have to be. Computers in the 1940s and 1950s were made of thermionic valves and Williams tubes: and they were real computers all the same. Charles Babbage envisaged computers made of polished brass and cogwheels and interlocking gears: and, if he had succeeded in assembling one, it would have been an entirely real computer. The computers of the future, made presumably of quantum entanglements and exotic gleaming materials, will be real computers. The system we have been imagining was a computer made of shelving and paper and oak floors and a pencil and you—and that was a real computer as well. The study of computing is not a branch of electronic engineering; transistors will not be mentioned again. In the sense in which we are using the term, a computer is defined not by the mechanical or electronic components from which it is made but by what it does: it stores and executes a list of unambiguously specified instructions. Thus, the imaginary room with you in it was a computer only as long as you carried out your instructions precisely and to the letter: the moment you had decided to use your own initiative, or to take industrial action demanding more exercise books and fewer repetitive trips over to the pigeonholes, it would no longer have been a computer (unless a human being is a computer anyway—which is probably a question for another day).
Most computers are divided into units corresponding to the ‘pigeonholes’ and ‘desk’ of our thought-experiment. The pigeonholes are the memory, where instructions and data are stored: it is divided into equally-sized segments (‘boxes’, or addresses) numbered from zero onwards. The phrase ‘random access’ memory is sometimes used: this means simply that the computer can look in whichever ‘box’ its instructions require, rather than needing to count all the way through. The desk, meanwhile, is the central processing unit—the part of the computer where instructions are decoded and carried out and where actual computation takes place. Besides the arithmetic and logic unit (you yourself), the CPU also features a few registers (the three exercise books). The blue exercise book, which tells you which instruction to read next, corresponds to the program counter; the green exercise book, where you write down the instruction you have fetched from memory before you decode it and execute it, is the instruction register; and the red exercise book, where you store the number you are currently working on, or the result of your latest computation, is the accumulator.
The instructions we used to calculate two plus two make up a complete computer program. (Note that the US spelling is used universally: *programme is wrong in this context, even in Britain.) Specifically, it is a program written in the machine language defined for Computer/zero, a very minimal computer intended to be used with this course. Computer/zero is about as small and simple as a computer can be and still allow programs to be written that are not entirely trivial. Despite its simplicity, however, it has all the essential characteristics of a computer—and, if it were given infinite time and infinite memory, it could do anything that can be done by any computer or indeed any possible computer. How much time you are willing to give it is a matter for you; but its memory is anything but infinite. Today’s computers typically count their memory addresses in billions; the largest supercomputers have trillions. Computer/zero has thirty-two. It does not sound much—but, as we shall see, it is enough to demonstrate a number of interesting ideas from mathematics and computer science. It is even enough for a rudimentary computer game.
The time has come to make Computer/zero’s acquaintance more properly. Click here to open Computer/zero in a new tab: you will see a large number of black rectangles, with a few numbers and letters dotted among them, and also three rows of buttons. This is Computer/zero’s front panel: the various buttons can be used to load instructions and data into the machine, and the black rectangles are lights that will stay black or light up in green to indicate the contents of the memory and the registers. For the time being, we are going to see how Computer/zero adds two and two to get four.
Find the row of buttons labelled ‘Sample programs’ and click 2+2. You should see a few of the lights come on: this tells us that the computer’s memory is no longer empty. Right above the buttons you will see a row of eight lights, three of which are now green: this is the instruction register, storing the instruction that the machine will execute next. To the right of it is the program counter (five lights, all black); and above it is the accumulator (eight lights, again all black). The remaining 256 smaller lights are the memory. In due course we shall learn how to understand what the lights themselves mean; for the moment, however, we shall rely on the fact that the registers (although not the memory) are ‘decoded’ for us. Next to the accumulator you should be able to see a 0: this tells us that the accumulator is currently holding zero—which makes sense, since we have not yet done any computations. There is another 0 next to the program counter (like the blue exercise book from earlier on): so the next instruction that will be executed is the instruction in memory address 0. Finally, underneath the instruction register you should see the following: 35 LDA 3. You will recognize the 35 as being the first instruction in the 2+2 program as we worked through it, meaning ‘load the accumulator with the number in address 3’. The readout abbreviates ‘load the accumulator’ to ‘LDA’; each instruction, in fact, has a convenient shorthand mnemonic by which it can be identified. Now click the Enter button (in the row above ‘Sample programs’). The 0 next to the program counter becomes a 1: we are now looking at the next instruction along. And we see that it is 100 ADD 4, just as we might expect. Click Enter again: the program counter now shows 2, and the instruction register shows 224 STP (short for Stop). Click Enter again: the program counter advances to 3, and the instruction register changes to 2 NOP. NOP stands for ‘No operation’, or ‘do nothing’: as a matter of fact we do not intend to execute this as an instruction, but, if we did, it would not do anything. Click Enter again: the program counter moves on to 4, and the instruction register shows another 2 NOP. This is the end of the program: you can keep clicking Enter, and the program counter will keep going up by one, but the instruction register will always say 0 NOP.
When you are satisfied that the program loaded into Computer/zero is the same one that we worked through with the imaginary exercise books and desk, click the button marked Back to 0: the effect of this button is to restore the program counter (and accumulator) to zero, so that we can start running the program. Near the Back to 0 button you should see a button labelled Step. This button has Computer/zero carry out one instruction (the one the program counter tells it to execute, which is also the one shown in the instruction register), update the memory and the registers as appropriate, and then stop. Click it. At once, the readout labelled ‘Instructions executed’ changes from 0 to 1. Next to the accumulator there is now a 2: the ‘load’ instruction has been carried out. The program counter tells us that the next instruction will be the instruction at address 1; and the instruction register reminds us that this is an ‘add’. Click Step again. The accumulator now shows 4—the result of the calculation. The program counter has changed to 2; and the instruction register tells us that the next instruction will be to stop. It feels faintly pointless to click Step again just to tell the computer to stop, when it isn’t actually doing anything; but, for completeness, you may as well do so. What is in the registers now? How many instructions does Computer/zero say it has executed?
Click Back to 0 again, to return to the beginning of the program. ‘Instructions executed’ now shows 0 again. This time, instead of using Step you should click Run: and you will see that Computer/zero runs through the whole program, halting only when it meets the ‘stop’ instruction. Now scroll down to the bottom of the Computer/zero page, and you will see that the 2+2 program is written out in mnemonic notation. The notation (usually referred to as assembly language) is a matter of convention, and there is no essential reason why you should not invent your own system of mnemonics: but it is a better idea to keep to the system that is exemplified by the Computer/zero sample programs. If you look at the 2+2 mnemonic listing, you will see that it is lined up in columns. From left to right, we have: the address; a label (followed by a colon) that we can use if we want to refer to that address somewhere else in the program; the instruction; the label of the address that this instruction refers to, or else a simple numeric value if this address holds data rather than an instruction; and perhaps a comment, introduced by a semicolon, explaining what the instruction is for. (Not all the columns are used in every case.) Choosing sensible labels, and adding some comments, makes your programs enormously more readable for other people and also for you in the future. If you don’t have much experience with programming, you will be astonished to find that even a short program can seem entirely transparent and self-explanatory while you are working on it—and virtually incomprehensible when you look back at it only a few months later. Good labels and plenty of comments do not stop this happening altogether, but they do help.
II
We usually write numbers in decimal, or base ten—perhaps because we have ten fingers, although the Romans also had ten fingers and Roman numerals are nonetheless not purely decimal. In our Hindu-Arabic numerals, there are ten different basic symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. When we have counted up as far as 9, we change it to a 0 and write a 1 to the left of it: 10. This means ‘one ten and zero ones’. Thus, we can write numbers as high as we like using only the same ten symbols. ‘2016’, for example, means ‘two thousands, zero hundreds, one ten, and six ones’. (The zero is just as important as any of the other numbers: without it, we would have ‘216’ and we would naturally read it as ‘two hundreds, one ten, and six ones’.) This way of writing numbers was invented in India, and represented a great advance on Roman numerals and other systems: in fact, when it was introduced to Europe—by way of the Arabs—it made the use of calculating machines (like the abacus) almost obsolete for several centuries. There is, however, no reason why we need to work with precisely ten symbols. There are sometimes occasions when it is easier to use either more or fewer. We can use base eight, for instance, which we call octal: in octal we count 0, 1, 2, 3, 4, 5, 6, 7, 10, 11..., and ‘45’ would stand for four eights and five ones—the number that we ordinarily write as ‘37’. Or we can use base sixteen, dubbed hexadecimal: we shall then borrow the first few letters of the alphabet to act as numerals for ten, eleven, etc., and we shall count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 11... The hexadecimal number ‘1c’ means one sixteen and twelve ones, or decimal 28.
The vast majority of computers, including Computer/zero, use neither decimal, nor hexadecimal, nor octal, but binary—base two. The principle is exactly the same, but we now have only the two symbols 0 and 1 at our disposal, and we count 0, 1, 10, 11... Each binary digit (each bit) may be thought of as a switch, or indeed a light, that can be either on or off: and in fact this is what the lights on Computer/zero’s front panel are for. If you glance back at the front panel, you will see that the memory is divided into groups of eight lights; and the accumulator consists of eight lights; and the instruction register consists of eight lights. (The program counter, for reasons that will soon become clear, consists of only five lights.) Just as in decimal numbers we have, from right to left, the ones, the tens, the hundreds, the thousands, etc., so in binary numbers we have the ones, the twos, the fours, the eights: the value of a 1 in each column is twice what it was in the last. Each Computer/zero machine word consists of eight bits (or one byte): so the largest number that can be stored in one word of memory is one plus two plus four plus eight plus sixteen plus thirty-two plus sixty-four plus one hundred and twenty-eight, which comes to 255—or, in binary, 11111111. The smallest number is zero, or 00000000. Any number between these two can be written by choosing an appropriate combination of ones and zeros. For example, 37 equals thirty-two plus four plus one (00100101); and 28 equals sixteen plus eight plus four (00011100).
Now, go back to Computer/zero. If the 2+2 program is still in memory, click the button marked Clear: you will be asked to confirm that you do indeed want to clear the machine. Once the memory and registers have been reset to zero, you can practise entering some numbers in binary form. Next to Enter you will see a row of eight green buttons: each of these is a switch that turns one of the bits in the instruction register on or off. Click the rightmost button, and you will see the rightmost green light in the instruction register come on; you will also see that the readout for the instruction register’s contents has changed from 0 to 1. Click the same button again: the green light goes out, and the instruction register is once again storing zero. Try clicking the other buttons, until you have convinced yourself (a) that each button gives a number twice the one given by the button to the right of it, and (b) that it is indeed possible to make any number between zero and 255. (You can ignore, for the time being, anything that is shown on the readout except the number—underneath the register and to the left.) When you have settled on a number you are happy with, click Enter: the instruction register goes black, the program counter moves on by one, and the machine word that was previously in the instruction register is transferred into the memory (starting at address zero). This is how we program Computer/zero: one word at a time, using the green buttons to select the number we want and then clicking Enter to load it into memory. You are unlikely to enter at random a program that does anything useful: despite the machine’s small memory, the number of possible Computer/zero programs is comparable to the number of atoms in the universe, and most of those possible programs will do either nothing or nothing we want. The aim for now is to get comfortable with using the front panel to load numbers into memory. You should not feel nervous, however, about running any programs you enter (by clicking Back to 0 and then Run) and seeing what they do: there is absolutely no way your programs can damage either your computer or Computer/zero, and if the machine seems to have got stuck in an infinite loop you can just click the Stop button to halt it.
When you feel you have got the hang of the front panel, click Clear to reset Computer/zero. Now enter the 2+2 program yourself, instead of loading it from the sample programs. Remember that it consists of the numbers 35, 100, 224, 2, 2. Click Enter each time to load the number from the instruction register into memory; if you make a mistake, click Back to 0 to return to the beginning and then go through the program clicking Enter until you reach the number you need to correct. When you have finished, click Back to 0 and then Run to make sure the program works as expected. (If it doesn’t, it means you have entered the wrong number somewhere, or perhaps forgotten to click Back to 0: find the mistake and correct it!) Once you have it working, try running it with different values in addresses 3 and 4.
Next, change the 100 in address 1 to 132. You will see the instruction on the readout change from ADD 4 to SUB 4. SUB, perhaps guessably, is short for ‘subtract’: instead of adding, the program will now subtract the number in address 4 from the number in address 3. Put suitable numbers in those two addresses, and try it.
You may be wondering what happens if the result of an addition or subtraction operation would be outside the range of numbers that Computer/zero can hold in its accumulator—below 0, or above 255. The answer is that the accumulator simply loops around: 255 + 1 gives 0, and 0 – 1 gives 255. The accumulator can in fact be pictured as a wheel, with the numbers from 0 to 255 written around the rim. Rolling the wheel one way is ‘adding’; rolling it the other way is ‘subtracting’. This behaviour has a very useful consequence: it allows us (if we are a little bit careful) to represent negative numbers. Since 255 is the answer to 0 – 1, we can think of it as meaning –1. Subtract 1 again—and the result is 254, or –2. Add 3 to this, and we will go ‘past’ 255 to 0 and end up with 1: the correct answer. Any arithmetic we might want to do with the numbers from –1 to –128 can be done with the positive numbers from 255 down to 128, and produce the answer we expect. This trick, which is referred to as two’s complement, is the way most computers do in fact store negative numbers. (If you are having trouble picturing how two’s complement works, picture a wheel that only goes from 0 up to, say, 7: imagine what would happen if you turn it forward or backward by different numbers of steps.) We say that eight bits of computer memory, like our accumulator or one of our memory addresses, can hold either (a) an unsigned number—a number without a plus or minus sign—in the range from 0 to 255, or else (b) a signed number in the range from –128 to +127. Note that it is entirely up to you as the programmer to know whether you are treating the numbers you work with as signed or unsigned: the computer does not know or care whether 11111111 means –1 or 255. (I have more than once seen a well-known commercial application display some huge number, in the billions of billions, when –1 would have made more sense: this is because the computer had quite properly come up with 1111111111111..., and the programmer had forgotten that it was a signed rather than an unsigned value.) Computer/zero’s readouts show the negative interpretation of the instruction register and accumulator, where there is one, as well as the positive interpretation: go back to Computer/zero and verify that this is so, then practise using ADD and SUB with negative numbers until you feel you are starting to get used to two’s complement.
III
So far, we have treated Computer/zero instructions simply as arbitrary decimal numbers: 35 for LDA 3, 132 for SUB 4. When they are written in binary form, however, they make more sense. The eight-bit word actually consists of two sections: the leftmost three bits encode the type of instruction it is (NOP or LDA or ADD or whatever), and the remaining five bits encode the address it refers to (if any). An instruction that starts 000... is always a NOP, an instruction that starts 001... is always a LDA, and so forth. The five-bit address field is enough for an unsigned number in the range from zero (00000) to thirty-one (11111)—which is why Computer/zero has 32 memory addresses, and why the program counter is only five bits long. The three-bit instruction field is enough for an unsigned number in the range from zero (000) to seven (111): from which we can see that Computer/zero is capable of recognizing eight different instructions. We have already encountered five:
000 — NOP
001 — LDA
011 — ADD
100 — SUB
111 — STP
Each of them is a pretty elementary operation—and the same is true, more or less, of full-scale modern computers as well. The power of a computer comes not from any great sophistication in the instructions it can execute, but from its ability to carry out simple instructions very quickly and very reliably. If we are to benefit from this, however, we shall need ways of directing the computer to carry out the same instruction or sequence of instructions repeatedly—and the simplest way is by using a ‘Jump’ instruction, represented by the binary numeric code 110 and by the mnemonic symbol JMP. When the computer encounters a Jump, it loads the address mentioned in the instruction into its program counter (discarding whatever was there before). The result is that the machine ‘jumps’ to that address and carries on from there. If, in the 2+2 program, we were to replace the STP with JMP 0 (11000000 in binary), the program would never halt: it would loop back to the beginning and keep performing the same calculation over and over again, forever.
This is probably not what we want. But there are better uses for JMP than that. As an illustration, let us compose a very short program that—unlike 2+2—could conceivably have some practical utility. You have probably seen the mechanical or digital ‘clickers’ that are used, for example, to count how many people have passed a gate. We shall now program Computer/zero to function as one of these counters or clickers. A counter/clicker can do two things: it adds one to the number it is storing each time its user presses a given button, and it can also be reset to zero. Assuming we are storing the number in the accumulator, adding one is not difficult:
ADD one
STP
one: 1
(It is a good idea to write out your programs first in mnemonic notation, using a text editor application or even a piece of paper, and to fill in the actual numerical addresses last of all.) When this program is run, it will change the accumulator from 0 to 1. This is the beginning of our counter/clicker—but so far it can only count up to one. We can remedy this, however, with a JMP. After the STP instruction, the program counter is left pointing to the next address: if the user clicks Run again, the machine will resume execution from there.
start: ADD one
STP
JMP start
one: 1
We now have a counter/clicker that will count up each time it is clicked; but there is no way of resetting it. To add this feature, we can take advantage of the fact that Computer/zero’s Enter button moves the program counter on by one without executing the instruction. We simply place, after the jump, instructions that will reset the accumulator to zero and then jump back to wait for the user to click the clicker again.
start: ADD one
wait: STP
JMP start
LDA zero
JMP wait
one: 1
zero: 0
Replacing the labels with addresses, we have:
0 ADD 5
1 STP
2 JMP 0
3 LDA 6
4 JMP 1
5 1
6 0
And that is a complete counter/clicker. It could scarcely be easier to use: click Run to add one, or Enter and then Run to reset the count to zero. Now go over to Computer/zero and enter the program at the front panel. If you forget the binary encoding associated with an instruction, scroll down on the Computer/zero page to the place where it says ‘Instruction set’—or just experiment with turning the leftmost three lights in the instruction register on and off until the readout shows the instruction you want. When you have finished, you may feel that needing to use the front panel to enter the program every time you want to use it is something that could get old. Fortunately, Computer/zero provides a way to save your programs for future use, or indeed to share them with other people. Click the Save/share button located just to the right of Clear, and the contents of Computer/zero’s memory will be converted into a URL—a link—and displayed in a popup box. Select this link, copy it, and you can then paste it into a browser address bar, a text editor, an email, an SMS message, a tweet, or anywhere you like. If the link is clicked on, it will be found to lead to a Computer/zero with your program already loaded into its memory. (Nothing is actually saved centrally: the link itself includes the whole program, in compact hexadecimal—base sixteen—numbers.)
The instructions we have looked at so far may change the number in the accumulator, but they do not change any of the numbers stored in memory. Sometimes, however, it is desirable to do just that: to use a memory address as a variable, whose contents can be changed. For this purpose, Computer/zero employs the instruction 010 or STA (short for ‘store accumulator’). STA is the counterpart of LDA, and is used similarly: if LDA 3 loads the value at address 3 into the accumulator, STA 3 stores the value in the accumulator at address 3. To see STA at work, load this program (saved using Save/share) and use Step to go through it one instruction at a time. How soon can you tell what it is doing? And can you write a program to do something analogous (with your initials, for example)?
There is only one instruction left: number 101, which is called BRZ or ‘branch on zero’. Like JMP, BRZ jumps to the address specified in the instruction—but it does so only if the number stored in the accumulator is 0. Otherwise, the computer simply passes on to the next instruction. The importance of BRZ cannot be overstated. We can use it, for instance, to test whether two variables are equal:
LDA x
SUB y
BRZ eq ; branch if equal
; otherwise carry on
It is also how we program Computer/zero to do something a specified number of times, by using a variable as a counter and branching out of the loop when the counter gets down to zero:
start: ; do something
LDA count
SUB one
STA count ; don't forget this!
BRZ done
JMP start
done: ; carry on after loop
For examples of this technique, go back to Computer/zero and load the 7×8 and Fibonacci sequence sample programs. Both of them are based on loops. Work through the notes and listings at the foot of the Computer/zero page until you are confident you understand both programs.
IV
We have now covered all Computer/zero’s instructions (and all the features provided by the online implementation). What remains is to learn programming techniques—fresh ways of combining and using instructions you already know. For instance, it is often very useful to be able to work not just with one-off variables but with an array. An array is a sequence of memory addresses storing data that we intend to use as a group. (Computer/zero’s memory is in fact stored internally using an array.) Let us say we have an array of numbers located somewhere in memory.
array: 2
3
5
7
11
13
17
What we think of as the address of the array is in fact the address of its first element. Since the elements are arranged sequentially in memory, the second is at array + 1, the third at array + 2, and so on, until we reach the seventh and last at array + 6. If we want to load the first element of the array into the accumulator, we shall simply use LDA array. To access subsequent elements, we can make use of the fact that an instruction is simply a number—and we can therefore perform arithmetic on it. If we load the LDA array instruction into the accumulator, and add one, the accumulator will then hold an instruction that is equivalent to LDA array+1. We store this new instruction in place of the original, and we are then ready (next time we come round the loop) to process the second element of the array. This technique, where the program changes its own instructions as it runs, is known as self-modifying code.
How are we to know when we have reached the end of the array? There are two possibilities. If we know in advance how many elements it has, we know the address of the last of them—and so we can test each time whether we have got past it.
load: LDA array
; do something
LDA load
ADD one
STA load
SUB last+1
BRZ done
JMP load
done: ; rest of program
last+1: LDA array+7
Alternatively, we can ‘mark’ the end of the array with some special value (0 would be convenient, or possibly 255) and branch out of the loop when we find an array element storing that value. Obviously this is only possible if there is a value that we can be confident will not occur as a legitimate part of the array.
As an exercise, write and test a program that finds the sum of an array (the total of all the elements).
The programming language APL provides a useful function called iota, which creates an array of the integers up to some specified number. Write a program that implements iota. The number to end on should be stored as a variable n: when you run the program, it should store the numbers 1, 2... n as an array.
Now look at the Computer/zero sample program, ‘linked list’. Lists and arrays are both examples of data structures: ways of combining multiple variables so we can work on them together. What are the differences between a list and an array? Which one might you choose (a) if economical use of memory is important, (b) if you might need to add additional elements in the middle while the program is running, (c) if you want quick access to specified elements—the fifth, say—without having to trawl all the way through?
Note that two of Computer/zero’s instructions, NOP and STP, do not refer to an address. The number in their address field is simply ignored. As a result, you can if necessary use these instructions to store small variables or constants (in the range from 0 to 31 for NOP, from 224 to 255 unsigned or –1 to –32 signed for STP). You can occasionally save yourself a word of memory this way. For instance, many programs will include a counter that counts down to zero:
LDA count
SUB one
STA count
For this to work, of course, there must be a memory address somewhere given over to storing the 1. If, however, you use 255 instead of 224 for your STP instruction, Computer/zero will still read it as Stop—but it will also be usable, by two’s complement, as the number –1. Since adding –1 is the same as subtracting 1, we can rewrite the loop-counter code using the Stop as our constant:
LDA count
ADD stop
STA count
In general, however, tricks of this kind are to be avoided unless you are sure you need them. They tend to make your programs less readable,—and there are often other ways to save memory.
The last sample program, the Prisoner’s Dilemma, is a complete and playable computer game. Unlike the examples we have seen so far, it uses up all 32 words of Computer/zero’s memory; and it does employ some tricks to make everything fit into the available space. You should now be in a position to understand how it works, though: read the notes and the listing carefully, and run the program to verify that it does indeed operate as anticipated.
The course ends here, but there is no reason why you should stop experimenting with Computer/zero. You may like to try writing a program to perform division, for instance: it is harder than multiplication, but not impossible. And you can of course create your own exercises. Think of things you might like to program Computer/zero to do; and program it to do them. You will often find it useful to start by working out your algorithm—the list of steps by which the computer will solve the problem—before you convert it into Computer/zero instructions. Some more sample programs are available on the Computer/zero page at the programming chrestomathy site, Rosetta Code. The Rosetta Code page also includes a list of programming tasks that have not yet been solved using Computer/zero: some of them are probably rather ambitious, but you are warmly encouraged to solve any that you can and to add your programs to the site. And I hope you will ultimately consider moving on from Computer/zero, either by learning to program a more sophisticated computer in machine language or by learning one of the many excellent high-level programming languages that are available for modern computers. Either way, your experience with Computer/zero will help you understand what is going on. And, if you do choose to learn a high-level language, one thing you may like to do with it is to write your own implementation of Computer/zero. The Appendix contains some hints on how to set about it.
Appendix: implementing your own Computer/zero
If you know a high-level computer language, or if you are learning one, you may like to try writing an implementation of Computer/zero for yourself. It is surprisingly easy to do. The fundamentals take fewer than twenty lines of code (which you will have little difficulty translating into your favourite programming language):
acc = 0
pc = 0
REPEAT
instruction = memory(pc) DIV 32
address = memory(pc) MOD 32
pc += 1
CASE instruction OF
WHEN 1: acc = memory(address)
WHEN 2: memory(address) = acc
WHEN 3: acc += memory(address)
IF acc > 255 THEN acc -= 256
WHEN 4: acc -= memory(address)
IF acc < 0 THEN acc += 256
WHEN 5: IF acc = 0 THEN pc = address
WHEN 6: pc = address
ENDCASE
UNTIL instruction = 7 OR pc > 31
This is not a complete implementation, naturally, because it does not include any input or output: you will need to add some way of getting instructions and data into the memory, and also some way of displaying the results when the program has finished running. Nor does it offer a Step function, or Save/share, or sample programs, etc.: all these are features you can include if you want them.
Rather than simply reproducing Computer/zero as I have implemented it, however, you may enjoy adding your own extensions. Perhaps you could allow your version to read programs in as text files, meaning you could edit them at leisure instead of fiddling with a front panel. A slightly more ambitious project, but still not too hard, would be a symbolic assembler: this is a program that takes programs written in mnemonic symbols and converts them into numerical machine code. I know of at least one user who has written an assembler for use with the online Computer/zero: it translates a program written in mnemonics into the format used by Computer/zero’s Save/share. While you are extending Computer/zero, you may wish to give it a word length greater than eight bits. (This will probably involve nothing more than changing a few constants in your code, but if you are using a statically typed language you should make sure you choose an appropriate numeric type.) The longer the machine word, the larger the numbers each word can store—and, also, the more memory addresses Computer/zero can work with. If you increased the word length to 24 bits, each word could hold an unsigned number from zero to nearly 17 million; and the available memory would increase from 32 bytes to 6 megabytes. An advantage of 24 bits over 16 or 32 is that 24 is divisible by three, so you could write your programs as eight-digit numbers in base eight (octal) with the instruction in the first digit and the address in the remaining seven. Computer/zero programs written for an eight-bit word length can be mechanically converted for any longer word simply by inserting the right number of zeros: for instance, the instruction ADD 5 is 01100101 on an eight-bit machine and 011000000000000000000101 on a 24-bit one. Long binary numbers do look slightly dismaying, and they are not easy to read or debug; but it would be straightforward enough to write a program to do the conversion, and in any case the same number can also be written in octal as 30000005.
Once you have more memory, you will find yourself building up a library of subroutines to perform useful jobs that are not included directly in the instruction set. You may also want to add some more output capabilities—say, graphics. It would be possible, in principle, to create a black-and-white graphical display using one bit of memory to control each pixel, along the same lines as the ‘hello’ program. With six megabytes to play with, however, you will probably find it easier to allow one machine word per pixel, with the number stored in the word controlling the colour of the pixel. 24 bits is precisely enough to store colours in the industry-standard format, with eight bits each for the red, green, and blue components of the light. A 400×400-pixel full-colour display, which would be enough for some quite impressive graphics, would take 160,000 machine words. Since a 24-bit Computer/zero would put more than two million words at your disposal, you could probably spare it. And the same principle of memory-mapped input and output could also be used to print text: just set aside a particular memory address and have the computer print characters based on numbers that are stored there. This will mean adopting some system of numerical encoding for characters. You could use ASCII, which is restricted to the charactersplus a few that are invisible (space, return, etc.),—but you may prefer Unicode, which encodes thousands of different characters including mathematical symbols and characters used to write dozens of ancient and modern languages.
These are some possibilities for you to think about, at any rate. But it is entirely up to you.