Show HN: NANDゲートで作られたプログラム可能なコンピュータ
(github.com/ArhanChaudhary)NAND: Web上に実装された完全なチューリング等価の16ビットコンピュータ
- NANDは、NANDゲートとクロックだけでWeb上にエミュレーションされた、チューリング等価の16ビットコンピュータ
- NANDは、独自のCPU、機械語、アセンブリ言語、アセンブラ、VM言語、VMトランスレータ、プログラミング言語、コンパイラ、IDE、UIを備える
- NANDは、Nand to Tetrisコースと関連書籍で規定されているJack-VM-Hackプラットフォームをベースにしている
プログラム例
Average
- 数値を入力して平均を計算するシンプルなプログラム
- 制御フロー、算術演算、I/O、動的メモリ割り当てを示す
Pong
- Pongゲームで言語のオブジェクト指向モデルを示す
- 矢印キーでパドルを左右に動かしてボールを打ち返す
- 打ち返すたびにパドルが小さくなり、ボールが画面下に落ちるとゲーム終了
2048
- 2048ゲームで再帰と複雑なアプリケーションロジックを示す
- 矢印キーで数値を4x4グリッド上で動かす
- 同じ数値同士がぶつかると結合される
- 2048タイルに到達すると勝ちだが、そのまま続けてさらに大きくできる
- 盤面が埋まり、動かせなくなったときにゲーム終了
Overflow
- 無限再帰によって意図的にスタックオーバーフローを発生させ、仮想マシンから脱出するプログラム
- スタックオーバーフローを防ぐランタイムチェックがない点を利用
- 実行中はスタックポインタの値を継続的に出力する
- スタックが意図されたメモリ領域の終端に達してヒープメモリへはみ出すと、print文が爆発的に誤動作する
SecretPassword
- ランタイムがスタックスマッシングを防がない点を利用して、通常はアクセスできない関数を呼び出すプログラム
- NANDのスタックフレームレイアウトを理解している必要がある
- ユーザーが任意のメモリアドレスを任意の値で上書きできるようにしている
- 関数の戻りアドレスを別の関数のアドレスで上書きすると、任意のコードを実行できる
- スタックアドレスとアセンブラを手動で調べて得た特定のメモリ位置と上書き値を入力すると、このアイデアが動作するのを確認できる
GeneticAlgorithm
- NANDの多くのコンポーネントの中でも、開発に最も時間がかかった部分
- シンプルな機械学習を用いた生物シミュレーション
- 各点の「脳」は加速ベクトルであり、目標に向けて自然選択によって進化する
- 各世代で、目標により近い位置で「死んだ」点ほど、次世代の親として選ばれやすい
- 繁殖によって脳に突然変異が起こり、自然進化を効果的にシミュレートする
- 性能上の制約のため、多くの最適化手法を使ってハードウェアの制限を回避し、これを実現している
Jackでプログラミングする
- Jackでプログラミングするとき最も重要なのは、演算子優先順位がないこと。これがプログラムが正しく動かない理由かもしれない
4 * 2 + 3→(4 * 2) + 3、if (~x & y)→if ((~x) & y)のように、括弧で優先順位を明示する必要がある
Jackの紹介
- NANDは独自の技術スタック全体を備えている
- Jackは弱い型付けのオブジェクト指向言語。ひと言でいえば、Java構文を持つC言語
- 例を通して学んでみよう
カスタムデータ型
- Jackは3つの基本型
int、char、booleanをサポートする - 必要に応じて、抽象データ型としてこれらを拡張できる
- オブジェクト指向プログラミングの知識をそのまま活用できる
- 例では、
Pointクラスで抽象的な空間上の点を定義している field変数で、データ型のインスタンスごとの属性を宣言する- 点を操作する公開
method関数を提供し、呼び出し側が点を加算したり、2点間の距離を計算したりできるようにする - すべての
field変数は非公開スコープとなる。これらにアクセスするにはmethod関数として提供する必要がある - データクラスでは
disposeメソッドを定義するのが慣例 function、methodの呼び出し構文を参照
弱い型変換
- JackはJavaに強く影響を受けているが、あくまで表面的なものにすぎない
- Javaは強い型付け言語で、ダウンキャスト、多態性、継承などの複雑な型機能をサポートする
- 一方Jackが実際にサポートするのは、符号付き16ビット整数ただ1つ
- これがJackが弱い型付けである主な理由
- そのため、Jackコンパイラは代入や演算で異なる型を混在させても気にしない
- Jackはそれでも強力で実用的なオブジェクト指向モデルを提供する
- 型変換をいつどのように行うべきかを理解する助けになるはず
手動メモリ管理
- Jackは手動でメモリを管理する言語
- もう不要になったメモリを適切に解放することに注意する必要がある
- そうしないと、Jack OSはメモリリークがあるとみなす
- ベストプラクティスは、各クラスごとに割り当て解除を適切にカプセル化した
disposeメソッドを書くこと - オブジェクトが不要になったときにこのメソッドを呼べば、ヒープメモリ不足を防げる
- Cのような他の手動メモリ管理言語の経験があれば、なじみやすいだろう
- 違いは、Jack OSが配列と文字列をスタックではなくヒープに保存すること
String.disposeを見れば、disposeメソッドをどう書くべきか分かるはず
未定義動作
演算子優先順位
- あまりに重要なので前に移した
より小さい・より大きい演算子
- Jackの比較式
a > b、a < bは単純に見えるが、数学的に常に正しいわけではない - 仮想マシンはこれを
a - b > 0に変換する。しかしa - bはオーバーフローする可能性がある 20000 > -20000はどう評価されるだろうか？20000 - (-20000) > 0、つまり-25336 > 0となりfalseになる- しかし
20000 > -10000は30000 > 0、つまりtrueになる aとbの絶対値の差が32767より大きいと、a > bとa < bは誤る。それ以外なら問題ない- これはバグではなく、Nand to Tetrisとの非互換性によるもの。互換性のため、この動作は修正されない
-32768
- -32768は、-(-32768) = -32768 というユニークな性質を持つ唯一の数。正の対になる値を持たない単独の存在
- このため、一見すると筋が通らないロジックエラーが発生しうる
-xが内部的には~(x-1)として処理されるためxに-32768を代入するとx-1 = ~xが成り立つ。~(~x)はxと同じになる- 何が起きたのか？ NANDは16ビットマシンなので、-32768から1を引くとビットが反転した結果になる
- 重要なのは、単項マイナス演算子の扱いで起こるロジックエラーに対処すること
- -32768のケースを確認し、適切に処理するのはプログラマの責任
引数が足りない関数呼び出し
- 説明不要の、明らかな未定義動作
不適切な型キャスト
Arrayを使えば変数をどんな型にでもキャストできる- 存在しないインスタンスメソッドを呼ぶと未定義動作が発生する
- コンパイラはそこまで検出できるほど賢くない
スタックオーバーフロー
- Overflowプログラムを参照
スタックフレームや内部レジスタの改変
- スタックフレームや、256〜2047、1〜15番地にある内部レジスタを改変すると未定義動作が発生する可能性がある
- 通常は
Memory.pokeや負の配列インデックスを誤用しない限り不可能 - SecretPasswordプログラムを参照
ハードウェア仕様
-
1970年代以降、16ビットコンピューティングが廃れたのには理由がある
-
32ビットや64ビットと比べて処理能力とメモリ容量が限られ、現代ソフトウェアの要求を満たせない
-
NANDも例外ではない
-
16GiBのMacBookと比べると、NANDには4KiBのRAMしかない。わずか0.00002%
-
それでも、私たちを月に連れて行くくらいのことはできる
-
Jack OSは4KiBのうち14,336番地までのメモリアドレスをヒープ用に予約している。異様に小さい値
-
そのため、Jackアプリケーションがメモリを効率的に解放することは非常に重要
-
あまりに野心的な計画だと、ヒープメモリが足りなくなり、データ型やロジックを完全に書き直す必要が出るかもしれない
-
4KiBのうち8,192番地以降のメモリアドレスは画面に予約されている
-
各アドレスの各ビットは、512x256画面のピクセルに線形にマッピングされる。LSb 0ビット番号付けを使用
-
24,576番地のメモリアドレスはキーボードに予約されている
-
押されたキーのASCIIコード値が反映される
-
ただし、ユーザー入力処理のために直接アクセスしてはいけない。Jack OSが提供するKeyboardクラスと関連関数を使う必要がある
-
NANDキーボードはASCIIと特殊キーを認識する
-
静的クラス変数には240個、グローバルスタックには1,792個のメモリアドレスが予約されている
-
深い再帰をしない限り、この制限は問題にならないはず
1件のコメント
Hacker Newsの意見