Show HN: Ein programmierbarer Computer aus NAND-Gattern

NAND: Ein vollständig Turing-äquivalenter 16-Bit-Computer, im Web umgesetzt

• NAND ist ein im Web emulierter Turing-äquivalenter 16-Bit-Computer, der nur aus NAND-Gattern und einem Takt besteht
• NAND verfügt über eine eigene CPU, Maschinensprache, Assemblersprache, einen Assembler, eine VM-Sprache, einen VM-Translator, eine Programmiersprache, einen Compiler, eine IDE und eine UI
• NAND basiert auf der Jack-VM-Hack-Plattform, wie sie im Kurs Nand to Tetris und im zugehörigen Buch beschrieben wird

Beispielprogramme

Average

• Ein einfaches Programm, das Zahlen entgegennimmt und ihren Durchschnitt berechnet
• Zeigt Kontrollfluss, arithmetische Operationen, I/O und dynamische Speicherzuweisung

Pong

• Das Spiel Pong demonstriert das objektorientierte Modell der Sprache
• Mit den Pfeiltasten wird das Paddle nach links und rechts bewegt, um den Ball zurückzuschlagen
• Nach jedem erfolgreichen Abprallen wird das Paddle kleiner; fällt der Ball unter den Bildschirmrand, ist das Spiel vorbei

2048

• Das Spiel 2048 demonstriert Rekursion und komplexe Anwendungslogik
• Mit den Pfeiltasten werden Zahlen in einem 4x4-Raster bewegt
• Gleiche Zahlen werden beim Zusammenstoßen zusammengeführt
• Wer den 2048-Stein erreicht, gewinnt, kann aber weiterspielen und noch mehr sammeln
• Ist das Spielfeld voll und kein Zug mehr möglich, ist das Spiel vorbei

Overflow

• Ein Programm, das absichtlich durch unendliche Rekursion einen Stack Overflow auslöst, um aus der virtuellen Maschine auszubrechen
• Es nutzt aus, dass es keine Laufzeitprüfung zur Verhinderung von Stack Overflow gibt
• Während der Ausführung wird fortlaufend der Wert des Stack-Pointers ausgegeben
• Wenn der Stack das Ende des vorgesehenen Speicherbereichs erreicht und in den Heap-Speicher überläuft, gerät die print-Anweisung explosionsartig außer Kontrolle

SecretPassword

• Ein Programm, das eine unzugängliche Funktion aufruft, indem es ausnutzt, dass die Runtime kein Stack Smashing verhindert
• Dafür muss man das Layout der Stack-Frames in NAND verstehen
• Es erlaubt dem Benutzer, einen beliebigen Speicherwert an eine beliebige Speicheradresse zu schreiben
• Überschreibt man die Rücksprungadresse einer Funktion mit der Adresse einer anderen Funktion, kann beliebiger Code ausgeführt werden
• Gibt man eine bestimmte Speicherposition und einen bestimmten Überschreibwert ein, die durch manuelle Prüfung der Stack-Adressen und des Assemblers gewonnen wurden, sieht man diese Idee in Aktion

GeneticAlgorithm

• Einer der vielen NAND-Bestandteile, dessen Entwicklung am längsten gedauert hat
• Eine Biologie-Simulation mit einfachem maschinellem Lernen
• Das „Gehirn“ jedes Punkts besteht aus Beschleunigungsvektoren, die sich durch natürliche Selektion in Richtung des Ziels weiterentwickeln
• In jeder Generation haben „gestorbene“ Punkte, die näher am Ziel liegen, eine höhere Wahrscheinlichkeit, als Eltern der nächsten Generation ausgewählt zu werden
• Die Reproduktion mutiert die Gehirne und simuliert so natürliche Evolution effektiv
• Wegen Performance-Beschränkungen werden viele Optimierungstechniken eingesetzt, um die Hardware-Limits zu umgehen und dies möglich zu machen

Programmieren in Jack

• Beim Programmieren in Jack ist am wichtigsten, dass es keine Operatorpräzedenz gibt. Das kann der Grund sein, warum ein Programm nicht korrekt funktioniert.
• Die Priorität muss also mit Klammern explizit gemacht werden, etwa 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

Einführung in Jack

• NAND präsentiert seinen gesamten eigenen Technologie-Stack
• Jack ist eine schwach typisierte objektorientierte Sprache. Vereinfacht gesagt: C mit Java-Syntax
• Schauen wir uns das an einem Beispiel an

Benutzerdefinierte Datentypen

• Jack unterstützt die drei primitiven Typen int, char und boolean
• Diese können bei Bedarf durch abstrakte Datentypen erweitert werden
• Vorwissen in objektorientierter Programmierung lässt sich direkt anwenden
• Im Beispiel definiert die Klasse Point einen abstrakten Punkt im Raum
• Mit field-Variablen werden instanzspezifische Eigenschaften des Datentyps deklariert
• Öffentliche method-Funktionen zur Manipulation des Punkts erlauben es dem Aufrufer, Punkte zu addieren oder den Abstand zwischen zwei Punkten zu berechnen
• Alle field-Variablen haben privaten Geltungsbereich. Auf sie kann nur über bereitgestellte method-Funktionen zugegriffen werden
• Für Datenklassen ist es üblich, eine dispose-Methode zu definieren
• Siehe die Aufrufsyntax für function- und method-Aufrufe

Schwache Typumwandlung

• Jack ist zwar stark von Java inspiriert, aber nur eine einfache Fassade
• Java ist eine stark typisierte Sprache und unterstützt komplexe Typsystem-Features wie Downcasting, Polymorphie und Vererbung
• Jack unterstützt in Wirklichkeit nur einen einzigen signed 16-bit integer
• Das ist der Hauptgrund, warum Jack schwach typisiert ist
• Deshalb kümmert sich der Jack-Compiler nicht darum, wenn bei Zuweisungen und Operationen verschiedene Typen gemischt werden
• Jack bietet trotzdem ein leistungsfähiges und funktionales objektorientiertes Modell
• Das hilft zu verstehen, wann und wie Typumwandlungen vorgenommen werden sollten

Manuelle Speicherverwaltung

• Jack ist eine Sprache mit manueller Speicherverwaltung
• Man muss darauf achten, Speicher korrekt freizugeben, wenn er nicht mehr benötigt wird
• Andernfalls nimmt das Jack-OS an, dass ein Speicherleck vorliegt
• Bewährte Praxis ist es, für jede Klasse eine dispose-Methode zu schreiben, die die Freigabe sauber kapselt
• Wird diese Methode aufgerufen, sobald das Objekt nicht mehr benötigt wird, lässt sich ein Mangel an Heap-Speicher vermeiden
• Wer schon mit anderen Sprachen mit manueller Speicherverwaltung wie C gearbeitet hat, wird das kennen
• Der Unterschied ist, dass das Jack-OS Arrays und Strings nicht auf dem Stack, sondern im Heap speichert
• In String.dispose kann man sehen, wie eine dispose-Methode geschrieben werden sollte

Undefiniertes Verhalten

Operatorpräzedenz

• So wichtig, dass es weiter nach oben verschoben wurde

Größer-als- und Kleiner-als-Operatoren

• Jacks Vergleichsausdrücke a > b und a < b wirken einfach, sind mathematisch aber nicht immer korrekt
• Die virtuelle Maschine wandelt dies in a - b > 0 um. Dabei kann a - b jedoch überlaufen
• Wie wird 20000 > -20000 ausgewertet? 20000 - (-20000) > 0, also -25336 > 0, ergibt false
• Aber 20000 > -10000 wird zu 30000 > 0, also true
• Wenn sich die Absolutwerte von a und b um mehr als 32767 unterscheiden, sind a > b und a < b falsch. Andernfalls ist alles in Ordnung
• Das ist kein Bug, sondern eine Inkompatibilität mit Nand to Tetris. Aus Kompatibilitätsgründen wird dieses Verhalten nicht geändert

-32768

• -32768 ist die einzige Zahl mit der eigentümlichen Eigenschaft -(-32768) = -32768. Sie ist ein Singleton ohne positives Gegenstück
• Dadurch können scheinbar ungültige Logikfehler entstehen
• Denn -x wird intern als ~(x-1) verarbeitet
• Wenn x den Wert -32768 hat, gilt x-1 = ~x. Dann ist ~(~x) wieder gleich x
• Was ist passiert? Da NAND eine 16-Bit-Maschine ist, führt das Subtrahieren von 1 bei -32768 dazu, dass als Ergebnis die invertierten Bits entstehen
• Wichtig ist, Logikfehler bei der Behandlung des Negationsoperators zu berücksichtigen
• Den Fall -32768 zu prüfen und passend zu behandeln, liegt in der Verantwortung des Programmierers

Funktionsaufrufe mit zu wenigen Argumenten

• Offensichtlich undefiniertes Verhalten, das keiner weiteren Erklärung bedarf

Ungeeignete Type Casts

• Mit Array kann eine Variable in jeden beliebigen Typ gecastet werden
• Der Aufruf einer nicht existierenden Instanzmethode führt zu undefiniertem Verhalten
• Der Compiler ist nicht schlau genug, das zu erkennen

Stack Overflow

• Siehe das Programm Overflow

Verändern von Stack-Frames oder internen Registern

• Das Verändern von Stack-Frames oder internen Registern an den Adressen 256–2047 und 1–15 kann zu undefiniertem Verhalten führen
• Normalerweise ist das nur möglich, wenn Memory.poke oder negative Array-Indizes missbraucht werden
• Siehe das Programm SecretPassword

Hardware-Spezifikationen

• Es gibt einen Grund, warum sich 16-Bit-Computing seit den 1970er-Jahren nicht mehr durchgesetzt hat

• Im Vergleich zu 32 Bit oder 64 Bit sind Rechenleistung und Speicherkapazität begrenzt und genügen den Anforderungen moderner Software nicht

• NAND ist da keine Ausnahme

• Verglichen mit einem MacBook mit 16 GiB hat NAND nur 4 KiB RAM. Das sind gerade einmal 0,00002 %

• Trotzdem reicht es immerhin dafür, uns zum Mond zu bringen

• Das Jack-OS reserviert im 4-KiB-Speicher 14.336 Speicheradressen für den Heap. Eine ungewöhnlich kleine Zahl

• Deshalb ist es äußerst wichtig, dass Jack-Anwendungen Speicher effizient freigeben

• Bei zu ehrgeizigen Vorhaben kann der Heap-Speicher ausgehen, sodass Datentypen und Logik möglicherweise komplett neu geschrieben werden müssen

• Von den 4 KiB sind 8.192 Speicheradressen für den Bildschirm reserviert

• Jedes Bit jeder Adresse wird linear auf Pixel des 512x256-Bildschirms abgebildet. Es wird LSb-0-Bitnummerierung verwendet

• Speicheradresse 24.576 ist für die Tastatur reserviert

• Dort erscheint der ASCII-Code der gedrückten Taste

• Für die Verarbeitung von Benutzereingaben sollte jedoch nicht direkt darauf zugegriffen werden. Stattdessen sollte die vom Jack-OS bereitgestellte Klasse Keyboard mit ihren zugehörigen Funktionen verwendet werden

• Die NAND-Tastatur erkennt ASCII sowie Sondertasten

• Für statische Klassenvariablen sind 240 und für den globalen Stack 1.792 Speicheradressen reserviert

• Solange keine tiefe Rekursion verwendet wird, dürfte diese Begrenzung kein Problem darstellen

[GN⁺]

Hacker-News-Kommentare

• Durch das Nand to Tetris-Projekt kann man die Abstraktionsebenen eines Computers tiefgehend verstehen
• Das 6502-Computerkit von Ben Eater hat ebenfalls einen ähnlichen pädagogischen Wert
• Dieses Projekt ist so gut aufbereitet, dass man daraus mehrere Universitätskurse machen könnte
• In der Qualifikationsprüfung für Computerhardware an der UC Berkeley Anfang der 1990er Jahre gab es in ähnlicher Form eine Aufgabe, bei der man allein mit NAND-Gattern einen mikrocodegesteuerten und gepipelinten RISC-Prozessor entwerfen sollte
  • Damals wurde keine tatsächliche Umsetzung verlangt; es reichte, den detaillierten Entwurf auf Papier auszuarbeiten
• Dieses Projekt scheint MarquisdeGeek/gates ähnlich zu sein
• Während des Nand2Tetris-Kurses wollte ich virtuell etwas Ähnliches bauen, und es ist beeindruckend, dass es hier tatsächlich umgesetzt wurde
  • Dadurch dürfte sich das Verständnis der Funktionsweise von Computern erheblich verbessert haben
• Es gibt den Hinweis, dass neben NAND-Gattern auch ein Takt verwendet wurde
• Ich habe Nand2Tetris zwar nicht abgeschlossen, möchte mir dieses Projekt als Fan aber sehr genau ansehen
• Ich frage mich, wie viele NAND-Gatter insgesamt verwendet wurden
• Danke für diesen Ansatz, der den Grundprinzipien treu bleibt