Little Man Computer
![Wellingborough School - Little Man Computer Simulator](http://upload.wikimedia.org/wikipedia/commons/thumb/7/70/Little_Man_Computer_Simulator_LMC.png/676px-Little_Man_Computer_Simulator_LMC.png)
Der Little Man Computer (LMC) ist ein Modell zur besseren Erklärung der Von-Neumann-Architektur, das im Jahr 1965 von Stuart Madnick entwickelt worden ist.
Das Modell stellt die grundlegenden Funktionen eines Computers verständlich und spielerisch dar und kann sowohl in Maschinen- als auch in Assemblersprache programmiert werden. Zur Zielgruppe gehören insbesondere Schüler und Studenten.[1][2]
Das LMC-Modell basiert auf dem Konzept eines kleinen Mannes, der in einer geschlossenen Poststelle eingesperrt ist (analog zu einem Computer in diesem Szenario). An einem Ende des Raums befinden sich 100 Mailboxen (Speicher), die von 0 bis 99 nummeriert sind und jeweils eine dreistellige Anweisung oder Daten (im Bereich von 000 bis 999) enthalten können. Darüber hinaus befinden sich am anderen Ende zwei Postfächer mit der Bezeichnung INBOX und OUTBOX, die dem Empfang und der Ausgabe von Daten dienen. In der Mitte des Raumes befindet sich ein Arbeitsbereich mit einem einfachen Rechner mit zwei Funktionen (Addition und Subtraktion), der als Akkumulator bekannt ist, und einem rücksetzbaren Zähler, der als Programmzähler bekannt ist. Der Programmzähler speichert die Adresse der nächsten Anweisung, die der kleine Mann ausführen wird. Dieser Programmzähler wird normalerweise nach der Ausführung jeder Anweisung um 1 erhöht, sodass der kleine Mann ein Programm sequentiell abarbeiten kann. Verzweigungsanweisungen ermöglichen die Integration von Iterationen (Schleifen) und bedingten Programmierstrukturen in ein Programm. Letzteres wird dadurch erreicht, dass der Programmzähler auf eine nichtsequentielle Speicheradresse gesetzt wird, wenn eine bestimmte Bedingung erfüllt ist (normalerweise ist der im Akkumulator gespeicherte Wert Null oder positiv).
Gemäß der von Neumann-Architektur kann jedes Postfach (was einen eindeutigen Speicherort bedeutet) entweder eine Anweisung oder Daten enthalten. Daher muss darauf geachtet werden, dass der Programmzähler nicht eine Speicheradresse erreicht, die Daten enthält – sonst versucht der kleine Mann, sie als Anweisung zu behandeln. Dies kann man sich zunutze machen, indem man Anweisungen in Mailboxen schreibt, die als Code interpretiert werden sollen, um selbstmodifizierenden Code zu erstellen. Um die LMC zu verwenden, lädt der Benutzer Daten in die Mailboxen und signalisiert dann dem kleinen Mann, mit der Ausführung zu beginnen, beginnend mit der Anweisung, die an der Speicheradresse Null gespeichert ist. Durch das Zurücksetzen des Programmzählers auf Null wird das Programm effektiv neu gestartet, wenn auch in einem möglicherweise anderen Zustand.[3]
Ausführungsschritte
Um ein Programm auszuführen, werden folgende Schritte durchlaufen:
- Überprüfen des Programmzählers auf die Registeradresse, die eine Programmanweisung enthält (d. h. Null beim Start des Programms).
- Holen der Anweisung aus dem Register mit dieser Nummer. Jede Anweisung enthält zwei Felder: einen Opcode (der die auszuführende Operation angibt) und das Adressfeld (das angibt, wo sich die Daten befinden, an denen die Operation ausgeführt werden soll).
- Erhöhen des Programmzählers (so dass er die Mailboxnummer der nächsten Anweisung enthält)
- Dekodieren der Anweisung. Entsprechend dem Befehl, auf die das neue angetragene Register springen (?), wenn die Operation von diesem Daten benötigt, z. B. 'Daten aus Postfach 42 abrufen'
- Daten abrufen (vom Eingang, Akku oder Register mit der in Schritt 4 ermittelten Adresse)
- Führen Sie die Anweisung basierend auf dem angegebenen Opcode aus
- Ergebnis verzweigen oder speichern (in der Ausgabe, im Akkumulator oder im Register mit der in Schritt 4 ermittelten Adresse)
- Kehren Sie zum Programmzähler zurück, um den Zyklus zu wiederholen oder anzuhalten.
Befehle
Während das LMC die tatsächliche Funktionsweise von Binär-Prozessoren widerspiegelt, wurde die Einfachheit von Dezimal-Zahlen gewählt, um die Komplexität für Schüler zu minimieren, die möglicherweise nicht mit der Arbeit im Binär/Hexadezimal vertraut sind.
Anleitung
Einige LMC-Simulatoren werden direkt mit dreistelligen numerischen Anweisungen programmiert, andere verwenden mnemonische Codes und Beschriftungen aus drei Buchstaben. In beiden Fällen ist der Befehlssatz bewusst sehr begrenzt (typischerweise etwa zehn Anweisungen), um das Verständnis zu vereinfachen. Wenn die LMC mnemonische Codes und Beschriftungen verwendet, werden diese beim Zusammenstellen des Programms in dreistellige numerische Anweisungen umgewandelt.
Die folgende Tabelle zeigt einen typischen numerischen Befehlssatz und die entsprechenden mnemonischen Codes.
Numeric code | Mnemonic code | Instruction | Description |
---|---|---|---|
1xx | ADD | ADD | Addiert den im Register xx gespeicherten Wert zu dem Wert, der sich derzeit im Akkumulator (Rechner) befindet. Hinweis: Der Inhalt des Register wird nicht geändert und die Aktionen des Akkumulators (Rechners) ist nicht für Additionsanweisungen definiert, die Summen mit mehr als 3 Ziffern als Ergebnis hat . Ähnlich wie bei SUBTRACT kann man bei Überlauf ein negative Flag setzen. |
2xx | SUB | SUBTRACT | Subtrahiert den im Register xx gespeicherten Wert von dem Wert, der sich derzeit im Akkumulator (Rechner) befindet. Hinweis: Der Inhalt des Register wird nicht geändert und die Aktionen des Akkumulators sind nicht für Subtraktionsanweisungen definiert, die zu negativen Ergebnissen führen. Es wird jedoch ein negatives Flag gesetzt, sodass '''7xx (BRZ)'' und „8xx (BRP)“ ordnungsgemäß verwendet werden kann |
3xx | STA | STORE | Speichert den Inhalt des Akkus im Register xx (destruktiv). Hinweis: Der Inhalt des Akkus (Rechner) wird nicht verändert (nicht destruktiv), aber der Inhalt des Registers wird ersetzt, unabhängig davon, was sich darin befand (destruktiv). |
5xx | LDA | LOAD | Lädt den Wert aus Registers xx (nicht destruktiv) und trägt ihn in den Akku ein (destruktiv). |
6xx | BRA | BRANCH | Setzt den Programmzähler auf die angegebene Adresse (Wert xx). Das heißt, der Wert im Register xx ist die nächste ausgeführte Anweisung. |
7xx | BRZ | BRANCH IF ZERO (Bedingt) | Wenn der Akku (Rechner) den Wert 000 enthält, setzt der Befehl den Programmzähler auf den Wert xx. Ansonsten tut er nichts. Ob das Negativ-Flag berücksichtigt wird, ist nicht definiert. Wenn ein SUBTRACT den Akku unterschreitet, wird dieses Flag gesetzt, woraufhin der Akku undefiniert ist, möglicherweise Null, was dazu führt, dass das Verhalten von BRZ bei Unterlauf undefiniert ist. Das vorgeschlagene Verhalten wäre eine Verzweigung, wenn der Akku Null ist und das Negativ-Flag nicht gesetzt ist. Hinweis: Da das Programm im Speicher gespeichert ist, haben alle Daten und Programmanweisungen das gleiche Adress-/Ortsformat. |
8xx | BRP | BRANCH IF POSITIVE (Bedingt) | Wenn der Akku (Rechner) 0 oder positiv ist, setzt es den Programmzähler auf den Wert xx. Ansonsten tun er nichts. Da LMC-Speicherzellen nur Werte zwischen 0 und 999 speichern können, hängt dieser Befehl ausschließlich vom negativen Flag ab, das durch einen Unterlauf bei SUBTRACT und möglicherweise von einem Überlauf bei ADD (undefiniert) gesetzt wird. Hinweis: Da das Programm im Speicher gespeichert ist, haben alle Daten und Programmanweisungen das gleiche Adress-/Ortsformat. |
901 | INP | INPUT | Gehen Sie zum Posteingang, holen Sie den Wert vom Benutzer ab und geben Sie ihn in den Akku (Rechner) ein. Hinweis: Dadurch wird der Wert im Akkumulator überschrieben (destruktiv). |
902 | OUT | OUTPUT | Kopiert den Wert aus dem Akku (Rechner) in die OUTBOX (Ausgang). Hinweis: Der Inhalt des Akkus wird nicht verändert (zerstörungsfrei). |
000 | HLT/COB | HALT/COFFEE BREAK | Stopt / Hört auf zu arbeiten |
DAT | DATA | Dies ist eine Assembler-Anweisung, die den Wert einfach in das nächste verfügbare Register lädt. DAT kann auch in Verbindung mit Labels zum Deklarieren von Variablen verwendet werden. Beispielsweise speichert DAT 984 den Wert 984 in ein Register an der Adresse der DAT-Anweisung. |
Beispiele
Verwendung numerischer Anweisungscodes
Dieses Programm (Anweisung „901“ bis Anweisung „000“) ist nur mit numerischen Codes geschrieben. Das Programm nimmt zwei Zahlen als Eingabe und gibt die Differenz aus. Beachten Sie, dass die Ausführung bei Mailbox 00 beginnt und bei Mailbox 07 endet. Die Nachteile der Programmierung des LMC mit numerischen Befehlscodes werden im Folgenden erläutert.[4]
Mailbox | Numeric code | Operation | Comments |
---|---|---|---|
00 | 901 | Accumulator = Inbox | Gibt die erste Zahl ein und gibt sie in den Rechner (löscht alles, was dort war). |
01 | 308 | Mailbox 08 = Accumulator | Speichert den aktuellen Wert des Rechners (zur Vorbereitung auf den nächsten Schritt ...) |
02 | 901 | Accumulator = Inbox | INPUT the second number, enter into calculator (erasing whatever was there) |
03 | 309 | Mailbox 09 = Accumulator | Gibt die zweite Zahl ein und übergibt sie in den Rechner (löschen Sie alles, was dort war) |
04 | 508 | Accumulator = Mailbox 08 | (Jetzt werden beide INPUT-Werte in die Register 08 und 09 gespeichert...) Lädt den ersten Wert in den Rechner (löscht alles, was dort war) |
05 | 209 | Accumulator = Accumulator - Mailbox 09 | Subtrahiert die zweite Zahl vom aktuellen Wert des Rechners (der gerade auf die erste Zahl eingestellt ist) |
06 | 902 | Outbox = Accumulator | Gibt das Ergebnis des Rechners an den Ausgang |
07 | 000 | Halt | Hält die Maschine an |
Verwendung von Mnemonikcodes und Beschriftungen
Assemblersprache ist eine Low-Level-Programmiersprache, die Mnemonikcodes und Beschriftungen anstelle numerischer Befehlscodes verwendet. Obwohl die LMC nur einen begrenzten Satz an Mnemonikcodes verwendet, wird die Bequemlichkeit der Verwendung eines Mnemonikcodes für jede Anweisung durch die unten gezeigte Assemblersprache desselben Programms deutlich – der Programmierer muss sich nicht länger einen Satz numerische Codes merken, sondern kann jetzt mit einer Reihe einprägsamerer mnemonischer Codes arbeiten. Wenn es sich bei der Mnemonik um eine Anweisung handelt, die eine Speicheradresse beinhaltet („entweder eine Verzweigungsanweisung oder das Laden/Speichern von Daten“), wird eine Bezeichnung zur Benennung der Speicheradresse verwendet.
INP STA FIRST INP STA SECOND LDA FIRST SUB SECOND OUT HLT FIRST DAT SECOND DAT
Labels
Ohne Labels muss der Programmierer die Registeradresse („Speicher“) manuell berechnen. Wenn im numerischen Codebeispiel ein neuer Befehl vor dem letzten HLT-Befehl eingefügt werden müsste, würde dieser HLT-Befehl von Adresse 07 zu Adresse 08 verschoben (die Adressbeschriftung beginnt an der Adressposition 00). Angenommen, der Benutzer hat als erste Eingabe 600 eingegeben. Die Anweisung 308 würde bedeuten, dass dieser Wert an der Adressstelle 08 gespeichert wird und die Anweisung 000 (HLT) überschreibt. Da 600 „Verzweigung zur Postfachadresse 00“ bedeutet, würde das Programm nicht anhalten, sondern in einer Endlosschleife stecken bleiben.
Um dieses Problem zu umgehen, kombinieren die meisten Assemblersprachen („einschließlich LMC“) die mnemonischen Zeichen mit labels. Eine Bezeichnung ist einfach ein Wort, das verwendet wird, um entweder eine Speicheradresse zu benennen, an der eine Anweisung oder Daten gespeichert sind, oder um in einer Anweisung auf diese Adresse zu verweisen.
Programmzusammenstellung:
- Eine Beschriftung links neben einer Befehlsmnemonik wird in die Speicheradresse umgewandelt, an der der Befehl oder die Daten gespeichert sind. d. h. loopstart INP
- Eine Beschriftung rechts neben einer Befehlsmnemonik nimmt den Wert der oben genannten Speicheradresse an. d. h. BRA loopstart
- Eine mit einer DAT-Anweisung kombinierte Bezeichnung fungiert als Variable und bezeichnet die Speicheradresse, an der die Daten gespeichert sind. d. h. „ein DAT 1“ oder „Nummer 1 DAT“
Wenn im Beispiel „Assemblersprache“, das Mnemonik und Beschriftungen verwendet, ein neuer Befehl vor dem letzten HLT-Befehl eingefügt würde, befände sich der mit FIRST gekennzeichnete Adressort jetzt am Speicherort 09 und nicht an 08 Die STA FIRST-Anweisung wurde beim Zusammenstellen des Programms in 309 (STA 09) und nicht in 308 (STA 08) konvertiert.
Etiketten werden daher verwendet, um:
- Identifizieren Sie eine bestimmte Anweisung als Ziel für eine BRANCH-Anweisung.
- Identifizieren Sie einen Speicherort als benannte Variable (mithilfe von DAT) und laden Sie optional Daten zur Assemblierungszeit in das Programm, um sie vom Programm zu verwenden (diese Verwendung ist erst offensichtlich, wenn man bedenkt, dass es keine Möglichkeit gibt, 1 zu einem Zähler hinzuzufügen. Eins könnte den Benutzer zu Beginn auffordern, 1 einzugeben, aber es wäre besser, dies zum Zeitpunkt der Assemblierung mit „ein DAT 1“ zu laden)
Beispiel
Das folgende Programm nimmt eine Benutzereingabe entgegen und zählt bis Null herunter.
INP OUT // Initialize output LOOP BRZ QUIT // Label this memory address as LOOP. If the accumulator value is 0, jump to the memory address labeled QUIT SUB ONE // Subtract the value stored at address ONE from the accumulator OUT BRA LOOP // Jump (unconditionally) to the memory address labeled LOOP QUIT HLT // Label this memory address as QUIT ONE DAT 1 // Store the value 1 in this memory address, and label it ONE (variable declaration)
Das folgende Programm nimmt eine Benutzereingabe entgegen, quadriert sie, gibt die Antwort aus und wiederholt den Vorgang. Die Eingabe einer Null beendet das Programm.
(Hinweis: Eine Eingabe, die zu einem Wert größer als 999 führt, weist aufgrund der 3-stelligen Zahlenbeschränkung des LMC ein undefiniertes Verhalten auf.)
START LDA ZERO // Initialize for multiple program run STA RESULT STA COUNT INP // User provided input BRZ END // Branch to program END if input = 0 STA VALUE // Store input as VALUE LOOP LDA RESULT // Load the RESULT ADD VALUE // Add VALUE, the user provided input, to RESULT STA RESULT // Store the new RESULT LDA COUNT // Load the COUNT ADD ONE // Add ONE to the COUNT STA COUNT // Store the new COUNT SUB VALUE // Subtract the user provided input VALUE from COUNT BRZ ENDLOOP // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP BRA LOOP // Branch to LOOP to continue adding VALUE to RESULT ENDLOOP LDA RESULT // Load RESULT OUT // Output RESULT BRA START // Branch to the START to initialize and get another input VALUE END HLT // HALT - a zero was entered so done! RESULT DAT // Computed result (defaults to 0) COUNT DAT // Counter (defaults to 0) ONE DAT 1 // Constant, value of 1 VALUE DAT // User provided input, the value to be squared (defaults to 0) ZERO DAT // Constant, value of 0 (defaults to 0)
Hinweis: Wenn nach einer DAT-Anweisung keine Daten vorhanden sind, wird der Standardwert 0 in der Speicheradresse gespeichert.
Im obigen Beispiel hängt [BRZ ENDLOOP] von undefiniertem Verhalten ab, da COUNT-VALUE negativ sein kann, woraufhin der ACCUMULATOR-Wert undefiniert ist, was dazu führt, dass BRZ entweder verzweigt oder nicht (ACCUMULATOR kann Null sein oder umbrochen werden). Um den Code mit der Spezifikation kompatibel zu machen, ersetzen Sie:
... LDA COUNT // Load the COUNT ADD ONE // Add ONE to the COUNT STA COUNT // Store the new COUNT SUB VALUE // Subtract the user provided input VALUE from COUNT BRZ ENDLOOP // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP ...
mit der folgenden Version, die VALUE-COUNT anstelle von COUNT-VALUE auswertet und sicherstellt, dass der Akkumulator niemals unterläuft:
... LDA COUNT // Load the COUNT ADD ONE // Add ONE to the COUNT STA COUNT // Store the new COUNT LDA VALUE // Load the VALUE SUB COUNT // Subtract COUNT from the user provided input VALUE BRZ ENDLOOP // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP ...
Ein weiteres Beispiel ist ein Quine, der seinen eigenen Maschinencode druckt (das Drucken der Quelle ist nicht möglich, da Buchstaben nicht ausgegeben werden können):
LOAD LDA 0 // Load position 0 into the accumulator. This line will be modified on each loop to load the next lines into the accumulator
OUT // Output the accumulator's value. The accumulator's value will be the line that was just loaded
SUB ONE // Subtract 1 from the value in the accumulator. This is so we can do the BRZ in the next step to see if we are on the last line in the program
BRZ ONE // If the previous subtraction has made the accumulator 0 (which means we had the value 001 in the accumulator), then branch to position ONE LDA LOAD // Load the LOAD position into the accumulator, this is in preparation to increment the address digits for this position ADD ONE // Increment the position digits for the LOAD line. The value currently in the accumulator would, if read as an instruction, load the next line into the accumulator, compared to the last line loaded STA LOAD // Store the newly incremented LOAD line back in the LOAD position BRA LOAD // Return to the beginning of the loop ONE DAT 1 // The variable ONE. If read as an instruction, this will be interpreted as HLT/COB and will end the program
Dieses Quine funktioniert mit selbstmodifizierendem Code. Position 0 wird in jeder Iteration um eins erhöht und gibt den Code dieser Zeile aus, bis der ausgegebene Code 1 ist. An diesem Punkt wird zur Position EINS verzweigt. Der Wert an der Position ONE hat als Opcode 0 und wird daher als HALT/COB-Befehl interpretiert.
Weblinks
- The "Little Man" Computer
Online-Simulatoren
- by 101computing
- Wellingborough LMC Simulator
- Peter Higginson's LMC Simulator
Einzelnachweise
- ↑ W. Yurcik, H. Osborne: Proceedings of the 2001 Winter Simulation Conference (Cat. No.01CH37304). Band 2, 2001, ISBN 0-7803-7307-3, A crowd of Little Man Computers: Visual computer simulator teaching tools, S. 1632, doi:10.1109/WSC.2001.977496 (englisch).
- ↑ W. Yurcik, L. Brumbaugh: Proceedings of the thirty-second SIGCSE technical symposium on Computer Science Education - SIGCSE '01. 2001, ISBN 1-58113-329-4, A web-based little man computer simulator, S. 204, doi:10.1145/364447.364585 (englisch).
- ↑ Little Man Computer. Abgerufen am 19. Juni 2023.
- ↑ Richard J. Povinelli:Teaching:Introduction to Computer Hardware and Software:Little Man Computer. Abgerufen am 19. Juni 2023.