半熟前端

軟體工程師 / 台灣人 / 在前端的路上一邊探索其他領域的可能性

本部落格使用 Gatsby 製作

本部落格有使用 Google Analytic 及 Cookie

遊戲心得

從 NAND 邏輯閘開始做電腦 - Turing Complete 遊戲心得

從 NAND 邏輯閘開始做電腦 - Turing Complete 遊戲心得

以往在講到 NAND 邏輯閘組電腦這件事情的時候,我們第一個會想到的是 nand2teris 這門神課程。這門課程教你實際做出一台可以動作的電腦(在模擬器上跑)。

從最基礎的理論開始,先從硬體層面的邏輯閘以及各種電路設計指令,自行撰寫必要的元件,設計組合語言與指令集,最後再撰寫軟體層面的程式語言,包含編譯與 assembler 都有涵蓋。基本上上完 nand2teris,就知道電腦背後到底是如何運作的。

圖靈完備

將 CPU 的工作拆解,可以發現有大部分的操作都是在做運算,四則運算、移動位元、矩陣乘法等等,那麼我們要怎麼知道一台電腦是否能夠運算所有「可以運算的東西」?

舉例來說好了,在遊戲當中會遇到全加器(full adder),可以執行加法操作,減法則可以用補數的概念用加法完成。那麼乘法呢?sin 函數呢?cos 函數呢?

我們可以不斷地加入新的硬體電路例如乘法器、sin 函數器、cos 函數器,但是這樣子沒完沒了,因為世界上的公式那麼多,不可能全部都在硬體電路實現。

圖靈在他的論文提出了圖靈完備這個理論,簡單來說,如果我們可以儲存目前執行指令的位址(Program Counter),並根據當前的指令得到下一個狀態(Register),就能達到圖靈完備。這件事其實很神奇,圖靈證明了這樣子的架構可以解決所有可運算的函數。

將數位邏輯視覺化

最近在 steam 上發現這款遊戲 Turing Complete,其概念跟 nand2teris 如出一轍(但只有到組合語言),也是一樣從邏輯閘開始慢慢組裝成一台圖靈完備的電腦。

這款遊戲透過視覺化把程式碼的撰寫變成可以拖拉的邏輯閘,即時的互動更方便玩家觀察的真值表變化。

XOR gate

透過拉線的方式簡化用紙筆抄寫真值表的成本;用滑鼠點擊的方式切換 1 跟 0(ON 與 OFF),省略了軟體安裝跟 HDL 描述語言,盡可能地讓玩家從核心理念開始。

一顆 CPU 可以拆解為無數個 NAND 邏輯閘組合而成的電路。你的目標是從邏輯閘開始一步步完成關卡,最後做出一台可運作的電腦。

從邏輯閘開始組合各種電路,包含暫存器、記憶體、多工器、解多工器,透過各種功能的小關卡讓你熟悉電路特性。只要完成關卡,遊戲就會將你組好的電路變成元件送給你,遊戲進行到後面,元件就會越來越多。關卡後面的電路也會越來越複雜,需要的元件與拉線也會越來越多。

full adder

demux

邁向圖靈完備之路

遊戲當中一個重要的分水嶺是圖靈完備,當你完成 WORKING COMPUTER 之後會發現原來之前辛苦組合的電路都是為了這一刻。這個關卡會要求你達成幾個條件:

  • 根據 byte code 的 bit 判斷要執行哪個操作:ADD、XOR、OR 等等
  • Program Counter:紀錄程式執行到哪個位置
  • 根據某個 bit 判斷是否要執行 jump(跳至指定位址):要實作六種情形(大於、小於、等於、always、never)
  • 5 個暫存器

Turing Complete

這個遊戲好玩的地方在於每個玩家拉出來的電路不會全然相同,而是有自己的風格與實作方法。

完成之後其實就算是達成電腦所需要的功能了,算是一個重要的里程碑。然而,遊戲並不是到此結束,接下來遊戲會要求你用你組好的電路完成關卡指定的需求,像是:

  • 計算 mod 4:剛開始遊戲會叫你使用 byte code 自己慢慢點

    byte code

  • 計算 2 * pi * r:接下來可以使用編輯器撰寫了,你可以自己命名指令,創造你的指令集

assembly editor

  • 走迷宮:撰寫程式碼走迷宮

如果真的有自己動頭腦、動手玩完遊戲關卡,我認為可以吸收許多計算機組織的知識,再搭配教科書來幫助理解,甚至能夠比某部分工程師的基礎還要紮實。

現有電路再進化

一旦你用組合語言破完遊戲指定的關卡,接下來會在既有的架構上加入更進階的東西。一個簡單的例子是,為什麼暫存器的數量有限,但程式裏卻允許有那麼多的變數存在?答案是 RAM,因此遊戲接下來會要你加入 RAM 以後做尋址,並達成指定功能。

RAM

原本的電路在執行指令時只能固定將 r1、r2、r3 當作計算或跳轉用的暫存器,然而這樣子對程式碼的撰寫比較麻煩,因此遊戲會要求你實作 OPCODE、argument1、argument2、result 這樣的架構。每次程式會讀取 4byte,你要針對 4byte 解碼,讓整個電路可以自由決定參數要使用哪個暫存器、結果要存到哪個暫存器。

有了 RAM 也有了更彈性的電路架構,接下來是實作 stack 功能,讓我們的電路可以儲存一連串的 context,也是之後實作 function 的基礎,這代表著電路又要變得更加複雜了。

Stack circuit

當你到達這個階段後,會解鎖新的功能—scoring。在實作電路時理想是同時進行越多操作越好,因為電路穿過更多邏輯閘代表更多的 delay,遊戲會幫你計算 NAND 使用數量與 delay,因此你可以回頭修改電路,達到更好的效能。

接下來的關卡大部分都是依照現有的架構做修改,然後用組合語言完成更進階的小遊戲。

缺點

這款遊戲目前還在開發當中,雖然不需要非常紮實的 IT 基礎,但可能還是需要大概了解一下邏輯閘在做什麼,對二進位有概念再來玩會比較容易上手。

另外,遊戲當中的指引跟提示實在是少得可憐,很多時候就是要花時間去掙扎,不斷試錯跟思考改進電路,尤其到後面電路會越來越難,很多時候沒辦法體驗到遊戲的樂趣,遊戲介面也不是那麼好理解,拉線拉得很痛苦。

有蠻多次我在玩到一半的時候遊戲會突然跳掉,在遊戲中後期發生頻率非常高,不知道在正式發布之後會不會改善。

玩遊戲真的能學東西嗎?

同樣可以當作舉例的還有 Nintendo Switch 的「附帶導航!一做就上手 第一次的遊戲程式設計」。

它的遊戲教學設計相當優秀,會用大量的範例告訴你接下來要實作哪些功能,功能實作需要什麼東西,實際讓你跑一遍看結果,叫你去修正結果。需求→實作→驗證→修改,其實就跟實際的開發週期是類似的。在遊戲裡你不需要撰寫任何程式碼,所有的功能都被抽象為一個個「節點」,用拖拉的方式來進行。程式的本質從來就不是語法本身,而是背後的思考邏輯。而且 Nintendo Switch 的從頭開始的遊戲程式設計函數文件寫得相當優秀,簡直可以當作開發人員的典範了。

Turinb Complete 這個遊戲比較變態一點,基本上你不會看到什麼手把手教學(不知道正式發布後會不會有),所以很多時候要自己來。

遊戲化的好處在於我們可以省略所有不必要的安裝設定,語言符號理解,直接深入最核心的概念,作者將描述邏輯閘、真值表的概念抽象為視覺化與可拖拉的區塊,比撰寫程式碼或文字來得直覺許多。

心得

這個遊戲讓我重溫了整個計算機結構的基礎,也是重新複習了 nand2teris。雖然以前在學校或多或少都有接觸同樣的課程,但是極少數有像這樣子的課程,讓你從頭自己的打造可以運作的電腦。儘管大部分的東西在學校都有學過,但實際要動手拉線時還是很容易遇到問題,也因此辛辛苦苦把電路組合好時真的很開心。

實際上當然不可能把遊戲拉拉線組合的電路拿來使用,在現實世界當中往往不是只要把功能拉出來就好。不過對於入門學習來說,這種方式可以幫助學習者更快速地掌握核心理念,相當推薦對電腦背後如何運作有興趣的人可以入手這款遊戲。

預告影片有一句讓我印象深刻的話:

If you try to make such projects, unseen by others, as perfect as any human could, you'll develop skills that other professionals don't have

不過,玩完之後我覺得這門遊戲的上手門檻實在太高,遊戲教學與說明相當少,而且寫得非常晦澀,一開始就要你實作電路,對於不熟悉二進位與數位邏輯的玩家來說很容易撞牆。到後面的提示和說明有跟沒有差不多,而且由於難度的關係,卡關、陷入沉思可以說是非常正常的事,因此當作純娛樂的遊戲來玩可能不太適合。

我甚至認為 21 世紀電腦發展已經如此成熟,透過電腦強大的運算能力與視覺化效果可以指數性地幫助學習。在學習數位邏輯時,由於在電路上我們時常想要觀察輸入的組合與輸出的關聯,需要不斷修改輸入值,這件事情在紙本上做比較麻煩,因為我們需要用橡皮擦修改數字,但是在電腦上就不一樣了,滑鼠按一下就能從 0 變成 1,輸出也可以即時改變。

  • 回饋週期的成本降低
  • 可以即時觀察結果

光是這兩點就讓我們的學習效率遠遠超越數十年前的人了。

參考

這是之前的直播,雖然沒有將全部的遊戲內容都直播出來,但大部分的關卡應該都可以在上面找到。

如果覺得這篇文章對你有幫助的話,可以考慮到下面的連結請我喝一杯 ☕️
可以讓我平凡的一天變得閃閃發光 ✨

Buy me a coffee