Bukan
A
N dan bertenaga
Perangkat
adalah komputer 16-bit setara Turing yang seluruhnya terbuat dari jam dan gerbang NAND yang ditiru di web. NAND memiliki fitur CPU sendiri, bahasa kode mesin, bahasa rakitan, assembler, bahasa mesin virtual, penerjemah mesin virtual, bahasa pemrograman, kompiler, IDE, dan antarmuka pengguna. NAND didasarkan pada platform Jack-VM-Hack yang ditentukan dalam kursus Nand to Tetris dan buku terkaitnya.
Sebuah program sederhana yang memasukkan beberapa angka dan menghitung rata-ratanya, menampilkan aliran kontrol, operasi aritmatika, I/O, dan alokasi memori dinamis.
Keluaran program:
How many numbers? 4
Enter a number: 100
Enter a number: 42
Enter a number: 400
Enter a number: 300
The average is 210Program ini disediakan oleh rangkaian perangkat lunak Nand to Tetris.
Permainan Pong, memamerkan model bahasa berorientasi objek. Gunakan tombol panah untuk menggerakkan dayung ke kiri dan ke kanan untuk memantulkan bola. Setiap memantul, dayung menjadi lebih kecil, dan permainan berakhir ketika bola menyentuh bagian bawah layar.
Program ini disediakan oleh rangkaian perangkat lunak Nand to Tetris.
Game tahun 2048, memamerkan rekursi dan logika aplikasi yang kompleks. Gunakan tombol panah untuk memindahkan angka di sekitar kisi 4x4. Angka-angka yang sama digabungkan menjadi jumlah mereka ketika dipindahkan ke satu sama lain. Setelah ubin 2048 tercapai, Anda memenangkan permainan, meskipun Anda dapat terus bermain hingga kalah. Anda kalah ketika papan sudah penuh dan Anda tidak dapat bergerak lagi.
Sebuah program yang dengan sengaja menyebabkan stack overflow melalui rekursi tak terbatas untuk melakukan escape mesin virtual. Ini memanfaatkan fakta bahwa tidak ada pemeriksaan runtime untuk mencegah stack overflow. Tidak ada platform modern lain yang mengizinkan Anda melakukan ini :-)
Saat dijalankan, program akan terus-menerus mencetak penunjuk tumpukan ke layar. Ketika nilai yang ditampilkan melebihi 2048, tumpukan akan mencapai akhir dari ruang memori yang diinginkan dan tumpah ke ruang memori tumpukan, menyebabkan pernyataan cetak tidak berfungsi secara eksplosif:
Ada dua hal penting yang perlu diperhatikan.
Jika Anda menjalankan program ini pada RAM kosong yang penuh dengan angka nol (Anda dapat menghapus RAM melalui antarmuka pengguna), Anda akan melihat bahwa program akan mereset sendiri di tengah eksekusi meskipun tidak menekan tombol "Reset". Mengapa hal ini terjadi sederhana saja: runtime yang sudah di-jailbreak mengeksekusi instruksi yang menetapkan nilai penghitung program menjadi 0, yang secara efektif memerintahkan program untuk melompat ke instruksi pertama dan memulai kembali.
Jika Anda menjalankan program contoh GeneticAlgorithm dan kemudian menjalankannya segera setelahnya, program tersebut akan membaca memori RAM lama yang tidak pernah ditimpa.
Sebuah program yang mengeksploitasi fakta bahwa runtime tidak mencegah penghancuran tumpukan untuk memanggil fungsi yang seharusnya tidak dapat diakses. Untuk memahami cara kerjanya, mari kita periksa ilustrasi tata letak bingkai tumpukan NAND ini.
diambil dari buku Nand to Tetris.
Jika Anda tidak terbiasa dengan tata letak tumpukan, inilah ide utama di balik eksploitasi tersebut. Setiap kali suatu fungsi kembali, ia perlu mengetahui di mana (alamat memori instruksi kode mesin mana) ia harus pergi untuk melanjutkan alur eksekusi. Jadi, ketika fungsi tersebut pertama kali dipanggil, alamat memori ini, bersama dengan beberapa data tidak penting lainnya, disimpan sementara di tumpukan di wilayah memori yang disebut bingkai tumpukan sebagai referensi ke mana harus kembali. Ilustrasi ini menjelaskan posisi sebenarnya dari alamat pengirim ini relatif terhadap pemanggilan fungsi, suatu posisi yang dapat direkayasa balik.
Program ini memungkinkan pengguna untuk menimpa satu alamat memori di RAM ke nilai apa pun. Dengan menggabungkan dua dan dua, jika pengguna menimpa alamat pengirim bingkai tumpukan dengan alamat fungsi lain, mereka pada dasarnya memperoleh kemampuan untuk mengeksekusi kode arbitrer yang disertakan dalam program.
Memang benar, jika Anda memasukkan 267 sebagai lokasi memori dan 1715 sebagai nilai yang akan ditimpa, dua angka direkayasa balik dengan memeriksa secara manual ruang memori tumpukan dan assembler, Anda akan melihat ide ini dalam tindakan kerja.
Ini bukanlah kerentanan yang hanya terjadi pada NAND. Itu ada di C juga! Keren sekali!
Percaya atau tidak, dari sekian banyak komponen NAND yang berbeda, komponen ini membutuhkan waktu paling lama untuk dikembangkan!
Program ini merupakan simulasi makhluk yang memanfaatkan pembelajaran mesin sederhana. Ini mengikuti seri kode kecerdasan buatan (bagian satu dan dua) dari Code Bullet. Pastikan untuk memeriksa salurannya, dia membuat beberapa hal yang sangat keren!
Dijelaskan secara sederhana:
Setiap titik memiliki "otak" vektor percepatannya sendiri, dan mereka berevolusi untuk mencapai suatu tujuan melalui seleksi alam. Setiap generasi, titik-titik yang “mati” mendekati tujuan, kemungkinan besar akan terpilih sebagai induk bagi generasi berikutnya. Reproduksi secara inheren menyebabkan sebagian otak bermutasi, yang sepenuhnya merupakan simulasi evolusi alami.
Meski begitu, masih banyak hal yang diinginkan. Karena kinerjanya, satu-satunya faktor yang digunakan titik-titik untuk berevolusi adalah kedekatannya dengan tujuan setelah kematian, sehingga memberikan entropi rendah pada algoritma seleksi alam. Karena penggunaan memori, terdapat batasan yang lebih kecil dari jumlah titik dan ukuran otak mereka yang memuaskan. Terakhir, karena kerumitan teknis, menempatkan kembali rintangan selama simulasi tidak menjamin bahwa titik-titik tersebut akan memiliki otak yang cukup besar untuk mencapai tujuan. Ukuran otak hanya ditentukan di awal program.
Saya telah menggunakan berbagai teknik pengoptimalan untuk mengatasi batasan perangkat keras berikut dan mewujudkannya:
Untuk menghindari bertele-tele, saya terus mendokumentasikan teknik-teknik ini dan wawasan tambahan dalam basis kode program ini bagi mereka yang tertarik.
Sebelum kita mulai, hal terpenting yang perlu diingat tentang penulisan program di Jack adalah tidak ada prioritas operator; ini mungkin alasan mengapa program Anda tidak berfungsi.
Misalnya, Anda harus mengubah:
4 * 2 + 3 sampai (4 * 2) + 3
if (~x & y) ke if ((~x) & y)
tetapi Anda dapat mempertahankan if (y & ~x) sama karena tidak ada ambiguitas operator.
Tanpa tanda kurung, nilai evaluasi ekspresi ambigu tidak terdefinisi .
NAND membanggakan tumpukan teknologinya yang lengkap. Akibatnya, NAND hanya dapat diprogram dalam Jack, bahasa pemrograman berorientasi objek yang diketik dengan lemah. Dalam istilah awam, Jack adalah C dengan sintaksis Java.
Mari kita ambil pendekatan pembelajaran berbasis contoh dan selami lebih dalam.
/**
* 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 ;
}
}
}diambil dari slide kuliah Nand ke Tetris.
Jika Anda sudah mempunyai pengalaman dengan pemrograman, ini akan terlihat familiar; jelas bahwa Jack sangat terinspirasi oleh Java. Main.main , titik masuk ke program, menunjukkan penggunaan dasar variabel serta loop while untuk aliran kontrol.
Selain itu, ia menggunakan Keyboard.readLine dan Keyboard.readInt untuk membaca masukan dari pengguna, dan Output.printString dan Output.println untuk mencetak keluaran ke layar — semuanya ditentukan secara rinci dalam Referensi Jack OS. Secara default, Jack OS dibundel dengan program Anda selama kompilasi untuk mengaktifkan antarmuka dengan string, memori, perangkat keras, dan banyak lagi.
Setiap bahasa pemrograman memiliki sekumpulan tipe data primitif yang tetap. Jack mendukung tiga: int , char , dan boolean . Anda dapat memperluas repertoar dasar ini dengan tipe data abstrak Anda sendiri sesuai kebutuhan. Pengetahuan sebelumnya tentang pemrograman berorientasi objek langsung dibawa ke bagian ini.
/** 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 3diambil dari slide kuliah Nand ke Tetris.
Kami mendefinisikan kelas Point untuk mewakili titik abstrak dalam ruang. Ia menggunakan variabel field untuk mendeklarasikan atribut per instance dari tipe data. Ini memperlihatkan fungsi method publik yang dapat kita gunakan untuk berinteraksi dengan suatu titik, memberikan pemanggil fungsionalitas untuk menjumlahkan dua titik dan menghitung jarak antara dua titik.
Semua variabel field memiliki cakupan pribadi. Jika Anda ingin mendapatkan atau mengatur variabel-variabel ini dari luar deklarasi kelas, variabel-variabel ini harus memiliki fungsi method yang sesuai untuk menyediakan fungsionalitas ini.
Dihilangkan dari contoh kode agar tetap sesuai topik, biasanya kelas data menentukan metode dispose untuk pembatalan alokasi setelah objek tidak lagi diperlukan. Lihat Manajemen Memori Manual.
Jika diperlukan, berikut referensi sintaks pemanggilan function dan 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
}
}diambil dari slide kuliah Nand ke Tetris.
Ingat bagaimana kami mengatakan Jack mirip dengan Java? Itu hanyalah sebuah fasad, atau paling tidak menyesatkan. Meskipun Java memiliki tipe yang kuat dan dengan demikian mendukung fitur tipe yang kompleks seperti down casting, polimorfisme, dan pewarisan, Jack tidak mendukung semua ini dan hanya memiliki satu tipe: bilangan bulat 16-bit yang ditandatangani. Inilah alasan utama mengapa tipe Jack sangat lemah. Akibatnya, kompiler tidak akan peduli jika Anda mencampur dan mencocokkan tipe yang berbeda dalam tugas dan operasi.
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 typesemua segmen kode diambil dari slide kuliah Nand hingga Tetris.
Jangan salah paham — Jack masih menyediakan model berorientasi objek yang kuat dan fungsional. Wawasan ini bermaksud membantu Anda memahami kapan dan bagaimana Anda harus melakukan konversi jenis sesuai kebutuhan.
Katakanlah Anda seorang pecinta kucing yang gila, sama seperti saya! Dan Anda ingin menulis program ini untuk menunjukkan betapa Anda sangat menyukai kucing.
class Main {
function void main ( ) {
while ( true ) {
do Output . printString ( "Kittens are so adorable! " ) ;
}
}
}Anda mungkin terkejut saat mengetahui bahwa setelah beberapa detik, program akan crash dengan "ERR6", atau heap overflow!
Jack adalah bahasa pemrograman yang dikelola memori secara manual. Ini berarti Anda harus waspada untuk membatalkan alokasi memori yang tidak lagi diperlukan dengan benar, atau Jack OS akan berpikir sebaliknya dan memfasilitasi kebocoran memori. Saran praktik terbaik adalah menampilkan metode dispose untuk setiap kelas yang mewakili objek yang merangkum deallokasi ini dengan benar. Jadi, ketika objek tidak lagi diperlukan, Anda dapat memanggil metode dispose untuk memastikan Anda tidak kehabisan memori heap.
Jika Anda telah memprogram dalam bahasa lain yang dikelola memori secara manual, seperti C, ini akan terlihat sangat familiar. Salah satu perbedaan utamanya adalah Jack OS menyimpan array dan string di heap, bukan di stack, yang memberi petunjuk mengapa program mogok karena heap overflow.
Mari kita perbaiki program ini untuk sesama fanatik kucing.
class Main {
function void main ( ) {
var String s ;
while ( true ) {
let s = "Kittens are so adorable! " ;
do Output . printString ( s ) ;
do s . dispose ( ) ;
}
}
}Alternatifnya, Anda dapat mengalokasikan memori untuk string hanya sekali.
class Main {
function void main ( ) {
var String s ;
let s = "Kittens are so adorable! " ;
while ( true ) {
do Output . printString ( s ) ;
}
}
}Anda akan melihat bahwa versi alternatif ini tidak hanya mencetak string lebih cepat, tetapi kali ini mereka akan mencetak selamanya! Hore!
Mari kita intip String.dispose agar Anda dapat lebih memahami cara menulis metode dispose Anda sendiri.
method void dispose ( ) {
do stringArray . dispose ( ) ;
do Memory . deAlloc ( this ) ;
} Array.dispose dipanggil dengan stringArray
method void dispose ( ) {
do Memory . deAlloc ( this ) ;
} Metode dispose yang tepat pertama-tama harus dispose variabel bidangnya dengan tepat dan kemudian diakhiri dengan do Memory.deAlloc(this); untuk membatalkan alokasi instance objek itu sendiri.
Dengan betapa primitifnya Jack dan NAND, serangan dalam bahasa tidak bisa dihindari. Saya telah mengumpulkan contoh perilaku tidak terdefinisi berikut yang harus Anda waspadai, diurutkan dari (menurut saya) yang paling penting hingga yang paling tidak penting.
Saya merasa peringatan ini sangat penting sehingga saya memindahkannya ke awal bagian ini.
Ekspresi Jack
a > b
a < btampak sederhana. Ekspresi tersebut tidak selalu benar secara matematis, dan masing-masing setara dengan ekspresi Java
( ( a - b ) & ( 1 << 15 ) ) == 0 && a != b
( ( a - b ) & ( 1 << 15 ) ) != 0 Ada apa dengan nuansanya? Implementasi mesin virtual mengubah a > b menjadi a - b > 0 . Ini masalahnya: a - b bisa meluap :(
Apa yang dievaluasi oleh 20000 > -20000 ? Mesin virtual mengubah ini menjadi 20000 - (-20000) > 0 yang bernilai -25336 > 0 . Sayangnya, jawabannya false .
Namun, 20000 > -10000 bernilai 30000 > 0 , atau true .
Seperti yang sudah Anda bayangkan, jika jarak absolut antara a dan b lebih dari 32767, a > b dan a < b salah. Jika tidak, kamu baik-baik saja.
Ini bukan bug implementasi, melainkan ketidakkonsistenan antara Nand dan Tetris itu sendiri. Lebih lanjut tentang itu di sini. Demi alasan kompatibilitas, perilaku ini tidak akan diperbaiki.
-32768 adalah salah satu dari jenisnya. Ini adalah satu-satunya bilangan yang memiliki properti sedemikian rupa sehingga -(-32768) = -32768, bilangan tunggal tanpa pasangan positif * . Hal ini dapat menyebabkan ketidakwajaran dan kesalahan logika.
/**
* 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 secara internal mengharapkan Math.abs mengembalikan angka positif. Ini tidak terjadi pada -32768, sehingga Jack OS tidak berfungsi.
Perhatian utama Anda adalah menangani kesalahan logika dengan operator negatif. Sebagai pemrogram, jika Anda ingin menjamin bilangan negatif negatif adalah positif, Anda bertanggung jawab untuk memeriksa kasus -32768 dan mengambil tindakan yang tepat.
* Hal ini berlaku karena ALU NAND secara internal memproses ekspresi Jack -x sebagai ~(x - 1) . Mari kita atur x ke -32768 dan evaluasi langkah demi langkah. Berikut adalah representasi biner komplemen dua 16-bit yang sesuai dari komputasi:
x = 1000 0000 0000 0000
x - 1 = 0111 1111 1111 1111
~(x - 1) = 1000 0000 0000 0000 = x
Itu hal yang sama! Apa yang terjadi di sini? Karena NAND adalah mesin 16-bit, -32768 adalah satu-satunya angka yang jika Anda kurangi satu darinya, Anda mendapatkan bit yang dibalik. Dengan kata lain, -32768 memenuhi x - 1 = ~x , menyederhanakan ekspresi menjadi ~(~x) atau hanya x .
Yang ini sudah cukup jelas, jadi inilah demonstrasi singkatnya.
/**
* 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." ) ;
}
} Di sisi lain, memanggil fungsi dengan terlalu banyak argumen adalah sah. Anda dapat menggunakan kata kunci arguments untuk mengindeks argumen fungsi tambahan. Perhatikan bahwa tidak ada indikator untuk jumlah argumen.
Anda dapat menggunakan Array untuk memasukkan variabel ke tipe lainnya. Memanggil metode instance yang tidak ada pada variabel tipe yang dicor adalah perilaku tidak terdefinisi; kompiler tidak cukup pintar untuk menyadari saat Anda melakukan ini.
/**
* 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 ( ) ) ;
}
} Lihat program Overflow untuk contoh mendalam.
Memodifikasi bingkai tumpukan atau register internal yang masing-masing berada di alamat memori 256 hingga 2047 dan 1 hingga 15 dapat menyebabkan perilaku tidak terdefinisi. Ini biasanya tidak mungkin dilakukan tanpa menyalahgunakan Memory.poke atau pengindeksan array negatif. Lihat program SecretPassword untuk contoh mendalam.
NAND menawarkan validasi program untuk file .jack tetapi tidak untuk file .vm . Ini berarti kompiler mesin virtual NAND memberi Anda kebebasan untuk memanggil fungsi yang tidak ada, mereferensikan variabel yang belum ditetapkan, atau melakukan operasi memori lain yang secara logis tidak valid. Dalam sebagian besar kasus perilaku tidak terdefinisi seperti itu, mesin virtual akan keluar dan layar tidak menampilkan apa pun. Anda bertanggung jawab untuk men-debug sendiri program tersebut.
Sejak kemunculannya pada tahun 1970-an, ada alasan bagus mengapa komputasi 16-bit tidak lagi populer di era modern. Dibandingkan dengan komputasi 32-bit atau 64-bit, komputasi 16-bit menawarkan kekuatan pemrosesan dan kapasitas memori terbatas yang tidak memenuhi tuntutan perangkat lunak dan aplikasi kontemporer.
NAND tidak terkecuali dalam kenyataan ini.
diambil dari slide kuliah Nand ke Tetris.
Dibandingkan dengan MacBook 16 GiB Anda, NAND menikmati RAM 4 KiB yang sedikit, rasio 0,00002% ! Meskipun demikian, itu sudah cukup untuk membawa kita ke bulan, jadi siapa bilang NAND juga tidak bisa.
Jack OS mencadangkan 14.336 alamat memori
