15A: Das ENDe?

Die Aufgaben 15A, 15B, und 15C können in beliebiger Reihenfolge bearbeitet werden.

In dieser Übung wirst du ein langes und komplexes Problem bearbeiten, das für dich in Einzelteile zerlegt wurde. In dieser Übung findest du auch str.split(), eine hilfreiche Methode, um Strings, also Zeichenketten aufzusplitten: es löscht alle Leerzeichen und gibt dann eine Liste all jener Worte in der Zeichenkette aus. Die Originalkette wird dabei nicht verändert.

Beispiel
Beispiele für str.split()

Du kannst split() mit besonderen Argumenten aufrufen, um ein anspruchsvolleres Splitting durchzuführen, aber wir brauchen diese Fähigkeit weiter unten nicht. Wenn du aber interessiert bist, findest du weitere Details in der Python Dokumentation.

Jetzt können wir zum eigentlichen Problem vorstoßen. Die alte Programmiersprache BASIC war berühmt für ihre nummerierten Zeilen und goto Statements. Für diese Übung wirst du eine einfache Version von BASIC implementieren, die nur diese Eigenschaften hat. Um es genauer zu sagen: die Eingabe für dein Programm wird aus mehreren Zeilen des Formats

«label» goto «target»

erstellt, wobei «label» und «target» positive ganze Zahlen sind. Das Label ist sowas wie der Name oder die Adresse der Zeile; alle Labels sind einzigartig. Das Ziel (engl.: target) sagt dir, zu welchem Label, bzw. zu welcher Zeile als nächstes gegangen wird (engl.: go to). Die letzte Zeile des Programms ist «label» END , was anzeigt, dass du aufhören solltest, wenn du diese Zeile erreichst. Hier ist ein einfaches BASIC-Programm:

5 GOTO 30
10 GOTO 20
20 GOTO 10
30 GOTO 40
40 END
Wenn BASIC das Programm ausführt, passiert folgendes. Wir fangen mit der ersten Zeile an (mit dem Label 5). Die Zeile mit dem Label 5 hat das Ziel 30, also machen wir weiter mit der Zeile mit dem Label 30. Dann sagt uns Zeile 30, dass als nächstes Zeile 40 dran ist. Zeile 40 sagt uns: END. Also wurde das Programm erfolgreich beendet.

Andererseits, kann ein BASIC-Programm in einer ewigen Schleife sein. Hier ist ein Beispiel:

10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END
Das Programm beginnt mit der Zeile 10, aber dann vollführt es eine unendliche Schleife zwischen den Zeilen 21 und 37.

Deine Aufgabe ist es, ein Python-Programm zu schreiben, das ein BASIC Programm als Eingabe einliest. Wenn das Programm zu Ende ist, sollte es success ausgeben. Wenn das Programm eine unendliche Schleife beginnt, sollte dein Programm infinite loop ausgeben. Nimm an, dass jedes Ziel gleich einem zulässigen Label ist, und dass es kein Label zweimal gibt, so dass du nicht nochmal auf Fehler überprüfen musst.

Es gibt mehrere Ansätze, um dieses Problem zu lösen, aber in dieser Übung haben wir eine einfache Variante ausgewählt, die das Problem in 3 kleinere Aufträge unterteilt. (In der Lektion 15C hast du ein großes Problem und musst die kleineren Aufträge selbst entwerfen).

Auftrag 1: Das Programm lesen

Um das Programm zu lesen, müssen wir immer wieder input() aufrufen. Wir müssen jedoch aufhören, input() aufzurufen, wenn die letzte Zeile (die mit END) erreicht wurde, um einen EOFError zu vermeiden.

Programmierübung: Reading the Program
Schreibe eine Funktion getBASIC(), die keine Argumente nimmt und folgendes macht: Sie sollte Zeilen aus der Eingabe lesen, indem sie eine while Schleife verwendet. Wenn das Ende erreicht wurde, sollte sie das ganze Programm zurückgeben als eine Auflistung von Zeichenketten bzw. Strings. (Tipp: über Listen und das Beenden von Schleifen)
Du kannst die Eingabe für das Programm in die Box unten eingeben.

Auftrag 2: Geh dort hin!

Wenn wir das Programm ausgelesen haben, müssen wir in der Lage sein, uns im Programm von Zeile zu Zeile zu bewegen. Um dies zu erreichen, möchten wir, dass du die folgende Subroutine schreibst:

Programmierübung: Geh dort hin
Definiere eine Funktion findLine(prog, target), die das Folgende machen soll: Nimm an, prog sei eine Liste von Strings, die ein BASIC-Programm enthalten, wie der Typ, der von getBASIC() erzeugt wird. Nimm weiterhin an, dass target ein String ist, der eine Zeilennummer enthält, die das Ziel eines GOTO Statements ist. Die Funktion soll den Index i (eine Zahl zwischen 0 und len(prog)-1) so zurückgeben, dass prog[i] die Zeile ist, deren Label gleich target ist. Tipp
Muster Ein- / Ausgabe: Wenn du folgendes aufrufst:

findLine(['10 GOTO 20','20 END'], '10')
sollte die Ausgabe 0 sein, da der Eintrag 0 der Liste die Zeile mit dem Label 10 ist.
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

Auftrag 3: Geschickt Simuliert

In den vorhergehenden beiden Übungen haben wir die Eingaberoutine und den Suchauftrag behandelt. Diese werden uns dabei hilfreich sein, das Hauptprogramm knapper zu schreiben. Trotz all dem bleibt eine wichtige Frage: wie können wir das ursprüngliche Problem lösen? Am einfachsten wäre es, wenn wir einfach das BASIC Programm simulieren würden:

  • nehmen wir an, dass prog das BASIC Programm ist (eine Liste mit Strings)
  • lassen wir einen Zähler (den wir location nennen) bei 0 beginnen, da wir mit der ersten Zeile des Programms anfangen
  • while True,
    • wenn prog[location] die END-Zeile ist, gib "success" ein und beende das Programm.
    • Lege T als die  Ziel-Zeichenkette fest, die unter prog[location] aufgeführt wird
    • Lege findLine(prog, T) als den neuen Wert von location fest

Dies hat aber eine große Schwachstelle: dieser Vorgang erlaubt es uns nicht, unendliche Schleifen aufzuspüren und, wenn das BASIC-Programm eine unendliche Schleife hat, dann wird auch das Python Programm eine unendliche Schleife ausführen. Was wir wollten, war, dass das Programm "unendliche Schleife" in dieser Situation ausgibt. Wir überlassen es Dir, eine Lösung für dieses Problem zu finden, unten findest du einen Tipp dazu.

Programmierübung: Smart Simulation
Schreibe eine Funktion namens execute(prog), die das Folgende macht: Nimm an, dass prog eine Liste von Zeichenketten ist, die das BASIC-Programm enthalten wie vorher. Nun soll dein Programm entweder "success" oder "infinite loop" ausgeben, je nachdem ob das Programm terminiert oder eine unendliche Schleife ausführt. Wichtig: du solltest annehmen, dass findLine(prog, target), das wir in der Unteraufgabe 2 definiert haben, bereits definiert ist, du musst es nicht neu schreiben. Tipp
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

Alles zusammenführen

Um deinen Code als Komplettlösung zu testen, kopiere deine vorherigen Lösungen in das folgende Muster.

Programmierübung: BASIC Simulator
Stelle Deinen BASIC Simulator zusammen.
Du kannst die Eingabe für das Programm in die Box unten eingeben.

Wenn deine Programmiersprache etwas komplizierter ist, dann ist es unmöglich, ein Programm zu schreiben, das die Terminierung überprüft. Das war das früheste Theorem in der Informatik, es wurde von Alan Turing in den 1930er Jahren bewiesen und wenn Leute heute darüber reden, dann sagen sie "das Halteproblem ist unlösbar"