Nand2Tetris part-II review

If you ever wanted to improve your understanding of a computer system or write a compiler then this post may convince you to take the course or read the book.

TLDR

Cons

1. Hack platform is an educational platform, so learnings aren’t directly applicable in “real world” (see Pros tho)
2. provided software is somewhat rough at times with unclear and hard to debug errors
3. Jack OS is not what many people may expect, it’s a mix of Jack standard library (Array, String) and HW drivers (Memory, Keyboard, Output, Screen)

Pros

1. the only course(AFAIK) with such a depth: from NAND gates to the OS(requires part I)
2. learning are transferrable to the “real world” platforms to some degree
3. introduces concept of the Stack Machines
4. introduces Virtual Machines and VM instructions
5. introduces concepts of high-level programming languages
6. introduces to Syntax and Formal Grammars
7. teaches how to implement Hack assembler
8. teaches how to implement Jack Lexer
9. teaches how to implement Jack Parser
10. teaches how to implement Jack Compiler
11. teaches how to program in Jack
12. teaches how to implement memory allocator as part of Jack OS
13. teaches how to implement Strings and Arrays
14. teaches how to deal with IO and build Jack OS

Week 1: Machine language and Stack Arithmetic

Is a warmup week and a refresher on the Hack HW platform and Assembly in the first half.

Some notes about the platform and assembly:

1. Hack is a 16 bit platform meaning its memory is an array of words(16bit) and CPU operates with instructions that are 16bit values
2. Hack Assembly contains only 2 kinds of instructions: A and C
3. A instructions are used to load a value and to address the memory via the M register
4. C instructions are used to perform the operations

Stack Machines

The second part introduces:

1. Hack’s VM language and general ideas about VMs and what role they serve as a HW abstraction
2. Hack’s VM implementation using Stack Machine

Turns out that Stack Machine is an extended variant of a Reverse Polish Notation

For example, the infix expression (1 + 2) * 3 is equal to 1 2 + 3 *, in postfix notation, and translates to the following VM instructions:

push const 1
push const 2
add
// `add`s implementation pushes result back on stack
push 3
call Math.multiply 2
// `Math.multiply` s `return` pushes the final result back on stack

The assignment requires to implement VM language translator for the arithmetic/logic and memory access VM instructions: given the VM instructions - generate the corresponding assembly.

The VM topic deserves a separate blog post.

Hack VM language

1. Arithmetic/Logic: add, sub, neg, eq, gt, lt, and, or, not
2. Memory segment: push/pop <segment> <value>
3. Branching: goto <label>, label <label>, if-goto <label>
4. Function cmds: call <fname> <nvars>, function <fname> <nvars>, return

• nvars - defines how many local variables the function declares
• nargs - defines how many argument variables function accepts (last nargs values on stack)

Week 2: VM language part II

Last part of the VM instructions translation implementation.

1. branching with goto, if-goto, label VM instructions
2. function “invocation” with call, return VM instructions and all the mechanics that comes with it: call frame, stack and memory allocation, handling recursive calls

The call and return mechanics deserves a separate blog because their implementations are significantly more complex than the rest of instructions and the ideas translate well to other platforms.

This chapter was quite challenging and educational.

Week 3: Jack language

Introduced Jack language, syntax and programming. Jack feels like mix of Java and C. For educational purposes and simplification, Jack syntax is somewhat verbose and clunky.

/** Hello World program. */
// must be in Main.jack
class Main {
  function void main() {
    var String s;
    let s = "world";
    /* Prints some text using the standard library. */
    do Output.printString("Hello ");
    do Output.printString(s);
    do Output.println(); // New line
    return;
  }
}

Some notes:

1. to simplify parsing, every statement is explicitly prefixed with a keyword thus - var, let, do, etc
2. declaration and initialization are separate
3. arithmetic expressions are evaluated sequentially left-to-right disregarding the mathematical precedence, ie 1 + 2 * 3 = (1 + 2) * 3
4. operators <= and >= are absent so instead I was using negated variants ie: ~(a < b) instead of a >= b
5. lack of modulo operator. In special case of x mod 16 I was using x & 15
6. 3 simple types: int, char, boolean
7. void is not a real type(cannot declare a void variable) rather a way to “mark” a function/method that doesn’t return any value
8. few built-in data types Array, String
9. custom types defined via class

Compilation could be done via provided Jack compiler:

./nand2tetris/tools/JackCompiler.sh Main.jack 
Compiling /nand2tetris/Main.jack

And then running via /nand2tetris/tools/VMEmulator.sh the produces the Main.vm file.

Week 4: Compiler I, Parsing and parse-tree traversal

This chapter introduces few concepts required to implement a compiler:

1. Tokenizing - the process of consuming input bytes and classifying them into tokens
2. Grammars - high-level formal definition of a language’s structure and terminals(tokens)
3. Parsing - a process of consuming input tokens and inferring the structure based on the language’s grammar
4. Parse trees - a tree-like byproduct of the parsing/traversal process
5. touched on other concepts like parser-generators and other variants of parsers

The week’s assignment is to build a parser that, given the Jack source code, outputs XML encoded parse-tree representation. Next week’s VM code generation builds upon the implementation.

Week 5: Compiler II, VM code generation

The second part of the compiler implementation.

Implementation from the week 5’s assignment has to be modified to emit VM instructions for the corresponding Jack source code. During the week we went through:

1. handling variables by defining them in symbol tables and mapping onto VM memory segments
2. handling expressions and translating Jack’s infix notation into VM’s bytecode as postfix notation
3. handling flow of control and translating Jack’s while, if, else statements into VM’s goto, if-goto, label commands
4. handling Objects and translating Jack’s class constructor/method/function notation into VM’s procedural notation
5. handling Arrays with memory allocation and access

Worth noting that Week 6’s assignment(the next one) uncovered many issues with my freshly implemented compiler while implementing Jack OS which was challenging to debug and fix.

Week 6: Jack OS.

Was likely my least favorite week since I’m not too fond of Jack programming and it was 100% of it. Yet some great nuggets are there like implementing:

1. Math module: simple implementations of multiplication, division, and square root
2. Memory module: memory allocator
3. Screen module: implementing graphical routines like drawLine, drawCircle, drawRectangle
4. Output module: implementation of textual interface like moveCursor, printChar, printString, font glyphs
5. Keyboard module: implementing reading from keyboard like readChar, readLine, etc
6. String module: allocation and basic manipulations: new, appendChar, charAt, etc
7. Array module: and how array variable is just a pointer to its first element similarly to C
8. Sys module: the entry point for the Jack applications application along with sleep, halt` routines

Week 7: Future

There are plans to continue the saga and create part III with some exciting ideas like implementing Hack platform in real hardware.

Looking forward to the part III.

Slides and the Book

Most of the slides (and some chapters of the book) are freely available on the Nand2Tetris website and provide great overview of the course.