M. Sperber, H. Klaeren Wintersemester 1998/99

Compilerbau I

Blatt 7

Abgabe: 8.12.1998

1. [5 Punkte] Zeigen Sie, daß Y' mit folgender Definition ein Fixpunktkombinator für Links-Innen-Reduktion ist:

   

2. [5 Punkte] (Quelle: Ralf Hinze, Bonn) Zeigen Sie, daß F mit der folgenden Definition ein Fixpunktkombinator ist:

   

3. [5 Punkte] Schreiben Sie eine Funktion

   rename_uniquely : Ident.t program -> Ident.t program

   welche alle gebundenen Namen eines Programms unter Semantikerhaltung derart umbenennt, daß jeder Name nur einmal gebunden wird. Die Umbenennung soll so erfolgen, daß kein programmgebundener Bezeichner den gleichen Namen trägt wie ein Builtin. (Für die Lösung der Aufgabe ist es sinnvoll, die Struktur Ident zu erweitern und eine Referenz zu benutzen.)
4. [5 Punkte] Implementieren Sie ein Lösungsverfahren für reine Vereinigungsprobleme. Gegeben sei also eine Relation auf einer Menge A und eine mengenwertige Funktion . Gesucht ist eine Funktion , welche folgende Gleichung löst:

   

5. [10 Punkte] Implementieren Sie Lambda-Lifting als Abbildung

   caml_to_lambda : 'ident Camlsyn.program -> 'ident Lambda.scheme

   Wählen Sie dabei den Aufruf einer Funktion main : unit -> unit als Eintrittspunkt. Sie können dabei annehmen, daß in der abstrakten Syntax alle Bezeichner wie in Aufgabe 1 umbenannt worden sind. Ignorieren Sie dabei (für den Moment) raise und try.

• Über dieses Dokument ...