Building an Unlimited Register Machine in Elm

One of the highlights of the 2016 Strange Loop conference in St Louis was the Tom Hall talk Unlimited Register Machines, Gödelization and Universality, which I’d recommend you watch over at the Strange Loop YouTube channel.

Tom’s talk was inspired by the chapter The Seven Secrets of Computing Power Revealed from the book Intuition Pumps and Other Tools for Thinking by the American philosopher Daniel Dennet. In it Dennet says:

Computers are without doubt the most potent thinking tools we have, not just because they take the drudgery out of many intellectual tasks, but also because many of the concepts computer scientists have invented are excellent thinking tools in their own right.

Computers can carry out incredibly complicated tasks, but these tasks are composed of steps that are relatively simple. If we can understand how these simple steps are composed to create complex programs, we can reason about how other complex machines could actually be built from simple steps. For example it can be used to consider how it’s possible that a human brain consists of nothing but billions of simple neurons, yet can exhibit extremely complex behaviour.

Apart from being a very interesting philosophical topic, building and understanding how programs can be written for a simple register machine is a fun software engineering problem.

In his talk Tom demonstrated the topic using an unlimited register machine written in ClojureScript. I decided to try building one in Elm.

Unlimited Register Machines

An unlimited register machine (URM) is an idealised computing device which is useful for teaching the basics of how a computer works. For this reason it is particularly relevant in this context. Any properly defined URM is Turing equivalent and therefore is also equivalent to Von Neumann machines such as our smart phones or laptops. Anything your laptop can do can also be done by a URM, albeit at a much much slower rate.

A URM contains a finite number of registers and can execute programs. The registers are labelled with an address (register 1, register 2, etc.) and can hold a single positive integer value. Programs are sequences of instructions which the URM can execute. Like the registers, instructions are labelled 1, 2, 3 etc. so it is possible to refer to an instruction by index.

The URM that Dennet describes understands three instructions. These are:

Exit : Stop execution. At this point the program is complete

Inc a x: Increment the value of register a and then go to instruction x

Deb a x y: If the value of register a is not already zero, decrement it and go to instruction x. If it is already zero, leave the value unchanged and go to instruction y

So for example a simple program to increment the value of register 1 twice looks like this:

1. Inc 1 2
2. Inc 1 3
3. Exit

Here is another program to zero out the contents of register 1:

1. Deb 1 1 2
2. Exit

And a bit more interesting, here is a program to add the value of register 3 to that of register 4 and place the result in register 1, leaving the values of registers 3 and 4 unchanged:

1.  Deb 3 2 4
2.  Inc 1 3
3.  Inc 2 1
4.  Deb 2 5 6
5.  Inc 3 4
6.  Deb 4 7 9
7.  Inc 1 8
8.  Inc 2 6
9.  Deb 2 10 11
10. Inc 4 9
11. Exit

You can see these and a few other programs in action in the live demo.

Implementing a URM in Elm

I implemented a URM in Elm along with a simple UI for visualising the machine and some example programs. It’s quite basic right now but you can see it working here and find the code on GitHub. For the rest of the post I’d like to describe the Elm code for the core of the machine.

Elm allows you to create programs with no run time exceptions by virtue of the fact it is a statically typed language. In Elm you model your problem by designing your types, which thankfully is pretty easy thanks to the well designed type system.

We can start by representing the registers of our machine using the Elm Array type. This gives us a nice way to read and write the values of our registers using the get and set functions of the Array module.

registers : Array Int

We can also use the Array type to represent our program, but first we need to define our instructions. Since we know we have just three types of instructions we can use an Elm union type.

type Instruction
    = Exit
    | Inc Int Int    
    | Deb Int Int Int
program : Array Instruction

Here we are saying an Instruction must be one of Exit, Inc or Deb and that Inc is tagged with two Int values and Deb is tagged with three Int values.

With the Instruction type defined we can then say our program is an Array of Instructions.

To represent the state of our machine at any given point, we create a type alias to a record which includes the registers, the program, a flag to indicate if the machine has exited and a program counter to keep track of the next instruction to execute.

type alias State =
    { registers : Array Int
    , program : Array Instruction
    , exited : Bool
    , programCounter : Int
    }

Now we create the step function. This function takes a URM state and returns the new state after the next instruction is executed. Like all great programs, it is a giant case statement.

step : State -> State
step state =
    let
        cmd =
            nextInstruction state
    in
        case cmd of
            Exit ->
                { state | exited = True }

            Inc register nextInstr ->
                { state
                    | programCounter = nextInstr
                    , registers = 
                         incrementRegister state.registers register
                }

            Deb register successIndex branchIndex ->
                let
                    ( newRegisters, decremented ) =
                        decrementRegister state.registers register

                    nextInstr =
                        if decremented then
                            successIndex
                        else
                            branchIndex
                in
                    { state
                        | programCounter = nextInstr
                        , registers = newRegisters
                    }

If we step through this program we can see we first get the next instruction on line 5. The nextInstruction function is not shown here but it basically pulls the instruction from the states program based on the programCounter.

Now we get into our three cases.

For the Exit case we simple return a new state with the exited flag set.

For the Inc case, we return a new state with the programCounter updated to the correct instruction and a new registers Array which is the result of the incrementRegister function. This function is shown below:

incrementRegister : Array Int -> Int -> Array Int
incrementRegister registers index =
    let
        arrayIndex =
            index - 1

        value =
            Array.get arrayIndex registers
                |> Maybe.withDefault 0
    in
        Array.set arrayIndex (value + 1) registers

There is a little bit of cheating happening here. When we get the current value of the register, if it doesn’t exist, we default to zero. Since Array.set with an out of bound index returns the array unaltered, this whole function is a no op if the register does not exist. Also note how we switch from 1 based to zero based indexing since the registers are labelled 1, 2, 3 etc. while the Array type used zero based indexing.

The Deb case is a bit more complicated. The corresponding function to incrementRegister here is decrementRegister. This returns a tuple containing the new value of the registers as well as a flag to indicate if it was possible to decrement the register value. We then use the flag to determine what the next instruction will be before returning a new state.

For completeness decrementRegister is show here:

decrementRegister : Array Int -> Int -> ( Array Int, Bool )
decrementRegister registers index =
    let
        arrayIndex =
            index - 1
        value =
            Array.get arrayIndex registers
                |> Maybe.withDefault 0
        decremented =
            value > 0
        newValue =
            if decremented then
                value - 1
            else
                0
    in
        ( Array.set arrayIndex newValue registers, decremented )

Hopefully this is now easy to understand. We have the same “cheating” approach to out of bound registers and we add some basic conditional logic to decide the new value of the register.

And that’s it! My entire URM is implemented 121 lines of Elm code. It’s worth remembering that since the URM is Turing equivalent, those 121 lines of code can do anything that the Von Neumann machine inside any laptop can do. In fact because it is a true universal machine, the climax of Toms talk is to show how, with a little creativity, it is possible to write a URM program that itself simulates a running URM, something we more commonly refer to as a virtual machine.

No more secrets!

The final of Dennets seven secrets of computing power is that “There are no more secrets!” and demonstrating this point is the purpose of building a URM like this. All improvements found in modern hardware are just more efficient ways to do the same things this register machine can do.

I’ve used my app to explain computers to several non software engineers and have found that it does not take very long to understand it.

I’ve also found it a lot of fun writing programs for it. It’s certainly been a good reminder of just how far programming languages have come when switching between writing fiddly URM programs and far easier to write Elm code.

Interested in making an Impact? Join the carwow-team!
Feeling social? Connect with us on Twitter and LinkedIn :-)