392139 Implementierung funktionaler Programmiersprachen (S) (WiSe 2003/2004)

In dieser Veranstaltung soll ein Compiler für eine funktionale Programmiersprache entwickelt werden. Hierbei orientieren wir uns an der Programmiersprache Haskell. Die im Seminarteil erarbeiteten theoretischen Grundlagen sollen dabei im Übungsteil in die Praxis umgesetzt werden.

Die typische Vorgehensweise beim Übersetzen einer funktionalen Programmiersprache ist folgende:

• Übersetzen der syntaktisch reichen Ausgangssprache in eine einfache Kernsprache ("core language"). Diese Kernsprache ist sehr simpel gehalten, und daher relativ einfach zu implementieren. Gleichzeitig bietet sie aber die volle Leistungsfähigkeit der Ausgangssprache. Beispielweise lassen sich if-then-else Ausdrücke, Wächter und Pattern Matching auch durch case-Konstrukte ausdrücken.

• Übersetzen der Kernsprache in Programmcode für eine abstrakte Zielmaschine. Hier gab es in der Vergangenheit eine Reihe von Entwicklungen, u.a. die Three Instruction Machine (TIM) und die G-Machine mit ihren Varianten (Spineless G-Machine und Spineless Tagless G-Machine (STGM)). Die im Haskell-Compiler GHC verwendete abstrakte Maschine ist die STGM.

• Übersetzen des Codes für die abstrakte Maschine in konkreten Maschinencode. Hier wird üblicherweise C als eine Art "High-level-Assembler" verwendet. Da es für fast alle denkbaren Architekturen einen C Compiler gibt, hat diese Vorgehensweise den Vorteil, dass man die erzeugten Programme ohne Umwege auf einer Vielzahl von Rechnerarchitekturen verwenden kann.

Die einzelnen Phasen der Übersetzung sollen in Kleingruppen bearbeitet werden, so dass am Ende ein möglichst vollständiger Übersetzer von einer funktionalen Programmiersprache nach C vorliegt. Beginnen wollen wir in dieser Veranstaltung mit der Übersetzung der Kernsprache. Je nach Teilnehmerzahl können aber auch zusätzliche höhere Sprachkonstrukte (z.B. Pattern Matching, Listenbeschreibungen) hinzugenommen werden.

Entsprechend dem Thema der Veranstaltung, soll der Übersetzer selbst in einer funktionalen Sprache entwickelt werden. Hier bietet sich natürlich Haskell an.

Requirements for participation, required level

Das Seminar und die Übung bauen direkt aufeinander auf, daher ist eine Teilnahme an beiden Veranstaltungen erforderlich.

Bibliography

• Simon L. Peyton Jones, David R. Lester

Implementing Functional Languages
Prentice Hall, 1992

• Simon L. Peyton Jones

The Implementation of Functional Programming Languages
Prentice-Hall, 1987

• Brian W. Kernighan, Dennis M. Ritchie

The C Programming Language. 2. ed.
Prentice Hall, 1988

External comments page

http://www.techfak.uni-bielefeld.de/ags/pi/lehre/W03.html#392139