Programming the Wireworld Computer

I previously wrote on Wireworld here: World of wires
It’s an interesting and entertaining cellular automaton, particularly the ease of simulating logic circuits it offers. Please take a look at the text and browse the links provided if you need a refresher on the rules of Wireworld.

One of the most fascinating things ever done in Wireworld is an implementation of a complete working computer (by David Moore,Mark Owen et al.). The computer (and its verbose description) can be found at: https://quinapalus.com/wi-index.html. The computer is presented there running a hard-coded prime search program (by Michael Fryers). Ever since I saw the computer, I thought it would be very fun to have a go at programming it. And wouldn’t it be great to have an interactive online tool to do just that?

The simulator is available here: Wireworld simulator

The program simulates the Quinapalus machine, and provides an interface to inject the instructions/data into its register bank. The machine can then be restarted to run a completely custom program.

The programming of the machine boils down to inserting a proper arrangement of pixels into its general purpose registers. I had to strip down the already working demonstration to revert it to its bare-metal state. In order to do that, I removed every unnecessary electron and synchronized the machine so that the electrons in the registers are aligned. The program can then insert the electrons and tails into the registers at their proper positions. The blank state machine is presented in Fig. 1.

Fig. 1. The blank state of the Quinapalus machine.

The simulation uses my own implementation of Wireworld rules. It’s most certainly not the fastest one available. It is probably possible to save the image generated by the program and import it into the dedicated cellular automaton running software, such as Golly (http://golly.sourceforge.net/). In the future, I’ll think about adding an export feature.

There are also further limitations. It is currently only possible to program the machine using hex codes for the instructions and the data. It would be good to add the possibility of using mnemonics, and - who knows - maybe even a C wrapper? ;)
The memory of the machine is of course limited. Moreover, the program only allows for writing into the registers R1-R52.

I must admit that I am no Javascript wizz. It took me long enough to get the demo working, and the code could arguably use some polish! Here it is: https://github.com/dagothar/wireworld-compiler

If you run into any problems running the code, please let me know. Any suggestions are welcome! I’m looking forward to improve the “compiler”.

(I haven’t probably synchronized the computer completely. Whenever it starts with a new program, it first prints out ‘65535’, then reverts to ‘00000’ before it starts printing out the commanded output. This is perhaps governed by the state of the frequency divisor at the bottom of the unit, but I haven’t yet figured how to set it appropriately.)

Programming the machine

Instruction set for the Wireworld computer is quite short. To be precise, the machine can only execute one instruction:

MOV Rd, Rs                  Move content of register Rs to register Rd

To quote its creators:

We wanted to make the Wireworld computer as simple as we could while still being able to run worthwhile programs. We therefore settled on a highly orthogonal RISC architecture.

The description of the instruction set (repeated below) is available at: https://quinapalus.com/wires10.html

Since only one instruction is available, all the more complicated operations are done using writing to/reading from special purpose registers. These registers are as follows:

Register	Action on read	Action on write
R0	Returns 0	Sends value to display
R53	Returns AND of R54 with NOT R53	Writes value to register
R54	Returns bitwise AND of R53 with NOT R54	Writes value to register
R55	Returns 0	Writes value to register
R56	Returns value in R55 if register R56 is non-zero, and the value in R57 otherwise	Writes value to register
R57	Returns 0	Writes value to register
R58	Returns R58 rotated right one place	Writes value to register
R59	Returns R59 rotated left one place	Writes value to register
R60	Reads value from the register	Writes value to register
R61	Returns sum of R60 and R61	Writes value to register
R62	Returns NOT R62	Writes value to register
R63	Returns program counter value	Causes branch (jump) to the given target

How to arrive at the hexadecimal representation given the mnemonic? Each command consists of two bytes (16 bits altogether). The two bytes contain the address of the destination/source respectively, e.g. MOV R60, R7 translates to 0x3c07 (00111100 00000111 ⇐=> 60, 7).

How to use the simulator?

Simply click ‘Start’ to launch the machine in its current state. The RAM is initially empty, and thus the computer will not do much. Left running on its own, the computer will repeatedly refresh the display with ‘00000’.

You can ‘Stop’ the machine at any time. If you wish, you can ‘Step’ through the simulation manually.

The interface on the left is used for programming the machine. In the text area, enter the hex codes of the instructions (or data) in separate lines. For example:

0x0001
0x0002
...

(Take care, I do not do much validation of the input at this point! If stuff breaks, simply reload the page.)

Click ‘Load’ to load the program into the memory. The machine will be reset and stopped, and you’ll have to ‘Launch’ it again.

Sample program

Now that we have dealt with the boring background, let’s try something practical.
The original program presented on the Quinapalus machine was a prime finder. Let’s try something a bit less sophisticated. How about just counting up (0, 1, 2, …)?

We can do that by writing the following code:

R1    MOV R0, R7    ; send R7 (counter) to the display
R2    MOV R60, R7  ; send counter to R60 (adder input 1)
R3    MOV R61, R8  ; send R8 (1) to adder input 2
R4    MOV R7, R61  ; send the addition result to counter
R5    MOV R63, R9  ; move R9 (R1 address) to jump back to the beginning
R6    MOV R0, R7    ; send counter to display again (branch delay)
R7    0                      ; contains counter
R8    1                      ; 1 for incrementing
R9    1                      ; jump target: R1

Then we have to compile it by hand. The compiled code is:

0x0007
0x3c07
0x3d08
0x073d
0x3f09
0x0007
0x0000
0x0001
0x0001

Go launch the simulator and try to run the program. It will be a while before it counts up a single tick (reserve at least a couple of hours to witness the true glory). The code has room for improvements. See if you can make it run smoother!

Fig. 2. Counter program reaching 2!

​

Langton's Ant

Langton's ant is a small bug that crawls tirelessly on a floor tiled with rectangular plates, which are black on one side and white on the other. Whenever the ant first steps on the plate, it checks its color and changes direction:

• if the plate is black - it turns to the right,
• if the plate is white - it turns to the left.

It then proceeds - a nasty little vandal - to turn over the plate it is now standing on: white to black or black to white. And then it moves forward (in the new direction) again.

Could the rules be any simpler? Of course, with such simple rules we do not expect the ant to exhibit any interesting behaviour. It will probably just run around in a circle, and maybe flip some tiles randomly. Nothing interesting can come out of such a system. Or can it?

Let's see what happens anyway. At first, it seems our predictions were correct. The ant produces simple and symmetric patterns (see Fig. 1).

Fig. 1. At first nothing interesting happens.

After a couple hundred of iterations, the patterns seem still quite symmetric and predictable (see Fig. 2).

Fig. 2. Making nice patterns.

After 2000 iterations chaos emerges (see Fig. 3):

Fig.3. The beginning of chaos.

We now change our prediction. The ant is going to fool around and paint the whole floor with no regard to symmetry or aesthetics - it is going to be a pure chaos.

Let's watch a little more...

This is what happens after ~11,000 iterations (Fig. 4):

Fig. 4. The ant escapes, leaving a "rose" behind.

After tumultous youth, the ant has abandoned its chaotic ways and started behaving orderly. The structure left behind reminds me vaguely of a rose. The ant now constructs a "highway", taking 104 steps to make yet another turn in the coil of the stalk.

How did this happen? Why did such simple rules result in so many different kinds of behaviours? From order, to chaos, to order again. How did the number 104 come up from the rules we have defined in the beginning?

There was certainly no way to predict the final result from those.

You can play with the Langton's ant using the simulator I made: https://rawgit.com/dagothar/langton-ant-js/master/index.html

As usual, the source files are provided: https://github.com/dagothar/langton-ant-js

 

Simply click Start. You can also try to make the ant go step-by-step with the aptly named Step button.

You can also draw on the board with the mouse! What do you think will happen when the ant encounters your drawings? Can you trap it? Will the ant draw a different shape?

 You can read more about the Langton's ant here: https://en.wikipedia.org/wiki/Langton's_ant

World of wires

Or Wirewold for short.

In good old days I spent an inordinate amount of time doing weird things, such as drawing and simulating spaceships and battles using humble MS Paint (that itself is worth making a post on its own - if for nothing else but to explain myself). What would I give to see my painstakingly hand-crafted animations to come to life all on their own! I wish I knew of Wireworld back then.

Wireworld is a cellular automaton designed by Brian Silverman in 1987 (yay, I was born the same year) to simulate the behaviour of digital circuits. Its Wiki page explains the rules briefly, but to the point: https://en.wikipedia.org/wiki/Wireworld.

Basically, you have a grid of 'pixels', each of which can be in four different states: empty, wire, head of the electron or tail of the electron.
Each turn the pixels change their state according to the following rules:
1. empty remains empty,
2. tail of the electron becomes the wire,
3. head becomes tail,
4. wire becomes a head if, and only if 1 or two adjacent cells (4-connectivity!) are heads.

These rules make it possible to construct all sorts of circuits (logic gates, clocks, flip-flops, frequency multipliers etc.). You can see several examples on the Wiki page.

Isn't it hypnotizing to watch the electrons zooming around on beautiful copper wires? I can watch them all day. Especially in this picture:

Fig.1. A computer calculating primes implemented in Wireworld (by http://www.quinapalus.com).

The circuit presented in Fig. 1 is a complete (and working) computer implemented in Wireworld (made by http://www.quinapalus.com). What's more, it is programmed to calculate and display primes! I remember running the simulation for many, many hours before I managed to witness it jump to next prime in line.
(Here you can watch the recording of the Wireworld computer: https://youtu.be/jnIs7n9-LKs - I still have to figure out how to encode the videos to be clearer though).

The inner workings of the simulated device are presented in great detail on its webpage. It describes the philosophy behind the clocks, logic gates, ALU and the memory of the machine (it's the long skewed bank of horizontal parallel lines on the right side of the image). It's interesting to read how it operates.

And they do have the assembly code of the CPU described there. You could program the computer to do something else altogether!

I made some implementations of Wireworld (long ago) to play with the concept. These were the days when my complete lack of knowledge about good programming practices didn't stop me to try and to write all sorts of things. You can only imagine how I feel looking back at the code. Nevertheless, here it is (you have been warned!): https://github.com/dagothar/wireworld

The programs were made to run on Ubuntu, but should work on Windows as well, if you manage to configure the environment. They use the allegro graphic libraries (http://allegro.cc), which you can install on Ubuntu easily:

$ sudo apt-get install liballegro4-dev

Then it's only a matter of makeing the projects. Sorry, there's not much support that I can give if things do not work out! I myself cannot make heads and tails out of the scramble.

Let me explain the programs briefly.

1.  wireworld program
 This one is more of a sandbox. The board is quite small, and the data is represented as a char array and stored in text files. You can paint on the board with the mouse; scroll wheel changes the type of the pixel that you paint (empty, wire, head, tail). Spacebar starts/stops the simulation. Escape closes the window. The default diagram loaded is that of a binary adder module and Gray to Binary decoder (see Fig. 2.). You can save your work (to save.wir file) by pressing the S key. L loads the file.

Fig. 2. Wireworld program. Gray2Bin decoder presented.

2.  wire program
This one is more versatile and powerful. The program accepts a .bmp file as input, e.g.:

$ ./wire circuit.bmp

 The colors of wires, heads and tails (in that order) are taken from the pixels in the upper left corner of the picture (top row). Spacebar pauses and starts the simulation. You can use S/L to store and load the diagram. The BMP file for the computer is attached (see Fig. 3.). If you wish to make your own design, simply draw one in any Paint-like program!

Fig.3. Wire program. Quinaplus computer loaded and running.

I should make a new implementation of the simulator one of these days!