Prüfungsvorbereitung

Beispielklausur http://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/klausur/

• was ist eine Umgebung (Env), welche Operationen gehören dazu?
• was ist eine Speicher (Store), welche Operationen gehören dazu?
• Gemeinsamkeiten/Unterschiede zw. Env und Store?
• Für (λx.xx)(λx.xx): zeichne den Syntaxbaum, bestimme die Menge der freien und die Menge der gebundenen Variablen. Markiere im Syntaxbaum alle Redexe. Gib die Menge der direkten Nachfolger an (einen Beta-Schritt ausführen).
• Definiere Beta-Reduktion und Alpha-Konversion im Lambda-Kalkül. Wozu wird Alpha-Konversion benötigt? (Dafür Beispiel angeben.)
• Wie kann man Records (Paare) durch Funktionen simulieren? (Definiere Lambda-Ausdrücke für pair, first, second)
• welche semantischen Bereiche wurden in den Interpretern benutzt? (definieren Sie Val, Action Val, CPS Val)
• welches sind die jeweils hinzukommenden Ausdrucksmöglichkeiten der Quellsprache (Exp)?
• wie lauten die Monad-Instanzen für Action, CPS, Parser, was bedeutet jeweils das bind (>>=)?
• warum benötigt man call-by-name für Abstraktionen über den Programmablauf (warum kann man if oder while nicht mit call-by-value implementieren)?
• wie kann man call-by-name simulieren in einer call-by-value-Sprache?
• wie kann man call-by-value simulieren in einer call-by-name-Sprache (Antwort: durch CPS-Transformation)
• Definiere Fakultät mittels Fixpunktoperator (Definiere das f in fak = fix f )
• Bezüglich welcher Halbordnung ist dieses f monoton? (Definiere die Ordnung, erläutere Monotonie an einem Beispiel.)
• Wie kann man Rekursion durch get/put simulieren? (Programmbeispiel ergänzen)
• Wie kann man Rekursion durch label/jump simulieren? (Programmbeispiel ergänzen)
• Für die Transformationen CPS, Closure Conv., Lifting, Registervergabe: welche Form haben jeweils Eingabe- und Ausgabeprogramm? Auf welchem Maschinenmodell kann das Zielprogramm ausgeführt werden? (Welche Operationen muß das Laufzeitsystem bereitstellen?)
• Was sind die Bestandteile eines Inferenzsystems (Antwort: Grundbereich, Axiome, Regeln), wie kann man ein Axiom als Spezialfall einer Regel auffassen?
• wie lauten die Inferenzregeln für das Nachschlagen eines Namens in einer Umgebung?
• Inferenzregeln für Applikation, Abstraktion, Let, If/Then/Else im einfach getypten Kalkül
• Geben Sie ein Programm an, das sich nicht einfach (sondern nur polymorph) typisieren läßt. Geben Sie den polymorphen Typ an.
• Inferenz-Regeln für Typ-Applikation, Typ-Abstraktion im polymorphen Kalkül
• für Typ-Rekonstruktion im einfach getypten Kalkül: Welches ist der Grundbereich des Inferenzsystems?
• geben Sie die Inferenzregel für Typrekonstruktion bei If/Then/Else an
• Geben Sie eine Inferenzregel für Typrekonstruktion an, durch die neue Variablen eingeführt werden.
• Wann ist σ ein Unifikator von zwei Termen s, t?
• Geben Sie zwei verschiedene Unifikatoren von f (a, X) und f (Y, Z) an. Einer davon soll streng allgemeiner als der andere sein. Begründen Sie auch diese Beziehung.
• Bestimmen Sie einen Unifikator von f (X_n, f (X_n-1,…, f (X₀, a)…)) und f (f (X_n-1, X_n-1), f (f (X_n-2, X_n-2),…, f (a, a)…)).