Praktikum:

Funktionale Programmierung

Anleitung zum Praktikum

Sommersemester 2007

Stand vom: 4. Juni 2007

Professur für Künstliche Intelligenz und Softwaretechnologie

Institut für Informatik

Johann Wolfgang Goethe-Universität

Frankfurt am Main

Inhaltsverzeichnis

1 Allgemeines 3

1.1 Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Computerraum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.2 Regelmäßiges Treffen . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.3 Scheinvergabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Quellcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Dokumentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Kurzübersicht über das Projekt 8

2.1 Das Softwareprojekt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Die Sprache LFP+C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Aufbau eines Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4 Compiler, Interpreter, Virtuelle Maschine . . . . . . . . . . . . . . . . . . . 11

2.5 Zeitplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5.1 Präsentation der Ergebnisse . . . . . . . . . . . . . . . . . . . . . . 13

3 Der Compiler 15

3.1 Lexikalische Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2 Syntaktische Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2.1 Übersetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.3 Semantische Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4 Transformation in CoreLFPCR . . . . . . . . . . . . . . . . . . . . . . . . 24

1

4 Verzögert auswertende Abstrakte Maschinen 27

4.1 Die Abstrakte Maschine Mark 1 zur Ausführung deterministischerCoreLFPCR-Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.1.1 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2 Verbesserungen von Mark 1 – Mark 2 . . . . . . . . . . . . . . . . . . . . . 35

4.2.1 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.3 Nebenläufigkeit – Concurrent Mark 2 . . . . . . . . . . . . . . . . . . . . . 39

4.3.1 Auswahl eines Threads zur Auswertung . . . . . . . . . . . . . . . . 42

4.3.2 Zustandsübergang . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.3.3 Beenden von Threads . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.4 Von Concurrent Mark 2 zur Virtuellen Maschine . . . . . . . . . . . . . . . 51

4.4.1 Codegenerierung und Codeloader der VM . . . . . . . . . . . . . . 51

4.4.2 lfpcc – Der Compiler für LFP+C . . . . . . . . . . . . . . . . . . . 51

4.4.3 lfpcvm – Die Virtuelle Maschine . . . . . . . . . . . . . . . . . . . 52

4.4.4 lfpci – Ein Interpreter für LFP+C . . . . . . . . . . . . . . . . . . 52

4.5 Automatische Speicherverwaltung . . . . . . . . . . . . . . . . . . . . . . . 52

5 Hinweise zu einzelnen Themen 53

5.1 Modularisierung in Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.1.1 Module in Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.2 Parser und Parsergeneratoren . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.2.1 Parser und Syntaxanalyse . . . . . . . . . . . . . . . . . . . . . . . 59

5.2.2 Parsergeneratoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.2.3 Happy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.3 Haddock – A Haskell Documentation Tool . . . . . . . . . . . . . . . . . . 66

5.3.1 Dokumentation einer Funktionsdefinition . . . . . . . . . . . . . . . 66

A Zusatzaufgaben 68

A.1 Transformation in CoreLFPCDB – Verwendung von De Bruijn Indices . . . 68

A.2 Die Abstrakte Maschine Mark 3 . . . . . . . . . . . . . . . . . . . . . . . . 70

A.2.1 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

A.3 Concurrent Mark 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

A.3.1 Zustandsübergang . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

A.3.2 Beenden von Threads . . . . . . . . . . . . . . . . . . . . . . . . . . 79

2

Kapitel 1

Allgemeines

1.1 Organisation

1.1.1 Computerraum

Der Raum 027 (im Keller des Informatikgebäudes) ist Montags von 14-18h reserviert, d.h.wer möchte kann dann an diesen Rechnern arbeiten. Dieser Termin ist kein Pflichttermin,sondern stellt nur ein Angebot dar.

1.1.2 Regelmäßiges Treffen

Montags, um 12 c.t. findet in Seminarraum 9 ein regelmäßiges Treffen aller Praktikums-teilnehmer statt. Hier sollen Fragen und Probleme diskutiert werden, die Anwesenheit istsomit i.A. erforderlich.

1.1.3 Scheinvergabe

Der Leistungsschein für das Praktikum wird für die korrekte und vollständige Bearbeitungder Aufgaben vergeben.

Es sollen je 4 Praktikanten für das Praktikum eine Gruppe bilden.

Zur Erfüllung der Aufgaben gehört die Abgabe und Präsentation eines hier auf den Rech-nern der RBI laufenden, kommentierten Programms, sowie eine schriftliche Ausarbeitung,die folgenden enthält:

• eine kurze Erläuterung der Grundlagen, die zur Lösung der Aufgabe notwendigwaren.

• eine kurze Beschreibung der Lösung selbst.

• ein Protokoll, das den Prozess der Problemlösung dokumentiert, hierbei sollte insbe-sondere erfasst werden, wieviel Zeit für die einzelnen Tätigkeiten benötigt wurden,und wie die Arbeiten innerhalb der Gruppe aufgeteilt wurden.

3

• die Dokumentation der durchgeführten Tests.

In Abschnitt 2.5 ist ein Zeitplan gegeben, dieser sollte eingehalten werden. Es gibt dreiZeitpunkte zu denen (Zwischen-)ergebnisse präsentiert werden sollen. Gleichzeitig soll zudiesen Zeitpunkten der aktuelle Stand der schriftlichen Ausarbeitung abgegeben werden!

Außerdem sei nochmal erwähnt, dass die Beteiligung bzw. das Stellen von Fragen beiden Besprechungen ausdrücklich erwünscht ist; davon hat nämlich sowohl der Frager, derBetreuer als auch die Kommilitonen etwas.

1.2 Haskell

Die Implementierung der Programme soll in Haskell erfolgen. Es wird vorausgesetzt, dassdie Teilnehmer bereits über Kenntnisse in Haskell oder anderen Funktionalen Program-miersprachen verfügen.

1.2.1 Haskell

Haskell1 ist eine der zur Zeit wohl bedeutendsten, nicht-strikten, funktionalen Program-miersprachen. Wer sich eingehender in Haskell vertiefen möchte sei auf den Haskell-Report[6] verwiesen, in dem die Sprache definiert wird.

Zur Einarbeitung in Haskell sind das deutsche Buch [2], die Bücher [16], [1] sowie [4] undauch die Skripte [12] und [11] empfehlenswert.

Für Haskell gibt es mittlerweile eine recht große Anzahl von Standardbibliotheken,die hierarchisch organisiert sind. Die Dokumentation der Bibliotheken ist online unterhttp://www.haskell.org/ghc/docs/6.6/html/libraries/index.html zu finden.

Zum Haskell-Programmieren stehen uns Hugs und GHC zur Verfügung.

GHC

Der Glasgow Haskell Compiler2 hält sich an den Haskell-Report. Im GHC gibt es Er-weiterungen, die z.B. die Typklassen betreffen. Der GHC ist fast vollständig in Haskellgeschrieben und erzeugt C-Code als Zwischencode, der dann von einem auf dem Systemverfügbaren C-Compiler in ein ausführbares Programm übersetzt wird. Diese Tatsachemacht den GHC äußerst portierbar. Für einige Plattformen gibt es zusätzlich einen Code-Erzeuger, dessen Verwendung die Übersetzungszeit reduziert, aber nicht zu so gut opti-miertem Code führt wie die Verwendung des GNU C Übersetzers. GHC bietet zusätzlichnoch den GHCi, der eine interaktive Version des GHC darstellt.

1Die offizielle Homepage zu Haskell ist http://haskell.org.2Die Homepage des GHC ist http://haskell.org/ghc.

4

http://www.haskell.org/ghc/docs/6.6/html/libraries/index.htmlhttp://haskell.orghttp://haskell.org/ghc

Hugs

Hugs3 steht für Haskell Users Gofer System und ist ein Interpreter der Sprache Haskell98. Es gibt ihn für verschiedene Rechner und Betriebssysteme: darunter Mac, Windows,Unix, Linux. Hugs kann zum schnellen Testen von Implementierungen benutzt werden,verfügt jedoch nicht über den für das Praktikum notwendigen vollen Funktionsumfang,da z.B. kein Preprocessing mittels Hugs durchgeführt werden kann.

1.3 Quellcode

Der Quellcode sollte wartbar sein, und dementsprechend aufgebaut, dokumentiert undkommentiert werden.

Die vorgegebenen Dateien sind mithilfe der hierarchischen Modulstruktur (siehe Ab-schnitt 5.1) strukturiert. Sämtlicher neuer Quellcode sollte in diese Struktur eingefügtwerden. Zudem sollte durch geeignete Import- und Export-Listen in den Moduldeklara-tionen eine geeignete Kapselung erfolgen.

Die bereits vorgegebene Struktur sieht wie folgt aus:

LFPC|-- AbsM| |-- CodeGen.lhs| |-- ConcurrentMark3.lhs| |-- Environment.lhs| |-- Heap.lhs| |-- IEnvironment.lhs| |-- Mark1.lhs| |-- Mark2.lhs| |-- Mark3.lhs| |-- Stack| | |-- CStackElem.lhs| | ‘-- StackElem.lhs| ‘-- Stack.lhs|-- Compiler| ‘-- Main.lhs|-- CoreL| |-- CoreExpression.lhs| |-- MachineExp.lhs| ‘-- TransCode.lhs|-- Interpreter| ‘-- Main.lhs|-- Parse| |-- InternalOp.hs| |-- InternalOp.lfp| |-- Lex.lhs| ‘-- Parser.ly|-- Run.lhs|-- SemAna

3Die Homepage von Hugs ist http://haskell.org/hugs/.

5

http://haskell.org/hugs/

| ‘-- RenameBV.lhs|-- Util| |-- Declarations.lhs| ‘-- PTree.lhs‘-- VM

‘-- Main.lhs

Damit der ghci das Modul auch findet, muss das oberste Verzeichnis der Modulstrukturfür ihn auffindbar sein. Dafür gibt es beim ghci den Parameter

-i Search for imported modules in the directory .

Wenn wir z.B. gerade im Verzeichnis LFPC/Parse/ sind und wollen das Modul mit Da-teinamen Lex.lhs laden, so sollten wir ghci wie folgt aufrufen:

ghci -i:../../ Lex.lhs

Nahezu sämtliche vorgegebenen Quellcode-Dateien sind im”Literate Haskell“-Stil ver-

fasst. Hierbei werden alle Text-Zeilen als Kommentar interpretiert, es sei denn sie be-ginnen mit > , zusätzlich muss sich zwischen Kommentar und Codezeilen immer eineLeerzeile befinden, ansonsten bekommen wir eine Fehlermeldung:

.... line 8: unlit: Program line next to comment

phase ‘Literate pre-processor’ failed (exitcode = 1)

Der Quellcode wird mittels CVS4 verwaltet werden. Genauere Informationen zum Zugangzum CVS-Server werden während der ersten Besprechung bekannt gegeben.

1.3.1 Dokumentation

Die erstellten Programme sollten ausführlich kommentiert werden, so dass ein”Leser“

des Programms dieses nachvollziehen kann. Zusätzlich soll für die Module eine HTML-Dokumentation mit Hilfe des Tools Haddock5 erstellt werden. Ein kurze Anleitung zuHaddock ist im Abschnitt 5.3 zu finden. Es sei jedoch angemerkt, dass eine reine Haddock-Dokumentation nicht ausreicht, da mit Haddock nur die exportierten Funktionen undDatentypen dokumentiert werden und zudem eher deren Verwendung und nicht derenImplementierung erklärt wird.

Das Erstellen der Dokumentation mit Haddock erfordert u.a. einen Aufruf sämtlicher Mo-dule innerhalb eines Kommandos, zudem muss bei Verwendung von Literate Haskell einPreprocessing-Schritt durchgeführt werden. Um dies zu automatisieren, steht das Shell-Skript genDoc.sh (im Verzeichnis src) zur Verfügung, welches im Abschnitt 5.3 kurzerläutert wird.

4Concurrent Versions System, http://www.nongnu.org/cvs/5http://haskell.org/haddock

6

http://www.nongnu.org/cvs/http://haskell.org/haddock

1.4 Tests

Sämtliche implementierten Funktionen, Datenstrukturen und Module sollten getestet wer-den. Teilweise sind Testdaten bzw. Testaufrufe vorgegeben. Diese müssen durchgeführtund im Idealfall auch bestanden werden. Es ist aber auch notwendig eigene Tests mitsinnvoll überlegten Testaufrufen durchzuführen. Sämtliche Tests sind zu dokumentierenund derart zu gestalten, dass sie leicht erneut durchgeführt, d.h. reproduziert, werdenkönnen.

7

Kapitel 2

Kurzübersicht über das Projekt

2.1 Das Softwareprojekt

Innerhalb des Praktikums soll ein Compiler für eine funktionale Programmiersprachenamens LFP+C entwickelt werden. LFP+C wertet verzögert aus und verfügt zusätzlichüber Programmkonstrukte amb und por zur nebenläufigen Auswertung.

Im Praktikum sollen die wesentlichen Phasen des Kompilierens für LFP+C implementiertwerden, und im wichtigerer Teil werden verschiedene aufeinander aufbauende abstrakteMaschinen bzw. einer virtuellen Maschine implementiert. Im nächsten Abschnitt wird dieProgrammiersprache LFP+C vorgestellt. Anschließend wird ein Überblick über das Projektgegeben.

2.2 Die Sprache LFP+C

Abbildung 2.1 zeigt die vollgeklammerte Syntax der Sprache LFP+C.

Die Sprache LFP+C verfügt über Variablen, Abstraktionen, Applikation, rekursive letrec-Ausdrücke, Zahlen mit den Operationen Addition (+) und einem Nulltest (null?), Boo-lesche Werte True und False, Paare (geschrieben als (a,b)), Listenkonstruktoren (:)und ([]), case-Ausdrücke um Listen, Paare oder Boolesche Werte zu zerlegen. Zusätzlichzur Grammatik muss gelten, dass die Variablen V1, . . . , Vn der Bindungen von letrec-Ausdrücken paarweise verschieden sind, gleiches gilt für die Variablen V1 und V2 in case-Alternativen. Zudem darf es keine doppelten Alternativen, d.h. Alternativen für den selbenKonstruktor innerhalb der case-Alternativen geben.

Als besondere Spezialität gibt es die beiden nichtdeterministischen Operatoren amb undpor. Während das parallele

”Oder“ por schwach nichtdetermintistisch ist, wird durch

amb starker Nichtdeterminismus eingeführt. Schwacher Nichtdeterminismus meint hier-bei, dass der Wert eines Programms eindeutig ist, obwohl es verschiedene Möglichkeiten(Auswertungen) gibt diesen Wert zu erreichen. Hingegen bedeutet starker Nichtdetermi-nismus, dass je nach gewähltem Auswertungspfad das Programm verschiedene Werte alsErgebnis liefern kann. Ein Überblick über verschiedene nichtdeterministische Operatoren

8

Expr ::= Var | Int | True | False | [] | (Expr 1:Expr 2) | (Expr 1,Expr 2)| (\Var -> Expr )| (Expr 1 Expr 2)| (case Expr of {Alt 1 . . .Alt n})| (letrec Var 1 = Expr 1, . . . ,Var n = Expr n in Expr n+1)| (amb Expr 1 Expr 2)| (por Expr 1 Expr 2)| (Expr 1 + Expr 2)| (null? Expr )

Alt ::= Pat -> Expr

Pat ::= True | False | [] | (Var 1:Var 2) | (Var 1,Var 2)

Abbildung 2.1: Vollgeklammerte Syntax der Sprache LFP+C

und Arten von Nichtdeterminismus in Funktionalen Programmiersprachen ist z.B. in [15]zu finden.

Die Semantik von por lässt sich ungefähr durch die folgenden Gleichungen beschreiben,wobei ⊥ für einen Ausdruck steht, dessen Auswertung nicht terminiert.

por s t = True, falls s oder t zu True auswertetpor s t = False, falls s und t zu False auswertenpor s t = ⊥, in allen anderen Fällen.

Eine Anwendung des por Operators ist die Beschreibung und semantische Modellierungvon sequentiellen Schaltungen mit asynchronen Anteilen (direkten Rückkopplungen) inn-herhalb von funktionalen Programmiersprachen. Eine Untersuchung dazu ist z.B. in [13]zu finden.

Die Semantik von amb (welches auf [8] zurück geht und von”ambigious“ abgeleitet ist).

kann inetwa durch folgende Gleichungen spezifiziert werden:

amb s t = t, falls die Auswertung von s nicht terminiert.amb s t = s, falls die Auswertung von t nicht terminiert.amb s t = s oder t, falls die Auswertungen von s und t terminieren.

Untersuchungen von call-by-need Lambda-Kalkülen, die über einen amb-Operatorverfügen sind in [5, 9, 10] zu finden.

Die beiden nichtdeterministischen Operatoren können durch nebenläufige Auswertungimplementiert werden, für einen Ausdruck (por s t) bzw. (amb s t) wird jeweils ein ne-benläufige Auswertung für s als auch für t gestartet. Im Falle des amb wird sobald einer der

9

beiden Threads einen Wert liefert, dieser als Wert des Gesamtausdrucks übernommen. ImFalle por wird True als Wert übernommen, sobald einer der beiden Threads True liefert,und False falls beide nebenläufigen Auswertungen mit den Wert False beendet wurden.

Wir geben noch einige Beispiel-Ausdrücke an, um zu verdeutlichen, wie in LFP+C pro-grammiert wird.

Beispiel 1. Eine Funktion, die eine Zahl verdoppelt, kann definiert werden als

letrec double = \x -> x+x in double

Die Auswertung von (letrec double = \x -> x+x in double) 20 ergibt 40.

Beispiel 2. Ein Ausdruck, der die Liste [1, 2, 3] von Zahlen, umdreht kann in LFP+C

programmiert werden als

letrec reverse = \xs -> case xs of {

[] -> [],

(y:ys) -> append (reverse ys) (y:[])

},

append = \xs -> \ys -> case xs of {

[] -> ys,

(u:us) -> u:(append us ys)

}

in reverse 1:2:3:[]

Die Auswertung ergibt dann (3:(2:(1:[])))

Beispiel 3. Die folgende asynchrone Schaltung

kann in LFP+C beschrieben werden durch:

\a ->

letrec

x = por x y,

y = por z y,

z = por (not a) a,

not = \b -> case b of {True -> False, False -> True}

in x

Angewendet auf True oder False liefert die Funktion stets True.

Beispiel 4. Ein Ausdruck der potentiell zu jeder natürlichen Zahl auswerten kann ist

letrec nat = \x -> amb (nat (x+1)) x in nat 1

Die Auswertung des amb kann entweder das aktuelle x wählen oder eins dazu addierenund dann weitermachen.

10

2.3 Aufbau eines Compilers

Wir beschreiben grob die Phasen eines Compilers

Lexikalische Analyse, Scanning Hierbei wird der Quelltext in einen Strom von Tokentransformiert, Leerzeichen, Umbrüche, Kommentare usw. werden dabei entfernt. EinToken ist eine syntaktische Einheit, wie z.B. Schlüsselwörter (letrec, case, in,. . . )oder Zahlen. Der Lexer sollte dabei den Eingabestring nur einmal durchlaufen undsomit lineare Zeit (in der Anzahl der Zeichen) verbrauchen. Die Ausgabe des Lexerswird an den Parser übergeben.

Syntaktische Analyse, Parsing Hier wird geprüft, ob der Tokenstrom von der kon-textfreien Grammatik hergeleitet wird, d.h. das Programm syntaktisch korrekt ist.Es gibt hierfür verschiedene Parse-Methoden, wir werden einen sog. Shift-Reduce-Parser automatisch mithilfe eines Parsergenerators erzeugen. Die Ausgabe des Par-sers ist i.A. ein Syntaxbaum, wir werden den Syntaxbaum mittels eines Haskell-Datentyps darstellen, wobei er zugleich ein wenig modifiziert wird.

Semantische Analyse Hierbei wird das Programm auf semantische Fehler überprüft.Z.B. wird bei manchen imperativen Programmen geprüft, ob alle benutzten Va-riablen auch deklariert sind, oder auch ein Typcheck durchgeführt. Wir werden indieser Phase prüfen, ob unser Programm geschlossen ist, d.h. keine freien Variablenenthält.

Zwischencodeerzeugung Hier wird Code für eine abstrakte Maschine erzeugt.

Codeoptimierung Der erzeugte Zwischencode wir optimiert.

Codeerzeugung Erzeugung eines Programms für eine reale Maschine. Wir werden je-doch keinen Code für eine reale Maschine, sondern

”ASCII-Code“ für eine virtuelle

Maschine erzeugen.

2.4 Compiler, Interpreter, Virtuelle Maschine

Abbildung 2.2 gibt einen ungefähren Überblick über die einzelnen Teilschritte unseresCompilers (LFPCC), der Virtuellen Maschine (LFPCVM) und des Interpreters (LFPCI),welche wir im Praktikum implementieren werden.

Neben den einzelnen Phasen des Compilers wird im Praktikum, wie bei der Codeerzeu-gung schon erwähnt, eine virtuelle Maschine erstellt. Wir werden jedoch vorher verschie-dene Varianten der abstrakten Maschine von Sestoft [14] implementieren und diese umnebenläufige Auswertung erweitern, was notwendig ist, um die beiden nichtdeterministi-schen Operatoren korrekt auswerten zu können. Schließlich wird die virtuelle Maschinedaraus relativ einfach abgeleitet. Der rechte Teil von Abbildung 2.2 zeigt die einzelnenMaschinen.

11

Abbildung 2.2: Projektübersicht

12

Hierbei ist zu bemerken, dass die Maschine Mark 2 nur eine Verbesserung der MaschineMark 1 ist, die Machine Mark 3 eine Verbesserung der Maschine Mark 2 ist, aber mo-difizierten Programmcode erwartet. Die Maschinen Mark 1, Mark 2 und Mark 3 könnennur deterministische Programme, d.h. Programme, die die Operatoren por und amb nichtenthalten, ausführen. Die Maschine Concurrent Mark 3 ist schließlich eine Erweiterungder Maschine Mark 3 um nebenläufige Auswertung. Die bisher genannten Maschinen er-halten Datenstrukturen (Bäume) als Eingabe, und sind daher nicht direkt als VirtuelleMaschinen brauchbar (jedoch als Interpreter, wie die Abbildung schon zeigt). Deswegenwird ein Programm in der letzten Phase des Compilers in ASCII-Code konvertiert, derdann in eine Datei geschrieben werden kann. Auf der Maschinen-Seite wird vor die Con-current Mark 3-Maschine ein Code-Loader gestellt, der den ASCII-Code liest und darauswieder die Datenstruktur für Programme erstellt.

Die Implementierung der abstrakten Maschinen wird einen Großteil der für das Prakti-kum eingeplanten Zeit beanspruchen, weswegen wir das eigentlich Compilieren möglichstzügig abschließen wollen. Aus diesem Grund werden hier größere Programmteile (wie derGroßteil des Parsers) schon zur Verwendung vorgegeben.

2.5 Zeitplan

In Tabelle 2.1 ist der Zeitplan abgebildet, wobei das Projekt in sieben Projektabschnitteunterteilt ist. Man beachte, dass Aufgabe ?? zunächst nach Ende des zweiten Abschnittsübersprungen wird und erst im vierten Abschnitt bearbeitet wird.

2.5.1 Präsentation der Ergebnisse

Ergebnisse sollen dreimal präsentiert werden:

• Nach Abschluss von Teil 2

• Nach Abschluss von Teil 43

• Nach Abschluss aller Teile.

Zu diesen drei Zeitpunkten soll auch der aktuelle Stand der Ausarbeitung sowie die bisdahin vorhanden Programme abgegeben werden.

13

Projektabschnitt ZugehörigeAufgaben

beendet bis(Bearbeitungszeit)

Teil 1:Lexen und Parsen

Aufgabe 1Aufgabe 2Aufgabe 3

30. April(2 Wochen)

Teil 2:Semantische Analyse und Transformation in einfache-re Syntax

Aufgabe 4Aufgabe 5

07. Mai(1 Woche)

Teil 3:Abstrakte Maschinen Mark 1 und Mark 2

Aufgabe 6Aufgabe 7Aufgabe 8Aufgabe 9Aufgabe 10Aufgabe 11Aufgabe 12Aufgabe 13Aufgabe 14

28. Mai4.Juni(34 Wochen)

Teil 4:Einführung von de Bruijn-Indices und die AbstrakteMaschine Mark 3

Aufgabe 26Aufgabe 27Aufgabe 28Aufgabe 29

11. Juni(2 Wochen)

Teil 5:Nebenläufigkeit: Die Abstrakte Maschine ConcurrentMark 3 2

Aufgabe 15Aufgabe 16Aufgabe 17Aufgabe 18Aufgabe 32Aufgabe 19Aufgabe 20

2. Juli25. Juni(3 Wochen)

Teil 6:Codeerzeugung, Compiler, Interpreter und die Virtu-elle Maschine

Aufgabe 21Aufgabe 22Aufgabe 23Aufgabe 24

9. Juli(12 Wochen)

Teil 7:Verbesserungen: Garbage Collection

Aufgabe 2516. Juli(1 Woche)

Tabelle 2.1: Zeitplan

14

Kapitel 3

Der Compiler

CExpr ::= letrec Binds in CExpr Const ::= Var | Int | False | True | []| \Var -> CExpr| AExpr Binds ::= Bind ,Binds | Bind

AExpr ::= AExpr Expr Bind ::= Var =CExpr| Expr

Alts ::= Alt ,Alts | AltExpr ::= amb Expr Expr

| por Expr Expr Alt ::= Pat -> CExpr| Expr +Expr| null? Expr Pat ::= True | False | []| Expr :Expr | Var :Var | (Var ,Var )| (CExpr ,CExpr )| case Expr of { Alts }| \Var -> Expr| Const| (CExpr )

Abbildung 3.1: Die Syntax der Programmiersprache LFP+C

In Abbildung 3.1 ist die Syntax der Sprache dargestellt, wie sie im Parser verwendet wird,.Hierbei sind kursive Symbole Nichtterminale. Worte der Sprache LFP+C werden mit demNichtterminal CExpr als Startsymbol gebildet. Desweiteren ist Int das Nichtterminal für(positive als auch negative) Ganzahlen und Var sind Variablennamen, die aus Buchstabenund Zahlen bestehen dürfen, jedoch mit einem Kleinbuchstaben beginnen müssen. Incase-Alternativen müssen die Pattern-Variablen verschieden sein, in letrec-Ausdrückenmüssen die Variablen in den Bindungen paarweise verschieden sein.

Die Grammatik ist noch mehrdeutig, deswegen legen wir noch die folgenden Assoziati-vitäten fest: letrec-Ausdrücke, Abstraktionen, case-Ausdrücke und der Listenkonstruk-tor (:) sind rechts geklammert, während die Addition (+) wie üblich links-assoziativ ist.

15

Die Operatoren amb und por sind ebenfalls links zu klammern. Damit der Rumpf einerAbstraktion, der Ausdruck nach dem in bei letrec-Ausdrücken möglichst weit reichen,haben diese niedrigere Priorität als die anderen Operationen.

Obige Grammatik lässt bei case-Alternativen auch mehrere”doppelte“ Alternativen zu,

wir verbieten sie jedoch. Zuwenige Alternativen sind jedoch erlaubt, die fehlenden Alter-nativen werden während des Parsens durch Dummy-Alternativen aufgefüllt.

3.1 Lexikalische Analyse

Die Grammatik zu LFP+C enthält keine Kommentare, wir nehmen jedoch an, dass Zeilen-kommentare, eingeleitet durch --, bis zum Zeilenende möglich sind, ebenso wie beliebigeZeilenumbrüche, Leerzeichen und Tabulatoren. Diese werden bei der lexikalischen Analyseentfernt. Ziel der Lexikalischen Analyse ist es, den reinen Quelltext in einen Strom (eineListe) von Token zu konvertieren.

Hierfür soll der Datentyp LFPCTok verwendet werden, der neben den Programmsymbolenauch Markierungen über den Ort (Zeile, Spalte) des entsprechenden Tokens enthält. Diesdient zur Produktion von brauchbaren Fehlermeldungen.

> type CodeMark = (Int,Int) -- (Row, Column)

> data LFPCTok = TokInt CodeMark Integer -- Ganzzahl

> | TokVar CodeMark String -- Variable

> | TokTrue CodeMark -- True

> | TokFalse CodeMark -- False

> | TokNil CodeMark -- []

> | TokCons CodeMark -- :

> | TokPlus CodeMark -- +

> | TokIsNull CodeMark -- null?

> | TokLet CodeMark -- letrec

> | TokIn CodeMark -- in

> | TokCase CodeMark -- case

> | TokOf CodeMark -- of

> | TokComma CodeMark -- ,

> | TokCBOpen CodeMark -- {

> | TokCBClose CodeMark -- }

> | TokArrow CodeMark -- ->

> | TokLam CodeMark -- \

> | TokBOpen CodeMark -- (

> | TokBClose CodeMark -- )

> | TokEq CodeMark -- =

> | TokAmb CodeMark -- amb

> | TokPor CodeMark -- por

16

Beispielsweise soll der Quelltext (letrec double = \x -> x+x in double) (-20) ge-rade den Tokenstrom

[TokBOpen (1,1),TokLet (1,2),TokVar (1,9) "double",TokEq (1,16),

TokLam (1,18),TokVar (1,19) "x",TokArrow (1,21),

TokVar (1,24) "x",TokPlus (1,25),TokVar (1,26) "x",TokIn (1,28),

TokVar (1,31) "double",TokBClose (1,37),TokBOpen (1,39),

TokInt (1,40) (-20),TokBClose (1,43)]

erzeugen, während 10*10 einen Fehler ergibt, da * kein definiertes Symbol ist:

*** Exception: Error during lexing:

Line: 1

Column: 3

*10

Aufgabe 1. Implementieren Sie die folgenden Funktionen im Modul LFPC.Parse.Lex

• getCodeMark :: LFPCTok -> CodeMark, die die Positionsmarkierung eines Tokenszurück gibt.

• printLFPCTok :: LFPCTok -> String, die ein Token in den ursprünglichen Quell-text des Tokens konvertiert.

• lexLFPC :: String -> [LFPCTok], die aus einem LFP+C-Quelltext eine Liste vonToken erstellt und dabei Kommentare entfernt und für jedes Token dessen Positionim Quelltext (Zeile, Spalte) mit abspeichert.

Sollte ein Fehler bei der lexikalischen Analyse auftreten, so generieren Sie mit dererror-Funktion eine Fehlermeldung, die zumindest die Zeile und Spalte des nichtlexbaren Symbols und das Symbol selbst ausgibt.

3.2 Syntaktische Analyse

Der Parser wird mittels happy1 (siehe dazu auch Abschnitt 5.2) generiert, d.h. wir gebennur eine Parserspezifikation an, und lassen uns den Parser dann generieren. Die Spezifikati-onsdatei ist schon teilweise vorgegeben, um nicht all zuviel Zeit in das Erstellen eben dieserzu investieren. Allerdings muss der Parser noch um einige Funktionalitäten vervollständigtwerden, was deutlich wird, wenn wir einen Blick auf den Datentypen CoreLFPC für unsereKernsprache werfen:

1http://haskell.org/happy

17

http://haskell.org/happy

> module LFPC.CoreL.CoreExpression where

> data CoreLFPC =

> V CoreVar

> | App CoreLFPC CoreLFPC

> | Lambda CoreVar CoreLFPC

> | Let [Bind] CoreLFPC

> | Cons Int Int [CoreLFPC]

> | Case CoreLFPC [Alt]

> | Amb CoreLFPC CoreLFPC

> | Por CoreLFPC CoreLFPC

> deriving (Eq,Show)

> data Alt = Alt Int Int [CoreVar] CoreLFPC

> deriving (Eq,Show)

> data Bind = CoreVar :=: CoreLFPC

> deriving (Eq,Show)

> type CoreVar = (CodeMark,Bool,Var,Var)

Die entsprechende Syntax kann durch die in Abbildung 3.2 abgebildete Grammatik dar-gestellt werden.

Expr ::= Var | (Expr 1 Expr 2) | \Var -> Expr | ci,k Expr 1 . . . Expr k| letrec Var 1 = Expr 1, . . .Var n = Expr n in Expr| case Expr of { Pat 1 -> Expr 1, . . . ,Pat n -> Expr n }| amb Expr 1 Expr 2 | por Expr 1 Expr 2

Pat ::= ci,k Var 1 . . . Var k

Abbildung 3.2: Syntax von CoreLFPC

Während der Datentyp über Konstrukte für

• Abstraktionen (Lambda CoreVar CoreLFPC)

• Applikationen (App CoreLFPC CoreLFPC)

• letrec-Ausdrücke (Let [Bind] CoreLFPC),

• case-Ausdrücke (Case CoreLFPC [Alt]),

• amb-Ausdrücke (Amb CoreLFPC CoreLFPC),

• por-Ausdrücke (Por CoreLFPC CoreLFPC) und

18

• Variablen (V CoreVar)

verfügt, fehlen Konstrukte auf die sich der null?- und der +-Operator oder Ganzzahlendirekt abbilden lassen. Konstruktoren wie True, False, [] und : sowie Paare werdendurch eine einheitliche Darstellung mithilfe des Cons Int Int [CoreLFPC]-Konstruktes(in der Grammatik als ci,k Expr 1 . . . Expr k repräsentiert) realisiert. Hierbei ist das ersteArgument (i) die Nummer des Konstruktors, das zweite Argument (k) seine Stelligkeitund schließlich das dritte Argument die Liste der Argumente des Konstruktors (die geradeüber k Elemente verfügt). Neben diesen in LFP+C enthalten Konstruktoren fügen wir diezwei Konstruktoren Zero und One und spezielle Paare |a,b| hinzu, die für die Darstellungder Ganzzahlen benötigt werden (s.u.).

Nun müssen wir noch die verschiedenen Konstruktoren durchnummerieren und Stelligkei-ten vergeben, um eine einheitliche Darstellung zu erhalten. Diese Zuordnung ist Tabelle 3.1zu entnehmen.

[] Cons 1 0 []

a:b Cons 2 2 [a,b]True Cons 3 0 []

False Cons 4 0 []

Zero Cons 5 0 []

One Cons 6 0 []

(a,b) Cons 7 2 [a,b]|a,b| Cons 8 2 [a,b]

Tabelle 3.1: Konstruktoren

3.2.1 Übersetzung

Wir definieren eine Übersetzung J·K, die Ausdrücke der Sprache LFP+C in den DatentypenCoreLFPC übersetzt.

Zunächst betrachten wir die Übersetzung von Variablen:

JxK = V (pos(x),True,x,x)

Hier wird der Typ CoreMark verwendet, der aus vier Komponenten besteht

1. pos(x) ist die Position der Variablen x im Quelltext (vom Typ CodeMark).

2. Ein Boolescher Wert: True falls die Variable im Quelltext an dieser Position vor-kommt, False falls die Variable vom Compiler eingefügt wurde (s.u).

3. Der Name der Variablen im Quelltext

4. Der aktuelle Name der Variable, dieser kann vom vorherigen Namen abweichen, dader Compiler Umbenennungen durchführt.

19

Dieser Aufwand für Variablen wird betrieben, damit auch nach der syntaktischen Analyse,z.B. während der semantischen Analyse für den Benutzer verständliche Fehlermeldungengeneriert werden können.

Betrachten wir nun die Übersetzung von Konstruktoren:

J[]K = Cons 1 0 []JTrueK = Cons 3 0 []

JFalseK = Cons 4 0 []Je1 : e2K = Cons 2 2 [Je1K,Je2K]

J(e1,e2)K = Cons 7 2 [Je1K,Je2K]JZeroK = Cons 5 0 []JOneK = Cons 6 0 []

J|e1,e2|K = Cons 8 2 [Je1K,Je2K]

Die Konstruktoren True, False, [], :, und Paare werden direkt in Konstruktoren gemäßTabelle 3.1 übersetzt. Die Konstruktoren One, Zero und das spezielle Paar |a,b| gibt es imQuelltext gar nicht, aber wir übersetzen sie hier auch, da wir sie später für die Kodierungvon Ganzzahlen verwenden. Für die zweistelligen Konstrukte müssen selbstverständlichdie Argumente auch übersetzt werden.

Die Übersetzung von Zahlen ist anders (sonst bräuchten wir unendlich viele Konstrukto-ren). Wir benutzen zur internen Darstellung die Binärdarstellung nicht-negativer Zahlenund speichern zusätzlich, ob die Zahl positiv oder negativ ist, genauer:

JiK = J|s, bn(i): . . . :b1(i):[]|K

wobei

• s ={

True, wenn i ≥ 0False, sonst

• bj ={

Zero, wenn die j-te Stelle von i in Binärdarstellung 0 ist,One, sonst

• n die Anzahl der Stellen von i in Binärdarstellung ist.

Das spezielle Paar und die Liste müssen natürlich noch entsprechend der Übersetzung J·Kkodiert werden.

Man beachte, dass die Binärdarstellung mit dem niedrigsten Bit beginnt. Diese Darstel-lung ermöglicht eine effiziente Implementierung der Addition. Die Verwendung speziellerPaare im Gegensatz zu normalen Paaren hat den Zweck, stets zu wissen, dass es sich umeine Zahl handelt und nicht um ein beliebiges Paar. Das ist insbesondere notwendig, wennwir das Ergebnis einer Berechnung wieder als Dezimalzahl drucken wollen. Wir geben zurVerdeutlichung noch zwei Beispiele an:

20

J1K = J|True, One:[]|K = Cons 8 2 [JTrueK,JOne:[]K]= Cons 8 2 [Cons 3 0 [], Cons 2 2 [JOneK,J[]K]]= Cons 8 2 [Cons 3 0 [], Cons 2 2 [Cons 6 0 [], Cons 1 0 []]]

J−2K = J|False, Zero:One:[]|K = Cons 8 2 [JFalseK,JZero:One:[]K]= Cons 8 2

[Cons 4 0 [],

Cons 2 2 [Cons 5 0 [],Cons 2 2 [Cons 6 0 [],Cons 1 0 []]]]

Wir betrachten nun die Übersetzung der Abstraktionen, Applikationen und der beidennichtdeterministischen Konstrukte.

J\x -> eK = Lambda (pos(x),True,x,x) JeKJe1 e2K = App Je1K Je2K

Jamb e1 e2K = Amb Je1K Je2KJpor e1 e2K = Por Je1K Je2K

Die Übersetzung ist relativ einfach, da die Konstrukte im Datentyp CoreLFPC genauvorhanden sind. Bei der Übersetzung der Abstraktion ist zu beachten, dass die Variablewieder als 4-Tupel übersetzt wird.

Die Übersetzung von letrec-Ausdrücken erfolgt ebenfalls direkt:

Jletrec bind1, . . . , bindn in eK = Let [Jbind1K,, . . . ,JbindnK] JeKJx = eK = (pos(x),True,x,x) :=: JeK

Bei der Übersetzung von case-Ausdrücken und den zugehörigen Alternativen müssenfehlende Alternativen ergänzt werden:

Jcase e of {alt1, . . . altn}K = Case JeK [Jalt1K, . . . ,JaltnK,altn+1, . . . ,altm]J[] -> eK = Alt 1 0 [] JeK

JTrue -> eK = Alt 3 0 [] JeKJFalse -> eK = Alt 4 0 [] JeKJZero -> eK = Alt 5 0 [] JeKJOne -> eK = Alt 6 0 [] JeK

J(x:y) -> eK = Alt 2 2 [(pos(x),True,x,x),(pos(y),True,y,y)] JeKJ(x,y) -> eK = Alt 7 2 [(pos(x),True,x,x),(pos(y),True,y,y)] JeKJ|x,y| -> eK = Alt 8 2 [(pos(x),True,x,x),(pos(y),True,y,y)] JeK

Hierbei sind altn+1, . . . altm Alternativen für Pattern, die nicht in den ersten n Alternati-ven vorkommen, wobei die rechten Seiten der zusätzlichen Alternativen aus der VariablenV ((0,0),False,"_bot","_bot") bestehen, diese wird intern auf einen nichtterminie-renden Ausdruck abgebildet (durch die Funktion mkOuterLet, s.u.). Zusätzlich müssendie Alternativen noch anhand der Konstruktornummer sortiert werden.

Falls case-Ausdrücke doppelte Alternativen enthalten, d.h. Alternativen mit dem selbenPattern, so sollte ein Fehler beim Parsen auftreten. Dies wird in der Parser-Definitionimplementiert.

21

Es fehlt nun noch die Übersetzung der Operatoren + und null? auf Ganzzahlen. Diesewerden zunächst nur in Anwendungen auf Variablen übersetzt, wobei diese Variablenintern sind, und deswegen spezielle Namen erhalten, die mit einem Unterstrich beginnen.Das hat den Vorteil, dass sie nicht im Programm-Quelltext auftreten können, da sie bereitsbei der lexikalischen Analyse einen Fehler produzieren würden.

Jnull?eK = App ((0,0),False,"_isNull","_isNull") JeKJe1+e2K = App (App ((0,0),False,"_plus","_plus") Je1K) Je2K

Die syntaktische Analyse besteht nun aus dem Parsen des Stromes von Token in dieDatenstruktur CoreLFPC entsprechend der Übersetzung J·K und einem zusätzlichen ab-schließenden Schritt: Wir müssen Funktionen für die Addition, den null?-Operator undeine Bindung für die interne Variable "_bot" hinzufügen.

Das ist relativ leicht: Wir fügen um den geparsten Ausdruck, ein letrec-herum, dassBindungen für "_plus", "_isNull" und "_bot" enthält. Dies erledigt die FunktionmkOuterLet im Modul LFPC.Parse.InternalOp. Diese Funktion wurde mit einem er-weiterten Parser, der auch interne Variablen, die Konstruktoren One und Zero und |a,b|-Paare erkennt, aus dem Quelltext in der Datei InternalOp.lfp generiert.

Aufgabe 2. Implementieren Sie in der Parserdefinition Parser.ly (aus der dann dasModul LFPC.Parse.Parser generiert wird), die in den Aktionen verwendeten Funktionen

• mkInt :: Integer -> CoreLFPC die entsprechend der Übersetzung J·K eine Ganz-zahl in die Darstellung innerhalb des Datentyps CoreLFPC konvertiert.

• checkBinds :: CoreLFPC -> [Bind] -> LFPCTok -> CoreLFPC, die den in-Ausdruck, die Bindungen, das Token des letrec-Ausdrucks erhält, und prüft, oballe Bindungsvariablen verschieden sind. Ist dies der Fall, so wird eine Fehlermel-dung mithilfe der im übergebenen Token steckenden Informationen generiert. An-dernfalls wird der letrec-Ausdruck in der Darstellung des Datentyps CoreLFPCzurück gegeben.

• checkAlts :: CoreLFPC -> LFPCTok -> [Alt] -> CoreLFPC, die das erste Ar-gument eines case-Ausdrucks, das Token für den case-Ausdruck und eine Listevon case-Alternativen erhält und einen case-Ausdruck im Datentyp CoreLFPC er-stellt, wobei

– geprüft werden muss, ob doppelte case-Alternativen enthalten sind. Ist dies derFall, so wird anhand des Tokens eine Fehlermeldung generiert. Sind gar keineAlternativen vorhanden, so sollte auch eine Fehlermeldung generiert werden.

– fehlende Alternativen entsprechend der Übersetzung J·K hinzufügt werden,– die Liste der Alternativen anhand der Konstruktornummern sortiert wird.

• chkAltPair und chkAltCons, die jeweils die SignaturLFPCTok -> LFPCTok -> LFPCTok -> CoreLFPC -> Alt haben, wobei das er-ste Token das Token für , oder : eines case-Patterns ist, das zweite Argument

22

die erste Patternvariable, das dritte Argument die zweite Patternvariable und dasvierte Argument die rechte Seite der Alternativen ist. Beide Funktionen prüfen obdie Patternvariablen verschieden sind (andernfalls wird ein Fehler generiert), undliefern anschließend eine Alternative.

Aufgabe 3. Vervollständigen Sie die Parserdefinition in der Datei Parser.ly und gene-rieren Sie mittels happy den Parser.

Wir geben noch einige Aufrufe des Parser an, die fehlschlagen sollten:

*> parseLFPC "letrec x=True, x=False in x"

*** Exception: multiple bindings in letrec expression for variable ’x’

Zeile: 1 Spalte: 1

*> parseLFPC "case True of {True -> False, True -> False}"

*** Exception: multiple case-alternatives for constructor "True"

Zeile: 1 Spalte: 1

*> parseLFPC "case [] of {(a:a) -> True}"

*** Exception: repeated variable ’a’ in pattern ":"

Zeile: 1 Spalte: 15

3.3 Semantische Analyse

Wir werden im Rahmen der semantischen Analyse werden wir zwei Aufgaben erledigen:

• Wir prüfen, ob das Programm ein geschlossener Ausdruck ist, d.h. keine ungebun-denen (freien) Variablen vorkommen.

• Wir benennen alle gebundenen Variablen mit neuen Namen um, so dass diese paar-weise verschieden sind.

Die Bindungsregeln von LFP+C sind wie folgt:

• In \x-> e ist x durch \x in e gebunden.

• In case e of { . . . , (x,y) -> e′, . . . } sind x, und y durch das Pattern (x,y) in e′gebunden.

• In case e of { . . . , (x:y) -> e′, . . . } sind x, und y durch das Pattern (x,y) in e′gebunden.

• In letrec x1 = e1, . . . , xn = en in en+1 sind die Variablen x1, . . . , xn durch dieletrec-Bindungen in e1, . . . , en+1 gebunden.

Variablen die nicht gebunden sind, sind frei.

23

Aufgabe 4. Implementieren Sie im Modul LFPC.SemAna.RenameBV die FunktionrenameLFPC :: CoreLFPC -> [Var] -> (CoreLFPC,[Var]), die einen Ausdruck undeine Liste von neuen Variablennamen erwartet, und die gebundenen Variablen durchVerwendung der neuen Variablennamen umbenennt und schließlich ein Paar bestehendaus dem umbenannten Ausdruck und den nicht verwendeten Variablennamen zurück gibt.Gleichzeitig soll dabei geprüft werden, ob freie Variablen im Ausdruck vorkommen und indiesem Fall eine aussagekräftige Fehlermeldung generiert werden.

Versuchen Sie obige Funktion möglichst effizient zu implementieren, z.B. sollte der Aus-druck nur einmal durchlaufen werden. Außerdem könnte die Datenstruktur Map aus demModul Data.Map der Standardbibliotheken hilfreich sein.

Wir geben noch einige Beispiele an, die zu Fehlern führen:

*> (renameLFPC.parseLFPC) "(a b)" ["_internal" ++ show i | i (renameLFPC.parseLFPC) "letrec x=y in True" ["_internal" ++ show i | i (renameLFPC.parseLFPC) "case True of {(a:b) -> c }" ["_internal" ++ show i | i data CoreLFPCR =

> App CoreLFPCR Var

> | V Var

> | Lambda Var CoreLFPCR

> | Let [Bind] CoreLFPCR

> | Cons Int Int [Var]

> | Case CoreLFPCR [Alt]

> | Amb CoreLFPCR CoreLFPCR

24

> | Por CoreLFPCR CoreLFPCR

> data Alt = Alt Int Int [Var] CoreLFPCR

> data Bind = Var :=: CoreLFPCR

In Abbildung 3.3 ist die entsprechende Grammatik dargestellt.

Expr ::= Var | (Expr Var ) | \Var -> Expr | ci,k Var 1 . . . Var k| letrec Var 1 = Expr 1, . . .Var n = Expr n in Expr| case Expr of { Pat 1 -> Expr 1, . . . ,Pat n -> Expr n }| amb Expr 1 Expr 2 | por Expr 1 Expr 2

Pat ::= ci,k Var 1 . . . Var k

Abbildung 3.3: Syntax von CoreLFPCR

Man beachte, dass wir die Datentypen Alt und Bind neu definieren und die bekannten Da-tenkonstruktoren V, App, . . . benutzen, d.h. die beiden Module LFPC.CoreL.MachineExpund LFPC.CoreL.CoreExpression dürfen niemals beide ohne Qualifizierung von einemModul importiert werden (siehe Abschnitt 5.1).

Wir müssen nun den Datentyp CoreLFPC in CoreLFPCR konvertieren. Dabei müssen diefolgenden Transformationen durchgeführt werden:

Für jede Applikation:

(s t) → letrec y = t in (s y),wobei y eine neue Variable ist.

Für jede Konstruktorapplikation (nicht in Pattern, nicht für 0-stellige Konstruktoren):

(c t1 . . . tn) → letrec y1 = t1, . . . , yn = tn in (c y1 . . . yn),wobei alle yi neue Variablen sind.

Beispiel 5. Wir transformieren den Ausdruck ((λx -> x) (λy -> y)) (True:[]), wobeii1, . . . i4 neue Variablen sind:

((λx -> x) (λy -> y)) (True:[])→ letrec i1 = (True:[]) in ((λx -> x) (λy -> y))→ letrec i1 = (letrec i2 = True, i3 = [] in (i1:i2))

in ((λx -> x) (λy -> y))→ letrec i1 = (letrec i2 = True, i3 = [] in (i1:i2))

in (letrec i4 = λy -> y in (λx -> x) i4)

Gleichzeitig werden wir bei dieser Transformation aus den als 4-Tupel dargestellten Va-riablen (vom Typ CoreVar) nun Variablen vom Typ Var machen, d.h. wir behalten nurdie aktuellen Namen und werfen die restliche Information weg.

25

Aufgabe 5. Implementieren Sie im Modul LFPC.CoreL.TransCode eine FunktiontransLFPCtoLFCPR :: CoreLFPC -> [Var] -> (CoreLFPCR,[Var]), die einen Aus-druck vom Typ CoreLFPC und eine Liste (neuer) Variablennamen erhält und ein Paarliefert, bestehend aus dem CoreLFPCR-Ausdruck und der Restliste von Variablennamen(jene, die nicht benutzt wurden).

Ausdrücke vom Typ CoreLFPCR, die weder amb noch por enthalten, sind auf den abstrak-ten Maschinen Mark 1 und Mark 2 ausführbar (siehe Kapitel 4). Deswegen sollten diesenun zunächst implementiert werden. Dieses Kapitel enthält jedoch noch weitere Abschnit-te zur Erzeugung von Ausdrücken, die auf der Mark 3 bzw. Concurrent Mark 3, ausgeführtwerden können. Diese Abschnitte müssen im Anschluss bearbeitet werden.

26

Kapitel 4

Verzögert auswertende AbstrakteMaschinen

4.1 Die Abstrakte Maschine Mark 1 zur Ausführung

deterministischer CoreLFPCR-Programme

Eine einfache abstrakte Maschine zur call-by-need Auswertung von letrec-Sprachen istdie Mark 1 aus [14]. Die in [14] beschriebenen Maschinen passen zu unserer Sprache bis aufdie nichtdeterministischen Operatoren, da die Maschinen deterministisch sind. Deshalbwerden wir später die Mark 2 um nebenläufige Auswertung erweitern. Wir betrachtenalso zunächst nur Ausdrücke vom Typ CoreLFPCR, die weder amb- noch por-Ausdrückeenthalten.

Wir benötigen noch die Definition der Werte, welche jene Ausdrücke sind, zu denen wirunsere Programme auswerten möchten:

Definition 1. Ein Ausdruck ist ein Wert wenn eine Abstraktion, oder eine Konstrukto-rapplikation ist. Ein Ausdruck der Sprache CoreLFPCR ist in WHNF (weak head normalform, schwache Kopfnormalform), wenn er eine der folgenden Formen besitzt:

• \x -> s, oder

• ci,k y1 . . . yk

• letrec x1 = s1, . . . , xn = sn in v, wobei v ein Wert ist.

Der Zustand der Maschine ist ein Tripel (Γ, e, S) wobei:

• Γ ein Heap ist, der Heapbindungen enthält. Eine Heapbindung p 7→ e′ besteht auseiner Heapvariablen p und einem Ausdruck e′. Für jede Heapvariable darf nur eineBindung im Heap vorkommen, d.h. der Heap ist eine Abbildung von Heapvariablenauf Ausdrücke;

• e der aktuell auszuwertende Ausdruck ist. Wir nennen diese Komponente auch Con-trol, da sie die Auswertung (d.h. den Ablauf der Maschine) steuert.

27

• S ein Stack ist, der sich”merkt“, wie man weitermachen muss, falls der aktuell

auszuwertende Ausdruck ein Wert ist.

Abbildung 4.1 zeigt die Übergangsrelation der Mark 1-Maschine, d.h. wie man aus einemZustand den darauf folgenden Zustand berechnet. Hierbei ist ·∪ die disjunkte Vereinigung.

28

(Γ,(

ep)

,S)

push

−−→

(Γ,e

,p:S

)

(Γ,λ

y->

e,p

:S

)ta

ke

−−→

(Γ,e

[p/y

],S

)

(Γ′ · ∪{p

7→e}

,p,S

)en

ter

−−−→

(Γ′ ,

e,#

p:S

)

(Γ,λ

y->

e,#

p:S

)update

−−−→

(Γ· ∪{

p7→

λy->

e},λ

y->

e,S

)

(Γ,letrec

x1

=e 1

,...

,xn

=e n

in

e,S

)m

kB

inds

−−−−−→

(Γ· ∪

n ⋃ i=1{pi7→

ê i},

ê,S

)

wob

eip 1

,...

,pn

neu

ePoi

nte

rsi

nd,d.h

.w

eder

inS

noch

inΓ

vork

omm

en,

ê i=

e i[p

1/x

1,.

..p n

/xn]und

ê=

e[p 1

/x1,.

..p n

/xn]

(Γ,case

eof

alt

s,S

)push

Alt

s−−−−−→

(Γ,e

,alt

s:S

)

(Γ,c

k,a

p 1..

.pa,#

p:S

)update

2−−−−→

(Γ· ∪{

p7→

c k,a

p 1..

.pa},

c k,a

p 1..

.pa,S

)

(Γ,c

k,a

p 1..

.pa,a

lts

:S

)br

anch

−−−−→

(Γ,e

[p1/y

1,.

..,p

a/y

a],

S)

wob

eic k

,ay 1

...

y a->

edie

k-t

eA

lter

nat

ive

inalt

sis

t

(Γ,p

,S)

black

hole

−−−−−→

(Γ,p

,S)

falls

für

pke

ine

Bin

dung

inΓ

(Γ,c

k,a

p 1..

.pa,p

:S

)bl

ack

hole

2−−−−−−→

(Γ,c

k,a

p 1..

.pa,p

:S

)

(Γ,λ

y->

e,alt

s:S

)bl

ack

hole

3−−−−−−→

(Γ,λ

y->

e,alt

s:S

)

Abbildung

4.1:

Zust

andsü

ber

gangs

rege

lnder

Mar

k1

29

Es fehlen jetzt noch Angaben, mit welchem Zustand man beginnt, und wann man aufhört:

Sei e ein CoreLFPCR Ausdruck, dann startet man mit dem Zustand (∅, e, []), d.h. mitleerem Heap und leerem Stack.

Die Maschine stoppt, wenn keine Regel anwendbar ist, d.h. e ist eine Abstraktion odereine Konstruktoranwendung und der Stack ist leer.

Wir betrachten zunächst eine Beispielausführung der Maschine:

Beispiel 6. Wir demonstrieren die Auswertung des Ausdrucksletrec x = (λy -> y) z, z = c3,0 in x:

Heap Control Stack∅ letrec x = (λy -> y) z, []

z = c3,0in x

mkBinds−−−−−→ {p1 7→ ((λy -> y) z)[p1/x, p2/z], x[p1/x, p2/z] []p2 7→ c3,0[p1/x, p2/z]}

= {p1 7→ (λy -> y) p2p2 7→ c3,0} p1 []enter−−−→ {p2 7→ c3,0} (λy -> y) p2 [#p1]push−−→ {p2 7→ c3,0} (λy -> y) [p2,#p1]take−−→ {p2 7→ c3,0} y[p2/y] [#p1]

= {p2 7→ c3,0} p2 [#p1]enter−−−→ ∅ c3,0 [#p2,#p1]

update2−−−−→ {p2 7→ c3,0} c3,0 [#p1]update2−−−−→ {p2 7→ c3,0, p1 7→ c3,0} c3,0 []

4.1.1 Implementierung

Zur Implementierung der Maschine sollte man nun genauer untersuchen, welche Daten-strukturen und welche Operationen benötigt werden.

Wir benötigen drei Datenstrukturen:

Control: Hier ist die Datenstruktur bereits durch CoreLFCPR implementiert, aller-

dings brauchen wir eine zusätzliche Operation: In den Regelntake−−→, mkBinds−−−−−→

undbranch−−−−→ werden Variablen durch Heapvariablen ersetzt. Wir benutzen für

Heapvariablen in der Mark 1 ebenfalls Strings. D.h. es fehlt eine Funktionsubstitute :: CoreLFPCR -> Var -> Var -> CoreLFPCR, die einen Ausdruckund zwei Variablen erhält und im Ausdruck die erste durch die zweite Variableersetzt.

30

Heap: Heapeinträge sind Paare vom Typ (Var,CoreLFPCR). Da der Heap eine Abbil-dung von Variablen auf Ausdrücke ist, bietet es sich an den Datentyp Map aus derStandardbibliothek Data.Map zu verwenden, d.h. wir definieren den Typ Heap als

type Heap = Map Var CoreLFPCR

Wir benötigen die folgenden Operationen auf dem Heap:

• Für die Regeln enter−−−→ und blackhole−−−−−→:lookupHeap : Var -> Heap -> Maybe (CoreLFPCR,Heap), die eine Heapva-riable und einen Heap erhält, und

– falls eine Bindung für die Heapvariable existiert, die Bindung aus dem Heapentfernt und das Paar bestehend dem Ausdruck und dem modifiziertenHeap liefert,

– Nothing liefert falls keine Bindung existiert.

• Für die Regeln update−−−→, update2−−−−→ und mkBinds−−−−−→:insertHeap : Var -> CoreLFPCR -> Heap -> Heap, die eine Variable, einenAusdruck und einen Heap erhält und eine neue Bindung auf dem Heap anlegt,und schließlich den geänderten Heap zuückgibt.

• emptyHeap :: Heap zum Erstellen eines leeren Heaps.

Stack: Stackelemente können Heapvariablen, case-Alternativen, oder markierte Heap-variablen (#p) sein. d.h.

data StackElem = Unmarked Var | MarkedVar Var | Alts [Alt]

der Stack selbst kann dann durch eine Liste von StackElem-Elementen dargestelltwerden, d.h.

type Stack = [StackElem]

Operationen auf dem Stack sind:

• Für die Regeln push−−→, enter−−−→ und pushAlts−−−−−→,push :: StackElem -> Stack -> Stack, welche ein Stack-Element aufden Stack legt.

• Für die Regeln take−−→, update−−−→, update2−−−−→ pop :: Stack -> (StackElem,Stack),welche das oberste Element des Stacks nimmt.

• isEmptyStack :: Stack -> Bool, die prüft, ob der Stack leer ist.• emptyStack :: Stack, die einen neuen leeren Stack anlegt.

Zusätzlich werden Operationen auf dem StackElem-Typ benötigt.

31

Wir könnten nun direkt loslegen und die Datenstrukturen wie eben analysiert implemen-tieren. Allerdings benötigen die Maschinen Mark 2 und Mark 3 auch andere Elemente imStack und im Heap. Deswegen werden diese Datenstrukturen in der folgenden Aufgabepolymorph über den Elementtypen definiert und implementiert.

Aufgabe 6. Implementieren Sie im Modul LFPC.AbsM.Heap einen Datentypen für denHeap, der polymorph über den Heapvariablen und den rechten Seiten der Bindungen ist,d.h.

type Heap p e = ...

Implementieren Sie im gleichen Modul die folgenden Operationen auf dem Datentypen

• emptyHeap :: Heap p e zum Erstellen eines leeren Heaps.

• lookupHeap :: p -> Heap p e -> Maybe (e, Heap p e), die wie oben beschrie-ben im Heap nach dem Eintrag für p sucht und die rechte Seite der Bindung,sowie den modifizierten Heap liefert. Eventuell müssen Sie an den Typ p weitereTypklassen-Anforderungen stellen.

• insertHeap :: p -> e -> Heap p e -> Heap p e, die wie oben beschriebeneine Heapvariable vom Typ p und eine rechte Seite vom Typ e sowie einen Heaperhält und die entsprechende neue Bindung im Heap anlegt und schließlich den modi-fizierten Heap zurück liefert. Auch hier ist es möglich, dass an p weitere Typklassen-Anforderung gestellt werden müssen.

Versuchen Sie eine möglichste effiziente Datenstruktur zu wählen.

Aufgabe 7. Implementieren Sie im Modul LFPC.AbsM.Stack einen Datentypen für denStack, der polymorph über den Einträgen im Stack ist

type Stack a = ...

Implementieren Sie im gleichen Modul die folgenden Operationen auf dem Stack:

• emptyStack :: Stack a zum Erzeugen eines leeren Stacks.

• isEmptyStack :: Stack a -> Bool, die prüft ob der Stack leer ist.

• push :: a -> Stack a -> Stack a, die ein Element und einen Stack erhält unddas Element oben auf den Stack legt.

• pop :: Stack a -> (a, Stack a), die das oberste Element vom Stack nimmt unddas Paar bestehend aus diesem Element und dem Reststack zurück gibt.

Aufgabe 8. Im Modul LFPC.AbsM.Stack.StackElem ist der gleichnamige Datentyp de-finiert als

32

> data StackElem v a = Marked v | Unmarked v | Other a

> deriving (Eq,Show)

D.h. Stack-Elemente sind polymorph über den Variablen v und den Alternativen a. Siekönnen entweder markierte oder unmarkierte Variablen sein, oder etwas anderes (Other).Später werden wir auch tatsächlich etwas anderes als reine case-Alternativen auf demStack ablegen. Implementieren Sie die folgenden Funktion diesem Modul:

• isMarkedVar :: StackElem v a -> Bool, die testet, ob das Stack-Element einemarkierte Variable ist.

• isUnmarkedVar :: StackElem v a -> Bool, die testet, ob das Stack-Element eineunmarkierte Variable ist.

• isOther :: StackElem v a -> Bool, die testet, ob das Stack-Element gerade einOther-Element ist.

• fromVar :: StackElem v a -> v, die eine markierte oder unmarkierte Variablevom Typ StackElem nimmt und die Variable zurück gibt. Falls es sich um ein Other-Element handelt sollte ein Fehler generiert werden.

• fromOther :: StackElem v a -> a, die ein Other-Element erwartet und diesesunverpackt zurück gibt. Falls eine markierte oder unmarkierte Variable übergebenwird, sollte ein Fehler auftreten,

• mark :: v -> StackElem v a, die aus einer Variablen eine markierte Variablevom Typ StackElem macht.

• unmark :: v -> StackElem v a, die aus einer Variablen eine unmarkierte Varia-ble vom Typ StackElem macht.

• other :: a -> StackElem v a, die aus irgendwas ein Other-Element TypStackElem macht.

Aufgabe 9. Implementieren Sie im Modul LFPC.CoreL.MachineExp eine Funktion

substitute :: CoreLFPCR -> Var -> Var -> CoreLFPCR

die einen Ausdruck und zwei Variablen erhält und alle Vorkommen der ersten Variablendurch die zweite ersetzt.

Nachdem nun alle notwendigen Datenstrukturen und Operationen vorhanden sind, könnenwir die Mark 1-Maschine implementieren.

Im Modul LFPC.AbsM.Mark1 wird der Datentyp für den Zustand der Mark 1 definiert:

> newtype Mark1State =

> Mark1State (Heap Var CoreLFPCR,

> CoreLFPCR,

> Stack (StackElem Var [Alt]))

33

Der Zustand besthet somit aus dem 3-Tupel mit den Komponenten:

• dem Heap vom Typ (Heap Var CoreLFPCR), d.h. einer Abbildung von Variablenauf CoreLFPCR-Ausdruecke;

• Control, als Ausdruck vom Typ CoreLFPCR;

• dem Stack vom Typ (Stack (StackElem Var [Alt])), d.h. der Stack kann dreiverschiedene Elementtypen aufnhemen: umarkierte Variablen, markierte Variablenoder eine Liste von case-Alternativen.

Aufgabe 10. Implementieren Sie im Modul LFPC.AbsM.Mark1 die folgenden Funktionen:

• startState :: CoreLFPCR -> Mark1State, die einen CoreLFPCR-Ausdruck erhältund den Startzustand der Maschine für diesen Ausdruck berechnet.

• nextState :: Mark1State -> [Var] -> (Mark1State, [Var]), die einen Zu-stand der Mark 1 sowie eine Liste (neuer) Variablen erhält, und entsprechend derÜbergangsrelation den Folgezustand berechnet und zusätzlich die nicht benutztenneuen Variablen zurück gibt.

• finalState :: Mark1State -> [Var] -> (Mark1State, [Var]), die einen Zu-stand der Mark 1 sowie eine Liste (neuer) Variablen erhält, und entsprechend denEndzustand der Maschine berechnet und zusätzlich die nicht benutzten neuen Va-riablen zurück gibt.

• exec :: CoreLFPCR -> [Var] -> String, die einen Ausdruck vom TypCoreLFPCR und eine Liste neuer Variablennamen erhält, anschließend dieMark 1-Maschine für diesen Ausdruck ausführt und schließlich das Ergebniszurück in einen String konvertiert. Hierbei sollen Zahlen, Listen und Paa-re wieder in ihrer gebräuchlichen Darstellung ausgegeben werden. Z.B. sollbeim Ergebnis "15" genau dieser String zurückgegeben werden (im Gegensatz zuCons 8 2 [Cons 3 0, Cons 2 2 [Cons 6 0, Cons 2 2 [Cons 6 0, Cons 1 1]]]).

Hinweis: Da die Mark 1 Maschine nur bis zur WHNF auswertet, müssen Sie dieMachine zum Drucken des Ergebnisses erneut mit den Argumenten eines Konstruk-tors aufrufen.

Aufgabe 11. Implementieren Sie im Modul LFPC.Run eine Funktion runMark1, die eindeterministisches LFP+C-Programm erwartet, dann das Programm lext, parst, der seman-tischen Analyse unterzieht, in CoreLFPCR umwandelt, schließlich auf der Mark 1-Maschinelaufen lässt und das Ergebnis als String zurück liefert.

Für die neuen Variablen, die Sie brauchen werden, verwenden Sie interne Variablen, z.B.die Liste ["_internal" ++ show x | x

4.2 Verbesserungen von Mark 1 – Mark 2

Ein Schwachpunkt der Mark 1-Maschine ist das Ersetzen von Variablen für Variablen in

den Regelntake−−→, mkBinds−−−−−→ und branch−−−−→. Dieses Substituieren ist zum einen sehr aufwendig,

zum anderen verhindert es das effiziente Abarbeiten von sequentiellem Code, da bei derSubstitution komplette Ausdrücke (was später Codesequenzen sind) durchlaufen werdenmüssten.

Deswegen wird in der Mark 2 Maschine eine zusätzliche Komponente zum Zustand derMaschine hinzugefügt, eine Umgebung (Environment), welche eine Abbildung von Pro-grammvariablen auf Heapvariablen darstellt. Mithilfe dieser Umgebung werden die Sub-stitution quasi

”verzögert“ ausgeführt, d.h. erst dann, wenn sie gebraucht werden.

Formaler ist der Zustand der Mark 2-Maschine ist ein 4-Tupel (Γ, e, E, S) wobei:

• Γ ein Heap ist, der Heapbindungen enthält. Eine Heapbindung p 7→ (e′, E ′) bestehtaus einer Heapvariablen p und einem Paar (Ausdruck e′, Umgebung E ′). Für jedeHeapvariable darf nur eine Bindung im Heap vorkommen, d.h. der Heap ist eineAbbildung.

• e der aktuell auszuwertende Ausdruck ist.

• Der aktuellen Umgebung passend zum aktuell auszuwertenden Ausdruck, die eineAbbildung von Programmvariablen auf Heapvariablen ist.

• S ein Stack ist.

Ein interessanter Nebeneffekt bei der Einführung der Umgebung ist, dass Programmva-riablen und Heapvariablen nicht mehr vom gleichen Typ sein müssen. Deswegen werdenwir Heapvariablen ab sofort durch Integer-Zahlen darstellen.

Abbildung 4.2 zeigt die Übergangsrelation für die Mark 2-Maschine. Die einzelnen Re-geln entsprechen den Regeln der Mark 1-Maschine, wobei es jedoch keine Variablen-Substitutionen mehr gibt, stattdessen wird die Umgebung modifiziert.

35

(Γ,(

ex),

E· ∪{

x7→

p},S

)push

−−→

(Γ,e

,E· ∪{

x7→

p},p

:S

)

(Γ,λ

y->

e,E

,p:S

)ta

ke

−−→

(Γ,e

,E· ∪{

y7→

p},S

)

(Γ′ · ∪{p

7→(e

′ ,E

′ )},

x,E

· ∪{x7→

p},S

)en

ter

−−−→

(Γ′ ,

e′,E

′ ,#

p:S

)

(Γ,λ

y->

e,E

,#p

:S

)update

−−−→

(Γ· ∪{

p7→

(λy->

e,E

)},λ

y->

e,E

,S)

(Γ,letrec

x1

=e 1

,...

,xn

=e n

in

e,E

,S)

mkB

inds

−−−−−→

(Γ· ∪

n ⋃ i=1{pi7→

(ei,

Ê)}

,e,Ê

,S)

wob

eiÊ

=E· ∪{

x17→

p 1,.

..x

n7→

p n}

und

p 1,.

..,p

nneu

ePoi

nte

rsi

nd,

d.h

.w

eder

inS

noch

inΓ

vork

omm

en

(Γ,case

eof

alt

s,E

,S)

push

Alt

s−−−−−→

(Γ,e

,E,(

alt

s,E

):S

)

(Γ,c

k,a

x1..

.xa,E

,#p

:S

)update

2−−−−→

(Γ· ∪{

p7→

(ck,a

x1..

.xa,E

)},c

k,a

x1..

.xa,E

,S)

(Γ,c

k,a

x1..

.xa,E

,(alt

s,E

′ ):S

)br

anch

−−−−→

(Γ,e

,Ê′ ,

S)

wob

eic k

,ay 1

...

y a->

edie

k-t

eA

lter

nat

ive

inalt

sis

t

und

Ê′=

E′ · ∪

⋃ a i=1{y

i7→

E(x

i)}

(Γ,x

,E· ∪{

x7→

p},S

)bl

ack

hole

−−−−−→

(Γ,x

,E· ∪{

x7→

p},S

)fa

lls

für

pke

ine

Bin

dung

inΓ

(Γ,c

k,a

x1..

.xa,E

,p:S

)bl

ack

hole

2−−−−−−→

(Γ,c

k,a

x1..

.xa,E

,p:S

)

(Γ,λ

y->

e,E

,alt

s:S

)bl

ack

hole

3−−−−−−→

(Γ,λ

y->

e,E

,alt

s:S

)

Abbildung

4.2:

Zust

andsü

ber

gangs

rege

lnder

Mar

k2

36

Die Maschine startet mit leerem Heap, leerer Umgebung und leerem Stack. Sie akzeptiertwie vorher, falls der Stack leer ist und der auszuwertende Ausdruck eine Konstrukto-rapplikation oder eine Abstraktion ist.

Bevor wir uns der Implementierung widmen, demonstrieren die Ablauf der Maschine an-hand eines Beispiels:

Beispiel 7. Wir demonstrieren die Auswertung der Mark 2-Maschine anhand des Aus-drucks letrec x = (λy -> y) z, z = c3,0 in x:

Heap Control Environment Stack∅ letrec x = (λy -> y) z, ∅ []

z = c3,0in x

mkBinds−−−−−−→ {1 7→ (((λy -> y) z), x {x 7→ 1, z 7→ 2} []{x 7→ 1, z 7→ 2}),

2 7→ (c3,0, {x 7→ 1, z 7→ 2})}enter−−−→ {2 7→ (c3,0, {x 7→ 1, z 7→ 2})} ((λy -> y) z) {x 7→ 1, z 7→ 2} [#1]push−−−→ {2 7→ (c3,0, {x 7→ 1, z 7→ 2})} (λy -> y) {x 7→ 1, z 7→ 2} [2,#1]take−−→ {2 7→ (c3,0, {x 7→ 1, z 7→ 2})} y {x 7→ 1, z 7→ 2, y 7→ 2} [#1]

enter−−−→ ∅ c3,0 {x 7→ 1, z 7→ 2} [#2,#1]update2−−−−−→ {2 7→ (c3,0, {x 7→ 1, z 7→ 2})} c3,0 {x 7→ 1, z 7→ 2} [#1]update2−−−−−→ {2 7→ (c3,0, {x 7→ 1, z 7→ 2}), c3,0 {x 7→ 1, z 7→ 2} []

1 7→ (c3,0, {x 7→ 1, z 7→ 2})}

4.2.1 Implementierung

Aufgabe 12. Implementieren Sie im Modul LFPC.AbsM.Environment einen polymorphenDatentypen Environment a b, der eine Abbildung von Werten des Types a auf Werte desTypes b darstellt.

Implementieren Sie des weiteren die Operationen

• emptyEnv :: Environment a b zum Erzeugen einer leeren Umgebung

• lookupEnv :: a -> Environment a b -> b, welche einen Wert vom Typ a undeine Umgebung erhält und den Eintrag für den Wert berechnet, d.h. ein Ergebnisvom Typ b liefert. (Im Gegensatz zu lookupHeap) wird die Umgebung dabei nichtverändert, d.h. es wird nur gelesen). Falls kein Eintrag für den übergebenen Wertvorhanden ist, soll ein Laufzeitfehler auftreten.

• insertEnv :: a -> b -> Environment a b -> Environment a b, die einenWert vom Typ a und einen Wert vom Typ b als neue Abbildung in die im dritten

37

Argumenten übergebene Umgebung einfügt und schließlich die Umgebung alsResultat liefert.

Benutzen Sie eine für diese Operationen möglichst effiziente Datenstruktur.

Da wir nun auch Umgebungen mit den benötigten Operationen implementiert haben,können wir nun die Mark 2-Maschine implementieren. Im Modul LFPC.Abs.Mark2 ist derZustand der Mark 2 Maschine durch den Typ Mark2State vorgegeben als:

> type Mark2Environment = (Environment Var Integer)

> newtype Mark2State =

> Mark2State (

> (Heap Integer (CoreLFPCR, Mark2Environment)),

> CoreLFPCR,

> Mark2Environment,

> (Stack (StackElem Integer ([Alt], Mark2Environment)))

> )

Verglichen mit Mark1State ist die Umgebungskomponente neu, die nun für jeden Aus-druck vorhanden sein muss (insbesondere auch bei den im Heap gespeicherten Ausdrückenund den case-Alternativen auf dem Stack). Außerdem werden Heapvariablen nun durchInteger-Werte und nicht mehr durch Variablen vom Typ Var dargestellt. Man beachte,dass die auf den Stack geschobenen Variablen immer Heapvariablen sind.

Aufgabe 13. Implementieren Sie im Modul LFPC.Abs.Mark2 die folgenden Funktionen:

• startState :: CoreLFPCR -> Mark2State, die für einen CoreLFPCR-Ausdruckden Startzustand der Mark 2-Maschine berechnet.

• nextState :: Mark2State -> Counter -> (Mark2State,Counter), die einenMark2State Zustand und einen Zähler erwartet. Der Typ Counter ist im ModulLFPC.Util.Declarations gerade definiert als

type Counter = Integer

Der Zähler wird zum Generieren neuer Heapvariablen verwendet (d.h. der aktuelleZähler wird die aktuelle neue Heapvariable, anschließend wird der Zähler inkremen-tiert),

Das Ergebnis der Funktion nextState ist der Folgezustand der Maschine und deraktuelle Wert des Zählers.

• finalState :: Mark2State -> Counter -> (Mark2State, Counter), die einenZustand der Mark 2-Maschine sowie einen Counter erwartet und das Paar bestehendaus dem Endzustand und dem neuem Counter liefert.

38

• exec :: CoreLFPCR -> Counter -> String, die einen (deterministischen)CoreLFPCR-Ausdruck und einen Counter erwartet und dann das Ergebnis desAblaufs der Mark 2-Maschine als String ausgibt. Hierbei sollen Zahlen in ihrerDezimaldarstellung ausgegeben werden.

Aufgabe 14. Implementieren Sie im Modul LFPC.Run eine Funktion runMark2, die eindeterministisches LFP+C-Programm erwartet, dann das Programm lext, parst, der seman-tischen Analyse unterzieht, in CoreLFPCR umwandelt, schließlich auf der Mark 2-Maschinelaufen lässt und das Ergebnis als String zurück liefert.

4.3 Nebenläufigkeit – Concurrent Mark 2

Bisher können wir nur deterministische LFP+C-Programme ausführen, d.h. die Programmedürfen weder por- noch amb-Ausdrücke enthalten. In diesem Abschnitt erweitern wir dieMark 2-Maschine um Nebenläufigkeit um dann sämtliche LFP+C-Programme ausführenzu können.

Wir erweitern den Zustand der Mark 2-Maschine um eine Folge von Threads (genauereine hierarchische Baumstruktur), jeder dieser Threads hat einen eigenen aktuell auszu-wertenden Ausdruck, eine eigene Umgebung und einen eigenen Stack. Der Heap ist jedochglobal, d.h. er steht allen Threads zur Verfügung.

Bei Auswertung eines Ausdrucks (amb e1 e2) sollen nun zwei nebenläufige Threads fürdie Auswertung von e1 bzw. e2 gestartet werden. Sobald ein Wert bei einem der Threadserhalten ist, wird dieser als Wert des (amb e1 e2) übernommen und die anderen erzeugtenThreads beendet. Bei dieser Auswertung ist Fairness erforderlich, es darf nicht sein, dassz.B. ständig der zu e1 zugehörige Thread ausgewertet wird, aber nie terminiert, währendder zu e2 zugehörige Thread in endlich vielen Schritten zu einem Wert auswerten würde,aber nie dran kommt.

Um Fairness zu erreichen werden Ressourcen verteilt: Jeder Thread besitzt eine Ressource(nicht-negative Ganzzahl), jeder Auswertungsschritt des Threads erniedrigt die Ressourceund die Ressourcen aller Vaterprozesse um 1. Wenn die Ressource 0 ist muss der Threadwarten. Das Verteilen der Ressourcen (Scheduling) ist erst möglich wenn die Ressourcenaller konkurrierender Threads 0 sind. Dann muss jeder Thread eine Ressource größer als0 erhalten.

Die Threads sind hierarchisch in einem binären Baum (Prozessbaum) angeordnet, wo-bei ein innerer Knoten aus einem Paar (n, m) von nicht-negativen Ganzzahlen undzwei Teilbäumen (die ebenfalls Prozessbäume sind) besteht. Wir schreiben dies alsnode(n, m, tn, tm), die Zahlen n und m sind die Ressourcen für die beiden Unterbäume. EinBlattknoten ist gerade ein Thread, d.h. er besteht aus einem Ausdruck, seiner Umgebungund einem Stack. Wir schreiben dies als leaf(e, E, S)

Beispiel 8. Der CoreLFPCR-Ausdruck amb (amb (True False)) (\x -> x) kann dreiThreads erzeugen, der zugehörige Prozessbaum sieht wie folgt aus, wobei (ni, mi) irgend-

39

welche Ressourcen sind.

(n1, m1)

tthhhhhhhh

hhhhhhhh

hhhhh

&&NNNNN

NNNNN

(n2, m2)

yyrrrrrr

rrrr

&&LLLLL

LLLLL

leaf(\x -> x, ∅, [])

leaf(True, ∅, []) leaf(False, ∅, [])

oder in der Notation mit node:node(n1, m1, (node(n2, m2, leaf(True, ∅, []), leaf(False, ∅, []))), leaf(\x -> x, ∅, [])

Der Zustand der Concurrent Mark 2 ist somit ein Paar (Γ, P ) wobei

P ∈ {node(n, m, tn, tm) | n, m ∈ N0, tn, tm ∈ P}∪ {leaf(e, E, S) | e CoreLFPCR-Ausdruck, E Umgebung, S Stack}

und Γ der Heap ist

Der Datentyp für Prozessbäume (PTree) ist im Modul LFPC.Util.PTree definiert als

> data PTree a = Node Integer (Integer, Integer) (PTree a) (PTree a)

> | Leaf Integer a

> deriving (Eq,Show)

Hierbei ist anzumerken, dass Knoten und Blätter noch zusätzlich eine Zahl als erstesArgument besitzen, diese dient zur Identifikation der Knoten, d.h. die gesetzten Zahlensollten stets verschieden sein. Wir können dafür später den Counter benutzen.

Datentypen für einzelne Threads (ConcurrentMark2Thread) und für den Zu-stand der ConcurrentMark2-Maschine (ConcurrentMark2State) sind im ModulLFPC.AbsM.ConcurrentMark2 definiert als:

> newtype ConcurrentMark2Thread =

> ConcurrentMark2Thread (

> CoreLFPCR,

> Mark2Environment,

> (Stack (CStackElem Integer ([Alt], Mark2Environment)))

> )

> newtype ConcurrentMark2State =

> ConcurrentMark2State (

> (Heap Integer (CoreLFPCR, Mark2Environment)),

> PTree (ConcurrentMark2Thread)

> )

40

Man beachte, dass der der Typ der Stackelemente nicht mehr StackElem, sondernCStackElem ist. Wir benötigen nämlich zwei zusätzliche Stackelemente, die wir hier mitAMBRET und

PORRET bezeichnen.

Aufgabe 15. Im Modul LFPC.AbsM.Stack.CStackElem ist der DatentypCStackElem v a, definiert als

> data CStackElem v a = Marked v | Unmarked v | Other a | PorRet | AmbRet

der markierte Variablen vom Typ v, unmarkierte Variablen vom Typ v, Other a-Elemente, sowie die nullstelligen Konstruktoren AmbRet und PorRet beinhaltet. Imple-mentieren Sie die folgenden Operationen:

• isMarkedVar :: CStackElem v a -> Bool, die testet, ob das Stack-Element einemarkierte Variable ist.

• isUnmarkedVar :: CStackElem v a -> Bool, die testet, ob das Stack-Element ei-ne unmarkierte Variable ist.

• isOther :: CStackElem v a -> Bool, die testet, ob das Stack-Element gerade einOther-Element ist.

• fromVar :: CStackElem v a -> v, die eine markierte oder unmarkierte Variablevom Typ StackElem nimmt und die Variable zurück gibt.

• fromOther :: CStackElem v a -> a, die ein Other-Element erwartet und diesesunverpackt zurück gibt.

• mark :: v -> CStackElem v a, die aus einer Variablen eine markierte Variablevom Typ StackElem macht.

• unmark :: v -> CStackElem v a, die aus einer Variablen eine unmarkierte Va-riable vom Typ StackElem macht.

• other :: a -> CStackElem v a

• isPorRet :: CStackElem v a -> Bool, die test ob ein Stackelement eine PorRet-Konstante ist.

• isAmbRet :: CStackElem v a -> Bool, die test ob ein Stackelement eine AmbRet-Konstante ist.

Sie können einen Großteil des Codes aus Aufgabe 8 wiederverwenden!.

Der Startzustand der Concurrent Mark 2-Maschine besteht aus einem leeren Heap, undeinem Prozessbaum, der gerade ein Blatt enthält, bestehend aus dem Ausdruck, der leerenUmgebung und dem leerem Stack.

Aufgabe 16. Implementieren Sie im Modul LFPC.AbsM.ConcurrentMark2 die FunktionstartState :: CoreLFPCR -> ConcurrentMark2State, die für einen CoreLFPCR Aus-druck den Startzustand der Concurrent Mark 2-Maschine berechnet. Als initiale Blatti-dentifikation können Sie den Wert -1 benutzen.

41

4.3.1 Auswahl eines Threads zur Auswertung

Bevor wir einen neuen Zustand berechnen können, müssen wir zunächst einen Threadauswählen, der einen Auswertungsschritt machen darf (am Anfang gibt es nur einenThread, aber wir beschreiben das Verfahren zunächst allgemein).

Die Auswahlprozedur hat noch einen weiteren Zweck: Eventuell müssen Ressourcen neuverteilt werden, falls keine mehr vorhanden sind.

Die in Abbildung 4.3 dargestellten Regeln wählen ein Thread (fair) aus. Wir beginnen dieBerechnung mit dem Paar ([], T ) wobei [] der leere Baumkontext und T der Prozessbaumist. Im folgenden bezeichnen wir mit tree einen nicht genauer spezifizierten Baumkontext,mit tree[s] die Einsetzung des Baumes / Baumkontexts s an die Stelle des Loches (wel-ches mit [] gekennzeichnet ist). Nun werden die Regeln solange auf das Paar bestehendaus Baumkontext und Unterbaum angewendet, bis keine Regel mehr anwendbar ist. DasErgebnis ist dann ein Paar (tree, l) wobei l ein Blatt-Knoten im Prozessbaum ist und treeder darüber stehende Baumkontext ist. Dieser hat an der Stelle ein Loch hat, an welcherdas Blatt stand.

Den Heap lassen wir bei diesen Regeln weg, denn er wird bei der Auswahl nichtberücksichtigt.

(tree[node(n− 1, m, [], tm)], tn)(tree, node(n, m, tn, tm)

select−nondet−−−−−−−−→ oder(tree[node(n, m− 1, tn, [])], tm)

wenn n > 0 und m > 0

tree, node(n, 0, tn, tm)select−l−−−−→ (tree[node(n− 1, 0, [], tm)], tn)wenn n > 0

(tree, node(0, m, tn, tm)select−r−−−−→ (tree[node(0, m− 1, tn, [])], tm)wenn m > 0

(tree, node(0, 0, tn, tm)schedule−−−−−→ (tree, node(n, m, tn, tm))

wobei m, n beliebig positive Zahlen sind

Abbildung 4.3: Regeln zur Thread-Auswahl in der Concurrent-Mark 2 Maschine

Aufgabe 17. Implementieren Sie im Modul LFPC.Util.PTree eine Funktion

select :: PTree a -> RandomList -> (PTree a -> PTree a, PTree a, RandomList))

die einen Prozessbaum sowie eine Liste von positiven Zufallszahlen erwartet und dieThread-Selektion entsprechend Abbildung 4.3 durchführt. Hierbei ist das Ergebnis ein 3-Tupel mit den Komponenten:

42

• Der Baumkontext der nicht gewählten Knoten, er wird als Funktion auf Pro-zessbäumen dargestellt. (Der leere Baumkontext ist gerade die Identitätsfunktion!)

• Das ausgewählte Blatt (welches später den ausgewählten Thread beinhaltet)

• Die Liste der nicht benutzten Zufallszahlen.

Hinweise:

• Der Typ RandomList ist im Modul LFPC.Util.Declarations gerade definiert alstype RandomList = [Integer]

• Verwenden Sie die Liste der Zufallszahlen sowohl beim Scheduling ( schedule−−−−−→) als auchbei der nichtdeterministischen Auswahl zwischen zwei Kindknoten (

select−nondet−−−−−−−−→).

4.3.2 Zustandsübergang

Die eigentlichen Zustandsübergangsregeln nehmen nun das 3-Tupel bestehend aus demHeap, dem ausgewählten Blattknoten und dem restlichen Baumkontext und führen aufdem gewählten Thread einen Auswertungsschritt durch. Das Resultat ist wieder einZustand der Concurrent Mark 2-Maschine, d.h. ein Paar bestehend aus einem evtl.veränderten Heap und dem neuen Prozessbaum. Die Abbildungen 4.4 und 4.5 zeigendiese Regeln.

Die Regeln aus Abbildung 4.4 kennen wir bereits von der Mark 2-Maschine, sie sindlediglich um die Prozessbaumstruktur erweitert.

Die Regeln in Abbildung 4.5 sind notwendig zur Auswertung der nichtdeterministischen

Operatoren. Die Regelnfork(amb)−−−−−−→ und fork(por)−−−−−→ erzeugen aus einem Thread der gera-

de einen amb- bzw. por-Ausdruck auswerten möchte, zwei Threads – jeweils einen zurAuswertung eines Arguments –, die nun konkurrierend laufen. Zusätzlich gibt es zweineue Stack-Elemente

AMBRET und

PORRET, die markieren, ob die Berechnung eines amb- bzw. por-

Arguments durchgeführt wird.

Wenn nun eine amb-Auswertung stattfindet und einer der Threads einen Wert (Abstrakti-on oder Konstruktoranwendung) gefunden hat, so wird dieser Wert übernommen für den

gesamten amb-Ausdruck. Das Erledigen die Regelnambl1−−−→, ambl2−−−→, ambr1−−−→ und ambr2−−−→.

Der nicht mehr benötigte zweite Thread (der mittlerweile auch ein Prozessbaum vonmehreren Threads sein kann) darf jedoch nicht einfach verworfen werden: Er kann Einträge

vom Heap mittelsenter−−−→ genommen haben, aber noch kein Update durchgeführt haben.

Um die fehlenden Heapeinträge zurück zuschreiben (in ihrem momentanen evtl. nichtfertig ausgewerteten Zustand) ist einiges zu tun. Dies werden wir später in Abschnitt 4.3.3erläutern, wenn wir die Funktion kill definieren.

Wenn eine por-Auswertung stattfindet, gibt es mehr Möglichkeiten: Wenn einer der beidenThreads zu True (d.h. c3,0) ausgewertet ist, dann ist es wie bei amb: Der Wert des por-Ausdrucks ist True, der zweite Thread kann mittels kill beendet werden (dies entspricht

43

den RegelnporTruel−−−−−→ und porTruer−−−−−→). Wenn jedoch einer der Threads zu False (d.h. c4,0)

ausgewertet ist, muss er nachschauen, ob der zweite Thread auch zu False ausgewertetist. Ist dies der Fall, so ist das Ergebnis des por-Ausdrucks False (die entsprechenden

Regeln sindporFalsel−−−−−→ und porFalser−−−−−→). Hat der zweite Thread noch kein Ergebnis, so muss

der erste warten (d.h. er reduziert auf sich selbst), die beiden Regelnwaitporl−−−−→ und waitporr−−−−−→

decken diese Fälle ab. Schließlich kann es noch passieren, dass die Argumentauswertungeines por-Ausdrucks einen nicht-booleschen Konstruktor oder eine Abstraktion liefert.

Dann reduziert der Thread auf sich selbst (Regelnblackhole4−−−−−−→ und blackhole5−−−−−−→).

Aufgabe 18. Implementieren Sie im Modul LFPC.AbsM.ConcurrentMark2

• die Funktion nextState’ mit der Signatur:

> nextState’ :: Heap Integer (CoreLFPCR, Mark2Environment)

> -> PTree ConcurrentMark2Thread

> -> (PTree ConcurrentMark2Thread -> PTree ConcurrentMark2Thread)

> -> Counter

> -> (ConcurrentMark2State, Counter)

Die Funktion erwartet einen Heap, einen Blattknoten des Prozessbaums, einen Pro-zessbaumkontext sowie einen Zähler und berechnet entsprechend der definierten Zu-standsübergangsrelation den neuen Zustand und den neuen Zähler.

Die Funktion kill können Sie zunächst weglassen, bzw. als

kill = undefined

definieren.

• die Funktion nextState mit Signatur:

> nextState :: ConcurrentMark2State

> -> Counter

> -> RandomList

> -> (ConcurrentMark2State, Counter, RandomList)

die einen Zustand der Maschine, den Counter und eine Liste von Zufallszahlen er-wartet und dann die Thread-Selektion und das Berechnen des nächsten Zustandesdurchführt und schließlich das 3-Tupel bestehend aus neuem Zustand, neuem Coun-ter und nicht benutzten Zufallszahlen als Ergebnis liefert.

• die Funktion

> finalState :: ConcurrentMark2State

> -> Counter

> -> RandomList

> -> (ConcurrentMark2State, Counter, RandomList)

44

die einen Zustand, einen Counter und eine Liste von Zufallszahlen erwartet und denEndzustand der Maschine, den neuen Counter und die nicht benutzten Zufallszahlenzurückgibt.

• die Funktion exec :: CoreLFPCR -> Counter -> RandomList -> String, dieeinen CoreLFPCR-Ausdruck, einen Counter und eine Liste von Zufallszahlenerhält und zunächst den Startzustand, anschließend den Endzustand der Concur-rent Mark 2-Maschine berechnet und das Ergebnis als String zurück gibt. Wie vorhersollten Zahlen in Dezimaldarstellung zurück konvertiert werden.

45

(Γ,l

eaf((

ex),

E· ∪{

x7→

p},S

),tr

ee)

push

−−→

(Γ,t

ree[

leaf(e

,E· ∪{

x7→

p},p

:S

)])

(Γ,l

eaf(λ

y->

e,E

,p:S

),tr

ee)

take

−−→

(Γ,t

ree[

leaf(e

,E· ∪{

y7→

p},S

)])

(Γ′ · ∪{p

7→(e

′ ,E

′ )},

leaf(i

,E· ∪{

x7→

p},S

),tr

ee)

ente

r−−−→

(Γ′ ,

tree

[lea

f(e

′ ,E

′ ,#

p:S

)])

(Γ,l

eaf(λ

y->

e,E

,#p

:S

),tr

ee)

update

−−−→

(Γ· ∪{

p7→

(λy->

e,E

)},t

ree[

leaf(λ

y->

e,E

,S)]

)

(Γ,l

eaf(letrec

x1

=e 1

,...

,xn

=e n

in

e,E

,S),

tree

)m

kB

inds

−−−−−→

(Γ· ∪

n ⋃ i=1{pi7→

(ei,

Ê)}

,tre

e[le

af(e

,Ê,S

)])

wob

eiÊ

=E· ∪{

x17→

p 1,.

..,x

n7→

p n}

und

p 1,.

..,p

nneu

ePoi

nte

rsi

nd.

(Γ,l

eaf(case

eof

alt

s,E

,S),

tree

)push

Alt

s−−−−−→

(Γ,t

ree[

leaf(e

,E,(

alt

s,E

):S

)])

(Γ,l

eaf(c

k,a

x1..

.xa,E

,#p

:S

),tr

ee)

update

2−−−−→

(Γ· ∪{

p7→

(ck,a

x1..

.xa,E

)},t

ree[

leaf(c

k,a

x1..

.xa,E

,S)]

)

(Γ,l

eaf(c

k,a

x1..

.xa,E

,(alt

s,E

′ ):S

),tr

ee)

branch

−−−−→

(Γ,t

ree[

leaf(e

,Ê′ ,

S)]

)w

obei

c k,a

y 1..

.y a

->

edie

k-t

eA

lter

nat

ive

inalt

sis

t

und

Ê′=

E′ · ∪

⋃ a i=1{y

i7→

E(x

i)

(Γ,l

eaf(x

,E· ∪{

x7→

p},S

),tr

ee)

black

hole

−−−−−→

(Γ,t

ree[

leaf(x

,E· ∪{

x7→

p},S

)])

falls

für

pke

ine

Bin

dung

inΓ

(Γ,l

eaf(c

k,a

x1..

.xa,E

,p:S

),tr

ee)

black

hole

2−−−−−−→

(Γ,t

ree[

leaf(c

k,a

x1..

.xa,E

,p:S

)])

(Γ,l

eaf(λ

y->

e,E

,alt

s:S

),tr

ee)

black

hole

3−−−−−−→

(Γ,t

ree[

leaf(λ

y->

e,E

,alt

s:S

)])

Abbildung

4.4:

Zust

andsü

ber

gangs

rege

lnder

Con

curr

ent

Mar

k2

46

(Γ,l

eaf(amb

e 1e 2

,E,S

),tr

ee)

fork(a

mb)

−−−−−−→

(Γ,t

ree[

nod

e(0,

0,le

af(e

1,E

,AM

BR

ET:S

),le

af(e

2,E

,AM

BR

ET:S

))])

(Γ,l

eaf(por

e 1e 2

,E,S

),tr

ee)

fork(p

or)

−−−−−→

(Γ,t

ree[

nod

e(0,

0,le

af(e

1,E

,PO

RR

ET:S

),le

af(e

2,E

,PO

RR

ET:S

))])

(Γ,l

eaf(λ

y->

e,E

,AM

BR

ET:S

),tr

ee[n

ode(

n,m

,[],

t m)]

)am

bl1

−−−→

(kill(

Γ,t

m),

tree

[lea

f(λ

y->

e,E

,S)]

)

(Γ,l

eaf(c

k,a

x1..

.xa,E

,AM

BR

ET:S

),tr

ee[n

ode(

n,m

,[],

t m)]

)am

bl2

−−−→

(kill(

Γ,t

m),

tree

[lea

f(c

k,a

x1..

.xa,E