From Nand to Tetris, via Scala

Nand to Tetris, or Building a Modern Computer From First Principles is a project-based course and book in which you build a hardware and software platform capable of running games such as Tetris, starting from simple logic gates such as NAND.

What’s in the box

Ironically, throughout the book you’re not building NAND or Tetris, but everything in between.

Hardware

We start our journey with basic gates like Not, And, Mux, but also more advanced components like ALU, Register, RAM and finally CPU and COMPUTER.

All hardware work is done virtually using an HDL variant and a supplied hardware emulator. There is also a CPU emulator for testing CPU commands, which will come in handy later.

Software

Having our CPU chip we later create an assembler which encodes our assembly mnemonics to actual CPU commands.

Next you might expect a compiler, but Nand2Tetris takes the software abstraction exercise a bit further and defines a Hack Virtual Machine, so we also write a VM translator that accepts code in Hack VM bytecode and outputs assembly.

Subsequently, we construct a compiler for an object-oriented language targeting the Hack VM, which is similar to Java, but closer to the hardware like C. The Hack VM emulator that comes with the suite is useful for testing it.

The final step is to develop operating system services and a standard library for our imaginary platform. Without these, we wouldn’t be able to display anything on the screen.

General impression

What I really like about Nand to Tetris is not just the insights you get into the low-level workings of your computer system, but the whole streamlined experience.

Before this book, I tried to get into Computer Systems: A Programmer’s Perspective. It was a tough ride. Not only is the book less accessible, but the widely available, global edition has a lot of errors, and no errata. Working through the exercises in this way and on your own can be a little bit frustrating.

On the other hand, Nand to Tetris comes with a whole suite of tools and tests that automates checking and debugging your solution. You can even approach it in a test driven development fashion.

Moreover, there is a Nand to Tetris VS Code extension which adds syntax highlighting for various Hack platform sources and the ability to run/compile the code directly from the editor.

Project Highlights

The hardware part of the course was relatively straightforward. The software part, starting with Chapter 6 was definitely more challenging - the project exercises were more involved, with a bigger potential error surface.

The three major software projects I mentioned earlier were Hack Assembler, Hack VM and Jack Compiler.

I decided to do them in Scala, a plain Scala variant to be exact. My goal was to keep things simple, with a minimal level of abstraction, but with code that felt “Scala”. I also kept the dependencies to a minimum, using only the standard toolkit and the always handy pprint. No parser combinator libs, or any other fancy stuff.

HASM

The Hack assembler was a simple affair. The only thing worth mentioning, which differs from the book requirements is my Codes trait.

trait Codes[O]:
  def fromNumber(number: Int): O
  def fromA(address: Address): O
  def fromC(instruction: Instruction.C): O

Codes is type class for encoding HACK’s CPU instructions. There is an implementation for outputting them in a string format in the form of Codes[String], which works well with the tools provided with Nand 2 Tetris suite, but for a real machine we would like to use something in the form of Codes[Bytes] instead.

HACK VM

Hack VM translator, the backend for our compiler that outputs Hack ASM code. There was definitely more work on this one to pass all the tests. The core functionality is kept in HASMWriter.scala, which at first glance might look scary, but I think it has a nice structure to it.

I may have gone a bit overboard with the \ dsl for composing asm code, but I just couldn’t help it…

extension (s: String)
    inline def \(inline line: String): String = s + "\n" + line
    inline def \?(inline line: Option[String]): String = line match
        case Some(l) => s \ l
        case None    => s

Jack compiler

And finally, the most complicated part.

Some of the complications come from the inherent nature of the problem we are trying to solve, some from my own choices.

The first necessary part was the Tokenizer, which takes a stream of strings and outputs a stream of tokens. The output from Tokenizer is piped to the SyntaxAnalyzer, which creates an abstract syntax tree using the full Jack Grammar. The AST is then piped to the Compilation Engine which outputs Hack VM code.

Originally, in the book, the SyntaxAnalyzer is just a temporary step for building an actual compilation engine. I decided to keep it separate because it makes the compiler design more flexible. If we had to do syntax rewrites, aka syntactic sugar, it would be done at this stage.

For both SyntaxAnalyzer and Compilation Engine I decided to use a little abstraction in the form of ResultT, which is essentially a wrapper around TailRec[Either[Error, A]]. The TailRec is just a simple ADT that helps us create stack-safe, trampolined recursive algorithms. In retrospect, I should have used something like a mutable stateful iterator or StateT instead. I had some state in the form of consumed tokens amount and context that made the code less readable and it desperately needed some encapsulation.

Jack OS

The Jack OS services from chapter 12, like Screen.jack or Output.jack, although not in Scala, are also worth mentioning. With some of them, like the printChar method, I also had quite a lot of trouble.

Summary

Completing all these exercises takes a lot of time and energy. Skimming through the book without doing them won’t give you much. But if you want to learn, or re-learn how computers work and have some free time then I cannot recommend it highly enough.