Oct 17

Nand2Tetris: project 8 completed

With project 8 completed, I now have a Virtual Machine translator that takes any VM program as an input and outputs a corresponding Hack assembly file (see project 4) that can be run on the Hack CPU simulator. Since I had a few bugs, I ended up step through some code at the assembly level for the recursive Fibonacci example, which was an interesting exercise of concentration and patience.
The virtual machine in question is a single stack-stack machine, that provides support for function calling, including recursion.
After having implemented it, one feels quite at home reading section 2.1.1 Single vs. multiple stacks from the book Stack computers: the new wave by Philip Koopman (it is from 1989, so new is relative, but it is available online and it is one of the very few publications available about stack machine hardware).
Quoting the section:

An advantage of having a single stack is that it is easier for an operating system to manage only one block of variable sized memory per process. Machines built for structured programming languages often employ a single stack that combines subroutine parameters and the subroutine return address, often using some sort of frame pointer mechanism.

This “sort of frame pointer mechanism” is precisely what I have implemented in project 8. In our case, the stack machine is not built in hardware, it is implemented in the form of a translator to the machine language of a simple 16-bit register based CPU. It could however be directly built in hardware, as the many examples given in Stack computers: the new wave show. I suppose a very interesting project following this course would be to implement the VM specification of chapter 7 and chapter 8 in the HDL language in the same way as the Hack CPU was built in project 5. I am not sure how much the ALU would have to be modified to do that.
I will keep this project idea in the back of my mind for now and move on to chapter 9, where we study “Jack”, a simple object oriented high level language, that we will in later chapters write a compiler for. The compiler will use the VM translator implemented in chapter 7 and chapter 8 as a back end.

Oct 06

Nand2Tetris: computer implemented and verified (project 5)

Yes, that’s right. In three days (quite busy, I have to admit), I have constructed a working 16-bit computer from Nand gates, that is able to manage I/O with memory mapped keyboard and monochrome screen. Am I a genius? Not even close. I have just been walking in the footsteps of Noam Nisan and Shimon Schocken, two wonderful professors who are currently giving me for free a once-in-a-lifetime experience in the category construct-a-simple-and-yet-powerful-computer-from-scratch! Their design is so elegant that every project step mostly consists in putting together pieces of a puzzle that just fall into place.
A few highlights:

  • Gluing together the RAM with the keyboard and screen gave for some interesting muxing/demuxing, due to the different sizes of their respective memory areas.
  • When it comes to the CPU, I had first planned to construct some separate control logic chip, but the pieces fit together so well that I finally didn’t think it was necessary.
  • Lastly, composing the computer from ROM, RAM + I/O and CPU was almost as easy as building the first logic chips of chapter 1.

Certainly if it is so easy, I cannot have learned that much, right? Wrong. I guess pedagogy could be defined as the ability to provide the highest teaching value per unit of of time spent by the student. And Noam Nisan and Shimon Schocken are certainly masters of pedagogy. No wonder Shimon Shocken is currently working on a program to revolutionize math teaching for young children.
A couple of additional details about his module:

  • Test scripts are for the first time in this module coming in two flavors: the regular ones and the “external” ones. I have not found an explanation about what the external ones could be all about (I might have overlooked some information in my hungry book and web site browsing), so I diffed the CPU scripts, and found that the only difference was an explicit reference to the DRegister chip in the non-external script. My implementation did not use that chip, it just used the regular Register as a D-Register. I think that the DRegister chip really is a regular Register, with an additional GUI-side effect allowing one to see its contents – presented as the D-register’s contents – while running. When it comes to the non-external test script, I think the point is that it is not only testing the outputs of the tested chip, but also some internal state (in this case the D-register). Anyway, when using DRegister instead of just Register for the D-Register, both test scripts run successfully on my implementation.
  • When I run the CPU test script for the first time, I had two control bit bugs (as it turned out). The first one made the output file comparison fail on the 2nd result row. That pretty much indicated an obvious bug. But the second bug made the script fail at the 62nd result row, which I found really surprising. That bug was more nasty, which can happen in a design that after all is not that trivial. Comparing the result rows did however allow a bug resolution within minutes.

Next step: writing an assembler for the machine. I cannot wait. :-)

Oct 04

Building a Modern Computer from First Principles

The free and open source NAND to Tetris course has been teasing me for a few months.
I believe I first heard about it in the text attached to the following video.

The video shows an implementation of the ALU from the course in Minecraft, which is pretty amazing, but more importantly it made me aware of the course. The course site in its turn made me discover that designing one’s own general purpose computer from scratch was apparently not beyond reach. I will humbly admit that before discovering that course, although I have an academic degree in computer science, I would not have thought that one could design a general purpose 16-bit computer in the scope of a one-semester course homework.
After watching several videos by Shimon Schocken, a sympathetic human being who is one of the two professors behind the course (see Quick presentation, Google talk and TED talk), I was convinced.

Designing my own general purpose computer ranks very high on the list of my fantasies (had I already mentioned I was a nerd?), but I do not think I could achieve that without some serious support. That course might just be the support I need. One needs to be aware of that the hardware built in the course only exists in a simulator when the course is completed. It is built with the help of a Hardware Description Language (called HDL). Generating real hardware from the chips described in HDL in the course has however been done, and the way it was done is very much like modern real life hardware construction: by burning the design synthesized from HDL (or actually Verilog, a real life variant of HDL) to an FPGA.
Of course, the design in the course is not my design, but who knows how much inspiration I could get from taking the course?

Anyway, I decided to give it a go and have taken module 0 today. :-)
The hardware simulator works on my Linux computer (written in Java like all the tools for the course). Scrolling horizontally in the text editor windows does not work for me (the text is no longer displayed correctly when I move the sliders), but it was still usable, and editing the HDL code requires an external editor anyway.
Thanks a lot to the Nand to Tetris team!