NAND2Tetris Part2

三月時看到coursera 上，Nand2Teris 第二部分終於開課了，同樣給它選修下去；最近剛把最後的 project 寫完，完成這門課程。
課程網址：
https://www.coursera.org/learn/build-a-computer
另外，這門結束之後，5/8 立刻有開下一個 session，有興趣的大家趕快 Enroll ，一起把電腦給看透透吧。

Nand2Tetris 2 的影片長度明顯比 season 1 長得多，光第一週的影片，要介紹Virtual Machine 概念，又要講解整個 memory layout, pointer access 的概念，第一週影片長達200 分鐘，還不算上 week 0 複習 Nand2Tetris 1 Machine Language 的部分。
另外 part 2 畢竟進到軟體的部分，作業都很吃軟體能力，像是實作 VMTranslator，編譯器，寫高階語言，也不像第一部分，有提供手爆作業給不會寫程式的人，如果沒有基本程式能力選修起來會有些難度。
作業我本來想延續上一個 part 1 都用rust 寫作業，後來…還是偷懶改用Python 寫了(yay，我魯我廢我不會寫 rust QQQQ。

讓我們帶過七週的課程內容：

第一週：

介紹整體 Nand2Tetris stack machine 的架構，整個 Nand2Tetris 都是執行在這種stack machine 上面，之所以用 stack machine 應該是因為相較 register machine，stack machine 還是好做一些，Memory 設定為：

0-4: SP, LCL, ARG, THIS, THAT
5-12: temp
13-15: general register
16-255: static variable
256: stack
2048: heap (以下暫時不用管)
16384: Screen
24576: Keyboard

在 part 1 的最後，我們可以把 assembly 像是 D=A 轉成機械碼 1101...，VM stack machine 程式碼比 assembly 再高階一些，我們可以直接寫stack 操作，例如 push ARG 1，把 Argument 1 推到 stack 的頂端，這樣高階的程式碼讓我們可以更簡單的實作複雜的行為。

作業是VMTranslator，也就是把剛才那些 push ARG 1 轉成一連串的 D=A, D=M 的assembly，寫作業時發現這份文件非常好用：
http://www.dragonwins.com/domains/getteched/csm/CSCI410/references/hack.htm

稍微卡的地方：
pop local 2 這條指令，因為我要先把 local 2 的位址算出來，這樣就需要 D, M, A 三個register (@2, D=A, @LCL, A=M, D=A+D)，然後要取SP 的位址也需要三個 register (@SP, A=M, D=M)，這樣就沒有地方可以存 pop 出來的東西了
解法是要用到 13-15 的 general purpose register，算出 local 2 位址之後，先塞進 @R13 裡面，取出stack top 放到D 之後就能直接用 @R13, A=M, M=D 將資料塞進 local 2 裡了。

對應課程：我其實不確定，編譯器一般不會是編譯成虛擬機 bytecode ，都是直接變成 bitcode；如果說是stack machine 的觀念的話，那就是虛擬機器了。

第二週：
VM 裡的 branching, function call
branch 很單純，一個影片就講完了；大部分的內容都在講 Function Call，這部分最複雜的也就是 Function call 跟 Return 的calling convention，作業也就實作這兩個功能：
Function Call 大致的內容如下：LCL (local) 對應一般機器上的 base pointer，SP 則是 stack pointer：

呼叫函式的部分：

Push argument
儲存return address, LCL, ARG, THIS, THAT 到 stack 上面
將 ARG 移動到stack 上存參數的位置
將 LCL 到stack 頂端
Jump
寫入Return label

函式本體的部分：

執行Push stack，留給 local 變數空間
函式本體

Return 部分：

將 LCL 儲存到 R13 (general purpose register) 中
將 Return address (LCL - 5) 儲存在 R14 中
複製 stack 頂端的 return value 到 ARG，要注意沒有參數的話，ARG 指向的位置就是 LCL-5 Return address，所以上面要先把 Return address 備份，不然沒有參數的話會被 return value 蓋掉。
將 SP 移到 ARG 的位置 (pop stack)
恢復 LCL, ARG, THIS, THAT
跳到 R14 的 return address

如此就完成了函式的呼叫與返回，有一點要注意的事，講義的部分沒有講很清楚：這週的作業有要寫bootstrap 的部分，他只寫要做到 SP=256; Call Sys.init，其實在Call Sys.init 的部分，也應該要把bootstrap 的 LCL, ARG, THIS, THAT 存到 stack 中，雖然 Sys.init 永遠不會 return，但在實作上還是要求這麼做。
另外我在寫的過程中，如上所述，函式return 時試著去調換 return value 寫入ARG 跟取出return address 的部分，結果就把 return address 蓋掉導致 \explosion/ 了，正好驗證那句：「你以為你會寫程式，假的！叫你用assembly 寫一個Fibonacci 都寫不出來」

對應課程：這周的對應課程我不甚肯定，calling convention 也許是作業系統，也許是編譯器的 code generation 吧，實際可能分散在下面幾堂課裡：
計算機結構、作業系統、計算機組織與組合語言、系統程式。

第三週：
Jack programming language

就是介紹 Jack 的設計，syntax, data struct 之類的怎麼設計的，因為Jack 比起什麼C++/Java 簡單非常非常多，說真的只要學過任何一種 programming language 的，這周應該都可以跳過去不用看。
對應課程：計算機程式。


第四週：

Jack language 的 parser，內容介紹 tokenizer 還有 parse 的基本原理，作業是實做 tokenizer 跟 parser，把 jack program parse 成一堆 token 然後寫到 xml 檔中，要產生 token 的xml ，還有parser 處理過，加上結構節點像是 WhileExpression 的 xml。
tokenizer 我一樣用 python 實作，regular expression 文件裡面有一節就是如何用 re 的 scanner 來寫一個 tokenizer，整個 jack language 的規則大概就是這樣，寫起來輕鬆寫意：
https://docs.python.org/3.2/library/re.html#writing-a-tokenizer

jackkeyword = ['class', 'constructor', 'method', 'function', 'int',
  'boolean', 'char', 'void', 'var', 'static', 'field', 'let', 'do',
  'if', 'else', 'while', 'return', 'true', 'false', 'null', 'this']
tokenSpec = [
  ('comment', r'//[^\n]*|/\*(\*(?!\/)|[^*])*\*/'),
  ('integerConstant', r'\d+'),
  ('symbol', r'[+\-*\/\&\|\<\>\=\~\(\)\{\}\[\]\.\,\;]'),
  ('identifier',  r'[A-Za-z_][A-Za-z_0-9]*'),
  ('stringConstant', r'\"([^"]*)\"'),
  ('newline', r'\n'),
  ('space', r'[ \t]+'),
]

parser 部分我寫了個class ，對各種狀況寫函式來處理，寫得超級醜，文法檢查和輸出的部分都混在一起了，整個 parser 都是用土砲打造而成，正符合下面這句話：
「我一直以為我會寫程式…假的！連個 jack compiler 都寫不出來。」
那個 code 實在是太醜了，決定還是不要公開…，但相較在網路上找到一些人的實作，連文法檢查都沒有，我是覺得我寫得還是很有誠意啦XD
https://github.com/kmanzana/nand2tetris/tree/master/projects/10

對應課程：無疑問的就是編譯器的上半學期


第五週：
Code Generation

上週實作的編譯器只能輸出 xml ，這周要直接把 jack 轉成 VM code，影片就是一步步教你，當遇到運算符號要怎麼處理，呼叫函式要怎麼處理。它的class 沒有 inheritance 所以…嗯，也不用處理 virtual table 的問題，其實滿簡單的。
我覺得收獲最大的，是學到怎麼處理物件 method 的call，其實也就是把指向物件的記憶體位址塞進函式的第一個參數，然後在進到 method 的時候先把這個參數塞進 THIS，這樣就能用 THIS[n] 來取用物件的 data member 了。
這裡也會知道，上面實作時遇到的 THIS, THAT，其實分別對應物件跟陣列，要用物件的 data member 就用 THIS[n] 去取，陣列的內容則用 THAT[n]，這樣只需要把記憶體位址存到 THIS, THAT 裡面，就能取用物件和陣列了。

下面是一些實作的筆記：
Jack language 裡面沒有 header/linker 的概念，編譯的時候是以一個 class 為單位在編譯，所以如果裡面出現呼叫其他class 的函式，例如 do obj.foo()，我們只能把它們當成「合法」的程式來產生 code，就算沒有這個 class 或是函式還是可以編譯
但沒有最後一步將所有 vm file link成一個檔案，而是模擬器個別 load 所有的 vm 檔，自然不會像 C/C++ 的 linker ，在最後階段回報 undefined reference to class name/function name 的錯誤。

因為parser 已經把整個程式碼變成 AST了，code generate的部分，只需要把對應的函式寫好，大抵就會動了；沒實作的地方，我發現與其寫 pass 不如直接 raise NotImplementedError，這樣一編譯遇到沒實作的地方，程式就直接 crash 並指出是哪個地方沒有實作；而無論是 parser 還是 code generation， expr->term->factor 這部分的變化是最多元的，這部分處理完，各個 statement 的部分都可以輕鬆對付。

然後…它的模擬程式其實有點兩光，如果選用 program flow 模擬的話會非常慢，依它的建議要把它選成 No Animation，可是這個模式無法編輯記憶體的內容；正確步驟是：load 程式，編譯記憶體，選成 No Animation 執行。
另外，No animation 下，所有對記憶體的操作，都要按下停止模擬才會反映出來，不知道這點的我一直以為我 code generate 哪裡寫錯了lol。

這次作業會需要 call 到一些 library 提供的函式，請參考官方的文件：
http://www.nand2tetris.org/projects/09/Jack%20OS%20API.pdf
例如，要產生字串的話，要用 String.new, String.appendChar 兩個方法，大致如下：

push constant num_of_character
call String.new 1 // 1 argument
for char in string:
  push constant ord(char)
  call String.appendChar 2 //first is string, second is character

最後的 compiler 總共 1000 行左右…覺得實作超糟，都用了python 怎麼還會寫得這麼肥？

對應課程：編譯器的下半學期


第六週：

作業系統，或者稱 Library 或是 runtime 應該比較恰當，總之就是 jack 中，會用到一些 Keyboard, Screen, Math 之類的函式，在之前都是用預先編譯好的模組來執行，現在則要自己用 jack 實作這些功能。這次的影片也高達 230 分，到最後一個 module 連教授都忍不住大叫：Yeah, the last module~~

理論上是用 jack 這樣的高階語言來寫，以為有高階語言就沒事了嗎，錯！
jack 他X 的有夠難寫，少了一個 do, return 什麼的程式就炸給你看（沒有return 它的函式就會一路執行到下一個函式 lol），因為它沒有 operator precedance 所以該加括號的地方也要加，宣告也無法和賦值寫在一起，我大概照他設計的內容，寫完Math 跟 Memory 之後才比較抓到該怎麼寫。
作業寫起來都滿有挑戰性的，像是 Memory.jack 就要用 linked-list 來實作的記憶體管理（用這破破的語言XD）。

作業不止是在考驗寫 jack ，同時也在驗證上一次寫的 compiler ，測試過程中我找到好幾個 compiler 相關的錯誤，像是函式的參數沒處理好，不該傳入 this 的時候傳入 this，讓我在Output 文字的地方 de 了很久的 bug。
這種錯真的超級麻煩，你不一定知道是高階語言寫錯還是compiler 錯…，有時要追著模擬器一步步執行，才能知道是哪裡錯了。這次真的是體會到：好的編譯器帶你上天堂，壞的編譯器帶你住套房。

對應課程：作業系統、系統程式
有一些些的演算法概念（例如乘法要怎麼實作才會快），但份量極少所以不列上好了。

第七週：
這週只是提點一些 Nand2Tetris 可以加強的部分，像是：
在硬體中實作乘法除法來加速，這樣就不需要 library 的函式支援。
在硬體中實作位元運算（左移右移）
如何自己實作模擬器的 built-in chip

另外也公佈可能會有的 Nand2Tetris part 3，如何真的在 FPGA 上實作這台電腦

－－

末語：
大推這門課，課程中 Shimon 講課的速度都滿慢的（我都開 1.3-1.4 倍速在聽課），不會太難聽懂。
第二部分相較之下實在太難，覺得還是稍微有碰過程式再來學會比較好，第一部分就沒這問題（也許可以說：電機系的不用修第一部分，資工系的不用修第二部分XDD）修完整部 Nand2Tetris ，對數位電路到組成電腦都有一些概念，第二部分更是讓你看透程式到底怎麼編譯、執行，這點可能即使是資工本科生都不一定全盤了解。
同時，修這門課對我來說也有一點點復健的作用，從簡單的東西入手給自己一點信心：原來，我也是會寫程式，寫得出一些些可以用的東西呢。

僅引用課程講義最後一節的文字：

In CS, God gave us Nand, everything else was done by humans.
神給了我們反及閘，於是我們打造一台電腦。

另外還有影片中教授引用的這段：

We shall not cease from exploration, and the end of all our exploring will be to arrive where we started and know the place for the first time." - T. S. Eliot

作為這門課的總結。