Eine generische funktionale Programmiersprache: Theorie, Sprachentwurf, Implementierung und Anwendung
Final Report Abstract
Ein Ansatz zur generischen funktionalen Programmierung benötigt drei Bestandteile: • eine Art der Typrepräsentation, • einen Mechanismus zur Reflektion von Typen, • und eine allgemeine Sicht auf die Struktur von Typen. Für jeden Bestandteil gibt es verschiedene Wahlmöglichkeiten. Die Bestandteile sind weitgehend orthogonal und spannen daher einen dreidimensionalen Entwurfsraum für generische funktionale Programmierung auf. Nicht alle Kombinationen machen Sinn, aber für jeden Bestandteil können die Möglichkeiten isoliert betrachtet und auf Stärken und Schwächen verglichen werden. Während die Wahl der Typrepräsentation und des Reflektionsmechanismus durchaus praktisch relevant ist, so ist es die Sicht auf die Struktur von Typen, die einem Ansatz zur generischen Programmierung seine Eigenständigkeit verleiht. Viele Ansätze zur generischen Programmierung bestanden bereits zu Beginn des Projektes. Mittlerweile sind noch einige neue hinzugekommen. Normalerweise verwenden verschiedene Ansätze nicht nur unterschiedliche Terminologie, sondern kombinieren verschiedene Wahlmöglichkeiten auf den drei Achsen willkürlich miteinander. Dadurch wird verschleiert, ob die Stärken eines bestimmten Ansatzes inhärent in der verwendeten Sicht liegen, oder ob sie auf andere Ansätze übertragbar sind. Unsere Arbeit im Projekt hat zur Identifikation des oben beschriebenen Entwurfsraums geführt, und es ist uns gelungen, zumindest die Haskell-spezifischen Ansätze zur generischen funktionalen Programmierung darin zu positionieren. In der Konsequenz können wir nun einerseits auf einfache Art und Weise neue, bisher unerforschte Kombinationen bilden und andererseits die Achsen getrennt voneinander evaluieren. Durch Kombination der jeweils stärksten Wahlmöglichkeiten können wir einen idealen Ansatz zur generischen Programmierung schaffen. Nach unseren bisherigen Erkenntnissen bietet sich hierzu an, Typreflektion mittels verallgemeinerten algebraischen Datentypen zu betreiben. Da hierbei ein Datentyp alle Datentypen repräsentiert, muss dieser Datentyp erweiterbar sein. Wir haben dazu für Haskell eine einfache Lösung gefunden und präsentiert. Die Haskell-Typsprache kann fast vollständig repräsentiert werden: Typapplikationen und parametriesierte Typterme mit freien Variablen sind keine Hindernisse. Als Sicht halten wir die zwei sogenannten "Scrap your Boilerplate"-Sichten "Spine" und "TypeSpine" für die geeignetsten. Bei der "Spine"-Sicht wird jedes Element eines Datentyps als Applikation eines Konstruktors auf seine Argumente aufgefasst. Dies ermöglicht eine breite Anwendbarkeit der Sicht und eine konzise Definition von generischen Funktionen durch Unterscheidung von nur zwei Fällen: einen zur Interpretation des Konstruktors selbst, und einen zur Interpretation der Applikation auf ein Argument. Diese Einfachheit macht die Sicht attraktiv für den Anwender.
Publications
- (2005). Type Inference for Generic Haskell . Technischer Bericht UU-CS-2005-060, Institute of Information and Computing Sciences, Utrecht University.
Rodriguez, Alexey, J. Jeuring und A. Löh
- (2006). "Scrap Your Boilerplate" Reloaded. In: Wadler, Philip und M. Hagiya, Hrsg.: Proceedings of the Eighth International Symposium on Functional and Logic Programming (FLOPS 2006), 24- 26 April 2006, Fuji Susono, Japan, Bd. 3945 d. Reihe Lecture Notes in Computer Science, S. 13¿-9. Springer-Verlag.
Hinze, Ralf, A. Löh und B. C. Oliveira
- (2006). "Scrap Your Boilerplate" Revolutions. In: Uustalu, Tarmo, Hrsg.: 8th International Conference on Mathematics of Program Construction (MPC '06), Bd. 4014 d. Reihe Lecture Notes in Computer Science, S. 180-208. Springer-Verlag.
Hinze, Ralf und A. Löh
- (2006). Generic views on data types. In: Uustalu, Tarmo, Hrsg.: Mathematics of Program Construction, 8th International Conference, MPC 2006, Kuressaare, Estonia, July 3-5, 2006 , Bd. 4014 d. Reihe Lecture Notes in Computer Science, S. 209-234. Springer-Verlag.
Holdermans, Stefan, J. Jeuring, A. Löh und A. Rodriguez
- (2006). Generics as a Library. In: Nilsson, Henrik, Hrsg.: Proceedings of the Seventh Symposium on Trends in Functional Programming, April 19-21, 2006, Nottingham, UK.
Oliveira, Bruno C. d. S., R. Hinze und A. Lölh
- (2006). Generics for the masses. J. Functional Programming, 16(4&5):451-483.
Hinze, Ralf
- (2006). Open data types and open functions. In: Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, Venice, Italy, S. 133-144. ACM Press.
Löh, Andres und R. Hinze
- (2006). Open data types and open functions. Technischer Bericht IAI-TR-2006-3, Institut für Informatik III, Universität Bonn.
Hinze, Ralf und A. Löh
- (2006). Open data types and open functions. Technischer Bericht IAI-TR-2006-3, Institut für Informatik III, Universität Bonn.
Hinze, Ralf und A. Löh
- (2006). Typed Contracts for Functional Programming. In: Wadler, Philip und M. Hagiya, Hrsg.: Proceedings of the Eighth International Symposium on Functional and Logic Programming (FLOPS 2006), 24- 26 April 2006, Fuji Susono, Japan, Bd. 3945 d. Reihe Lecture Notes in Computer Science, S. 208-225. Springer-Verlag.
Hinze, Ralf, J. Jeuring und A. Löh
- (2007). Comparing Approaches to Generic Programming. In: Backhouse, Roland, J. Gibbons, R. Hinze und J. Jeuring, Hrsg.: Datatype-Generic Programming 2006 , Bd. 4719 d. Reihe Lecture Notes in Computer Science, S. 72-149. Springer-Verlag.
Hinze, Ralf, J. Jeuring und A. Löh
- (2007). Extensible and modular generics for the masses. In: Trends in Functional Programming 7 , S. 199-216. Intellect.
Oliveira, Bruno C. D. S., R. Hinze und A. Löh
- (2007b). Generic Programming, Now!. In: Backhouse, Roland, J. Gibbons, R. Hinze und J. Jeuring, Hrsg.: Datatype- Generic Programming 2006 , Bd. 4719 d. Reihe Lecture Notes in Computer Science, S. 150-208. Springer-Verlag.
Hinze, Ralf und A. Löh
