Der Haskell-Compiler GHC verwendet eine Reihe von Programmanalysen, um das gegebene Programm besser zu verstehen und dann so umzubauen, dass es schneller läuft.

Eine dieser Analysen ist die Demand Analysis, die Fragen beantwortet: Welche Argumente einer Funktion werden auf jeden Fall ausgewertet? Welche gar nicht? Welche höchstens einmal? Die Antworten darauf werden als strictness signature im Syntaxbaum gespeichert.

Eine weitere ist die Call Arity Analyse, die die Frage beantwortet: Wie oft wird eine Funktion aufgerufen, und mit wievielen Argumenten? Auch diese Analysie speichert das Ergebnis im Syntaxbaum.

Bisher laufen diese Analysen unabhängig voneinander, und verwenden ihre eigenen Datentypen um den analysierten Code zu annotieren. Dabei gibt es Überschneidungen, etwa die Aussage, dass eine Funktion nur einmal aufgerufen wird, lässt sich auch in der Sprache der strictness signatures ausdrücken. Außerdem können die Analysen vermutlich jeweils mit Hilfe der anderen präsziser werden.

Eine komplette Verschmelzung der Analysen ist allerdings nicht einfach möglich: Grundsätzlich untersucht die Demand Analysis zuerst die Definition einer Funktion, um die daraus gewonnen Informationen bei der Analysis des Gültigkeitsbereichs zu verwenen, während Call Arity erst die Aufrufe einer Funktion und dann ihre Defintion betrachtet.

Aufgabe:

Sie untersuchen in dieser Arbeit, in wie weit die Analysen verschmolzen werden können, und ob dies zu einer Verbesserung der Programm oder auch der Compiler-Performance führt. Mögliche Ansätze, nach aufsteigendem Integrationsgrad sortiert, sind:

• Verwendung der Ergebnisse der einen Analyse in der jeweils anderen.
• Vereinheitlichung der Datentypen der Ergebnisse.
• Vollständige Integration in einen Algorithmus, mit einer guten Lösung des Problems der Analysereihenfolge (etwa durch Fixpunktiteration oder geeignete Heuristiken).

Sie arbeiten diese und möglicherweise weitere Ansätze aus, beschreiben sie gründlich und präzise und mit Bezug auf die Beschreibungen der Analsen in der Literatur und implementieren Ihre Ansätze im Compiler. Durch empirische Analyse bewerten Sie diese Ansätze und wägen den Nutzen (etwa schnellerer Code) gegen die Kosten (etwa längere Kompilierzeit, größere Komplexität im Compiler) ab.

Voraussetzungen

Sie haben Erfahrung mit funktionale Programmierung und können in Haskell Programmieren. Sie können Gedanken formal präzise ausarbeiten und machen dies auch gerne.

Diese Arbeit ergebnisoffen gestellt und erfordert von Ihnen, selbständig das Thema zu durchdringen, aktiv mögliche Ansätze zu untersuchen und kreativ Lösungen zu finden.

Schlüsselworte

Haskell, Compiler

Literatur

Demand Analysis:

Ilya Sergey, Dimitrios Vytiniotis, and Simon Peyton Jones: “Modular, Higher-order Cardinality Analysis in Theory and Practice,”, http://research.microsoft.com/apps/pubs/?id=204260

“Demand analyser in GHC”: https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Demand

Call Arity:

Joachim Breitner: “Call Arity”, http://link.springer.com/chapter/10.1007/978-3-319-14675-1_3

Joachim Breitner: “Lazy Evaluation: From natural semantics to a machine-checked compiler transformation”, http://www.joachim-breitner.de/thesis/

Joachim Breitner: “Formally Proving a Compiler Transformation Safe”: http://www.joachim-breitner.de/publications/CallArity-preprint.pdf

Informationen zum GHC:

https://ghc.haskell.org/trac/ghc/wiki/Newcomers



Veröffentlichungen

Veröffentlichung

Call Arity vs. Demand Analysis

Betreuer

Ehemalige Mitarbeiter
Dr. rer. nat. Joachim Breitner
Dipl.-Inform. Denis Lohner

Studenten

Wissenschaftliche Mitarbeiter
Sebastian Graf