Hier ist eine theoretische Frage, die sich auf keinen Fall leicht beantworten lässt, auch nicht die triviale.

In Conways Game of Life gibt es Konstrukte wie das Metapixel, mit denen das Game of Life auch jedes andere Game-of-Life-Regelsystem simulieren kann. Darüber hinaus ist bekannt, dass das Game of Life Turing-vollständig ist.

Ihre Aufgabe ist es, einen zellularen Automaten nach den Regeln von Conways Lebensspiel zu bauen, mit dem Sie Tetris spielen können.

Ihr Programm erhält Eingaben, indem Sie den Zustand des Automaten bei einer bestimmten Generierung manuell ändern, um einen Interrupt darzustellen (z. B. ein Stück nach links oder rechts bewegen, fallen lassen, drehen oder ein neues Stück zufällig generieren, um es auf das Gitter zu legen) und zählen eine bestimmte Anzahl von Generationen als Wartezeit und Anzeige des Ergebnisses irgendwo auf dem Automaten. Das angezeigte Ergebnis muss sichtbar einem tatsächlichen Tetris-Gitter ähneln.

Ihr Programm wird nach folgenden Kriterien bewertet (wobei niedrigere Kriterien als Tiebreaker für höhere Kriterien fungieren):

• Größe des Begrenzungsrahmens - der rechteckige Rahmen mit dem kleinsten Bereich, der die angegebene Lösung vollständig enthält, gewinnt.

• Kleinere Änderungen an der Eingabe - die wenigsten Zellen (für den schlimmsten Fall in Ihrem Automaten), die für einen Interrupt manuell angepasst werden müssen, gewinnen.

• Schnellste Ausführung - Die wenigsten Generationen, die einen Tick in der Simulation vorrücken, gewinnen.

• Anfängliche Anzahl lebender Zellen - kleinere Anzahl gewinnt.

• Erster Beitrag - früherer Beitrag gewinnt.

Dies begann als Suche, endete aber als Odyssee.

Quest for Tetris Processor, 2.940.928 x 10.295.296

Die Pattern - Datei, in seiner ganzen Pracht, findet sich hier , sichtbar im Browser hier .

Dieses Projekt ist der Höhepunkt der Bemühungen vieler Benutzer im Laufe der letzten 1 1/2 Jahre. Obwohl sich die Zusammensetzung des Teams im Laufe der Zeit geändert hat, sind die Teilnehmer zum Zeitpunkt des Schreibens folgende:

• PhiNotPi
• El'endia Starman
• K Zhang
• Blau (Schlammfisch)
• Kühe quaken (Kritixi Lithos)
• Mego
• Quartata

Wir möchten auch unseren Dank 7H3_H4CK3R, erweitern Conor O'Brien , und die vielen anderen Anwender , die Mühe haben , in dieser Herausforderung zu lösen.

Aufgrund des beispiellosen Umfangs dieser Zusammenarbeit ist diese Antwort in mehrere Antworten aufgeteilt, die von den Mitgliedern dieses Teams verfasst wurden. Jedes Mitglied wird über bestimmte Unterthemen schreiben, die in etwa den Bereichen des Projekts entsprechen, an denen es am meisten beteiligt war.

Bitte verteilen Sie alle Upvotes oder Bounties auf alle Mitglieder des Teams.

Inhaltsverzeichnis

1. Überblick
2. Metapixel und VarLife
3. Hardware
4. QFTASM und Cogol
5. Montage, Übersetzung und die Zukunft
6. Neue Sprache und Compiler

Sehen Sie sich auch unsere GitHub-Organisation an, in der wir den gesamten Code abgelegt haben, den wir als Teil unserer Lösung geschrieben haben. Fragen können an unseren Entwicklungschat gerichtet werden .

Teil 1: Übersicht

Die Grundidee dieses Projekts ist die Abstraktion . Anstatt ein Tetris-Spiel direkt in Life zu entwickeln, haben wir die Abstraktion langsam in mehreren Schritten verbessert. Auf jeder Ebene entfernen wir uns weiter von den Schwierigkeiten des Lebens und nähern uns dem Aufbau eines Computers, der so einfach zu programmieren ist wie jeder andere.

Zunächst verwendeten wir OTCA-Metapixel als Grundlage für unseren Computer. Diese Metapixel können jede "lebensechte" Regel emulieren. Wireworld und der Wireworld-Computer dienten als wichtige Inspirationsquellen für dieses Projekt, daher wollten wir eine ähnliche Konstruktion mit Metapixeln erstellen. Obwohl es nicht möglich ist, Wireworld mit OTCA-Metapixeln zu emulieren, ist es möglich, verschiedenen Metapixeln unterschiedliche Regeln zuzuweisen und Metapixelanordnungen zu erstellen, die ähnlich wie Drähte funktionieren.

Der nächste Schritt bestand darin, eine Vielzahl grundlegender Logikgatter zu konstruieren, die als Grundlage für den Computer dienen. Bereits in dieser Phase beschäftigen wir uns mit Konzepten, die dem realen Prozessordesign ähneln. Hier ist ein Beispiel für ein ODER-Gatter. Jede Zelle in diesem Bild ist tatsächlich ein ganzes OTCA-Metapixel. Sie können sehen, wie "Elektronen" (die jeweils ein einzelnes Datenbit darstellen) das Tor betreten und verlassen. Sie können auch alle verschiedenen Metapixeltypen sehen, die wir in unserem Computer verwendet haben: B / S als schwarzer Hintergrund, B1 / S in Blau, B2 / S in Grün und B12 / S1 in Rot.

Von hier aus haben wir eine Architektur für unseren Prozessor entwickelt. Wir haben erhebliche Anstrengungen unternommen, um eine Architektur zu entwerfen, die sowohl nicht esoterisch als auch so einfach wie möglich zu implementieren ist. Während der Wireworld-Computer eine rudimentäre transportgesteuerte Architektur verwendete, verwendet dieses Projekt eine viel flexiblere RISC-Architektur mit mehreren Operationscodes und Adressierungsmodi. Wir haben eine Assemblersprache namens QFTASM (Quest for Tetris Assembly) erstellt, die den Aufbau unseres Prozessors leitete.

Unser Computer ist auch asynchron, was bedeutet, dass es keine globale Uhr gibt, die den Computer steuert. Die Daten werden vielmehr von einem Taktsignal begleitet, während es um den Computer fließt, was bedeutet, dass wir uns nur auf lokale, nicht aber auf globale Zeitabläufe des Computers konzentrieren müssen.

Hier ist eine Illustration unserer Prozessorarchitektur:

Von hier aus geht es nur noch darum, Tetris auf dem Computer zu implementieren. Um dies zu erreichen, haben wir an mehreren Methoden zum Kompilieren einer höheren Sprache in QFTASM gearbeitet. Wir haben eine Basissprache namens Cogol, eine zweite, fortgeschrittenere Sprache in der Entwicklung, und schließlich haben wir ein im Aufbau befindliches GCC-Backend. Das aktuelle Tetris-Programm wurde in Cogol geschrieben / kompiliert.

Nachdem der endgültige Tetris QFTASM-Code generiert wurde, bestand der letzte Schritt darin, diesen Code in das entsprechende ROM und dann von den Metapixeln zum zugrunde liegenden Game of Life zusammenzusetzen, um unsere Konstruktion abzuschließen.

Tetris ausführen

Für diejenigen, die Tetris spielen möchten, ohne mit dem Computer herumzuspielen, können Sie den Tetris-Quellcode auf dem QFTASM-Interpreter ausführen . Stellen Sie die RAM-Anzeigeadressen auf 3-32 ein, um das gesamte Spiel anzuzeigen. Hier ist ein Permalink für die Bequemlichkeit: Tetris in QFTASM .

Spielfunktionen:

• Alle 7 Tetrominos
• Bewegung, Rotation, weiche Tropfen
• Linienräumung und Wertung
• Vorschau Stück
• Spielereingaben führen zu Zufälligkeiten

Anzeige

Unser Computer repräsentiert das Tetris-Board als Gitter in seinem Speicher. Die Adressen 10-31 zeigen die Tafel an, die Adressen 5-8 zeigen das Vorschaubild an, und die Adresse 3 enthält die Partitur.

Eingang

Die Eingabe in das Spiel erfolgt durch manuelles Bearbeiten des Inhalts von RAM-Adresse 1. Unter Verwendung des QFTASM-Interpreters bedeutet dies, dass direkte Schreibvorgänge an Adresse 1 ausgeführt werden. Suchen Sie auf der Seite des Interpreters nach "Direct Write to RAM" (Direktes Schreiben in RAM). Für jede Bewegung muss nur ein einziges RAM-Bit bearbeitet werden. Dieses Eingaberegister wird automatisch gelöscht, nachdem das Eingabeereignis gelesen wurde.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

Punktesystem

Sie erhalten einen Bonus für das Löschen mehrerer Zeilen in einer Runde.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Teil 2: OTCA Metapixel und VarLife

OTCA-Metapixel

( Quelle )

Das OTCA-Metapixel ist ein Konstrukt in Conways Game of Life, mit dem beliebige lebensechte zellulare Automaten simuliert werden können. Wie das LifeWiki (oben verlinkt) sagt,

Das OTCA-Metapixel ist eine Einheitszelle mit einer Größe von 2048 × 2048 Perioden und 35328 Pixeln, die von Brice Due hergestellt wurde. Es hat viele Vorteile, einschließlich der Fähigkeit, jeden lebensechten zellularen Automaten zu emulieren und der Tatsache, dass, wenn herausgezoomt, der EIN und AUS-Zellen sind leicht zu unterscheiden ...

Lebensechte zelluläre Automaten bedeuten hier im Wesentlichen, dass Zellen geboren werden und Zellen überleben, je nachdem, wie viele ihrer acht Nachbarzellen am Leben sind. Die Syntax für diese Regeln lautet wie folgt: a B gefolgt von der Anzahl der lebenden Nachbarn, die eine Geburt verursachen, dann ein Schrägstrich, dann ein S gefolgt von der Anzahl der lebenden Nachbarn, die die Zelle am Leben erhalten. Ein bisschen wortreich, also denke ich, dass ein Beispiel helfen wird. Das kanonische Spiel des Lebens kann durch die Regel B3 / S23 dargestellt werden, die besagt, dass jede tote Zelle mit drei lebenden Nachbarn am Leben wird und jede lebende Zelle mit zwei oder drei lebenden Nachbarn am Leben bleibt. Ansonsten stirbt die Zelle.

Obwohl es sich um eine 2048 x 2048-Zelle handelt, hat das OTCA-Metapixel tatsächlich einen Begrenzungsrahmen von 2058 x 2058-Zellen, da es sich mit seinen diagonalen Nachbarn in jeder Richtung um fünf Zellen überlappt . Die überlappenden Zellen dienen dazu, Segelflugzeuge abzufangen, die den Nachbarn der Metazellen signalisieren, dass sie eingeschaltet sind, damit sie andere Metapixel nicht stören oder unbegrenzt davonfliegen. Die Geburts- und Überlebensregeln werden in einem speziellen Abschnitt von Zellen auf der linken Seite des Metapixels kodiert, indem Esser an bestimmten Positionen entlang zweier Spalten (eine für die Geburt, die andere für das Überleben) anwesend oder abwesend sind. Um den Zustand benachbarter Zellen zu erkennen, gehen Sie wie folgt vor:

Ein 9-LWSS-Stream geht dann im Uhrzeigersinn um die Zelle und verliert für jede angrenzende "Ein" -Zelle einen LWSS, der eine Honeybit-Reaktion ausgelöst hat. Die Anzahl der fehlenden LWSS wird gezählt, indem die Position des vorderen LWSS ermittelt wird, indem ein anderer LWSS aus der entgegengesetzten Richtung hineingestoßen wird. Diese Kollision löst Segelflugzeuge aus, die eine oder zwei weitere Honigbissenreaktionen auslösen, wenn die Esser, die auf einen Geburts- / Überlebenszustand hinweisen, nicht anwesend sind.

Ein detaillierteres Diagramm der einzelnen Aspekte des OTCA-Metapixels finden Sie auf der Originalwebsite: Wie funktioniert es? .

VarLife

Ich habe einen Online-Simulator für lebensechte Regeln erstellt, in dem Sie jede Zelle dazu bringen können, sich nach einer lebensechten Regel zu verhalten. Er wurde "Variationen des Lebens" genannt. Dieser Name wurde aus Gründen der Übersichtlichkeit in "VarLife" abgekürzt. Hier ist ein Screenshot davon (Link hier: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):

Bemerkenswerte Eigenschaften:

• Schalten Sie die Zellen zwischen "Live" und "Dead" um und malen Sie die Tafel mit verschiedenen Regeln.
• Die Möglichkeit, die Simulation zu starten und zu stoppen und jeweils einen Schritt auszuführen. Es ist auch möglich, eine bestimmte Anzahl von Schritten so schnell wie möglich oder langsamer auszuführen, und zwar mit der Geschwindigkeit, die in den Feldern Ticks pro Sekunde und Millisekunden pro Tick festgelegt ist.
• Löschen Sie alle aktiven Zellen oder setzen Sie die Karte vollständig in den leeren Zustand zurück.
• Kann die Zellen- und Platinengröße ändern und auch das horizontale und / oder vertikale Umwickeln von Toroiden ermöglichen.
• Permalinks (die alle Informationen in der URL kodieren) und kurze URLs (weil es manchmal einfach zu viele Informationen gibt, die aber trotzdem nett sind).
• Regelsätze mit B / S-Spezifikation, Farben und optionaler Zufälligkeit.
• Und zu guter Letzt, Rendering von Gifs!

Die Render-to-Gif-Funktion ist meine Lieblingsfunktion, da die Implementierung eine Menge Arbeit gekostet hat. Es war also sehr befriedigend, als ich sie um sieben Uhr morgens geknackt habe, und weil es sehr einfach ist, VarLife-Konstrukte mit anderen zu teilen .

Grundlegende VarLife-Schaltung

Insgesamt benötigt der VarLife-Computer nur vier Zelltypen! Acht Staaten insgesamt, einschließlich der toten / lebendigen Staaten. Sie sind:

• B / S (schwarz / weiß), das als Puffer zwischen allen Komponenten dient, da B / S-Zellen niemals am Leben sein können.
• B1 / S (blau / cyan), der Hauptzellentyp für die Signalausbreitung.
• B2 / S (grün / gelb), das hauptsächlich zur Signalsteuerung verwendet wird, um sicherzustellen, dass es sich nicht rückwärts ausbreitet.
• B12 / S1 (rot / orange), der in einigen speziellen Situationen verwendet wird, z. B. beim Überqueren von Signalen und Speichern eines Datenbits.

Verwenden Sie diese kurze URL, um VarLife mit den bereits kodierten Regeln zu öffnen: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Drähte

Es gibt einige verschiedene Drahtdesigns mit unterschiedlichen Eigenschaften.

Dies ist der einfachste und grundlegendste Draht in VarLife, ein Streifen Blau, der von grünen Streifen umrandet ist.

Kurze URL: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Dieser Draht ist unidirektional. Das heißt, es wird jedes Signal, das versucht, sich in die entgegengesetzte Richtung zu bewegen, abbrechen. Es ist auch eine Zelle schmaler als der Basisdraht.

Kurze URL: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Diagonaldrähte gibt es auch, aber sie werden überhaupt nicht viel verwendet.

Kurze URL: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Tore

Tatsächlich gibt es viele Möglichkeiten, jedes einzelne Tor zu konstruieren, daher werde ich nur ein Beispiel für jede Art zeigen. Dieses erste GIF zeigt AND-, XOR- und OR-Gatter. Die Grundidee dabei ist, dass eine grüne Zelle wie ein UND, eine blaue wie ein XOR und eine rote wie ein ODER fungiert und alle anderen Zellen um sie herum nur dazu da sind, den Fluss richtig zu steuern.

Kurze URL: http://play.starmaninnovations.com/varlife/EGTlKktmeI

Das UND-NICHT-Gatter, abgekürzt als "ANT-Gatter", erwies sich als eine wichtige Komponente. Es ist ein Tor, das ein Signal von A genau dann durchlässt, wenn es kein Signal von B gibt. Daher "A AND NOT B".

Kurze URL: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Obwohl es sich nicht gerade um ein Tor handelt , ist es dennoch sehr wichtig und nützlich, ein Kabelkreuzungsplättchen zu haben.

Kurze URL: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Übrigens gibt es hier kein NICHT-Tor. Das liegt daran, dass ohne ein eingehendes Signal eine konstante Ausgabe erzeugt werden muss, was nicht gut mit der Vielfalt an Timings zusammenarbeitet, die die aktuelle Computerhardware erfordert. Wir haben uns ohne sowieso gut verstanden.

Viele Komponenten wurden absichtlich so entworfen, dass sie in einen Begrenzungsrahmen von 11 x 11 (eine Kachel ) passen, in dem es 11 Ticks dauert, bis die Kachel betreten wird, um die Kachel zu verlassen. Dadurch werden die Komponenten modularer und können bei Bedarf einfacher zusammengesteckt werden, ohne dass die Drähte auf Abstand oder Zeitpunkt eingestellt werden müssen.

In diesem Blog-Beitrag von PhiNotPi: Building Blocks: Logic Gates finden Sie weitere Gates, die bei der Erforschung von Schaltungskomponenten entdeckt / konstruiert wurden .

Verzögerungskomponenten

Während des Entwurfs der Computerhardware entwickelte KZhang mehrere Verzögerungskomponenten (siehe unten).

4-Tick-Verzögerung: Kurze URL: http://play.starmaninnovations.com/varlife/gebOMIXxdh

5-Tick-Verzögerung: Kurze URL: http://play.starmaninnovations.com/varlife/JItNjJvnUB

8-Tick-Verzögerung (drei verschiedene Einstiegspunkte): Kurze URL: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

Verzögerung von 11 Ticks: Kurze URL: http://play.starmaninnovations.com/varlife/kfoADussXA

12-Tick-Verzögerung: Kurze URL: http://play.starmaninnovations.com/varlife/bkamAfUfud

14-Tick-Verzögerung: Kurze URL: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Verzögerung von 15 Ticks (durch Vergleich damit bestätigt ): Kurze URL: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Nun, das ist es für grundlegende Schaltungskomponenten in VarLife! Siehe KZhang Hardware Beitrag für die Hauptschaltung des Computers!

Teil 3: Hardware

Mit unserem Wissen über Logikgatter und der allgemeinen Struktur des Prozessors können wir alle Komponenten des Computers entwerfen.

Demultiplexer

Ein Demultiplexer oder Demux ist eine entscheidende Komponente für ROM, RAM und ALU. Es leitet ein Eingangssignal auf der Grundlage einiger gegebener Auswahldaten zu einem der vielen Ausgangssignale. Es besteht aus 3 Hauptteilen: einem Seriell-Parallel-Wandler, einem Signalprüfer und einem Taktsignalverteiler.

Wir beginnen mit der Konvertierung der seriellen Selektordaten in "parallel". Dies erfolgt durch strategisches Aufteilen und Verzögern der Daten, sodass das Datenbit ganz links das Taktsignal im Quadrat 11 x 11 schneidet, das Datenbit ganz links das Taktsignal im Quadrat 11 x 11 und so weiter. Obwohl jedes Datenbit in jedem 11 × 11-Quadrat ausgegeben wird, schneidet sich jedes Datenbit nur einmal mit dem Taktsignal.

Als nächstes prüfen wir, ob die parallelen Daten mit einer voreingestellten Adresse übereinstimmen. Wir tun dies, indem wir UND- und ANT-Gatter für die Takt- und Paralleldaten verwenden. Wir müssen jedoch sicherstellen, dass die parallelen Daten auch ausgegeben werden, damit sie erneut verglichen werden können. Dies sind die Tore, die ich mir ausgedacht habe:

Schließlich teilen wir einfach das Taktsignal auf, stapeln eine Reihe von Signalprüfern (einen für jede Adresse / jeden Ausgang) und wir haben einen Multiplexer!

Rom

Der ROM soll eine Adresse als Eingabe nehmen und den Befehl an diese Adresse als Ausgabe senden. Wir beginnen mit der Verwendung eines Multiplexers, um das Taktsignal zu einem der Befehle zu leiten. Als nächstes müssen wir ein Signal unter Verwendung einiger Drahtkreuzungen und ODER-Gatter erzeugen. Die Drahtkreuzungen ermöglichen es dem Taktsignal, alle 58 Bits des Befehls nach unten zu laufen, und ermöglichen es auch, dass ein erzeugtes Signal (derzeit parallel) durch den ROM nach unten wandert, um ausgegeben zu werden.

Als nächstes müssen wir nur das parallele Signal in serielle Daten umwandeln, und der ROM ist vollständig.

Das ROM wird derzeit durch Ausführen eines Skripts in Golly generiert, das Assembly-Code aus Ihrer Zwischenablage in das ROM übersetzt.

SRL, SL, SRA

Diese drei logischen Gatter werden für Bitverschiebungen verwendet und sind komplizierter als die typischen UND-, ODER-, XOR-Gatter usw. Damit diese Gatter funktionieren, verzögern wir zunächst das Taktsignal um eine angemessene Zeit, um eine "Verschiebung" zu bewirken. in den Daten. Das zweite Argument für diese Gatter gibt an, wie viele Bits verschoben werden sollen.

Für den SL und die SRL müssen wir

1. Stellen Sie sicher, dass die 12 höchstwertigen Bits nicht aktiviert sind (andernfalls ist der Ausgang einfach 0) und
2. Verzögern Sie die Daten um die richtige Menge, basierend auf den 4 niedrigstwertigen Bits.

Dies ist mit einer Reihe von AND / ANT-Gattern und einem Multiplexer möglich.

Der SRA ist etwas anders, weil wir das Vorzeichenbit während der Verschiebung kopieren müssen. Wir tun dies, indem wir das Taktsignal mit dem Vorzeichen-Bit UND-verknüpfen und dann diese Ausgabe einige Male mit Draht-Splittern und ODER-Gattern kopieren.

Set-Reset (SR) Latch

Viele Teile der Funktionalität des Prozessors hängen von der Fähigkeit ab, Daten zu speichern. Mit 2 roten B12 / S1-Zellen können wir genau das tun. Die beiden Zellen können sich gegenseitig anhalten und auch gemeinsam ausgeschaltet bleiben. Mit einigen zusätzlichen Setz-, Rücksetz- und Leseschaltungen können wir einen einfachen SR-Latch erstellen.

Synchronizer

Indem wir serielle Daten in parallele Daten konvertieren und dann eine Reihe von SR-Latches setzen, können wir ein ganzes Wort von Daten speichern. Um die Daten wieder herauszubekommen, können wir einfach alle Latches lesen und zurücksetzen und die Daten entsprechend verzögern. Auf diese Weise können wir ein (oder mehrere) Datenworte speichern, während wir auf ein anderes warten, sodass zwei zu unterschiedlichen Zeitpunkten eintreffende Datenwörter synchronisiert werden können.

Zähler lesen

Dieses Gerät verfolgt, wie oft es vom RAM aus adressieren muss. Dazu wird ein Gerät verwendet, das dem SR-Latch ähnelt: ein T-Flip-Flop. Jedes Mal, wenn das T-Flip-Flop eine Eingabe empfängt, ändert es den Zustand: Wenn es eingeschaltet war, wird es ausgeschaltet und umgekehrt. Wenn das T-Flip-Flop von EIN auf AUS geschaltet wird, sendet es einen Ausgangsimpuls aus, der in ein anderes T-Flip-Flop eingespeist werden kann, um einen 2-Bit-Zähler zu bilden.

Um den Lesezähler zu erstellen, müssen wir den Zähler mit zwei ANT-Gattern auf den entsprechenden Adressierungsmodus einstellen und anhand des Ausgangssignals des Zählers entscheiden, wohin das Taktsignal geleitet werden soll: zur ALU oder zum RAM.

Warteschlange lesen

Die Lesewarteschlange muss nachverfolgen, welcher Lesezähler eine Eingabe an den RAM gesendet hat, damit sie die Ausgabe des RAM an die richtige Stelle senden kann. Dazu verwenden wir einige SR-Latches: ein Latch für jeden Eingang. Wenn ein Signal von einem Lesezähler an den RAM gesendet wird, wird das Taktsignal aufgeteilt und der SR-Latch des Zählers gesetzt. Der RAM-Ausgang wird dann mit dem SR-Latch UND-verknüpft, und das Taktsignal vom RAM setzt den SR-Latch zurück.

ALU

Die ALU funktioniert ähnlich wie die Lesewarteschlange, indem sie ein SR-Latch verwendet, um zu verfolgen, wohin ein Signal gesendet werden soll. Zuerst wird der SR-Latch der Logikschaltung, der dem Operationscode des Befehls entspricht, unter Verwendung eines Multiplexers eingestellt. Als nächstes werden die Werte des ersten und zweiten Arguments mit dem SR-Latch UND-verknüpft und dann an die Logikschaltungen übergeben. Das Taktsignal setzt den Zwischenspeicher beim Durchlauf zurück, so dass die ALU wieder verwendet werden kann. (Der größte Teil der Schaltung ist heruntergefahren, und eine Menge Delay-Management ist eingebaut, so dass es ein bisschen chaotisch aussieht.)

RAM

Der RAM war der komplizierteste Teil dieses Projekts. Es erforderte eine sehr spezifische Kontrolle über jedes SR-Latch, das Daten speichert. Zum Lesen wird die Adresse in einen Multiplexer gesendet und an die RAM-Einheiten gesendet. Die RAM-Einheiten geben die von ihnen gespeicherten Daten parallel aus, die in serielle umgewandelt und ausgegeben werden. Zum Schreiben wird die Adresse in einen anderen Multiplexer gesendet, die zu schreibenden Daten werden von seriell zu parallel konvertiert und die RAM-Einheiten verbreiten das Signal im gesamten RAM.

Jede 22x22-Metapixel-RAM-Einheit hat diese Grundstruktur:

Wenn wir den gesamten Arbeitsspeicher zusammenfassen, erhalten wir etwas, das so aussieht:

Alles zusammenfügen

Mit all diesen Komponenten und der in der Übersicht beschriebenen allgemeinen Computerarchitektur können wir einen funktionierenden Computer konstruieren!

Downloads: - Fertiger Tetris-Computer - ROM-Erstellungsskript, leerer Computer und Prime Finding-Computer

Teil 4: QFTASM und Cogol

Architekturübersicht

Kurz gesagt, unser Computer verfügt über eine asynchrone 16-Bit-RISC-Harvard-Architektur. Wenn ein Prozessor von Hand gebaut wird, ist eine RISC- Architektur ( Reduced Instruction Set Computer ) praktisch eine Voraussetzung. In unserem Fall bedeutet dies, dass die Anzahl der Opcodes gering ist und, was noch wichtiger ist, dass alle Anweisungen auf sehr ähnliche Weise verarbeitet werden.

Als Referenz verwendete der Wireworld-Computer eine transportgetriggerte Architektur , in der der einzige Befehl war MOVund Berechnungen durch Schreiben / Lesen von Sonderregistern durchgeführt wurden. Obwohl dieses Paradigma zu einer sehr einfach zu implementierenden Architektur führt, ist das Ergebnis auch unbrauchbar: Alle arithmetischen / logischen / bedingten Operationen erfordern drei Befehle. Uns war klar, dass wir eine viel weniger esoterische Architektur schaffen wollten.

Um unseren Prozessor einfach zu halten und gleichzeitig die Benutzerfreundlichkeit zu erhöhen, haben wir einige wichtige Designentscheidungen getroffen:

• Keine Register. Jede Adresse im RAM wird gleich behandelt und kann als Argument für jede Operation verwendet werden. In gewissem Sinne bedeutet dies, dass der gesamte RAM wie Register behandelt werden könnte. Dies bedeutet, dass es keine speziellen Lade- / Speicheranweisungen gibt.
• In ähnlicher Weise Memory-Mapping. Alles, was geschrieben oder gelesen werden kann, hat ein einheitliches Adressierungsschema. Dies bedeutet, dass der Programmzähler (PC) die Adresse 0 hat und der einzige Unterschied zwischen regulären Befehlen und Steuerflussbefehlen darin besteht, dass Steuerflussbefehle die Adresse 0 verwenden.
• Daten werden seriell übertragen und parallel gespeichert. Aufgrund der "elektronenbasierten" Natur unseres Computers sind Addition und Subtraktion wesentlich einfacher zu implementieren, wenn die Daten in serieller Little-Endian-Form (niedrigstwertiges Bit zuerst) übertragen werden. Durch serielle Daten entfällt außerdem die Notwendigkeit umständlicher Datenbusse, die sowohl sehr umfangreich als auch zeitaufwendig sind (damit die Daten zusammen bleiben, müssen alle "Fahrspuren" des Busses dieselbe Fahrverzögerung aufweisen).
• Harvard-Architektur, dh eine Unterteilung zwischen Programmspeicher (ROM) und Datenspeicher (RAM). Obwohl dies die Flexibilität des Prozessors verringert, hilft dies bei der Größenoptimierung: Die Länge des Programms ist viel größer als die Menge an RAM, die wir benötigen, sodass wir das Programm in ROM aufteilen und uns dann auf das Komprimieren des ROM konzentrieren können , was viel einfacher ist, wenn es schreibgeschützt ist.
• 16-Bit-Datenbreite. Dies ist die kleinste Zweierpotenz, die breiter ist als eine Standard-Tetris-Karte (10 Blöcke). Dies gibt uns einen Datenbereich von -32768 bis +32767 und eine maximale Programmlänge von 65536 Anweisungen. (2 ^ 8 = 256 Anweisungen reichen für die meisten einfachen Dinge aus, die ein Spielzeugprozessor ausführen soll, aber nicht Tetris.)
• Asynchroner Entwurf. Anstatt dass eine zentrale Uhr (oder äquivalent mehrere Uhren) das Timing des Computers bestimmt, werden alle Daten von einem "Taktsignal" begleitet, das sich parallel zu den Daten bewegt, wenn sie den Computer umfließen. Bestimmte Pfade können kürzer sein als andere, und während dies für einen zentral getakteten Entwurf Schwierigkeiten bereiten würde, kann ein asynchroner Entwurf leicht mit Operationen mit variabler Zeit umgehen.
• Alle Anweisungen sind gleich groß. Wir waren der Meinung, dass eine Architektur, in der jeder Befehl 1 Opcode mit 3 Operanden (Wert, Wert, Ziel) enthält, die flexibelste Option ist. Dies umfasst sowohl binäre Datenoperationen als auch bedingte Verschiebungen.
• Einfaches Adressierungsmodus-System. Eine Vielzahl von Adressierungsmodi ist sehr nützlich, um beispielsweise Arrays oder Rekursionen zu unterstützen. Mit einem relativ einfachen System ist es uns gelungen, mehrere wichtige Adressierungsmodi zu implementieren.

Eine Illustration unserer Architektur finden Sie im Übersichtsbeitrag.

Funktionalität und ALU-Operationen

Von hier aus galt es zu bestimmen, welche Funktionalität unser Prozessor haben sollte. Besonderes Augenmerk wurde auf die einfache Implementierung sowie die Vielseitigkeit der einzelnen Befehle gelegt.

Bedingte Bewegungen

Bedingte Bewegungen sind sehr wichtig und dienen sowohl als Kontrollfluss im kleinen als auch im großen Maßstab. "Klein" bezieht sich auf seine Fähigkeit, die Ausführung einer bestimmten Datenverschiebung zu steuern, während sich "groß" auf seine Verwendung als bedingte Sprungoperation bezieht, um den Steuerfluss auf ein beliebiges Stück Code zu übertragen. Es gibt keine dedizierten Sprungoperationen, da durch eine bedingte Verschiebung aufgrund der Speicherzuordnung sowohl Daten in den regulären RAM kopiert als auch eine Zieladresse auf den PC kopiert werden kann. Aus einem ähnlichen Grund haben wir uns auch dafür entschieden, sowohl auf bedingungslose Züge als auch auf bedingungslose Sprünge zu verzichten: Beide können als bedingter Zug mit einer Bedingung implementiert werden, die fest auf WAHR codiert ist.

Wir haben uns für zwei verschiedene Arten von bedingten Zügen entschieden: "move if not zero" ( MNZ) und "move if less than zero" ( MLZ). Funktionell wird MNZgeprüft, ob ein Bit in den Daten eine 1 ist, während MLZgeprüft wird, ob das Vorzeichenbit 1 ist. Sie sind für Gleichheiten bzw. Vergleiche nützlich. Der Grund haben wir uns für diese beide über anderen, wie „bewegen , wenn Null“ ( MEZ) oder „bewegen , wenn größer als Null“ ( MGZ) war , dass MEZwürde ein TRUE - Signal von einem leeren Signal erzeugt wird , während MGZeine komplexere Überprüfung ist, erfordert das die Vorzeichenbit ist 0, während mindestens ein anderes Bit 1 ist.

Arithmetik

Die nächstwichtigsten Anweisungen zur Steuerung des Prozessordesigns sind die Grundrechenarten. Wie bereits erwähnt, verwenden wir serielle Little-Endian-Daten, wobei die Wahl der Endianzahl von der Einfachheit der Additions- / Subtraktionsoperationen abhängt. Indem das niedrigstwertige Bit zuerst ankommt, können die Recheneinheiten das Übertragsbit leicht verfolgen.

Wir haben die 2-Komplement-Darstellung für negative Zahlen gewählt, da dies die Addition und Subtraktion konsistenter macht. Es ist erwähnenswert, dass der Wireworld-Computer die Ergänzung 1 verwendet hat.

Addition und Subtraktion sind das Ausmaß der systemeigenen Rechenunterstützung unseres Computers (abgesehen von Bitverschiebungen, die später erläutert werden). Andere Operationen wie die Multiplikation sind viel zu komplex, um von unserer Architektur verarbeitet zu werden, und müssen in Software implementiert werden.

Bitweise Operationen

Unser Prozessor verfügt über AND, ORund XORAnweisungen, die genau das tun, was Sie erwarten. Anstatt eine NOTAnweisung zu haben, haben wir uns für eine "and-not" ( ANT) Anweisung entschieden. Die Schwierigkeit bei der NOTAnweisung besteht wiederum darin, dass sie aus einem Signalmangel ein Signal erzeugen muss, was bei zellularen Automaten schwierig ist. Der ANTBefehl gibt nur dann 1 zurück, wenn das erste Argumentbit 1 und das zweite Argumentbit 0 ist. Dies NOT xist also gleichbedeutend mit ANT -1 x(sowie XOR -1 x). Darüber hinaus ANTist es vielseitig und hat seinen Hauptvorteil in der Maskierung: Im Falle des Tetris-Programms verwenden wir es, um Tetrominoes zu löschen.

Bitverschiebung

Die Bitverschiebungsoperationen sind die komplexesten Operationen, die von der ALU gehandhabt werden. Sie nehmen zwei Dateneingaben vor: einen Wert zum Verschieben und einen Betrag zum Verschieben. Trotz ihrer Komplexität (aufgrund des variablen Verschiebungsgrades) sind diese Vorgänge für viele wichtige Aufgaben von entscheidender Bedeutung, einschließlich der zahlreichen "grafischen" Vorgänge in Tetris. Bitverschiebungen würden auch als Grundlage für effiziente Multiplikations- / Divisionsalgorithmen dienen.

Unser Prozessor verfügt über drei Bitverschiebungsoperationen, "Verschieben nach links" ( SL), "Verschieben nach rechts logisch" ( SRL) und "Verschieben nach rechts arithmetisch" ( SRA). Die ersten beiden Bitverschiebungen ( SLund SRL) füllen die neuen Bits mit allen Nullen (was bedeutet, dass eine nach rechts verschobene negative Zahl nicht länger negativ ist). Wenn das zweite Argument der Verschiebung außerhalb des Bereichs von 0 bis 15 liegt, enthält das Ergebnis erwartungsgemäß alle Nullen. Bei der letzten Bitverschiebung behält SRAdie Bitverschiebung das Vorzeichen der Eingabe bei und wirkt daher als echte Division durch zwei.

Anleitung Pipelining

Jetzt ist es an der Zeit, über einige der wichtigsten Details der Architektur zu sprechen. Jeder CPU-Zyklus besteht aus den folgenden fünf Schritten:

1. Holen Sie sich den aktuellen Befehl aus dem ROM

Der aktuelle Wert des PCs wird verwendet, um die entsprechende Anweisung aus dem ROM abzurufen. Jeder Befehl hat einen Operationscode und drei Operanden. Jeder Operand besteht aus einem Datenwort und einem Adressierungsmodus. Diese Teile werden voneinander getrennt, wenn sie aus dem ROM gelesen werden.

Der Opcode besteht aus 4 Bits, um 16 eindeutige Opcodes zu unterstützen, von denen 11 zugewiesen sind:

0000  MNZ    Move if Not Zero
0001  MLZ    Move if Less than Zero
0010  ADD    ADDition
0011  SUB    SUBtraction
0100  AND    bitwise AND
0101  OR     bitwise OR
0110  XOR    bitwise eXclusive OR
0111  ANT    bitwise And-NoT
1000  SL     Shift Left
1001  SRL    Shift Right Logical
1010  SRA    Shift Right Arithmetic
1011  unassigned
1100  unassigned
1101  unassigned
1110  unassigned
1111  unassigned

2. Schreiben Sie das Ergebnis (falls erforderlich) der vorherigen Anweisung in den RAM

Abhängig von der Bedingung des vorherigen Befehls (z. B. dem Wert des ersten Arguments für eine bedingte Bewegung) wird ein Schreibvorgang ausgeführt. Die Adresse des Schreibvorgangs wird durch den dritten Operanden des vorherigen Befehls bestimmt.

Es ist wichtig zu beachten, dass das Schreiben nach dem Abrufen von Befehlen erfolgt. Dies führt zur Erzeugung eines Verzweigungsverzögerungsschlitzes, in dem der Befehl unmittelbar nach einem Verzweigungsbefehl (jede Operation, die auf den PC schreibt) anstelle des ersten Befehls am Verzweigungsziel ausgeführt wird.

In bestimmten Fällen (wie bei bedingungslosen Sprüngen) kann der Verzweigungsverzögerungsschlitz wegoptimiert werden. In anderen Fällen ist dies nicht möglich, und die Anweisung nach einer Verzweigung muss leer bleiben. Darüber hinaus bedeutet diese Art von Verzögerungsschlitz, dass Verzweigungen ein Verzweigungsziel verwenden müssen, das 1 Adresse unter dem tatsächlichen Zielbefehl liegt, um das auftretende PC-Inkrement zu berücksichtigen.

Kurz gesagt, da die Ausgabe des vorherigen Befehls nach dem Abrufen des nächsten Befehls in den RAM geschrieben wird, müssen bedingte Sprünge mit einem leeren Befehl versehen werden, sonst wird der PC für den Sprung nicht ordnungsgemäß aktualisiert.

3. Lesen Sie die Daten für die Argumente des aktuellen Befehls aus dem RAM

Wie bereits erwähnt, besteht jeder der drei Operanden aus einem Datenwort und einem Adressierungsmodus. Das Datenwort hat 16 Bit, die gleiche Breite wie der RAM. Der Adressierungsmodus beträgt 2 Bits.

Adressierungsmodi können für einen Prozessor wie diesen eine Quelle von erheblicher Komplexität sein, da viele reale Adressierungsmodi mehrstufige Berechnungen beinhalten (wie das Hinzufügen von Offsets). Gleichzeitig spielen vielseitige Adressierungsmodi eine wichtige Rolle für die Benutzerfreundlichkeit des Prozessors.

Wir wollten die Konzepte der Verwendung von fest codierten Zahlen als Operanden und der Verwendung von Datenadressen als Operanden vereinheitlichen. Dies führte zur Schaffung von zählerbasierten Adressierungsmodi: Der Adressierungsmodus eines Operanden ist einfach eine Zahl, die angibt, wie oft die Daten um eine RAM-Leseschleife gesendet werden sollen. Dies umfasst die sofortige, direkte, indirekte und doppelte indirekte Adressierung.

00  Immediate:  A hard-coded value. (no RAM reads)
01  Direct:  Read data from this RAM address. (one RAM read)
10  Indirect:  Read data from the address given at this address. (two RAM reads)
11  Double-indirect: Read data from the address given at the address given by this address. (three RAM reads)

Nachdem diese Dereferenzierung durchgeführt wurde, haben die drei Operanden des Befehls unterschiedliche Rollen. Der erste Operand ist normalerweise das erste Argument für einen binären Operator, dient jedoch auch als Bedingung, wenn der aktuelle Befehl eine bedingte Bewegung ist. Der zweite Operand dient als zweites Argument für einen Binäroperator. Der dritte Operand dient als Zieladresse für das Ergebnis des Befehls.

Da die ersten beiden Befehle als Daten und der dritte als Adresse dienen, werden die Adressierungsmodi in Abhängigkeit von der Position, an der sie verwendet werden, geringfügig unterschiedlich interpretiert. Der Direktmodus wird beispielsweise zum Lesen von Daten aus einer festen RAM - Adresse verwendet ein RAM-Lesevorgang ist erforderlich), aber der Sofortmodus wird zum Schreiben von Daten an eine feste RAM-Adresse verwendet (da keine RAM-Lesevorgänge erforderlich sind).

4. Berechnen Sie das Ergebnis

Der Operationscode und die ersten beiden Operanden werden an die ALU gesendet, um eine Binäroperation auszuführen. Für die arithmetischen, bitweisen und Verschiebungsoperationen bedeutet dies, dass die relevante Operation ausgeführt wird. Für die bedingten Züge bedeutet dies einfach die Rückgabe des zweiten Operanden.

Der Operationscode und der erste Operand werden verwendet, um die Bedingung zu berechnen, die bestimmt, ob das Ergebnis in den Speicher geschrieben wird oder nicht. Im Fall von bedingten Bewegungen bedeutet dies, entweder zu bestimmen, ob irgendein Bit im Operanden 1 (für MNZ) ist, oder zu bestimmen, ob das Vorzeichenbit 1 (für MLZ) ist. Wenn der Opcode keine bedingte Bewegung ist, wird immer geschrieben (die Bedingung ist immer wahr).

5. Inkrementieren Sie den Programmzähler

Schließlich wird der Programmzähler gelesen, inkrementiert und geschrieben.

Aufgrund der Position des PC-Inkrements zwischen dem Befehlslesevorgang und dem Befehlsschreibvorgang bedeutet dies, dass ein Befehl, der den PC um 1 inkrementiert, ein No-Op ist. Eine Anweisung, die den PC auf sich selbst kopiert, bewirkt, dass die nächste Anweisung zweimal hintereinander ausgeführt wird. Seien Sie jedoch gewarnt, dass mehrere PC-Anweisungen in einer Reihe komplexe Auswirkungen haben können, einschließlich Endlosschleifen, wenn Sie die Anweisungs-Pipeline nicht beachten.

Suche nach der Tetris-Versammlung

Wir haben eine neue Assemblersprache namens QFTASM für unseren Prozessor erstellt. Diese Assemblersprache entspricht 1: 1 dem Maschinencode im ROM des Computers.

Jedes QFTASM-Programm besteht aus einer Reihe von Anweisungen, eine pro Zeile. Jede Zeile ist folgendermaßen formatiert:

[line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

Opcode-Liste

Wie bereits erwähnt, werden vom Computer elf Opcodes unterstützt, von denen jeder drei Operanden hat:

MNZ [test] [value] [dest]  – Move if Not Zero; sets [dest] to [value] if [test] is not zero.
MLZ [test] [value] [dest]  – Move if Less than Zero; sets [dest] to [value] if [test] is less than zero.
ADD [val1] [val2] [dest]   – ADDition; store [val1] + [val2] in [dest].
SUB [val1] [val2] [dest]   – SUBtraction; store [val1] - [val2] in [dest].
AND [val1] [val2] [dest]   – bitwise AND; store [val1] & [val2] in [dest].
OR [val1] [val2] [dest]    – bitwise OR; store [val1] | [val2] in [dest].
XOR [val1] [val2] [dest]   – bitwise XOR; store [val1] ^ [val2] in [dest].
ANT [val1] [val2] [dest]   – bitwise And-NoT; store [val1] & (![val2]) in [dest].
SL [val1] [val2] [dest]    – Shift Left; store [val1] << [val2] in [dest].
SRL [val1] [val2] [dest]   – Shift Right Logical; store [val1] >>> [val2] in [dest]. Doesn't preserve sign.
SRA [val1] [val2] [dest]   – Shift Right Arithmetic; store [val1] >> [val2] in [dest], while preserving sign.

Adressierungsmodi

Jeder der Operanden enthält sowohl einen Datenwert als auch eine Adressierungsbewegung. Der Datenwert wird durch eine Dezimalzahl im Bereich von -32768 bis 32767 beschrieben. Der Adressierungsmodus wird durch ein Ein-Buchstaben-Präfix vor dem Datenwert beschrieben.

mode    name               prefix
0       immediate          (none)
1       direct             A
2       indirect           B
3       double-indirect    C 

Beispielcode

Fibonacci-Sequenz in fünf Zeilen:

0. MLZ -1 1 1;    initial value
1. MLZ -1 A2 3;   start loop, shift data
2. MLZ -1 A1 2;   shift data
3. MLZ -1 0 0;    end loop
4. ADD A2 A3 1;   branch delay slot, compute next term

Dieser Code berechnet die Fibonacci-Sequenz, wobei die RAM-Adresse 1 den aktuellen Term enthält. Es läuft nach 28657 schnell über.

Gray-Code:

0. MLZ -1 5 1;      initial value for RAM address to write to
1. SUB A1 5 2;      start loop, determine what binary number to covert to Gray code
2. SRL A2 1 3;      shift right by 1
3. XOR A2 A3 A1;    XOR and store Gray code in destination address
4. SUB B1 42 4;     take the Gray code and subtract 42 (101010)
5. MNZ A4 0 0;      if the result is not zero (Gray code != 101010) repeat loop
6. ADD A1 1 1;      branch delay slot, increment destination address

Dieses Programm berechnet den Gray-Code und speichert den Code ab Adresse 5 in aufeinanderfolgenden Adressen. Dieses Programm verwendet mehrere wichtige Funktionen wie die indirekte Adressierung und einen bedingten Sprung. Es wird angehalten, sobald der resultierende Gray-Code ist 101010, was für die Eingabe 51 an der Adresse 56 geschieht.

Online-Dolmetscher

El'endia Starman hat ein sehr nützliches Online - Interpreter erstellt hier . Sie können den Code schrittweise durchlaufen, Haltepunkte festlegen, manuell in den RAM schreiben und den RAM als Anzeige anzeigen.

Cogol

Nachdem die Architektur und die Assemblersprache definiert waren, war der nächste Schritt auf der "Software" -Seite des Projekts die Erstellung einer höheren Sprache, die für Tetris geeignet ist. So habe ich Cogol geschaffen . Der Name ist ein Wortspiel auf "COBOL" und eine Abkürzung für "C of Game of Life", obwohl es erwähnenswert ist, dass Cogol für C ist, was unser Computer für einen tatsächlichen Computer ist.

Cogol existiert auf einer Ebene knapp über der Assemblersprache. Im Allgemeinen entsprechen die meisten Zeilen in einem Cogol-Programm jeweils einer einzelnen Assemblierungszeile, es gibt jedoch einige wichtige Merkmale der Sprache:

• Zu den grundlegenden Funktionen gehören benannte Variablen mit Zuweisungen und Operatoren mit besser lesbarer Syntax. Wird zum Beispiel, ADD A1 A2 3wenn z = x + y;der Compiler Variablen auf Adressen abbildet.
• Looping - Konstrukte wie if(){}, while(){}und do{}while();so die Compiler Verzweigung Griffe.
• Eindimensionale Arrays (mit Zeigerarithmetik), die für die Tetris-Karte verwendet werden.
• Unterprogramme und ein Aufrufstapel. Diese sind nützlich, um das Duplizieren großer Codestücke zu verhindern und die Rekursion zu unterstützen.

Der Compiler (den ich von Grund auf geschrieben habe) ist sehr einfach / naiv, aber ich habe versucht, einige der Sprachkonstrukte von Hand zu optimieren, um eine kurze kompilierte Programmlänge zu erreichen.

Hier einige kurze Übersichten über die Funktionsweise verschiedener Sprachfunktionen:

Tokenisierung

Der Quellcode wird linear getokenet (Single-Pass), wobei einfache Regeln verwendet werden, welche Zeichen innerhalb eines Tokens benachbart sein dürfen. Wenn ein Zeichen angetroffen wird, das nicht neben dem letzten Zeichen des aktuellen Tokens stehen kann, gilt das aktuelle Token als vollständig und das neue Zeichen beginnt mit einem neuen Token. Einige Zeichen (wie z. B. {oder ,) dürfen nicht neben anderen Zeichen stehen und sind daher ihre eigenen Zeichen. Andere (wie >oder =) nur in andere Zeichen innerhalb ihrer Klasse sein benachbarten erlaubt, und kann somit bilden Token wie >>>, ==, oder >=, aber nicht wie =2. Leerzeichen erzwingen eine Grenze zwischen Token, sind jedoch selbst nicht im Ergebnis enthalten. Das am schwierigsten zu tokenisierende Zeichen ist- weil es sowohl Subtraktion als auch unäre Negation darstellen kann und daher eine spezielle Umhüllung erfordert.

Parsing

Das Parsen erfolgt ebenfalls in einem Durchgang. Der Compiler verfügt über Methoden zum Behandeln der verschiedenen Sprachkonstrukte, und Token werden aus der globalen Tokenliste entfernt, wenn sie von den verschiedenen Compilermethoden verwendet werden. Wenn der Compiler jemals ein Token sieht, das er nicht erwartet, wird ein Syntaxfehler ausgelöst.

Globale Speicherzuordnung

Der Compiler weist jeder globalen Variablen (Wort oder Array) eine eigene zugewiesene RAM-Adresse (n) zu. Es ist erforderlich, alle Variablen mit dem Schlüsselwort zu deklarieren my, damit der Compiler Speicherplatz dafür reservieren kann. Viel cooler als die genannten globalen Variablen ist die Verwaltung des Arbeitsspeichers. Viele Befehle (insbesondere Bedingungen und viele Array-Zugriffe) erfordern temporäre "Scratch" -Adressen zum Speichern von Zwischenberechnungen. Während des Kompilierungsprozesses weist der Compiler nach Bedarf Arbeitsadressen zu und hebt die Zuordnung auf. Wenn der Compiler mehr Arbeitsspeicheradressen benötigt, wird mehr Arbeitsspeicher als Arbeitsspeicheradressen zugewiesen. Ich glaube, es ist typisch für ein Programm, nur ein paar Arbeitsadressen zu benötigen, obwohl jede Arbeitsadresse viele Male verwendet wird.

IF-ELSE Aussagen

Die Syntax für if-elseAnweisungen ist die Standard-C-Form:

other code
if (cond) {
  first body
} else {
  second body
}
other code

Bei der Konvertierung in QFTASM sieht der Code folgendermaßen aus:

other code
condition test
conditional jump
first body
unconditional jump
second body (conditional jump target)
other code (unconditional jump target)

Wenn der erste Körper ausgeführt wird, wird der zweite Körper übersprungen. Wenn der erste Körper übersprungen wird, wird der zweite Körper ausgeführt.

In der Baugruppe ist ein Zustandstest normalerweise nur eine Subtraktion, und das Vorzeichen des Ergebnisses bestimmt, ob der Sprung ausgeführt oder der Körper ausgeführt werden soll. Eine MLZAnweisung wird verwendet, um Ungleichungen wie >oder zu behandeln <=. Eine MNZAnweisung wird zum Behandeln verwendet ==, da sie über den Körper springt, wenn die Differenz nicht Null ist (und daher, wenn die Argumente nicht gleich sind). Bedingungen für mehrere Ausdrücke werden derzeit nicht unterstützt.

Wenn die elseAnweisung weggelassen wird, wird auch der unbedingte Sprung weggelassen, und der QFTASM-Code sieht folgendermaßen aus:

other code
condition test
conditional jump
body
other code (conditional jump target)

WHILE Aussagen

Die Syntax für whileAnweisungen ist auch die Standard-C-Form:

other code
while (cond) {
  body
}
other code

Bei der Konvertierung in QFTASM sieht der Code folgendermaßen aus:

other code
unconditional jump
body (conditional jump target)
condition test (unconditional jump target)
conditional jump
other code

Die Bedingungsprüfung und der bedingte Sprung befinden sich am Ende des Blocks, dh sie werden nach jeder Ausführung des Blocks erneut ausgeführt. Wenn die Bedingung false zurückgibt, wird der Body nicht wiederholt und die Schleife endet. Während des Starts der Schleifenausführung springt der Steuerungsfluss über den Schleifenkörper zum Bedingungscode, sodass der Körper niemals ausgeführt wird, wenn die Bedingung das erste Mal falsch ist.

Eine MLZAnweisung wird verwendet, um Ungleichungen wie >oder zu behandeln <=. Anders als bei ifAnweisungen wird eine MNZAnweisung zum Behandeln verwendet !=, da sie zum Hauptteil springt, wenn die Differenz nicht Null ist (und daher die Argumente nicht gleich sind).

DO-WHILE Aussagen

Der einzige Unterschied zwischen whileund do-whilebesteht darin, dass der do-whileKörper einer Schleife zunächst nicht übersprungen wird, sodass er immer mindestens einmal ausgeführt wird. Ich verwende im Allgemeinen do-whileAnweisungen, um ein paar Zeilen Assembler-Code zu speichern, wenn ich weiß, dass die Schleife niemals vollständig übersprungen werden muss.

Arrays

Eindimensionale Arrays werden als zusammenhängende Speicherblöcke implementiert. Alle Arrays haben aufgrund ihrer Deklaration eine feste Länge. Arrays werden folgendermaßen deklariert:

my alpha[3];               # empty array
my beta[11] = {3,2,7,8};   # first four elements are pre-loaded with those values

Für das Array ist dies eine mögliche RAM-Zuordnung, die zeigt, wie die Adressen 15-18 für das Array reserviert sind:

15: alpha
16: alpha[0]
17: alpha[1]
18: alpha[2]

Die beschriftete Adresse alphaist mit einem Zeiger auf den Speicherort von gefüllt. alpha[0]In diesem Fall enthält die Adresse 15 den Wert 16. Die alphaVariable kann im Cogol-Code verwendet werden, möglicherweise als Stapelzeiger, wenn Sie dieses Array als Stapel verwenden möchten .

Der Zugriff auf die Elemente eines Arrays erfolgt mit der Standardnotation array[index]. Wenn der Wert von indexeine Konstante ist, wird diese Referenz automatisch mit der absoluten Adresse dieses Elements gefüllt. Andernfalls führt es eine Zeigerarithmetik (nur Addition) durch, um die gewünschte absolute Adresse zu finden. Es ist auch möglich, Indizierungen zu verschachteln, wie z alpha[beta[1]].

Unterprogramme und Aufruf

Subroutinen sind Codeblöcke, die aus mehreren Kontexten aufgerufen werden können. Sie verhindern die Vervielfältigung von Code und ermöglichen die Erstellung rekursiver Programme. Hier ist ein Programm mit einer rekursiven Subroutine zum Generieren von Fibonacci-Zahlen (im Grunde der langsamste Algorithmus):

# recursively calculate the 10th Fibonacci number
call display = fib(10).sum;
sub fib(cur,sum) {
  if (cur <= 2) {
    sum = 1;
    return;
  }
  cur--;
  call sum = fib(cur).sum;
  cur--;
  call sum += fib(cur).sum;
}

Eine Unterroutine wird mit dem Schlüsselwort deklariert sub, und eine Unterroutine kann an einer beliebigen Stelle im Programm platziert werden. Jedes Unterprogramm kann mehrere lokale Variablen haben, die als Teil seiner Argumentliste deklariert werden. Diesen Argumenten können auch Standardwerte zugewiesen werden.

Um rekursive Aufrufe zu verarbeiten, werden die lokalen Variablen eines Unterprogramms auf dem Stapel gespeichert. Die letzte statische Variable im RAM ist der Aufrufstapelzeiger, und der gesamte darauf folgende Speicher dient als Aufrufstapel. Wenn ein Unterprogramm aufgerufen wird, erstellt es einen neuen Frame auf dem Aufrufstapel, der alle lokalen Variablen sowie die Rücksprungadresse (ROM-Adresse) enthält. Jedes Unterprogramm im Programm erhält eine einzelne statische RAM-Adresse als Zeiger. Dieser Zeiger gibt die Position des "aktuellen" Aufrufs des Unterprogramms im Aufrufstapel an. Das Referenzieren einer lokalen Variablen erfolgt unter Verwendung des Werts dieses statischen Zeigers plus eines Offsets, um die Adresse dieser bestimmten lokalen Variablen anzugeben. Im Aufrufstapel ist auch der vorherige Wert des statischen Zeigers enthalten. Hier'

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

fib map:
0: return
1: previous_call
2: cur
3: sum

Das Interessante an Unterprogrammen ist, dass sie keinen bestimmten Wert zurückgeben. Vielmehr können alle lokalen Variablen des Unterprogramms gelesen werden, nachdem das Unterprogramm ausgeführt wurde, so dass eine Vielzahl von Daten aus einem Unterprogrammaufruf extrahiert werden kann. Dies wird erreicht, indem der Zeiger für diesen spezifischen Aufruf der Unterroutine gespeichert wird, der dann verwendet werden kann, um eine der lokalen Variablen innerhalb des (kürzlich freigegebenen) Stapelrahmens wiederherzustellen.

Es gibt mehrere Möglichkeiten, eine Unterroutine mit dem callSchlüsselwort aufzurufen :

call fib(10);   # subroutine is executed, no return vaue is stored

call pointer = fib(10);   # execute subroutine and return a pointer
display = pointer.sum;    # access a local variable and assign it to a global variable

call display = fib(10).sum;   # immediately store a return value

call display += fib(10).sum;   # other types of assignment operators can also be used with a return value

Es können beliebig viele Werte als Argumente für einen Unterprogrammaufruf angegeben werden. Jedes Argument, das nicht angegeben wird, wird mit seinem Standardwert (falls vorhanden) ausgefüllt. Ein Argument, das nicht angegeben wird und keinen Standardwert hat, wird nicht gelöscht (um Anweisungen / Zeit zu sparen), sodass es zu Beginn des Unterprogramms möglicherweise einen beliebigen Wert annehmen kann.

Zeiger sind eine Möglichkeit, auf mehrere lokale Variablen eines Unterprogramms zuzugreifen. Es ist jedoch zu beachten, dass der Zeiger nur temporär ist: Die Daten, auf die der Zeiger zeigt, werden zerstört, wenn ein anderer Unterprogrammaufruf erfolgt.

Etiketten debuggen

Jeder {...}Codeblock in einem Cogol Programm kann durch ein Mehrwort beschreibende Bezeichnung vorangestellt werden. Diese Bezeichnung wird als Kommentar in den kompilierten Assemblycode eingefügt und kann beim Debuggen sehr hilfreich sein, da sie das Auffinden bestimmter Codestücke erleichtert.

Slot-Optimierung für Verzweigungsverzögerung

Um die Geschwindigkeit des kompilierten Codes zu verbessern, führt der Cogol-Compiler als letzten Durchlauf des QFTASM-Codes eine grundlegende Optimierung der Verzögerungszeiträume durch. Für jeden unbedingten Sprung mit einem leeren Verzweigungsverzögerungsschlitz kann der Verzögerungsschlitz durch den ersten Befehl am Sprungziel gefüllt werden, und das Sprungziel wird um eins erhöht, um auf den nächsten Befehl zu zeigen. Dies spart im Allgemeinen einen Zyklus jedes Mal, wenn ein bedingungsloser Sprung ausgeführt wird.

Schreiben des Tetris-Codes in Cogol

Das endgültige Tetris-Programm wurde in Cogol geschrieben. Den Quellcode finden Sie hier . Der kompilierte QFTASM-Code ist hier verfügbar . Der Einfachheit halber wird hier ein Permalink bereitgestellt: Tetris in QFTASM . Da das Ziel darin bestand, den Assembly-Code (nicht den Cogol-Code) zu verwenden, ist der resultierende Cogol-Code unhandlich. Viele Teile des Programms befanden sich normalerweise in Unterprogrammen, aber diese Unterprogramme waren tatsächlich kurz genug, um den Code zu duplizieren, der über die Befehle gespeichert wurdecallAussagen. Der endgültige Code enthält neben dem Hauptcode nur ein Unterprogramm. Darüber hinaus wurden viele Arrays entfernt und entweder durch eine entsprechend lange Liste einzelner Variablen oder durch viele fest codierte Nummern im Programm ersetzt. Der endgültig kompilierte QFTASM-Code steht unter 300 Anweisungen, obwohl er nur geringfügig länger als die Cogol-Quelle selbst ist.

Teil 5: Montage, Übersetzung und die Zukunft

Mit unserem Assembler-Programm vom Compiler ist es Zeit, ein ROM für den Varlife-Computer zusammenzustellen und alles in ein großes GoL-Muster zu übersetzen!

Versammlung

Das Assemblieren des Assemblierungsprogramms in ein ROM erfolgt auf die gleiche Weise wie bei der herkömmlichen Programmierung: Jeder Befehl wird in ein binäres Äquivalent übersetzt, und diese werden dann zu einem großen binären Blob verkettet, den wir als ausführbare Datei bezeichnen. Für uns besteht der einzige Unterschied darin, dass ein binärer Blob in Varlife-Schaltkreise übersetzt und an den Computer angeschlossen werden muss.

K Zhang hat CreateROM.py geschrieben , ein Python-Skript für Golly, das die Assemblierung und Übersetzung übernimmt. Es ist ziemlich einfach: Es nimmt ein Assemblerprogramm aus der Zwischenablage, setzt es in eine Binärdatei zusammen und übersetzt diese Binärdatei in eine Schaltungsanordnung. Hier ist ein Beispiel mit einem einfachen Primalitätstester, der im Skript enthalten ist:

#0. MLZ -1 3 3;
#1. MLZ -1 7 6; preloadCallStack
#2. MLZ -1 2 1; beginDoWhile0_infinite_loop
#3. MLZ -1 1 4; beginDoWhile1_trials
#4. ADD A4 2 4;
#5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
#6. SUB A5 A4 5;
#7. SUB 0 A5 2;
#8. MLZ A2 5 0;
#9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
#10. MLZ A5 3 0;
#11. MNZ 0 0 0; endDoWhile1_trials
#12. SUB A4 A3 2;
#13. MNZ A2 15 0; beginIf3_prime_found
#14. MNZ 0 0 0;
#15. MLZ -1 A3 1; endIf3_prime_found
#16. ADD A3 2 3;
#17. MLZ -1 3 0;
#18. MLZ -1 1 4; endDoWhile0_infinite_loop

Dies erzeugt die folgende Binärdatei:

0000000000000001000000000000000000010011111111111111110001
0000000000000000000000000000000000110011111111111111110001
0000000000000000110000000000000000100100000000000000110010
0000000000000000010100000000000000110011111111111111110001
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011110100000000000000100000
0000000000000000100100000000000000110100000000000001000011
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000110100000000000001010001
0000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000001010100000000000000100001
0000000000000000100100000000000001010000000000000000000011
0000000000000001010100000000000001000100000000000001010011
0000000000000001010100000000000000110011111111111111110001
0000000000000001000000000000000000100100000000000001000010
0000000000000001000000000000000000010011111111111111110001
0000000000000000010000000000000000100011111111111111110001
0000000000000001100000000000000001110011111111111111110001
0000000000000000110000000000000000110011111111111111110001

In Varlife-Schaltungen sieht das so aus:

Das ROM wird dann mit dem Computer verbunden, der in Varlife ein voll funktionsfähiges Programm bildet. Aber wir sind noch nicht fertig ...

Übersetzung zum Spiel des Lebens

Die ganze Zeit haben wir in verschiedenen Abstraktionsebenen über der Basis von Game of Life gearbeitet. Aber jetzt ist es Zeit, den Vorhang der Abstraktion zurückzuziehen und unsere Arbeit in ein Game of Life-Muster zu übersetzen. Wie bereits erwähnt, verwenden wir OTCA Metapixel als Basis für Varlife. Der letzte Schritt besteht also darin, jede Zelle in Varlife in ein Metapixel in Game of Life umzuwandeln.

Zum Glück wird Golly mit einem Skript ( metafier.py ) ausgeliefert, das Muster in verschiedenen Regelsätzen über das OTCA-Metapixel in Game of Life-Muster konvertieren kann. Leider ist es nur zum Konvertieren von Mustern mit einem einzigen globalen Regelsatz vorgesehen, sodass es in Varlife nicht funktioniert. Ich habe eine modifizierte Version geschrieben , die dieses Problem behebt, sodass die Regel für jedes Metapixel für Varlife zellenweise generiert wird.

Unser Computer (mit dem Tetris-ROM) hat also einen Begrenzungsrahmen von 1.436 x 5.082. Von den 7.297.752 Zellen in dieser Box sind 6.075.811 leer, was eine tatsächliche Bevölkerungszahl von 1.221.941 ergibt. Jede dieser Zellen muss in ein OTCA-Metapixel übersetzt werden, das einen Begrenzungsrahmen von 2048 x 2048 und eine Grundgesamtheit von 64.691 (für ein EIN-Metapixel) oder 23.920 (für ein AUS-Metapixel) aufweist. Das heißt, das Endprodukt hat einen Begrenzungsrahmen von 2.940.928 x 10.407.936 (plus einige Tausend zusätzliche für die Grenzen der Metapixel) mit einer Bevölkerung zwischen 29.228.828.720 und 79.048.585.231. Bei 1 Bit pro lebender Zelle sind zwischen 27 und 74 GiB erforderlich, um den gesamten Computer und das ROM darzustellen.

Ich habe diese Berechnungen hier eingefügt, weil ich sie vor dem Starten des Skripts nicht ausgeführt habe und sehr schnell nicht mehr genügend Arbeitsspeicher auf meinem Computer vorhanden ist. Nach einem in Panik geratenen killBefehl nahm ich eine Änderung am Metafier-Skript vor. Nach jeweils 10 Zeilen Metapixel wird das Muster auf der Festplatte gespeichert (als gezippte RLE-Datei) und das Raster wird geleert. Dies erhöht die Laufzeit der Übersetzung und beansprucht mehr Speicherplatz, hält jedoch die Speichernutzung in einem akzeptablen Rahmen. Da Golly ein erweitertes RLE-Format verwendet, das die Position des Musters enthält, erhöht dies die Komplexität beim Laden des Musters nicht. Öffnen Sie einfach alle Musterdateien auf derselben Ebene.

K Zhang baute auf dieser Arbeit auf und erstellte ein effizienteres Metafier-Skript , das das MacroCell-Dateiformat verwendet, das für große Muster effizienter als RLE ist. Dieses Skript wird erheblich schneller ausgeführt (einige Sekunden im Vergleich zu mehreren Stunden für das ursprüngliche Metafier-Skript), erzeugt eine erheblich geringere Ausgabe (121 KB gegenüber 1,7 GB) und kann den gesamten Computer und das ROM auf einen Schlag metafizieren, ohne dass eine massive Menge benötigt wird der Erinnerung. Es nutzt die Tatsache aus, dass MacroCell-Dateien Bäume codieren, die die Muster beschreiben. Durch die Verwendung einer benutzerdefinierten Vorlagendatei werden die Metapixel in den Baum vorgeladen, und nach einigen Berechnungen und Änderungen für die Nachbarerkennung kann das Varlife-Muster einfach angehängt werden.

Die Pattern-Datei des gesamten Computers und ROMs in Game of Life finden Sie hier .

Die Zukunft des Projekts

Jetzt, wo wir Tetris gemacht haben, sind wir fertig, richtig? Nicht annähernd. Wir haben mehrere weitere Ziele für dieses Projekt, auf die wir hinarbeiten:

• muddyfish und Kritixi Lithos arbeiten weiter an der höheren Sprache, die zu QFTASM kompiliert wird.
• El'endia Starman arbeitet an Upgrades für den Online-QFTASM-Interpreter.
• quartata arbeitet an einem GCC-Backend, das die Kompilierung von freistehendem C- und C ++ - Code (und möglicherweise anderen Sprachen wie Fortran, D oder Objective-C) in QFTASM über GCC ermöglicht. Auf diese Weise können anspruchsvollere Programme in einer vertrauteren Sprache erstellt werden, allerdings ohne eine Standardbibliothek.
• Eine der größten Hürden, die wir überwinden müssen, bevor wir weitere Fortschritte erzielen können, ist die Tatsache, dass unsere Tools keinen positionsunabhängigen Code (z. B. relative Sprünge) ausgeben können. Ohne PIC können wir keine Verknüpfungen herstellen, sodass wir die Vorteile der Verknüpfung mit vorhandenen Bibliotheken verpassen. Wir arbeiten daran, einen Weg zu finden, um PIC richtig zu machen.
• Wir diskutieren das nächste Programm, das wir für den QFT-Computer schreiben möchten. Im Moment sieht Pong wie ein schönes Tor aus.

Teil 6: Der neuere Compiler für QFTASM

Obwohl Cogol für eine rudimentäre Tetris-Implementierung ausreicht, ist es zu einfach und zu niedrig für die allgemeine Programmierung auf einer leicht lesbaren Ebene. Wir haben im September 2016 mit der Arbeit an einer neuen Sprache begonnen. Die Fortschritte in der Sprache waren langsam, da sowohl Fehler als auch das wirkliche Leben schwer zu verstehen waren.

Wir haben eine einfache Sprache mit einer ähnlichen Syntax wie Python erstellt, einschließlich eines einfachen Typsystems, Subroutinen, die Rekursions- und Inline-Operatoren unterstützen. Der Compiler von Text zu QFTASM wurde mit 4 Schritten erstellt: dem Tokenizer, dem Grammatikbaum, einem High-Level-Compiler und einem Low-Level-Compiler.

Der Tokenizer

Die Entwicklung wurde mit Python unter Verwendung der integrierten Tokeniser-Bibliothek gestartet, was bedeutet, dass dieser Schritt ziemlich einfach war. Es waren nur wenige Änderungen an der Standardausgabe erforderlich, darunter das Entfernen von Kommentaren (aber nicht von #includes).

Der Grammatikbaum

Der Grammatikbaum wurde so erstellt, dass er leicht erweiterbar ist, ohne dass Quellcode geändert werden muss.

Die Baumstruktur wird in einer XML-Datei gespeichert, die die Struktur der Knoten enthält, aus denen der Baum bestehen kann, und wie sie mit anderen Knoten und Token zusammengesetzt sind.

Die Grammatik sollte sowohl wiederholte als auch optionale Knoten unterstützen. Dies wurde durch die Einführung von Meta-Tags erreicht, die beschreiben, wie Token gelesen werden sollten.

Die generierten Token werden dann anhand der Grammatikregeln analysiert, sodass die Ausgabe einen Baum von Grammatikelementen wie subs und bildet generic_variables, die wiederum andere Grammatikelemente und Token enthalten.

Kompilierung in High-Level-Code

Jedes Merkmal der Sprache muss in der Lage sein, zu Konstrukten auf hoher Ebene kompiliert zu werden. Dazu gehören assign(a, 12) und call_subroutine(is_prime, call_variable=12, return_variable=temp_var). Features wie das Inlining von Elementen werden in diesem Segment ausgeführt. Diese werden als operators definiert und sind insofern besonders, als sie jedes Mal eingebettet werden, wenn ein Operator wie +oder %verwendet wird. Aus diesem Grund sind sie eingeschränkter als normaler Code - sie können weder einen eigenen Operator noch einen Operator verwenden, der auf dem zu definierenden beruht.

Während des Inlinings werden die internen Variablen durch die aufgerufenen Variablen ersetzt. Das dreht sich tatsächlich

operator(int a + int b) -> int c
    return __ADD__(a, b)
int i = 3+3

in

int i = __ADD__(3, 3)

Dieses Verhalten kann jedoch nachteilig und fehleranfällig sein, wenn die Eingangsvariable und die Ausgangsvariable auf dieselbe Stelle im Speicher verweisen. Um das "sicherere" Verhalten zu verwenden, unsafepasst das Schlüsselwort den Kompilierungsprozess so an, dass zusätzliche Variablen erstellt und nach Bedarf in und aus der Inline kopiert werden.

Arbeitsvariablen und komplexe Operationen

Mathematische Operationen wie a += (b + c) * 4können nicht ohne Verwendung zusätzlicher Speicherzellen berechnet werden. Der High-Level-Compiler behandelt dies, indem er die Operationen in verschiedene Abschnitte unterteilt:

scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

Dies führt in das Konzept der Scratch-Variablen ein, die zum Speichern von Zwischeninformationen von Berechnungen verwendet werden. Sie werden nach Bedarf zugewiesen und nach Abschluss des Vorgangs dem allgemeinen Pool zugewiesen. Dies verringert die Anzahl der für die Verwendung erforderlichen Arbeitsspeicherplätze. Arbeitsvariablen werden als globale Variablen betrachtet.

Jede Unterroutine verfügt über einen eigenen Variablenspeicher, in dem eine Referenz auf alle von der Unterroutine verwendeten Variablen sowie auf deren Typ gespeichert wird. Am Ende der Kompilierung werden sie vom Beginn des Speichers an in relative Offsets übersetzt und erhalten dann die tatsächlichen Adressen im RAM.

RAM-Struktur

Program counter
Subroutine locals
Operator locals (reused throughout)
Scratch variables
Result variable
Stack pointer
Stack
...

Low-Level-Kompilierung

Das einzige , was das niedrige Niveau Compiler hat zu behandeln sind sub, call_sub, return, assign, ifund while. Dies ist eine stark reduzierte Liste von Aufgaben, die einfacher in QFTASM-Anweisungen übersetzt werden können.

sub

Dies lokalisiert den Anfang und das Ende einer benannten Unterroutine. Der Low-Level-Compiler fügt Labels hinzu und fügt im Falle der mainSubroutine einen Exit-Befehl hinzu (Sprung zum Ende des ROM).

if und while

Sowohl die whileals auch die ifLow-Level-Interpreter sind ziemlich einfach: Sie erhalten Zeiger auf ihre Bedingungen und springen abhängig von ihnen. whileSchleifen unterscheiden sich geringfügig darin, dass sie als kompiliert werden

...
condition
jump to check
code
condition
if condtion: jump to code
...

call_sub und return

Im Gegensatz zu den meisten Architekturen bietet der Computer, für den wir kompilieren, keine Hardware-Unterstützung für das Pushen und Poppen von einem Stapel. Dies bedeutet, dass sowohl das Schieben als auch das Herausspringen aus dem Stapel zwei Anweisungen erfordern. Im Falle eines Poppings dekrementieren wir den Stapelzeiger und kopieren den Wert in eine Adresse. Beim Pushen kopieren wir einen Wert von einer Adresse in die Adresse am aktuellen Stapelzeiger und erhöhen ihn dann.

Alle Locals für ein Unterprogramm werden an einem festen Ort im RAM gespeichert, der zur Kompilierungszeit bestimmt wird. Damit die Rekursion funktioniert, werden zu Beginn eines Aufrufs alle Gebietsschemas für eine Funktion auf dem Stapel abgelegt. Dann werden die Argumente der Unterroutine an ihre Position im lokalen Speicher kopiert. Der Wert der Rücksprungadresse wird in den Stapel geschrieben und die Unterroutine ausgeführt.

Wenn eine returnAnweisung angetroffen wird, wird die Oberseite des Stapels entfernt und der Programmzähler auf diesen Wert gesetzt. Die Werte für die Locals des aufrufenden Unterprogramms werden vom Stapel genommen und in ihre vorherige Position gebracht.

assign

Variablenzuweisungen sind am einfachsten zu kompilieren: Sie nehmen eine Variable und einen Wert und kompilieren sie in eine einzelne Zeile: MLZ -1 VALUE VARIABLE

Sprungziele zuweisen

Schließlich erarbeitet der Compiler die Sprungziele für an Anweisungen angehängte Bezeichnungen. Die absolute Position von Beschriftungen wird bestimmt und dann werden Verweise auf diese Beschriftungen durch diese Werte ersetzt. Die Etiketten selbst werden aus dem Code entfernt und schließlich werden dem kompilierten Code Anweisungsnummern hinzugefügt.

Beispiel für eine schrittweise Zusammenstellung

Nachdem wir alle Phasen durchlaufen haben, gehen wir Schritt für Schritt durch den eigentlichen Kompilierungsprozess für ein tatsächliches Programm.

#include stdint

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, einfach genug. Es soll , dass am Ende des Programms offensichtlich a = 8, b = 12, c = 96. Lassen Sie uns zunächst die relevanten Teile von stdint.txt:

operator (int a + int b) -> int
    return __ADD__(a, b)

operator (int a - int b) -> int
    return __SUB__(a, b)

operator (int a < int b) -> bool
    bool rtn = 0
    rtn = __MLZ__(a-b, 1)
    return rtn

unsafe operator (int a * int b) -> int
    int rtn = 0
    for (int i = 0; i < b; i+=1)
        rtn += a
    return rtn

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, etwas komplizierter. Lassen Sie uns auf den Tokenizer gehen und sehen, was herauskommt. Zu diesem Zeitpunkt haben wir nur einen linearen Fluss von Token ohne irgendeine Form von Struktur

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP )
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT     
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP )
...

Jetzt werden alle Token durch den Grammatik-Parser geführt und es wird ein Baum mit den Namen der einzelnen Abschnitte ausgegeben. Dies zeigt die übergeordnete Struktur, wie sie vom Code gelesen wird.

GrammarTree file
 'stmts': [GrammarTree stmts_0
  '_block_name': 'inline'
  'inline': GrammarTree inline
   '_block_name': 'two_op'
   'type_var': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'a'
    '_global': False

   'operator': GrammarTree operator
    '_block_name': '+'

   'type_var_2': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'b'
    '_global': False
   'rtn_type': 'int'
   'stmts': GrammarTree stmts
    ...

Dieser Grammatikbaum richtet Informationen ein, die vom Compiler auf hoher Ebene analysiert werden sollen. Es enthält Informationen wie Strukturtypen und Attribute einer Variablen. Der Grammatikbaum nimmt dann diese Informationen und weist die Variablen zu, die für die Unterprogramme benötigt werden. Der Baum fügt auch alle Inlines ein.

('sub', 'start', 'main')
('assign', int main_a, 8)
('assign', int main_b, 12)
('assign', int op(*:rtn), 0)
('assign', int op(*:i), 0)
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'start', 1, 'for')
('call_sub', '__ADD__', [int op(*:rtn), int main_a], int op(*:rtn))
('call_sub', '__ADD__', [int op(*:i), 1], int op(*:i))
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'end', 1, global bool scratch_2)
('assign', int main_c, int op(*:rtn))
('sub', 'end', 'main')

Als nächstes muss der Low-Level-Compiler diese High-Level-Darstellung in QFTASM-Code konvertieren. Variablen werden Speicherorte im RAM wie folgt zugewiesen:

int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int <result>
global int <stack>

Die einfachen Anweisungen werden dann zusammengestellt. Schließlich werden Anweisungsnummern hinzugefügt, was zu ausführbarem QFTASM-Code führt.

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

Die Syntax

Jetzt, da wir die nackte Sprache haben, müssen wir tatsächlich ein kleines Programm darin schreiben. Wir verwenden wie Python Einrückungen, die logische Blöcke aufteilen und den Ablauf steuern. Das bedeutet, dass Leerzeichen für unsere Programme wichtig sind. Jedes vollständige Programm verfügt über ein mainUnterprogramm, das genau wie die main()Funktion in C-ähnlichen Sprachen funktioniert. Die Funktion wird beim Start des Programms ausgeführt.

Variablen und Typen

Wenn Variablen zum ersten Mal definiert werden, muss ihnen ein Typ zugeordnet sein. Die aktuell definierten Typen sind intund boolmit der Syntax für Arrays definiert, nicht jedoch der Compiler.

Bibliotheken und Betreiber

Es steht eine aufgerufene Bibliothek stdint.txtzur Verfügung, die die Grundoperatoren definiert. Wenn dies nicht enthalten ist, werden auch einfache Operatoren nicht definiert. Wir können diese Bibliothek mit verwenden #include stdint. stdintdefiniert Operatoren wie +, >>und selbst *und %von denen keiner Opcodes, direkte QFTASM sind.

Die Sprache ermöglicht auch das direkte Aufrufen von QFTASM-Opcodes mit __OPCODENAME__.

Zugabe in stdintist definiert als

operator (int a + int b) -> int
    return __ADD__(a, b)

Womit festgelegt wird, was der +Operator bei zwei Sekunden tut int.