Show HN: NAND kapılarıyla yapılmış programlanabilir bir bilgisayar

 (github.com/ArhanChaudhary)
2 puan yazan GN⁺ 2024-04-27 | 1 yorum | WhatsApp'ta paylaş
  • NAND, yalnızca clock ve NAND gate'lerden oluştuğu eğitimsel öncülüne dayanan, web üzerinde emüle edilen Turing-dengi 16-bit bir bilgisayardır ve CPU'dan IDE ile UI'a kadar her şeyi içerir
  • Kendi yığını Jack-VM-Hack platformu temel alınarak oluşturulmuştur; CPU, makine dili, assembly, assembler, VM dili, VM translator, Jack dili ve compiler'ı birlikte sunar
  • Örnek programlar arasında Average, Pong, 2048'in yanı sıra stack overflow ve stack smashing kullanan VM escape demosu ile basit makine öğrenimi kullanan GeneticAlgorithm da bulunur
  • Jack, Java sözdizimine benzeyen zayıf tipli nesne yönelimli bir dil olsa da, iç yapıda yalnızca signed 16-bit integer'a dayanır; operatör önceliğinin olmaması, manuel bellek yönetimi ve tanımsız davranış gibi büyük kısıtlar içerir
  • Proje, tüm hesaplamaların gerçekten fiziksel NAND gate'lerde çalıştığı anlamına gelmez; TypeScript compiler ve VM translator, Rust tabanlı NAND gate mantık simülatörü ve WebAssembly kullanan eğitimsel ve kuramsal bir uygulamadır

NAND'in sunduğu tam bilgisayar yığını

  • NAND, Not A Nand-powered Device kısaltmasıyla tanıtılan, web tabanlı 16-bit bir bilgisayardır
  • Clock ve NAND gate'lerle yapılmış Turing-dengi bir bilgisayarı emüle eder ve aşağıdaki bileşenleri kendi içinde barındırır
    • CPU
    • machine code language
    • assembly language
    • assembler
    • virtual machine language
    • virtual machine translator
    • programming language
    • compiler
    • IDE
    • user interface
  • Temeli, Nand to Tetris course ve ilgili kitaplardaki Jack-VM-Hack platformudur
  • NAND demo videosu sunulmaktadır

Örnek programlar ve demolar

  • Average

    • Sayı girişi ve ortalama hesaplama yapan basit bir program
    • control flow, aritmetik işlemler, I/O ve dinamik bellek tahsisini gösterir
    • Nand to Tetris software suite ile sağlanan bir programdır

  • Pong

    • Nesne yönelimli modeli gösteren bir Pong oyunu
    • Yön tuşlarıyla paddle'ı sağa ve sola hareket ettirip topu sektirirsiniz
    • Top her sektiğinde paddle küçülür ve top ekranın altına değdiğinde oyun biter
    • Nand to Tetris software suite ile sağlanan bir programdır

  • 2048

    • Recursion ve karmaşık application logic'i gösteren bir 2048 oyunu
    • 4x4 grid üzerinde yön tuşlarıyla sayılar hareket ettirilir ve aynı sayılar birleşir
    • 2048 tile'ına ulaşıldığında kazanılır, ancak kaybedene kadar oynamaya devam edilebilir

  • Overflow

    • Sonsuz recursion ile bilerek stack overflow oluşturup virtual machine escape gerçekleştirir
    • Runtime'da stack overflow'u önleyen bir kontrol olmamasından yararlanır
    • Stack pointer değeri 2048'i aşınca stack, amaçlanan bellek alanını terk ederek heap memory space'e taşar
    • Boş RAM üzerinde çalıştırılırsa, program counter'ı 0'a ayarlayan instruction nedeniyle program ortada resetlenebilir
    • GeneticAlgorithm çalıştırıldıktan hemen sonra yürütülürse, üzerine yazılmamış önceki RAM memory'si okunabilir

  • SecretPassword

    • Runtime'ın stack smashing'i engellememesinden yararlanarak normalde erişilemeyen bir fonksiyonu çağırır
    • Kullanıcı, RAM'deki bir memory address'i istediği bir değerle ezebilir
    • Stack frame'in return address'i başka bir fonksiyonun adresiyle ezilirse, program içindeki rastgele kodların çalıştırılması mümkün olur
    • Örnek değerler memory location 267 ve overwrite value 1743 şeklindedir
    • Aynı tür zafiyet C'deki buffer overflow'da da bulunur

  • GeneticAlgorithm

    • Basit makine öğrenimi kullanan bir creature simulation'dır
    • Her dot, acceleration vector'lerden oluşan kendi “brain”ine sahiptir ve doğal seçilim yoluyla goal'e ulaşacak şekilde evrimleşir
    • Goal'e daha yakın bir konumda ölen dot'ların bir sonraki neslin parent'ı olarak seçilme olasılığı daha yüksektir
    • Reproduction sürecinde brain'in bazı bölümleri mutation geçirerek doğal evrimi simüle eder
    • Genetic Algorithm demo videosu sunulmaktadır

GeneticAlgorithm'ın karşılaştığı donanım kısıtları

  • GeneticAlgorithm, NAND'in çeşitli bileşenleri arasında geliştirilmesi en uzun süren tek programdır
  • Performans nedeniyle, dot'ların evrimde kullandığı tek unsur ölürken goal'e ne kadar yakın olduklarıdır; doğal seçilim algoritmasının entropy'si düşüktür
  • Bellek kullanımı nedeniyle dot sayısı ve brain boyutu üzerinde tatmin edici olmayan sınırlamalar vardır
  • Teknik karmaşıklık nedeniyle, simulation sırasında obstacle'lar yeniden yerleştirilse bile dot'ların brain'inin goal'e ulaşacak kadar büyük olacağı garanti edilemez
    • Brain size yalnızca program başlangıcında belirlenir
  • Uygulama, çeşitli optimizasyonlarla NAND'in kısıtlarını aşar
    • ROM instruction memory space sınırlıdır; kod çok fazla olursa compile edilemez
    • Nihai GeneticAlgorithm, instruction memory space'in %99,2'sini kullanır
    • RAM memory space sınırlıdır; bu yüzden heap memory usage optimize edilmelidir
    • Nesiller arasında ekranın statik biçimde dolu görünmesinin nedeni, screen memory space'in sonraki nesil için temporary swap memory olarak kullanılmasıdır
    • NAND'de floating point type yoktur ve temsil edilebilen integer aralığı -32768 ile 32767 arasındadır
    • Fitness hesaplamasının hassasiyeti düşer ve integer overflow da hesaba katılmalıdır
  • İlgili optimizasyonlar ve ek içgörüler GeneticAlgorithm codebase içinde belgelenmiştir

Jack ile NAND programlama

  • Jack’te programın çalışmamasının en önemli nedenlerinden biri olarak operatör önceliğinin olmaması vurgulanıyor
    • 4 * 2 + 3, (4 * 2) + 3 şeklinde yazılmalı
    • if (~x & y), if ((~x) & y) şeklinde yazılmalı
    • Parantez içermeyen belirsiz expression’ların evaluation value’su undefined’dır
  • Jack, NAND’ın weakly typed object-oriented programming language’idir
    • Açıklamaya göre “Java syntax’ına sahip C”ye daha yakındır
    • NAND kendi complete tech stack’ine sahip olduğu için yalnızca Jack ile programlanabilir
  • Varsayılan Jack OS, compile sırasında programla birlikte bundle edilir
    • string, memory ve hardware ile interface sağlar
    • Keyboard.readLine, Keyboard.readInt, Output.printString, Output.println gibi function’ları içerir
  • Jack, üç primitive type destekler: int, char, boolean
    • class aracılığıyla abstract data type tanımlanabilir
    • field variable’ları, instance bazında attribute tanımlar
    • field variable’ları private scope’a sahiptir; dış erişim için method gerekir
  • function ve method farklı şekillerde çağrılır
    • Mevcut object’in method’u aynı class içinde do g(); gibi çağrılabilir
    • function call’da başa class name eklenmelidir
    • object method’u do b.q(); gibi object üzerinden çağrılır

Jack’in zayıf tiplemesi ve bellek yönetimi

  • Jack, Java’dan farklı olarak strong type, down casting, polymorphism ve inheritance desteklemez
  • İçeride gerçekte yalnızca tek bir type vardır: signed 16-bit integer
    • compiler, assignment ve operation’larda type’ların karışmasına aldırmaz
    • char içine 65 atanırsa 'A' ile eşdeğer kabul edilebilir
    • Array değişkenine 5000 atanıp a[100] = 77 çalıştırılırsa RAM[5100] = 77 olur
    • array entry’leri farklı data type’ları barındırabilir
    • bellek yerleşimi uyuyorsa Array, başka bir class instance’ı gibi kullanılabilir
  • Jack, manuel bellek yönetimi kullanan bir dildir
    • Artık gerekmeyen memory deallocate edilmezse memory leak oluşur
    • heap overflow, ERR6 olarak görünür
    • Jack OS, array ve string’leri stack’te değil heap’te saklar
  • Object’i temsil eden class’ların dispose method’una sahip olması best practice kabul edilir
    • Önce field variable’larının dispose method’u çağrılır
    • En sonda do Memory.deAlloc(this); ile object instance’ının kendisi deallocate edilir
  • String literal’ları tekrar tekrar üretip yazdıran döngüler heap overflow oluşturabilir
    • Her iterasyonda string dispose edilebilir
    • veya string bir kez allocate edilip yeniden kullanılırsa sürekli yazdırma yapılabilir

Tanımsız davranışlar ve dikkat edilmesi gerekenler

  • Karşılaştırma operatörleri

    • a > b ve a < b her zaman matematiksel olarak doğru değildir
    • VM implementasyonu a > b ifadesini a - b > 0 biçimine dönüştürür
    • a - b overflow yapabileceği için 20000 > -20000, false olur
    • a ile b arasındaki mutlak fark 32767’den büyükse > ve < yanlış sonuç verebilir
    • Bu davranış, Nand to Tetris ile compatibility nedeniyle düzeltilmemiştir

  • -32768

    • -32768, -(-32768) = -32768 olan tek değerdir
    • pozitif karşılığı olmadığı için unsoundness ve logic error üretebilir
    • Output.printInt, içerde Math.abs’in positive number döndüreceğini varsayar; ancak -32768 için bu gerçekleşmediğinden Jack OS hatalı çalışır

  • Çok az argümanla function çağrısı

    • Parameter alan bir function, argümansız çağrılırsa undefined behavior oluşabilir
    • Tersine, çok fazla argümanla yapılan function call geçerlidir ve extra argument’ler arguments keyword’ü ile indexlenebilir
    • argument count indicator yoktur

  • Uygunsuz type casting

    • Array kullanılarak variable’lar başka bir type’a cast edilebilir
    • cast edilmiş variable üzerinde var olmayan bir instance method çağrılırsa bu undefined behavior’dır
    • compiler bunu fark edecek kadar smart değildir

  • Stack frame ve internal register değiştirme

    • 256~2047 memory address aralığındaki stack frame’ler veya 1~15 aralığındaki internal register’lar değiştirilirse undefined behavior oluşabilir
    • Bunun, genelde Memory.poke yanlış kullanımı veya negative array indexing olmadan zor olduğu belirtiliyor

  • Kullanıcı VM dosyası yükleme

    • NAND, .jack file’ları için program validation sağlasa da .vm file’ları için sağlamaz
    • .vm file’larında nonexistent function çağrıları, unassigned variable referansları ve mantıksal olarak invalid memory operation’ları yapılabilir
    • Çoğu durumda virtual machine escape meydana gelir ve ekranda hiçbir şey görünmeyebilir

Donanım özellikleri ve bellek yerleşimi

  • NAND’ın RAM’i 32.768 word’den oluşur ve her word bir 16-bit binary number tutar
  • Hardware, screen için 8.192 memory address ayırır
    • Her address’teki her bit, 512x256 ekranın karşılık gelen pixel’ine lineer olarak map edilir
    • bit numaralandırması LSb 0 yöntemini kullanır
  • Keyboard, 24576 memory address’ine map edilmiştir
    • O anda basılı olan key bu konuma yansıtılır
    • user input’u doğrudan bu address üzerinden işlemek yerine Jack OS’in Keyboard class’ını kullanmak önerilir
  • Keyboard, ASCII character’ları ve special key’leri tanır
    • 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, static class variable’ları için 240 memory address, global stack için ise 1.792 memory address ayırır
    • Derin recursion yapılmadıkça bu sınırın genelde sorun yaratmadığı belirtiliyor

Jack OS'un ötesine geçip kendi OS'ini implement etmek

  • Temelde Jack OS, derleme sırasında programla birlikte paketlenir ve string, bellek, donanım arayüzü sağlar
  • Özel bir donanım arayüzüne sahip kendi OS implementasyonunuzu sağlayabilirsiniz
    • IDE, Jack OS dosyasını normal program dosyasıyla aynı şekilde ele alır
    • OS dosyası da silinebilir veya üzerine yazılabilir
  • Kendi OS'inizi kullansanız bile derleme için mutlaka implemente etmeniz gereken çekirdek fonksiyonlar vardır
    • Sys.init: Main.main değil, VM implementasyonuna hardcoded edilmiş gerçek giriş noktasıdır
    • Memory.alloc: class constructor'larının nesne oluştururken dahili olarak kullandığı heap bellek ayırıcısıdır
    • String.newWithStr: string literal'lar için dahili constructor'dır
    • Math.multiply: Jack ifadesi x * y yerine dahili olarak çağrılır
    • Math.divide: Jack ifadesi x / y yerine dahili olarak çağrılır
  • Sağlanan Jack OS'teki Sys.init, belleği, matematik modülünü, ekranı ve output'u başlattıktan sonra Main.main() çağırır ve Sys.halt() çağırır

NAND'in iç çalışma şekli

  • NAND computer, Harvard architecture kullanır
    • Komut belleği olan ROM ile veri belleği olan RAM ayrıdır
    • CPU bu ikisinin birlikte çalışmasını sağlar
  • CPU bir accumulator machine'dir
    • Kontrol akışında built-in register'lara büyük ölçüde bağımlıdır
    • Buradaki accumulator, D register'ıdır
  • CPU instruction set'inde yalnızca iki opcode vardır
    • instruction set görece basittir ama zengin işlevler sunar
    • ALU, tek bir instruction içinde hesaplanabilecek expression'larla tanımlanır
  • compiler ve virtual machine, NAND'e özgü kavramlar olmadığından kısaca ele alınır
    • Bazı tuhaf syntax özellikleri, compiler implementasyonunu kolaylaştırmanın sonucudur
    • compiler, LL(1) grammar üzerinde çalışan bir recursive descent parser'dır
    • compiler VM code üretir ve VM, simple stack machine olarak kullanılır
    • Her VM instruction'ı assembly ve machine code'a mapping edilir
  • Implementasyon koduna core ve compiler implementation içinde bakılabilir

Jack dili ve OS Reference'ın özü

  • Jack programı, bir class collection'ından oluşur
    • class'lar ayrı dosyalarda tanımlanır
    • Bir veya daha fazla class gerekir ve bunlardan biri Main olmalıdır
    • Jack OS'e göre giriş noktası, Main class'ının main function'ıdır
  • class'lar field, static, constructor, method, function bildirimleri içerebilir
    • field ve static declaration'larının sırası arbitrary'dir
    • subroutine declaration'larının sırası da arbitrary'dir
    • type, void, int, boolean, char veya bir class name olabilir
  • syntax özellikleri
    • whitespace ve comment'ler ignored edilir
    • & ve | bitwise operator'leridir ve short-circuit yapmaz
    • true, false, null sırasıyla -1, 0, 0 değerleridir
    • string constant'lar newline ya da quotation mark'ı doğrudan içeremez ve escape de desteklenmez
    • quotation mark ve newline, OS içindeki String.doubleQuote() ve String.newLine() ile sağlanır
    • identifier'lar case-sensitive'dir
  • Jack OS'in başlıca class'ları
    • Array: array oluşturma ve dispose
    • Keyboard: tuş basımı, karakter, satır, integer girişi
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: metin ekranına çıktı ve imleç hareketi
    • Screen: pixel, line, rectangle, circle çizimi
    • String: string oluşturma, dispose, karakter erişimi, append, integer dönüşümü
    • Sys: halt, error, wait
  • invalid state, "ERR[N]" biçiminde bir error code gösterir ve program execution'ı sonlandırır
    • ERR3: sıfıra bölme
    • ERR6: heap taşması
    • ERR15, ERR16: string index sınır dışında
    • ERR17: string dolu
    • ERR20: geçersiz imleç konumu

Gerçekten yalnızca NAND gate'lerinden oluşan bir proje değil

  • FAQ, “everything made from NAND gates” açıklaması ve başlığının misleading olduğunu ama good faith ile yazıldığını kabul ediyor
  • compiler ve virtual machine translator TypeScript ile yazılmış
  • emulated kernel ve emulated hardware, gerçek bir bilgisayarın çalışma biçimini birebir temsil etmiyor
  • Gerçek NAND gate logic simulator Rust ile yazılmış ve tüm codebase'in yalnızca küçük bir bölümünü oluşturuyor
    • Rust kodu, tarayıcıda çalışması için WebAssembly'e derleniyor
    • Bu nedenle tüm computation'ın NAND gate'lerinde çalıştığı varsayımının fiilen ortadan kalktığı belirtiliyor
  • NAND, educational and theoretical bir proje işlevi görüyor
    • Teoride aynı CPU logic'i, emulated hardware'in gerçek dünyadaki bir karşılığında da çalışabilir
    • nand2tetris tabanlı FPGA hardware project örneği olarak https://gitlab.com/x653/nand2tetris-fpga/ veriliyor

Implementasyon kapsamı ve IDE sınırlamaları

  • NAND, Nand to Tetris course ve ilgili kitabın specification'ını takip ediyor
  • Geliştirici CPU, assembler, virtual machine translator ve compiler specification'ını bizzat implemente etmiş; platformu web'e taşırken kendi IDE ve UI'ını eklemiş
  • Jack'te type belirtme zorunluluğunun nedeni, compiler'ın bir instance method'un hangi class'a ait olduğunu belirlemesidir
    • String type'ı olarak tanımlanan s için s.appendChar(33), derleme sırasında String.appendChar(s, 33) biçimine dönüştürülür
  • IDE, implementasyonu basit tutmak için user experience'tan ödün veriyor
    • syntax highlighting için contenteditable ve cursor positioning logic kullanılıyor
    • Sonuç olarak yavaş, gözle görülür biçimde buggy ve yaygın keybind'ler çalışmıyor
  • Kodu derleyip çalıştırmak için “Start” düğmesine basmak yeterli
    • OS, genellikle bellek başlatma ve servis kurulumunu 1 saniyeden biraz kısa sürede tamamlıyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-04-27
Hacker News yorumları

  • Harika bir yan proje ve README de gerçekten çok iyi. Ben Eater'ın 6502 Computer'ıyla (https://eater.net/) biraz uğraştıktan sonra Nand to Tetris'i takip etmeyi düşünüyordum.

    • Fiziksel bir NAND-to-Tetris bilgisayarı yapmak da mümkün mü? Yoksa bu tamamen sanal ortamda yapılan bir alıştırma mı?

  • Sadece bu materyalle birkaç üniversite dersi çıkarılabilir. İyi hazırlanmış bir kaynak.

    • Bu bildiğimiz Nand2Tetris değil mi? O dersi almıştım; ilk bakışta Jack dili de dahil aynı görünüyor.

  • Gerçekten çok iyi yapılmış. Çoğu programcının kariyeri boyunca görmediği soyutlama katmanlarını bizzat deneyimlemiş oluyor.

  • Harika iş. NAND to Tetris, üniversiteden mezun olduktan sonraki ilk işimi almama yardımcı olmuştu.

    • Nasıl yardımcı olduğunu merak ettim.

  • 1990'ların başında UC Berkeley'deki bilgisayar donanımı yeterlilik sınavında buna benzer bir tasarım temel soruydu.
    Daha özel olarak, yalnızca NAND kapılarıyla sıfırdan mikrokod tabanlı boru hatlı bir RISC işlemci tasarlama sorusuydu; gerçekten inşa etmek gerekmiyordu ama kâğıt üzerinde ayrıntılı bir tasarım teslim etmek gerekiyordu.

  • Gerçekten muazzam bir çalışma. Nand2Tetris dersini alırken ben de benzer bir sanal uygulama yapmayı istemiştim.
    Bunu gerçekten başarmış olması etkileyici; artık bilgisayarların nasıl çalıştığını gerçekten çok iyi anlıyor olmalı.

    • Ben de bu sabah temel parçaları SVG ile modelleme konusunda benzer bir fikir düşünüyordum.
      Ama birinin, benim hayal ettiğimden bir basamak daha etkileyici bir işi çoktan yapmış olmasına şaşırdım.

  • Harika çalışma. Ben de yakın zamanda Nand2Tetris'e başladım ve önümüzdeki birkaç ay içinde dersin donanım kısmı olan 1. bölümü bitirmek istiyorum.
    İlerlememi burada blogda yazdım: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • Yalan. NAND kapıları ve saat sinyali kullanmışsın.

    • O saat sinyali de halka osilatör ile yapılabilir; halka osilatör de NAND kapılarını NOT kapısı gibi bağlayıp tek sayıda kullanarak oluşturulur.

  • Harika iş. Daha sonra derinlemesine bakmak için yer imlerine ekledim.
    NAND-to-Tetris'i seviyorum ama sonuna kadar tamamlayamamıştım; bu projeyi incelemeyi sabırsızlıkla bekliyorum.

  • Merak ettim, toplam NAND kapısı sayısı kaç?

    • Kodu ayrıntılı inceledim; her saat döngüsünde NAND kapısı 3.234 kez kullanılıyor :)