Compiling and Distributing Generic Libraries with Heterogeneous Data and Code Representation

Abstract

Generic programming has evolved at fast pace in recent years. There now exist numerous programming languages that support genericity, and generic libraries were developed that range from small utility libraries to huge general purpose or domain specific libraries. The importance of specification and verification was further emphasized in the context of generic algorithms and data structures, which became major issues in the research community. The largest generic code base is available in C++ which plays a central role for generic programming, because the Standard Template Library (STL) was implemented in C++. The STL ignited the application of its underlying principles to other domains, resulting in influential C++ libraries like the Matrix Template Library (MTL) or the Boost Graph Library (BGL). Other C++ libraries like the Matrix Template Library (MTL) or the Boost Graph Library (GPL) applied the same principles underlying the STL.

This thesis deals with a problem that became apparent for languages like C++, Ada, or Modula-3 that support genericity with heterogeneous data and code representation, especially with regard to large generic libraries. These libraries cannot be compiled and distributed without their source code. Application programs using generic libraries will have to compile the occurring instantiations of generic constructs from the libraries' source code repeatedly during their development cycle.

We first present a general approach to overcome the conceptual problem that necessitates this practice. It mandates a strict separation of compiler front-end and back-end which are connected by a special intermediate representation. Then an overview of the GILF system is given, our incarnation of the solution. Although the GILF system was developed for SuchThat, a generic programming language devised by Sibylle Schupp, GILF is designed to support a wide range of generic programming languages with varying semantics for instantiation, specialization and overloading. We achieve this by separating declarations from definitions, as well as splitting the instantiation process into analysis and application. The information gathered by instantiation analysis is propagated from a compiler's front-end to its back-end as explicit bindings of instantiation parameters to arguments in the mentioned intermediate language. GILF even allows binding multiple algorithms to one function symbol, which provides the basic mechanisms required for online or off-line algorithm selection. Algorithm selection can be exploited with instantiation at load-time or run-time.

Thereafter, we introduce XGILF, the XML-based external GILF representation. An extensive specification is elaborated, covering all core features of GILF. Finally, the GILF prototype implementation is discussed in detail, showing the feasibility of our approach.

Generische Programmierung hat sich in den letzten Jahren mit beträchtlicher Geschwindigkeit entwickelt. Es existiert nun eine Vielzahl von Programmiersprachen die Generizität unterstützen. Weiterhin wurden generische Bibliotheken erstellt, die von kleinen Hilfsbibliotheken bis hin zu großen Universal- oder bereichsspezifischen Bibliotheken reichen. Die Bedeutung von Spezifikation und Verifikation wurde im Kontext generischer Algorithmen und Datenstrukturen weiter betont, deshalb entwickelten sich diese beiden Aspekte zu Kernpunkten in der Forschungsgemeinde. Die größte Basis an generischem Code existiert in C++, das eine zentrale Rolle für generische Programmierung spielt, da die Standard Template Library (STL) in C++ implementiert wurde. Die STL initiierte die Anwendung der ihr zugrunde liegenden Prinzipien auf andere Bereiche, was einflussreiche Bibliotheken wie die Matrix Template Library (MTL) oder die Boost Graph Libraray (BGL) hervorbrachte.

Diese Arbeit beschäftigt sich mit einem Problem, dass bei Sprachen wie C++, Ada95 oder Modula-3 deutlich wurde, die Generizität mit heterogener Daten- und Codedarstellung unterstützen, insbesondere im Hinblick auf große generische Bibliotheken. Diese Bibliotheken können ohne ihren Quellcode nicht übersetzt und verteilt werden. Anwendungsprogramme, die generische Bibliotheken verwenden, müssen in ihrem Entwicklungszyklus die auftretenden Instanzen generischer Konstrukte wiederholt aus dem Quellcode der Bibliotheken übersetzen.

Wir präsentieren zuerst einen allgemeinen Ansatz, der die Überwindung des konzeptuellen Problems ermöglicht, das dieses Vorgehen erforderlich macht. Es schreibt eine strikte Trennung des Übersetzer-Frontends und -Backends vor, die über eine besondere Zwischensprache verbunden sind. Anschließend geben wir einen Überblick über das GILF-System, unsere Realisierung der Lösung. Obwohl das GILF-System ursprünglich für SuchThat entwickelt wurde, einer von Sibylle Schupp konzipierten generischen Programmiersprache, unterstützt sein Design eine weite Spanne von generischen Programmiersprachen mit variierender Semantik für Instanziierung, Spezialisierung und Überladung. Wir erreichen dies durch die Separierung von Deklarationen und Definitionen sowie der Teilung des Instanziierungsprozesses in Analyse und Applikation. Die mittels Instanziierungsanalyse bestimmten Informationen werden in der angesprochenen Zwischensprache als explizite Bindungen von Instanziierungsparameter an ihre Argumente vom Übersetzer-Frontend zum Übersetzer-Backend propagiert. GILF erlaubt es sogar mehrere Algorithmen an einen Funktionsbezeichner zu binden, was den grundlegenden Mechanismus zur Verfügung stellt, der für Offline- oder Online-Algorithmenselektion benötigt wird. Algorithmenselektion kann durch Instanziierung zur Lade- oder Laufzeit ausgenutzt werden.

Danach stellen wir XGILF vor, die XML-basierte externe Repräsentierung von GILF. Eine umfangreiche Spezifikation wird erarbeitet, die alle Hauptmerkmale von GILF behandelt. Abschließend wird die prototypische GILF-Implementierung diskutiert, die die Umsetzbarkeit unseres Ansatzes zeigt.