Little Man Computer

Little Man Computer Simulator LMC

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.

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.

Ausführungsschritte

Um ein Programm auszuführen, werden folgende Schritte durchlaufen:

1. Überprüfen des Programmzählers auf die Registeradresse, die eine Programmanweisung enthält (d. h. Null beim Start des Programms).
2. 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).
3. Erhöhen des Programmzählers (so dass er die Mailboxnummer der nächsten Anweisung enthält)
4. 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'
5. Daten abrufen (vom Eingang, Akku oder Register mit der in Schritt 4 ermittelten Adresse)
6. Führen Sie die Anweisung basierend auf dem angegebenen Opcode aus
7. Ergebnis verzweigen oder speichern (in der Ausgabe, im Akkumulator oder im Register mit der in Schritt 4 ermittelten Adresse)
8. 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.

Instructions

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 negatives 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 (Unbedingt)	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.

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

• 101computing LMC Simulator
• Wellingborough LMC Simulator
• Peter Higginson's LMC Simulator