Programming comes easily to some people and is more difficult to others. Also, the C++ programming language is very fussy about how its programs are typed, and very rich with a huge number of commands and functions you can use. Rather than start with the full language we are going to start with a tiny language. Experience shows that students can get a better idea of what programming is about and how it works much better when they start off by thinking about languages like this.
In any case, the programming language we will start with is particularly interesting and is, it turns out, theoretically capable of almost anything. More ambitious students will find plenty of challenges here to convince themselves of this. If however you are new to programming, all you need concentrate on are the basics.
The programming language we start with is one for Register Machines. You can think of it as describing the operation of a machine that has a certain fixed (finite) number of registers , each one containing at any one time a natural number.
Note: Throughout this module the natural numbers are taken to be , i.e. including zero. This is standard in the subject and any other convention would be impossible.
Registers are a bit like variables in mathematics. They are "containers" or "names" for a number. Indeed we will also call them variables later on. But they are not at all like variables in mathematics in the sense that the value inside a register can be changed by special instructions that we give to the register machine.
The main instructions are as follows.
Note: There are two important things to remember about LOOP. The first is that the curly brackets must always be used. The second is that the loop is carried out times, where is the original value of x. It is possible to change the value of x inside the loop, but this does not affect the number of times the loop is carried out.
To make register machines a bit more usable, we add three additional instructions.
Of course the register name x can be anything you like, any of the letters a to z or A to Z, or even a "word" made from letters a to z or A to Z, digits, and the special symbol _. Such "words" must start with a letter and the case of letters is important.
Here is an example program. It creates the number two and prints it.
USES(x) INCR(x) INCR(x) PRINT(x)
Here is another example program. It takes two inputs, x and y, and adds them.
INPUT(x)
INPUT(y)
USES(z)
LOOP(x) { INCR(z) }
LOOP(y) { INCR(z) }
PRINT(z)
Notice that the variable z in USES(z) is always initialised as 0.
Here is another example. This time we multiply x and y.
INPUT(x)
INPUT(y)
USES(z)
LOOP(x) { LOOP(y) { INCR(z) } }
PRINT(z)
If you want to modify the input register and just print that, then that is fine. Here's a very simple program that doubles its input.
INPUT(x)
LOOP(x) { INCR(x) }
PRINT(x)
These examples are key to what is going on in this part of the module. Before you go any further you should make sure you understand them. If you are in a computer lab you will be able to try them out on the computer, and modify them to see how they work in detail but there are a few things you will need to learn about the computer before you can do this.
The next page in this sequence will get you to try out these ideas in the computer lab on a real computer.
You have seen a basic mathematical concept of a computer. I like to call these machines "Primitive Register Machines" because (a) they are rather primitive:) and (b) because it turns out that they can compute all functions in a class of functions called the "primitive recursive functions". This latter fact is an optional extra for more ambitious students only.
The important things to note are,