Programmiersprachen
LVA 185.208, VL 2.0, 2008 S

1. Übungsaufgabe

Entwickeln Sie in Java, C# oder C++ einen Taschenrechner entsprechend folgenden Spezifikationen und lösen Sie damit die weiter unten beschriebene Testaufgabe (Primzahlberechnung):

Allgemeines:

Alle Eingaben erfolgen in Postfix-Notation (auch UPN-Logik genannt - zuerst kommen die Argumente, danach der Operator). Berechnungen erfolgen über einen Stack. Die Anzahl der benötigten Argumente hängt vom Operator ab, und es wird angenommen, dass die Argumente als oberste Elemente am Stack liegen. Daten sind ganze Zahlen oder Operationen (in Hochkomma, siehe unten).

Zum Beispiel ist 12,3+ eine Anwendung von + auf 12 und 3, die als Ergebnis 15 liefert. Genau genommen wird diese Eingabe Zeichen für Zeichen von links nach rechts abgearbeitet: Zuerst wird 1 als oberstes Element auf den Stack gelegt und als nicht abgeschlossene Zahl markiert. Bei der Abarbeitung von 2 wird (da das oberste Stackelement eine nicht abgeschlossene Zahl ist) das Stackelement mit 10 multipliziert und 2 addiert. Der Beistrich bewirkt (wie jede Eingabe außer einer Ziffer), dass die Markierung gelöscht wird; ; hat keinerlei sonstige Auswirkungen. Dadurch wird 3 als neues Stackelement auf den Stack gelegt und als nicht abgeschlossene Zahl markiert. Im nächsten Schritt löscht + die Markierung wieder, entfernt die beiden obersten Stackelemente (da + zweistellig ist) und legt das Ergebnis der Addition auf den Stack.

Der Ausdruck 1,2,3,4+*- wird zu 1-(2*(3+4)) = -13 ausgewertet: Der (von links gelesen) erste Operator addiert die direkt davor stehenden Argumente 3 und 4 zu 7, der Operator * wird auf die nach der Addition direkt davor stehenden Argumente 2 und 7 angewandt, und schließlich wird - auf 1 und 14 angewandt.

Ausdrücke in Hochkomma werden nicht gleich ausgewertet. Einige Operatoren verarbeiten solche Ausdrücke als Argumente. Zum Beispiel wird '2*' als Argument des Operators a selbst als Operator gesehen, der ein Argument mit 2 multipliziert. Der Ausdruck 3'2*'a wird also zu 6 ausgewertet.

In den Taschenrechner sollen Ausdrücke direkt eingegeben werden können, und Ergebnisse sollen nach jedem Tastendruck berechnet und ausgegeben werden, ohne spezielle Taste mit der Bedeutung jetzt berechnen. Da es in Java schwierig ist, Tastendrücke direkt abzufragen, können Sie die Auswertung von Eingaben verzögern, bis die Eingabetaste gedrückt wird. Danach soll die Abarbeitung jedoch für jedes eingegebene Zeichen getrennt erfolgen.

Architektur:

Die Architektur des Taschenrechners ist sehr einfach und besteht nur aus folgenden Teilen:

Registersatz:

Der Taschenrechner soll über sehr viele (genaue Anzahl nicht vorgegeben) durchnummerierte Register verfügen, in die Zahlen und Ausdrücke abgelegt werden. Die Initialisierung der Register ist nicht festgelegt und kann (bis auf die Register -7 bis -1, siehe unten) frei gewählt werden. Dadurch können gleich beim Programmstart häufig benötigte Zahlen und Ausdrücke in Registern abgelegt sein.

Top of Stack (Register -7):

Der für die Abarbeitung der Ausdrücke in Postfix-Notation benötigte Stack ist nur als Ausschnitt aus dem Registersatz realisiert. Register -7 enthält stets die Nummer des Registers, in dem das aktuelle oberste Stackelement zu finden ist.

Eingabepuffer (Register -6):

Register -6 enthält die Liste der eingegebenen, aber noch nicht abgearbeiteten ASCII-Zeichen. Alle Eingaben werden entsprechend der Reihenfolge in dieser Liste abgearbeitet. Außer durch Tastatureingaben werden auch durch den Operator a Eingaben in diese Liste geschrieben.

Markierung (Register -5):

Register -5 enthält eine Zahl zwischen -1 und 1 mit folgender Bedeutung:

• -1: Das ist eine Markierung als nicht abgeschlossene Zahl. Falls das nächste aus dem Eingabepuffer gelesene Zeichen eine Ziffer ist, wird (statt einer normalen Abarbeitung) die Zahl im aktuellen Top-of-Stack-Register mit 10 multipliziert und danach die Ziffer in der Eingabe addiert. Andernfalls wird Register -5 auf 0 gesetzt und mit der normalen Abarbeitung fortgesetzt.
• 0: Es ist keine Markierung gesetzt. Das nächste Zeichen wird normal abgearbeitet.
• 1: Das ist die Markierung für die Eingabe von Ausdrücken in Hochkomma. Falls das nächste Zeichen im Eingabepuffer ' ist, wird dieses Zeichen nicht weiter bearbeitet, und Register -5 wird auf 0 gesetzt. Andernfalls wird das Zeichen zum Ausdruck im aktuellen Top-of-Stack-Register hinzugefügt.

Display (Register -4 bis -1):

Der Taschenrechner zeigt gleichzeitig vier Text-Zeilen an, die den Inhalten von vier Registern entsprechen. Die Register -4 bis -1 enthalten die Nummern der Register, die angezeigt werden sollen.

Der Inhalt aller Register kann über r gelesen, über s geschrieben und durch Setzen der Register -4 bis -1 angezeigt werden, und jedes Register kann als Teil des Stacks betrachtet werden. Das gilt auch für die Register -7 bis -1 (obwohl das nicht immer sinnvoll erscheint). Achten Sie besonders darauf, dass bei einem Schreibzugriff auf Register -7 keine unerwarteten Seiteneffekte auftreten.

Zur Vereinfachung können Sie (vernünftig gewählte) Maximalgrößen für Ausdrücke in Registern festlegen, bei deren Überschreitung eine Fehlermeldung ausgegeben wird. Nach Fehlermeldungen kann die Programmausführung abgebrochen werden. Verwenden Sie zur Darstellung ganzer Zahlen zumindest long.

Operationen:

Die Bedeutung folgender Eingaben ist vordefiniert (bei normaler Abarbeitung, also Register -5 hat den Wert 0):

Ziffer 0 bis 9:

Diese wird als Zahl in ein neues Stackelement geschrieben (und dabei Register -7 erhöht). Außerdem wird Register -5 auf -1 gesetzt.

Hochkomma ':

Ein leerer Ausdruck wird in ein neues Stackelement geschrieben (und dabei Register -7 erhöht). Außerdem wird Register -5 auf 1 gesetzt.

Trennsymbol ,:

Für den Beistrich ist keine weitere Bearbeitung nötig.

Arithmetischer Operator oder Vergleichsoperator (+, -, *, /, %, &, |, =, <, >):

Ein solcher zweistelliger Operator entspricht einer Grundrechnung oder einem einfachen Vergleich, wobei % für die Modulo-Operation steht und & bzw. | sowohl als logisches als auch als bitweises UND bzw. ODER verwendbar ist. Die zwei obersten Argumente werden vom Stack genommen und das Ergebnis auf den Stack gelegt. Register -7 wird dabei um 1 erniedrigt. Wenn ein Argument keine Zahl ist, soll ein Fehler gemeldet werden. Ausgenommen hiervon ist nur =: Wenn = auf zwei gleiche Ausdrücke oder zwei gleiche Zahlen angewandt wird, soll als Ergebnis wahr zurückgegeben werden, sonst falsch. Dabei wird wahr durch die Zahl -1 dargestellt und falsch durch 0. Bei nichtassoziativen Operationen ist auf die Reihenfolge der Argumente zu achten: 4,2-, 4,2/ und 6,4% sollen jeweils 2 ergeben, und 4,2> und 2,4< sollen -1 liefern. Das Ergebnis einer Modulo-Operation soll dasselbe Vorzeichen wie das zweite Argument haben und betragsmäßig (also ohne Berücksichtigung von Vorzeichen) kleiner als das zweite Argument sein. Ein Fehler soll gemeldet werden, wenn das zweite Argument von / oder % gleich 0 ist.

Bitweise Negation !:

Diese einstellige Operation angewandt auf eine Zahl (am Top-of-Stack) negiert die Zahl bitweise (z.B: ist 0! gleich -1, entspricht also der logischen Negation). Anwendungen auf Ausdrücke führen zu Fehlermeldungen.

Vorzeichenänderung ~:

Diese einstellige Operation angewandt auf eine Zahl (am Top-of-Stack) ändert das Vorzeichen der Zahl. Anwendungen auf Ausdrücke führen zu Fehlermeldungen.

Anwenden a:

Diese Operation nimmt das oberste Argument vom Stack. Ist das Argument ein Ausdruck, dann wird dieser an vorderster Stelle in die Eingabeliste geschrieben, damit die darin enthaltenen Eingaben als nächste abgearbeitet werden. Ist das Argument eine Zahl, dann wird das Register mit der entsprechenden Nummer ausgelesen. Falls kein Register mit dieser Nummer existiert oder das Register keinen Ausdruck enthällt, wird eine Fehlermeldung ausgegeben. Sonst wird der Ausdruck im Register an vorderster Stelle in die Eingabeliste geschrieben.

Lesen r:

Das oberste Argument am Stack muss eine Zahl sein, die ein Register bezeichnet, andernfalls erfolgt eine Fehlermeldung. Dieses oberste Argument wird durch den Inhalt des Registers ersetzt.

Speichern s:

Das oberste Argument am Stack muss eine Zahl sein, die ein Register bezeichnet, andernfalls erfolgt eine Fehlermeldung. Das zweite Argument am Stack wird in das durch das erste Argument bezeichnete Register gespeichert. Das oberste Element wird vom Stack genommen (und Register -7 dabei verändert), das andere Argument bleibt am Stack erhalten.

Ausschalten q:

Schaltet den Taschenrechner aus bzw. beendet das Programm. Das Programm endet auch, wenn Register -6 leer ist.

Hinweise:

Der Aufbau des Taschenrechners ähnelt der Architektur üblicher Rechner. Es sollte daher möglich sein, ihn ähnlich wie übliche Computer zu programmieren, allerdings auf einer sehr niedrigen Ebene und mit einem stark eingeschränkten Befehlssatz. Einige kleine Hinweise sollen helfen, diese Einschränkungen zu umgehen:

• Ein if-then-else kann man folgendermaßen implementieren: Zum logischen Wert (-1 oder 0) wird eine (konstante) Zahl b addiert, in das Register mit der Nummer b-1 wird der Ausdruck gespeichert, der im then-Zweig ausgeführt werden soll, in das Register b der Ausdruck für den else-Zweig. Eine Anwendung von a führt die Anweisung aus. Auf ähnliche Weise kann man eine switch-Anweisung realisieren.
• a stellt eine sehr einfache Form von Funktionsaufrufen dar. Innerhalb einer derart aufgerufenen Funktion sind aber keine direkten Programmverzweigungen möglich. Falls am Ende eines Programmstücks eine Verzweigung benötigt wird, schließt der entsprechende Ausdruck mit a ab, wie bei den Hinweisen zur Implementierung von if-then-else beschrieben. Diese Form der Programmierung ist unter dem Begriff continuation passing bekannt. Bei jedem anderen Abschluss des Ausdrucks kehrt die Funktion implizit an den Aufrufer zurück, indem mit den verbliebenen Befehlen in Register -6 fortgesetzt wird.
• Diese Form von Prozeduraufrufen kümmert sich nicht um lokale Variablen; solche gibt es im Modell gar nicht. Falls lokale Variablen benötigt werden, müssen diese selbst verwaltet werden, z.B. dadurch, dass man Zahlen oder Ausdrücke auf den Stack legt, über eine Basisadresse in einem Register darauf zugreift (dynamic link) und am Ende der Prozedur den Stack (und nötigenfalls den dynamic link) wieder auf den richtigen Wert setzt.

Testaufgabe (Verpflichtend):

Entwerfen Sie einen möglichst kurzen und effizienten Ausdruck (in einem Register) der entscheidet, ob eine Zahl eine Primzahl ist oder nicht, und testen Sie mit mehreren, auch größeren Zahlen.

Zusatzaufgaben für Interessierte:

Die Lösung dieser Zusatzaufgaben ist nicht verpflichtend und hat keinen Einfluss auf die Beurteilung.

Turing-Äquivalenz:

Es stellt sich die Frage, ob man mit diesem Taschenrechner wirklich alles Programmieren kann. Ist es damit möglich, eine Turing-Maschine zu bauen?

Quasi-parallele Programmierung:

Da alle Register geschrieben werden können ist es möglich, auch den Eingabepuffer zu verändern. Ist es damit möglich, Coroutinen zur quasi-parallelen Programmierung zu unterstützen? Versuchen Sie eventuell, die Primzahlberechnung mit Hilfe von Coroutinen zu implementieren.