Show HN: NANDゲートで作られたプログラム可能なコンピュータ

 (github.com/ArhanChaudhary)
2 ポイント 投稿者 GN⁺ 2024-04-27 | 1件のコメント | WhatsAppで共有
  • NANDは、Web上でエミュレーションされるチューリング完全な16-bitコンピュータで、clockとNAND gateのみで構成されるという教育的前提に基づき、CPUからIDE、UIまでを含む
  • 独自スタックはJack-VM-Hackプラットフォームをベースとしており、CPU、機械語、アセンブリ、assembler、VM言語、VM translator、Jack言語、compilerをあわせて提供する
  • サンプルプログラムにはAverage、Pong、2048に加え、stack overflowとstack smashingを利用したVM escapeのデモ、単純な機械学習を使うGeneticAlgorithmまで含まれる
  • JackはJavaの文法に似た弱い型付けのオブジェクト指向言語だが、内部的にはsigned 16-bit integerひとつに依存しており、演算子優先順位なし・手動メモリ管理・未定義動作といった大きな制約がある
  • このプロジェクトは、実際にすべての計算が物理的なNAND gate上で実行されることを意味するものではなく、TypeScript compilerとVM translator、RustベースのNAND gate logic simulator、WebAssemblyを用いた教育・理論向けの実装である

NANDが提供するコンピュータスタック全体

  • NANDは、Not A Nand-powered Deviceの略として紹介されるWebベースの16-bitコンピュータである
  • clockとNAND gateで作られたチューリング完全なコンピュータをエミュレーションし、次の構成要素を独自に備える
    • CPU
    • machine code language
    • assembly language
    • assembler
    • virtual machine language
    • virtual machine translator
    • programming language
    • compiler
    • IDE
    • user interface
  • ベースとなっているのは、Nand to Tetris courseおよび関連書籍のJack-VM-Hackプラットフォームである
  • NANDデモ動画が公開されている

サンプルプログラムとデモ

  • Average

    • 数値入力と平均計算を行うシンプルなプログラム
    • control flow、算術演算、I/O、動的メモリ割り当てを示す
    • Nand to Tetris software suiteで提供されたプログラムである

  • Pong

    • オブジェクト指向モデルを示すPongゲーム
    • 方向キーでpaddleを左右に動かし、ボールを打ち返す
    • ボールを打ち返すたびにpaddleは小さくなり、ボールが画面下に触れるとゲーム終了となる
    • Nand to Tetris software suiteで提供されたプログラムである

  • 2048

    • recursionと複雑なapplication logicを示す2048ゲーム
    • 4x4 gridで方向キーを使って数字を動かし、同じ数字同士は合体する
    • 2048 tileに到達すると勝利だが、負けるまでプレイを続けられる

  • Overflow

    • 無限再帰によって意図的にstack overflowを発生させ、virtual machine escapeを実行する
    • runtimeにstack overflow防止チェックがない点を利用している
    • stack pointerの値が2048を超えると、stackは本来想定されたメモリ空間を外れてheap memory spaceへ流れ込む
    • 空のRAMで実行すると、program counterが0に設定されるinstructionのため、プログラムが途中でリセットされることがある
    • GeneticAlgorithm実行直後に実行すると、上書きされずに残った以前のRAM memoryを読み取れる

  • SecretPassword

    • runtimeがstack smashingを防がないことを利用し、本来アクセスできない関数を呼び出す
    • ユーザーはRAM上のあるmemory addressを任意の値で上書きできる
    • stack frameのreturn addressを別の関数アドレスで上書きすれば、プログラム内の任意コード実行が可能になる
    • 例の値はmemory location 267、overwrite value 1743である
    • 同種の脆弱性はCのbuffer overflowにも存在する

  • GeneticAlgorithm

    • 単純な機械学習を使うcreature simulationである
    • 各dotはacceleration vectorで構成された独自の「brain」を持ち、自然選択を通じてgoalに到達するよう進化する
    • goalにより近い位置で死んだdotほど、次世代のparentに選ばれる可能性が高い
    • reproductionの過程でbrainの一部がmutationし、自然進化をシミュレートする
    • Genetic Algorithmデモ動画が公開されている

GeneticAlgorithmが直面したハードウェア制約

  • GeneticAlgorithmは、NANDのさまざまな構成要素の中でも開発に最も時間がかかった単一プログラムである
  • 性能上の理由から、dotの進化で使われる要素は死ぬ時点でgoalにどれだけ近いかだけであり、自然選択アルゴリズムのentropyは低い
  • メモリ使用量のため、dotの数とbrainの大きさには満足のいかない制限がある
  • 技術的な複雑さのため、simulation中にobstacleを再配置しても、dotのbrainがgoalに到達できるほど十分大きいとは保証されない
    • brain sizeはプログラム開始時にのみ決定される
  • 実装では、複数の最適化によってNANDの制約を回避している
    • ROM instruction memory spaceには制限があり、コードが多すぎるとcompileできない
    • 最終的なGeneticAlgorithmはinstruction memory spaceの**99.2%**を使用する
    • RAM memory spaceにも制限があり、heap memory usageを最適化する必要がある
    • 世代間で画面が静的に塗りつぶされるのは、screen memory spaceを次世代のためのtemporary swap memoryとして使っているためである
    • NANDにはfloating point typeがなく、表現可能なintegerの範囲は**-32768から32767**までである
    • fitness計算の精度が低くなり、integer overflowも考慮しなければならない
  • 関連する最適化や追加のinsightは、GeneticAlgorithm codebaseに文書化されている

JackでNANDプログラムを書く

  • Jackでプログラムが動作しない最大の原因として、演算子の優先順位がないことが強調されている
    • 4 * 2 + 3 は (4 * 2) + 3 のように書かなければならない
    • if (~x & y) は if ((~x) & y) のように書かなければならない
    • 括弧のない曖昧な expression の評価値は undefined である
  • JackはNANDの weakly typed object-oriented programming language である
    • 説明としては「Java syntax を持つC」に近い
    • NANDは独自の complete tech stack を備えているため、Jackだけでプログラミングできる
  • 基本のJack OSは compile 時にプログラムへ一緒に bundle される
    • strings、memory、hardware との interface を提供する
    • Keyboard.readLine, Keyboard.readInt, Output.printString, Output.println のような関数が含まれる
  • Jackは int, char, boolean の3つの primitive type をサポートする
    • class を通じて abstract data type を定義できる
    • field variable は instance ごとの attribute を宣言する
    • field variable は private scope であり、外部からアクセスするには method が必要である
  • function と method は呼び出し方が異なる
    • current object の method は同じ class 内で do g(); のように呼び出せる
    • function call では class name を前に付けなければならない
    • object method は do b.q(); のように object を通じて呼び出す

Jackの弱い型付けとメモリ管理

  • JackはJavaと異なり、strong type、down casting、polymorphism、inheritance をサポートしない
  • 内部的には実際の type は signed 16-bit integer ただ1つしかない
    • compiler は assignment や operation で type が混在していても気にしない
    • char に 65 を入れると 'A' と同等に扱える
    • Array 変数に 5000 を入れて a[100] = 77 を実行すると RAM[5100] = 77 になる
    • array entry には異なる data type を入れられる
    • memory layout が合っていれば Array を別の class instance のように使える
  • Jackは手動メモリ管理の言語である
    • もう不要な memory を deallocate しないと memory leak が発生する
    • heap overflow は ERR6 として現れる
    • Jack OSは array と string を stack ではなく heap に保存する
  • object を表す class は dispose method を持つのが best practice である
    • まず field variable の dispose を呼び出す
    • 最後に do Memory.deAlloc(this); で object instance 自体を deallocate する
  • string literal を繰り返し生成して出力するループは heap overflow を引き起こす可能性がある
    • 各反復で string を dispose するか
    • string を一度だけ allocate して再利用すれば、出力を続けられる

未定義動作と注意点

  • 比較演算子

    • a > b と a < b は常に数学的に正確とは限らない
    • VM実装では a > b を a - b > 0 に変換する
    • a - b が overflow する可能性があるため、20000 > -20000 は false になる
    • a と b の absolute distance が 32767 より大きいと、> と < は誤る可能性がある
    • この挙動は Nand to Tetris との compatibility のため修正されていない

  • -32768

    • -32768 は -(-32768) = -32768 となる唯一の値である
    • 対応する positive counterpart がないため、unsoundness や logic error を引き起こしうる
    • Output.printInt は内部的に Math.abs が positive number を返すことを期待しているが、-32768 ではそうならないため Jack OS が誤動作する

  • 引数が少なすぎる関数呼び出し

    • parameter のある function を引数なしで呼び出しても undefined behavior が発生しうる
    • 逆に引数が多すぎる function call は有効で、extra argument は arguments keyword で index できる
    • argument count indicator はない

  • 不適切な type casting

    • Array を使って変数を別の type に cast できる
    • cast された variable で存在しない instance method を呼び出すと undefined behavior になる
    • compiler はそれを見抜けるほど smart ではない

  • stack frame と internal register の改変

    • memory address 256~2047 の stack frame や 1~15 の internal register を改変すると undefined behavior が発生する可能性がある
    • 通常は Memory.poke の誤用や negative array indexing がない限り難しいとされる

  • ユーザーVMファイルの読み込み

    • NANDは .jack file に対しては program validation を提供するが、.vm file には提供しない
    • .vm file では nonexistent function の呼び出し、unassigned variable の参照、論理的に invalid な memory operation を実行できる
    • 多くの場合、virtual machine escape が発生し、screen に何も表示されないことがある

ハードウェア仕様とメモリ配置

  • NANDのRAMは 32,768 words で構成され、各 word は 16-bit binary number を保持する
  • hardware は screen のために 8,192 個の memory address を予約している
    • 各 address の各 bit は 512x256 screen の対応する pixel に linearly map される
    • bit numbering は LSb 0 方式である
  • keyboard は memory address 24576 に map されている
    • 現在押されている key がこの位置に反映される
    • user input を直接この address で処理するより、Jack OS の Keyboard class を使うことが推奨される
  • keyboard は ASCII character と特殊 key を認識する
    • new line = 128
    • backspace = 129
    • left/up/right/down arrow = 130~133
    • home/end/page up/page down/insert/delete/ESC = 134~140
    • F1~F12 = 141~152
  • hardware は static class variable のために 240 個の memory address、global stack のために 1,792 個の memory address を予約している
    • 深い recursion を行わない限り、この制限は概ね問題にならないとされている

Jack OSを超えて独自OSを実装する

  • 基本的にJack OSはコンパイル時にプログラムと一緒にバンドルされ、string、memory、hardware interfaceを提供する
  • 専用のhardware interfaceを持つ独自のOS implementationを提供できる
    • IDEはJack OS fileを通常のprogram fileと同じように扱う
    • OS fileもdeleteまたはoverwriteできる
  • 独自OSを使う場合でも、コンパイルのために必ず実装しなければならないcore functionがある
    • Sys.init: Main.mainではなく、VM implementationにハードコードされた実際のentry point
    • Memory.alloc: class constructorがobjectを作るときに内部的に使うheap memory allocator
    • String.newWithStr: string literalのためのinternal constructor
    • Math.multiply: Jack expression x * yの代わりに内部呼び出しされる
    • Math.divide: Jack expression x / yの代わりに内部呼び出しされる
  • 提供されるJack OSのSys.initはmemory、math、screen、outputを初期化した後、Main.main()を呼び出し、Sys.halt()を呼び出す

NANDの内部動作

  • NAND computerはHarvard architectureに従う
    • instruction memoryであるROMとdata memoryであるRAMが分離されている
    • CPUが両者を連携して動作させる
  • CPUはaccumulator machineである
    • control flowでbuilt-in registerに大きく依存する
    • ここでのaccumulatorはD registerである
  • CPU instruction setのopcodeは2種類しかない
    • instruction setは比較的単純だが豊富な機能を提供する
    • ALUは1つのinstructionで計算できるexpression群によって指定される
  • compilerとvirtual machineはNAND固有の概念ではないため、簡潔に扱われている
    • 一部の奇妙なsyntax featureはcompilerの実装を容易にするための結果である
    • compilerはLL(1) grammar上のrecursive descent parserである
    • compilerはVM codeを生成し、VMはsimple stack machineとして使われる
    • 各VM instructionはassemblyとmachine codeにmappingされる
  • 実装コードはcoreとcompiler implementationで確認できる

Jack言語とOS Referenceの要点

  • Jack programはclass collectionで構成される
    • classは別々のfileに定義される
    • 1つ以上のclassが必要で、そのうち1つはMainでなければならない
    • Jack OS基準のentry pointはMain classのmain functionである
  • classはfield、static、constructor、method、function宣言を含められる
    • fieldとstatic declarationの順序はarbitraryである
    • subroutine declarationの順序もarbitraryである
    • typeはvoid、int、boolean、char、class nameのいずれかである
  • syntaxの特徴
    • whitespaceとcommentは無視される
    • &と|はbitwise operatorであり、short-circuitしない
    • true、false、nullはそれぞれ-1、0、0である
    • string constantはnewlineやquotation markを直接含めることができず、escapeも不可能である
    • quotation markとnewlineはOSのString.doubleQuote()とString.newLine()で提供される
    • identifierはcase-sensitiveである
  • Jack OSの主要class
    • Array: arrayの作成とdispose
    • Keyboard: key press、character、line、integer input
    • Math: abs、multiply、divide、sqrt、max、min
    • Memory: peek、poke、alloc、deAlloc
    • Output: text screenへの出力とcursor移動
    • Screen: pixel、line、rectangle、circleの描画
    • String: stringの作成、dispose、character access、append、integer conversion
    • Sys: halt、error、wait
  • invalid stateでは"ERR[N]"形式のerror codeを表示し、program executionを終了する
    • ERR3: 0による除算
    • ERR6: heap overflow
    • ERR15、ERR16: string index out of bounds
    • ERR17: string is full
    • ERR20: 不正なcursor位置

実際にNAND gateだけでできたプロジェクトではない

  • FAQでは「everything made from NAND gates」という説明とtitleはmisleadingだが、good faithであると認めている
  • compilerとvirtual machine translatorはTypeScriptで書かれている
  • emulated kernelとemulated hardwareは、real computerが動作する方式をそのまま表現しているわけではない
  • 実際のNAND gate logic simulatorはRustで書かれており、codebase全体のごく一部しか占めない
    • Rust codeはbrowserで動作するようWebAssemblyにcompileされる
    • この点により、すべてのcomputationがNAND gate上で実行されるという前提は事実上取り除かれるとされている
  • NANDはeducational and theoretical projectとしての役割を持つ
    • 理論上は、同じCPU logicがemulated hardwareのreal-world manifestationでも動作しうる
    • nand2tetrisベースのFPGA hardware projectの例としてhttps://gitlab.com/x653/nand2tetris-fpga/が挙げられている

実装範囲とIDEの限界

  • NANDはNand to Tetris courseと関連書籍のspecificationに従っている
  • 実装者はCPU、assembler、virtual machine translator、compiler specificationを直接実装し、platformをwebへportingする際に独自のIDEとUIを付け加えた
  • Jackでtypeの明示が必要な理由は、compilerがinstance methodがどのclassに属するかを判断するためである
    • String typeとして宣言したsのs.appendChar(33)は、コンパイル中にString.appendChar(s, 33)へ変換される
  • IDEは実装の単純化のためにuser experienceを犠牲にしている
    • syntax highlightingのためにcontenteditableとcursor positioning logicを使用している
    • その結果、動作は遅く、目に見えてbuggyで、common keybindも機能しない
  • codeをcompileして実行するには「Start」を押せばよい
    • OSは通常、memory initializeとservice setupに1秒弱かかる

関連記事

1件のコメント

 
GN⁺ 2024-04-27
Hacker News のコメント

  • 素晴らしいサイドプロジェクトで、README も本当に良いです。Ben Eater の 6502 Computer（https://eater.net/）を少し触ったあと、Nand to Tetris をやってみようと思っていました

    • 物理的な NAND-to-Tetris コンピュータを作ることも可能なのでしょうか？ それとも純粋に仮想環境で行う演習にすぎないのでしょうか？

  • この資料だけで大学の授業をいくつか作れそうです。よくできた資料です

    • これ、単に Nand2Tetris ではないですか？ そのコースをやりましたが、ざっと見たところ Jack 言語まで含めて同じに見えます

  • 本当によく作られています。ほとんどのプログラマーがキャリアを通じて見ることのない抽象化レイヤーを、自分で一段ずつ踏んだということですね

  • 見事な仕事です。NAND to Tetris のおかげで、大学卒業後の最初の仕事を得る助けになりました

    • どう役に立ったのか気になります

  • 1990年代初頭、UC Berkeley のコンピュータハードウェア資格試験で、これに似た設計が中心問題でした
    具体的には、NAND ゲートだけでゼロからマイクロコードベースのパイプライン RISC プロセッサを設計する問題で、実際に作る必要はありませんでしたが、紙に詳細設計を提出する必要がありました

  • 本当にすごい仕事です。Nand2Tetris のコースを受けていたとき、自分も似たような仮想実装を作ってみたいと思っていました
    実際にやり遂げたのが印象的で、今ではコンピュータがどう動くのかを本当に深く理解しているのだろうと思います

    • 私も今朝、SVG で基本部品をモデル化するという似たようなことを考えていました
      でも、自分が想像していたものより桁違いにすごい仕事を、すでに誰かがやっていたとは驚きです

  • 素晴らしい仕事です。最近私も Nand2Tetris を始めて、今後数か月以内にコースのハードウェア部分である第1部を終えたいと思っています
    進捗はこのブログに書いています: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • 嘘ですね。NAND ゲートとクロックを使っているじゃないですか

    • そのクロックもリング発振器で作れますし、リング発振器は NAND ゲートを NOT ゲートのように接続して奇数個並べれば構成できます

  • 見事な仕事です。あとでじっくり見るためにブックマークしました
    NAND-to-Tetris は好きですが最後までやり切れなかったので、このプロジェクトを見て回るのが楽しみです

  • 気になるのですが、全体の NAND ゲート数はいくつですか？

    • コードを詳しく見てみたところ、クロック周期ごとに NAND ゲートが 3,234回使われています :)