Show HN: Komputer yang dapat diprogram dan dibuat dari gerbang NAND

NAND: komputer 16-bit lengkap yang setara Turing dan diimplementasikan di web

• NAND adalah komputer 16-bit setara Turing yang diemulasikan di web hanya dengan gerbang NAND dan clock
• NAND memiliki CPU, bahasa mesin, assembly, assembler, bahasa VM, VM translator, bahasa pemrograman, compiler, IDE, dan UI miliknya sendiri
• NAND berbasis pada platform Jack-VM-Hack yang dijelaskan dalam kursus Nand to Tetris dan buku terkait

Contoh program

Average

• Program sederhana yang menerima angka lalu menghitung rata-ratanya
• Menunjukkan alur kontrol, operasi aritmetika, I/O, dan alokasi memori dinamis

Pong

• Game Pong yang menunjukkan model berorientasi objek dari bahasanya
• Gerakkan paddle ke kiri dan kanan dengan tombol panah untuk memantulkan bola
• Setiap kali bola terpantul, paddle mengecil, dan game berakhir saat bola jatuh ke bawah layar

2048

• Game 2048 yang menunjukkan rekursi dan logika aplikasi yang kompleks
• Pindahkan angka di grid 4x4 dengan tombol panah
• Angka yang sama akan bergabung saat saling bertemu
• Mencapai tile 2048 berarti menang, tetapi Anda bisa terus mengumpulkan angka lebih besar
• Game berakhir saat papan penuh dan tidak ada lagi langkah yang bisa dilakukan

Overflow

• Program yang sengaja memicu stack overflow lewat rekursi tak terbatas untuk keluar dari virtual machine
• Memanfaatkan tidak adanya pemeriksaan runtime untuk mencegah stack overflow
• Saat dijalankan, program terus mencetak nilai stack pointer
• Ketika stack mencapai akhir ruang memori yang dimaksud lalu masuk ke heap memory, perintah print mulai rusak secara eksplosif

SecretPassword

• Program yang memanfaatkan fakta bahwa runtime tidak mencegah stack smashing untuk memanggil fungsi yang seharusnya tidak bisa diakses
• Harus memahami layout stack frame NAND
• Mengizinkan pengguna menimpa alamat memori arbitrer dengan nilai arbitrer
• Jika alamat return suatu fungsi ditimpa dengan alamat fungsi lain, kode arbitrer bisa dieksekusi
• Dengan memasukkan lokasi memori tertentu dan nilai penimpaan yang didapat dari pemeriksaan manual alamat stack dan assembler, Anda bisa melihat ide ini bekerja

GeneticAlgorithm

• Salah satu dari banyak komponen NAND yang paling lama dikembangkan
• Simulasi makhluk hidup yang menggunakan machine learning sederhana
• "Otak" tiap titik adalah vektor percepatan, dan berevolusi menuju target melalui seleksi alam
• Di setiap generasi, titik yang "mati" lebih dekat ke target memiliki peluang lebih besar dipilih sebagai induk generasi berikutnya
• Reproduksi memutasi otak, sehingga evolusi alami dapat disimulasikan secara efektif
• Karena keterbatasan performa, banyak teknik optimisasi digunakan untuk mengakali batasan perangkat keras dan membuat ini memungkinkan

Memrogram dengan Jack

• Hal terpenting saat memrogram dengan Jack adalah tidak adanya prioritas operator. Ini bisa menjadi alasan program Anda tidak berjalan dengan benar.
• Prioritas harus dinyatakan dengan tanda kurung, seperti 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

Pengantar Jack

• NAND membanggakan seluruh tech stack buatannya sendiri
• Jack adalah bahasa berorientasi objek bertipe lemah. Sederhananya, C dengan sintaks Java
• Mari pelajari lewat sebuah contoh

Tipe data kustom

• Jack mendukung tiga tipe dasar: int, char, boolean
• Sesuai kebutuhan, ini bisa diperluas menjadi tipe data abstrak
• Pengetahuan pemrograman berorientasi objek bisa langsung diterapkan
• Dalam contoh, kelas Point mendefinisikan titik dalam ruang abstrak
• Variabel field mendeklarasikan properti per-instans dari tipe data tersebut
• Fungsi method publik untuk memanipulasi titik disediakan agar pemanggil bisa menjumlahkan titik atau menghitung jarak antara dua titik
• Semua variabel field bersifat privat secara cakupan. Untuk mengaksesnya, harus disediakan lewat fungsi method
• Sudah menjadi kebiasaan bagi data class untuk mendefinisikan method dispose
• Lihat sintaks pemanggilan function dan method

Konversi tipe lemah

• Memang Jack banyak terinspirasi dari Java, tetapi itu hanya fasad sederhana
• Java adalah bahasa dengan tipe kuat dan mendukung fitur tipe kompleks seperti downcasting, polimorfisme, dan pewarisan
• Sebaliknya, Jack pada praktiknya hanya mendukung satu jenis data: signed 16-bit integer
• Itulah alasan utama Jack bertipe lemah
• Karena itu compiler Jack tidak mempermasalahkan pencampuran tipe berbeda dalam assignment dan operasi
• Jack tetap menyediakan model berorientasi objek yang kuat dan fungsional
• Ini akan membantu memahami kapan dan bagaimana konversi tipe perlu dilakukan

Manajemen memori manual

• Jack adalah bahasa yang mengelola memori secara manual
• Anda harus berhati-hati membebaskan memori yang tidak lagi diperlukan dengan benar
• Jika tidak, Jack OS akan menganggap ada memory leak
• Praktik terbaiknya adalah menulis method dispose untuk tiap kelas agar alokasi dan dealokasi terenkapsulasi dengan baik
• Dengan memanggil method ini saat objek tidak lagi dibutuhkan, Anda bisa mencegah heap memory habis
• Jika pernah memakai bahasa lain dengan manajemen memori manual seperti C, ini akan terasa familier
• Bedanya, Jack OS menyimpan array dan string di heap, bukan di stack
• Lihat String.dispose untuk memahami cara menulis method dispose

Perilaku tak terdefinisi

Prioritas operator

• Ini sangat penting sehingga dipindahkan ke depan

Operator lebih kecil atau lebih besar

• Ekspresi perbandingan Jack a > b, a < b tampak sederhana, tetapi secara matematis tidak selalu benar
• Virtual machine mengubahnya menjadi a - b > 0. Masalahnya, a - b bisa overflow
• Bagaimana 20000 > -20000 dievaluasi? 20000 - (-20000) > 0, yaitu -25336 > 0, sehingga hasilnya false
• Tetapi 20000 > -10000 menjadi 30000 > 0, yaitu true
• Jika selisih nilai absolut a dan b lebih besar dari 32767, maka a > b dan a < b menjadi salah. Jika tidak, aman
• Ini bukan bug, melainkan ketidakcocokan dengan Nand to Tetris. Demi kompatibilitas, perilaku ini tidak akan diperbaiki

-32768

• -32768 adalah satu-satunya angka dengan sifat unik -(-32768) = -32768. Ia adalah singleton tanpa pasangan positif
• Hal ini dapat menyebabkan kesalahan logika yang tidak valid
• Karena -x secara internal diproses sebagai ~(x-1)
• Jika x diberi nilai -32768, maka x-1 = ~x terpenuhi. ~(~x) menjadi sama dengan x
• Apa yang terjadi? Karena NAND adalah mesin 16-bit, mengurangi 1 dari -32768 menghasilkan pembalikan bit-bitnya
• Yang penting adalah menangani kesalahan logika pada pemrosesan operator negatif
• Memeriksa kasus -32768 dan menanganinya dengan benar adalah tanggung jawab programmer

Pemanggilan fungsi dengan argumen kurang

• Perilaku tak terdefinisi yang jelas dan tidak perlu penjelasan

Type casting yang tidak tepat

• Dengan Array, variabel bisa di-cast ke tipe apa pun
• Memanggil instance method yang tidak ada akan menimbulkan perilaku tak terdefinisi
• Compiler tidak cukup pintar untuk mendeteksinya

Stack overflow

• Lihat program Overflow

Mengubah stack frame atau register internal

• Mengubah stack frame atau register internal pada alamat 256~2047 dan 1~15 dapat menyebabkan perilaku tak terdefinisi
• Biasanya ini tidak mungkin kecuali Anda menyalahgunakan Memory.poke atau indeks array negatif
• Lihat program SecretPassword

Spesifikasi perangkat keras

• Ada alasan mengapa komputasi 16-bit ditinggalkan sejak tahun 1970-an

• Dibandingkan 32-bit atau 64-bit, kemampuan pemrosesan dan kapasitas memorinya terbatas sehingga tidak dapat memenuhi kebutuhan perangkat lunak modern

• NAND juga tidak terkecuali

• Dibandingkan MacBook 16GiB, NAND hanya memiliki RAM 4KiB. Itu cuma 0.00002%

• Meski begitu, itu tetap cukup untuk membawa kita ke bulan

• Jack OS mencadangkan 14.336 alamat memori dari total 4KiB untuk heap. Jumlah yang sangat kecil

• Karena itu sangat penting bagi aplikasi Jack untuk membebaskan memori secara efisien

• Jika rencananya terlalu ambisius, heap memory bisa habis dan Anda mungkin harus menulis ulang total tipe data serta logika

• Dari 4KiB tersebut, 8.192 alamat memori dicadangkan untuk layar

• Setiap bit pada tiap alamat dipetakan secara linear ke piksel layar 512x256. Menggunakan penomoran bit LSb 0

• Alamat memori 24.576 dicadangkan untuk keyboard

• Nilai kode ASCII dari tombol yang ditekan akan tercermin di sana

• Namun, untuk menangani input pengguna, Anda tidak boleh mengaksesnya secara langsung. Gunakan kelas Keyboard dan fungsi terkait yang disediakan Jack OS

• Keyboard NAND mengenali ASCII dan tombol khusus

• Sebanyak 240 alamat memori dicadangkan untuk variabel kelas statis, dan 1.792 untuk stack global

• Selama tidak melakukan rekursi yang sangat dalam, batas ini seharusnya tidak menjadi masalah

[GN⁺]

Komentar Hacker News

• Melalui proyek Nand to Tetris, kita bisa memahami level abstraksi komputer secara mendalam
• Kit komputer 6502 dari Ben Eater juga memiliki nilai edukatif yang serupa
• Proyek ini memiliki materi yang tertata sangat baik, sampai-sampai bisa dijadikan beberapa mata kuliah universitas
• Pada ujian kualifikasi perangkat keras komputer UC Berkeley di awal 1990-an, ada soal serupa yang meminta perancangan prosesor RISC bermikrokode dan berpipelining hanya dengan gerbang NAND
  • Saat itu, pembuatan nyata tidak diwajibkan; cukup menuliskan desain rinci di atas kertas
• Proyek ini tampak mirip dengan MarquisdeGeek/gates
• Saat mengikuti kursus Nand2Tetris, saya ingin membuat sesuatu yang mirip secara virtual, dan implementasi nyata ini sangat mengesankan
  • Melalui ini, pemahaman tentang prinsip kerja komputer pasti meningkat pesat
• Ada yang menyoroti bahwa selain gerbang NAND, proyek ini juga menggunakan clock
• Saya memang belum menuntaskan Nand2Tetris, tetapi sebagai penggemar saya ingin melihat proyek ini lebih dalam
• Saya penasaran berapa total gerbang NAND yang digunakan
• Terima kasih atas pendekatan yang setia pada prinsip-prinsip dasar