\section{Anhang}

\begin{slide}{Prüfungsvorbereitung}

  \begin{itemize}
  \item was ist eine Umgebung (\verb|Env|),
    welche Operationen gehören dazu? 
  \item was ist eine Speicher (\verb|Store|),
    welche Operationen gehören dazu?
  \item Gemeinsamkeiten/Unterschiede zw. Env und Store?
  \item Für $(\lambda x.xx) (\lambda 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).
  \item Definiere Beta-Reduktion und Alpha-Konversion
    im Lambda-Kalkül. Wozu wird Alpha-Konversion benötigt?
    (Dafür Beispiel angeben.)
  \item Wie kann man Records (Paare) durch Funktionen
    simulieren? (Definiere Lambda-Ausdrücke für 
    \verb|pair, first, second|)
  \item welche semantischen Bereiche 
    wurden in den Interpretern benutzt?
    (definieren Sie \verb|Val, Action Val, CPS Val|)
  \item  welches sind die jeweils hinzukommenden 
    Ausdrucksmöglichkeiten der Quellsprache (\verb|Exp|)?
  \item wie lauten die Monad-Instanzen 
    für \verb|Action, CPS, Parser|, 
    was bedeutet jeweils das bind (\verb|>>=|)?
  \item warum benötigt man call-by-name für Abstraktionen
    über den Programmablauf 
    (warum kann man \verb|if| oder \verb|while| 
    nicht mit call-by-value implementieren)?
  \item wie kann man call-by-name simulieren
    in einer call-by-value-Sprache?
  \item wie kann man call-by-value simulieren
    in einer call-by-name-Sprache 
    (Antwort: durch CPS-Transformation)
  \item Definiere Fakultät mittels Fixpunktoperator
    (Definiere das \verb|f| in \verb|fak = fix f| )
  \item Bezüglich welcher Halbordnung ist dieses \verb|f|
    monoton? (Definiere die Ordnung, erläutere Monotonie
    an einem Beispiel.)
  \item Wie kann man Rekursion durch get/put simulieren?
    (Programmbeispiel ergänzen)
  \item Wie kann man Rekursion durch label/jump simulieren?
    (Programmbeispiel ergänzen)    
  \item 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?)
  \item Was sind die Bestandteile eines Inferenzsystems
    (Antwort: Grundbereich, Axiome, Regeln), 
    wie kann man ein Axiom als Spezialfall einer Regel auffassen?
  \item wie lauten die Inferenzregeln für das Nachschlagen eines
    Namens in einer Umgebung?
  \item Inferenzregeln für Applikation, Abstraktion, Let, If/Then/Else
    im einfach getypten Kalkül
  \item Geben Sie ein Programm an, das sich nicht
    einfach (sondern nur polymorph) typisieren läßt.
    Geben Sie den polymorphen Typ an.
  \item Inferenz-Regeln für Typ-Applikation, Typ-Abstraktion
    im polymorphen Kalkül
  \item für Typ-Rekonstruktion im einfach getypten Kalkül:
    Welches ist der Grundbereich des Inferenzsystems?
  \item geben Sie die Inferenzregel für Typrekonstruktion bei If/Then/Else an
  \item Geben Sie eine Inferenzregel für Typrekonstruktion an,
    durch die neue Variablen eingeführt werden.
  \item Wann ist $\sigma$ ein Unifikator von zwei Termen $s, t$?
  \item 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.
  \item Bestimmen Sie einen Unifikator von
    $f(X_n, f(X_{n-1}, \ldots, f(X_0, a) \ldots))$
    und $f(f(X_{n-1},X_{n-1}),f(f(X_{n-2},X_{n-2}),\ldots,f(a,a)\ldots))$.
  \end{itemize}


\end{slide}
