Register machine examples

This page is devoted to some example register machines, all written with the basic instructions of primitive register machines. Some of them are given for you to try out and some are for you to write on your own. Part of your first assignment will be to write one of these machines yourself.

1. Preliminaries

The #include "regmac.h", MAIN and END lines will be omitted on this page for simplicity, since they are always the same. You can read the instructions for running these machines in the computer labs, which are available elsewhere.

Here are some things to always remember about register machines. (Similar points will also apply to C++.)

Generally speaking each command goes on a separate line, and each command does exactly one thing to the register machine. It is your job to put all these commands together to make the whole machine do something useful.
"Comments" (i.e. remarks to yourself that are ignored by the computer) can be inserted with // or /*..*/ e.g.
```
 INCR(x) // comment to end of line 
```
or
```
 /* .. a possibly multi-line comment .. */ 
```
These are useful if you think you need to remind yourself what a particular line does.
Be very very careful about what you type at all times. The computer language is very precise and unforgiving.
If you get an error message, carefully review what you have written and compare with the web pages for the sorts of things the computer might have been "expecting". Remember that an error might have occurred on a line before the point the error was detected.
If you do not understand the actual error message (because it is in computer gobbledegook) you are in good company. Very few of us understand all the error messages. You still should be able to guess what's wrong by looking at the line where the error was detected.
If you get a lot of error messages, aim to fix the first one (only) and try again. You do not have to fix all errors. In fact you may get several messages for a single error.
You always need to test all your programs carefully. That usually means trying it out on inputs for which you can easily compute the answer yourself.
If you have a running program and it runs but does not do what you think it should do, but do not understand why not, try putting extra PRINT statements in the program and study the output carefully.

If you are still stuck and do not understand how a program works (or doesn't work) you can always simulate the computer on paper. This is an important skill that you must develop carefully.

Write a box for each register, put the current values in the boxes. (You can find out what these are with PRINT statements.) Then read the program just like the computer would and carry out on paper exactly what the computer would do, to see if you get the same answer (and more particularly, why). Of course you almost certainly only want to try this on very simple values for the inputs.

2. Adding, multiplying, etc.

The first example squares a number.

  INPUT(x)
  USES(y)
  LOOP(x) { LOOP(x) { INCR(y) } }
  PRINT(y)

Q1. Try the program out on some simple numbers. Does it work? Are you sure?

Q2. Try the effect of putting "PRINT(y)" inside the loop. For example: (a) put it just before the second LOOP(y); (b) put it just before the INCR(y).

Q3. What does this program compute?

  INPUT(x)
  USES(y)
  LOOP(x) { LOOP(y) { INCR(y) } }
  PRINT(y)

Q4. What does this program compute?

  INPUT(x)
  USES(y)
  INCR(y)
  LOOP(x) { LOOP(y) { INCR(y) } }
  PRINT(y)

Q5. The following attempts to square x without using a separate variable y. Does it work? If not, what does it compute?

  INPUT(x)
  LOOP(x) { LOOP(x) { INCR(x) } }
  PRINT(x)

3. Subtracting

A second page shows how the following operations can be programmed in the original primitive register machine language.

DECR(x) If possible, decrease (or decrement) the value of the register x by one.
IFNZ(x) { ... } If x>0 do "...".
IFZ(x) { ... } If x=0 do "...".

Because these operations are useful and awkward to program using LOOP INCR and ZERO only, they are provided as built in macros and you can use them. For example, the following sets z to be max(0, x - y) and prints the answer.

  INPUT(x)
  INPUT(y)
  USES(z)
  LOOP(x) { INCR(z) }
  LOOP(y) { DECR(z) }
  PRINT(z)

Exercise.

(Tricky!) Write a register machine program that returns a value y which is the result of dividing its input x by two. Suppose for simplicity the input value of x is even. Use other variables and LOOP(x) { ... } Hint: have the other variable, u say, to always have the value 0 or 1 and test which it is with IFNZ( ... ) { ... } ELSE { ... }. You can do different commands depending on the value of u.

Exercise.

(This is a challenge! The answer will be provided later. To take up the challenge, don't cheat and read the answer elsewhere.) See if you can spot a way to program DECR using LOOP INCR and ZERO only.

Assessment: There will be an assessment based on this work that is at the end of week 2. You should look at Canvas to see the details. Be careful to follow the instructions exactly. (Your program will be tested on a computer and if it does not meet the specification in the assignment it is wrong. Also, it is your job to test your program - just checking it gives the right answer in one case only is unlikely to be enough.) Answer the Canvas quiz too.

Note: the second assessment is based on the same material but is quite a lot more difficult. Two weeks should be more than enough time to get to this point in the course. Three weeks should be plenty to do the first two assessments, so if you have spare time at this point you should make a start the following week's work now.