M. Sperber, H. Klaeren Wintersemester 1998/99

Compilerbau I

Blatt 6

Abgabe: 1.12.1998

1. [10 Punkte] Die Grammatik von Mini-Caml erfaßt nicht alle Korrektheitseigenschaften eines Programms, die für eine weitere Übersetzung notwendig sind. Insbesondere wird nicht überprüft, ob alle verwendeten Bezeichner auch tatsächlich gebunden sind. Implementieren Sie eine entsprechende Analyse mit folgender Signatur:

   val analyze_bound :
         'ident Camlsyn.program
            -> 'ident list
              -> ('ident Camlsyn.program * 'ident list)

   Für analyze_bound e l ist e ein Mini-Caml-Programm und l eine Liste eingebauter Bezeichner. Der Rückgabewert ist ein Tupel aus einem Mini-Caml-Programm, in dem Referenzen Ident i auf eingebaute Bezeichner durch Builtin i ersetzt worden sind, und einer Liste im Programm verwendeter aber nicht gebundener Bezeichner.
2. [5 Punkte] Geben Sie einen ``Un-Parser'' für Mini-Caml an, der aus der abstrakten Syntax wieder ein konkretes Programm produziert. Testen Sie den Un-Parser an einigen repräsentativen Beispielen.
3. [10 Punkte] Geben Sie eine Definition für einen Rechts-nach-Links-Call-by-Name-Lambda-Kalkül an und untersuchen Sie diesen. Ist er noch in der Lage, mit Sicherheit schwache Kopf-Normalformen zu finden? Tun Sie das gleiche für einen Rechts-nach-Links-Call-by-Value-Lambda-Kalkül. Wie vergleicht dieser sich mit seinem Links-Nach-Rechts-Gegenstück?
4. [5 Punkte] (Quelle: Thomas Beth, Universität Karlsruhe) Korrigieren Sie folgenden Induktionsbeweis:

   Alle Pferde haben die gleiche Farbe.

   Induktionsanfang: Für eine leere Menge von Pferden gilt die Behauptung trivialerweise.

   Induktionsschritt: Gegeben sei eine Menge von n+1 Pferden. Nehme ein Pferd aus der Menge -- die restlichen Pferde haben per Induktionsannahme die gleiche Farbe. Nimm ein anderes Pferd aus der Menge -- wieder haben die restlichen Pferde per Induktionsannahme die gleiche Farbe. Da die übrigen Pferde die Farbe nicht plötzlich gewechselt haben können, war es jeweils dieselbe Farbe, und alle n+1 Pferde haben diese Farbe.

• Über dieses Dokument ...