Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Allgemeines, Stimmung

Allgemeines, Stimmung

Pruefer: Phillipsen
Beisitzer: Blass
Zeit: 30 Minuten (voll ausgenutzt, nix zur Besprechung abgezwackt)

Ich habe mich etwa 10 Tage lang recht intensiv vorbereitet. Alle Folien zusammengefasst und aus Zusammenfassung gelernt, alle Uebungsaufgaben zweimal gemacht, Verstaendnisfragen mit Kommilitonen geklaert und vor allem einen Tag vor der Klausur alle Protokolle gemacht und Unklarheiten nochmal angeguckt.

Ich war ziemlich aufgeregt, weil ich bis dato in meinem Pruefungsjahrgang nur Leute kannte, die durchgefallen waren oder mit 4.0 rausgingen. Aber viele der Fragen waren schonmal in Protokollen dran. Wenn man die ordentlich durchmacht, sollte man nicht auf die Schnauze fliegen!

Um die Atmosphaere zu schildern, bietet sich die Frage zu Displays und die Folgefrage an. Hier waren naemlich beide kurz verwirrt. Die Atmosphaere war ziemlich locker. Aufgeregt war ich trotzdem weiterhin wie sau, weil viele Pruefer einem sagen, wenn man was richtiges gesagt hat und das hier nicht so genau der Fall war. Aber wenn man zum naechsten Thema geht, kann man wohl davon ausgehen, dass man entweder auf keinen gruenen Zweig mehr gekommen waere, oder man schon das richtige gesagt hat.

Code

int g;
      
int foo(int x, double y){/*unwichtig*/}
int foo(double x, int y){/*unwichtig*/}
int foo(int x, int y){ return 4*x + x/y + 3*y;} //[2]
      
int main(){
	int i = 5;
	int j = 6;
      
	return g + foo(i*1., j+2.0); //[1]
}

Fragen

B: Beisitzer P: Pruefer S: Ich

AST und Typpruefung

B: Wir beginnen bei [1]. Was passiert da, fang ganz vorne an.

S: Lexer erklaert, Parser erklart. Auf Nachfrage den Syntaxbaum zu malen, den AST gemalt und gesagt, dass ich den AST, nicht den Syntaxbaum mache:

return
   |
   +
  / \
 g  call foo
    /    \
   *      +
 /  \   /  \
i   1. j   2.0

S: Wollte zuerst call: int foo hinschreiben, aber hab mich dann verbessert, dass bei den Konstanten zwar der Typ schon klar ist, aber noch nicht beim Call, das erst in Typpruefung.

B: Ok, wie funktioniert denn die Typpruefung?

S: Typpruefung ist verschraenkt mit Namenspruefung, bei Deklaration Typ merken. Von unten nach oben die Typen annotiert und erwaehnt, dass es kein foo gibt, das auf die Parametertypen (double, double) passt.

B: Woher weiss ich denn den Typ, den des Returns? (Um mich auf Prototypen zu stupsen)

S: Naja, den tatsaechlichen kriege ich durch bottom-up durchgang durch AST, den erwarteten hole ich mir aus der umgebenden Funktion.

P: Sie haben jetzt Prototypen gar nicht erwaehnt. Wie funktionieren die?

S: Falsches Zeug gestammelt. Ich finde, das wird nicht richtig klar auf den Folien und ich war nicht in der entsprechenden Vorlesung. Hier ist die Loesung, wie sie mir Prof. Philippsen nach der Pruefung erklaert hat: Der Prototyp wird Top-Down durchgereicht. Bei Returns heisst das, beim Besuch der Funktion weiss ich ja schon, dass das Return vom Typ int sein muss. Den Prototyp vom foo muss man sich aber aus der Deklaration (ueber die Symboltabelle) rausfummeln. Oder so. Keine Garantie.

P: Ok, lassen wir das erstmal (schreibt ein F ins Protokoll und geht zum naechsten Thema, was ich nicht erwartet haette, weil ich da schon Horrorgeschichten gehoert habe, dass 10 Minuten auf ein Thema verschwendet wurden. Ich denke, wenn ich darum gebeten haette, waere das Thema garantiert abgebrochen worden, so hat er das sogar selbst entschieden).

Stack

B: Wie sieht denn der Stack der Funktion von [2] auf, angenommen das waeren in [1] zwei ints?

S:

 |-------------------|
 |   int y           |
 |   int x           |
 | Returnaddr        |
 | Framepointer      |
 |-------------------|

P: Sonst nix? (Hat er n paar mal gefragt, bis er zufrieden war, ich merge die Antworten jetzt mal)

S: Lokale Variablen, aber da gibts ja keine. Evtl Register sichern; ABI erklaert. Evtl Rueckgabewert, wenn nicht ueber Register zurueckgegeben. Evtl SV-Verweis, wenn verschachtelte Funktionen;

P: Wieso ist die Reihenfolge der Argumente da vertauscht ggue der Deklaration?

S: Fuer variable Argumentzahl. Wenn man einen Formatstring hat muesste man sonst fuer den Zugriff auf das erste Element erst alle Format-%-dingsis zaehlen, dann nochmal durchgehen und einsetzen. So kann man die Argumente direkt der Reihe nach von unten nach oben durchgehen.

P: Wozu benoetigt man den Framepointer?

S: Um dynamische Arrays zu realisieren. Haetten wir hier zB int[x] b; drin, dann muessten wir wissen, wie gross x ist, um die Speicherstelle von x vom SP aus zu finden (weil wir ja x*4 bytes aufsteigen muessten) ⇒ Henne-Ei-Problem. Mit dem FP kann man das x finden und damit die groeses des Arrays ausrechnen.

P: Wie ist das denn, braucht man den SV-Verweis nur bei static Funktionen?

S: Nein, auch bei verschachtelten nicht-static, aber wenn man so eine Closure returnt, dann muss man vorher Werte auf dem Heap sichern, sonst ist der Stackframe ja schon weggeraumt und der SV-Verweis zeigt ins nichts.

B: Wie ist das mit Displays?

S: Also bei der Typpruefung? Displays kommen ja spaeter nochmal bei Objektorientierung.

Beide kurz verwirrt B: Aeh… nein? P: Mhm. Doch, bei instanceof. S: Ja, genau. P: Ich denke, das war Antwort genug. (Antwort waere: Man will sich nach oben durchhangeln muessen, um den -n. SV-Verweis zu erhalten, deshalb speichert man sich die in einem Array. Dann hat man allerdings maximale Verschachtelungstiefe oder muss das Array teuer vergroesern.)

B: Ok. Dann mal uns doch mal den AST da hin. S: Also nochmal die gleiche Uebung? P: Ja, nen AST hat er ja da schon hingemalt. Aufwachen, Beisitzer!

Codeerzeugung

B: Na gut, dann wie koennte man da jetzt Code erzeugen?

S: Wir haben da ja verschiedene Verfahren kennen gelernt. Insbesondere Dynamische Programmierung, Graham Glenville, AST-Transformation. Ich mach mal mit Graham-Glenville.

B: Grinst. Nein, mach mal AST-Transformation.

(Meh, das hatte ich nicht detailliert gelernt)

S: Ok… also ich hab da Muster, (auf Nachfrage:) die werden aus der Maschinengrammatik generiert.

B: *Holt ein Blatt mit Regeln hervor* Mach mal das Muster hierfuer: R_i ← R_i op R_j

S:

    op
    /  \    ->   Ri
   Ri  Rj

Noch erklaert, dass man die auf den AST matcht und maximal grosse Verschlingung dargelegt (man spart sich Instruktionen und hofft, dass das dann schneller ist)

P: Und wenn eine einzelne langsamer ist?

S: Dann muss man da noch Semantiken an die Muster dranmachen, das braucht man uU auch, wenn ein spezielles Register benoetigt wird (zB bei Floats).

P: Und da gibts dann eine Regel fuer alle Eintraege des Kreuzprodukts aller R_i und R_j?

S: Kreuzprodukt? Nachgefragt, was er meint. Dann daemmerte mir, dass er wohl darauf hinaus wollte, dass das auf virtuellen Registern passiert und man anschliessend noch Graphfaerben machen muss.

P: Woher kommt jetzt dann der Code?

S: Bei jeder Anwendung einer Transformation wird der entsprechende Code emittiert.

P: Bottom-Up, oder einmal hier, einmal da im AST?

S: Falsches Zeug geredet. Die richtige Antwort war: Ja, einmal hier, einmal da. Das ist genau der Vorteil dieses Verfahrens ggue Graham-Glenville.

Graphfaerben

P: Wie funktioniert jetzt Graphfaerben?

S: Lebendigkeit, Kollisionen, Interferenzgraph etc erklaert. Das steht ja recht gut in den Folien. Mit etwas Stupsen kam ich noch darauf, dass die Eintraege im Graph im allgemeinen nicht die virt. Register sind, sondern Lebenspannen! Ein virt Reg kann theoretisch mehrere Lebenspannen haben (zB: R0 ← 0; R1 ← R0 op 4; … R0 ← 0; R3 ← R0 op 5;).

P: Sie hatten da noch Spilling erwaehnt. Wie laeuft das?

S: Man muss das Register auf dem Stack sichern und bei Zugriff wieder laden. Fuer optimierung laedt man in ein virtuelles Register und fuehrt Graphfaerben erneut durch.

P: AHA! Also muss da doch noch was auf den Stack (zeigt auf meinen gemalten Stack).

S: Ja, wenn man hier was spillen muesste, muesste es noch auf den Stack.

Damit war die Zeit um. Nach kurzer Besprechung wurde ich wie immer nach meinem Eindruck gefragt. Ich hatte schon ein paar Fehler, aber konnte iA zeigen, dass ich was wusste und auch verstanden hatte. Mit Note ziemlich zufrieden, der groebere Schnitzer bei den Prototypen und AST-Transformation ging nicht stark in die Benotung ein.