Wir programmieren eine Schleife
In diesem Abschnitt lernst du die Befehle dec x, jmp x und isz x an einem weiteren Programmbeispiel kennen. Zusammen mit den beiden Befehlen aus dem vorangegangenen Kapitel sind das auch schon alle Befehle, die du brauchst, um den Know-How-Computer zu programmieren. Am Ende dieser Seite findest du eine Kurzübersicht über alle fünf KHC-Befehle.
Zweites Programmbeispiel "Von x auf 0"
Was soll das Programm tun?
Bei diesem Programm gehen wir davon aus, dass vor dem Programmstart in Zelle 6 ein beliebiger Wert steht, z.B. der Wert 3. Das Programm soll nun dafür sorgen, dass in dieser Zelle nach dem Programmende der Wert 0 steht.
Idee
Für das schrittweise Herunterzählen können wir den KHC-Befehl dec verwenden ("decrement" bedeutet verringern).
dec x
Der Befehl dec x veringert den Datenwert an der Adresse x um 1 und erhöht anschließend den Programmzähler um 1.
Allerdings besteht die Lösung der gestellten Aufgabe nicht darin, einfach den Befehl dec 6 dreimal hintereinander in den Hauptspeicher zu schreiben, denn damit würde das Programm ausschließlich für den Anfangswert 3 in Zelle 6 korrekt arbeiten. Es soll aber für beliebige Startwerte funktionieren. Egal, welcher Wert zu Beginn in Zelle 6 steht - nach dem Programmende soll dort immer der Wert 0 stehen.
Idee
Ein erster Lösungsversuch könnte nun darin bestehen, den dec-Befehl zwar nur einmal in den Hauptspeicher zu schreiben, dann aber mit dem jmp-Befehl (von "jump" = springen) dafür zu sorgen, dass dieser dec-Befehl mehrfach ausgeführt wird.
jmp x
Der Befehl jmp x verändert keine Datenwerte im Hauptspeicher, sondern setzt lediglich den Programmzähler auf den Wert x.
"Von x auf 0" - erster Entwurf
Ein erster Programmentwurf könnte so aussehen:
1: dec 6
2: jmp 1
...
6: 3
Anders als bei den Befehlen inc x und dec x macht der Befehl jmp x natürlich nur Sinn, wenn an der Adresse x im Speicher kein Datenwert, sondern auch wieder ein KHC-Befehl steht, der dann als nächstes ausgeführt werden kann.
Aufgabe
Führe den ersten Entwurf des Programms im Hauptspeicher aus. Dabei stößt du auf gleich mehrere Probleme. Welche sind das?
Lösung
Tatsächlich führt die Befehlsfolge 1: dec 6 und 2: jmp 1 erst einmal dazu, dass der Wert in Zelle 6 schrittweise von 3 auf 0 heruntergezählt wird. Mit dem dec-Befehl wird der Programmzähler um 1 auf 2 erhöht. Dort sorgt aber der jmp-Befehl dafür, dass er gleich wieder auf die Adresse 1 zurückgesetzt wird, so dass als nächstes erneut der dec-Befehl ausgeführt wird. Wir haben damit eine so genannte Schleife programmiert, die tatsächlich jeden beliebigen Wert in Zelle 6 bis auf den Wert 0 herunterzählt.
Ein Problem ist nun allerdings: Nachdem der Wert in Zelle 6 einmal den gewünschten Zielwert 0 erreicht hat, sorgt der jmp-Befehl dafür, dass der dec-Befehl trotzdem erneut ausgeführt wird.
Dies führt zu einem weiteren Laufzeitfehler, denn das Verringern des Wertes 0 um 1 würde zu dem negativen Wert -1 führen, der aber als Datenwert im KHC nicht zugelassen ist.
Und ein weiteres Problem besteht darin, dass diese Schleifenkonstruktion - unabhängig von dem Laufzeitfehler - nie zu einem Ende kommen würde. Man spricht hier auch von einer
Endlosschleife. Mit den bisher verfügbaren KHC-Befehlen gibt es auch keine Möglichkeit, daran etwas zu ändern, auch nicht mit dem stp-Befehl, weil dieser nicht zum richtigen Zeitpunkt erreicht werden kann. Aber zum Glück gibt es noch einen weiteren Befehl ...
"Von x auf 0" - zweiter Entwurf
Idee
Um das Problem der Endlosschleife zu lösen, benötigen wir eine Möglichkeit, die Schleife genau dann zu beenden, wenn in Zelle 6 der Wert 0 erreicht wird. Hierfür können wir den Befehl isz x verwenden ("is zero" bedeutet abgekürzt "ist Null"). Dieser Befehl funktioniert so:
isz x
Wenn in der Zelle x der Wert 0 steht, dann wird der Programmzähler um 2 erhöht, andernfalls nur um 1.
Der zweite Programmentwurf mit dem isz-Befehl sieht so aus:
Programm testen im KHC-Emulator
# Von x auf 0 (2. Entwurf)
1: dec 6
2: isz 6
3: jmp 1
4: stp
5: 0
6: 3
# Von x auf 0 (3. Entwurf)
1: isz 6
2: jmp 4
3: stp
4: dec 6
5: jmp 1
6: 3
Aufgabe
Führe den zweiten Programmentwurf im KHC-Emulator oder in deinem eigenen KHC-Modell aus. Beschreibe den Programmablauf in eigenen Worten. Sind die Probleme, die beim ersten Entwurf aufgetreten sind, jetzt behoben?
Jedes Mal, nachdem der Wert in Zelle 6 um 1 verringert wurde, wird nun in Zelle 2 mit dem Befehl isz 6 eine Entscheidung getroffen. Wenn in Zelle 6 der Wert 0 erreicht wurde, wird der Programmzähler um 2 auf 4 erhöht. Und da dort der stp-Befehl steht, wird das Programm beendet. Wenn allerdings der Wert in Zelle 6 noch nicht 0 ist, dann wird der Programmzähler nur um 1 auf 3 erhöht. In Zelle 3 steht der Befehl jmp 1, der dafür sorgt, dass die Schleife noch einmal ausgeführt wird und der Wert in Zelle 6 erneut um 1 verringert wird.
Dies kann nun aber nicht mehr endlos so weitergehen, denn irgendwann muss das wiederholte Verringern des Wertes in Zelle 6 dazu führen, dass dort schließlich der Wert 0 erscheint. Und in diesem Fall sorgt dann der isz-Befehl dafür, dass die Schleife durch den stp-Befehl beendet wird.
Aufgabe
So weit scheint also alles in Ordnung zu sein. Aber das Programm hat immer noch einen kleinen Schönheitsfehler. Es funktioniert jetzt zwar für fast alle Startwerte in Zelle 6 - aber eben nicht für alle ! Für welchen Startwert geht die Ausführung schief - und warum?
Wenn von Anfang an in Zelle 6 der Wert 0 steht, dann führt unser zweiter Programmentwurf wieder zu einem Laufzeitfehler, denn gleich zu Beginn müsste der Wert 0 in Zelle 6 um 1 verringert werden. Das Ergebnis wäre die negative Zahl -1 und die ist beim KHC nicht zugelassen. Du kannst das im KHC-Emulator ausprobieren, indem du einfach das Programm nach dem ersten Durchgang noch einmal ausführen lässt.
"Von x auf 0" - dritter Entwurf
Aufgabe
Das Problem mit dem Startwert in Zelle 6 lässt sich umgehen, indem man das Programm ein wenig umbaut. Wie kann man durch eine andere Anordnung der bekannten fünf KHC-Befehle dafür sorgen, dass das Programm auch für den kritischen Startwert in Zelle 6 funktioniert?
Das Problem wird umgangen, wenn man gleich zu Beginn mit dem isz-Befehl prüft, ob in Zelle 6 der Wert 0 steht. Die Position der anderen Befehle muss entsprechend angepasst werden.
Die endgültige Fassung des Programms "Von x auf 0" könnte z.B. so aussehen:
1: isz 6
2: jmp 4
3: stp
4: dec 6
5: jmp 1
6: 3
Jetzt wird immer schon, bevor der dec-Befehl ausgeführt wird, erst mal geprüft, ob dies überhaupt möglich ist - und zwar auch schon beim allerersten Mal. Steht von Anfang an in der Zelle 6 der Wert 0, dann wird der Programmzähler schon mit dem ersten Schritt auf die Adresse 3 mit dem stp-Befehl gesetzt und das Programm korrekt beendet.
Du kannst diese Version des Programms auch mit dem Schalter "Von x auf 0 (3. Entwurf)" als fertige Speicherkonfiguration in den KHC-Emulator laden und dort testen.
Programmablaufplan
Der Ablauf eines Programms kann auch mit einem so genannten "Programmablaufplan (PAP)" oder auch "Flussdiagramm" grafisch anschaulich dargestellt werden. Für das KHC-Programm "Von x auf 0" könnte ein solcher PAP zum Beispiel so aussehen:
Bedeutung der PAP-Symbole
- Oval
- Anfang / Ende des Programms
- Raute
- Verzweigung / Entscheidung - abhängig von der angegebenen Bedingung
- Rechteck
- Operation / Anweisung / Befehl
- Pfeil
- zeigt auf den nächsten Programmschritt
Hinweis
Diese Grafik gibt es im
Anhang auch als taktile Schwellpapier-Kopiervorlage mit Braillebeschriftung.
Pseudocode
Eine andere Möglichkeit, die Programmidee übersichtlich darzustellen, bietet der so genannte Pseudocode, der manchmal auch als Entwurfsprache bezeichnet wird. Für das KHC-Programm "Von x auf 0" könnte ein solcher Pseudocode zum Beispiel so aussehen:
solange nicht x = 0 wiederhole
verringere x um 1
solange_ende
Kurzübersicht der KHC-Befehle
- inc x
- Erhöhe den Wert in Zelle x um 1 und erhöhe den Programmzähler um 1.
- dec x
- Verringere den Wert in Zelle x um 1 und erhöhe den Programmzähler um 1.
- jmp x
- Setze den Programmzähler auf den Wert x.
- isz x
- Wenn Zelle x den Wert 0 (zero) enthält, dann erhöhe den Programmzähler um 2, sonst erhöhe den Programmzähler um 1.
- stp
- Beende das Programm.
