Arrows

The beauty of simple rules creating complex and unique behaviours always amazes me. In this post, I discuss how basic arrows can be combined to create logic gates and, eventually, an adding machine.

We will be working with three types of arrows: the normal arrow (→), the invert arrow (»), and the divide arrow (↔). By combining these arrows, we can create a variety of logic gates, including the OR gate and the NOT gate. While these two gates allow us to create any Boolean expression, having AND and XOR gates makes building even easier.

Using De Morgan's laws, we can create an AND gate from NOT and OR gates. This is equivalent to NOT ((NOT A) OR (NOT B)); translated into arrows, it looks like this:

The XOR gate is more challenging to create with arrows because there is no easy way to cross lines. A real chip has multiple routing layers that let wires pass one another, but this two-dimensional representation does not. The first diagram below is my partial solution for an XOR gate. For the second, I took the lazy route and used a non-overlapping arrangement of NOR gates.

Now that we have the basic gates, we can combine them to make a simple adder.

Adding Machine

Addition is one of the core operations performed by a computer's arithmetic logic unit (ALU).

We can start building an adder. The truth table is below:

The most common half-adder design looks like the following. We cannot implement it directly because the lines would need to cross at the point shown in red.

To work around that limitation, I cross lines by taking an XOR of an XOR. The identity A = XOR(XOR(A, B), B) lets the signal emerge on the other side, as shown below.

Replacing every crossing with that identity takes many arrows. It would be fun to create a reduction function that rewrites a Boolean expression to reduce line crossings, or at least identifies where a crossing costs more than three XORs. Even a function that counts the crossings in an expression could become part of an optimizer.

Converted into arrows:

We have built a half-adder, which has no carry input. We can add one by combining two half-adders with an OR gate:

Reusing half-adders means we do not have to design another circuit; we can place the existing blocks into the new design.

Finally, we can combine four full-adders to make a 4-bit adder.

I enjoyed making this; it was a fun challenge, and I learned a lot. I hope to return to it and try building a simple computer. I am sure everything could be much smaller and faster.

The game logic runs in Rust with help from ggez, a library for window management, 2D graphics, and event handling. Rust makes it possible to simulate a large number of states quickly. Python calls the Rust library through a C foreign-function interface (FFI).

The Python side places the arrows. A Board object is sent to Rust to be displayed and run. Python also contains a higher-level drafting tool in which more complex boards can be designed. The drafter includes a topological-layout function for arranging sub-blocks and a basic wire router that uses breadth-first search. I later dropped some of these experiments, but the ability to try ideas quickly was important.

If you would like to inspect or run it, the code is available on GitHub.