KSP Aufgabe 7
In dieser Aufgabenstellung soll das Rechnen mit Komponenten von
Records und Arrays implementiert werden. Bei uns sind diese beiden
Datenstrukturen (im Gegensatz zu C) "richtige Objekte", d.h. alle
Instanzen von Records und Arrays leben auf dem Heap und werden nur
ueber Zeiger zugegriffen. Das ist in Ninja nicht anders als in Java,
und deshalb heissen die Komponenten auch "Instanzvariable". Um Ihnen
einen Eindruck zu vermitteln, welche Berechnungen nun moeglich sind,
gibt's hier drei Beispielprogramme:
a) listrev.nj
(Umdrehen einer Liste von Zahlen)
b) twodim.nj
(Belegen und Ausgeben eines zweidimensionalen Arrays)
c) matinv.nj
(Invertieren einer 2x2-Matrix mit Bruechen als Komponenten)
1. Studieren Sie die neu hinzugekommenen Instruktionen des dann
kompletten Befehlssatzes unserer VM, wobei
Sie die Diskussion der Struktur von Objekten
und die Erlaeuterungen zu Referenzvergleichen
hinzuziehen sollten.
2. Ueberpruefen Sie Ihr Verstaendnis der neuen Befehle! Vorschlag:
Sie lassen das o.g. Programm matinv.nj
uebersetzen und entnehmen dem entstandenen Assemblerprogramm die
Funktionen
newFraction ,
subFraction und
newMatrix .
Dann ergaenzen Sie die Funktionen Zeile fuer Zeile um einen
aussagekraeftigen Kommentar, was da jeweils genau passiert.
Sie sollten zu jedem Zeitpunkt den Stack der VM zeichnen koennen!
3. Implementieren Sie die neuen Instruktionen. Sie koennen mit der
Umsetzung der Objektstruktur beginnen. Es gibt ja zwei Sorten von
Objekten: primitive Objekte (die eine Anzahl Bytes speichern) und
zusammengesetzte Objekte (die eine Anzahl Objektreferenzen speichern).
Das hoechste Bit des Zaehlers, der in jedem Objekt enthalten ist,
bestimmt, ob der Zaehler Bytes oder Instanzvariable zaehlt. Deswegen
kann man als Interface zum Objektspeicher die beiden folgenden
Funktionen vorsehen:
ObjRef newPrimitiveObject(int numBytes);
ObjRef newCompoundObject(int numObjRefs);
Dann realisieren Sie new, getf und putf. Denken Sie daran,
alle Instanzvariablen mit nil zu initialisieren! Als naechstes
kommen die Instruktionen fuer Arrays an die Reihe; bitte auch
hier die Initialisierung nicht vergessen. Und wo wir schon dabei
sind: die lokalen Variablen einer Methode muessen ebenfalls mit
nil initialisiert werden, genauso wie die globalen Variablen.
Noch ein Hinweis: Ihre VM muss erkennen, wenn auf ein Objekt
zugegriffen werden soll, aber nur eine nil-Referenz vorliegt.
Ebenso muessen Sie einen Zugriff auf ein Array mit unzulaessigem
Index abfangen. Testen Sie alle Befehle und Fehlerbedingungen
ausfuehrlich! Vergessen Sie nicht die Instruktion "getsz" zum
Bestimmen der Groesse eines Objektes, sowie die Instruktionen
zu den Referenzvergleichen!
4. Passen Sie Ihren Debugger der veraenderten Situation an.
Insbesondere die Inspektion von Objekten wird wahrscheinlich
auf das MSB des Zaehlers Ruecksicht nehmen muessen.
5. Natuerlich gibt's einen erweiterten Compiler ,
der mit Records und Arrays umgehen kann (dazu die
Grammatik , die Tokens ,
und die vordefinierten Bezeichner ), sowie
einen passenden Assembler , der die neuen
Instruktionen assemblieren kann.
6. Hier wie immer die Referenzimplementierung:
njvm
Aufgaben fuer Tests
a) Entwerfen Sie eine Datenstruktur zum Speichern von Baeumen
fuer arithmetische Ausdruecke in Ninja (ganz so, wie wir das in
der Vorlesung fuer C gemacht haben). Stellen Sie die entsprechenden
Konstruktoren bereit, sowie eine Methode, die einen Baum mit
korrekter Einrueckung ausgibt. Ueberpruefen Sie Ihr Programm
mit dem Ausdruck "5 - (1 + 3) * (4 - 7)": diese
Konstruktoraufrufe sollten einen
Baum erzeugen, der, wenn er ausgegeben wird, diese
Ausgabe produzieren sollte. Nein,
das ist kein Fehler in der Aufgabenstellung... ;-)
b) Ersetzen Sie die Ausgabe in a) durch eine Auswertefunktion
("Evaluator"). Kommt bei dem o.g. Beispiel wirklich 17 heraus?
c) Ersetzen Sie jetzt den Evaluator aus b) durch eine Prozedur
zum Erzeugen von Ninja-Assembler. Wenn Sie den erzeugten Code
fuer das o.g. Beispiel assemblieren und ausfuehren lassen, kommt
dann wieder 17 heraus?