Build a Computer from NAND Gates

Part 10: Beyond - Extensions and Explorations

We've built a complete computer system from first principles. But this is just the beginning. Here are directions to explore further.

What we built

Let's recap the complete stack:

Each layer abstracts the one below, enabling higher-level thinking.

Hardware extensions

More instructions

Our CPU has a minimal instruction set. You could add:

Multiplication/Division hardware: Instead of calling OS functions, add dedicated circuits.

Bit shifting: SHL (shift left), SHR (shift right), ROL (rotate).

Stack operations: Hardware PUSH and POP instructions.

Interrupts: Allow external events to interrupt execution.

Pipelining

Our CPU executes one instruction at a time. Real CPUs overlap stages:

Instruction 1: Fetch → Decode → Execute → Writeback
Instruction 2:         Fetch  → Decode  → Execute  → Writeback
Instruction 3:                  Fetch   → Decode   → Execute  → ...

This increases throughput but adds complexity (hazards, stalls).

Cache memory

Memory access is slow. Add a small, fast cache:

CPU ←→ L1 Cache (1 cycle) ←→ L2 Cache (10 cycles) ←→ RAM (100 cycles)

Cache management is a rich topic: write-through vs write-back, replacement policies, coherence.

FPGA implementation

Our simulator runs in software. You could implement the Hack CPU on an FPGA (Field-Programmable Gate Array):

1. Write hardware description in Verilog or VHDL
2. Synthesize to FPGA bitstream
3. Run on actual hardware

This gives real parallel execution and nanosecond timing.

Software extensions

Better compiler

Our Jack compiler is minimal. Real compilers add:

Optimization:

• Constant folding: 3 + 4 → 7 at compile time
• Dead code elimination
• Register allocation
• Inlining

Type checking:

• Verify types match
• Catch errors before runtime
• Enable better code generation

Better error messages:

• Source locations
• Suggestions for fixes
• Recovery to find more errors

Garbage collection

Jack requires manual memory management. Add automatic garbage collection:

Mark and sweep: Periodically find unreachable objects and free them.

Reference counting: Track how many pointers reference each object.

Generational GC: Most objects die young; optimize for this.

Exception handling

Add try/catch/throw:

try {
    let x = dangerousOperation();
} catch (e) {
    do handleError(e);
}

This requires:

• Stack unwinding
• Exception objects
• Runtime type checking

Inheritance

Jack is object-based but not object-oriented. Add inheritance:

class Animal {
    method void speak() { }
}

class Dog extends Animal {
    method void speak() {
        do Output.printString("Woof!");
    }
}

This requires:

• Virtual method tables (vtables)
• Dynamic dispatch
• Type hierarchies

Operating system extensions

File system

Our OS has no persistent storage. Add a file system:

API:

File.open(path, mode)
File.read(handle, buffer, size)
File.write(handle, buffer, size)
File.close(handle)

Implementation:

• Directory structure
• File allocation (contiguous, linked, indexed)
• Disk block management

Processes

Our system runs one program. Add multitasking:

Process abstraction:

• Each process has its own memory space
• Context switching saves/restores registers
• Scheduler decides which process runs

Concurrency primitives:

• Semaphores
• Mutexes
• Message passing

Networking

Connect to other computers:

Protocol stack:

• Physical layer (bits on wire)
• Data link (frames, MAC addresses)
• Network (IP, routing)
• Transport (TCP, UDP)
• Application (HTTP, etc.)

Socket API:

Socket.connect(host, port)
Socket.send(data)
Socket.receive(buffer)

Application ideas

With our platform, you could build:

Games

Tetris: Falling blocks, collision detection, scoring.

Snake: Grid movement, growing body, food.

Pong: Ball physics, paddle control.

Utilities

Text editor: Buffer management, cursor control, file I/O.

Calculator: Expression parsing, arbitrary precision.

Simple shell: Command parsing, program loading.

Graphics

Mandelbrot set: Complex number iteration, pixel coloring.

3D wireframe: Matrix transformations, perspective projection.

Turtle graphics: Logo-style drawing commands.

Learning more

Books

"The Elements of Computing Systems" (Nisan & Schocken): The book this series is based on. More depth on every topic.

"Computer Organization and Design" (Patterson & Hennessy): MIPS architecture, detailed hardware.

"Compilers: Principles, Techniques, and Tools" (Aho, Lam, Sethi, Ullman): The "Dragon Book" for compiler design.

"Operating Systems: Three Easy Pieces" (Arpaci-Dusseau): Processes, memory, concurrency.

Online resources

nand2tetris.org: Official course materials, software, projects.

From NAND to Tetris (Coursera): Video lectures by the authors.

Projects

Build your own:

• Different ISA: Design a RISC-V or ARM-like instruction set
• GPU: Add graphics acceleration hardware
• Virtual memory: Page tables, TLB, swapping
• Compiler for a different language: Lua, Lisp, a custom DSL

The bigger picture

Building a computer from NAND gates teaches something profound:

Abstraction is power. Each layer hides complexity:

• Logic gates hide transistor physics
• CPUs hide gate-level details
• Assembly hides binary encoding
• High-level languages hide memory layout
• Operating systems hide hardware differences

Everything is computable. Any computation expressible in logic can be built from NAND gates. This is the Church-Turing thesis in action.

Simplicity compounds. Simple rules, applied recursively, create complexity. A NAND gate is trivial. A million of them, organized correctly, is a computer.

Conclusion

We started with a question: How does a computer work?

Now we know. Not just abstractly, but concretely. We've built every layer:

• Hardware: From Boolean logic to a functioning CPU
• Software: From machine code to a high-level language
• Tools: Assembler, VM translator, compiler
• Runtime: Operating system services

The mystery is gone. A computer is not magic. It's engineering. Layer upon layer of careful abstraction, each one enabling the next.

You now understand something most programmers never learn: what happens all the way down.

---

Series summary

Thank you for following along. Now go build something amazing.

---

This concludes the 10-part series on building a computer from first principles.