Disappearing down the ‘Nand to Tetris’ rabbit hole

A few months ago I read an article on Medium that recommended a few books, amongst them was ‘The elements of computing systems’, better known by its nickname ‘From Nand to Tetris’. This book describes how computers work from basic logic gates all the way up to compilers and walks you through building these systems. I loved it, the supporting web site is here Home | nand2tetris

One of the reason I liked it so much was that it took me back to somewhere around 1970. My father was an officer in the English army and went on an intro to computers course, he gave me some of the course material. A big chunk of it was all about gates, flip flops, half adders etc. This really ignited my passion for all things digital, and I never looked back. (I retired a few years ago from a very happy software career). The first half of this book was almost identical to that course material.

The ‘hack’ system

The system built by this book (aka the ‘hack cpu) is extremely simple but they manage to coax a lot out of it.

• 16 bit machine with memory organized in 16 bit words
• 32k words of instruction memory (ROM basically)
• 32k words of data memory
• Memory mapped peripherals. Screen and keyboard.

CPU:

• 2 instructions! Not really, the second instruction has a lot of variations
• No memory protection, no interrupts
• No shift / rotate, carry / borrow, stack, relative branch

But despite these limitations the book walks through build progressively higher- and higher-level systems and languages on top of it. Finishing off with a single player Pong like game written in a Java like OO language (‘jack’).

In the process the reader gets to implement the CPU using HDL and a chip emulator; to create an assembler, a virtual machine compiler and the jack compiler.

Its real fun.

My rabbit hole

I had been looking for an FPGA project for some time, because — why not?

This one seemed perfect. In the book they even suggest it as a project. I got the basics working but then thought ‘what should I do with this?’, reproducing the system from the book didnt seem that much of a challenge. Then I recalled an earlier system I built an emulator for — the PDP11. The first version of this machine is about the same power as the hack system.

• 64k RAM of instructions and data
• No memory protection
• 4mhz clock (my FPGA version runs at 25mhz)

This system ran a version of Unix called mini-unix which was a derivative of Unix version 6 designed to run on the minimal pdp11. See MINI-UNIX — Computer History Wiki (gunkies.org) and Mini-UNIX (tavi.co.uk)

So I decided to try to get mini-unix running on the hack system, implemented on an FPGA. And thats the hole I have disappeared down.

The building blocks

(I will probably post about these in more detail later)

FPGA implementation

The FPGA implementation of the system, plus supporting peripherals. It surely needs a disk drive. That can be added as a memory mapped device just like the screen and keyboard. Also needs ways to get data on and off and a debugging mechanism.

‘Jack’ toolchain

I realized that I needed non trivial code to test my initial FPGA system. So I decided to complete the s/w part of the book, writing a complete toolchina to compile the Jack language down to raw machine code. I did this in rust , because I love rust. The compiler itself is not useful for min-unix but it lets me build non trivial s/w to run on the system; pong anyone?

Emulator / debugger

I am going to need a emulator / debugger. Debugging on the FPGA hardware is tough so I expect to spend most of my time in an emulator / debugger. The course comes with an emulator (that’s slow) with extremely limited debugging capabilities.

So I am writing an emulator / debugger. Its written in rust, and uses the egui GUI framework egui — Rust (docs.rs). This allows it to run on Windows, Linux, Mac and in a browser. I previously wrote a debugger for the 6502 emulator and posted about it here Interfacing C With Rust To Build a Debugger | by Pm | Rustaceans | Medium

I need to update the toolchain to generate debugging information, line numbers, variable meta data, function addresses etc.

C Compiler

I need a c compiler since that’s what mini-unix is written in. I have started adding a hack backend to the tiny c compiler. Tiny C Compiler Reference Documentation (bellard.org). This is a huge task 🙂

Collaborators

I would love to share the workload with others, even though its a totally useless project, nobody will ever use it for anything real, it is full of interesting challenges:-

• Learn how mini-unix is put together
• Build FPGA project
• Learn rust and egui
• Build a c compiler backend
• Build a debugger

If interested, say something in the discussions section of my repo for the compiler toolchain here pm100/hack · Discussions · GitHub