Show HN: Komputer yang Dapat Diprogram Dibuat dari Gerbang NAND

 (github.com/ArhanChaudhary)
2 poin oleh GN⁺ 2024-04-27 | 1 komentar | Bagikan ke WhatsApp
  • NAND adalah komputer 16-bit setara Turing yang diemulasikan di web, mencakup semuanya dari CPU hingga IDE dan UI berdasarkan premis edukatif bahwa ia tersusun hanya dari clock dan gerbang NAND
  • Stack miliknya sendiri berbasis platform Jack-VM-Hack, serta menyediakan CPU, bahasa mesin, assembly, assembler, bahasa VM, VM translator, bahasa Jack, dan compiler
  • Program contoh mencakup bukan hanya Average, Pong, dan 2048, tetapi juga demo VM escape yang memanfaatkan stack overflow dan stack smashing, serta GeneticAlgorithm yang menggunakan machine learning sederhana
  • Jack adalah bahasa berorientasi objek bertipe lemah dengan sintaks mirip Java, tetapi secara internal bergantung pada satu signed 16-bit integer, dengan banyak batasan seperti tidak adanya prioritas operator, manajemen memori manual, dan perilaku yang tidak terdefinisi
  • Proyek ini bukan berarti semua komputasi benar-benar dijalankan pada gerbang NAND fisik; ini adalah implementasi untuk edukasi dan teori yang menggunakan compiler TypeScript, VM translator, simulator logika gerbang NAND berbasis Rust, dan WebAssembly

Seluruh stack komputer yang disediakan NAND

  • NAND adalah komputer 16-bit berbasis web yang diperkenalkan sebagai singkatan dari Not A Nand-powered Device
  • Ia mengemulasikan komputer setara Turing yang dibuat dari clock dan gerbang NAND, serta menyertakan sendiri komponen-komponen berikut
    • CPU
    • bahasa kode mesin
    • bahasa assembly
    • assembler
    • bahasa virtual machine
    • penerjemah virtual machine
    • bahasa pemrograman
    • compiler
    • IDE
    • antarmuka pengguna
  • Dasarnya adalah platform Jack-VM-Hack dari kursus Nand to Tetris dan buku terkait
  • Video demo NAND tersedia

Program contoh dan demo

  • Average

    • Program sederhana yang menerima input angka dan menghitung rata-rata
    • Menunjukkan control flow, operasi aritmetika, I/O, dan alokasi memori dinamis
    • Program ini disediakan dalam Nand to Tetris software suite

  • Pong

    • Game Pong yang menunjukkan model berorientasi objek
    • Paddle digerakkan ke kiri dan kanan dengan tombol arah untuk memantulkan bola
    • Setiap kali bola memantul, paddle menjadi lebih kecil, dan jika bola menyentuh bagian bawah layar, game berakhir
    • Program ini disediakan dalam Nand to Tetris software suite

  • 2048

    • Game 2048 yang menunjukkan recursion dan application logic yang kompleks
    • Di grid 4x4, angka digerakkan dengan tombol arah, dan angka yang sama akan digabungkan
    • Pemain menang saat mencapai tile 2048, tetapi dapat terus bermain sampai kalah

  • Overflow

    • Dengan rekursi tak terbatas, program sengaja memicu stack overflow untuk melakukan virtual machine escape
    • Memanfaatkan tidak adanya pemeriksaan pencegahan stack overflow saat runtime
    • Jika nilai stack pointer melebihi 2048, stack keluar dari ruang memori yang semestinya dan mengalir ke heap memory space
    • Jika dijalankan pada RAM kosong, program dapat reset di tengah jalan karena instruction yang menetapkan program counter ke 0
    • Jika dijalankan segera setelah GeneticAlgorithm, program dapat membaca RAM memory sebelumnya yang belum tertimpa

  • SecretPassword

    • Memanfaatkan fakta bahwa runtime tidak mencegah stack smashing untuk memanggil fungsi yang semula tidak dapat diakses
    • Pengguna dapat menimpa satu memory address di RAM dengan nilai yang diinginkan
    • Jika return address pada stack frame ditimpa dengan alamat fungsi lain, eksekusi kode arbitrer di dalam program menjadi mungkin
    • Nilai contoh adalah memory location 267, overwrite value 1743
    • Kerentanan sejenis juga ada pada buffer overflow di C

  • GeneticAlgorithm

    • Ini adalah simulasi creature yang menggunakan machine learning sederhana
    • Setiap dot memiliki “brain” sendiri yang terdiri dari acceleration vector, dan berevolusi melalui seleksi alam untuk mencapai goal
    • Dot yang mati di posisi lebih dekat ke goal memiliki peluang lebih tinggi untuk dipilih sebagai parent generasi berikutnya
    • Dalam proses reproduction, sebagian brain mengalami mutation untuk menyimulasikan evolusi alami
    • Video demo Genetic Algorithm tersedia

Batasan hardware yang dihadapi GeneticAlgorithm

  • GeneticAlgorithm adalah program tunggal yang paling lama dikembangkan di antara berbagai komponen NAND
  • Karena alasan performa, satu-satunya faktor yang digunakan dot untuk berevolusi adalah seberapa dekat posisinya dengan goal saat mati, sehingga entropy algoritme seleksi alamnya rendah
  • Karena penggunaan memori, ada batasan yang kurang memuaskan pada jumlah dot dan ukuran brain
  • Karena kompleksitas teknis, meskipun obstacle dipindahkan ulang selama simulation, tidak ada jaminan brain dot cukup besar untuk mencapai goal
    • Brain size hanya ditentukan saat program dimulai
  • Implementasinya mengakali batasan NAND dengan berbagai optimasi
    • ROM instruction memory space terbatas, sehingga jika kode terlalu banyak, program tidak akan ter-compile
    • GeneticAlgorithm final menggunakan 99,2% dari instruction memory space
    • RAM memory space terbatas, sehingga heap memory usage harus dioptimalkan
    • Alasan layar terisi static di antara generasi adalah karena screen memory space digunakan sebagai temporary swap memory untuk generasi berikutnya
    • NAND tidak memiliki floating point type, dan rentang integer yang dapat direpresentasikan adalah dari -32768 hingga 32767
    • Presisi perhitungan fitness menjadi rendah, dan integer overflow juga harus diperhitungkan
  • Optimasi terkait dan insight tambahan didokumentasikan di codebase GeneticAlgorithm

Menulis Program NAND dengan Jack

  • Hal paling penting yang ditekankan sebagai penyebab utama program tidak berjalan di Jack adalah tidak adanya prioritas operator
    • 4 * 2 + 3 harus ditulis seperti (4 * 2) + 3
    • if (~x & y) harus ditulis seperti if ((~x) & y)
    • Nilai evaluasi dari expression ambigu tanpa tanda kurung bersifat undefined
  • Jack adalah weakly typed object-oriented programming language milik NAND
    • Dalam penjelasannya, lebih mendekati “C dengan syntax Java”
    • Karena NAND memiliki complete tech stack sendiri, pemrograman hanya bisa dilakukan dengan Jack
  • Jack OS bawaan di-bundle bersama program saat compile
    • Menyediakan interface dengan strings, memory, dan hardware
    • Mencakup function seperti Keyboard.readLine, Keyboard.readInt, Output.printString, Output.println
  • Jack mendukung tiga primitive type: int, char, boolean
    • Abstract data type dapat didefinisikan melalui class
    • Variable field mendeklarasikan attribute per instance
    • Variable field memiliki private scope, dan akses dari luar membutuhkan method
  • function dan method memiliki cara pemanggilan yang berbeda
    • Method dari current object dapat dipanggil di dalam class yang sama seperti do g();
    • Function call harus diawali dengan class name
    • Object method dipanggil melalui object seperti do b.q();

Weak typing dan manajemen memori di Jack

  • Tidak seperti Java, Jack tidak mendukung strong type, down casting, polymorphism, maupun inheritance
  • Secara internal, satu-satunya type sebenarnya adalah signed 16-bit integer
    • Compiler tidak peduli meskipun type dicampur dalam assignment dan operation
    • Jika 65 dimasukkan ke char, itu dapat diperlakukan setara dengan 'A'
    • Jika 5000 dimasukkan ke variable Array lalu menjalankan a[100] = 77, hasilnya menjadi RAM[5100] = 77
    • Entry array dapat berisi data type yang berbeda-beda
    • Jika memory layout cocok, Array dapat digunakan seperti instance class lain
  • Jack adalah bahasa dengan manajemen memori manual
    • Jika memory yang tidak lagi diperlukan tidak di-deallocate, memory leak akan terjadi
    • Heap overflow muncul sebagai ERR6
    • Jack OS menyimpan array dan string di heap, bukan di stack
  • Best practice untuk class yang merepresentasikan object adalah memiliki method dispose
    • Panggil dispose milik field variable terlebih dahulu
    • Terakhir, deallocate object instance itu sendiri dengan do Memory.deAlloc(this);
  • Loop yang berulang kali membuat dan mencetak string literal dapat menyebabkan heap overflow
    • Dispose string pada setiap iterasi, atau
    • Allocate string hanya sekali dan gunakan ulang agar dapat terus mencetak

Perilaku tidak terdefinisi dan hal yang perlu diperhatikan

  • Operator perbandingan

    • a > b dan a < b tidak selalu benar secara matematis
    • Implementasi VM mengubah a > b menjadi a - b > 0
    • Karena a - b dapat overflow, 20000 > -20000 menjadi false
    • Jika absolute distance antara a dan b lebih besar dari 32767, > dan < bisa salah
    • Perilaku ini tidak diperbaiki demi compatibility dengan Nand to Tetris

  • -32768

    • -32768 adalah satu-satunya nilai yang membuat -(-32768) = -32768
    • Karena tidak memiliki positive counterpart, nilai ini dapat menimbulkan unsoundness dan logic error
    • Output.printInt secara internal mengharapkan Math.abs mengembalikan positive number, tetapi pada -32768 hal itu tidak terjadi sehingga Jack OS mengalami malfunction

  • Pemanggilan function dengan argumen terlalu sedikit

    • Undefined behavior dapat terjadi meskipun function yang memiliki parameter dipanggil tanpa argumen
    • Sebaliknya, function call dengan argumen terlalu banyak valid, dan extra argument dapat di-index dengan keyword arguments
    • Tidak ada argument count indicator

  • Type casting yang tidak tepat

    • Variable dapat di-cast ke type lain menggunakan Array
    • Memanggil instance method yang tidak ada pada variable hasil cast adalah undefined behavior
    • Compiler tidak cukup smart untuk menyadari hal ini

  • Modifikasi stack frame dan internal register

    • Jika stack frame pada memory address 256~2047 atau internal register pada 1~15 dimodifikasi, undefined behavior dapat terjadi
    • Disebutkan bahwa hal ini umumnya sulit terjadi tanpa penyalahgunaan Memory.poke atau negative array indexing

  • Memuat file VM pengguna

    • NAND menyediakan program validation untuk file .jack, tetapi tidak untuk file .vm
    • Dalam file .vm, pemanggilan function yang tidak ada, referensi ke variable yang belum di-assign, dan memory operation yang secara logis invalid dapat dilakukan
    • Dalam sebagian besar kasus, virtual machine escape terjadi dan mungkin tidak ada apa pun yang ditampilkan di screen

Spesifikasi hardware dan tata letak memori

  • RAM NAND terdiri dari 32.768 words, dan setiap word berisi 16-bit binary number
  • Hardware mencadangkan 8.192 memory address untuk screen
    • Setiap bit pada setiap address dipetakan secara linear ke pixel yang sesuai pada screen 512x256
    • Bit numbering menggunakan metode LSb 0
  • Keyboard dipetakan ke memory address 24576
    • Key yang sedang ditekan tercermin di lokasi ini
    • Disarankan menggunakan class Keyboard dari Jack OS daripada menangani user input langsung melalui address ini
  • Keyboard mengenali ASCII character dan key khusus
    • 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 mencadangkan 240 memory address untuk static class variable dan 1.792 memory address untuk global stack
    • Disebutkan bahwa batasan ini umumnya tidak menjadi masalah selama tidak melakukan deep recursion

Mengimplementasikan OS sendiri melampaui Jack OS

  • Pada dasarnya, saat kompilasi Jack OS dibundel bersama program dan menyediakan string, memori, serta antarmuka hardware
  • Anda dapat menyediakan implementasi OS sendiri dengan antarmuka hardware khusus
    • IDE memperlakukan file Jack OS sama seperti file program biasa
    • File OS juga dapat dihapus atau ditimpa
  • Meski menggunakan OS sendiri, ada beberapa fungsi inti yang wajib diimplementasikan untuk kompilasi
    • Sys.init: entry point sebenarnya yang di-hardcode dalam implementasi VM, bukan Main.main
    • Memory.alloc: heap memory allocator yang digunakan secara internal saat constructor class membuat object
    • String.newWithStr: constructor internal untuk string literal
    • Math.multiply: dipanggil secara internal sebagai pengganti expression Jack x * y
    • Math.divide: dipanggil secara internal sebagai pengganti expression Jack x / y
  • Sys.init pada Jack OS yang disediakan menginisialisasi memori, math, screen, dan output, lalu memanggil Main.main() dan kemudian Sys.halt()

Cara kerja internal NAND

  • Komputer NAND mengikuti arsitektur Harvard
    • ROM sebagai instruction memory dan RAM sebagai data memory dipisahkan
    • CPU membuat keduanya bekerja bersama
  • CPU adalah accumulator machine
    • Pada control flow, CPU sangat bergantung pada register bawaan
    • Di sini accumulator adalah register D
  • Instruction set CPU hanya memiliki dua opcode
    • Instruction set relatif sederhana, tetapi menyediakan fitur yang kaya
    • ALU ditentukan lewat expression yang dapat dihitung dalam satu instruction
  • Compiler dan virtual machine bukan konsep yang unik hanya untuk NAND, sehingga dibahas singkat
    • Beberapa fitur sintaks yang aneh merupakan akibat dari upaya mempermudah implementasi compiler
    • Compiler adalah recursive descent parser di atas grammar LL(1)
    • Compiler menghasilkan VM code, dan VM digunakan sebagai simple stack machine
    • Setiap VM instruction dipetakan ke assembly dan machine code
  • Kode implementasi dapat dilihat di core dan implementasi compiler

Inti referensi bahasa Jack dan OS

  • Program Jack terdiri dari kumpulan class
    • Class didefinisikan dalam file terpisah
    • Diperlukan satu atau lebih class, dan salah satunya harus Main
    • Entry point menurut Jack OS adalah function main pada class Main
  • Class dapat berisi deklarasi field, static, constructor, method, dan function
    • Urutan deklarasi field dan static bersifat arbitrary
    • Urutan deklarasi subroutine juga arbitrary
    • Type adalah salah satu dari void, int, boolean, char, atau nama class
  • Karakteristik sintaks
    • Whitespace dan comment diabaikan
    • & dan | adalah operator bitwise dan tidak melakukan short-circuit
    • true, false, null masing-masing adalah -1, 0, 0
    • String constant tidak dapat memuat newline atau quotation mark secara langsung, dan escape juga tidak bisa digunakan
    • Quotation mark dan newline disediakan melalui String.doubleQuote() dan String.newLine() dari OS
    • Identifier bersifat case-sensitive
  • Class utama Jack OS
    • Array: pembuatan dan dispose array
    • Keyboard: input key press, character, line, dan integer
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: output text screen dan perpindahan cursor
    • Screen: menggambar pixel, line, rectangle, circle
    • String: pembuatan string, dispose, akses character, append, konversi integer
    • Sys: halt, error, wait
  • Invalid state menampilkan error code dalam format "ERR[N]" dan menghentikan eksekusi program
    • ERR3: division by zero
    • ERR6: heap overflow
    • ERR15, ERR16: string index out of bounds
    • ERR17: string is full
    • ERR20: illegal cursor location

Ini bukan proyek yang benar-benar hanya terdiri dari NAND gate

  • FAQ mengakui bahwa deskripsi dan judul “everything made from NAND gates” menyesatkan, tetapi dibuat dengan good faith
  • Compiler dan virtual machine translator ditulis dalam TypeScript
  • Emulated kernel dan emulated hardware tidak merepresentasikan apa adanya cara kerja real computer
  • Simulator logika NAND gate sebenarnya ditulis dalam Rust dan hanya merupakan bagian kecil dari keseluruhan codebase
    • Kode Rust dikompilasi menjadi WebAssembly agar berjalan di browser
    • Disebutkan bahwa karena hal ini, premis bahwa semua computation berjalan di NAND gate pada dasarnya menjadi tidak berlaku
  • NAND berperan sebagai proyek edukatif dan teoretis
    • Secara teori, CPU logic yang sama dapat berjalan juga pada manifestasi dunia nyata dari emulated hardware
    • Sebagai contoh proyek hardware FPGA berbasis nand2tetris, disajikan https://gitlab.com/x653/nand2tetris-fpga/

Cakupan implementasi dan keterbatasan IDE

  • NAND mengikuti spesifikasi dari course Nand to Tetris dan buku terkait
  • Pengimplementasi membuat sendiri spesifikasi CPU, assembler, virtual machine translator, dan compiler, lalu saat mem-porting platform ke web menambahkan IDE dan UI sendiri
  • Alasan Jack harus menyatakan type secara eksplisit adalah agar compiler dapat menentukan instance method itu milik class mana
    • s.appendChar(33) dari s yang dideklarasikan sebagai type String diubah saat kompilasi menjadi String.appendChar(s, 33)
  • IDE mengorbankan user experience demi kesederhanaan implementasi
    • Untuk syntax highlighting, digunakan contenteditable dan cursor positioning logic
    • Akibatnya lambat, tampak jelas buggy, dan common keybind tidak berfungsi
  • Untuk mengompilasi dan menjalankan code, cukup tekan “Start”
    • OS umumnya membutuhkan sedikit kurang dari 1 detik untuk inisialisasi memory dan setup service

Bacaan terkait

1 komentar

 
GN⁺ 2024-04-27
Komentar Hacker News

  • Proyek sampingan yang luar biasa, dan README-nya juga benar-benar bagus. Setelah sedikit mengutak-atik 6502 Computer milik Ben Eater (https://eater.net/), saya sempat berpikir untuk mencoba mengikuti Nand to Tetris

    • Apakah mungkin juga membuat komputer NAND-to-Tetris fisik? Atau ini murni latihan yang dilakukan di lingkungan virtual?

  • Dengan materi ini saja, sepertinya bisa dibuat beberapa kelas kuliah. Materinya dibuat dengan baik

    • Bukankah ini pada dasarnya Nand2Tetris? Saya sudah mengikuti kursus itu, dan sekilas terlihat sama, termasuk sampai bahasa Jack

  • Benar-benar dibuat dengan baik. Ini berarti sudah menapaki sendiri lapisan abstraksi yang tidak akan pernah dilihat sebagian besar programmer sepanjang karier mereka

  • Karya yang keren. NAND to Tetris membantu saya mendapatkan pekerjaan pertama setelah lulus kuliah

    • Penasaran, bagaimana itu membantu?

  • Pada awal 1990-an, dalam ujian kualifikasi perangkat keras komputer di UC Berkeley, desain yang mirip seperti ini adalah soal inti
    Secara spesifik, soalnya adalah merancang prosesor RISC pipeline berbasis microcode dari dasar hanya dengan gerbang NAND. Tidak perlu benar-benar membuatnya, tetapi harus menyerahkan rancangan rinci di atas kertas

  • Pekerjaan yang benar-benar hebat. Saat mengikuti kursus Nand2Tetris, saya juga ingin mencoba membuat implementasi virtual serupa
    Mengesankan bahwa ini benar-benar berhasil diwujudkan, dan saya rasa sekarang dia benar-benar memahami cara kerja komputer dengan sangat baik

    • Saya juga pagi ini sempat memikirkan hal serupa, yaitu memodelkan komponen dasar dengan SVG
      Tapi mengejutkan bahwa seseorang sudah membuat sesuatu yang setidaknya satu tingkat orde lebih hebat daripada yang saya bayangkan

  • Pekerjaan yang luar biasa. Belakangan ini saya juga mulai Nand2Tetris, dan ingin menyelesaikan Bagian 1, yaitu bagian perangkat keras dari kursus itu, dalam beberapa bulan ke depan
    Saya menuliskan progresnya di blog ini: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • Bohong. Kamu memakai gerbang NAND dan clock, kan

    • Clock itu juga bisa dibuat dengan ring oscillator, dan ring oscillator bisa disusun dari jumlah ganjil gerbang NAND yang dihubungkan seperti gerbang NOT

  • Karya yang keren. Saya sudah menandainya untuk dibaca lebih dalam nanti
    Saya suka NAND-to-Tetris, tetapi belum pernah menyelesaikannya sampai akhir, jadi saya menantikan untuk menjelajahi proyek ini

  • Penasaran, total jumlah gerbang NAND-nya berapa?

    • Saya melihat kodenya cukup detail, dan gerbang NAND digunakan 3.234 kali setiap siklus clock :)