Show HN: Programmierbarer Computer aus NAND-Gattern

 (github.com/ArhanChaudhary)
2 Punkte von GN⁺ 2024-04-27 | 1 Kommentare | Auf WhatsApp teilen
  • NAND ist ein im Web emulierter turingäquivalenter 16-bit-Computer, der auf der didaktischen Prämisse basiert, nur aus clock und NAND gate zu bestehen, und vom CPU bis hin zu IDE und UI alles umfasst
  • Der eigene Stack basiert auf der Jack-VM-Hack-Plattform und bietet zusammen CPU, machine code, assembly, assembler, VM-Sprache, VM translator, Jack-Sprache und compiler
  • Zu den Beispielprogrammen gehören nicht nur Average, Pong und 2048, sondern auch eine VM-escape-Demo mit stack overflow und stack smashing sowie GeneticAlgorithm mit einfachem maschinellem Lernen
  • Jack ist eine schwach typisierte objektorientierte Sprache mit einer Java-ähnlichen Syntax, stützt sich intern jedoch nur auf einen signed 16-bit integer und hat große Einschränkungen wie keine operator precedence, manuelle Speicherverwaltung und undefiniertes Verhalten
  • Das Projekt bedeutet nicht, dass tatsächlich jede Berechnung auf physischen NAND gate ausgeführt wird, sondern ist eine Implementierung für Lehre und Theorie, die einen TypeScript compiler und VM translator, einen NAND-gate-Logiksimulator auf Rust-Basis sowie WebAssembly verwendet

Der vollständige Computer-Stack von NAND

  • NAND wird als webbasierter 16-bit-Computer vorgestellt, dessen Name für Not A Nand-powered Device steht
  • Er emuliert einen turingäquivalenten Computer aus clock und NAND gate und enthält die folgenden Bestandteile direkt selbst
    • CPU
    • machine code language
    • assembly language
    • assembler
    • virtual machine language
    • virtual machine translator
    • programming language
    • compiler
    • IDE
    • user interface
  • Grundlage ist die Jack-VM-Hack-Plattform aus dem Nand to Tetris course und den dazugehörigen Büchern
  • Ein NAND-Demovideo ist verfügbar

Beispielprogramme und Demos

  • Average

    • Ein einfaches Programm zur Eingabe von Zahlen und zur Berechnung des Durchschnitts
    • Zeigt control flow, arithmetische Operationen, I/O und dynamische Speicherzuweisung
    • Ein Programm aus der Nand to Tetris software suite

  • Pong

    • Ein Pong-Spiel, das ein objektorientiertes Modell demonstriert
    • Mit den Pfeiltasten bewegt man das paddle nach links und rechts und hält den Ball im Spiel
    • Bei jedem Abprallen des Balls wird das paddle kleiner; berührt der Ball den unteren Bildschirmrand, ist das Spiel vorbei
    • Ein Programm aus der Nand to Tetris software suite

  • 2048

    • Ein 2048-Spiel, das recursion und komplexe application logic demonstriert
    • Auf einem 4x4 grid werden Zahlen mit den Pfeiltasten bewegt; gleiche Zahlen werden zusammengeführt
    • Beim Erreichen des 2048 tile gewinnt man, kann aber bis zur Niederlage weiterspielen

  • Overflow

    • Führt absichtlich einen stack overflow durch unendliche Rekursion aus, um einen virtual machine escape zu erreichen
    • Nutzt aus, dass die runtime keine Prüfung zur Verhinderung von stack overflow enthält
    • Wenn der Wert des stack pointer 2048 überschreitet, läuft der stack aus dem vorgesehenen Speicherbereich in den heap memory space hinein
    • Bei Ausführung auf leerem RAM kann das Programm zwischendurch zurückgesetzt werden, weil eine instruction den program counter auf 0 setzt
    • Wird es direkt nach der Ausführung von GeneticAlgorithm gestartet, kann es vorherige, nicht überschriebene RAM-Inhalte auslesen

  • SecretPassword

    • Nutzt aus, dass die runtime stack smashing nicht verhindert, um eine ursprünglich unzugängliche Funktion aufzurufen
    • Der Benutzer kann einen memory address im RAM mit einem gewünschten Wert überschreiben
    • Wenn die return address eines stack frame mit der Adresse einer anderen Funktion überschrieben wird, lässt sich beliebiger Code im Programm ausführen
    • Beispielwerte sind memory location 267 und overwrite value 1743
    • Die gleiche Art von Schwachstelle gibt es auch bei buffer overflow in C

  • GeneticAlgorithm

    • Eine creature simulation mit einfachem maschinellem Lernen
    • Jeder dot hat ein eigenes „brain“ aus acceleration vectors und entwickelt sich durch natürliche Selektion so weiter, dass er das goal erreicht
    • Dots, die näher am goal sterben, werden mit höherer Wahrscheinlichkeit als parent der nächsten Generation ausgewählt
    • Während der reproduction werden Teile des brain mutiert, um natürliche Evolution zu simulieren
    • Ein Genetic-Algorithm-Demovideo ist verfügbar

Hardware-Beschränkungen, auf die GeneticAlgorithm stieß

  • GeneticAlgorithm ist unter den verschiedenen Bestandteilen von NAND das einzelne Programm, dessen Entwicklung am längsten dauerte
  • Aus Performance-Gründen ist der einzige Faktor, den die dots für ihre Evolution nutzen, wie nah sie beim Sterben am goal waren; der Entropiegehalt des Natural-Selection-Algorithmus ist niedrig
  • Wegen des Speicherverbrauchs gibt es unbefriedigende Einschränkungen bei der Anzahl der dots und der Größe ihrer brain
  • Aufgrund der technischen Komplexität ist auch dann nicht garantiert, dass die brain eines dot groß genug sind, um das goal zu erreichen, wenn Hindernisse während der simulation neu platziert werden
    • Die brain size wird nur beim Start des Programms festgelegt
  • Die Implementierung umgeht die Einschränkungen von NAND mit verschiedenen Optimierungen
    • Der ROM instruction memory space ist begrenzt; bei zu viel Code lässt sich das Programm nicht compilieren
    • Der finale GeneticAlgorithm nutzt 99,2 % des instruction memory space
    • Der RAM memory space ist begrenzt, daher muss die heap memory usage optimiert werden
    • Dass der Bildschirm zwischen den Generationen statisch gefüllt erscheint, liegt daran, dass der screen memory space als temporärer swap memory für die nächste Generation verwendet wird
    • NAND hat keinen floating point type, und der darstellbare integer-Bereich reicht von -32768 bis 32767
    • Die Präzision der fitness-Berechnung sinkt, und auch integer overflow muss berücksichtigt werden
  • Zugehörige Optimierungen und weitere Einblicke sind in der GeneticAlgorithm codebase dokumentiert

Mit Jack NAND-Programme schreiben

  • Als wichtigste Ursache dafür, dass Programme in Jack nicht funktionieren, wird das Fehlen einer Operatorpräzedenz hervorgehoben
    • 4 * 2 + 3 muss als (4 * 2) + 3 geschrieben werden
    • if (~x & y) muss als if ((~x) & y) geschrieben werden
    • Der Auswertungswert eines mehrdeutigen Ausdrucks ohne Klammern ist undefiniert
  • Jack ist die weakly typed objektorientierte Programmiersprache von NAND
    • Der Beschreibung nach kommt es „C mit Java-Syntax“ nahe
    • Da NAND einen eigenen vollständigen Tech-Stack besitzt, kann ausschließlich in Jack dafür programmiert werden
  • Das grundlegende Jack OS wird beim Kompilieren zusammen mit dem Programm gebündelt
    • Es stellt Schnittstellen zu Strings, Speicher und Hardware bereit
    • Es enthält Funktionen wie Keyboard.readLine, Keyboard.readInt, Output.printString und Output.println
  • Jack unterstützt die drei primitiven Typen int, char und boolean
    • Über Klassen lassen sich abstrakte Datentypen definieren
    • field-Variablen deklarieren Attribute pro Instanz
    • field-Variablen haben privaten Scope, für externen Zugriff sind also Methoden nötig
  • function und method unterscheiden sich in der Aufrufweise
    • Eine Methode des aktuellen Objekts kann innerhalb derselben Klasse als do g(); aufgerufen werden
    • Bei einem Function-Call muss der Klassenname vorangestellt werden
    • Eine Objektmethode wird über das Objekt aufgerufen, etwa als do b.q();

Schwache Typisierung und Speicherverwaltung in Jack

  • Anders als Java unterstützt Jack weder strong typing noch Downcasting, Polymorphismus oder Vererbung
  • Intern gibt es tatsächlich nur einen einzigen Typ: signed 16-bit integer
    • Dem Compiler ist es bei Zuweisungen und Operationen egal, ob Typen gemischt werden
    • Weist man char den Wert 65 zu, kann er äquivalent zu 'A' behandelt werden
    • Wenn man einer Array-Variablen 5000 zuweist und a[100] = 77 ausführt, wird daraus RAM[5100] = 77
    • Array-Einträge können unterschiedliche Datentypen enthalten
    • Wenn das Speicherlayout passt, kann ein Array wie eine Instanz einer anderen Klasse verwendet werden
  • Jack ist eine Sprache mit manueller Speicherverwaltung
    • Wird nicht mehr benötigter Speicher nicht freigegeben, entsteht ein Memory Leak
    • Ein Heap Overflow erscheint als ERR6
    • Das Jack OS speichert Arrays und Strings nicht auf dem Stack, sondern auf dem Heap
  • Für Klassen, die Objekte darstellen, gilt eine dispose-Methode als Best Practice
    • Zuerst wird dispose der field-Variablen aufgerufen
    • Zum Schluss wird mit do Memory.deAlloc(this); die Objektinstanz selbst freigegeben
  • Eine Schleife, die wiederholt String-Literale erzeugt und ausgibt, kann einen Heap Overflow verursachen
    • Entweder wird der String in jeder Iteration freigegeben
    • Oder der String wird nur einmal alloziert und wiederverwendet, sodass er dauerhaft ausgegeben werden kann

Undefiniertes Verhalten und Vorsichtspunkte

  • Vergleichsoperatoren

    • a > b und a < b sind nicht immer mathematisch korrekt
    • Die VM-Implementierung wandelt a > b in a - b > 0 um
    • a - b kann überlaufen, sodass 20000 > -20000 zu false wird
    • Wenn der absolute Abstand zwischen a und b größer als 32767 ist, können > und < falsch sein
    • Dieses Verhalten wird aus Kompatibilitätsgründen mit Nand to Tetris nicht geändert

  • -32768

    • -32768 ist der einzige Wert, für den -(-32768) = -32768 gilt
    • Da es kein positives Gegenstück gibt, kann das zu Unsoundness und Logikfehlern führen
    • Output.printInt erwartet intern, dass Math.abs eine positive Zahl zurückgibt, was bei -32768 nicht der Fall ist, sodass das Jack OS fehlerhaft arbeitet

  • Funktionsaufrufe mit zu wenigen Argumenten

    • Wird eine Funktion mit Parametern ohne Argumente aufgerufen, kann undefiniertes Verhalten auftreten
    • Umgekehrt sind Funktionsaufrufe mit zu vielen Argumenten gültig; zusätzliche Argumente können über das Keyword arguments per Index angesprochen werden
    • Es gibt keinen Indikator für die Anzahl der Argumente

  • Ungeeignetes Type-Casting

    • Mit Array lassen sich Variablen in einen anderen Typ casten
    • Wird auf einer gecasteten Variablen eine nicht vorhandene Instanzmethode aufgerufen, ist das undefiniertes Verhalten
    • Der Compiler ist nicht intelligent genug, um das zu erkennen

  • Änderung von Stack-Frames und internen Registern

    • Werden Stack-Frames im Speicherbereich 256~2047 oder interne Register 1~15 verändert, kann undefiniertes Verhalten auftreten
    • Im Allgemeinen soll das außer durch Missbrauch von Memory.poke oder negatives Array-Indexing schwer möglich sein

  • Laden benutzerdefinierter VM-Dateien

    • NAND bietet Programmvalidierung für .jack-Dateien, aber nicht für .vm-Dateien
    • In .vm-Dateien lassen sich nicht existierende Funktionen aufrufen, nicht zugewiesene Variablen referenzieren und logisch ungültige Speicheroperationen ausführen
    • In den meisten Fällen kommt es zu einem Escape aus der Virtual Machine, und auf dem Bildschirm wird möglicherweise nichts angezeigt

Hardware-Spezifikationen und Speicherbelegung

  • Das RAM von NAND besteht aus 32.768 Wörtern, wobei jedes Wort eine 16-bit binary number enthält
  • Die Hardware reserviert 8.192 Speicheradressen für den Bildschirm
    • Jedes Bit jeder Adresse wird linear auf das entsprechende Pixel des 512x256-Bildschirms abgebildet
    • Die Bit-Nummerierung erfolgt nach dem LSb-0-Schema
  • Die Tastatur ist auf die Speicheradresse 24576 gemappt
    • Die aktuell gedrückte Taste wird an dieser Position abgebildet
    • Es wird empfohlen, Benutzereingaben nicht direkt über diese Adresse zu verarbeiten, sondern die Keyboard-Klasse des Jack OS zu verwenden
  • Die Tastatur erkennt ASCII-Zeichen und Sondertasten
    • neue Zeile = 128
    • Rücktaste = 129
    • Pfeil links/oben/rechts/unten = 130~133
    • Home/Ende/Bild auf/Bild ab/Einfg/Entf/ESC = 134~140
    • F1~F12 = 141~152
  • Die Hardware reserviert 240 Speicheradressen für statische Klassenvariablen und 1.792 Speicheradressen für den globalen Stack
    • Es heißt, dass diese Begrenzung in der Regel kein Problem darstellt, solange keine tiefe Rekursion ausgeführt wird

Eigene OS-Implementierung über Jack OS hinaus

  • Standardmäßig wird Jack OS beim Kompilieren zusammen mit dem Programm gebündelt und stellt Strings, Speicher und Hardware-Interfaces bereit.
  • Man kann eine eigene OS-Implementierung mit einem dedizierten Hardware-Interface bereitstellen.
    • Die IDE behandelt Jack-OS-Dateien genauso wie normale Programmdateien.
    • OS-Dateien können ebenfalls gelöscht oder überschrieben werden.
  • Auch bei Verwendung eines eigenen OS gibt es Kernfunktionen, die für das Kompilieren zwingend implementiert werden müssen.
    • Sys.init: der tatsächliche Entry Point, der in der VM-Implementierung fest verdrahtet ist, nicht Main.main
    • Memory.alloc: der Heap-Speicher-Allocator, den Klassenkonstruktoren intern beim Erzeugen von Objekten verwenden
    • String.newWithStr: der interne Konstruktor für String-Literale
    • Math.multiply: wird intern anstelle des Jack-Ausdrucks x * y aufgerufen
    • Math.divide: wird intern anstelle des Jack-Ausdrucks x / y aufgerufen
  • Sys.init des mitgelieferten Jack OS initialisiert Speicher, Mathematik, Bildschirm und Ausgabe, ruft dann Main.main() auf und anschließend Sys.halt().

Interne Funktionsweise von NAND

  • Der NAND-Computer folgt einer Harvard-Architektur.
    • ROM als Instruction Memory und RAM als Data Memory sind getrennt.
    • Die CPU sorgt dafür, dass beide zusammenarbeiten.
  • Die CPU ist eine Akkumulator-Maschine.
    • Im Kontrollfluss stützt sie sich stark auf eingebaute Register.
    • Der Akkumulator ist hier das Register D.
  • Der Befehlssatz der CPU hat nur zwei Opcodes.
    • Der Befehlssatz ist relativ einfach, bietet aber einen großen Funktionsumfang.
    • Die ALU ist über die Ausdrücke definiert, die in einem einzelnen Befehl berechnet werden können.
  • Compiler und virtuelle Maschine sind keine NAND-spezifischen Konzepte und werden daher nur kurz behandelt.
    • Einige ungewöhnliche Syntax-Features sind das Ergebnis davon, die Compiler-Implementierung zu vereinfachen.
    • Der Compiler ist ein Recursive-Descent-Parser auf Basis einer LL(1)-Grammatik.
    • Der Compiler erzeugt VM-Code, und die VM wird als einfache Stack-Maschine verwendet.
    • Jede VM-Instruktion wird auf Assembler und Maschinencode abgebildet.
  • Der Implementierungscode ist unter core und compiler implementation zu finden.

Kernpunkte der Jack-Sprache und der OS-Referenz

  • Ein Jack-Programm besteht aus einer Sammlung von Klassen.
    • Klassen werden in separaten Dateien definiert.
    • Mindestens eine Klasse ist erforderlich, und eine davon muss Main sein.
    • Der Entry Point nach Maßgabe des Jack OS ist die Funktion main der Klasse Main.
  • Eine Klasse kann Deklarationen für field, static, constructor, method und function enthalten.
    • Die Reihenfolge von field- und static-Deklarationen ist beliebig.
    • Auch die Reihenfolge der Subroutine-Deklarationen ist beliebig.
    • Der Typ ist einer von void, int, boolean, char oder ein Klassenname.
  • Syntax-Eigenschaften
    • Whitespace und Kommentare werden ignoriert.
    • & und | sind bitweise Operatoren und verwenden kein Short-Circuiting.
    • true, false und null entsprechen jeweils -1, 0 und 0.
    • String-Konstanten dürfen weder Zeilenumbrüche noch Anführungszeichen direkt enthalten, Escaping ist ebenfalls nicht möglich.
    • Anführungszeichen und Zeilenumbrüche werden vom OS über String.doubleQuote() und String.newLine() bereitgestellt.
    • Bezeichner sind case-sensitive.
  • Wichtige Klassen des Jack OS
    • Array: Erzeugen und Freigeben von Arrays
    • Keyboard: Tastenanschläge, Zeichen-, Zeilen- und Integer-Eingabe
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: Ausgabe auf dem Textbildschirm und Cursor-Bewegung
    • Screen: Zeichnen von Pixeln, Linien, Rechtecken und Kreisen
    • String: Erzeugen und Freigeben von Strings, Zeichenzugriff, Anhängen und Integer-Konvertierung
    • Sys: halt, error, wait
  • Ungültige Zustände zeigen einen Fehlercode im Format "ERR[N]" an und beenden die Programmausführung.
    • ERR3: Division durch null
    • ERR6: Heap-Überlauf
    • ERR15, ERR16: String-Index außerhalb des gültigen Bereichs
    • ERR17: String ist voll
    • ERR20: ungültige Cursor-Position

Kein Projekt, das tatsächlich nur aus NAND-Gattern besteht

  • In den FAQ wird eingeräumt, dass die Beschreibung und der Titel „everything made from NAND gates“ irreführend sind, aber in guter Absicht formuliert wurden.
  • Compiler und Übersetzer der virtuellen Maschine sind in TypeScript geschrieben.
  • Der emulierte Kernel und die emulierte Hardware bilden die Funktionsweise eines echten Computers nicht eins zu eins ab.
  • Der eigentliche NAND-Gatter-Logiksimulator ist in Rust geschrieben und macht nur einen kleinen Teil der gesamten Codebasis aus.
    • Der Rust-Code wird zu WebAssembly kompiliert, damit er im Browser läuft.
    • Dadurch entfällt faktisch die Annahme, dass alle Berechnungen auf NAND-Gattern ausgeführt werden.
  • NAND dient als Bildungs- und Theorieprojekt.
    • Theoretisch könnte dieselbe CPU-Logik auch in einer Real-World-Ausprägung der emulierten Hardware funktionieren.
    • Als Beispiel für ein nand2tetris-basiertes FPGA-Hardwareprojekt wird https://gitlab.com/x653/nand2tetris-fpga/ genannt.

Implementierungsumfang und Grenzen der IDE

  • NAND folgt der Spezifikation des Kurses Nand to Tetris und des dazugehörigen Buchs.
  • Der Implementierer hat die Spezifikationen für CPU, Assembler, Übersetzer der virtuellen Maschine und Compiler selbst umgesetzt und beim Portieren der Plattform ins Web eine eigene IDE und UI ergänzt.
  • Dass Jack Typen explizit angeben muss, liegt daran, dass der Compiler erkennen muss, zu welcher Klasse eine Instanzmethode gehört.
    • s.appendChar(33) für ein als Typ String deklariertes s wird beim Kompilieren in String.appendChar(s, 33) umgewandelt.
  • Die IDE opfert zugunsten einer einfachen Implementierung die User Experience.
    • Für Syntax Highlighting werden contenteditable und Logik zur Cursor-Positionierung verwendet.
    • Dadurch ist sie langsam, auffällig fehlerhaft und gängige Tastenkombinationen funktionieren nicht.
  • Um Code zu kompilieren und auszuführen, muss man auf „Start“ klicken.
    • Das OS benötigt normalerweise etwas weniger als 1 Sekunde für Speicherinitialisierung und Service-Setup.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-04-27
Hacker-News-Kommentare

  • Ein großartiges Nebenprojekt, und auch das README ist wirklich gut. Nachdem ich ein wenig mit Ben Eaters 6502 Computer (https://eater.net/) herumgespielt hatte, dachte ich darüber nach, Nand to Tetris nachzuvollziehen.

    • Wäre es auch möglich, einen physischen NAND-to-Tetris-Computer zu bauen? Oder ist das rein eine Übung in einer virtuellen Umgebung?

  • Allein aus diesem Material könnte man mehrere Uni-Kurse machen. Sehr gut aufbereitet.

    • Ist das nicht einfach Nand2Tetris? Ich habe den Kurs gemacht, und auf den ersten Blick sieht es, einschließlich der Sprache Jack, genauso aus.

  • Wirklich gut gemacht. Damit hat man die Abstraktionsebenen, die die meisten Programmierer in ihrer gesamten Laufbahn nie zu sehen bekommen, direkt durchlaufen.

  • Großartige Arbeit. NAND to Tetris hat mir geholfen, nach dem Uni-Abschluss meinen ersten Job zu bekommen.

    • Mich würde interessieren, wie es geholfen hat.

  • In den frühen 1990er-Jahren war ein ähnlicher Entwurf an der UC Berkeley eine zentrale Aufgabe in der Qualifikationsprüfung für Computerhardware.
    Konkret ging es darum, von Grund auf nur mit NAND-Gates einen mikrocodebasierten, pipelined RISC-Prozessor zu entwerfen; man musste ihn nicht tatsächlich bauen, aber einen detaillierten Entwurf auf Papier einreichen.

  • Wirklich beeindruckende Arbeit. Als ich den Nand2Tetris-Kurs gemacht habe, wollte ich selbst eine ähnliche virtuelle Implementierung bauen.
    Beeindruckend, dass das tatsächlich jemand umgesetzt hat; ich vermute, die Person versteht jetzt wirklich sehr gut, wie Computer funktionieren.

    • Ich hatte heute Morgen auch eine ähnliche Idee, Grundbausteine in SVG zu modellieren.
      Umso erstaunlicher, dass jemand schon etwas umgesetzt hat, das um eine Größenordnung beeindruckender ist, als ich es mir vorgestellt hatte.

  • Hervorragende Arbeit. Ich habe kürzlich ebenfalls mit Nand2Tetris angefangen und möchte in den nächsten Monaten Teil 1, also den Hardware-Teil des Kurses, abschließen.
    Meinen Fortschritt habe ich hier im Blog festgehalten: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • Gelogen. Es wurden doch NAND-Gates und ein Takt verwendet.

    • Den Takt kann man auch mit einem Ringoszillator erzeugen, und einen Ringoszillator baut man, indem man eine ungerade Anzahl von NAND-Gates wie NOT-Gates verschaltet.

  • Tolle Arbeit. Ich habe es mir gebookmarkt, um später tiefer einzusteigen.
    Ich mag NAND-to-Tetris, habe es aber nie bis zum Ende durchgezogen, daher freue ich mich darauf, mir dieses Projekt anzusehen.

  • Mich würde interessieren: Wie viele NAND-Gates sind es insgesamt?

    • Ich habe mir den Code genauer angesehen: Pro Taktzyklus werden NAND-Gates 3.234-mal verwendet :)