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++.)

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.

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.