ない
あ
Nとパワード
デバイス
は、ウェブ上でエミュレートされたクロックと NAND ゲートだけで作られたチューリング同等の 16 ビット コンピューターです。 NAND は、独自の CPU、マシンコード言語、アセンブリ言語、アセンブラ、仮想マシン言語、仮想マシン トランスレータ、プログラミング言語、コンパイラ、IDE、およびユーザー インターフェイスを備えています。 NAND は、Nand to Tetris コースとその関連書籍で指定されている Jack-VM-Hack プラットフォームに基づいています。
いくつかの数値を入力してその平均を計算し、制御フロー、算術演算、I/O、および動的メモリ割り当てを示す単純なプログラム。
プログラム出力:
How many numbers? 4
Enter a number: 100
Enter a number: 42
Enter a number: 400
Enter a number: 300
The average is 210このプログラムは、Nand to Tetris ソフトウェア スイートによって提供されました。
言語のオブジェクト指向モデルを披露するポンのゲーム。矢印キーを使用してパドルを左右に動かし、ボールをバウンドさせます。バウンドするたびにパドルが小さくなり、ボールが画面の下に当たるとゲームが終了します。
このプログラムは、Nand to Tetris ソフトウェア スイートによって提供されました。
再帰と複雑なアプリケーション ロジックを披露する 2048 年のゲーム。矢印キーを使用して、4x4 グリッド上で数字を移動します。同じ数値を相互に移動すると合計が得られます。 2048 タイルに到達するとゲームに勝ちますが、負けるまでプレイを続けることもできます。ボードがいっぱいになってそれ以上動けなくなるとゲームに負けます。
仮想マシンのエスケープを実行するために、無限再帰によって意図的にスタック オーバーフローを引き起こすプログラム。これは、実行時チェックがないことを利用して、スタックのオーバーフローを防ぎます。他の最新のプラットフォームではこれを行うことはできません:-)
実行すると、プログラムは常にスタック ポインターを画面に出力します。この表示値が 2048 を超えると、スタックは意図したメモリ領域の終わりに達し、ヒープ メモリ領域に溢れて、print ステートメントが爆発的に誤動作する原因になります。
注目に値する 2 つの点を指摘しておきます。
このプログラムをゼロでいっぱいの空の RAM 上で実行すると (ユーザー インターフェイスから RAM をクリアできます)、[リセット] ボタンを押していないにもかかわらず、プログラムが実行の途中で自動的にリセットされることがわかります。これが起こる理由は単純です。ジェイルブレイクされたランタイムは、プログラム カウンタの値を 0 に設定する命令を実行し、事実上、最初の命令にジャンプして最初からやり直すようにプログラムに指示します。
GeneticAlgorithm サンプル プログラムを実行し、その直後にこれを実行すると、プログラムは暴走し、上書きされていない古い RAM メモリを読み取ります。
ランタイムがスタック スマッシングを防止しないという事実を利用して、他の方法ではアクセスできない関数を呼び出すプログラム。これがどのように機能するかを理解するために、NAND のスタック フレーム レイアウトの図を見てみましょう。
Nand to Tetris の本から引用。
スタック レイアウトに詳しくない場合は、このエクスプロイトの背後にある主なアイデアを以下に示します。関数が戻るときは常に、実行フローを続行するためにどこに行くべきか (どのマシンコード命令メモリ アドレスか) を知る必要があります。したがって、関数が最初に呼び出されるとき、このメモリ アドレスは、他の重要でないデータとともに、戻り先の参照として、スタック フレームと呼ばれるメモリ領域内のスタックに一時的に保存されます。この図は、関数呼び出しに対するこの戻りアドレスの正確な位置、つまりリバース エンジニアリングできる位置を示しています。
このプログラムを使用すると、ユーザーは RAM 内の単一のメモリ アドレスを任意の値に上書きできます。 2 つと 2 つを組み合わせると、ユーザーがスタック フレームのリターン アドレスを別の関数のアドレスで上書きすると、基本的にプログラムに含まれる任意のコードを実行できるようになります。
実際、メモリの場所として 267 を入力し、上書きする値として 1715 を入力すると、スタック メモリ領域とアセンブラを手動で検査してリバース エンジニアリングした 2 つの数値が、実際に動作していることがわかります。
これは NAND に固有の脆弱性ではありません。 Cにも存在します！なんてクールなんでしょう！
信じられないかもしれませんが、NAND の非常に多くのさまざまなコンポーネントの中で、これだけが開発に最も長い時間がかかりました。
このプログラムは、簡易的な機械学習を利用した生物シミュレーションです。これは、Code Bullet の人工知能コード化シリーズ (パート 1 および 2) に続きます。ぜひ彼のチャンネルをチェックしてみてください。彼は本当にクールなものを作っています。
簡単に説明すると：
すべてのドットには加速ベクトルの独自の「頭脳」があり、自然選択を通じて目標に到達するために進化します。どの世代でも、ゴールに近づいて「死ぬ」ドットは、次の世代の親として選択される可能性が高くなります。生殖は本質的に脳の一部に突然変異を引き起こし、自然の進化を完全に効果的にシミュレートします。
それにもかかわらず、望まれることはたくさんあります。パフォーマンスの都合上、ドットが進化するために使用する唯一の要素は、死亡時にゴールに近づくことです。これにより、自然選択アルゴリズムに低エントロピーが与えられます。メモリ使用量の関係で、ドットの数とその脳のサイズには十分とは言えない制限があります。最後に、技術的な複雑さのため、シミュレーション中に障害物を再配置しても、ドットがゴールに到達するのに十分な大きさになることは保証されません。脳の大きさはプログラムの開始時にのみ決定されます。
私は無数の最適化テクニックを利用して、次のハードウェア制限を回避し、これを可能にしました。
やりすぎを避けるために、私は興味のある人のために、これらのテクニックと追加の洞察をこのプログラムのコードベースに文書化することにこだわりました。
始める前に、Jack でプログラムを作成する際に覚えておくべき最も重要な点は、演算子の優先順位がないということです。おそらくこれがプログラムが動作しない理由です。
たとえば、次のように変更する必要があります。
4 * 2 + 3 ～ (4 * 2) + 3
if (~x & y)からif ((~x) & y)
ただし、演算子のあいまいさがないため、 if (y & ~x)を同じに保つことができます。
括弧がないと、あいまいな式の評価値は未定義になります。
NAND は独自の完全な技術スタックを誇っています。その結果、NAND は、弱く型付けされたオブジェクト指向プログラミング言語である Jack でのみプログラムできます。平たく言えば、Jack は Java の構文を使用した C です。
例に基づいた学習のアプローチを採用して、早速見てみましょう。
/**
* This program prompts the user to enter a phrase
* and an energy level. Program output:
*
* Whats on your mind? Superman
* Whats your energy level? 3
* Superman!
* Superman!
* Superman!
*/
class Main {
function void main ( ) {
var String s ;
var int energy , i ;
let s = Keyboard . readLine ( "Whats on your mind? " ) ;
let energy = Keyboard . readInt ( "Whats your energy level? " ) ;
let i = 0 ;
let s = s . appendChar ( 33 ) ; // Appends the character '!'
while ( i < energy ) {
do Output . printString ( s ) ;
do Output . println ( ) ;
let i = i + 1 ;
}
}
}Nand から Tetris への講義スライドから抜粋。
すでにプログラミングの経験がある場合、これは非常に見慣れたものであるはずです。 Jack が Java に大きな影響を受けたことは明らかです。プログラムへのエントリ ポイントであるMain.main 、変数の基本的な使用法と制御フローの while ループを示します。
さらに、 Keyboard.readLineとKeyboard.readInt使用してユーザーからの入力を読み取り、 Output.printStringとOutput.println使用して出力を画面に出力します。これらはすべて、Jack OS リファレンスで詳細に定義されています。デフォルトでは、Jack OS はコンパイル中にプログラムにバンドルされており、文字列、メモリ、ハードウェアなどとのインターフェイスが可能になります。
すべてのプログラミング言語には、プリミティブ データ型の固定セットがあります。 Jack は、 int 、 char 、およびboolean 3 つをサポートします。必要に応じて、この基本的なレパートリーを独自の抽象データ型で拡張できます。オブジェクト指向プログラミングに関する予備知識は、このセクションに直接引き継がれます。
/** Represents a point in 2D plane. */
class Point {
// The coordinates of the current point instance:
field int x , y ;
// The number of point objects constructed so far:
static int pointCount ;
/** Constructs a point and initializes
it with the given coordinates */
constructor Point new ( int ax , int ay ) {
let x = ax ;
let y = ay ;
let pointCount = pointCount + 1 ;
return this ;
}
/** Returns the x coordinate of the current point instance */
method int getx ( ) { return x ; }
/** Returns the y coordinate of the current point instance */
method int gety ( ) { return y ; }
/** Returns the number of Points constructed so far */
function int getPointCount ( ) {
return pointCount ;
}
/** Returns a point which is this
point plus the other point */
method Point plus ( Point other ) {
return Point . new ( x + other . getx ( ) ,
y + other . gety ( ) ) ;
}
/** Returns the Euclidean distance between the
current point instance and the other point */
method int distance ( Point other ) {
var int dx , dy ;
let dx = x - other . getx ( ) ;
let dy = y - other . gety ( ) ;
return Math . sqrt ( ( dx * dx ) + ( dy * dy ) ) ;
}
/** Prints the current point instance, as "(x, y)" */
method void print ( ) {
var String tmp ;
let tmp = "(" ;
do Output . printString ( tmp ) ;
do tmp . dispose ( ) ;
do Output . printInt ( x ) ;
let tmp = ", " ;
do Output . printString ( tmp ) ;
do tmp . dispose ( ) ;
do Output . printInt ( y ) ;
let tmp = ")" ;
do Output . printString ( tmp ) ;
do tmp . dispose ( ) ;
}
} var Point p1 , p2 , p3 ;
let p1 = Point . new ( 1 , 2 ) ;
let p2 = Point . new ( 3 , 4 ) ;
let p3 = p1 . plus ( p2 ) ;
do p3 . print ( ) ; // prints (4, 6)
do Output . println ( ) ;
do Output . printInt ( p1 . distance ( p2 ) ) ; // prints 5
do Output . println ( ) ;
do Output . printInt ( getPointCount ( ) ) ; // prints 3Nand から Tetris への講義スライドから抜粋。
空間内の抽象的な点を表すPointクラスを定義します。 field変数を使用して、データ型のインスタンスごとの属性を宣言します。これは、点とのインターフェースに使用できるパブリックmethod関数を公開し、呼び出し元に 2 つの点を加算し、2 点間の距離を計算する機能を提供します。
すべてのfield変数はプライベートスコープです。クラス宣言の外部からこれらの変数を取得または設定したい場合は、この機能を提供するために、これらの変数に対応するmethod関数が必要です。
本題に留まるためにコード サンプルからは省略されていますが、オブジェクトが不要になった場合、データ クラスは割り当てを解除するためのdisposeメソッドを定義するのが通例です。 「手動メモリ管理」を参照してください。
必要に応じて、 functionおよびmethod呼び出し構文のリファレンスを次に示します。
class Foo {
...
method void f ( ) {
var Bar b ; // Declares a local variable of class type Bar
var int i ; // Declares a local variable of primitive type int
do g ( ) ; // Calls method g of the current class on the current object instance
// Note: Cannot be called from within a function (static method)
do Foo . p ( 3 ) ; // Calls function p of the current class;
// Note: A function call must be preceded by the class name
do Bar . h ( ) ; // Calls function h of class Bar
let b = Bar . r ( ) ; // Calls function or constructor r of class Bar
do b . q ( ) ; // Calls method q of class Bar on the b object
}
}Nand から Tetris への講義スライドから抜粋。
Jack が Java に似ていると述べたことを覚えていますか?それは見せかけ、あるいはよく言えば誤解を招くものでした。 Java は厳密に型指定されているため、ダウン キャスト、ポリモーフィズム、継承などの複雑な型機能をサポートしていますが、Jack はこれらをいずれもサポートしておらず、内部にある型は符号付き 16 ビット整数の 1 つだけです。これが、ジャックのタイプが非常に弱い主な理由です。実際、コンパイラは、代入や演算で異なる型を組み合わせても気にしません。
var char c ;
var String s ;
let c = 65 ; // 'A'
// Equivalently
let s = "A" ;
let c = s . charAt ( 0 ) ; var Array a ;
let a = 5000 ;
let a [ 100 ] = 77 ; // RAM[5100] = 77 var Array arr ;
var String helloWorld ;
let helloWorld = "Hello World!"
let arr = Array . new ( 4 ) ; // Arrays are not strictly typed
let arr [ 0 ] = 12 ;
let arr [ 1 ] = false ;
let arr [ 2 ] = Point . new ( 5 , 6 ) ;
let arr [ 3 ] = helloWorld ; class Complex {
field int real ;
field int imaginary ;
...
}
. . .
var Complex c ;
var Array a ;
let a = Array . new ( 2 ) ;
let a [ 0 ] = 7 ;
let a [ 1 ] = 8 ;
let c = a ; // c == Complex(7, 8)
// Works because it matches the memory layout
// of the Complex typeすべてのコード セグメントは、Nand から Tetris への講義スライドから取得されました。
これを誤解しないでください。Jack は依然として強力で機能的なオブジェクト指向モデルを提供しています。この洞察は、必要に応じて型変換をいつ、どのように実行する必要があるかを理解するのに役立つことを目的としています。
あなたも私と同じように、大の猫好きだとしましょう。そして、あなたは自分がどれだけ猫を愛しているかを誇示するためにこのプログラムを書きたかったのです。
class Main {
function void main ( ) {
while ( true ) {
do Output . printString ( "Kittens are so adorable! " ) ;
}
}
}数秒後にプログラムが「ERR6」またはヒープ オーバーフローでクラッシュすることに気づいて驚かれるかもしれません。
Jack は手動でメモリ管理されるプログラミング言語です。これは、不要になったメモリの割り当てを適切に解除するように注意する必要があることを意味します。そうしないと、Jack OS が別のことを考え、メモリ リークを促進します。ベスト プラクティスのアドバイスは、この割り当て解除を適切にカプセル化するオブジェクトを表す各クラスのdisposeメソッドを特徴付けることです。したがって、オブジェクトが必要なくなったら、そのオブジェクトのdisposeメソッドを呼び出して、最終的にヒープ メモリが不足することを防ぐことができます。
C など、他の手動でメモリ管理される言語でプログラミングしたことがある場合は、これに非常に馴染みがあるはずです。重要な違いの 1 つは、Jack OS が配列と文字列をスタックではなくヒープに保存することです。これは、プログラムがヒープ オーバーフローでクラッシュする理由を示唆しています。
私たちの仲間の猫愛好家のためにこのプログラムを修正しましょう。
class Main {
function void main ( ) {
var String s ;
while ( true ) {
let s = "Kittens are so adorable! " ;
do Output . printString ( s ) ;
do s . dispose ( ) ;
}
}
}あるいは、文字列に 1 回だけメモリを割り当てることもできます。
class Main {
function void main ( ) {
var String s ;
let s = "Kittens are so adorable! " ;
while ( true ) {
do Output . printString ( s ) ;
}
}
}これらの代替バージョンでは、文字列の出力がはるかに高速になっているだけでなく、今回は実際に永久に出力されることがわかります。万歳！
独自のdisposeメソッドの作成方法をよりよく理解できるように、 String.disposeを簡単に調べてみましょう。
method void dispose ( ) {
do stringArray . dispose ( ) ;
do Memory . deAlloc ( this ) ;
} stringArrayによって呼び出されるArray.dispose
method void dispose ( ) {
do Memory . deAlloc ( this ) ;
}適切なdisposeメソッドは、最初にフィールド変数に対して適切にdispose呼び出し、次にdo Memory.deAlloc(this);で終了する必要があります。オブジェクト インスタンス自体の割り当てを解除します。
Jack と NAND が非常に原始的であるため、言語内でのフットガンは避けられません。以下に、注意すべき未定義の動作の例を、(私の意見では) 最も重要なものから最も重要でないものの順にまとめました。
この警告は非常に重要であることがわかったので、このセクションの最初の方に移動しました。
ジャックの表情
a > b
a < b一見シンプルです。これらは必ずしも数学的に正しいとは限らず、それぞれ Java 式と同等です。
( ( a - b ) & ( 1 << 15 ) ) == 0 && a != b
( ( a - b ) & ( 1 << 15 ) ) != 0ニュアンスはどうなってるの？仮想マシンの実装は、 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 と Tetris 自体の不一致です。詳細については、こちらをご覧ください。互換性上の理由から、この動作は修正されません。
-32768 は他に類を見ない製品です。これは、 -(-32768) = -32768 のようなプロパティを保持する唯一の数値であり、正の対応物*を持たないシングルトンです。これにより、不健全さや論理エラーが発生する可能性があります。
/**
* Program output:
* --.)*(
*/
class Main {
function void main ( ) {
// Note that -32768 must instead be written as ~32767
// because the CPU can't load a number that large
do Output . printInt ( ~ 32767 ) ;
}
} Output.printInt内部的にMath.abs正の数を返すことを期待しています。 -32768 ではこれに当てはまらないため、Jack OS が誤動作します。
主な関心事は、負の演算子を使用した論理エラーの処理です。プログラマは、負の数の負が正であることを保証したい場合、-32768 のケースを確認し、適切な措置を講じる責任があります。
*これは、NAND の ALU が内部で Jack 式-x ~(x - 1)として処理するため当てはまります。 x -32768に設定し、段階的に評価してみましょう。計算の対応する 16 ビット 2 の補数バイナリ表現は次のとおりです。
x = 1000 0000 0000 0000
x - 1 = 0111 1111 1111 1111
~(x - 1) = 1000 0000 0000 0000 = x
それは同じことです！ここで何が起こったのでしょうか？ NAND は 16 ビット マシンであるため、-32768 は、そこから 1 を引くと反転されたビットが得られる唯一の数値です。つまり、 -32768 はx - 1 = ~x満たし、式が~(~x)または単にxに簡略化されます。
これは説明するまでもないので、ここで簡単なデモンストレーションを示します。
/**
* Program output:
* I have 818 cookies.
*/
class Main {
function void main ( ) {
do Main . cookies ( ) ;
}
function void cookies ( int a ) {
do Output . printString ( "I have " ) ;
do Output . printInt ( a ) ;
do Output . printString ( " cookies." ) ;
}
}一方、引数が多すぎる関数の呼び出しは完全に有効です。 argumentsキーワードを使用して、追加の関数引数にインデックスを付けることができます。引数の数を示すインジケータがないことに注意してください。
Array利用して変数を他の型にキャストできます。型キャスト変数に存在しないインスタンス メソッドを呼び出すことは未定義の動作です。コンパイラは、これを実行していることを認識できるほど賢くありません。
/**
* Program output:
* 4
*/
class Main {
constructor Main new ( ) {
return this ;
}
function void main ( ) {
var Array a ;
var Main b ;
var String c ;
let a = Array . new ( 1 ) ;
let b = Main . new ( ) ;
let a [ 0 ] = b ;
let c = a [ 0 ] ;
// Invalidly calling `String.length` on an instance of `Main`.
do Output . printInt ( c . length ( ) ) ;
}
} 詳細な例については、オーバーフロー プログラムを参照してください。
メモリ アドレス256 ～ 2047および1 ～ 15にそれぞれ存在するスタック フレームまたは内部レジスタを変更すると、未定義の動作が発生する可能性があります。これは通常、 Memory.pokeまたは負の配列インデックスを誤用しない限り不可能です。詳細な例については、SecretPassword プログラムを参照してください。
NAND は、 .jackファイルのプログラム検証を提供しますが、 .vmファイルのプログラム検証は提供しません。つまり、NAND の仮想マシン コンパイラでは、存在しない関数を呼び出したり、割り当てられていない変数を参照したり、その他の論理的に無効なメモリ操作を自由に実行できるようになります。このような未定義の動作のほとんどの場合、仮想マシンはエスケープし、画面には何も表示されません。プログラムを自分でデバッグするのはあなたの責任です。
1970 年代に台頭して以来、16 ビット コンピューティングが現代ではその地位を失ったのには十分な理由があります。 32 ビットまたは 64 ビット コンピューティングと比較すると、16 ビット コンピューティングでは処理能力とメモリ容量が限られており、現代のソフトウェアやアプリケーションの需要をまったく満たしていませんでした。
NAND もこの現実の例外ではありません。
Nand から Tetris への講義スライドから抜粋。
16 GiB MacBook と比較すると、NAND の RAM はわずか 4 KiB、比率は0.00002%です。それにもかかわらず、私たちを月に連れて行ってくれるには十分だったので、NAND も月に行けないとは誰が言えるでしょうか。
Jack OS は 14,336 個のメモリ アドレスを予約します
