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

NAND: Web üzerinde uygulanmış, tamamen Turing eşdeğeri 16 bitlik bilgisayar

• NAND, yalnızca NAND kapıları ve saat sinyaliyle web üzerinde emüle edilen, Turing eşdeğeri 16 bitlik bir bilgisayardır
• NAND; kendi CPU’su, makine dili, assembly dili, assembler’ı, VM dili, VM çeviricisi, programlama dili, derleyicisi, IDE’si ve UI’ına sahiptir
• NAND, Nand to Tetris kursunda ve ilgili kitapta tanımlanan Jack-VM-Hack platformunu temel alır

Program örnekleri

Average

• Sayıları alıp ortalamalarını hesaplayan basit bir program
• Kontrol akışı, aritmetik işlemler, I/O ve dinamik bellek ayırmayı gösterir

Pong

• Pong oyunu üzerinden dilin nesne yönelimli modelini gösterir
• Ok tuşlarıyla raketi sağa sola hareket ettirip topu sektirirsiniz
• Her sekişte raket küçülür; top ekranın altına düşerse oyun biter

2048

• 2048 oyunu üzerinden özyineleme ve karmaşık uygulama mantığını gösterir
• Ok tuşlarıyla sayılar 4x4 ızgara üzerinde hareket ettirilir
• Aynı sayılar çarpıştığında birleşir
• 2048 karesine ulaştığınızda kazanırsınız, ancak daha da büyütmeye devam edebilirsiniz
• Tahta dolup artık hareket kalmadığında oyun biter

Overflow

• Sonsuz özyinelemeyle kasıtlı olarak stack overflow oluşturup sanal makineden kaçan bir program
• Stack overflow’u önleyecek çalışma zamanı denetimlerinin olmamasını kullanır
• Çalışırken stack pointer değerini durmadan yazdırır
• Stack, ayrılan bellek alanının sonuna ulaşıp heap belleğe taşınca yazdırma ifadeleri patlayıcı biçimde bozulur

SecretPassword

• Çalışma zamanının stack smashing’i önlememesinden yararlanarak erişilemeyen bir fonksiyonu çağıran program
• NAND’in stack frame düzenini anlamayı gerektirir
• Kullanıcının rastgele bir bellek adresini rastgele bir değerle ezmesine izin verir
• Bir fonksiyonun dönüş adresini başka bir fonksiyonun adresiyle ezerseniz rastgele kod çalıştırabilirsiniz
• Stack adreslerini ve assembler’ı elle inceleyerek elde edilen belirli bellek konumları ile ezilecek değerleri girerseniz bu fikrin çalıştığını görebilirsiniz

GeneticAlgorithm

• NAND’in birçok bileşeni arasında geliştirmesi en uzun süren bölüm
• Basit makine öğrenmesi kullanan bir biyolojik simülasyon
• Her noktanın "beyni" ivme vektörlerinden oluşur ve hedefe doğru doğal seçilimle evrilir
• Her nesilde, hedefe daha yakın "ölen" noktaların bir sonraki neslin ebeveyni olarak seçilme olasılığı daha yüksektir
• Üreme, beyinleri mutasyona uğratarak doğal evrimi etkili biçimde simüle eder
• Performans sınırlamaları nedeniyle donanım kısıtlarını aşmak ve bunu mümkün kılmak için çok sayıda optimizasyon tekniği kullanılır

Jack ile programlama

• Jack ile programlarken en önemli nokta, operatör önceliğinin olmamasıdır. Programınızın beklediğiniz gibi çalışmamasının nedeni bu olabilir.
• 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y) örneklerinde olduğu gibi önceliği parantezle açıkça belirtmelisiniz

Jack’e giriş

• NAND, kendi teknik yığınının tamamını sunar
• Jack, zayıf tipli nesne yönelimli bir dildir. Kısaca, Java sözdizimine sahip C dili gibidir
• Bunu bir örnek üzerinden öğrenelim

Özel veri türleri

• Jack üç temel türü destekler: int, char, boolean
• Bunları gerektiğinde soyut veri türleriyle genişletebilirsiniz
• Nesne yönelimli programlama bilginizi doğrudan uygulayabilirsiniz
• Örnekte, soyut uzaydaki bir noktayı tanımlamak için Point sınıfı kullanılır
• Veri türünün örneğe özgü özellikleri field değişkenleriyle tanımlanır
• Noktayı işlemek için açık method fonksiyonları sunulur; böylece çağıran taraf noktaları toplayabilir veya iki nokta arasındaki mesafeyi hesaplayabilir
• Tüm field değişkenleri özel kapsamlıdır. Bu değişkenlere erişim için method fonksiyonları sağlanmalıdır
• Veri sınıflarında dispose metodunu tanımlamak yerleşik bir gelenektir
• function, method çağrı sözdizimine bakın

Zayıf tip dönüşümü

• Jack’in büyük ölçüde Java’dan ilham aldığını söyledik, ancak bu sadece yüzeysel bir benzerliktir
• Java güçlü tipli bir dildir ve downcasting, çok biçimlilik, kalıtım gibi karmaşık tür özelliklerini destekler
• Buna karşılık Jack gerçekte yalnızca tek bir signed 16-bit integer türünü destekler
• Jack’in zayıf tipli olmasının temel nedeni budur
• Bu yüzden Jack derleyicisi, atama ve işlemlerde farklı türlerin karıştırılmasını pek umursamaz
• Yine de Jack güçlü ve işlevsel bir nesne yönelimli model sunar
• Tür dönüşümünü ne zaman ve nasıl yapmanız gerektiğini anlamanıza yardımcı olur

Elle bellek yönetimi

• Jack, belleğin elle yönetildiği bir dildir
• Artık gerekmeyen belleği uygun şekilde serbest bırakmaya dikkat etmelisiniz
• Aksi halde Jack OS bellek sızıntısı olduğunu varsayar
• En iyi uygulama, her sınıf için ayırma ve serbest bırakmayı düzgün biçimde kapsülleyen bir dispose metodu yazmaktır
• Bir nesneye artık ihtiyaç kalmadığında bu metodu çağırmak, heap belleğin tükenmesini önleyebilir
• C gibi elle bellek yönetimi kullanan başka diller deneyimlediyseniz bu size tanıdık gelecektir
• Fark şudur: Jack OS dizileri ve string’leri stack yerine heap üzerinde saklar
• String.dispose örneğine bakarak dispose metodunun nasıl yazılacağını görebilirsiniz

Tanımsız davranış

Operatör önceliği

• O kadar önemli ki en başa taşındı

Küçüktür ve büyüktür işleçleri

• Jack’teki a > b, a < b karşılaştırmaları basit görünür, ancak matematiksel olarak her zaman doğru değildir
• Sanal makine bunu a - b > 0 biçimine dönüştürür. Ancak a - b overflow üretebilir
• 20000 > -20000 nasıl değerlendirilir? 20000 - (-20000) > 0, yani -25336 > 0 olur ve sonuç false çıkar
• Buna karşın 20000 > -10000, yani 30000 > 0, sonuç olarak true verir
• a ile b arasındaki mutlak fark 32767’den büyükse a > b ve a < b yanlış sonuç verebilir. Değilse sorun yoktur
• Bu bir bug değil, Nand to Tetris ile uyumsuzluktur. Uyumluluk nedeniyle bu davranış düzeltilmeyecektir

-32768

• -32768, -(-32768) = -32768 gibi tuhaf bir özelliğe sahip tek sayıdır. Pozitif karşılığı olmayan tekil bir değerdir
• Bu nedenle geçersiz mantık hataları ortaya çıkabilir
• Çünkü -x dahili olarak ~(x-1) şeklinde işlenir
• x değerine -32768 atarsanız x-1 = ~x eşitliği sağlanır. Böylece ~(~x) yine x olur
• Ne oldu? NAND 16 bitlik bir makine olduğu için -32768’den 1 çıkarıldığında sonuç bitlerin ters çevrilmiş haline denk gelir
• Önemli olan, negatif işleci işlerken mantık hatalarını ele almaktır
• -32768 durumunu kontrol etmek ve uygun şekilde yönetmek programcının sorumluluğundadır

Eksik argümanla fonksiyon çağrısı

• Açıklama gerektirmeyecek kadar bariz bir tanımsız davranış

Uygunsuz tür dönüşümü

• Bir değişkeni Array olarak herhangi bir türe dönüştürebilirsiniz
• Var olmayan örnek metodları çağırmak tanımsız davranışa yol açar
• Derleyici bunu yakalayacak kadar akıllı değildir

Stack overflow

• Overflow programına bakın

Stack frame veya dahili register’ları değiştirme

• Stack frame’i ya da 256~2047 ve 1~15 adreslerindeki dahili register’ları değiştirmek tanımsız davranışa neden olabilir
• Normalde Memory.poke veya negatif dizi indekslerini kötüye kullanmadıkça bu mümkün değildir
• SecretPassword programına bakın

Donanım özellikleri

• 16 bit hesaplamanın 1970’lerden sonra neden geri planda kaldığının bir nedeni var

• 32 bit veya 64 bit sistemlerle karşılaştırıldığında işlem gücü ve bellek kapasitesi sınırlıdır; bu da modern yazılımın gereksinimlerini karşılamasını zorlaştırır

• NAND de bunun istisnası değildir

• 16GiB RAM’li bir MacBook ile karşılaştırıldığında NAND yalnızca 4KiB RAM’e sahiptir. Bu da sadece %0.00002 eder

• Yine de bizi Ay’a götürmeye yetecek kadar gücü vardır

• Jack OS, 4KiB içinde 14.336 bellek adresini heap için ayırır. Bu son derece küçük bir miktardır

• Bu yüzden Jack uygulamalarının belleği verimli biçimde serbest bırakması çok önemlidir

• Planlarınız fazla iddialıysa heap bellek yetmeyebilir ve veri türlerini ile mantığı baştan yazmanız gerekebilir

• 4KiB içinde 8.192 bellek adresi ekran için ayrılmıştır

• Her adresin her biti, 512x256 ekranın piksellerine doğrusal olarak eşlenir. LSb 0 bit numaralandırması kullanılır

• 24.576 numaralı bellek adresi klavye için ayrılmıştır

• Basılan tuşun ASCII kodu bu adrese yansıtılır

• Ancak kullanıcı girdisini işlemek için buna doğrudan erişmemelisiniz. Jack OS’nin sağladığı Keyboard sınıfını ve ilgili fonksiyonları kullanmalısınız

• NAND klavyesi ASCII ve özel tuşları tanır

• Statik sınıf değişkenleri için 240, genel stack için 1.792 bellek adresi ayrılmıştır

• Çok derin özyineleme yapmadığınız sürece bu sınır sorun çıkarmaz

[GN⁺]

Hacker News yorumları

• Nand to Tetris projesi sayesinde bilgisayarın soyutlama seviyelerini derinlemesine anlamak mümkün
• Ben Eater’ın 6502 bilgisayar kiti de benzer bir eğitsel değere sahip
• Bu proje, birden çok üniversite dersi oluşturulabilecek kadar iyi düzenlenmiş materyaller sunuyor
• 1990’ların başında UC Berkeley’nin bilgisayar donanımı yeterlilik sınavında, buna benzer şekilde yalnızca NAND kapılarıyla mikro kodlanmış ve boru hatlı bir RISC işlemci tasarlama sorusu sorulmuştu
  • O dönemde gerçek üretim istenmiyordu; yalnızca ayrıntılı tasarımın kağıt üzerinde hazırlanması yeterliydi
• Bu proje MarquisdeGeek/gates ile benzer görünüyor
• Nand2Tetris sürecini takip ederken buna benzer bir şeyi sanal olarak yapmak istemiştim; bunun gerçekten uygulanmış olması etkileyici
  • Bunun, bilgisayarların çalışma prensiplerine dair anlayışı büyük ölçüde geliştirmiş olması muhtemel
• NAND kapılarının yanı sıra saat sinyalinin de kullanıldığına dikkat çekenler var
• Nand2Tetris’i tamamlayamamış olsam da bir hayranı olarak bu projeye derinlemesine bakmak istiyorum
• Toplam kaç NAND kapısı kullanıldığını merak ediyorum
• Temel ilkelere sadık bu yaklaşım için teşekkür ediliyor