303 Pages
English

Advanced object-oriented language mechanisms for variability management [Elektronische Ressource] / vorgelegt von Vaidas Gasiūnas

-

Gain access to the library to view online
Learn more

Description

Advanced Object-Oriented LanguageMechanisms for Variability ManagementVom Fachbereich Informatik der Technischen Universit at Darmstadt genehmigteDissertationzur Erlangung des akademischen Grades einesDoktor-Ingenieurs (Dr.-Ing.)vorgelegt vonMagister der Informatik Vaidas Gasiunasgeboren in Paneve_zys, LitauenReferent: Prof. Dr. Mira MeziniKorreferent: Prof. Dr. Sophia DrossopoulouDatum der Einreichung: 25.11.2009 der mundlic hen Prufung: 16.12.2009Erscheinungsjahr 2010Darmstadt D17iiAbstractDecomposition of software into components is usually not su cient to achieve a high-degree of reusability, because a component seldom completely ts to the needs of aparticular use, and needs to be adapted to speci c requirements and the technical contextof that use. Thus, in order to increase reusability of components, they must be madecon gurable and adaptable, or in other words they must support a certain degree ofvariation.Object-oriented techniques, in particular inheritance and subtype polymorphism, facili-tate modular variability management. Subtype polymorphism can be used to hide vari-ations of an object behind stable inherfaces and bind them dynamically. Inheritance canmodularize unanticipated variations and variations a ecting interfaces of objects. Themodularized variations can be combined using some form of multiple inheritance. Multi-dispatch of methods enables modularization and dynamic binding of multi-dimensionalvariation.

Subjects

Informations

Published by
Published 01 January 2010
Reads 17
Language English
Document size 1 MB

Advanced Object-Oriented Language
Mechanisms for Variability Management
Vom Fachbereich Informatik der Technischen Universit at Darmstadt genehmigte
Dissertation
zur Erlangung des akademischen Grades eines
Doktor-Ingenieurs (Dr.-Ing.)
vorgelegt von
Magister der Informatik Vaidas Gasiunas
geboren in Paneve_zys, Litauen
Referent: Prof. Dr. Mira Mezini
Korreferent: Prof. Dr. Sophia Drossopoulou
Datum der Einreichung: 25.11.2009 der mundlic hen Prufung: 16.12.2009
Erscheinungsjahr 2010
Darmstadt D17iiAbstract
Decomposition of software into components is usually not su cient to achieve a high-
degree of reusability, because a component seldom completely ts to the needs of a
particular use, and needs to be adapted to speci c requirements and the technical context
of that use. Thus, in order to increase reusability of components, they must be made
con gurable and adaptable, or in other words they must support a certain degree of
variation.
Object-oriented techniques, in particular inheritance and subtype polymorphism, facili-
tate modular variability management. Subtype polymorphism can be used to hide vari-
ations of an object behind stable inherfaces and bind them dynamically. Inheritance can
modularize unanticipated variations and variations a ecting interfaces of objects. The
modularized variations can be combined using some form of multiple inheritance. Multi-
dispatch of methods enables modularization and dynamic binding of multi-dimensional
variation.
Classes are often too small units of modularization. In a lot of cases, a cohesive piece of
functionality involves a group of related classes. Although mainstream languages provide
class grouping mechanisms, such as packages and inner classes in Java, the typical object-
oriented techniques, such as inheritance and subtype polymorphism, are not supported
at the scope of such class groups. As a result, variations involving multiple classes must
be encoded by variations of individual classes. Such encodings compromise type-safety
and produce a considerable amount of glue code, which is often error-prone and not
stable.
The main statement of this thesis is that by making typical object-oriented techniques
available at the scope of a group of classes we can provide a better support for managing
variations at that scope.
For the purpose of making inheritance and polymorphism available for a group of classes,
we rely on the ideas of virtual classes and family polymorphism. A large-scale multiple
inheritance is enabled by the propagating mixin composition. In this thesis we present the
rst implementation of these ideas for Java, and propose improvements to their seman-
tics, namely a more intuitive linearization algorithm for propagating mixin composition
and more exible path-dependent types. We also introduce abstract virtual classes, which
iiiincrease the advantages of family polymorphism by providing the possibility to describe
interfaces for families of classes.
Further, we propose a novel concept of dependent classes, which enhances virtual classes
in analogous way like multimethods enhance single-dispatch. The multi-dispatch for
classes not only enables dispatch of their functionality by multiple constructor parame-
ters, but also generalizes family polymorphism with the possibility to express member-
ship of an object in multiple families. The feasibility of the new concept is validated in
two ways. First, we design a concrete language with dependent classes, called DepJ,
and implement a type-checker and interpreter for it. Second, we formalize the features of
ndependent classes in vc and DC calculi, and verify their soundness and decidability.C
A further development of dependent classes, so-called second-order dependent classes
combines parameterization of classes by objects and by types and provides the advan-
tages of dependent classes for generic classes. In particular, they make it possible to
vary the functionality of a generic class with respect to its type parameters, and to de-
ne such variations in a modular way. Abstraction from such variations in the client
code and their dynamic binding is enabled by representing types as runtime values and
supporting dynamic dispatch by such values.
The expected advantages of virtual classes and dependent classes for variation manage-
ment are validated by a set of variation scenarios. We explore variations at the scope
of individual objects, as well as at the scope of a group of objects. We also investigate
interactions of di erent kinds of variations and analyze speci c variation scenarios in the
context of object-oriented frameworks.
We identify the problems of implementing these scenarios using conventional object-
oriented techniques, and show that these problems are resolved by implementations with
the advanced techniques. In particular, we show that virtual classes and propagating-
mixin composition provide the typical advantages of inheritance for managing variations
of a group of objects. Dependent classes provide the typical advantages of multi-dispatch
for managing variations of a class. They also generalize the advantages of virtual classes
with the possibility to modularize variations of multiple overlapping groups of objects,
and provide a better solution for modelling multiple variations of a group of objects.
ivZusammenfassung
Die Zerlegung von Software in Komponenten ist oft nicht ausreichend um einen ho-
hen Wiederverwendbarkeitsgrad zu erreichen, weil eine Komponente selten genau den
Bedurfnissen einer konkreten Verwendung entspricht und deswegen an die speziellen An-
forderungen und den technischen Kontext dieser Verwendung angepasst werden muss.
Um folglich die Wiederverwendbarkeit der Komponenten zu erh ohen, mussen sie kon-
gurierbar und anpassungsf ahig gemacht werden, oder, anders gesagt, sie mussen einen
bestimmten Grad an Variabiliatt unterstutzen.
Die Modularisierung der Variabilit at wird duch die objektorientierten Techniken, inbeson-
dere durch die Vererbung und die Subtyppolymorphie, unterstutzt. Die Subtyppolymor-
phie macht es m oglich, die Variationen eines Objekts hinter stabilen Schnittstellen zu
verbergen und sie dynamisch zu binden. Die Vererbung ist besonders geeignet zur Modu-
larisierung der unvorhergesehenen Variationen und der Variationen, die die Schnittstellen
der Objekte beein ussen. Die modulariserten Variationen k onnen mittels einer Form der
Mehrfach-Vererbung kombiniert werden. Die Multi-Methoden erm oglichen die Modular-
isierung und das dynamische Binden einer mehrdimensionalen Variation.
Die Klassen sind oft zu kleine Einheiten fur Modularisierung. In vielen F allen betri t ein
logisch zusamenh angender Teil der Funktionalit at eine Gruppe von zusamenh angenden
Klassen. Obwohl die etablierten Sprachen verschiedene Mechanismen zur Gruppierung
von Klassen anbieten, zum Beispiel Packages und innere Klassen in Java, werden auf
der Ebene solcher Gruppierungen objektorientierten Techniken, wie die Vererbung und
die Subtyppolymorphie, nicht unterstutzt. Demzufolge mussen die Variationen, die
mehreren Klassen betre en, durch die Variationen der einzelnen Klassen kodiert wer-
den. Solche Kodierungen beeintr achtigen aber die Typsicherheit und erzeugen eine
betr achtliche Menge an Glue-Code.
Die Hauptthese dieser Dissertation ist, dass die Erm oglichung der objektorientierten
Techniken auf der Ebene von Gruppen der Klassen eine bessere Unterstutzung fur die
Modularisierung der Variationen auf dieser Ebene erreicht werden kann.
Um die Vererbung und die Subtyppolymorphie fur eine Gruppe von Klassen zu erm oglichen,
greifen wir auf die Ideen der virtuellen Klassen und der Familienpolymorphie zuruc k.
Die Verwendung von Mehrfachvererbung im gro em Umfang wird durch propagierende
Mixin-Komposition erm oglicht. In dieser Arbeit zeigen wir die erste Implementierung
vdieser Ideen fur Java und schlagen einige Verbesserungen zu ihrer Semantik vor, n amlich
einen intuitiveren Lineasierungsalgorithmus fur die propagierende Mixin-Komposition
und exiblere pfadabh angige Typen. Wir fuhren auch das Konzept der abstrakten
vituellen Klassen ein, das die Beschreibung der Schittstellen von Klassfamilien erm oglicht
und so die Vorteile der Familienpolymorphie steigert.
Au erdem schlagen wir das Konzept der abh angigen Klassen vor, der die virtuellen
Klassen analog zur Idee des Multi-Dispatch erweitert. Multi-Dispatch von Klassen
erm oglicht nicht nur den Dispatch ihrer Funktionalit at durch mehrere Konstruktor-
parameter, sondern erweitert auch die Familien-Polymorphie um die M oglichkeit, die
Zugeh origkeit eines Objekts zu mehreren Familien auszudruc ken. Die Machbarkeit des
neuen Konzepts wurde in zwei Weisen validiert. Erstens haben wir eine konkrete Pro-
grammiersprache mit abh angigen Klassen, DepJ, entworfen und implementiert. Zweit-
nens haben wir die Semantik der abh angigen Klassen durch die Kalkule vc und DCC
formalisiert, die dann auf Korrektheit und Entscheidbarkeit veri ziert wurden.
Eine Weiterentwicklung der abh angigen Klassen, sogennante abh angige Klassen zweiter
Ordnung, vereinigen die Parameterisierung der Klassen durch Objekte und durch Typen
und stellen die Vorteile der abh angigen Klassen auch fur die generischen Klassen bereit.
Insbesondere machen sie es m oglich, die Variationen der Funktionalit at einer generischen
Klasse bezuglic h ihrer Typparameter in einer modularen Weise zu beschreiben. Um die
Abstraktion von solchen Variationen auf der Client-Seite und ihr dynamisches Binden zu
erm oglichen, werden Typen als Laufzeitwerte zur Verfugung gestellt, und der dynamische
Dispatch mit solchen Werten erm oglicht.
Die erwarteten Vorteile der virtuellen und der abh angigen Klassen bezuglic h der Imple-
mentierung von Variationen werden durch eine Reihe verschiedenen Variationsszenarien
ub erpruft. Wir untersuchen die Variationen sowohl auf der Ebene der einzelner Objek-
ten als auch auf der Ebene der Gruppen von Objekten. Des Weiteren erforschen wir die
Interaktionen zwischen verschiedenen Arten von Variationen und untersuchen spezi sche
Variationsszenarien im Kontext der objektorientierten Frameworks.
Wir identi zieren die Probleme mit den Implementierungen solcher Szenarien mit den
konventionellen objektorientierten Techniken, und zeigen dass diese Probleme durch die
fortgeschrittenen Techniken gel ost werden k onnen. Insbesondere zeigen wir dass die
virtuellen Klassen und die propagierende Mixin-Komposition die typische Vorteile der
Vererbung fur die Implementierung von Variationen auf der Ebene einer Gruppe von Ob-
jekten bieten. Die abh angigen Klassen stellen die typischen Vorteile des Multi-Dispatch
fur die Implementierung von Variationen einer Klasse bereit. Sie erweitern auch die
Vorteile der virtuellen Klassen um die M oglichkeit, die Variationen von mehreren einan-
der ub erlappenden Gruppen von Objekten auszudruc ken.
viContents
Preface xv
1 Introduction 1
1.1 Background: Object-Oriented Variation Management . . . . . . . . . . . . 1
1.2 The Thesis in a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Virtual Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Dependent Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Implementation of Variability in Object-Oriented Languages 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Single Variations of Individual Objects . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Using Object Fields to Model Variability . . . . . . . . . . . . . . 13
2.2.2 Using Inheritance to Model Vy . . . . . . . . . . . . . . . . 16
2.2.3 Variation of Functions . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Multiple Variations of Individual Objects . . . . . . . . . . . . . . . . . . 20
2.3.1 Modeling Variations with Instance Variables . . . . . . . . . . . . . 20
2.3.2 Mo V with Inheritance . . . . . . . . . . . . . . . . 20
2.3.3 Combining Inheritance and Helper Objects . . . . . . . . . . . . . 22
2.3.4 Combining Variations with Multi-Dispatch . . . . . . . . . . . . . 26
2.4 Variation of Multiple Objects . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.1 Variations with Inheritance . . . . . . . . . . . . . . . . . . . . . . 29
2.4.2 Combining Variations with Inheritance . . . . . . . . . . . . . . . . 36
2.4.3 Application-Level Variations . . . . . . . . . . . . . . . . . . . . . 37
2.4.4 Variation at Multiple Scopes . . . . . . . . . . . . . . . . . . . . . 39
2.4.5 Dynamic Variations . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5 Variation of Frameworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5.1 Instantiating a Framework . . . . . . . . . . . . . . . . . . . . . . . 45
2.5.2 Dependency on Application Variations . . . . . . . . . . . . . . . . 49
2.5.3 Combining Framework Instances and Variations . . . . . . . . . . 50
2.5.4 Dependency on Multiple Variation Points of a Framework . . . . . 54
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
viiContents
3 Virtual Classes 61
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Virtual Classes in a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.1 Large-Scale Inheritance . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.2 Large-Scale Mixin Composition . . . . . . . . . . . . . . . . . . . . 66
3.2.3 Family Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3 Semantics of Virtual Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.1 Mixin Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.2 Inheritance with Virtual Classes . . . . . . . . . . . . . . . . . . . 78
3.3.3 Dependent Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3.4 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.4 Variation Management with Virtual Classes . . . . . . . . . . . . . . . . . 86
3.4.1 Variations of Multiple Objects . . . . . . . . . . . . . . . . . . . . 87
3.4.2 Interaction of Inheritance and Helper Objects . . . . . . . . . . . . 96
3.4.3 Variation of Frameworks . . . . . . . . . . . . . . . . . . . . . . . . 101
3.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4 Dependent Classes 117
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.2 Dependent Classes in a Nutshell . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.1 Dynamic Dispatch . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.2 Dispatch of Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.3 Multi-Dispatch of Classes . . . . . . . . . . . . . . . . . . . . . . . 122
4.2.4 Multiple Families . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.2.5 Dependent Classes and Multimethods . . . . . . . . . . . . . . . . 130
4.3 Language Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.3.1 Combining Nesting and Parameterization . . . . . . . . . . . . . . 134
4.3.2 Varying Set of Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.3.3 Recursive Dependencies . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.4 Abstract Dependent Classes . . . . . . . . . . . . . . . . . . . . . . 139
4.3.5 Dispatch Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.3.6 Method Renements . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.3.7 Checking Method Completeness and Uniqueness . . . . . . . . . . 144
4.3.8 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.3.9 Second-Order Dependent Classes . . . . . . . . . . . . . . . . . . . 148
4.4 Variation Management with Dependent Classes . . . . . . . . . . . . . . . 156
4.4.1 Variations of Individual Objects . . . . . . . . . . . . . . . . . . . 156
4.4.2 Variation of Multiple Objects . . . . . . . . . . . . . . . . . . . . . 164
4.4.3 V of Frameworks . . . . . . . . . . . . . . . . . . . . . . . . 171
4.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
viiiContents
5 Semantics of Dependent Classes 179
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
n5.2 vc Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.2.2 Operational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.2.3 Path Normalization and Type Equivalence . . . . . . . . . . . . . 186
5.2.4 Substitution in Types . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.2.5 Subtyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.2.6 Expression Typing and Well-Formedness . . . . . . . . . . . . . . . 193
n5.2.7 Properties of vc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.2.8 Dispatch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.3 DC Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201C
5.3.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
5.3.2 Constraint System . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.3.3 Operational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . 207
5.3.4 Type Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.4 Soundness of DC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211C
5.4.1 Type Preservation . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.4.2 Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
5.5 Decidability of DC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218C
5.5.1 Decidability of Constraint Entailment . . . . . . . . . . . . . . . . 219
5.5.2y of Variable Elimination . . . . . . . . . . . . . . . . . 224
5.5.3 Decidability of Expression Typing . . . . . . . . . . . . . . . . . . 233
5.5.4 Checking Method Completeness and Uniqueness . . . . . . . . . . 235
6 Related Work 243
6.1 Virtual Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
6.1.1 Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
6.1.2 gbeta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
6.1.3 vc Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
6.1.4 Nested Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
6.1.5 Tribe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
6.1.6 Deep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
6.1.7 Obj calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
6.1.8 Scala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
6.2 Flexible Modularization Techniques . . . . . . . . . . . . . . . . . . . . . . 255
6.2.1 Lightweight Family Polymorphism . . . . . . . . . . . . . . . . . . 255
6.2.2 Mixin Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
6.2.3 Classboxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
6.2.4 Open Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
6.2.5 Keris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
ix