Introduction
Nand2Tetris is a hands-on computer science course, starting from fundamental building blocks of digital logic all the way through to a functioning computer. The concept of the course is start with a single logic gate (the NAND gate), and through 12 successive chapters, build a computer capable of running programs written in a high level programming language. Notably, the course is freely available.
The course follows the book “The Elements of Computing Systems: Building a Modern Computer from First Principles” by Noam Nisan and Shimon Schocken.
Each chapter builds progressively on the previous, covering topics such as Boolean logic, hardware description languages, computer architecture, machine language, assembly programming, compilers, and even operating system fundamentals.
By the end of the course, a simple, yet capable 16 bit computer is created which can run an object oriented programming language. Assembly, virtual machine, and high level programming language are designed and compiled. Finally operating system functionality is added, and the course leaves it to the student to continue work such as:
- Programming a game (such as Tetris)
- Extensions to the computer architecture, and various programming languages
- Performance optimizations
Course Scope
The course covers the following topics (click to expand):
Hardware:
Boolean arithmetic, combinational logic, sequential logic, design and implementation of logic gates, multiplexers, flip-flops, registers, RAM units, counters, Hardware Description Language (HDL), chip simulation, verification and testing.
Architecture:
ALU/CPU design and implementation, clocks and cycles, addressing modes, fetch and execute logic, instruction set, memory-mapped input/output.
Low-level languages:
Design and implementation of a simple machine language (binary and symbolic), instruction sets, assembly programming, assemblers.
Virtual machines:
Stack-based automation, stack arithmetic, function call and return, handling recursion, design and implementation of a simple VM language.
High-level languages:
Design and implementation of a simple object-based, Java-like language: abstract data types, classes, constructors, methods, scoping rules, syntax and semantics, references.
Compilers:
Lexical analysis, parsing, symbol tables, code generation, implementation of arrays and objects, two-tier compilation.
Programming:
Implementation of an assembler, virtual machine, and compiler, following supplied APIs. Can be done in any programming language.
Operating systems:
Design and implementation of memory management, math library, input/output drivers, string processing, textual output, graphical output, high-level language support.
Data structures and algorithms:
Stacks, hash tables, lists, trees, arithmetic algorithms, geometric algorithms, running time considerations.
Software engineering:
Modular design, the interface/implementation paradigm, API design and documentation, unit testing, proactive test planning, quality assurance, programming at the large.
Capstone Project: Creating Tetris
Programming a game like Tetris was much more involved that I thought – but like the rest of the course, I broke it down into smaller manageable parts that can be developed and tested.
At first, a class was created that represents a tetrimino (the game pieces that contain four blocks). This class draws sprites (a fixed bitmap image) to show where the four blocks are. It can also hide those sprites by drawing them in white, which is necessary before movement can occur otherwise it would ghost across the screen. Translation and rotation input are handled from the user. At this stage, only the “T” tetrimino can be produced.
Next up was to add collision detection between other tetriminos and the walls of the game. The tetrimino class does this by simply looking at pixel values. When a bottom collision is detected, that tetrimino object is disposed off, leaving its “ghost” blocks in place. A new tetrimino is then created at the top of the game.
The game class watches for complete lines and clears them recursively at each time step of the game. If a complete line is detected, it clears that line, moves all the existing blocks downward, and re-checks for complete lines.
Next up the rest of the tetrimino shapes were added. To chose the next shape, a pseudo-random number generator was created using the Linear Congruential Method, which uses simple operators (plus, multiply, and modulo) to generate seemly random numbers based on an initial seed. At this point, the seed was hardcoded, so the game would still generate the same order of shapes every time, but we will see this improved later. A indicator for the next shape was also added.
An interesting addition to the code complexity I didn’t think about initially is that in certain cases tetriminos need to be moved off the wall if they are rotated. Otherwise, their shape would overlap the wall or other tetriminos. To solve this, the code actually temporarily allows the rotation first and checks for overlap. If overlap is present, a move away is attempted. If the move is successful, the rotation is allowed. Otherwise, the rotation is undone.
After the following changes, the game started becoming fun to play during testing! The tetriminos now move down automatically, at a increasing speed determined by the current level. Scores are calculated based on number of lines cleared at once and the current level. Game over is detected if the tetriminos pile up too high.
Also, the game is no longer deterministic in the way that tetriminos are chosen – the psuedo-random number generator is seeded by the time (technically… computer cycles) from initial start up to the first key press.
Finally, the user can hold the down arrow to rapidly send the tetrimino downward. This last addition required re-writing the key detection code completely. A new timer value was added and rather than the code waiting for the next key press, it (at a high level) continuously checks for new key presses. Programming smooth game operation on such a simple computer and language was an interesting challenge as I was used to more advanced constructs like hardware interrupts to check for hardware pin states.
Finally, after a bit of visual clean up and a “Press Start” type game entry, I’, pleased to present the final version of the game.
Comments & Reflections
The Journey
This was by far the biggest undertaking in self-learning I’ve taken on. It’s tough to know the total hours put in, but roughly estimating 12 chapters at 20-30 hours each, that’s 240-360 hours. This could easily be a complete undergraduate course over a semester.
This course was an incredible journey that completely fulfilled my desire to understand things from first principles. Many of the topics I had heard of but were always “black box” mysteries.
“Any sufficiently advanced technology is indistinguishable from magic.” -Arthur C. Clarke
The course takes these “black boxes”, explains them logically and systematically, has you build them yourself so you actually internalized them, then turns them back to into black boxes – abstracting them so you can focus on the next level of complexity. This allows you to fully grasp those constructs’ rationale and realize their capability. At the same time, the course is also modular, so that if one wishes, individual chapters could be learned on their own.
The Beauty
Over completing this course, it was amazing to see what seemed like arbitrary design decisions materialize into meaningful simplifications, optimizations, or elegant solutions to complex problems.
One of which is the breaking apart of the high level compiler to assembly code into two stages – high level to virtual machine code, and virtual machine code to assembly code. The stack architecture that the virtual machine implements conveniently solves the implementation of abstract ideas like a function, and what it means to return from a function and recursively call a functions.
I can also commend the authors successful efforts to create a architecture that is simple enough for one person to learn in a reasonable amount of time, yet powerful enough to be capable of running fully functional, interactive programs.
Along the way, they are careful note where complexity has been left out intentionally to leave the course a reasonable length – and where more learning can be had, should to student want.
Lessons Learned
- To implement the assembler (converts virtual machine code to assembly code) and the compiler (converts high level code to assembly code), I used Python as I enjoy using the language and was hoping to become more proficient. In completing this course, I certainly became a better Python programmer, and a better programmer in general.
I had previously hesitated to implement classes, (relying mostly on code abstraction by functions). I learned during programming for this course how useful even a simple class can be for creating legible, simple code. - This project was sufficiently complex that I truly learned the value of unit testing individual functions and classes – and leaving those tests intact. Whenever I had doubt about what was happening with my code, I could create more intricate or specific tests of my previously written code to verify what I was relying on was correctly working.
In particular, using the bit of Python code
“if name == ‘main’:” was useful in running test code on classes and functions, without having it run on calls to those classes and functions.
Ethan's Projects 