M. Sperber, H. Klaeren Wintersemester 1998/99

Compilerbau I

Blatt 9

Abgabe: 12.1.1999

1. [10 Punkte] Zeigen Sie, daß in der Danvy/Filinski-CPS-Transformation die Bindungszeitseparierung gewährleistet ist, d.h., daß in der Bildung von -Redexen immer auf trifft und immer auf .
2. [10 Punkte] Die Ausdrücke, welche die Danvy/Filinski''=CPS''=Transformation liefert, bilden eine echte Untermenge der Sprache der Lambda''=Ausdrücke. Geben Sie eine Grammatik für CPS-Ausdrücke an (falls nicht schon in der Vorlesung geschehen). Beweisen Sie, daß diese Grammatik genau die Sprache der CPS-Ausdrücke beschreibt.
3. [10 Punkte] Der CPS-Interpreter hat die Eigenschaft, daß die Continuations linear gefädelt (,,single-threaded``) sind. Das heißt, daß es zu jedem Zeitpunkt genau eine aktuelle Continuation gibt, die Continuation der aktuellen Continuation immer die vorherige aktuelle Continuation ist, und jede Continuation genau einmal aufgerufen wird.

   Wie ließe sich die Eigenschaft der linearen Fädelung für die Erzeugung von Maschinencode ausnutzen? Was für Konsequenzen hätte dies für die Implementierung von try/raise?

• Über dieses Dokument ...