Refined compilation of pattern-matching for functional languages (Q1123586)

Gegenstand des Papiers ist ein Algorithmus, der auf pattern-matching basierende Funktionsdefinitionen funktionaler Sprachen in sogenannte imperative Ausdrücke übersetzt. Die Semantik der Quellsprachen- Funktionen ist durch einen call-by-value Term-Ersetzungsprozeß definiert; die Zielsprache besteht aus geschachtelten if-then-else- Ausdrücken. Als wesentliche Neuerung gegenüber den in der Literatur bisher behandelten Übersetzungsalgorithmen akzeptiert der hier vorgestellte Algorithmus neben den Term-Ersetzungsregeln der Funktion als weiteren Parameter eine Beschreibung der möglichen Argumente (domain). Dieser zusätzliche Parameter führt zu einer einfachen Formulierung des Algorithmus und ermöglicht außerdem die Erzeugung von effizienteren Zielsprachenprogrammen. Ausgehend von Aufwandsbetrachtungen entwickelt der Autor eine Heuristik, die die Effizienz des Algorithmus verbessert. Erweiterungen der Quellsprache mit Teilmengentypen (subtypes), Gleichungen (equations between constructors) und bedingten Term-Ersetzungsregeln (conditional rewrite rules), die ohne große Änderungen am Algorithmus übersetzt werden können, demonstrieren die Bedeutung des Verfahrens für die Implementierung funktionaler Sprachen.