Compiling and distributing generic libraries with heterogeneous data and code representation [Elektronische Ressource] / vorgelegt von Roland Weiss

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2003
• Nombre de lectures: 5
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

CompilingandDistributingGenericLibraries
withHeterogeneousDataandCodeRepresentation
Dissertation
derFakultat¨ fur¨ Informations undKognitionswissenschaften
derEberhard Karls Universit at¨ Tubingen¨
zurErlangungdesGradeseines
DoktorsderNaturwissenschaften(Dr. rer. nat.)
vorgelegtvon
Dipl. Inform. RolandWeiss
ausRatibor
Tubingen¨
2003Tagdermundlichen¨ Qualifikation: 29.01.2003
Dekan: Prof. Dr. UlrichGuntzer¨
1. Berichterstatter: Prof. Dr. Rudiger¨ Loos
2. Prof. Dr. SibylleSchupp
(RensselaerPolytechnicInstitute,Troy,NY,USA)ToHannahandEddaAbstract
Generic programming has evolved at fast pace in recent years. There now exist nu
merous pr languages that support genericity, and generic libraries were de
veloped that range from small utility libraries to huge general purpose or domain spe
cific libraries. The importance of specification and verification was further emphasized
in the context of generic algorithms and data structures, which became major issues in
theresearchcommunity. ThelargestgenericcodebaseisavailableinC++whichplaysa
centralroleforgenericprogramming,becausetheStandardTemplateLibrary(STL)was
implementedinC++. TheSTLignitedtheapplicationofitsunderlyingprinciplestoother
domains,resultingininfluentialC++librariesliketheMatrixTemplateLibrary(MTL)or
theBoostGraphLibrary(BGL).
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
anddistributedwithouttheirsourcecode. Applicationprogramsusinggenericlibraries
willhavetocompiletheoccurringinstantiationsofgenericconstructsfromthelibraries’
sourcecoderepeatedlyduringtheirdevelopmentcycle.
We first present a general approach to overcome the conceptual problem that neces
sitates 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
developedfor SUCHTHAT,agenericprogramminglanguagedevisedbySibylleSchupp,
GILFisdesignedtosupportawiderangeofgenericprogramminglanguageswithvary
ing semantics for instantiation, specialization and overloading. We achieve this by sep
arating declarations from definitions, as well as splitting the instantiation process into
analysis and application. The information gathered by instantiation analysis is propa
gatedfromacompiler’sfront endtoitsback endasexplicitbindingsofinstantiationpa
rameters to arguments in the mentioned intermediate language. GILF even allows bind
ing multiple algorithms to one function symbol, which provides the basic mechanisms
required for online or off line algorithm selection. Algorithm selection can be exploited
withinstantiationatload timeorrun time.
Thereafter, weintroduceXGILF,theXML basedexternal GILFrepresentation. Anex
tensive specification is elaborated, covering all core features of GILF. Finally, the GILF
prototypeimplementationisdiscussedindetail,showingthefeasibilityofourapproach.Zusammenfassung
GenerischeProgrammierunghatsichindenletztenJahrenmitbetrachtlicher¨ Geschwin
digkeit entwickelt. Es existiert nun eine Vielzahl von Programmiersprachen die Gene
rizitat¨ unterstutzen.¨ 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 generi
scher Algorithmen und Datenstrukturen weiter betont, deshalb entwickelten sich diese
beiden Aspekte zu Kernpunkten in der Forschungsgemeinde. Die großte¨ Basis an gene
rischem Code existiert in C++, das eine zentrale Rolle fur¨ generische Programmierung
spielt,dadieStandardTemplateLibrary(STL)inC++implementiertwurde.DieSTLin
itiiertedieAnwendungderihrzugrundeliegendenPrinzipienaufandereBereiche,was
einflussreicheBibliothekenwiedieMatrixTemplateLibrary(MTL)oderdieBoostGraph
Libraray(BGL)hervorbrachte.
Diese Arbeit beschaftigt¨ sich mit einem Problem, dass bei Sprachen wie C++, Ada95
oder Modula 3 deutlich wurde, die Generizit at¨ mit heterogener Daten und Codedar-
stellungunterstutzen,¨ insbesondereimHinblickaufgroßegenerischeBibliotheken.Die
se Bibliotheken konnen¨ ohne ihren Quellcode nicht ubersetzt¨ und verteilt werden. An
wendungsprogramme, die generische Bibliotheken verwenden, mussen¨ in ihrem Ent
wicklungszyklusdieauftretendenInstanzengenerischerKonstruktewiederholtausdem
QuellcodederBibliothekenubersetzen.¨
¨Wirprasentier¨ enzuersteinenallgemeinenAnsatz,derdieUberwindungdeskonzep
tuellen Problems ermoglicht,¨ das dieses Vorgehen erforderlich macht. Es schreibt eine
¨strikte Trennung des Ubersetzer Frontends und Backends vor, die uber¨ eine besonde
¨re Zwischensprache verbunden sind. Anschließend geben wir einen Uberblick uber¨ das
¨ ¨ ¨GILF System,unsereRealisierungderL osung.ObwohldasGILF Systemurspr unglichfur
SUCHTHAT entwickelt wurde, einer von Sibylle Schupp konzipierten generischen Pro
grammiersprache, unterstutzt¨ sein Design eine weite Spanne von Program
¨miersprachen mit variierender Semantik fur¨ Instanziierung, Spezialisierung und Uber-
ladung. Wir erreichen dies durch die Separierung von Deklarationen und Definitionen
sowiederTeilungdesInstanziierungsprozessesinAnalyseundApplikation.Diemittels
Instanziierungsanalyse bestimmten Informationen werden in der angesprochenen Zwi
schensprache als explizite Bindungen von Instanziierungsparameter an ihre Argumen
¨ ¨te vom Ubersetzer Frontend zum Ubersetzer Backend propagiert. GILF erlaubt es sogar
mehrereAlgorithmenaneinenFunktionsbezeichnerzubinden,wasdengrundlegenden
Mechanismus zur Verfugung¨ stellt, der fur¨ Offline oder Online Algorithmenselektion
benotigt¨ wird.AlgorithmenselektionkanndurchInstanziierungzurLade oderLaufzeit
ausgenutztwerden.
Danach stellen wir XGILF vor, die XML basierte externe Repr asentier¨ ung von GILF.
Eine umfangreiche Spezifikation wird erarbeitet, die alle Hauptmerkmale von GILF be
handelt. Abschließend wird die prototypischeGILF Implementierung diskutiert, die die
UmsetzbarkeitunseresAnsatzeszeigt.Contents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 FromConceptstoMachineCode 3
2.1 GenericProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 ExploringGenericitywiththeFactorialandGammaFunction . . . . . 5
2.2.1 MathematicalBackground . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 Genericity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 AlgebraicSpecificationin SUCHTHAT with TECTON . . . . . . . . . . . . . 8
2.4 IntegratingandImplementation . . . . . . . . . . . . . . 11
2.5 GeneratingCodeforGenericAlgorithms . . . . . . . . . . . . . . . . . 14
2.5.1 TheInstantiationProcess . . . . . . . . . . . . . . . . . . . . . . . 14
2.5.2 OverviewofaTraditionalCompilationSystem . . . . . . . . . . 16
2.5.3 IncorporatingInstantiationintotheCompilationProcess . . . . 18
2.5.4 EasingtheTension . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 TheGILFCompilationSystem 24
3.1 RationalefortheIntermediateRepresentation . . . . . . . . . . . . . . 24
3.1.1 AbstractionLevel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.3 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 InfrastructureofaGILFSystem . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Front Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Code GeneratingLinkerandLoader . . . . . . . . . . . . . . . . 31
3.2.3 NativeCodeCache . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.4 RuntimeSystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.5 OptimizationSystem . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 TheAnnotatedXGILFSpecification 47
4.1 AConciseSummaryofXML. . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Elements,Attributes,andText . . . . . . . . . . . . . . . . . . . . 47
4.1.2 Entities,Well Formedness,andmore . . . . . . . . . . . . . . . . 48
4.1.3 Validdocuments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.4 Namespaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.5 XMLParsingTechnologies: DOMandSAX . . . . . . . . . . . . . 49ii CONTENTS
4.2 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Namespace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 GeneralAttributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .