Invariant Properties

I need to take a break from all-devops-all-the-time so I grabbed my Arduino toy chest (mostly sensors) and finally watched Ben Eater‘s excellent series on building an 8-bit computer on a breadboard.

Well… closer to a dozen breadboards.

There’s many hours of videos but you can tease out a dozen or so that have a really good example of encapsulation.

The first step is building basic logic circuits – AND, OR, INVERTER(NOT), NAND, and NOR(XOR – using discrete transistors. You can’t get more basic than that using electronics. (If you don’t limit yourself to electronics (transistors and vacuum tubes) uou can use electrical relays (relay ladder logic), pneumatic systems, or even mechanical systems like a stack of tinker toys.)

The next step is using these basic logic circuits to build “latches” and “flip-flops”. A “latch” holds a value even after the inputs have changed, a “flip-flop” has the practical effect of allowing you double the period of a clock cycle. That allows you to build binary counters.

It takes nearly a dozen videos to go from a “SR latch” to a “D flip-flop” but it’s an easy to follow series of progressive improvements. At each step an issue is identified and a solution identified. Sometimes there’s remaining issues, sometimes this creates a new issue, and the process continues.

One big difference from software is that the intermediate stages can still be very useful. If you know that you’ll never encounter the problematic input you can use the simpler circuits and reduce chip count and costs. You generally don’t see the same savings in software if you stay within the same abstraction layer.

The next step is using these latches and flip-flops to build adders (arithmetic control unit (ACU)), memory, etc.

The penultimate step is bundling these chips onto separate breadboards. We can start thinking of them in functional terms – clock, memory and registers, instruction pointer, microcode.

The final step is capturing one particularly nasty bit of logic in an EEPROM. A basic computer science truism is that a pure function (that is – one that does not depend on internal state) and a memory lookup are equivalent. You could use discrete logic to convert from the instruction set to the step of operations required to move data between elements of the processor but in this case it’s much better to use a memory lookup instead. It greatly reduces the risk of a wiring error, simplifies changing the “microcode” (e.g., to add a new instruction), etc.

We could build the “A register” out of discrete transistors, vacuum tubes, or even electrical relays (bombe, anyone?), but why? It comes down to who is looking at the circuitry. A human can only handle a few items at a time so a single breadboard containing at most 4 chips – no human could look at the equivalent collection of hundreds of transistors and make sense of it. It’s not worth our time or effort to peel back the encapsulation. If you do need to do it, e.g., to fit the logic in a FPGA or PLA, we’re still better off using a domain-specific language that allows the human to work at a high abstraction layer (e.g., registers or 3-to-8 decoders) and then uses an optimizer to eliminate redundant and unnecessary transistors.)

Further Ideas

I would have liked to seen how much of the existing circuitry could have been replaced by EEPROMs. E.g., the ‘clock’ uses a combination of analog electronics, switches, and logic chips to create the CLK, RST, ~RST signals used by the rest of the system. It seems like overkill – the cost of a small EEPROM is several times the cost of the individual logic chips – but perhaps a PLA could do the same work at about the same cost as the individual chips.

Another possibility is sticking with the EEPROM but combining related functionality. E.g., one of the main uses of the CLK is to increment the microcode counter. An EEPROM with an 8-bit output supports a 5-bit counter after accounting for the CLK, RST, and ~RST signals. Are there other places where related functionality can be combined?

Finally both approaches naturally lead to FPGA. In some ways it would be silly to have the ‘8-bit breadboard computer’ to be reduced to a single breadboard with a FPGA but at the same time it’s the culmination of a natural progression of encapsulating one abstraction layer after another.