PHD With Title
PHD With Title
PHD With Title
Peter Ebraert
March 2009
To my wife
whose endless patience and
support made this dissertation possible
To my mother
whose belief in her children’s capacities
is so high that it makes things
like a PhD just happen
Acknowledgements
The foundations of this dissertation were established in 2002, when Theo D’Hondt
proposed me to enroll for the European Master in Object-Oriented Software En-
gineering (EMOOSE). In this master-after-master formation, I was given the op-
portunity to meet and learn from expert researchers in the domain of software
engineering, and more specifically in the field of the separation of programming
concerns. Under the guidance of Eric Tanter, I realised that research on the sep-
aration of programming concerns was really interesting in a context of software
evolution. Thanks Theo and Eric!
With the help of Tom Tourwé and other colleagues from the programming
technology lab, I assembled an application for obtaining a grant from the Institute
for the Promotion of Innovation by Science and Technology in Flanders (IWT). I
was one of the lucky students that were awarded a four year grant for conducting
the research described in the application. I would like to express my gratitude to
Tom and the IWT!
Of course, a phd student needs a good promotor. According to our university, a
good promotor provides the necessary infrastructure you need to do your research,
helps you to find the necessary funding, guides and supervises your research, mak-
ing sure that your plans are realistic, evaluates and gives feedback on what you
have done, puts your ideas in a broader context, pointing out links with other re-
search, suggests methods and approaches to tackle the questions you raise, brings
you in contact with other people or publications that are relevant for your work,
stimulates you to present and publish your work and will promote and support
your work towards the rest of the academic community. I can formally state that
Theo complies with all these characteristics and can consequently be classified as
a good promotor!
According to our university, however, the promotor cannot guarantee funding,
does not always have time to see you or help you, expects you to study and work
largely on your own, cannot do the research or write a paper for you, has many
other responsibilities and expects you to share the burden by assisting in some of
these non-research tasks. While Theo always found funding, he was indeed a busy
man who had many other responsibilities wearing ties and suspenders. Luckily,
Pascal Costanza and Patrick Heymans managed to bridge those moments and
acted as perfect co-promotors.
I wish to thank the other members of my reading committee, Prof. Serge
Demeyer and dr. Yves Vandewoude for their numerous suggestions which have
considerably improved the quality of this text. Further thanks go to the other
members of my jury for taking an interest in my work: Prof. Stéphane Ducasse,
Prof. Viviane Jonckers and Prof. Ann Nowé.
I thank Jorge Vallejos and Wolfgang De Meuter for the many discussions we had
when sharing the office, after the research presentations or when having some beers.
It are these discussions that form the corner stones of this dissertation. I thank
Andy Kellens, Johan Brichau and Kris Gybels for helping me resolve Smalltalk
and SOUL issues. A formal thank you to Andreas Classen for his valuable input
with respect to the formalisation of this work. I thank Laurent Schumacher for
his efforts in increasing the collaboration between the VUB and the FUNDP. I
also would like to thank my other colleagues at the Programming Technology Lab
for our co-operation over the years. Also many thanks to our secretaries, Lydie
Seghers, Brigitte Beyens and Simonne De Schrijver, for their support in helping
me deal with the university administration.
Special thanks also go out to Tom Mens and Kim Mens, whose dedication
and effort in the software evolution research field resulted in numerous scientific
symposia which form the basis of a research network in software evolution. It was
on those events that I got to know Patrick Heymans, Serge Demeyer, Stéphane
Ducasse and Yves Vandewoude. Without Kim and Tom, it would have been a lot
harder to establish this network.
I also want to thank my closest family and friends (in random order) Ellen,
Inge, Dimitri, Nele, Ellen, Herlinde, Kaat, Michael, Bart, Kris, Jan, Dave, Evert,
Eric, Olivier, Hilde, Stijn, Stefaan, Lies, Katrijn, Kenny, Peter, my colleague
football referees, the orcs from the Grombasha clan and the members of the scuba
diving club for constantly enquiring how this dissertation was progressing and for
occasionally providing me with a welcome distraction from my work.
Last but certainly not least, I wish to thank my parents for allowing me to
obtain a higher education and my wife Sabine for unconditionally supporting me.
I dedicate this work to the three of you.
Peter Ebraert
March 2009
Abstract
In het domein van software constructie wordt er meer en meer gebruik gemaakt
van een software modularisatie op basis van de functionaliteit. Zulke modular-
isatie groepeert de bouwstenen van een software applicatie volgens de functie die ze
samen implementeren. Het voordeel van die modularisatie in functionaliteitsmod-
ules, is dat ze beter aanleunt bij de specificate van de wensen van de gebruikers,
aangezien elke functionaliteitsmodule slechts één functionaliteit implementeert.
Het resultaat is dat software ontwikkelaars het gemakkelijker vinden om variaties
van de software te ontwerpen en te implementeren. Feature-oriented programming
(FOP) is het wetenschapsdomein dat deze trend onderzoekt.
De thesis van dit onderzoek is dat een software ontwikkelingsomgeving de
nodige ondersteuning moet bieden om modularisatie-informatie te extraheren va-
nuit de acties van de software ontwikkelaars, zodat de ontwikkelde software au-
tomatisch geherstructureerd kan worden in hersamenstelbare functionaliteitsmod-
ules.
Deze verhandeling stelt voor om functionaliteitsmodules te modeleren als tran-
sities die op een software systeem moeten toegepast worden om de functionaliteit
toe te voegen aan dat systeem. Dit model stemt overeen met de ontwikkelings-
acties, die ook transformaties zijn van software systemen. Meer concreet stellen
we een nieuwe benadering van FOP voor die bestaat uit drie fasen. Eerst moeten
de ontwikkelingsacties geëncapsuleerd worden in entiteiten. Vervolgens worden
deze entiteiten geklasseerd in verschillende verzamelingen die elk één function-
aliteit implementeren. Nadien kunnen deze modules dan samengevoegd worden
om software variaties te produceren met verschillende combinaties van function-
aliteiten. Het encapsuleren van ontwikkelingsacties kan gebeuren op drie manieren:
loggen, differentiatie of change-oriented programming (een nieuwe programmeer-
stijl die ontwikkelingsoperaties centraliseert). Er bestaan verschillende classifi-
catiestrategiëen, waarvan wij er drie bespreken: de manuele classificatie, de half-
automatische strategie die gebaseerd is op gemeenschappelijke karakteristieken en
de automatische classificatie op basis van annotaties. De hersamenstelling van de
modules gebeurt door de verzameling van ontwikkelingsacties te ordenen en toe te
passen en heeft als doel een variatie te produceren van het software systeem die
overeenstemt met de noden van de software gebruiker.
De naar voren geschoven concepten, benaderingen en werktuigen worden
gevalideerd door middel van een bewijs-van-concept implementatie die getest
viii Samenvatting
wordt op een tekst editor die ontwikkeld wordt in een standaard object-gerichte
manier en achteraf geconfigureerd wordt om versies te bekomen met verschillende
combinaties van functionaliteit.
Abstract v
Samenvatting vii
Table of contents ix
List of listings xv
1 Introduction 1
1.1 Software modularisation . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Object-oriented programming . . . . . . . . . . . . . . . . . 3
1.1.2 Component-based software engineering . . . . . . . . . . . . 4
1.1.3 Aspect-oriented software development . . . . . . . . . . . . 4
1.2 Modularisation for variation . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Feature-oriented programming . . . . . . . . . . . . . . . . 5
1.2.2 Change-oriented feature-oriented programming . . . . . . . 6
1.3 Bottom-up approach to feature-oriented programming . . . . . . . 8
1.4 Scope of the dissertation . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Structure of the dissertation . . . . . . . . . . . . . . . . . . . . . . 9
2 Background 13
2.1 Program variability . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Feature-oriented programming . . . . . . . . . . . . . . . . . . . . 16
2.2.1 FODA diagrams . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Generic feature-based composition . . . . . . . . . . . . . . 18
2.2.3 Mixin-layers . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.4 FeatureC++ . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.5 Lifting functions . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.6 AHEAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
x CONTENTS
2.2.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 First-class changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 VisualWorks: Change List . . . . . . . . . . . . . . . . . . . 31
2.3.3 SpyWare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.4 CatchUp! . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.5 Changeboxes . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.6 Change-impact analysis . . . . . . . . . . . . . . . . . . . . 34
2.3.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 Aspect-oriented software development . . . . . . . . . . . . . . . . 37
2.4.1 AspectJ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.2 EAOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.3 Logic meta programming . . . . . . . . . . . . . . . . . . . 41
2.4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Change-oriented programming 47
3.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.1 Evolution scenario . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Change as the central development action . . . . . . . . . . . . . . 52
3.3 Requirements for ChOP . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1 First-class changes . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.2 Change management . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Advantages of ChOP . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.1 Incremental change management . . . . . . . . . . . . . . . 58
3.4.2 Combination with other paradigms . . . . . . . . . . . . . . 59
3.5 Tool support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8 Validation 163
8.1 Proof-of-concept implementation . . . . . . . . . . . . . . . . . . . 163
8.1.1 VisualWorks for Smalltalk . . . . . . . . . . . . . . . . . . . 164
8.1.2 Model of first-class change objects . . . . . . . . . . . . . . 165
8.1.3 Obtaining changes . . . . . . . . . . . . . . . . . . . . . . . 166
8.1.4 Change classification . . . . . . . . . . . . . . . . . . . . . . 169
8.1.5 Feature composition . . . . . . . . . . . . . . . . . . . . . . 172
xii CONTENTS
10 Conclusions 201
10.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
10.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Bibliography 207
Biography 221
List of Figures
5.1 Source code (left) and change objects (right) of the Buffer . . . . 98
5.2 Source code of adding Restore (left), Logging (middle), Multiple
Restore (right) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3 Change objects of Restore (left), Logging (middle), Multiple
Restore (right) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4 Reconstruction of the change sets by means of the differentiation
technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.5 Change model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.6 Classification model . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.7 Manual classification . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.8 Semi-automatic classification . . . . . . . . . . . . . . . . . . . . . 110
5.9 Automatic classification . . . . . . . . . . . . . . . . . . . . . . . . 111
5.10 Change specification of the buffer example . . . . . . . . . . . . . . 113
7.1 Change specification of the buffer example (copy of Figure 5.10) . 141
7.2 Compositions based on first-class changes . . . . . . . . . . . . . . 142
7.3 A buffer with a functionality for maintaining statistics . . . . . . . 144
7.4 Extended buffer code after adding the statistics feature . . . . . . 145
7.5 Extended logging changes after adding the statistic code . . . . . . 146
7.6 Extended change model . . . . . . . . . . . . . . . . . . . . . . . . 153
7.7 SOUL core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.8 Refactorings as composite changes . . . . . . . . . . . . . . . . . . 161
Introduction
Three, the application of FOP to systems that were not developed with feature
modularisation in mind, is a tedious task. In order to restructure a legacy system
– that was not developed with the separation of functionality in mind – reengineer-
ing techniques are needed. Few popular software development environments for
object-oriented languages support automated techniques for reengineering to fea-
ture modularisation. Therefore, software engineers reengineer manually by brows-
ing the source code. Reengineering code into modularised features involves a huge
intellectual effort. Reading and understanding source code of object-oriented pro-
grams requires many context switches and a high concentration to keep a mental
record of the recovered software architecture: the interrelationships between the
architectural components and the rationale behind the software design.
The three observations reveal the need for an alternative approach to FOP
for making this simpler: We propose one that captures modularisation informa-
tion and uses that information to automatically restructure the application into
feature-oriented modules. Although the solution to this problem seems obvious –
let the developer record modularisation information that results from development
actions – this is not easily achieved. First, the lack of proper notation and mod-
els for development actions is an impediment to capture the information hidden
behind development actions. The prevalent notation and models for describing,
building and reasoning about development actions deal with change in an implicit
manner only. Second, the modularisation information extracted from development
actions should be complemented with domain knowledge from the developer in or-
der to be able to modularise the application correctly. Third, the intrusiveness of
the extraction of the modularisation information in the development environment
should be minimized. The thesis of this dissertation is that:
The main strength of AOSD and related approaches is that they all support a
multi-dimensional separation of concerns which overcomes the problems that the
tyranny of the dominant decomposition brings along. As such, those approaches
support a clean modularisation of all the programming concerns.
A fundamental problem with many approaches to software modularisation is
that they view systems from the perspective of producers, rather than consumers.
Producers tend to specify their systems in terms of software building blocks while
the consumers tend to specify requirements primarily in terms of functionality.
This mismatch complicates variability, since there is no direct mapping between a
composition of functionality and the software modules that implement that compo-
sition, even by using AOSD techniques. Recent research in software construction
increasingly reflects a common theme: the need to realign modules around features
rather than software building blocks [62].
First, they all start from a top-down approach to FOP, in which the software
system has to be designed upfront before the implementation is started. In such a
method, the designer has to foresee feature modularisation from the start, which is
not always possible in practice. This problem is even more apparent in a context of
a development method that stresses a highly iterative and incremental development
cycle. Such methodologies, such as agile software development [21], are often used
in order to support change during the different phases of software engineering.
As they encourage programmers to frequently inspect and adapt their software
products, they appear incompatible with a top-down to FOP.
Second, in order to apply one of the state-of-the-art approaches to FOP, a
specific development process is required that is different from the one exerted by
developers. In FOP, code has to be modularised in features: a specific kind of
software module. Since feature modularisation is not mainstream, most developers
have a development process that does not include modularisation of code into
features. Consequently, developers are obliged to alter their development process
for applying FOP. As most developers are reluctant to change their development
process, they avoid using the FOP programming technique, making it even less
mainstream.
Third, we find that all approaches lack fine-grained control of how features
are specified. None of them allow the specification of feature building blocks with
a granularity below method level. Next to that, none of them allow to express
the removal of building blocks from a base. Examples of where such control is
desirable include anti-features, the creation of a demo-application which consists
of all features but only to a certain extent, or the customisation of certain features
so that the software system copes with specific hardware requirements (e.g. limited
memory or computation power). An anti-feature is a functionality that a developer
will charge users not to include. E.g. while it may seem more difficult to produce a
trial version of a software system that includes publicity, the producers will charge
more for a version that does not include the publicity.
In some situations, these characteristics of the top-down approaches to FOP
are undesirable as they make it less easy to use. We propose a novel approach to
FOP, which is based on a programming style we call change-oriented programming.
In the following section, we briefly introduce this style and show how it can be used
to do bottom-up FOP. Afterwards we elaborate on this novel approach to FOP
and hint at how it does not suffer from the three above-mentioned inconveniences.
Thirdly, this approach is not intrusive in the development process and the de-
velopment environment that has to be used to do FOP. In the state-of-the-art
approaches to FOP, developers have to specify features as extensions or modifica-
tions of existing software modules. In ChOP, in stead of specifying the changes
for implementing the features, the developer, just implements the features in his
favorite programming language and environment. Behind the scenes, an exter-
nal tool instantiates the changes that correspond to the development actions and
subsequently groups them in change sets that implement the different features.
Moreover, by specifying features as sets of fine-grained change objects, features
are not only aware of the building blocks they consist of. They also know how
they can be added to a software composition (by applying the changes they consist
of). This ensures that a programmer does not have to deviate from his develop-
ment process in order to do FOP.
8 Introduction
Chapter 9: Future work There exist many lines of future research with respect
to this dissertation. In this chapter, we suggest a handfull. We start by sug-
gesting how the restrictions made to the research setting can be left out
and on how that would probably affect the results of this work. Other lines
1.5 Structure of the dissertation 11
of future work include the study of other classification strategies, other ap-
plication domains for first-class changes, extensions to the formalism, the
automatic deduction of intensional changes (which is similar to aspect min-
ing), the restructuring of feature modules and the enforcement of design
contracts.
Background
As the title of this thesis already suggests, our work is tightly coupled with the
research domain of program variation. Program variations are different versions of
one program which provide different combinations of functionality. Constructing
program variations is mostly a programming and programming language issue.
Program variability itself, however, is also touched upon in the research domain
of software evolution.
Starting with an overview of important literature, we summarize the key-
characteristics of program variation and discuss how it is achieved by the different
state of the art in programming styles. We subsequently discuss feature-oriented
programming (FOP) and explain why we consider that programming style in the
context of program variation. Afterwards, we evaluate the state-of-the-art ap-
proaches to FOP with respect to characteristics that are desired in a context of
program variation. This evaluation exposes deficiencies in the current state of the
art. We conclude with our own contributions in addressing these deficiencies.
The third part of this chapter briefly describes software evolution. As our
contributions are based on expressing features as sets of first-class changes, we
present an overview of the state of the art in first-class changes and discuss how
those approaches satisfy the desiderata that emerge from the context of program
variability. We observe that the changes of one feature module often affect the
software building blocks of many other software modules and that their application
is similar to the weaving process from aspect-oriented software development. These
observations show that change objects exhibit a flavor of crosscutting concerns
that is explicitly targeted by the research on aspect-oriented software development
(AOSD).
This chapter concludes with a presentation of the state of the art approaches
to AOSD. We compare those approaches to our approach in a context of program
variation and discuss the similarities and differences. In Chapter 7, we exploit
some of the concepts of the AOSD technology for introducing a new kind of change
object that uses quantification to denote its impact.
14 Background
approaches. This list presents the qualitative properties that we aim to find in
an approach to program variability. They are motivated by the goals of our work
(Chapter 1). Throughout this chapter, we will use these criteria to evaluate the
state-of-the-art approaches to FOP.
1. Granularity: The granularity provided to express modules establishes the
smallest/biggest unit of information that composes a module. Some ap-
proaches use native OOP entities, such as classes, instance variables, and
methods, as the building blocks of a module. In that case, many of them
establish the granularity at the level of methods. This implies that a module
would not be capable of introducing a modification within a method, but it
would be able to replace the entire method. The granularity establishes the
kind of specifications that a feature can declare. For instance, an approach
that sets its granularity at the level of methods is not capable of modeling
a modification within the body of a method. It will consequently have to
model such modification as a modification on the method level, which brings
along a loss of detail.
2. Supported operations: The purpose of this criterium is to evaluate if the ap-
proach allows one to express modules by additions, modifications and dele-
tions of program building blocks. Usually, the building blocks that compose
a feature module are described in term of additions and modifications. In
this dissertation, we also realise that deletion is a proper way for describing
certain features such as anti-features [40]. Anti-features are features that re-
move a functionality from the system. Sometimes, the functionality affected
by anti-features is scattered among several feature modules. Consequently, it
should be possible to express the deletion of functionality that might be scat-
tered over different feature modules for defining anti-features (and features
in general).
3. Dependency management: In some settings one module might depend on
other modules. Such dependency means that the former module can only
be included in a composition that includes the latter modules. While some
approaches do manage the dependencies between modules, others don’t. De-
pending on the purpose of the approach, dependencies are managed. In a
context of software variability, however, dependency management is desirable
as it can be used to validate compositions.
4. Customized deployment: In a composition sometimes a feature cannot be
deployed since some of its own building blocks have at least one unsatisfied
dependency. Some modularisation approaches support a customised deploy-
ment of modules, which tackles this situation. Doing so, those approaches
allow for compositions that otherwise would be invalid.
5. Specific language support: This criterium checks whether the modularisation
approach requires the addition of new constructs to a programming language
or whether it just uses the capabilities of a main-stream programming lan-
guage.
16 Background
rial explosion, the number of the instances that in fact can be instantiated is
a minor proportion of them. In addition to decomposition operators, a feature
diagram can be annotated by constraints in a textual language, such as proposi-
tional logic [9], that further restrain the set of allowed configurations. Given the
industrial-strength satisfiability solvers on which most feature diagram implemen-
tations are based, this should not be a problem in practice [37].
1. Granularity: This is a general purpose model that does allows one to express
product lines. In theory, one can use it to modularise methods or even code
statements. The idea behind the FODA diagrams, however, is to use the
diagrams to modularise on a more coarse-grained level.
Buffer
Problem
Logging Restore Space Solution
Space
Mul. Res Bas. Res
logit()
logit()
int get()
void set(int x)
back = buf
logit()
void logit() restore()
int back = 0
int buf = 0
Buffer
5. Specific language support: This model does not require any specific language
support. It uses feature diagrams and dependency graphs to describe depen-
dencies between the different software artifacts.
Notation of Figure 2.2: The dashed arrows denote the mapping between
features (from the problem space) and their building blocks (in the solution
space). The Logging feature for instance, maps to the addition of several logit()
statements and an addition of the logit() method. The full arrows denote the
dependencies in the solution domain. The logit() method for instance, depends
on the Buf f er class (that contains the method). Those dependencies can all be
used to validate compositions declared within the problem domain.
Now we elaborated on two FOP approaches that target the problem space,
and one that provides a mapping between the problem and solution space, we dive
into the state of the art to FOP that targets the solution space. We start by an
approach that targets the modularisation of software building blocks by means
of code refinements. It is of particular interest for us, as it provides a basis for
feature-oriented software development in a setting of object-oriented programming.
2.2.3 Mixin-layers
The approach proposed by Smaragdakis et al. [100] uses a collaboration-based
technique for examining large-scale refinements. A refinement adds units of func-
tionality to a software system. It can affect many implementation entities such
20 Background
Figure 2.3: Collaboration diagram of the graph traversal application (from [49])
2.2.4 FeatureC++
Feature C++ is a language extension – proposed by Apel et al. in [4] – to support
FOP and AOP. FeatureC++ implements features by means of mixin-layers. Apel
et al. define a mixin-layer as a set of mixins that together implement a crosscutting
concern. Mixins consist of constants or refinements. Constants are new software
entities and refinements are increments on existing ones. In FeatureC++, mixin-
layers are represented as file system directories. Mixins found inside a directory
collaborate in the mixin-layer. FeatureC++ improves FOP in two ways: Firstly
it enhances refinements with multiple inheritance to introduce new behavior to a
class by making the class inherit from multiple classes; Secondly it improves re-
finements to produce generic transformations into classes. Using class and method
templates, refinements can be parameterized improving variability. FeatureC++
addresses FOP issues related with crosscutting modularity by means of AOP. The
following three concepts are introduced to that extent: multi mixins, aspect mixin
layers and aspectual mixins.
Multi mixins. Traditionally, a mixin is able to modify only one mixin. This
latter mixin is called the parent mixin. A multi mixin is a mixin able to refine a
whole set of parent mixins. This is accomplished by introducing a wildcard % in
the class or method name where the mixin is specified.
Aspect mixin-layers. The basic idea boils down to embed aspects into a mixin-
layer. A mixin-layer contains a set of mixins and a set of aspects, allowing mix-
ins to implement static/dynamic, homogeneus/heterogeneus and hierarchy/non-
hierarchy-conform crosscutting behavior.
Aspectual mixins. These provide mixins with the power of AOSD. Aspectual
mixins can contain pointcuts and pieces of advice, as well as common refinements
and constants. We refer the reader to Section 2.4 for a detailed explanation of those
concepts. The analysis of FeatureC++ with our criteria produced the following
results:
1. Granularity: The level of granularity provided by mixin-layers allows one
to manipulate source code at the level of a statement. Although a single
2.2 Feature-oriented programming 23
Figure 2.5 was taken from [91]. It shows four features (F 1, F 2, F 3 and F 4)
and three compositions of these features (F 1 - F 3, F 1 - F 2 - F 3 and F 1 -
F 3 - F 4). To accomplish these compositions, five lifting functions are provided
that handle the interactions between two features. In this example, they are:
(F 1,F 2), (F 1,F 3), (F 2,F 3), (F 2,F 4) and (F 1,F 4).
This approach requires intensive human intervention since lifters need to be
written for every pair of features which might be composed. Although it increases
the accuracy of the resulting composition, the extra work required to construct a
lifting functions to address every possible feature interaction seems awkward. With
respect to our criteria, the lifting functions approach is summarised as follows:
1. Granularity: In this model the smallest entity that a feature can control is
a statement. However, the ways in which a feature can add a statement to
a method is very restricted. It is addressed by overriding the method with a
new version and calling the old version of the method at a certain point. In
general this model modifies entities by adding classes, methods and instance
variables.
2. Supported operations: This model expresses features using the same building
blocks as the OOP languages. Moreover, by overriding methods, it allows
for the introduction of new behavior. It does not allow for the modification
of a specific statement or deletion of any entity.
base
B b modules
H ∂b / ∂h h derivative
module
5. Specific language support: This model extends Java by adding the notion
of a feature. A feature introduces a lifting function which addresses the
interaction of features.
2.2.6 AHEAD
Algebraic hierarchical equations for application design (AHEAD) is a unified for-
mulation for FOP that integrates step-wise development, generative programming,
and algebras [7, 10, 105]. This is based on step-wise development which proposes
that a complex program can be built from a simple program (called a base pro-
gram) by incrementally adding features. AHEAD models product-lines with a
simple algebraic structure. A base module contains the definition of classes, mem-
bers, and methods while a derivative module extends programs adding fragments
of methods, classes, and packages. Thus, a feature is modeled by a composition
of one base module and a set of derivative modules. Figure 2.6 (which was based
on a figure of [69]) shows two features B and H. B consists of a base module b and
feature H consists of a base module h and a derivative module ∂b/∂h which extends
the base module b.
GenVoca is a method for creating application families and architecturally ex-
tensible software by expressing programs as sets of equations. It provides the
same information that can be described by a feature diagram but adding cross-
tree relations for denoting relations between features that are not expressed by
the diagram. Since it provides a grammar, it can be used by applications in an
automatic way.
The function • weaves a derivative into a base module. An introduction sum +
is a binary operation that aggregates base modules by a disjoint set union. Thus,
an application composed by features B and H is expressed by:
class Buffer { 1
i n t buf = 0 ; 2
int get ( ) { 3
return buf ; 4
} 5
void s e t ( i n t x ) { 6
buf = x ; 7
} 8
} 9
Listing 2.1: AHEAD Base feature
r e f i n e s class Buffer { 1
i n t back = 0 ; 2
void s e t ( i n t x ) { 3
back = buf ; 4
buf = x ; 5
} 6
void r e s t o r e ( ) { 7
buf = back ; 8
} 9
} 10
Listing 2.2: AHEAD Restore feature
r e f i n e s class Buffer { 1
void l o g i t ( ) { 2
} 5
int s e t ( int x ){ 6
logit (); 7
super . s e t ( x ) ; 8
} 9
void g e t ( ) { 10
logit (); 11
super . g e t ( ) ; 12
} 13
void r e s t o r e ( ) { 14
logit (); 15
super . r e s t o r e ( ) ; 16
} 17
} 18
Listing 2.3: AHEAD Logging feature
restructuring the features in such a way that the feature involved in the interaction
is put in a separate feature. This solution allows one to produce an application with
Base and Logging functionality, but has some limitations: Firstly decoupling of
interactions requires a deep understanding of the feature implementation which in
realistic cases could be difficult to address, secondly a feature can have interactions
with many features at the same time.
encapsulating that part into a new one the adaptation must be addressed
with human intervention. This makes it less useful for using in software
product-lines.
2.2.7 Discussion
Table 2.2.7 summarizes the analysis of all the presented approaches with respect
to the provided criteria. It shows that, at the time of writing and to the best of
our knowledge, there is no approach that fulfills all criteria. Although, most of the
approaches support operations such as addition and a specific kind of modification,
none of them allow for deletion. Note that this might be desirable when adding an
anti-feature to a system that is already modularised into feature modules. Since
the anti-feature might require the deletion of building blocks that were introduced
by different feature modules, it must be able to express the deletion of building
blocks, rather than the “non inclusion” of certain feature modules in a composition.
We conclude that a new approach to FOP should be established that does address
the delete operation.
Next to that, most of approaches set the granularity of the supported oper-
ations at statement level, but only support it in a restricted way (denoted by
“Statement–” in Table 2.2.7). For instance, in AHEAD a programmer is not al-
lowed to insert a statement between two statements of an existing method. With
respect to the dependency management, we may conclude that the vast majority
of the approaches to FOP, do provide a mechanism for maintaining dependencies
between the feature modules. The two final criteria, however, are not covered in an
adequate way, as only FeatureC++ supports a customized deployment of feature
modules, and none of the discussed approaches do not require additional language
support.
After inspecting the state-of-the-art in feature-oriented programming we ac-
knowledge that all approaches we encoutered intend to encapsulate features in
separated modules, but that most of the approaches do it in different ways. There
is an awareness that features are not sufficiently described by object-oriented lan-
guage constructs – classes, methods, etc. That is why all approaches that target
the solution space make language extensions. They need new means for express-
ing the concepts they introduce. It is difficult to imagine writing a program in
a feature-oriented way where each feature is perfectly enclosed in a class. We
realized a feature normally impacts many software entities at a time. A popular
technique that addresses this issue is a refinement which is able to introduce mod-
ifications to previous language entities. However, refinements lack control, since
they cannot describe particular modifications of a software entity. For instance,
refinements do not allow for the deletion of a class, method or statement. They
only allow for a particular kind of modification of methods based on calling the
original method before or after certain statements of the new one.
2.2 Feature-oriented programming 29
2.3.1 Principles
A change is a record that captures the information about an adaptation of a soft-
ware system. A change can be generated by monitoring the developer producing
a software system. Such change can be encapsulated in a first-class entity, that
can afterwards be used as a value in programs without restriction. Some charac-
teristics of a first-class object are: being storable in variables, having an intrinsic
identity, being passable as a parameter, being returnable as the result, being in-
stantiatable at runtime, being printable, being readable and being transmissible
among distributed processes [18]. Approaches modeling changes as first-class en-
tities exploit these properties to ease the manipulation of changes and the storage
of information related to them. A field where this kind of model of changes would
be useful is Software Generators [8, 53, 5, 6]. Software generators are programs
that build other programs.
In this chapter, we present the state-of-the-art approaches we found to model
changes as first-class objects. We developed a set of criteria with the aim of an-
alyzing and situating these approaches. These criteria emerge from the context
in which our model of first-class changes is used. In a context of change-oriented
feature-oriented programming, changes must be able to capture information about
adding, removing or modifying the building blocks of a software system at the most
fine-grained level possible. As we have seen in the related work on feature-oriented
programming, it is also important to maintain dependencies in and between the
problem and solution spaces in order to support the automatic validation of pro-
gram variations. In order to be useable in our approach, the model must conse-
quently be capable of expressing development operations (addition, deletion and
modification) on software building blocks (down to the level of granularity of code
statements) while maintaining the dependencies amongst those changes.
2.3.3 SpyWare
Robbes and Lanza [93] propose a change-based approach to software evolution. In
their approach, the interactive development environment (IDE) is instrumented
with hooks that enable an IDE plug-in to monitor the developer and to create first-
class entities that represent the actions taken by the developer. In their approach,
the first-class change entities are objects that capture the history of a system in
an incremental way. They are able to reproduce the software which they represent
32 Background
the history of. When executed, they yield a representation of the program at a
certain point in time. They contain additional information interesting for evolution
researchers, such as when and who performed the change operation.
The main advantage of this approach in comparison to Change List is that it
supports capturing development actions on the level of granularity of code state-
ments. We study this approach as we require that level of granularity in our
approach to feature-oriented programming.
As a proof-of-concept they developed SpyWare. Spyware is a Squeak1 imple-
mentation which monitors developer activity by using event handlers located at
IDE hooks and generates change operations – as first-class entities – from them.
Doing so, it is able to provide graphical information for analyzing the evolution of
a program.
2. Granularity: Spyware is a tool that allows for capturing the changes that a
developer produces down to the level of statements.
2.3.4 CatchUp!
Henkel and Diwan [47] propose a model for capturing the changes that a devel-
oper produces while evolving software libraries. These changes can afterwards be
replayed on the software libraries on the client’s side reacting accordingly to the
corresponding library evolution. In [75] the authors claim that most changes that
a developer produces in the evolution of a library are refactorings. Moreover, they
state that any change to a software program that preserves behavior can be under-
stood as a refactoring. Using IDE hooks to catch the refactorings introduced to a
library, they store that information within changes modeled as first-class entities.
The process starts with the recording phase which occurs when the developer
is evolving the library. He introduces refactorings that produce changes which are
logged in an incremental way. Then the developer can annotate the changes with
semantic information. For instance, a change specifying it has been produced for
Renaming to avoid name clashes. That is particularly interesting with respect
to our approach, as we require an IDE that records such fine-grained modulari-
sation information for validating our thesis. The outcome of this phase is a new
version of the library and a file containing a list with all executed changes. In
case a refactoring does not affect client code, the change which represents that
refactoring can be removed from the list of changes. In order to integrate the new
1 See http://www.squeak.org/ for more information about Squeak
2.3 First-class changes 33
library version into client code, the list of changes needs to be replayed on the
client code.
CatchUp! is presented as a proof-of-concept. CatchUp! is an Eclipse plug-in
written in Java. It provides a means for recording library refactorings which are
stored as a list of first-class change objects. It allows one to replay the list of
changes to a client code updating it for using a new library version.
2.3.5 Changeboxes
Denker et al. propose Changeboxes [29] as a general-purpose mechanism that en-
capsulates change as first-class entities in a running software system. Figure 2.7
was taken from [29] and shows how Changeboxes are modeled. A ChangeBox
may specify three kinds of changes: definition, renaming or deletion. Elements
are the target of a ChangeSpecification and model classes, methods or fields.
A ChangeSpecification of a ChangeBox defines how one version of an Element
may be transformed into another version of that Element.
In the context of our research, the most interesting property of the Changeboxes
approach is that it has a change model in which the dependencies between change
objects are maintained. As those dependencies provide a source of fine-grained
modularisation information, we are interested in Changebox’ model of changes.
Changeboxes capture the incremental evolution of a software system. They can
be linked to ancestors ChangeBoxes, that represent prior ChangeBoxes to the
same system. A MergeStrategy defines how two ChangeBoxes can be merged. A
ChangeBox is defined within a Scope which allows one to execute multiple versions
of a same entity at a time. The system is changed by introducing new Changeboxes
which encapsulate a change specification. CompiledMethod and Class represent
specific versions of classes and methods, that later can be used by the virtual
machine to instantiate new objects.
A Changebox is an immutable entity that defines a snapshot of a system by en-
capsulating a set of change specifications, specifying a set of ancestor Changeboxes
which these changes apply to and by providing a scope for dynamic execution. A
Smalltalk implementation of Changeboxes was successfully evaluated [29]. It il-
lustrates that bug fixes, new features and refactorings can be safely incorporated
into a running system without impacting active sessions.
34 Background
1. Supported operations: This model allows one to define, rename and delete
software elements.
2. Granularity: The granularity of this model goes down to the level of fields,
methods and classes, as we can see in the model diagram of Figure 2.7.
by means of dynamic analysis – as we explain below. This allows for the recovery
of more accurate information [83] with respect to the dependencies between change
objects.
Type Description
AC Add an empty class
DC Delete an empty class
AM Add an empty method
DM Delete an empty method
CM Change body of method
LC Change Virtual method lookup
AF Add a field
DF Delete a field
2.3.7 Discussion
The list of related work shows many approaches which successfully modeled
changes as first-class entities. All acknowledge that there is a necessity for cap-
turing the operations that are applied when a program is written. Doing so,
36 Background
Table 2.3 summarizes the analysis of each approach presented in this chapter
based on the criteria we established for a model of first-class changes. In gen-
eral, most approaches provide a fine granularity at the level of a statement. They
also provide means to characterize changes as additions, modifications and dele-
tions. However, only Change-impact analysis and Changeboxes provide an explicit
dependency management model. To the best of our knowledge, we do not find
any approach to match all the criteria. Consequently, we choose to develop our
own model of first-class changes in which we support the expression of additions,
modifications and deletions at the statement level and in which we manage the
dependencies between the changes. This model is the subject of Chapter 4.
We observe that, in order to add one functionality to a software application, of-
ten changes have to be applied to different object-oriented modules. For instance,
when a logging functionality is added to an object-oriented application, changes
that add an invocation to a dedicated log method have to be applied to many
methods that are scattered over the entire application. This observation shows
that the changes of one feature often crosscut the standard object-oriented mod-
2.4 Aspect-oriented software development 37
Point Line
getX getX
2 *
getY getY
setX: setX:
DisplayUpdating
setY: setY:
Appliation Code
Aspect Tangled
Weaver Application Code
Aspect 1 Aspect 2
Aspect 3
Figure 2.9: Aspect weaving: composing an application using aspects and base
program.
2.4.1 AspectJ
Currently AspectJ [59] is the most widely used AOP language. AspectJ is an
aspect-oriented extension to Java that enables the modular implementation of
a wide range of crosscutting concerns. Each of those crosscutting concerns is
modularized by an aspect.
AspectJ adds to Java just one new concept, a join point – and that’s really
just a name for an existing Java concept (an event that occurs at runtime). It
2.4 Aspect-oriented software development 39
AspectJ
Advice
advice body
pointcut
joinpoint
Java Program
also adds to a few new constructs: point cuts, advices, inter-type declarations and
aspects. Join points state the points in the base program where we want aspects
to take control. They can be declared on operations like a method call, a class
boundary, a method execution, an access or modification of member variable,
exception handlers or on static and dynamic initialization.
Many join points can be assembled into a set of joint points – point cuts. To
each of the point cuts, we then attach a piece of advice, which states the actions to
take when one of the point cuts is reached. The body of the advice is specified in
ordinary Java code. The inter-type declarations allow the programmer to modify a
program’s static structure, namely, the members of its classes and the relationship
between classes. Aspects are the unit of modularity for crosscutting concerns.
They behave somewhat like Java classes, but may also include point cuts, advice
and inter-type declarations.
In AspectJ, aspect composition – or weaving – is done at load-time. Whenever a
class is loaded into the VM memory, its byte is first adapted in order to incorporate
the applicable pieces of advice. This results in modified byte code that contains
both the class behaviour and the pieces of advice that impact on that behaviour.
This modified byte code is actually loaded into the memory of the Jave VM. At
runtime, when at a certain point in the execution, a pointcut holds, the attached
piece of advice is executed, as we can see in Figure 2.10.
The base code and the aspect code must be written using an external Java
editor. The AspectJ development tools for Eclipse (AJDT) is an editor that is
written as a plugin for the Eclipse IDE and which supports the developer in doing
AOSD in AspectJ. Instantiations of the AspectJ model where conceived for many
other programming languages. AspectR 2 , AspectC 3 , AspectC++ [42], AspectS 4
and AspectS 5 are AspectJ-like implementations of AOP for respectively Ruby, C,
2 AspectR: http://aspectr.sourceforge.net/
3 AspectC: http://www.cs.ubc.ca/labs/spl/projects/aspectc.html
4 http://common-lisp.net/project/aspectl/
5 AspectS: http://www.prakinf.tu-ilmenau.de/ hirsch/Projects
40 Background
2.4.2 EAOP
Event-based aspect-oriented programming (EAOP) [30] is another AOSD ap-
proach. In EAOP, a global monitor keeps track of all base-level events. That
way, the monitor is always able to execute something extra when a certain event –
operation – occurred. In such approach, it is also very easy to keep track of control
flows because all information is centralized. The monitor can in that way be seen
as one big meta object which is responsible for managing the execution of the base
program and the aspects. An aspect can be seen as an event transformer. In fact
– in EAOP – an aspect is a Java object which takes an event as a parameter,
performs some computation or action (which may modify the argument event),
and waits for the next event.
In [30], the authors describe how a developer can resolve aspect composition
conflicts. This is done using a three phase model. The first step is to write all
the base and aspect code. The second phase holds the conflict detection. The last
phase includes the conflict resolution. The second and third phase can be iterated
on, till composition rules are specified that handle all composition conflicts.
A conflict occurs when two (or more) aspects interact with each other, i.e.
if at least one of their crosscuts match the same join points. But in fact, this
definition is too strong, because it is possible that there is no conflict at all, and
that the aspects could be executed one after another without affecting each other.
Therefore the authors distinguish between two kinds of dependence: strong and
weak independence. Two aspects are said to be strongly independent if none
of their crosscuts have common join points. Two aspects are said to be weakly
independent if they have crosscuts with common join points but if the aspects
6 Apostle: http://www.cs.ubc.ca/labs/spl/projects/apostle/
2.4 Aspect-oriented software development 41
Composition Semantics
A1 seq A2 When both aspects have a common cross point, first
A1 ’s actions and then A2 ’s actions will be applied.
A1 fst A2 Propagates the execution control to A1 , and, if and only if A1
did not detect a crosscut, the execution control is given to A2 .
A1 any A2 Propagates the execution control to A1 and A2
in an arbitrary order.
A1 cond A2 Propagates the execution control to A1 , and, if and only if
A1 detects a crosscut, the event is forwarded to A2 .
class Buffer { 1
i n t buf = 0 ; 2
int get ( ) { 3
return buf ; 4
} 5
void s e t ( i n t x ) { 6
buf = x ; 7
} 8
} 9
Listing 2.4: AOSD Base feature
structure of the concepts in the source code which the pointcut relies on as well as
to render the causal link between these concepts and the implementation structure
explicit and verifiable. The mechanism allows for the expression of pointcuts in
terms of a conceptual model: a first-class reification of the different concepts in the
source code which a pointcut relies on. As such, design contracts can be imposed
on the conceptual model, aiding in keeping this conceptual model synchronised
with the source code.
2.4.4 Discussion
Of course there are many more implementations and technologies related to AOSD,
but it is not our purpose to list all implementations, but just to give the reader an
idea of the current success of AOSD and on its integration in different programming
languages. Precisely that will be the challenge for all AOSD languages despite the
fact that its solutions are likely to be platform specific. Figuring out how best
to build usable and extensible tools is a problem that any serious programming
language project faces – it is impossible to judge the usefulness of a programming
language in the absence of real developers using it, and it is impossible to convince
real developers to use a language without high quality tools [52].
AOSD introduces the concept of a pointcut as way to match the places of
program code where the concern occurs. It also introduces pieces of advice as an
artifact that specifies code to introduce behavior at the places matched by the
pointcut. Advices are woven into the program at the point of the pointcut. Doing
so, a crosscutting concern can be stored in a modular way making the program’s
code easier to understand and to maintain.
Listings 2.4 and 2.5 show an example of a Buffer, which is implemented with
AspectJ [59]. It introduces a Buffer class that specifies a buf instance variable
and methods set and get, and an aspect that adds a back instance variable,
a method restore to restore the value of buf and that introduces a statement
before the execution of method set. Note that the advise corresponds to the set
of changes that needs to be applied in order to add the aspect to the base code
and that the pointcut refers to where those changes have to be applied.
2.4 Aspect-oriented software development 43
public a s p e c t R e s t o r e { 1
i n t back = 0 ; 2
void r e s t o r e ( ) { 3
buf = back ; 4
} 5
public p o i n t c u t s e t ( i n t x ) : t a r g e t ( x ) 6
&& e x e c u t i o n ( void B u f f e r . s e t ( ∗ ) ) ; 7
void b e f o r e ( i n t x ) ; s e t ( x ) { 8
back = buf ; 9
} 10
} 11
Listing 2.5: AOSD Restore feature
2.5 Conclusions
We started this chapter by explaining that the context of this dissertation is pro-
gram variation. We advocate feature-oriented programming (FOP) as the right
development technique for modularising software in recomposable modules as it
aims at modularising software systems in feature modules that each implement a
different functionality [91]. While features refer to entities within the solution do-
main (software capabilities), functionalities refer to entities in the problem domain
(software requirements).
We elaborate on what properties we require from approaches in order to sup-
port program variability. From our analysis of related work in previous sections,
three important deficiencies were found in current systems for providing program
variability:
Change-oriented
programming
The thesis of this dissertation is that the software development environment should
provide support for recording modularisation information that results from devel-
opment actions, so that software can be automatically restructured into recom-
posable feature modules. In order to facilitate the recording of modularisation
information, we propose a new style of computer programming, a new program-
ming paradigm: change-oriented programming (ChOP).
ChOP targets software evolution and centralises changes as the main entities in
the software development and evolution process. In ChOP, software programs are
developed by applying changes and can afterwards be evolved in the same way:
by applying changes to them. Some examples of developing code in a change-
oriented way can be found in most interactive development environments (IDE):
the creation of a class through interactive dialogs or the modification of the code
by means of an automated refactoring. ChOP goes further, however, as it requires
all building blocks to be created, modified and deleted in a change-oriented way
(e.g. adding a method to a class, removing a statement from a method, etc).
3.1 Context
Some interactive development environments (IDEs) include a tool to manage the
changes applied to a software system. VisualWorks for Smalltalk, for instance,
contains ChangeList [51, 109]. Using this tool, programmers can inspect, compare,
edit and merge changes applied to classes or methods. Each Smalltalk image1 holds
one single change list which records all the performed changes on that image.
Hence the user may recover from a crash by backtracking to the most recent non-
erroneous state of the image and reapplying changes listed by the ChangeList
tool.
Throughout this section, we consider the ChangeList tool as a case to demon-
strate the need for change-oriented programming. In ChangeList, changes are
modelled as standard Smalltalk objects and as such they can be referenced, queried
and passed along. Every time a system is modified, the Smalltalk IDE logs this
modification by creating a change object for it, linking this object to the project,
and adding the object to the list handled by ChangeList.
Change objects of the ChangeList tool properly satisfy the notion of first-
class changes for software evolution defined by Robes and Lanza [93]. According
to them, change objects provide more accurate information about the history
of a program than file-based and snapshot-based versioning change management
systems. Timestamps or instance, are more precise as they are not reduced to
commit times. Change objects also better represent the incremental and entity-
based way in which the evolution of a program occurs (changes are expressed in
terms of system entities and not over text). However, change objects still suffer
from a number of shortcomings which we illustrate in the following scenario.
application state (objects) in a single memory region called the image. Images can be saved and
loaded by the Smalltalk environment as a snapshot of the current code and state of a program.
3.1 Context 49
their name in the chat room whereas the guests cannot: Accordingly, the username
attribute of User class is moved to the RegisteredUser class. Figure 3.2 shows
this first feature added to the application.
RegisteredUser Guest
username
^ username name() name() ^ 'guest'
To ensure user privacy, the second developer adds two methods to the User
class, encrypt and decrypt, which are called from the send and receive methods
respectively. Figure 3.3 shows this second feature added to the application.
After implementing these two new features in the application, the developers
merge their changes, resulting in the class diagram showed in Figure 3.4.
Listing 3.1 illustrates how these three steps are registered by the ChangeList
tool in Smalltalk. Each line in this list corresponds to a change required for the
implementation and merging of the two new features described above. Each of
these changes is stored in a change object. We observe a series of problems in this
representation of the evolution of the chat application:
Restricted level of granularity The entities contained in the change list are
restricted to a granularity of classes and methods. Additions or removals of
attributes or statements within method bodies are not captured by dedicated
change objects. The changes within a method body result in a change that
redefines the complete method. This is what happens, for instance, with
the send: method which is first defined and then modified. As changes
within methods are not logged by dedicated changes on the statement level,
50 Change-oriented programming
Created package ChatApp 1
d e f i n e User 2
d o I t User o r g a n i s a t i o n addCategory :# m e s s a g i n g 3
d e f i n e User 5
d e f i n e User 6
d o I t User o r g a n i s a t i o n addCategory :# a c c e s s i n g 8
d e f i n e Chatroom 10
d e f i n e Chatroom 11
d o I t Chatroom o r g a n i s a t i o n addCategory :# m e s s a g i n g 12
d o i t Chatroom o r g a n i s a t i o n addCataegory :# r e g i s t e r i n g 14
Chatroom r e g i s t e r : ( change ) 15
Chatroom u n r e g i s t e r : ( change ) 16
17
d e f i n e Guest 18
d o I t Guest o r g a n i s a t i o n addCategory :# m e s s a g i n g 19
define RegisteredUser 21
R e g i s t e r e d U s e r name ( change ) 22
d e f i n e User 24
define RegisteredUser 25
26
d o I t User o r g a n i s a t i o n addCategory :# e n c r y p t i o n 27
User e n c r y p t : ( change ) 28
User d e c r y p t : ( change ) 29
Listing 3.1: Evolution scenario user privacy: change list by ChangeList
3.1 Context 51
these two different kinds of changes result in two occurrences of User send:
(change) on lines 7 and 30.
Term overloading The definition of a change object is in some cases ad hoc and
inconsistent. The same kind of Smalltalk change object can represent several
kinds of modifications. For instance, a ClassDefinitionChange object is
required to add a class to the program (for example to add the User class)
but also to add or remove attributes (for example to add the username
attribute in the User class). As a result of this term overloading, the change
define User appears four times in the change list (lines 2, 5, 6 and 24).
This hinders the understanding of the changes in the list.
Lack of high-level changes The ChangeList tool does not allow the explicit
monitoring of high-level changes which better represent the intention of the
developers. In this evolution scenario, the two intentions of the developers
(introducing user kinds on lines 18-25 and ensuring user privacy on lines 27-
31) are concatenated in the final change list. This may become a problem if
52 Change-oriented programming
the developers need to change the way in which the two features are merged,
for instance, to only enable registered users to benefit from encrypted com-
munication (see Figure 3.5). The developers have to manually recompose
their implementations from the change list.
No exploration facilities The three shortcomings described above illustrate
how difficult the change management can become. After making several
modifications to a program, the change list can contain large amounts of
change objects. In such a case, the exploration of the change lists is cum-
bersome and error-prone.
^f −1 (m)
^m
to that package. The IDE then provides the necessary dialogs to interact with
the programmer in order to obtain all parameters of the class. Finally, it is the
IDE that produces the source code of the newly created class and that inserts this
code in the correct locations. Another example is the refactoring2 [17] support of
the VisualWorks IDE. When a programmer decides to pull up a method (move it
to the superclass), he right-clicks the method and selects the ’pull-up’ menu item
after which the IDE performs the actual modifications to the source code in order
to execute the method pull up.
The idea of ChOP is that the entire software system is developed as illustrated
above: by making the IDE execute changes. It is clear that the IDE should
support all possible kinds of changes to source code and provide the dialogs to
collect the information it needs to perform them. Next to that, the evolution
scenario of Section 3.1.1 revealed a need to support user-defined changes. The
following section elaborates more on those and other requirements for ChOP.
Fine-grained changes
The different kinds of changes in the ChangeList tool are structured in a hierarchy
of change classes. This hierarchy eases extending the set of changes, stimulates
reuse and improves maintainability. We support all these principles and therefore
propose to preserve the idea of structuring the types of changes in a hierarchy in
which subtypes inherit common functionality from their super types.
2 In software engineering, refactoring source code means improving it without changing its
The first-class changes of the ChangeList tool express changes about packages,
classes, attributes or methods. The statements of a method body are not explicitly
considered as a subject of change. The decomposition of a method body, however,
always reveals more detailed information that can be used to study the evolution of
the concerned program. The fact that a method statement includes an invocation
of another method, implies that there is a relationship between both methods, and
that the former method could be affected when the latter is changed.
Another example of such a restriction of granularity can be found in the modifi-
cation of attributes. Changes to method parameters are also not explicitly modeled
by the the ChangeList tool. Assume a method call that has a complex expression
as an argument. This expression can contain method invocations which reveal
links between the caller and the callee.
In our model, we propose to introduce dedicated change objects for all possible
associations between program entities. An AddInvocation change, for instance,
describes the addition of an invocation of a specific method and maintains a ref-
erence to the method it invokes. Keeping this reference avoids the need to recover
it later, which is even not always possible due to programming language features
such as polymorphism, dynamic binding or especially behavioral and structural
reflective capabilities [67].
Enabling changes at this level of granularity allows the change list to contain
information which can be used to recover the invocations of a method.
Composable changes
Change
...
... changes
AtomicChange CompositeChange
... ...
... ...
High-level Refactorings
Hierarchy of Atomic changes
Change Classes
Atomic changes are operations that directly manipulate the abstract syntax
tree of a particular program. These operations consist of adding or removing an
entity (for instance a class) as well as changing the properties of an entity (for
instance the name of a class). Like all changes, atomic change operations are
captured in first-class entities that are (re)applicable. By reapplying the changes
of the complete change list, a developer can reproduce each development stage a
program went through during its evolution.
Composite changes consist of multiple changes which can in turn be composite
or atomic changes and which are all carried out whenever the composite change
is executed. They group some changes in a composition, which can be more
expressive than the atomic changes on their own. A ChangeMethod, for instance,
could be expressed by a composition of a RemoveMethod and an AddMethod change.
In some cases, if one of them is undone, the other should be undone as well.
The information that represents this relationship is captured in the ChangeMethod
change that surrounds both the RemoveMethod and an AddMethod change.
Composing changes also improves comprehension of the change list. A system
history consisting of only atomic operations leads to an enormous and poorly
organized amount of information. Therefore all change operations are composable:
They can be grouped into higher-level operations with a more abstract meaning.
A final application of composite changes can be found in domain-specific
changes. Imagine that we envision the addition of lots of new kinds of users
to our Chat application. In that case, it probably would be better to define a ded-
icated change type AddUserClass, which in its turn adds a subclass to the User
hierarchy and add methods for instanciating that new class. As such change types
are targeting a specific a specific problem domain, we call them domain-specific.
By means of such domain-specific changes, the level of abstraction of changes is
raised, which leads to better readable (and more understandable) change lists.
Dependent changes
In our model, every change has a set of preconditions that should be satisfied
before a change is applied. Such preconditions are related to system invariants
imposed by the programming language (usually defined by the meta-model of the
language). For example, methods can only be added to existing classes. Pre-
conditions enable expressing dependency relationships between changes. In the
scenario of Section 3.1.1, for instance, the change that adds the method name to
the RegisteredUser class depends on the change that added the RegisteredUser
class to the system, as the latter is the creational change for the subject of the
former.
There are many kinds of dependencies between changes. In Section 4.4, we
classify the dependencies based on their origin. An example is the creational
dependency.
A change is always applied to a building block, which we refer to as the subject
of change. Creational changes are changes which have as subject a new entity that
they produce. A change c1 is said to creationally depend on a change c2 if that is
the creational change of the subject of c1
56 Change-oriented programming
Change t h e name o f method " name " i n c l a s s R e g i s t e r e d U s e r 1
Change t h e name o f method " name " i n c l a s s Guest t o " username " 3
Listing 3.2: Change method body: extension
Change t h e name o f method name i n a l l s u b c l a s s e s o f t h e c l a s s 1
Listing 3.3: Change method body: intension
Intensional changes
from evolving software. The following sections subsequently present how the IDE
should support the production, the management and the use of changes.
Verification of pre-conditions
A change has pre-conditions which must hold before it can be executed. Those
pre-conditions can be of a semantic or a structural kind and are introduced by
the meta-model of the concerned programming language. In a class-based object-
oriented programming language, for instance, a method can only be added to a
class, if that class already exists. The IDE should enforce that the pre-conditions
of the changes are verified before they can be carried out. A good starting point to
do that, is to enable only the kinds of changes that can be performed in a certain
context of the IDE. For instance, when a class is already added and selected, a
programmer can execute a change to add a method to that class.
Composition of changes
As we have explained in the previous section, changes can be composed in order to
form new change types. The IDE should include the functionality to support this
process. Concretely, the programmer should be able to compose scripts of existing
changes and capture them in new change types. User dialogs must be generated
that can query the developer for the information that specifies those changes.
Another aspect of the composition of changes is the grouping of change in-
stances based on a common property (the user that produced those changes, their
intent (= their reason of existence), the time on which they were applied, etc).
Such grouping can be used to classify changes in change groups, which can after-
wards be used to reason about the changes on a more abstract level.
Development support
The idea behind ChOP is that a developer does not write code himself, but rather
that the code is generated for him when changes are executed. The IDE should
provide support for executing those changes. Concretely, all kinds of change should
be invokable from within the IDE. Moreover, the IDE should provide dialogs to
interact with the programmer in order to obtain the information required to specify
the change. In fact, some IDE’s already provide some support to that regard.
Eclipse [106] and VisualWorks [51] for instance, both provide an interactive way
of adding a new class to a system. Both do this by means of graphical dialogs which
request the desired information from the developers. Such interactive support to
apply other kinds of changes, like adding methods or more fine-grained changes,
however, is not included in those IDE’s.
In practice, though, pure ChOP does not seem realistic. We do not believe
a programmer will actually execute a dialog for adding a statement to a method
body. For that, we propose that the IDE is instrumented with a logging mechanism
which is capable of monitoring the actions of a programmer and which instantiates
the changes that correspond to those actions. While this does not correspond to
pure ChOP, we believe it makes ChOP more applicable and useable, while it does
not take away the main benefits of ChOP, which we discuss in the following section.
latter only records the evolutionary information at the explicit request of develop-
ers [93] while the former implicitly records the evolutionary information: changes
are recorded as they happen.
Such a change management system is integrated into the Interactive Develop-
ment Environment (IDE) and continuously captures changes as they are applied
by the developer(s). Hence developers do not carry the responsibility of commit-
ting versions. Each captured change increments the system history stored in the
repository enabling to reconstruct a software version at any point of time.
In [93], Robbes et al show that incremental change management provides a lot
of useful information about the evolution of the software systems. Hence, such
change management is a valuable source for software evolution researchers. An-
other advantage of incremental change management is that it allows a bottom-up
approach for feature-oriented programming (as we will elaborate on in Chapter 5).
classes, methods, etc. For aspect-oriented programming, on the contrary, the building blocks
also contain aspects, pointcuts, etc.
60 Change-oriented programming
Change Composer
ChEOPS fully supports change-oriented programming but also has the capa-
bility of logging developers producing code in the standard OO way. Therefore,
3.5 Tool support 61
Changes t o ChatApp package : 1
Add new i n s t a n c e method " receive : m from : s" t o c l a s s " User " 3
−> I n v o c a t i o n t r e e added 4
−> I n v o c a t i o n t r e e added 8
Add new i n s t a n c e method " get : m from : s" t o c l a s s " ChatRoom " 13
−> I n v o c a t i o n t r e e added 14
−> I n v o c a t i o n t r e e added 16
Listing 3.4: Chat application: change list by ChEOPS
ChEOPS instruments the IDE with hooks and uses them to produce fine-grained
first-class change objects that represent the actions taken by the developer. Those
objects can later be grouped into a change set that specifies a transition which
might be applied in order to extend the base with the feature expressed by that
change set.
The following goes back to the evolution scenario from Section 3.1.1 and shows
how the support provided by ChEOPS overcomes the four identified issues. List-
ing 3.4 shows the list of changes of the basic 2-class chat application, as they are
logged by ChEOPS. Listing 3.5 and 3.6 respectively show the changes of adding
different user categories and ensuring user privacy in the way that ChEOPS logged
them.
Contrary to Listing 3.1, the ChEOPS change list allows a clear separation
between an addition of a new class (line 2 of Listing 3.4) and the addition or
removal of instance variables to a class (lines 5 and 6 of Listing 3.4). This is a
consequence of not overloading the AddClass change, but separating every change
into a different kind of change class. This improves the understandability of the
change list.
In the ChEOPS change list, every modification at the method level is rep-
resented not only by a statement such as User send:(change) (lines 7, 30 of
Listing 3.1). Instead, ChEOPS distinguishes between the addition (line 7 of List-
ing 3.4) and the removal of a method (line 10 of Listing 3.6). Next to that,
ChEOPS does not log changes only at the level of methods, but also logs more
fine-grained changes at the statement level of the method bodies. This overcomes
the problem of the restricted granularity which was identified in Section 3.1.
62 Change-oriented programming
Changes t o ChatApp package : 1
−> I n v o c a t i o n t r e e Added 4
Add new empty i n s t a n c e method " name " t o c l a s s " RegisteredUser " 6
−> I n v o c a t i o n t r e e Removed 10
Listing 3.5: Adding different users: change list by ChEOPS
Changes t o ChatApp package : 1
−> I n v o c a t i o n t r e e Added 3
−> I n v o c a t i o n t r e e Added 5
Remove i n s t a n c e method " receive : m from : s" from c l a s s " User " 6
−> I n v o c a t i o n t r e e Removed 7
Add new i n s t a n c e method " receive : m from : s" t o c l a s s " User " 8
−> I n v o c a t i o n t r e e Added 9
−> I n v o c a t i o n t r e e Removed 11
−> I n v o c a t i o n t r e e Added 13
Listing 3.6: Adding user privacy: change list by ChEOPS
Changes t o ChatApp package : 1
−> I n v o c a t i o n t r e e Added 3
−> I n v o c a t i o n t r e e Added 5
−> I n v o c a t i o n t r e e Removed 7
−> I n v o c a t i o n t r e e Added 9
−> I n v o c a t i o n t r e e Added 11
−> I n v o c a t i o n t r e e Added 13
−> I n v o c a t i o n t r e e Added 15
−> I n v o c a t i o n t r e e Added 17
Listing 3.7: Adding user privacy correctly: change list by ChEOPS
Changes t o ChatApp package : 1
−> c o m p o s i t e c h a n g e s 4
"f(x )= x" 6
−> c o m p o s i t e c h a n g e s 7
Listing 3.8: Adding user privacy correctly: (compositional) change list by ChEOPS
can now be applied on all kinds of classes that understand the name message and
have access to an instance variable cr which behaves like a Chatroom. Next to
that, it also improves the readability of the change list, as the extensive list of
composite changes is abstracted away behind the high-level change.
Exploring the change list of ChEOPS is easier and more user-friendly than in
the traditional ChangeList tool. This is a consequence of exploiting the improved
exploration support brought by the first-class change model behind ChEOPS. By
means of the ChEOPS change browser, changes can be looked at from four per-
spectives: ordered on time, grouped by affected entity, grouped by composition
and grouped by intension.
• The first view (depicted in Figure 3.8) is similar to the traditional ChangeList
approach, with the difference that ChEOPS organises the changes in a tree
structure where the fine-grained changes beyond the method-level are hidden
in the branches of the method-changes.
64 Change-oriented programming
• Figure 3.9 shows how the second view groups the changes by the entity they
affect. This entity can be any of the building blocks of the chosen meta-model
For ChEOPS supports ChOP for class-based object-oriented programming it
supports changes on building blocks such as classes, methods, attributes, etc.
This view also contains a tree of changes, where the dependent changes are
hidden in the branches of the creational change of their subject. For example,
the dependent changes of the creational change of User, are structured in a
branch below that change.
the atomic changes it contains. This view dramatically decreases the number
of changes to be displayed.
• Yet another ChEOPS view can present the changes grouped by their common
intent. An intent of a change is the reason of existence of that change; the
reason why that change was instantiated (a bug fix, the introduction of a
functionality, a refactoring, etc). The nodes of this tree view contain all the
intentions that are detected amongst the complete change set. Those nodes
can be expanded to present all the change objects in the same way as the
second ChEOPS view.
Figures 3.8 to 3.11 present the different views on changes that ChEOPS can
produce. In ChEOPS, those views are actually part of the change browser, that
66 Change-oriented programming
3.6 Discussion
Table 3.1 shows an overview of the four problems we identified in Section 3.1.
The vertical axis shows the requirements that we propose for ChOP (Section 3.3).
Cells containing an x denote that the property of the cell’s row helps to overcome
the problem of the cell’s column. The rest of this section discusses how this is
achieved:
model includes not only coarse-grained changes (such as the addition of classes
or methods), but also more fine-grained changes such as method invocations and
accessors. The possibility to compose changes into composite changes allows the
definition of more coarse-grained changes, which can be used to abstract away
from the fine-grained level. These extensions provide the granularity required to
reason about and understand the evolution history of programs. These extensions
are supported by the IDE in the form of an extensible change hierarchy. As pro-
grammers can define their own kinds of changes, they can broaden or tighten the
granularity spectrum.
Term overloading Our model provides a different change for every building
block of the chosen meta-model. As such, every change to such a building block is
captured by a specific change. This avoids overloading change classes to capture
different kinds of changes. We can conclude that in our model, the definition of a
change is unique. The fact that the programmer can define his own change types
and incorporate them into the extensible change hierarchy, also assists in avoiding
term overloading.
and (2) by the composite design pattern (distinguishing between atomic changes
and composite changes). High-level changes can also be defined as intensional
changes, which describe a pattern of change. The application of high-level changes
is conditioned by the fulfillment of their preconditions. This can be supported
by the IDE, which guides the programmers in defining new kinds of changes,
applying their changes, undoing changes and verifying the preconditions to ensure
the application consistency.
Other researchers pointed out the use of encapsulating change as first-class en-
tities as well. In [93], Robbes shows that the information from the change objects
provides a lot more information about the evolution of a software system than the
central code repositories. In [29] Denker shows that first-class changes can be used
to define a scope for dynamic execution and that they can consequently be used
to adapt running software systems. We refer to Section 2.3 for a more complete
overview of related approaches.
3.7 Conclusions
In this chapter, we presented change-oriented programming (ChOP): a program-
ming paradigm that targets software evolution and that centralises changes as
the main entity in the development process. The subject of the change refers to
the building block of the programming language in which the program is being
developed. As such, ChOP builds on top of another programming paradigm in
which those building blocks are written. In this dissertation, we build on class-
based object-oriented programming and take the chosen meta-model as a model
for describing the programs that are to be changed.
By means of an evolution scenario, we show the need for the centralisation of
change. We then introduce ChOP and explain that it has two dimensions: the
model of first-class changes and the management of the change instances. We first
show why first-class changes are desired to program in a change-oriented way. We
identify four issues with respect to the model of first-class changes, as it is presented
in a related approach. The restricted level of granularity in the different types of
changes, the overloading of change types, the lack of high-level changes and the
lack of program exploration facilities hinder good software evolution support. This
3.7 Conclusions 69
explains the need to extend the model of first-class changes in such a way that
these problems are overcome. With respect to the management of changes, we
present six requirements for a change management system that can enable ChOP.
Advantages of ChOP include the fact that it enables an incremental change
management, which has been proven to be beneficial over a snapshot-based change
management system with respect to the amount of evolutionary information it
contains. In the context of this dissertation, which also includes software variation,
ChOP enables a bottom-up approach to feature-oriented programming (presented
in Chapter 5). Another advantage of ChOP is that it is actually applied to another
programming paradigm and that it consequently must – but also can – be used in
combination with any other programming paradigm and programming language.
We briefly present ChEOPS, a proof-of-concept implementation of ChOP which
is implemented as a plugin of the VisualWorks for Smalltalk IDE. It is based on the
existing implementation of first-class changes, but extended with solutions for the
requirements that were identified. The implementation of the evolution scenario
in ChEOPS shows that an implementation of ChOP – that takes into account all
requirements identified above – indeed overcomes the four problems we identified.
Chapter 4
In the context of software evolution, many researchers have provided their view
on how evolution could be interpreted. Mittermeir for instance, believes that
software evolution should only be considered as the changes that were applied to
an existing software system [78]. In [65], Lehman studies different interpretations
of software evolution and elaborates on the theory and practice behind them. He
defines software evolution as
C++ Grouping
Java Metrics
FAMIX Model Reorganisation
Ada
Smalltalk Heuristics
Figure 4.1 shows a conceptual view of the FAMIX model. On the left hand side
we find different programming languages that were used to implement several case
studies of the FAMOOS project. The right hand side of the figure lists various
experiments conducted by several software analysis tools on the provided case
studies. In the middle, there is the information exchange model that only captures
the common features of class-based object-oriented programming languages such
as classes, methods or the inheritance relation. To cope with language specific
features, the FAMIX meta-model can be extended by using the provided hooks.
4.1 The FAMIX model 73
Those are represented by the grey bars at the bottom of the figure. The extended
meta-model takes as input the source code of the different case studies which in
its turn is provided as input to several software analysis tools.
We now discuss the complete FAMIX meta-model, subsequently its basic data
types, classes, attributes and relationships.
• Primitive data types: There exist two primitive data types in FAMIX
(String and Integer).
• Non-primitive data types: FAMIX defines three extra data types that may
be used in the model:
– Name is a String that gets its semantics from the model of the developed
software system. A uniqueN ame, for instance, may be used to refer to
an object from within the model.
74 Model of first-class change objects
The naming conventions used in FAMIX are very compliant with UML [15, 45].
For more information about the FAMIX naming conventions, we refer the reader
to [28]. We subsequently discuss all the building blocks of FAMIX and illustrate
their structure by means of UML class diagrams. We see that all the building
blocks are classified in an inheritance hierarchy with a root called Object.
4.1.2 Object
Object Property
SourceAnchor : Qualifier belongsToObject name : Qualifier
CommentsAt : String value : String
Argument Entity
Model Association
position : Index name : Name
isReceiver : Boolean uniqueName : Name
The Object class is the root class of the FAMIX model. As shown in Figure 4.2,
Object is an abstract class1 that does not inherit from any superclass but which
acts itself as a superclass for all other classes presented in the model (except for
the Property class). An Object holds a sourceAnchor determining the location
of the source code of the concerned object. A typical example of a source anchor
consists of the filename and start and stop indices where a class is physically stored.
Developers have the possibility of commenting model elements, these comments
are stored in the commentsAt attribute.
The Property of an object holds annotations that can be made to the FAMIX
objects. As such, properties provide an extension hook that can be used to extend
the FAMIX model. A Model represents information concerning the particular soft-
ware system being modeled (e.g. name of the publisher or the used programming
1 An abstract class is a class that cannot be instantiated. It is typically used to group the
language). In the FAMOOS project, the models were used by software analysis
tools when investigating the provided case studies. The remaining three subclasses
(Entity, Association and Argument) are explored in the following three subsec-
tions.
4.1.3 Entity
Entity
name : Name
uniqueName : Name
eg
ka
ac
declaredClass
oP
BehaviouralEntity
sT
accessControlQualifier : Qualifier
ng
StructuralEntity Class Package
lo
signature : Qualifier
be
declaredType : Qualifier isAbstract : Boolean
isPureAccessor : Boolean
declaredReturnType : Qualifier
declaredReturnClass belongsToPackage
Figure 4.3 shows the Entity class which represents the different mechanisms
that can be used in an object-oriented programming language to manipulate the
static structure, behaviour and state of the implemented system. As shown in
Figure 4.2, Entity is an abstract class inheriting from the Object class. An
Entity stores a name and a uniqueName, which must be unique for all entities in
the model of the software system. This is usually ensured by development tools
such as an IDE or a compiler.
The Class and Package classes inherit from the Entity class and form the
static structure of a software system. Class and Package respectively model
a class and a package in the context of object-oriented programming. A class
defines the structure and behavior of all the instances of that class. A Package is
a container that can be used to group source code. As such, packages organise the
software system in smaller subsystems. It is the belongsToPackage relationship
that denotes this decomposition. The following two subsections elaborate on the
BahaviouralEntity and StructuralEntity classes.
Behavioural entity
Figure 4.4 shows the BehaviouralEntity class which represents the definition
of a behavioural abstraction in a software system. When invoked, a behavioural
abstraction executes one or more actions defined in its body (e.g. calling other
76 Model of first-class change objects
BehaviouralEntity
accessControlQualifier : Qualifier
signature : Qualifier
isPureAccessor : Boolean
declaredReturnType : Qualifier
declaredReturnClass : Qualifier
e
ag
ck
Pa
Tos
ng
Method
lo
Function Package
be
hasClassScope : Boolean
declaredReturnClass
isAbstract : Boolean
isConstructor : Boolean
Class
isAbstract : Boolean belongsToPackage belongsToPackage
belongsToClass
Structural entity
belongsToClass
belongsToBehaviour Attribute
accessControlQualifier : Qualifier
hasClassScope : Boolean
LocalVariable
ImplicitVariable Package
belongsToContext : Name
FormalParameter
position : Index
belongsToBehaviour GlobalVariable
belongsToPackage
Figure 4.5 shows the StructuralEntity and the relations it has to other
FAMIX entities. A StructuralEntity class represents the definition of an entity
that concerns the structure of a system (e.g. an attribute specified in a certain
class to which a particular value can be assigned). Structural entities are charac-
terized by their scope: Some are visible only within the entity in which they are
defined (e.g. attributes are only accessible from within the class). Others have a
scope equal to that of the entire running system (e.g. global variables).
Every structural entity is of a certain kind, which is denoted by its type. The
declaredType Is a qualifier that refers to the declared type of the structural entity.
Typically this will be a class, a pointer or a primitive type (e.g., int in Java).
declaredType is empty if the static type is not known or the empty string (i.e.,
“”) if the StructuralEntity does not have a static type. Note that this is the
case in programming languages which are not statically typed (such as Smalltalk).
78 Model of first-class change objects
4.1.4 Association
Association
invokedBy
se
candidate accesses
ba
superclass subclass
4.1.5 Argument
Argument
position : Index
isReceiver : Boolean
hasArguments hasArguments
Invocation Access
with a new entity called Statement, which models a code statement. A code
statement is a sequence of expressions and keywords (such as return). We model
the contents of a code statement as a String. In order to make this extension to
FAMIX, we use the extension hooks that are provided by its inheritance hierarchy.
belongsToClass
belongsToBehaviour Attribute
accessControlQualifier : Qualifier
hasClassScope : Boolean
LocalVariable
ImplicitVariable Package
belongsToContext : Name
FormalParameter
position : Index
belongsToBehaviour GlobalVariable
belongsToPackage
Statement
belongsToBehaviour contents : String
position : Index
the building blocks are modeled by the meta-model (like the one described in
the previous two sections), that meta-model is part of the evolution model. The
central entity of the evolution model is Change: A class that represents an evolution
action. The FAMIX building blocks (all inheriting from the FamixObject) form
the Subject of the change. We identify three kinds of evolution actions that can
be applied to those subjects: addition, removal and modification. We model those
actions with the classes Add, Remove and Modify respectively. Together, they
form the concrete commands of the Command design pattern [43]. The Atomic
Change class plays the role of the abstract command class in the Command design
pattern. Next to that, it also fullfils the responsibilities of the leaf participant in
the Composite design pattern [43]. A Composite Change is composed of Changes
(which can in turn be of any change kind). Note that the inclusion of those design
patterns in the evolution model provides an extension hook that can be used to
introduce new kinds of evolution actions. We elaborate on the difference between
atomic and composite changes in subsection 4.3.2.
semanticaldependentChanges
Change
timeStamp structuraldependentChanges
isApplied Dstr Dsem
intent
changesOnWhichIDependStructurally
user
parent apply changesOnWhichIDependSemantically
composites undo affectingChanges
The UML class diagram of the core of the evolution model is presented in Fig-
ure 4.9. The diagram also shows two dependency relationships between the change
objects: Dstr and Dsem . The details of the dependencies amongst the changes are
discussed in Section 4.4. Notice also that a subject maintains a reference to all
of the changes that affect it (expressed by the affectingChanges relation). This
information is redundant but allows for optimisation.
Figure 4.9 shows that we distinguish between two kinds of changes: atomic and
composite changes. Atomic changes are operations that manipulate the building
blocks of a particular program. As was stipulated in the previous section, these
operations consist of adding or removing an entity (for instance a class) as well as
modifying the properties of an entity (for instance the name of a class). By calling
the apply method to an atomic change, the change will be applied. By iterating
4.3 A model of changes 83
over the changes and re-applying them, one can reproduce each development stage
that a program went through during its development or evolution.
Composite changes consist of an ordered sequence of changes (which can in turn
be composite or atomic changes). They group changes in a composition, which
can be more powerful than the atomic changes on their own. The RenameMethod
refactoring, for instance, can be expressed as a composition of a Modify change of
a method m and a Modify-Invocation change for every invocation of the original
method m.
The following two subsections discuss the atomic (subsection 4.3.1) and com-
posite changes (subsection 4.3.2) respectively. Subsection 4.4 explains the depen-
dency relations between change objects.
Entity changes
From the point of view of changes we identify four different kinds of relations:
Changes can be creational, adaptive, destructive or invariant with respect to a
certain subject. A change c is said to be creational w.r.t. a building block b if the
application of c adds b to the software system. A change c is said to be adaptive
w.r.t. a building block b if the application of c adapts one of the attributes of b in
the software system. A change c is said to be destructive w.r.t. a building block b
if the application of c removes b from the software system. A change c is said to
be invariant w.r.t. a building block b if the application of c does not affect b.
Consequently, one change can be one of four kinds, depending on the building
block we relate it to. A change that adds a class C to a package P for example, is a
creational change w.r.t. class C, is an adaptive change w.r.t. package P and is invari-
ant w.r.t. another (unrelated) package Q. It is the meta-model of the programming
84 Model of first-class change objects
language that specifies the relations between the different building blocks. FAMIX
defines packages to contain classes that contain methods and attributes. Methods
in turn contain statements, which consist of invocations or accesses.
The horizontal axis of Table 4.1 lists the different entities which we identified
on the extended FAMIX model: Package, Class, Method, Function, Statement and
all the structural entities. The vertical axis contains the different kinds of changes
that can be applied to those entities. Note that each of these change kinds is
actually a combination of a change and its subject. An AddMethod change for
instance, corresponds to an instance of the Add class with a Method as its subject.
For the remainder of this text, we use this notation for change kinds.3
The table shows that an Add change is creational (C) at the level of granularity
of its subject and adaptive (A) at all more coarse-grained FAMIX entities that
contain the subject of that change. A Remove change is destructive (D) at the
level of granularity of its subject and adaptive (A) at all more coarse-grained
FAMIX entities that contain the subject of that change. A Modify change is
adaptive (A) at the level of granularity of its subject and also adaptive (A) at all
more coarse-grained FAMIX entities that contain the subject of that change. All
voids in the table consist of invariant relationships, as the corresponding change
is invariant w.r.t. the corresponding entity.
Association changes
As a side effect of applying an atomic change to one of the software system’s
entities, there might be a modification of the relation between those entities. Such
modifications are modeled by the association changes and are categorised in three
groups: changes to the inheritance definition, changes to the method invocation
and changes to the entity access. We subsequently discuss all three groups.
of while loops. Note that it is not necessary to model such special constructs in Smalltalk, as in
that language such constructs are implemented by ordinary messages sent to a Boolean instance.
4.3 A model of changes 85
Formal Parameter
Implicit Variable
Global Variable
Local Variable
Statement
Attribute
Function
Package
Method
Class
AddPackage C
ModifyPackage A
RemovePackage D
AddClass A C
ModifyClass A A
RemoveClass A D
AddMethod A A C
ModifyMethod A A A
RemoveMethod A A D
AddFunction A C
ModifyFunction A A
RemoveFunction A D
AddStatement A A A A C
ModifyStatement A A A A A
RemoveStatement A A A A D
AddAttribute A A C
ModifyAttribute A A A
RemoveAttribute A A D
AddLocalVariable A A A A A C
ModifyLocalVariable A A A A A A
RemoveLocalVariable A A A A A D
AddImplicitVariable A A A A A C
ModifyImplicitVariable A A A A A A
RemoveImplicitVariable A A A A A D
AddGlobalVariable A C
ModifyGlobalVariable A A
RemoveGlobalVariable A D
AddFormalParameter A A A A A C
ModifyFormalParameter A A A A A A
RemoveFormalParameter A A A A A D
Change instantiation
In order to develop or evolve a software system, the above explained atomic changes
need to be created and carried out. The creation of a change is done by instantiat-
ing the corresponding concrete operation class from the core model (Figure 4.9).
Instantiating an AddMethod for instance, is done by instantiating the Add class
with a Method as its subject. In order to carry out a change, it is sent the apply
message. The change itself is responsable of carrying itself out. For that, it needs
to contain all the information that specifies it. More concretely, in our model, a
change is specified by:
• what its kind (Add, Modify or Remove) and subject (the affected FAMIX
building block) are
• when it gets instantiated (time)
• who instantiated it (user)
• why it got instantiated (intent)
Throughout this dissertation, we use the declarative notation of Listing 4.1
to reference a change instance. ChangeName is the name of the change kind
(e.g. AddClass), parameter list is a list of the information that specifies the
4.3 A model of changes 87
ChangeName ( p a r a m e t e r l i s t , time , u s e r , i n t e n t ) 1
Listing 4.1: Change instantiation
AddClass ( ( B u f f e r , Object , B u f f e r P a c k a g e ) , 1
122233565.554 , 2
Listing 4.2: Change instantiation example
change subject (e.g. name, superclass, package), time is an object that represents
the time, user is an object that represents the user who created the change and
intent is an object that denotes the raison d’être of the change. In a simple
variation of this model, both the intent and user contain a String that describe
the intent and the user respectively. In Chapter 5 we present a more powerful
variation of this model in which these values are more abstract.
Listing 4.2 presents an example of a change instance. It can be read as follows:
the change stands for the creation of the class Buffer as a subclass of Object in
the BufferPackage and is instantiated on 122233565.554 by Peter in order to
produce the BufferBaseCode.
Change
...
apply changes
...
AtomicChange CompositeChange
... ...
apply apply
... ... forall c in changes
c apply
PushDownField AddUserClass
...
... ...
new new
apply apply
... ...
change, which will in turn add a subclass to the User hierarchy and add methods
for instantiating that new class. Another well-known example of domain-specific
changes are the code refactorings [41] which are used to increase the maintainabil-
ity and evolvability of software systems. Every refactoring can be modeled by a
composite change, that evaluates to a sequence of atomic changes whenever ap-
plied. In fact, composite changes are higher-order changes: changes that evaluate
to a sequence of changes, whenever they are applied.
Advantages of the composite changes include that they raise the level of ab-
straction, and stimulate the reuse of changes. The composition of changes into
composites, however, also improves the comprehensibility of the change list. A
system history consisting of only atomic operations leads to an enormous and
poorly organized amount of information.
Change definition
Developers can define their own domain-specific changes for the domain in which
they are working. This is done by producing a subclass of the CompositeChange
class. Figure 4.10 already depicts two examples of such definitions. The
PushDownField is a refactoring that relocates a attribute that is only used by
4.3 A model of changes 89
PushDownField ( ( a t t r i b u t e , sup , sub ) , timestamp , u s e r , i n t e n t ) i f 1
timestamp . 1 , u s e r , i n t e n t ) 3
Listing 4.3: Change definition example 1
AddUserClass ( ( name ) , timestamp , u s e r , i n t e n t ) i f 1
timestamp . 3 , u s e r , i n t e n t ) 5
timestamp . 5 , u s e r , i n t e n t ) 8
Listing 4.4: Change definition example 2
some subclass to that subclass. It consists of two atomic changes: one that re-
moves the attribute from the super class and one that adds it to the subclass.
Listing 4.3 presents the definition of a new change kind which models a push-
down field refactoring [41]. The listing shows that, in order to create a new in-
stance of the PushDownField change, one needs to specify the concerned attribute
attribute, super class sup and subclass sub. The composite change consists of
two atomic changes, that are responsible for removing the attribute from the su-
perclass and adding it to the subclass. The declarative definition of composite
changes describes what the change should accomplish, rather than describing how
it should accomplish it.
Listing 4.4 presents the definition of a new change kind which models a domain-
specific change that is responsible of adding a new kind of user to the chat appli-
cation of Figure 3.2. The listing shows that, in order to create a new instance of
the AddUserClass change, one only needs to specify the name of the new kind of
user. The composite change consists of five atomic changes, that are responsible
of creating the new class representing the new kind of user as a subclass of User
and by producing the methods for initialising that class. Note that the second pa-
rameter in the AddMethod change is a predicate that denotes wether the method
is added as a class method or as an instance method of the class. If the predicate
is true, the change is adding a class method.
Change instantiation
Employee Employee
quota
and
which, when applied, produce a software system as in the right-hand side of Fig-
ure 4.11.
When those changes are produced, they receive a time stamp. Every time
stamp must be unique. In order to accomplish that, we make the time stamps of
the changes follow a recursive model of nested numbers. If a change has a time
stamp x and a new change is created that should receive the same time stamp x,
we instead give it a time stamp x.1. The semantics of a time stamp x.y are as
follows. A change c with time stamp xc .yc happens after all changes with a time
stamp where x < xc , but before all changes with a time stamp where x > xc . The
change happens before changes that have a time stamp where x = xc and where
yc < y and after changes with yc > y. The same principle is applied recursively in
order to ensure that the uniqueness of the time stamps is also preserved for nested
time stamps. In case a change would be assigned an already given time stamp x.y,
it is assigned x.y.1 in stead.
added the invoked method. Dependencies are relations between changes and are
consequently implied by the relations between the entities of the evolution model.
In this subsection, we explain the seven kinds of structural dependencies we iden-
tified in our FAMIX-based evolution model.
Five kinds of structural dependencies can be derived from the FAMIX model.
We name them: hierarchical dependencies, accessive dependencies, invocative de-
pendencies, genetic dependencies and typological dependencies. Two kinds of de-
pendencies can be derived from the relations between the entities in the change
model itself. We call those: transactional dependencies and creational dependen-
cies. We now itemize the seven kinds of structural dependencies that can exist
between the change instances of our evolution model and illustrate them.
AddClass ( (A, Object , P) , 1 , Peter , " InvocationTest " ) 1
Listing 4.5: Invocative dependency example
and classes. As an example, consider that c1 adds the class A and c2 adds
a global variable a of type A. Than, c2 is said to typologically depend on
c1 . Note that this kind of dependency only gets instantiated in case entities
have a declared type. In Smalltalk, for instance, that is not the case.
AddClass ( (A, Object , P) , 1 , Peter , " AccessTest " ) 1
Listing 4.6: Accesive dependency example
4.5 Conclusion
In this chapter, we established a model that is capable of expressing the evolu-
tion of software systems to a certain extent. The model centralises change as a
first-class entity. Although our evolution model is not language-specific, it tar-
gets a specific set of programming languages. More precisely, it can be used to
model the evolution of all building blocks of programming languages that adhere
to the FAMIX meta-model: class-based object-oriented programming languages
(e.g. Java, Smalltalk, C++, Ada, etc.).
4.5 Conclusion 95
Feature-oriented
programming through
change-oriented
programming
5.1 Principles
5.1.1 Features as functions
In this dissertation, we follow the intuition of Batory and see a feature as a function
that modifies a program in order to increase the capabilities of that program with
the capability modeled by that feature. A capability can be of a functional or
non-functional nature (see Section 2.2 for more information). We define a feature B1
as a structure that has to be applied to a given program in order to satisfy a stake-
holder’s requirement, to implement and encapsulate a design decision or to offer
a configuration option and we show how ChOP enables a bottom-up approach to
Buffer B3
FOP that provides more control of how features are specified. In the following
subsections, we use a Buffer base program in order to present the building blocks B5
of the approach: the changes and the dependencies between them.
B6
5.1.2 Changes as feature building blocks
LogMethod Logging Restore
In ChOP, software systems are developed and evolved by instantiating changes
L1 instances actually represent
of a change model (illustrated in Chapter 4). Those R3
all the development operations that were carried out to implement the complete
software system. Consequently, the application of all those changes, results in a
complete version of the software system. However, PrintInstVars
one can also apply onlyInvokeLog
a part Mul. Res
of those changes in order to get another version of the same software system. Such
software system is actually a variation of the original software system – one with
L5 L6to FOP.
less functionality. This technique is the core of our approach L2 L3 L4 M6 M5
Consider a Buffer program that follows the value object pattern [43] in order
to provide the functionality of a buffer. The left hand side of Figure 5.1 presents
the Java code of the that buffer software application. It does not show what devel-
opment actions were performed in order to actually produce that code. Actually,
first the Buffer class was added by an AddClass change (B1). Afterwards, an
instance variable called buf was added by an AddAttribute change (B2). Finally,
the methods get (B3) with body (B4) and set (B5) with body (B6) were added by
twice respectively instantiating and applying an AddMethod and an AddStatement
change.
The right part of Figure 5.1 presents all the first-class change objects that re-
sulted from the development operations taken to produce the buffer. Next to that,
the figure also shows that all these changes are grouped into a set of changes that
represent that buffer. Conceptually, the drawing in the right part of Figure 5.1,
presents a feature as a set of all the development actions that were taken in order
to add the functionality of that feature (denoted by a name and a line surrounding
all the concerned change objects).
The edges between the change objects represent the dependencies between
the change objects that were introduced in Section 4.4. The following subsection
explains in more detail how these dependencies are modeled and used in the context
of FOP.
5.1.3 Dependencies
In our model of ChOP, a change object c1 is said to depend on another change ob-
ject c2 (c1 → c2 ) if the application of c1 without c2 would violate one of the system
invariants. As explained in the previous chapter, we differentiate between struc-
tural dependencies (ensuring structural invariants) and semantical dependencies
(ensuring behavioural invariants). While the former are automatically derived
from the meta-model, the latter depend on domain knowledge and must be in-
stantiated manually. Both kinds, however, are represented in the same way in
Figure 5.1: A dependency between a change c1 and a change c2 is represented by
an edge from c1 to c2 .
A software system often consists of more than one functionality. In ChOP,
a software system is always implemented incrementally. Consequently, the fea-
tures of a software system are added one after the other. We extend the buffer
application with a Restore, a Logging and a Multiple Restore feature which
respectively add the functionality of restoring the value of the buffer, logging the
values of all instance variables whenever a method of the buffer is executed and
allowing the buffer to restore more than one value. Figure 5.2 presents the code of
the adapted application. From left to right, the features Restore, Logging and Mul-
tiple Restore are implemented. The corresponding change objects are presented
in Figure 5.3.
The dependencies between changes are not always confined to a single feature,
but can reach changes of other features as well. For example, in Figure 5.3,
changes within the Restore feature depend on changes inside the Buffer feature.
Based on those dependencies one can state that the Restore feature depends on
the Buffer feature. Indeed, the dependencies that hold between certain of these
change objects can be propagated to the feature level. The dependency of a change
R1 of a feature Restore on another change B1 from a feature Buf f er implies that
Restore is dependent on Buf f er. Hence, feature dependencies are modeled by
means of fine-grained dependencies between change objects.
B4B4
return(
return( buf
buf ); ); intint get()
get() {{
}} return(
return( bufbuf
); );
void
B5B5void set(
set( int
int xx) {) { }}
buf
buf = x;B6B6
= x; void
void set(
set( intint
xx) {) {
}} back
back = buf;
= buf;
}} bufbuf = x; R3R3
= x;
}}
void
R2R2void restore()
restore() {{
bufbuf = back; R4
= back; R4
100 }
Change-oriented }feature-oriented programming
}}
class
class Buffer
Buffer {{ class
class Buffer
Buffer {{
int
int buf
buf = 0;
= 0; int
int buf
buf = 0; M1
= 0; M1
int
int back
back = 0;
= 0; Stack
Stack back
back = Stack
= Stack new();
new();
int
int get()
get() {{ int
int get()
get() {{
logit();L2L2
logit(); logit();
logit();
return(
return( buf ); );
buf return(
return( buf ); );
buf
}} }}
B1 class Buffer { class Buffer { void
voidset(
set(int xx
int ) {) { void
voidset(
set(intint
xx) {) {
int buf = 0; B2 int buf = 0; logit();
logit();L3L3 logit();
logit(); M2 M2M3 M3
B3 int get() { B4 R1 int back = 0; back
back = buf;
= buf; back.push(x);
back.push(x);
return( buf ); int get() { buf
buf= x;
= x; buf
buf= x;
= x;
} return( buf ); }} }}
B5 void set( int x ) { } void
voidrestore()
restore() {{ void
voidrestore()
restore() {{
buf = x; B6 void set( int x ) { logit();
logit();L4L4 logit();
logit(); M4 M4M5 M5
} back = buf; buf
buf= back;
= back; buf
buf= back.pop();
= back.pop();
} buf = x; R3 }} }}
} L1L1void
voidlogit()
logit() {{ void
voidlogit()
logit() { { M6 M6
R2 void restore() { print(back);
print(back); L5L5 print(back.top());
print(back.top());
buf = back; R4 print(buf);
print(buf);L6L6 print(buf);
print(buf);
} }} }}
} }} }}
class Buffer { class Buffer {
int buf = 0; Figure 5.2: Source
int buf M1 of adding Restore (left), Logging (middle), Multiple
= 0; code
int back = 0; RestoreStack (right)
back = Stack new();
int get() { int get() {
logit(); L2 logit();
return( buf );5.2 Mathematical
return( buf ); properties
} }
void set( int x )We{ nowvoid set( the
discuss int x ){
mathematical properties of the dependency relation between
logit(); L3 logit(); We
change objects. M2define
M3 the structural dependency relation to be irreflexive,
back = buf; asymmetric back.push(x);
and transitive and define the semantical dependency relation to be
buf = x; irreflexivebuf = x;
and transitive. We wrap up this section by introducing a dependency
} }
graph: a mathematical graph consisting of change objects (as the nodes) and
void restore() { void restore() {
dependencies (as the relation).
logit(); L4 logit(); M4 M5
buf = back; buf = back.pop();
} 5.2.1 } The dependency relation
L1 void logit() { void logit() { M6
print(back); L5 print(back.top());
We differentiate between the two kinds of dependency relations and elaborate
print(buf); L6on their print(buf);
mathematical properties. For that, we first introduce the dependency
} operator,} c → c – an alternative notation for (c , c ) ∈ D – meaning that the
1 2 1 2
} }
change c1 depends on c2 . This means that c1 needs c2 to be applied first.
Structural dependencies
In Section 4.4.1, we already elaborate on the different kinds of structural depen-
dencies. All these structural dependencies have similar properties, which we now
explain in detail. Given the changes c1 , c2 , c3 which belong to the set of change
objects C and the relation Dstr ⊂ C ×C with (c1 , c2 ) ∈ Dstr (in the alternative no-
5.2 Mathematical properties 101
B1 B1 R1
Restore R2 L1
Logging Mul. Res
R1 M5 M3 M1
R3 R4 L5 L6 L2 L3 L4 M4 M2 M6
B5 B2 R1 B2 B3 B5 R2 R4 R3 L5
str
tation, this boils down to c1 → c2 ). Then, we can say that Dstr is a homogeneous,
binary endorelation over C. An endorelation is a binary relation where the domain
and codomain are the same. The relation Dstr has the following properties:
• Dstr is irreflexive:
In our change model, a change can only be applied if the changes which
it depends on have already been applied. A change can never structurally
depend on itself. In case a change c1 would hierarchically depend on itself
for instance, c1 would have to affect a subject that is in a belongsTo rela-
tion with itself. The evolution model from Chapter 4 ensures that that is
never the case. In fact, it is the FAMIX core that ensures the irreflexive
property for hierarchical, accessive, invocational, genetical and typological
dependencies, while the change model ensures it for transactional and cre-
ational dependencies. Expressed by means of the dependency operator, this
str
property is c1 6 → c1 .
• Dstr is asymmetric:
the change model ensures this for the latter two kinds. A shorter notation
str str
of this property is: c1 → c2 ⇒ c2 6 → c1 .
• Dstr is transitive:
Semantical dependencies
A semantical dependency is a relation between changes where the software ap-
plication does not exhibit the desired behaviour whenever the depending change
is applied without the change it depends on. Consider for instance, the changes
R1 and R2 from the Restore feature. Each of those changes can be applied inde-
pendently from the other without the resulting software application violating the
meta-model. The resulting software application, however, would not contain the
restore functionality if either of the changes would not be applied. Consequently,
there is a semantical dependency between R1 and R2. In fact, there is a semantical
dependency between every two changes of the restore feature, since omitting one
of the changes would result in an application with an undesired behaviour.
A semantical dependency also exists between the changes that add the func-
tionality of viewing the contents of a log file and the changes of our Logging
feature, which output the results of the logging to a log file. If the latter changes
are not applied, the former do not make sense, as they would only allow viewing
5.2 Mathematical properties 103
an empty log file. It still makes sense, however, to include the changes of the
Logging feature without including the changes to view the log file.
Given the changes c1 , c2 , c3 which belong to the set of change objects C and the
relation Dsem ⊂ C × C with (c1 , c2 ) ∈ Dsem modeling the semantical dependency
relation ”c1 needs c2 to be applied together” (in the alternative notation, this
sem
boils down to c1 → c2 ). Then, we can say that Dsem is an homogeneous, binary
endorelation over C with the following properties:
• Dsem is irreflexive:
A change can never semantically depend on itself as that would imply that
the change would have to be applied before itself in order to obtain a cor-
rectly behaving software application. Expressed by means of the dependency
sem
operator, this property is c1 6 → c1 .
• Dsem is transitive:
are the structural dependency relations between the change objects. Together,
they form the set of edges of G, called Dstr .
We now express a program family P as a graph with the changes as its nodes
(C) and the structural dependencies between those changes as its edges (Dstr ) and
define this graph as a tuple:
5.3 Advantages
In the previous sections we worked towards a novel approach to FOP, which is
based on ChOP. We now explain the four advantages this approach to FOP has
with respect to the state-of-the-art approaches to FOP. This approach provides
more control of feature specification, does not require one to adapt his development
process, provides detailed composition support and enables a bottom-up approach
to FOP.
None of the state-of-the-art approaches to FOP allow features to express the
deletion of software building blocks, although this is often required. The granular-
ity the approaches provide rarely reaches the statement level and in case it does, it
is limited. AHEAD, Lifting Functions, Mixin-layers, FeatureC++ and most AOP
approaches do allow the specification of a feature that adds a statement to an ex-
isting method by means of the super call. This construct, however, only allows the
expression of a statement addition before and/or after the complete old method
behavior. With those approaches, it is not possible to specify a feature that adds
a statement between the statements of an existing method. With the exception
of FeatureC++ and the AOP approaches, none of the above techniques provide
means to specify crosscutting feature. They require an alternative implementation
of such feature depending on the features present in the composition, hindering
reusability. All these symtoms show that the state-of-the-art approaches to FOP
provide only a limited control of how features are specified.
To the best of the author’s knowledge, all the state-of-the-art approaches to
FOP require a programmer to alter the development process. Most of the ap-
proaches introduce new programming concepts such as features (by FeatureC++),
refinements (by AHEAD), mixins or mixin layers (by the Mixin approach) that
the programmer should use in order to specify program capabilities as extensions
to or modifications of the other software system modules. Most of the approaches
also require the use of a specific Interactive Development Environment (IDE) or
IDE plugin, which enables the use of those concepts. Consequently, the program-
mer is required to adapt his development process. ChOP enables an approach to
FOP in which the programmer does not need to alter his development process:
It does not introduce new concepts, nor does it require a programmer to specify
how a software system is extended with a program capability, nor does it require a
specific programming language or IDE. We believe that such an approach to FOP
increases its usability in an industrial context, where companies typically do not
want to alleviate from their development methodologies and exerted programming
language.
Our approach to FOP ensures that a lot of fine-grained development infor-
mation is available in the entire development process. Whenever a new software
product variation needs to be produced as a composition of feature modules, this
information can be used in order to support the software composition process. In-
consistencies can be presented to the developer on a very detailed level in order to
assist the debugging process. This information is based on what changes cannot
be included in the composition and the reason why they cannot be included: what
dependent change should be included first. Because changes can be topologically
106 Change-oriented feature-oriented programming
class Buffer {
int buf = 0;
Stack back = Stack new();
int get() {
logit();
return( buf );
}
void set( int x ) {
logit();
back.push(x);
buf = x;
}
void restore() {
logit();
buf = back.pop();
}
Version 0
void logit() {
print(back.top());
print(buf);
}
}
Version 1
a statement to a method body for instance. The third strategy overcomes this
problem by supporting a more pragmatic ChOP.
The third strategy is based on logging the developer when taking development
or evolution actions. In this strategy, the IDE is instrumented with a logging
mechanism responsible to instantiate change objects that represent all the actions
the developers take. The advantage of this approach is that it seems more realistic
than pure ChOP, which would require the development process to be adapted.
The main drawback of this technique is that it still cannot be used on legacy
systems. A secondary drawback might involve privacy issues, as the programmers
are required to allow “Big Brother” to watch them.
A final, less important way of obtaining changes is by receiving them from a
source that already captured the changes. That source can be another developer
or a repository that contains the changes that were committed by one or more
developers. In order to support this technique, the change objects need to be
first-class, persistent and already collected by one of these four strategies.
semanticaldependentChanges
Change
timeStamp structuraldependentChanges
isApplied Dstr Dsem
intent
changesOnWhichIDependStructurally
user
parent apply changesOnWhichIDependSemantically
composites undo affectingChanges
Classification model
The classification model is a meta-model that consists of two parts: the change
model and the actual classification model. Each part focuses on another level
of granularity. The change model describes how the changes are represented.
Figure 5.5 shows that the change model separates between four kinds of changes,
which can be composed. Atomic changes have a subject: the program building
block affected by the change and defined by the Famix model [28].
The actual classification model defines and describes the entities of the super-
structure, which is a flexible organisational structure based on feature and change
objects. Figure 5.6 shows that the model contains three relations: Dstr /Dsem
(the structural and semantical dependencies that hold between the change ob-
jects), F 4C (which changes are grouped together into which feature) and Sub
(which features are contained within another feature). The cardinality of the
F 4C and Sub entities is a boolean attribute that specifies whether or not the son
(change and/or feature) has to be included in a composition that includes the
parent (a feature). This information can afterwards be used to validate feature
compositions (as in Feature Diagrams [54]).
Classification techniques
A classification strategy is a method for setting up classifications. Many classifi-
cation strategies can be devised ranging from setting up classifications manually
to generating classifications automatically. We present three classification strate-
5.4 Bottom-up approach to FOP 109
Dsem
F4C Change
cardinality timeStamp
parent Feature
isApplied
Sub id
intent
cardinality apply parent sons
user
sons undo Dstr
apply
undo
is required to manually go over all the changes in order to classify them by hand
in the categories presented in the upper part of Figure 5.7. This manual effort is
both error-prone and laborious.
or changed specification or fixing a bug, he usually knows the context in which the
changes are made. When making the changes, he provides that information to the
IDE. Moreover, the IDE knows the exact time, and in what part of the software,
the change is performed. Instead of keeping this knowledge implicit in the heads
of the developers, the IDE tags it to the changes.
Since software developers often do not have sufficient time when source code
documentation is concerned, it is not realistic to rely on discipline for the forward
tagging process. Consequently, the IDE should require that developers provide
the information at development time.
Discussion
We introduced a model and three strategies to classify changes and/or features
in sets that represent features. The model consists of two parts which respec-
tively model the change objects and the actual classification. The first strategy is
straightforward: manual classification is a strategy to put together classifications
manually; Semi-automatic classification is based on clustering changes together
based on properties such as by whom, when, why and where the changes were
applied; Automatic classification is based on forward tagging, and automatically
groups changes together.
Only the automatic strategy is usable in practice, as it is the only strategy
that requires minor manual labour without an increase in error probability. As
this strategy requires forward tagging, it is only applicable in combination with
pure ChOP or logging as a technique to capture changes. In case a software sys-
tem was already developed (e.g a legacy system), the system usually does not
contain the forward tagged information. Consequently, the changes collected from
such systems can only be classified by means of a manual classification strategy,
which might be supported with a semi-automatic technique. We conclude that the
development environment should support logging or ChOP in order to enforce for-
ward tagging, so that the changes can automatically be classified in recomposable
feature modules.
B1 Buffer
B3 B2 B5
B4 B6
Restore R2 Log
L1
Logging
Method
R1
PrintInstVars InvokeLog
R3 R4 L5 L6 L2 L3 L4
Mul. Res
M3 M5 M1
M2 M4 M6
change classes from the change model (represented by the Change class from Sec-
tion 4.3). The edges denote the structural and semantical dependencies between
the changes (modeled by the D relation in the change model of Figure 5.5 of Sec-
tion 4.4). Finally, a grouping form is an entity that denotes the concept of a feature
and which groups a set of changes and/or features (modeled by the F4C and Sub
relations respectively in Figure 5.6 of Section 5.4.2). Every change or grouping can
be surrounded by a full or dashed line. A dashed line denotes that the change or
grouping is optional with respect to its parent (the grouping to which it belongs).
A full line specifies that the change or grouping is mandatory with respect to its
parent grouping. This is modeled by the cardinality attribute of the F4C and
Sub relations of Figure 5.6 of Section 5.4.2.
Every subset of the set of changes instantiated when developing a software
system represents a different variation of that system. Since a change specification
holds the complete set of changes C, it contains the specification of more than one
variation of the software system. Moreover, the change specification can be used
to check the validity of such a variation. In our approach, a variation Var is valid if
all parent changes of the change objects of Var are part of Var. In FOP, however,
the different software variations are to be expressed in terms of required features.
A composition is a set of features that have to be included in a variation. As every
feature consists of a set of changes, the composition is a variation that consists of
the union of all changes of those features. An invalid composition is the result of
114 Change-oriented feature-oriented programming
be applied to produce the required composition. The second list consists of the
changes that had to be omitted from the composition because of unsatisfied depen-
dencies. In case the latter is empty, the validation succeeded. In case the latter
is not empty, it can be used by the developer to correct unwanted composition
errors.
Input: A feature set F , a change specification CS
Output: A list consisting of 2 change sets
Fmin ← minimal f eature set(F, CS);
Cmin ← minimal change set(Fmin , CS);
Cunw ← unwanted change set(Fmin , Cmin , CS);
+
Cunw ← transitive closure(Cunw , CS);
+
Cerr ← all mandatory changes that are in Cunw \ Cunw ;
+
return ( C \ Cunw , Cerr )
The order of the time complexity of Algorithm 1 is the sum of the time com-
plexities of all its subroutines. Algorithms 2 and 3 have a time complexity of
respectively O(f + Sub) and O(f) where f is the number of features and Sub the
116 Change-oriented feature-oriented programming
These optimisations are not considered in this dissertation and remain topic for
future research. As a tradeoff for this performance, the algorithm needs extra
working memory to do the necessary bookkeeping.
5.5 Conclusion
In this chapter, we introduced a novel approach to Feature-Oriented Programming
(FOP). The approach is based on the view that a feature is a function that has to
be applied to a software system in order to add the corresponding functionality to
that software system. The building blocks of a feature are instances of the different
change kinds (Add, Remove or M odif y). In some cases, a change depends on
another change in a structural or semantical way. In our model of ChOP, a change
object c1 is said to depend structurally (resp. semantically) on another change
object c2 if c1 cannot be applied without c1 without breaking one of the system
invariants imposed by the meta-model (resp. obtaining a incorrectly behaving
application).
In Section 5.2.1, we have shown that the structural dependency relation is
shown to be a strict partial order (an irreflexive, asymmetric, transitive binary en-
dorelation) over the set of changes. The semantical dependency relation is a tran-
sitive binary relation over the set of changes. We introduce dependency graphs as
graphs in which the nodes are changes and the edges are structural dependencies
between those changes. We show that such a graph is directed and acyclic when
only structural dependencies are considered. This is an interesting property as it
allows sorting the changes topologically based on the structural dependency rela-
tion. The resulting sequence of changes is applicable as the syntactic dependencies
are always satisfied whenever a change is applied.
Advantages of describing features as sets of changes that need to be applied
in order to add a functionality to a system are threefold. First, this approach
enables a more control of feature specification, since features can contain the dele-
tion of software building blocks and this on the fine-grained level of granularity
of code statements. Second, this approach does not require a developer to alter
his development process. Features can be constructed while programming in an
object-oriented way. Finally, it allows a bottom-up approach to FOP, in which the
fine-grained development information can be used to enable an automatic compo-
sition of software variations and in which the developer can be supported when
debugging software compostions.
All state-of-the-art approaches to FOP are top-down approaches in which an
overview of the system is first formulated, specifying but not detailing any first-
level subsystems. Each subsystem is then refined in yet greater detail, sometimes in
many additional subsystem levels, until the entire specification is reduced to base
elements. We present a bottom-up approach to FOP which adheres more to ad-hoc
development. With a bottom-up approach, the software system can be developed
in a feature-oriented way without having to design it up-front completely.
The approach consists of three phases. First, the change operations have to
be captured into first-class entities. We present three techniques to do that which
118 Change-oriented feature-oriented programming
Buffer
Logging Restore
• r ∈ N is the root,
• The relation contains no cycles, and each feature has no more than one
parent.
?
{(f1 , f2 )|f1 → f2 } forms a forest1 . (6.3)
We define roots(F ) as a function that returns the set of all features of F that
do not have a parent feature:
?
roots(F ) = {f ∈ F |@f 0 ∈ F • f 0 → f }
which each change associates with its parent feature. For convenience, we will
note
man
f → c if F 4C(c) = (f, man),
opt
f →c if F 4C(c) = (f, opt), and
?
f →c if F 4C(c) = (f, man) ∨ F 4C(c) = (f, opt).
Dstr ⊆ C × C, (6.5)
• Dstr is asymmetric:
• Dstr is transitive:
In other words, Dstr is a strict partial order over C. The semantical dependencies
between changes, are denoted by the relation Dsem ,
Dsem ⊆ C × C, (6.9)
• Dsem is transitive:
In other words, Dsem is a irreflexive and transitive endorelation over C. For the
sake of simplicity, we also define D as the union of the Dstr and Dsem relations.
D actually groups all the dependency relations between change objects,
Change specification
In addition to the well-formedness constraints on Sub, we require that each feature
must have sub-features, changes, or both – as in our approach to FOP, a feature
is always specified by a set of change objects or features.
? ?
∀f ∈ F • (∃f 0 ∈ F • f → f 0 ) ∨ (∃c ∈ C • f → c) (6.13)
C = {B1, B2, B3, B4, B5, B6, R1, R2, R3, R4, M 1, M 2,
M 3, M 4, M 5, M 6, L1, L2, L3, L4, L5, L6},
F = {Buf f er, Restore, M ul.Res, Logging, LogM ethod,
P rintInstV ar, InvokeLog},
opt opt opt
Sub = {Buf f er → Restore, Restore → M ul.Res, Buf f er → Logging,
man man
Logging → LogM ethod, Logging → P rintInstV ar,
man
Logging → InvokeLog},
man man man
F 4C = {Buf f er → B1, Buf f er → B2, Buf f er → B3,
man man man
Buf f er → B4, Buf f er → B5, Buf f er → B6,
man man man
Restore → R1, Restore → R2, Restore → R3,
man man man
Restore → R4, M ul.Res → M 1, M ul.Res → M 2,
man man man
M ul.Res → M 3, M ul.Res → M 4, M ul.Res → M 5,
opt man opt
M ul.Res → M 6, LogM ethod → L1, P rintInstV ars → L5,
opt opt opt
P rintInstV ars → L6, InvokeLog → L2, InvokeLog → L3,
opt
InvokeLog → L4}, and
D = {B2 → B1, R1 → B1, L1 → B1, M 1 → R1, B3 → B1, R2 → B1,
L2 → L1, M 2 → R3, B5 → B1, R3 → R1, L2 → B3, M 3 → M 2,
B4 → B3, R3 → B3, L3 → L1, M 4 → R4, B4 → B2, R3 → B2,
L3 → R2, M 5 → M 4, B6 → B2, R4 → R1, L4 → L1, M 6 → L5,
B6 → B5, R4 → R2, L4 → B5, R4 → B2, L5 → L1, L5 → R1,
L6 → L1, L6 → B2}.
6.2.2 Properties
From the fundamental concepts, we can now define properties of change specifica-
tions, such as the property of composability mentioned earlier. Let us first define
what change compositions and legal change compositions are.
Definition 5 (Legal change composition, legal feature set). A legal change com-
position H is a change composition such that there exists a legal feature set G ⊆ F ,
which satisfies the following constraints
H \M ⊆O (6.17)
∀c ∈ H • ∃(c, c0 ) ∈ D =⇒ c0 ∈ H (6.18)
By extension, we will say that such a G is a legal feature set for H with respect
to Cs; or that the changes H are composable. H is the set of features in which
the changes of G are contained (through F 4C). For the remainder of this text, we
always assume G to be a feature set, unless otherwise stated. In order to prove that
there is at least one legal change composition and feature set for a given change
specification (Theorem 7), we first define the semantics of a change specification.
Definition 6 (Semantics of a change specification). The semantics of a change
specification Cs, noted [[Cs]], is defined as the set of pairs (H, G) such that H is
a legal change composition of Cs and G is a legal feature set for H with respect to
Cs according to the above definition.
Note that this definition does not imply that there is only one legal change
composition for a single legal feature set and vice versa. The following theorem
establishes that every change specification has at least one legal change composi-
tion, i.e. [[Cs]] 6= ∅ for every change specification Cs.
Theorem 7 (Legal composition existence). For each change specification Cs,
there is at least one legal change composition and feature set:
[[Cs]] 6= ∅
Given a legal feature set G, there might be several legal change compositions.
And similarly, given a legal change composition H, there can be several legal fea-
ture sets such that (H, G) ∈ [[Cs]]. For proving this, simply consider the following
opt man opt
example. Let us assume we have a Cs with only f → f 0 , f → c and f 0 → c0 . In
0 0 0
this case, we have [[Cs]] = {({c}, {f }), ({c}, {f, f }), ({c, c }, {f, f })}.
Consequently, we will define the notions of minimal and maximal change com-
positions and prove their unicity in Theorem 10.
In the small example we gave above, {c} is both the minimal and maximal
change composition with respect to {f }, whereas with respect to {f, f 0 }, we have
a minimal change composition {c} and a maximal change composition {c, c0 }.
The following theorem proves the unicity of the minimal and maximal change
composition in the general case.
H = M ∪ (O ∩ {c | c0 ∈ M ∧ (c0 , c) ∈ D+ })
Similarly, we can define the notions of minimal and maximal feature set and
prove their unicity in Theorems 13 and 14.
Proof. Let us assume we have a legal change composition H. All legal G associated
?
to it satisfies ∀c ∈ H · G ⊆ {f | f → c} since all changes need to be justified by a
128 Formalism for feature composition
feature. Since H is fixed, one can only add features to G that do not require more
changes being added to H.
Minimally, to make G legal, only those features that help satisfy Sub should be
?
added. This means that for each c ∈ H with f → c, we need to include in G (1)
the feature f , (2) the set Ancf of all its ancestors, (3) the mandatory descendants
of f , noted Descman
f , and (4) the mandatory descendants of the features in Ancf .
Because the resulting feature set should be legal with respect to H, those features
do not require more changes. We now define this formally.
man+
In what follows, we will use the notation f → f 0 to mean:
?+
and the notation f → f 0 to mean:
? ? ? ?
∃f1 , f2 . . . fn · f → f1 ∧ f1 → f2 ∧ . . . ∧ fn−1 → fn ∧ fn → f 0 .
?+ man+
If we define Ancf = {f 0 | f 0 → f } and Descman
f = {f 0 | f → f 0 } then the
unique, legal and minimal feature set G2 can be constructed as follows:
?
• G0 = {f | f → c ∧ c ∈ H}
S
• G1 = G0 ∪ f ∈G0 Ancf
Descman
S
• G2 = G1 ∪ f ∈G1 f
Proof. Let us again prove this theorem by means of construction. Starting from G2
built according to the previous proof, we can now possibly add (1) root features
that were not already in G2 plus some of their descendants, and (2) optional
descendants of features already in G2 . If we want to keep a change composition
that is legal with respect to H, the selected additional features cannot require to
add any change that is not already in H. Those requirements are fulfilled by the
algorithms 6 and 7 which provide a unique legal and maximal set G3 .
6.3 From change specification to feature diagram 129
added ← ∅;
foreach f ∈ candidates do
man
if ∀f 0 ∈ Descman (f ) • ∃c ∈ C • f 0 → c then
added ← added ∪ {f } ∪ Descman (f )
end
return added;
end
Algorithm 7: addCandidates subroutine
B1 Buffer
B3 B2 B5
B4 B6
Restore R2 Log
L1
Logging
Method
R1
PrintInstVars InvokeLog
R3 R4 L5 L6 L2 L3 L4
Mul. Res
M3 M5 M1
M2 M4 M6
The decomposition type of each feature in the feature diagram will be an and.
This means that, in the resulting feature diagram, all children are mandatory
with respect to their parent. In order to represent the optionality of a child with
respect to its parent in the feature diagram, a dummy feature node is inserted
between the parent and the optional child. That dummy node is mandatory to
its parent and has itself a decomposition type of h0..1i for its son: the optional
child from the change specification. Figure 6.3 presents the change specification
of the Mul.Res. feature (on the left) and shows how a dummy node is inserted
between the optional M 6 node and its parent feature Mul.Res. (in the middle) in
order to represent the feature diagram of the Mul.Res. (on the right). Note that
other decompositions types like xor and or (Table 6.1 on page 120) are not used
in change specifications.
Buffer
Logging B1 B2 B3 B4 B5 B6 Restore
L5 L6 L1 L2 L3 L4 M1 M2 M3 M4 M5 M6
B2 ⇒ B1 R1 ⇒ B1 L1 ⇒ B1 M 1 ⇒ R1
B3 ⇒ B1 R2 ⇒ B1 L2 ⇒ L1 M 2 ⇒ R3
B5 ⇒ B1 R3 ⇒ R1 L2 ⇒ B3 M3 ⇒ M2
B4 ⇒ B3 R3 ⇒ B3 L3 ⇒ L1 M 4 ⇒ R4
B4 ⇒ B2 R3 ⇒ B2 L3 ⇒ R2 M5 ⇒ M4
B6 ⇒ B2 R4 ⇒ R1 L4 ⇒ L1 M 6 ⇒ L5
B6 ⇒ B5 R4 ⇒ R2 L4 ⇒ B5
R4 ⇒ B2 L5 ⇒ L1
L5 ⇒ R1
L6 ⇒ L1
L6 ⇒ B2
Figure 6.4: Tentative feature diagram representing the buffer change specification.
Theorem 15 (Correctness of Algorithm 8). Let cs2fd denote the translation func-
tion described by algorithm 8. Then for each change specification Cs,
where
f latten(Set) = {a ∪ b|(a, b) ∈ Set}.
The set returned by [[Cs]] consists of couples (H, G) such that H is a legal
change composition for G and that G is a legal feature set for H with respect
to Cs. Consider for instance calling f latten on ((H1 , G1 ), (H2 , G2 ), (H3 , G3 )).
This returns the set ((H1 ∪ G1 ), (H2 ∪ G2 ), (H3 ∪ G3 )). Each element of this
set consists of features and the corresponding changes, which is the same as the
semantics of the result of the feature diagram returned by Algorithm 8. The proof
is straightforward and was omitted from this text.
6.3 From change specification to feature diagram 133
r
! !"#$⇒#%&#'⇒#%&((()
!( opt_Buffer )=0..1
!( Buffer )=8..8
!( opt_L5 )=0..1 !( opt_L6 )=0..1 !( opt_L2 )=0..1 !( opt_L3 )=0..1 !( opt_L4 )=0..1 !( Mul. Res )=6..6
L5 L6 L1 L2 L3 L4 M1 M2 M3 M4 M5 !( opt_M6 )=0..1
*!"#+,,-.&#%&#$&#'&#/�&2344564&*.5678697:;.9&20&21&234<-7=3>&2%&
M6
86?3@-234&2$&2'&2/&A-973.-&A%&A$&A'&A/&<+B(A-9&<%&<$&<'&</&<0&<1)
Figure 6.5: Buffer feature diagram resulting from the translation algorithm
6.3.2 Applications
Given Algorithm 8 and Theorem 15, it is possible to translate a change specification
Cs into a feature diagram d whose legal products are exactly the legal change
composition/feature set pairs of the change specification. This means that we can
analyse d instead of Cs but interpret the results in terms of Cs. Here we present
several analysis methods for feature diagrams and show how they can be useful in
the context of ChOP.
A first application of feature diagrams was already hinted at in the previous
sections. Indeed, given a change composition/feature set pair, it is legal iff it is
a product of the feature diagram. Which means that we can use feature diagram
tools to check the validity of change composition/feature set pairs. Formally, given
a change specification Cs, H ⊆ C and G ⊆ F , then
Furthermore, we can use the feature diagram to determine the feature compositions
that are legal with respect to a change composition, i.e.
the variability of a software product line, the number of valid feature combina-
tions of a feature diagram |[[d]]| is a measure for the variability of the software
product line. If the feature diagram was obtained from a change specification, it
measures the variability of the change specification. This kind of metric is already
implemented in feature diagram tools such as FAMA [11]. Obtaining the same
information based on only the data in Figure 6.2 would require a new algorithm
and would consequently imply more work.
A similar metric would be to determine in how many ways a feature set G ⊆
F can be implemented, and how many changes are needed (at most/least) to
implement it. This can be done by calculating f comp(H) and determining the
minimal/maximal cardinality of its elements. A configuration tool, i.e. a tool that
lets a user choose which features to include, could then show this kind of statistics
while performing the choices.
If additional information about changes is available, such as the lines of code
added or additional memory consumption, it can be added to the feature diagram
in the form of feature attributes. The configuration tool could then show more
comprehensive statistics about the user’s current feature selection. Instead of
seeing merely how many changes it will require, the user will be able to see to what
extend the resulting application will grow in code size or memory consumption.
Instead of showing metrics to the user, the configuration tool could also choose the
change composition itself, for instance by selecting the one that is optimal with
respect to an objective function (e.g. minimise memory consumption) [11]. The
advantage here is that the attribute values would be automatically derived from
the actual changes in the code without the need for human intervention.
Another application of feature diagrams is determining which features are al-
ways present (called commonality),
\
comm(d) = G,
G∈[[d]]
6.4 Conclusion
In Chapter 5 we propose an approach to feature-oriented programming (FOP).
In this approach, changes that encapsulate any developer action (including the
removing of code) are first instantiated. Afterwards, changes can be combined to
form a product. Before that is done, it has to be ensured that the selected changes
actually can be composed.
In this chapter, we make an effort to verify the validity of change compositions.
In order to do that, we first propose a formal model of change-oriented program-
ming and afterwards map it to the well-understood notion of feature diagrams
(feature diagrams), which has become one of the standard modelling languages for
variability in Software Product Line Engineering. In order to take those steps, we
first provide a formal description of feature diagrams.
We propose a formal model of change-oriented programming which is based on
set theory. Properties including the legality of a change and feature composition
are explained subsequently. A composition is valid if the following five properties
hold: if a feature is selected, its parent feature must be selected too, if a fea-
ture with mandatory sub-features is selected the latter need to be selected too,
all changes that are mandatory with respect to the selected features are in the
composition, all changes stem from selected features and all dependencies are sat-
isfied. Afterwards, we prove that at least one legal change composition exists and
that there is always one maximal and one minimal legal change composition for a
given change specification and feature set. Correspondingly, we prove that at least
one legal feature composition exists and that there is always one maximal and one
minimal legal feature composition for a given change specification and change set.
We then map the formal model of ChOP to the well-understood notion of
feature diagrams. The mapping, provided in form of a translation algorithm,
allows us to reuse a number of results in feature diagram research and apply
them to ChOP. The first application consists of the validation of compositions.
A composition is legal if it is a product of the feature diagram. The second
application consists of the calculation of all valid compositions for one change
specification. The final application contains some metrics, which we can easily
measure on feature diagrams and which provide some information about so called
common (resp. dead) features, which must always (resp. never) included in legal
compositions.
The particularity of a feature diagram obtained from a change specification is
that it contains, unlike most feature diagrams obtained from analysts, implemen-
tation details that were recorded as the code was written. The level of granularity
is the statement, which is very fine. This huge amount of information allows for
6.4 Conclusion 137
Expressing crosscutting
concerns
statements scattered around every method in the Buffer class. Consequently, the
Logging feature depends on more than one feature (Figure 5.3).
A positive property of our approach is that the implementation of crosscut-
ting functionality is actually not scattered over the software application. All the
changes of a feature that implements a crosscutting functionality are grouped in
one change set. It is the application of the changes that actually produces a
software system containing the scattered building blocks of the crosscutting func-
tionality.
A property of features that implement a crosscutting functionality is that their
changes usually depend on more than one feature. As we have seen in the previous
chapter, a change-based software composition is only valid if all the changes on
which the changes of the composition depend are also included in the composi-
tion. Consequently, the inclusion of a crosscutting functionality in a composition
requires all the features that contain changes on which the changes of the cross-
cutting functionality depend to be included in the composition. As that is not
always desired, this boils down to a composition conflict. A quick and dirty solu-
tion would be to provide a feature variation for each combination of the features
on which it depends. This kind of solution would suffer from a combinatorial
explosion, increase the coupling between features and decrease reusability.
B1 Buffer
B3 B2 B5
B4 B6
Restore R2 Log
L1
Logging
Method
R1
PrintInstVars InvokeLog
R3 R4 L5 L6 L2 L3 L4
Mul. Res
M3 M5 M1
M2 M4 M6
Figure 7.1: Change specification of the buffer example (copy of Figure 5.10)
method to the Buffer class. The flexible PrintInstVars feature consists of two
optional changes, which each add a statement printing the value of an instance
variable of Buffer. Finally, the flexible InvokeLog feature contains three optional
changes – which each add a statement that invokes the logit() method – to a
method of Buffer. We argue that in case a flexible feature like InvokeLog is
included in a composition, its AddInvocation changes that have to be added to
methods that do not exist because their creational changes are not part of the
composition, should be omitted from the composition in order to make it valid.
Let us now demonstrate the flexibility brought to the composition of features by
flexible features.
ing feature set. On the other hand, a strategy for obtaining the minimal change
composition can also be interesting in the case where code size needs to be min-
imised, as it returns the most basic implementation of a feature set. Yet another
strategy could be a mix of both in which the optional changes that add code are
included and the optional changes that remove code are omitted.
The structural dependencies are enforced by the meta-model of the asserted
programming language and are used by the composition strategy to ensure compo-
sition validity. The fact whether a feature is monolithic or flexible does not affect
the structural dependencies between the change objects. This means that, if a
change of a flexible feature is omitted from a composition, all of the changes that
depend on it are also omitted from that composition. As long as these changes
are optional, the composition will remain valid. In the case one of these changes
is mandatory the composition is invalid. For more details on this composition
strategy, we refer the reader back to Algorithm 1 on page 115.
R3 R4 B4 L5 L2 L6 L3 L4 B6 B4 L5 L2 L6 L3 L4 B6
R1 B3 B2 R2 L1 B5 R1 B3 B2 R2 L1 B5
B1 B1
would add a class and a method for each complex service. It can be conveniently
described by a flexible feature, allowing for it to be composed with a set of features
which not necessarily include all the services that the facade class references. In a
composition, the facade class will only provide the methods for which functionality
is indeed present in the composition.
While flexible features already help in modeling crosscutting functionality, they
still suffer from some inconveniences. As we have already stated, it is up to the
developer to specify which changes or features are optional and which are not. A
second drawback of flexible features is that they only contain an extensional list of
changes which leads to issues maintaining such features. In the following section,
we elaborate on this issue.
class Buffer {
int buf = 0;
Stack back = Stack new();
int setc = 0; S1
int getc = 0;
int get() { S2
getc = getc + 1;
logit(); S3 S4
return( buf );
}
void set( int x ) {
setc = setc + 1;
logit(); S5 S6
back.push(x);
buf = x;
}
void restore() {
logit();
buf = back.pop(); B1
}
void logit() { Stats
print(back.top()); S2 S7 S1
print(buf);
} S7
int statistics() { S5 S6 S9 S8 S3 S4
print(setc); S8
print(getc);
} S9
}
B5 B3
class Buffer {
int buf = 0;
Stack back = Stack new();
int setc = 0; S1
int getc = 0;
int get() { S2
getc = getc + 1;
logit(); S3 S4
return( buf );
}
void set( int x ) {
setc = setc + 1;
logit(); S5 S6
back.push(x);
buf = x;
}
void restore() {
logit();
buf = back.pop();
}
void logit() { L7
print(setc);
print(getc); L8
print(back.top());
print(buf);
} S7
int statistics() {
L9 logit();
print(setc); S8
print(getc); S9
}
}
Figure 7.4: Extended buffer code after adding the statistics feature
of LogM ethod, PrintInstVars and InvokeLog and which can be applied on any
variation of Buffer in order to add the logging functionality:
FLogging = {L1, L2, L3, L4, L5, L6, L7, L8, L9}
B1
Log
L1
Logging
Method
PrintInstVars InvokeLog
L5 L6 L7 L8 L2 L3 L4 L9
R1 B2 S1 S2 B3 R2 B5 S7
Figure 7.5: Extended logging changes after adding the statistic code
0 1
{changes ofLogM ethod}∪
FLogging = @ {changes ofP rintInstV ars}∪ A
{changes ofInvokeLog}
0 1
{AddMethod((Buf f er, f alse, logit()), 1235465, “P eter”, “Logging”)}∪
= @ {changes ofP rintInstV ars}∪ A
{changes ofInvokeLog}
0 1
{AddMethod((Buf f er, f alse, logit()), 1235465, “P eter”, “Logging”)}∪
= @ {add statement print(var) in logit for every instance variable var in p}∪ A
{changes ofInvokeLog}
0 1
{AddMethod((Buf f er, f alse, logit()), 1235465, “P eter”, “Logging”)}∪
= @ {add statement print(var) in logit for every instance variable var in p}∪ A
{add an invocation to logit in every method of Buffer}
Building blocks
The population of a change set is represented by means of n-tuples. Each n−tuple
consists of n artifacts which belong together. For instance, a number of examples
of 2-tuples are:
(“B1”, 112)
(“B2”, 123)
(“B3”, 145)
These tuples represent for example an association of the id of a change with the
time stamp of that change. In classic set-theory, the order in which the artifacts
appear in a tuple is important. For instance, the tuple (“B1”, 112) is different
from the tuple (112, “B1”). In order to improve readability of the tuples, we opt
to use named n-tuples which contain tags mapping a certain attribute of a tuple
to a value, similar to the way the population of databases are often described. In
this notation, we can express our example 2-tuples as follows:
(id:“B100 , timestamp:112)
(id:“B200 , timestamp:123)
(id:“B300 , timestamp:145)
where id and timestamp are the attributes of the tuples and B1, B2, B3,
112, 123 and 145 are the values of those tuples. Using this notation, the order
of the artifacts in the tuples is no longer important. For instance, the tuples
(id:B1, timestamp:112) and (timestamp:112, id:B1) are considered to be iden-
tical.
We define Cp to be the set of all changes that produce a program p whenever
they are applied. The changes in this set are 6-tuples that follow the following
pattern:
(id, type, parameterList, timestamp, user, intent)
where id is the attribute specifying the unique identifier of the change object, type
is the attribute denoting the kind of the change, parameterList is the attribute
containing a list of parameters that can be used to apply the change, timestamp
is the attribute that specifies the time at which this change is instantiated, user is
the attribute that contains the information of which user instantiated this change
and intent is the attribute that contains a description of the intent of this change.
Atoms
We assume a finite set Cp of tuples and an infinite set of tuple attributes attrib(Cp ),
for the construction of formulas on the set of tuples. Changetypes is the set of all
different types of changes (as described in Section 4.3). We then define the set of
atomic formulas A[Cp ]with the following rules:
148 Expressing crosscutting concerns
00
(c1 .user = “P eter )
AddM ethod(c)
The first example means that tuple c1 has a “user” attribute and c2 has a “user”
attribute with the same value. The second example means that tuple c1 has a
“user” attribute and its value is “Peter”. The last example means that tuple c is
of the AddM ethod type. The formal semantics of such atoms is defined given a
change set Cp and a tuple attribute binding val : Cp × attrib(Cp ) → Object that
maps tuple attributes to tuple values over the domain in Cp :
1. “c1 .a = c2 .b” is true if and only if val(c1 , a) = val(c2 , b)
2. “c.a = k” is true if and only if val(c, a) = k
3. “r(c)” is true if and only if the type atrribute of c is r.
The atomic formulas denote a condition for a change object. The next step
in defining the change cut language is the construction of more complex formulas
which consist of composed and quantified atomic formulas as we explain below.
Formulas
In our change cut language, the atomic formulas defined above can be combined
into formulas, with the logical operators ∧ (and), ∨ (or) and ¬ (not), and we
can use the existential quantifier (∃) and the universal quantifier (∀) to quantify
variables or relations. We define the complete set of formulas F [Cp ] inductively
with the following rules:
1. every atom in A[Cp ] is also in F [Cp ],
2. if f1 and f2 are in F [Cp ] then the formula “f1 ∧ f2 ” is also in F [Cp ],
3. if f1 and f2 are in F [Cp ] then the formula “f1 ∨ f2 ” is also in F [Cp ],
4. if f is in F [Cp ] then the formula “¬f ” is also in F [Cp ],
5. if c in Cp and f a formula in F [Cp ] then the formula “∃c : f ” is also in F [Cp ],
6. if c in Cp and f a formula in F [Cp ] then the formula “∃!c : f ” is also in
F [Cp ],
7.3 Intensional changes 149
Change cuts
Finally, we define a change cut expression (in short a change cut) for a given
change set Cp as:
{c : f (c)}
where c is a tuple in Cp and f(c) a formula in F [Cp ]. The result of such a query
for a given change set Cp that specifies a program p is the set of all tuples c of Cp
such that f is true.
150 Expressing crosscutting concerns
which returns all the changes that add a method to a class and all changes that
add an attribute to a class respectively. Now that we are capable of expressing
change cuts, all that remains in order to enable expressing intensional changes are
the actions that need to be taken for the tuples of a change cut. This is the subject
of the following paragraph.
Actions
The purpose of intensional changes is to allow a developer to describe which
changes have to be added (in an intensional way) instead of enumerating them
(in an extensional way). As an example, we consider again the Logging feature
which we want to express as:
{AddMethod((Buf f er, f alse, logit()), 1235465, “P eter”, “Logging”)}∪
{add statement print(var) in logit for every instance variable var in p}∪
{add an invocation to logit in every method of Buffer}
Now that we have established a formal language for expressing change cuts like
“for every instance variable var in p” or “in every method of Buffer”. We only
lack a way of specifying the actions that need to be taken for all the tuples of a
change cut (e.g. add statement print(var) in logit or add an invocation to logit).
These actions consist of the addition of a change (or change set) to the change set.
We define an action as the specification of the addition of a new tuple (repre-
senting a change instance) to the tuple set Cp . We differentiate between actions
that add that tuple just before and just after a change:
1. cnew before c
2. cnew after c
where cnew is a 6-tuple (id, type, parameterList, c.timestamp, user, intent) in
which all the attributes except for the id and the timestamp must be bound
to values. Those values can be the value of another attribute of the action, or a
constant. The id is assigned to the change tuple when the action is evaluated. It
is ensured to be a unique identifier. The timestamp of the new change tuples is
determined by the keyword (before or after ) and by the timestamp of the change
c. In case the action specifies the new change to come after c, the new timestamp
is set to a timestamp which is just after the one of c. In case the action specifies
the new change to come before c, the new timestamp is set to a timestamp which
is just before the one of c. We elaborate on how the uniqueness of the id is en-
sured and how the timestamps are calculated in Section 7.3.3. As an example of
an action, we present
(?id2, AddStatement, (Buf f er, f alse, get, “logit”), ?timestamp2, “P eter”, “InvokeLog”) after
(B3, AddM ethod, (Buf f er, f alse, get), 235935, “P eter”, “InvokeLog”)
which adds a statement to the get method of the Buffer class just after the
method get is added to the Buffer class. We conclude this subsection with the
definition of an intensional change.
7.3 Intensional changes 151
{c : A | f (c)}
where the values of all tuples that are specified in the change cut can be used as
values for the attributes of the tuples in the actions of A. In order to give an
example of intensional changes, we use intensional changes in order to specify the
complete Logging feature by means of intensional changes:
{AddMethod((Buf f er, f alse, logit()), 1235465, “P eter”, “LogM ethod”)}∪
{c : {(?id, AddStatement, (Buf f er, f alse, logit, “print(c.parameterList.attribute)”),
?timestamp, “P eter”, “P rintInstV ars”) after c} |
{∀c : (AddAttribute(c) ∧ c.parameterList.class = Buf f er)}}∪
{c : {(?id, AddStatement, (Buf f er, f alse, ?m, “logit()”), ?timestamp, “P eter”, “InvokeLog”)
after c} |
{∀c : (AddM etod(c) ∧ c.method =?m ∧ c.parameterList.class = Buf f er)}}
The two intensional changes included in the definition of the Logging feature
need to be evaluated with respect to a change set in order to produce the extension
they describe. The following subsection elaborates on the evaluation of intensional
changes.
( L1 , AddMethod, ( B u f f e r , f a l s e , l o g i t ) , 2 3 5 4 6 5 , " Peter " , " LogMethod " ) 1
Listing 7.1: Extension of Logging on {Buf f er, Restore, Statistics}
( L1 , AddMethod, ( B u f f e r , f a l s e , l o g i t ) , 2 3 5 4 6 5 , " Peter " , " LogMethod " ) 1
Listing 7.2: Extension of Logging on {Buf f er, Restore}
7.3 Intensional changes 153
all change objects that result from this process are optional with respect to the
feature they belong to.
For the sake of clarity, we specified the Logging feature in a very naive way
as the specification does not consider the possibility that attributes or methods
were modified or removed by other change objects in the change set. Such naive
specification could produce change objects with subjects that no longer exist in the
software product at the time the change is applied. As the composition algorithm
takes into account the structural dependencies between the change objects, this
never produces products with invalid structure. The semantics, however, can
indeed be influenced by this naive specification. It is up to the developer to
alter the intensional change in such a situation. We come back to this issue in
Section 7.3.5 but first discuss the implementation of the change cut language and
model of intensional changes.
7.3.3 Implementation
First, we extend the change model of Chapter 4 with the notion of inten-
sional changes. Figure 7.6 shows the change model which is extended with the
Intensional Change class, which is a subclass of Change that models the new
change kind. This extension shows that the change model we presented in Chap-
ter 4 is easy to extend when new kinds of changes are concerned.
composites affectingChanges
Change
Composite timeStamp Atomic Subject
Change isApplied Change changeSubject
intent add
apply user apply remove
undo apply undo modify
undo
Add Modify Remove FamixObject
D
sourceAnchor
apply apply apply commentsAt
undo undo undo ...
Intensional
Change
apply
undo
or Java environment. The symbiosis allows one to write Smalltalk or Java code
within the declarative language which gets executed whenever that declaration is
asserted. These features make SOUL an ideal candidate for reasoning about and
creating change objects, and thus for specifying intensional changes.
Logic Kernel
Smalltalk Java
primitives primitives
Smalltalk Java
The SOUL kernel is depicted in Figure 7.7. It consists of a logic kernel to-
gether with an underlying library of basic logic primitives for every programming
language it can reason about. Two such libraries exist, namely the Library for
Code Reasoning (LiCoR) [74] for reasoning about Smalltalk code and Irish [39] for
reasoning about Java code. The logic kernel itself consists of a library of predicates
that serve for basic reasoning. They can, for instance, be used to do parse tree
traversal. The predicates in that library can be used by the developers for creating
new predicates in SOUL. Predicates can be grouped in layers, for the purpose of
classification. We create a basic layer, which contains predicates for every change
kind.
that must have the same value whenever the predicate is evaluated. Formulas
are implemented by chaining atoms. A comma represents the ∧, an alternative
definition of a predicate represents the ∨, the not() represents the ¬. As for the ∀
and ∃ quantifiers, they are implemented by means of standard SOUL predicates
f orall(?query, ?test) and exists(?query, ?test).
Third, we implement the actions. An action is specified as a SOUL predicate
that includes symbiotic Smalltalk code that is executed to instantiate the con-
cerned changes. An example of an action for adding a method before a change ?c
is presented here:
D between changes and features – remain the same, as intensional changes are
changes that can depend on multiple other changes (D) and that are contained
within one feature (F 4C). Also the change specification does not require altering
in order to include intensional changes.
With respect to the properties of our formal model, we need to modify the
definition of a legal change and feature composition. As intensional changes eval-
uate to an enumeration of changes with respect to a change set, the actual change
set has to be considered whenever an intensional change is evaluated. Because of
that, feature compositions must no longer be specified by a set, but rather by an
ordered set – a sequence. On that sequence, we define the
function, which returns true for (f1 , f2 , F ) if f1 is specified on the left side of f2 in
the sequence F . In order to express the evaluation of intensional change, we first
introduce a function eval:
eval : C × PC → PC 0 (7.1)
which returns the set of changes that corresponds to the enumeration of changes
described by an intensional change c with respect to the change set containing all
the changes that stem from features in the feature composition before the feature
of c. In case eval is called for a change that is not intensional, it is returned
unchanged in a singleton set.
Now that we have a definition of the eval operator, we can redefine the legal
change and feature compositions as:
Definition 16 (Legal change composition, legal feature sequence). A legal change
composition H is a change composition such that there exists a legal feature se-
quence G ⊆ F , which satisfies the following constraints:
• If a feature is selected, all its ancestor features must be selected before that
feature in G:
?+
∀f ∈ G • g → f ⇒ g ∈ G ∧ before(g, f, G) (7.2)
?+
in which g → f is the transitive closure of the parent features of f .
• If a feature with mandatory sub-features is selected, these need to be selected,
as well:
man
∀f ∈ G • f → g =⇒ g ∈ G (7.3)
man
• Let M = {c|f ∈ G ∧ f → c}, the set of mandatory changes and O = {c|f ∈
opt
G ∧ f → c}, the set of optional changes. We need that
– all changes that are mandatory with respect to the selected features are
included in the change set:
M ⊆H (7.4)
7.3 Intensional changes 157
H \M ⊆O (7.5)
∀c ∈ H • ∃(c, c0 ) ∈ D =⇒ c0 ∈ H (7.6)
The only difference between this algorithm and the one presented in Algo-
rithm 1 on page 115 is that the changes that depend on changes resulting from the
evaluation of intensional changes need to be retrieved in order to calculate the tran-
sitive closure of unwanted changes (Algorithm 14). This is done by Algorithm 12,
which first evaluates all changes of the change specification and afterwards com-
putes the complete set of dependencies among that complete set of changes.
158 Expressing crosscutting concerns
Note that the actual construction of a software variation requires that inten-
sional changes are evaluated before they are carried out. As these algorithms are
only used to validate compositions, they do not evaluate intensional changes for
constructing variations, but rather only output change sets that can be used to
validate and fix erroneous compositions.
Change
...
apply changes
...
AtomicChange CompositeChange
... ...
apply apply
... ... forall c in changes
c apply
RenameMethod
... ...
...
new
apply
...
7.4 Conclusion
We started this chapter by explaining that some functionality, such as logging
or error handling, are notoriously difficult to implement in a modular way and
that we name such functionality crosscutting, because they include changes which
modify software building blocks scattered over the system. We show that in our
change-based approach to FOP, the implementation of crosscutting functionality
is actually not scattered over the software application because the changes are
grouped in one change set. An inconvenience of our model, however, is that
features that implement a crosscutting functionality usually depend on more than
one feature and that a composition that contains such a feature must consequently
include all the features it depends on.
We advocate a solution based on the concept of flexible features. A feature
is considered flexible if it contains at least one optional change object. That is a
162 Expressing crosscutting concerns
change that does not have to be included in a composition in order to make the
composition valid. This principle allows a flexible feature to be partially included
in a composition that excludes some features on which the flexible feature depends.
We show that this brings about more flexibility with respect to feature composition
and that flexible features can for instance also be used to implement a facade design
pattern.
While flexible features already help in modeling crosscutting functionality, they
still suffer from some conveniences with respect to maintainability as they can only
be specified as extensional lists of changes. In order to overcome these problems,
we introduce an extension to our change model. An intensional change is a kind of
change that can be applied on a software program p in order to apply the changes
described by that intensional change to p. This application consists of two phases.
First, the intensional change needs to be evaluated with respect to the change set
Cp that specifies p. This step produces an enumeration of changes which are all
applied on p in the second step.
We present a formal language that can be used to specify intensional changes.
It is based on a tuple calculus and implemented by means of SOUL, an imple-
mentation of a Prolog-like declarative language on top of Smalltalk. Finally, we
evaluate the extension of our model with intensional changes and present the ad-
vantages and drawbacks. Benefits include that intensional changes make features
more reusable and feature composition more flexible. Drawbacks include an in-
crease in complexity of the change specification and debugging process and the
fact that the order in which the features are specified within a composition be-
came important after the introduction of intensional changes, as those changes are
evaluated with respect to a change set.
Chapter 8
Validation
The main goal of this dissertation is to validate that software can indeed be au-
tomatically modularised in feature modules if it is developed in a development
environment that records fine-grained modularisation information resulting from
development actions. In the previous chapters, we elaborated on a novel devel-
opment approach which enables bottom-up feature-oriented programming (FOP).
That approach consists of three phases: First, the software system is completely
developed in a standard object-oriented way while fine-grained modularisation in-
formation is recorded (change collection). Second, that information is used to
decompose the software system into feature modules (change classification). Fi-
nally, those modules are recomposed in order to construct variations of the software
system (change composition).
In this chapter, we validate this approach in two steps. We first elaborate
on the Change- & Evolution Oriented Programming Support (ChEOPS). It is a
proof-of-concept implementation of a development environment that is capable
of capturing fine-grained modularisation information resulting from development
actions. It is written as a plugin for the Smalltalk VisualWorks development
environment and supports all three phases (change collection, change classification
and change composition) of our approach to FOP. Afterwards, we present a case
study, which we implemented in ChEOPS and show that the resulting software
system can indeed be automatically restructured in feature modules.
Change Composer
Differentiation
The first technique to capture changes requires two versions of a (part of a) soft-
ware system and computes the changes between both by executing a command
similar to the Linux diff command on both versions. This technique is sup-
ported in ChEOPS by means of an already-existing IDE plugin called StORE.
StORE is the version control system used by the VisualWorks for Smalltalk envi-
ronment. It is based on a client-server architecture and uses a centralized server
with a database acting as the central repository. Developers have the possibility
to publish (commit) packages which will be versioned by StORE. Instead of ver-
sioning files, StORE works on a granularity-level of program entities (e.g. a class
or method) which facilitates for example the merging of source code of different
developers.
StORE also provides the functionality of comparing two versions of the same
software system and is capable of calculating and presenting the differences be-
tween those versions detailed to the method level. This is presented in Figure 8.2.
In the upper left pane of the figure, a list of classes is presented. The upper right
pane contains the methods that were added, removed (crossed out) and /or mod-
ified (crossed out and not crossed out). The lower left and right panes show the
class definition of the class respectively in both versions.
We extended the functionality of StORE in two ways. First we developed a
parser that is capable of parsing method bodies and that can detect the differ-
ences between two method bodies. Second, we implemented the functionality that
8.1 Proof-of-concept implementation 167
instantiates the corresponding change objects for all the differences between two
versions.
The current implementation of ChEOPS calculates the differences between two
method bodies in a very naive way as it sequentially compares all the statements
and produces a RemoveStatement for every statement of the old version and
an AddStatement for every statement in the new version. A more intelligent
comparison within method bodies (such as Envy [112] provides) might be better
suited, but remains a topic of future work as it is not essencial to validate our
work.
Change-oriented programming
Just like in many other IDE’s (such as Squeak or Eclipse), change-oriented pro-
gramming is already partially supported in VisualWorks: A class can be created
though interactive dialogs, or the code can be modified by means of an automated
refactoring. ChOP goes further than that, however, as it requires all building
blocks to be created, modified and deleted in a change-oriented way (e.g. adding
a method to a class, removing a statement from a method, etc).
ChEOPS provides an interactive dialog for every change kind, so that the devel-
oper can instantiate that change to engage in pure change-oriented programming.
An interactive dialog queries the developer for all the information that is required
to instantiate the concerned change object. Some of those dialogs can be triggered
from within the standard IDE. The dialog for the addition of a class, for instance,
can be triggered by right-clicking the package as illustrated in Figure 8.3.
Other dialogs can only be triggered from within the change pane of the
ChEOPS plugin. Figure 8.4 shows different change types and the instantiate
button that can be clicked in order to trigger the dialog.
Another functionality of ChEOPS allows developers to specify their own kinds
of changes, by for instance composing atomic changes into a higher order composite
change. ChEOPS only supports this principle in a textual way. A developer who
wants to declare a new change kind, must write the definition of the new change
168 Validation
kind by subclassing the composite change and implement the correct new : and
instantiate : methods for the new change kind.
Logging
ChEOPS has the capability of logging developers producing code in the standard
object-oriented way. To that regard, ChEOPS instruments the VisualWorks IDE
with hooks and uses them to instantiate first-class change objects that represent
the software development or evolution actions taken by the developer. In order to
explain how this is done, we first explain how software is developed in a standard
object-oriented way in VisualWorks for Smalltalk.
In VisualWorks for Smalltalk, there only exist three entities that can be defined:
packages, classes and methods. All other building blocks are considered a part
of one of those three. An instance variable for instance, is a part of its class
description. A developer can add or modify one of these entities by typing the
new definition of that entity in the corresponding IDE pane and by afterwards
8.1 Proof-of-concept implementation 169
clicking the accept button. Clicking this button triggers a method of the IDE that
performs the necessary actions for (re)defining that class or method. ChEOPS
overrides that method and adds the code for instantiating a change object for
every change that is detected. Note that here, in fact we are also applying a
differentiation at the level of method bodies and class definitions. In order to
perform that differentiation, ChEOPS uses the same parser that we introduced
earlier.
Classification model
The classification model is a metamodel that consists of two parts: the change
model and the actual classification model. Each part focuses on another level of
granularity. The change model describes how the changes are modeled. We refer
the reader to Section 8.1.2 for an explanation on how that model was implemented.
The actual classification model defines and describes the entities of the super-
structure which is a flexible organisational structure based on feature and change
objects (represented in Figure 5.6 on page 109). A class named Feature was imple-
mented. Instances of that class represent the actual features of a software system.
A feature has a unique id (it’s object id) and a name. While the name has to be
provided by the one instantiating the feature, the id is provided automatically by
the IDE.
The implementation of the D relation was already elaborated on in Sec-
tion 8.1.2. C4F is implemented by means of the intent attribute of the Change
instances. Every change instance has an intent, which contains a reference to the
feature the change is related to in terms of a C4F relation. The cardinality of
the C4F relation is maintained within the change instance. How the intent of a
change instance is specified depends on the classification technique that is used
and is discussed below.
The Sub relation is implemented by a dedicated class Sub. An instance of the
Sub class maintains a reference to the parent and son feature that are in a sub-
feature relationship. The cardinality of the instance, specifies whether the son
feature has to be included in a composition that includes the parent feature. How
the Sub class is instantiated depends on the on the classification strategy that is
used and will be discussed below.
170 Validation
Classification techniques
The implementation of the classification of changes and features boils down to
creating the right instances of the F eature and Sub classes, setting the intent
of change instances to the correct feature instances and setting the cardinality of
the change. There exist different techniques for classifying changes and features,
which each have their own implementation. As in this dissertation we presented
three classification techniques, we now present how ChEOPS supports these three
techniques and how we implemented them.
With respect to the Sub relation, this technique is not different from the manual
classification technique. The developer must instantiate the Sub class with the
right relations between parent and son features and set the cardinality.
Composition views
Composition correction
In some cases, the developer requires a software variation that contains incom-
patible features. In such case, ChEOPS can support the developer in taking the
right corrective actions. In order to do that, the developer should provide the
analyzeCompositionFor: method with the desired composition. In case the
composition is invalid because of some unsatisfied dependencies among the change
objects, the resulting graphical representation will contain black nodes. The black
nodes denote the spots that provoke the composition conflict. The developer can
inspect these nodes in order to obtain extra information that can assist in com-
pleting the composition. Examples of such information are which changes should
be included in order to make this composition valid or which changes would have
to be excluded from the composition in order to make it valid. Such information
can afterwards serve as an input for a reclassification of changes in features.
While not included in the actual version of ChEOPS, another functionality
with respect to composition correction, may consist of the production of a fea-
ture diagram from the changes, the features and the relations among them. As
was elaborated on in Chapter 6, a change specification can automatically be trans-
formed into a feature diagram. This feature diagram represents the product family
of the actual implementation of the software product. This might differ from the
product family the designers of the software product had in mind. The compari-
son of the generated feature diagram and the originally designed feature diagram
might reveal discrepancies, that might have to be corrected.
The final support ChEOPS provides with respect to composition correction,
lies in the intent of the software building blocks of the software system. Every
building block of a software system that was developed with ChEOPS maintains a
reference to the changes that affect it. An inspection of this list reveals why it was
created (and adapted). The list might also reveal which developer(s) “touched”
this building block. Such information can assist a developer in the process of
understanding a software system [44].
for instance, returns all the parts where ?c is bound to a change of the ChEOPS
change set and ?u is bound to the value of the smalltalk block [?c user], which
evaluates to the value of the user message that is sent to the object bound to ?c.
Just as the formulas of the change cut language do, the actions of the inten-
sional changes also use the symbiotic capabilities of SOUL. An action needs to
instantiate the ChEOPS change objects denoted by an n-tuple. Remember the
example of an action that has to produce a change object that adds a method just
before another change:
in which a new change object is bound to ?cnew after it is created by the Smalltalk
block [AddChange newMethod: ?P arameterList before:?c by:?user for:?intent].
This block, when evaluated, produces a new change instance and registers it in
the ChangeLogger class.
Now we showed how the symbiosis from SOUL to Smalltalk is used for obtain-
ing and creating ChEOPS change objects from within intensional change speci-
fications, we elaborate on how the symbiosis from Smalltalk to SOUL is used in
order to specify intensional changes from within ChEOPS. Just like all ChEOPS
change kinds, intensional change objects have to be created by instantiating a
concrete subclass of the Change class. In case of an intensional change, the
IntensionalChange class has to be instantiated. This can be done by invok-
ing the new: method on that class. The parameter of the method has to be a
sequence that denotes the actions and change cut of the intensional change. An
example of such sequence is this one:
Thanks to splitting up the eval and apply methods of the intensional changes,
one can evaluate a intensional change without applying it. This comes in handy
for the implementation of a composition algorithm that produces the maximal
change composition of a feature composition containing intensional changes – as
presented in Algorithm 9. That algorithm requires an eval function that evaluates
an intensional change without applying it.
FOText
Save Copy-Cut-
New Open Save Quit SelectAll Find
As Paste
Composition Rules
Save requires SaveAs
Open requires Save
The FODA diagram of Figure 8.5 also includes two composition rules. The
first one imposes that every text editor variation that includes the Save feature
also includes the SaveAs feature. The second one states that the Open feature
can only be included in a composition that contains the Save feature. Note, that
due to transitivity, these two rules impose that the functionality to Open a text
file, can only be included if the functionality to SaveAs is included in the product
variation.
We extend FOText with two more features (the Compress and the Logging
feature), in order to demonstrate the power of flexible features and intensional
changes. The Compress feature provides the ability to compress text files before
they are saved, and decompresses them before they are opened. The Status Title
feature displays the name of the opened file and the name of the file that is being
saved in the title bar of the FOText window. It also clears the window title bar
when the user starts a new file. We specify the latter two as flexible while the
former nine are specified as monolithic.
The Logging feature is a feature that adds logging behaviour to the text edi-
tor. It is a crosscutting functionality and involves changes that depend on many
FOText features. The composition rules state two other dependencies. The Open
feature cannot be applied without the Save feature, which in its turn can not be
applied without the SaveAs feature. The rationale of the diagram states that the
Compress feature is useful for producing a variation for an environment that has
few resources.
The UML class diagram of the complete FOText application is presented in Fig-
ure 8.6. The main class Editor has a method execute that produces an instance
of the class ApplicationWindow. It provides the window to display and edit text.
The execute method also creates an instance of the class TextEditorView which
is linked to an instance of the EditorController and KeyboardProcessor classes.
The EditorController class inherits from the TextEditorController class in-
cluded in VisualWorks for Smalltalk and which adds some functionality such as
180 Validation
Application
EditorController Editor <uses> Window
theFileName applicationName
findWindow execute
saveNow <uses>
TextEditor
setLabel
Controller <uses>
menu <uses>
about
new Keyboard
open TextEditorView Processor
print
quit
save
saveAs
a method menu which is used to launch the FOText methods that implement the
different features. The KeyboardProcessor captures the events originating from
the keyboard and is linked to an ApplicationWindow to embed the text area into
the window.
application. Some of them, however, also introduce modifications (e.g. the Open
feature modifies the menu method introduced by the Base feature) and removals
(e.g. the Compress feature deletes several statements and introduces new ones
within existing methods).
Figure 8.7 presents a ChEOPS view which hierarchically presents the change
objects captured for implementing the Base feature. It contains additions of
classes, methods, instance variable or statements and and removals of methods
and statements. The figure shows that (a) our model is capable of expressing
features that include deletions of program building blocks, (b) that our model al-
lows features to specify changes up to the level of statements. Finally, we showed
that we were able to do feature-oriented programming in a bottom-up way by
programming in a standard object-oriented way (the Smalltalk way) in a stan-
182 Validation
A valid composition
In this first scenario, we want a variation of FOText that includes all the features
with the exception of the logging functionality, which we will add later in this
chapter. Our tool informs that this composition is valid (there were no unsatisfied
dependencies) and depicts the change composition graph of Figure 8.8.
This composition involves all features except Logging and is specified by 1260
changes.
A graphical overview of the changes of a valid composition, such as the one
shown in Figure 8.8 hints graphically at the size of all participating features. Other
uses of such a diagram might exist, but do not reside in the scope of this research.
As we “only” want to validate and produce program variations, the layout of the
changes of a valid composition does not seem useful and can be avoided in order
to significantly speed up the variation validity checking and composition process.
An invalid composition
The second composition involves the Base and Save features. Figure 8.9 depicts
the result of this composition: The changes belonging to the Base and Save fea-
tures are respectively depicted as red and green circles. The black nodes represent
the change objects that belong to the features in the composition which have at
least one unsatisfied dependency.
The graphical view of an invalid composition (such as the one shown in Fig-
ure 8.9) is already more useful than a view on the changes of a valid composition,
as it can be used to assist programmers in debugging their compositions. An in-
spection of the black nodes of the diagram of Figure 8.9, illustrates that there are
8.2 Validation: FOText 183
four changes from the Save feature that depend on changes of the SavesAs fea-
ture. Consequently, in this implementation of FOText, the Save feature cannot be
included in a composition without including at least the SavesAs feature. In case
this dependency is not desired, the developer can use the fine-grained information
of the inspected black first-class change objects to adapt the implementation of
the relevant features.
Note that the fact that Save depends on SaveAs is also included in the second
composition rule of the FODA diagram of Figure 8.5. The reason why these fea-
tures are dependent (the four changes of Save that depend on changes of SaveAs),
however, is not included in the FODA diagram and only becomes apparent in the
view of Figure 8.9. This shows that the problem and solution spaces are connected
184 Validation
in our approach, and that this connection can be used for assisting the developer
in correcting non-valid compositions.
SaveAs and Compress are respectively depicted as green circles, blue circles and
yellow boxes. The composition is valid, but one of the changes of the Compress
feature had to be omitted from the composition as it had an unsatisfied depen-
dency. Since that change was optional with respect to its parent, it was omitted
from the composition in order to make the composition valid.
Note that the composition diagram in Figure 8.10 contains some gray nodes
that belongs to the Compress feature. The gray nodes denote the change objects
that were omitted from the composition due to at least one unsatisfied dependency
186 Validation
they have. The nodes can be inspected by the developer in order to verify why
they were not included. An inspection of the change shows that it depends on a
change of the Open feature.
In the fourth composition, we add the flexible Compress feature to a viewer
version of FOText which is composed of the monolithic Base and Open features.
The result of this composition is depicted by the diagram of Figure 8.11. Changes
of Base, Open and Compress are respectively depicted as green circles, blue circles
and yellow boxes. In this composition, several changes of the flexible Compress
feature are grayed out and omitted from the composition (because they depend
on changes that belong to the SaveAs feature).
A closer inspection of the gray entities of both figures 8.10 and 8.11 teaches
us that different change objects of the Compress feature are omitted from the
8.2 Validation: FOText 187
composition depending on the composition the Compress feature belongs to: C259
in Figure 8.10 and C363, C365, C372, C373 and C377 in Figure 8.11. Those change
objects are omitted from the composition because they depend on at least one
change object that does not reside within the composition. C259 consists of the
addition of a statement to the open method, which is originally added by O219
in the Open feature. It is omitted as the Open feature and its changes are not
included in the composition of Figure 8.10.
Similarly, C363, C365, C372, C373 and C377 are changes that respectively de-
pend on S246, S249, S249, S248 and S247, and which are automatically omitted
from the composition as the SaveAs feature is not included in the composition of
Figure 8.11. This demonstrates how our approach and tools automatically cus-
tomize the deployment of flexible features in order to make compositions valid. It
shows how this approach supports the construction of compositions that would not
be permitted by other FOP approaches, but which do make sense. Consequently,
this validates that our model supports the customized feature deployment, which
improves the reusability of feature modules.
• Development: It turned out that forward tagging the changes in the right
way was not always that easy from the start. At some point, while developing
the Save feature, we realised that some functionality was missing in the
SaveAs feature. Consequently, we had to “modify” the SaveAs feature by
adding some changes to it. In practice, we first had to tell ChEOPS that we
were developing the SaveAs feature again, so that it could forward tag the
upcoming changes in the right way. Afterwards, we could make the changes
8.3 Lessons learned 189
that were required to “modify” the SaveAs feature. This observation makes
us believe that the development of features is an iterative process, which had
to be supported by ChEOPS.
quired time of the verification algorithm only grows linearly with the number
of changes. Still, the number of changes is quite high, considering that FO-
Text is an application of +- 1 KLOC. We realise that the high number of
changes might hinder scalability.
8.4 Conclusion
The thesis of this dissertation is that software can be automatically restructured
in feature modules if it is developed in a development environment that records
fine-grained modularisation information resulting from development actions. This
chapter consists of two steps for validating that hypothesis. We first discuss a
proof-of-concept implementation of a development environment that records fine-
grained modularisation information and than show how an application developed
in that environment can indeed be automatically restructured in feature modules.
The Change- and Evolution- Oriented Programming Support (ChEOPS) is a
tool-suit which we created in VisualWorks for Smalltalk – an interactive develop-
ment environment for Smalltalk. ChEOPS is a VisualWorks plugin that supports
techniques such as differentiation, change-oriented programming and logging for
obtaining change objects. It supports manual, semi-automatic and automatic
classification of changes in features and allows to specify features to be flexible or
monolithic. While a flexible feature will by default only have optional children, a
monolithic feature will by default have only mandatory children.
ChEOPS supports the composition of program variations. The developer only
has to specify the desired functionality, after which ChEOPS can automatically
produce the corresponding variation. For that, ChEOPS first composes the set of
change objects that corresponds to the desired variation and afterwards applies
those changes in order to get the desired program variation. The current ChEOPS
implementation includes only one composition algorithm which produces the max-
imal composition of a variation. We explain how the implementation has to be
adapted in order to add other composition algorithms.
ChEOPS provides two kinds of support with respect to debugging faulty com-
positions. First, ChEOPS is capable of producing a change diagram that is based
on the implementation. As we have demonstrated in Chapter 6, this change di-
agram is automatically transformable to a feature diagram, that can possibly be
8.4 Conclusion 191
compared to the feature diagram that was intended for the application. When dis-
crepancies are detected, the appropriate actions can be taken. Second, ChEOPS
provides support for retrieving the reason of a failure when a specification of a soft-
ware variation results in an invalid change composition. It uses the fine-grained
implementation information that is contained within the change objects to assist
the developer in taking appropriate corrective actions.
We show that ChEOPS is coherent with the formal model on which we elab-
orated in Chapter 6. It provides an implementation for changes, features and all
the relations between them and contains an implementation of the maximal com-
position algorithm. Intensional changes are integrated in ChEOPS by linking the
fact base of SOUL to the changes that are collected in ChEOPS and by instanti-
ating the right change classes from within SOUL whenever new changes have to
be added by it.
The second part of the validation introduces FOText: an application which we
developed in order to validate our bottom-up approach to FOP. FOText is a text
editor that consists of 16 features of which three are mandatory and the rest is
optional. We developed it in a standard object-oriented way and used ChEOPS
to log our development actions. The development of the complete application re-
sulted in approximately 1250 changes and 1350 dependencies. The changes show
to be expressive building blocks of features, as they can express additions, modi-
fications or deletions and because they can be specified on the level of granularity
of statements. They allow for a fine-grained control of how features are specified.
Afterwards, we let ChEOPS classify the changes in features and made six
compositions that each represent one product variation of FOText. We use the
graphical views on change compositions to obtain information about the invalid
compositions and show how the fine-grained control over changes entails infor-
mation that can be used to find out why some feature compositions are invalid.
Finally, we show how crosscutting functionality can be modularised and speci-
fied by means of flexible features and intensional changes in order to increase the
reusability of feature modules in different compositions. The findings of this second
part acknowledge that FOText was automatically decomposed in feature modules
which could afterwards be recomposed to form product variations of FOText.
Chapter 9
Future Work
operations can be used to recover the transitive closure of change operations that
must be redone before redoing c (cascading redo). We included an implementation
of the cascading redo in ChEOPS.
In some cases, the undoing or redoing of a change, brings along a large cascade
of changes that will also have to be respectively undone or redone. In some cases,
it is desirable to estimate the impact the undoing or redoing of a change operation
might have, before actually carrying it out. The study of impact estimation is
called impact analysis. We strongly believe that the dependencies between the
change operations can be exploited to help predicting the impact of redoing or
undoing a certain change.
In Chapter 7, we elaborated on intensional changes. Those changes can also
be used to express intensional undo statements, which can express requests like:
“undo all changes applied by Peter that were done on or before March 23, 2009”.
While ChEOPS already supports the expression of such queries by means of SOUL,
we did not yet test how they are defined and applied in practice. A more extensive
study might expose more difficulties, that must be investigated in this track of
future work.
This dissertation is about the modularisation of software systems. Concretely,
we modularise a software system in such a way that modules represent a function-
ality and that they can be composed to form variations of the software system
that offer different combinations of functionality. Software systems can also be
modularised in other ways. They can for instance be modularised in such a way
that the degree of coupling between the modules is minimised. This degree can
be measured by the number of dependencies that hold between the changes of
the different modules. Clustering techniques can most probably be used for doing
that.
Runtime evolution is another field in the domain of software evolution in which
we feel confident contributing to with the notion of change objects that encapsulate
development actions. In [34] we introduced the idea of change-oriented advanced
round-trip engineering as a technique to support runtime changes, automated test-
ing and refactorings in the context of Agile Software Development (AgSD). We
propose to represent changes applied to a system under development, as first-class
objects and envision the integration of a change management system into an exist-
ing methodology for AgSD called Advanced Round-Trip Engineering (ARTE) [85].
We explain how Change-Oriented ARTE allows capturing, visualising, replaying
and rewinding changes that have been applied on the modelling, implementa-
tion and runtime views of an ARTE environment, and automatically synchronizes
them with other views. In this setup tests and refactorings can be composed out of
changes, while runtime change propagation is realized with different propagation
strategies.
9.4 Formalism
The elaboration of the formal ChOP model led us to take a high-level look at
ChOP, independently from an implementation. This allowed us to identify new
9.5 Deriving intensional changes 197
environment. The rules of the rule base consist of an “IF” (denoting a condition)
and a “THEN” part (denoting an action). Both parts consist of change templates,
to which the change instances may match. Whenever a change is instantiated from
within the development environment (by change-oriented programming, logging
or differentiation), the rule base is checked for possible inconsistencies and the
developer is proposed the action included in the “THEN” part of the violated
design contract rule.
In the scenario from above, the rule would be “IF AddMehod(?class, ?class-
Side, =) THEN AddMehod(?class, ?classSide, hash)”, which states that in case
a method = is added to any class, a method hash should be added to the same
class. Note that an inverse rule should also be included as this particular design
contract is symmetric. In case a developer instantiates a change that adds a =
method to any class, he is suggested to also add a hash method to that same class.
Different suggestion strategies are conceivable. The suggestion can for instance
be made proactively or on demand (being less intrusive). The advantages and
inconveniences of these strategies remain the subject or future work.
In this chapter, we have enumerated some tracks of future work. While some
of them consist of enhancements to the conceptual and technical contributions
that we made, others elaborate on the application of our research results in other
fields of the software engineering research domain. By enumerating some tracks
of future work, I realised that research never ends, but that I will always strive to
find closure.
Chapter 10
Conclusions
The objective of this work has been the bottom-up modularisation of software sys-
tems around the functionality they provide. Since the modularisation of a software
system comprises too many aspects to handle in a dissertation the scope of this
work has been narrowed to the modularisation in a context of program variation.
The roots of this research being the research on change-oriented programming
have driven further scope reduction.
The result is that this work has three foci of attention: First, the recording of
modularisation information – which is lost if it is not made explicit at develop-
ment time; Second, the bottom-up approach to feature-oriented programming –
which provides an alternative for all top-down approaches. This topic includes the
classification of software building blocks into modules that represent the different
functionality a software system provides and which can be used afterwards to con-
struct software variations with different combinations of functionality; Third, the
support for a multi-dimensional separation of concerns – which tackles the tyranny
of the dominant decomposition.
10.1 Summary
The subject of this dissertation is to manage bottom-up program variation in
object-oriented systems. In Chapter 2, we present background material on the
research domains directly related to this work: software modularisation by feature-
oriented or aspect-oriented programming and the reification of change into first-
class change objects. Our thesis is that software can be automatically restructured
in recomposable feature modules if it was developed in a software development
environment that records fine-grained modularisation information resulting from
development actions.
It centralises change as the main development entity and can be applied to pro-
gramming paradigms such as object-oriented programing. When developing in a
ChOP way, developers have to instantiate and apply changes in order to develop
their software systems. A software system in turn, is specified by the sequence of
changes that was applied to produce it.
The goal of Chapter 4 is to establish a model that allows expressing the evolu-
tion of a computer application as first-class objects. We start out from FAMIX: a
model which captures the common features of different object-oriented program-
ming languages needed for software re-engineering activities [28, 31, 107]. We
create a model of first-class change classes which is based on the FAMIX model
and incorporate the notion of dependencies between different change operations in
the model. The result is an evolution model: a model that can be used to express
the evolution of software programs written in one of the programming languages
adhering to FAMIX.
more than one composition strategy. We expose a weakness of our change model
which is caused by the fact that features always consist of explicit enumerations
of change objects. We present a solution for that issue, and call it intensional
changes: descriptive changes which can evaluate to an enumeration of changes.
We explain how such changes can be used to model crosscutting concerns and
show how they increase robustness to variability.
In order to validate our work, Chapter 8 presents a proof-of-concept implemen-
tation of the evolution model and unveils ChEOPS. It is a tool that supports two
techniques of recording modularisation information. First, it allows a developer
to apply ChOP in a context of object-oriented software development. All kinds of
first-class change objects defined by the evolution model can be instantiated from
within ChEOPS. Second, ChEOPS supports logging. For that, we instrumented
an interactive development environment in such a way that change objects are cre-
ated whenever a development action is performed. ChEOPS, includes a graphical
user interface which allows visualising and reasoning over compositions of change
objects. The chapter concludes with an evaluation of the implementation of a text
editor called FOText, which we developed using our bottom-up approach. We
show how ChEOPS can be used to validate and produce variations of FOText and
discuss some benchmarks related to the production of a handfull of variations.
10.2 Contributions
We conclude by listing the contributions we made while doing the research for this
dissertation:
• Evolution model – The dissertation includes a presentation of a generic
model that can be used to encapsulate the information related to the evo-
lution of object-oriented class-based systems. This model encapsulates de-
velopment operations as change objects: first-class entities that each de-
note a development action. The evolution model is based on an extended
FAMIX model and is capable of capturing and reproducing the evolution
of any software program written in a programming language that adheres
to FAMIX (such as Java, Smalltalk or C++). The model is capable of ex-
pressing changes down to the level of statements, allows the declaration of
changes that add, modify or delete program building blocks and supports
the management of dependencies between the change objects.
• Classification model and techniques – The software classification model
provides simple concepts for organising software systems in manageable mod-
ules that can afterwards be recomposed. The software classification tech-
niques provide strategies to set up and recover those modules. Three clas-
sification strategies are presented in this dissertation: manual classification,
semi-automatic classification based on clustering and automatic classification
through development action annotations.
Very important in this work is the integration of software classification in the
software development environment and in the software development process.
204 Conclusions
[10] Don S. Batory. A tutorial on feature oriented programming and the ahead
tool suite. In GTTSE, pages 3–35, 2006.
[13] Thomas Berlage. A selective undo mechanism for graphical user interfaces
based on command objects. ACM Transactions on Computer-Human Inter-
action, 1(3):269 – 294, September 1994.
[14] Koen Bertels, Philip Vanneste, and Carlos De Backer. A cognitive model of
programming knowledge for procedural languages. In ICCAL ’92: Proceed-
ings of the 4th International Conference on Computer Assisted Learning,
pages 124–135, London, UK, 1992. Springer-Verlag.
[15] Grady Booch, James Rumbaugh, and Ivar Jacobson. The Unified Modeling
Language User Guide. Addison-Wesley, 1997.
[17] John Brant and Don Roberts. Refactoring browser. Technical report,
http://wiki.cs.uiuc.edu/RefactoringBrowser, 1999.
[20] P. Centonze, R.J. Flynn, and M. Pistoia. Combining static and dynamic
analysis for automatic identification of precise access-control policies. 23th
Computer Security Applications Conference, 2007.
[37] Niklas Eén and Niklas Sörensson. An extensible sat-solver. Theory and
Applications of Satisfiability Testing, pages 502–518, 2004.
[38] Tzilla Elrad, Mehmet Aksit, Gregor Kiczales, Karl Lieberherr, and Harold
Ossher. Discussing aspects of aop. Communications of the ACM, 44(10):33–
38, October 2001.
[39] Johan Fabry and Tom Mens. Language independent detection of object-
oriented design patterns. Computer Languages, Systems and Structures,,
30(1-2):21–33, April 2004.
[40] François Fleuret. Fast binary feature selection with conditional mutual in-
formation. J. Mach. Learn. Res., 5:1531–1555, 2004.
[43] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design
Patterns. Addison-Wesley, 1994.
[45] Object Management Group. Unified modeling language 1.3. Technical re-
port, Rational Software Corporation, June 1999.
[47] Johannes Henkel and Amer Diwan. Catchup!: capturing and replaying refac-
torings to support api evolution. In ICSE ’05: Proceedings of the 27th in-
ternational conference on Software engineering, pages 274–283, 2005.
[48] Michi Henning and Steve Vinoski. Advanced CORBA Programming with
C+. Addison-Wesley, 1999.
[49] Michael Van Hilst and David Notkin. Using role components to implement
collaboration-based designs. In Proceedings of the 11th ACM SIGPLAN
Conference on Object Oriented Programming Systems Languages and Appli-
cations, pages 359–369, 1996.
BIBLIOGRAPHY 211
[52] Jim Hugunin. The next steps for aspect-oriented programming languages.
Technical report, Xerox Palo Alto Research Center, 2001.
[53] Guillermo Jiménez-Pérez and Don Batory. Memory simulators and software
generators. In SSR ’97: Proceedings of the 1997 symposium on Software
reusability, pages 136–145, New York, NY, USA, 1997. ACM.
[56] Andy Kellens. Maintaining the causality between design regularities and
source code. PhD thesis, Vrije Universiteit Brussel, 2007.
[57] Andy Kellens, Kim Mens, Johan Brichau, and Kris Gybels. Managing the
evolution of aspect-oriented software with model-based pointcuts. In Dave
Thomas, editor, Proceedings of the 20th European Conference on Object-
Oriented Programming, volume 4067. Springer Verlag, 2006.
[59] Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm,
and Willian G. Griswold. An overview of aspectJ. In Proceedings of the
European Conference on Object-Oriented Programming, Lecture Notes in
Computer Science,, volume 2072, pages 327 – 353. Springer Verlag, 2001.
http://aspectj.org.
[60] Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Videira
Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented programming.
In Proceedings of the European Conference on Object-Oriented Programming.
Springer-Verlag, June 1997.
[61] Gregor Kiczales and Mira Mezini. Aspect-oriented programming and modu-
lar reasoning. In ICSE ’05: Proceedings of the 27th international conference
on Software engineering, pages 49–58, New York, NY, USA, 2005. ACM.
[62] Milan Kratochvı́l and Charles Carson. Growing Modular. Mass Customiza-
tion of Complex Products, Services and Software. Springer, March 2005.
212 BIBLIOGRAPHY
[63] Leslie Lamport. Time, clocks and the ordering of events in a distributed
system. Comm. ACM, 21(7), 1978.
[66] Karl Lieberherr, Doug Orleans, and Johan Ovlinger. Aspect-oriented pro-
gramming with adaptive methods. Comm. ACM, 44(10):39–41, 2001.
[67] Adrian Lienhard, Stéphane Ducasse, and Tudor Gı̂rba. Object flow analy-
sis - taking an object-centric view on dynamic analysis. In Proceedings of
International Conference on Dynamic Languages, pages 121 –140, 2007.
[68] Jia Liu, Don Batory, and Christian Lengauer. Feature oriented refactoring
of legacy applications. In ICSE ’06: Proceedings of the 28th international
conference on Software engineering, pages 112–121, New York, NY, USA,
2006. ACM.
[69] Jia Liu, Don Batory, and Srinivas Nedunuri. Modeling interactions in fea-
ture oriented software designs. In Stephan Reiff-Marganiec and Mark Ryan,
editors, FIW, pages 178–197. IOS Press, 2005.
[71] Roberta Mancini, Alan Dix, and Stefano Levialdi. Reflections on undo.
Technical report, Dipartimento di Scienze dell’Informazione, Universita degli
Studi di Roma “La Sapienza”, Via Salaria 113, 00198, Rome, Italy, 1996.
[72] Tomi Männistö, Timo Soininen, and Reijo Sulonen. Modeling configurable
products and software product families. In in Proc. of the International Joint
Conference on Artificial Intelligence (IJCAI-2001) - Workshop on Configu-
ration, 2001.
[73] Friedemann Mattern. Virtual time and global states of distributed systems.
In Parallel and Distributed Algorithms, pages 215–226. North-Holland, 1989.
[74] Kim Mens, Isabel Michiels, and Roel Wuyts. Supporting software devel-
opment through declaratively codified programming patterns. Journal on
Expert Systems with Applications, 23(4):405–413, 2002.
[75] Tom Mens and Tom Tourwé. A survey of software refactoring. IEEE Trans.
Softw. Eng., 30(2):126–139, 2004.
BIBLIOGRAPHY 213
[76] Andreas Metzger, Patrick Heymans, Klaus Pohl, Pierre-Yves Schobbens, and
Germain Saval. Disambiguating the documentation of variability in software
product lines: A separation of concerns, formalization and automated analy-
sis. In Proceedings of the 15th IEEE International Requirements Engineering
Conference (RE’07), pages 243–253, New Delhi, India, October 2007.
[77] Michael Meyer, Tudor Gı̂rba, and Mircea Lungu. Mondrian: an agile in-
formation visualization framework. In SoftVis ’06: Proceedings of the 2006
ACM symposium on Software visualization, pages 135–144, New York, NY,
USA, 2006. ACM.
[78] R.T. Mittermeir. Facets of software evolution, 2006.
[79] Sathit Nakkrasae and Peraphon Sophatsathit. A formal approach for specifi-
cation and classification of software components. In SEKE ’02: Proceedings
of the 14th international conference on Software engineering and knowledge
engineering, pages 773–780, New York, NY, USA, 2002. ACM.
[80] OMG. Omg unified modeling language (omg uml) infrastructure. Technical
Report formal/2009-02-04, OMG, 2009.
[81] OMG. Omg unified modeling language (omg uml), superstructure. Technical
Report formal/2009-02-02, OMG, 2009.
[82] Workshop on Advanced Separation of Concerns in Object-Oriented Systems
(OOPSLA 2001), 2001.
[83] Ro Orso, Taweesup Apiwattanapong, James Law, Gregg Rothermel, and
Mary Jean Harrold. An empirical comparison of dynamic impact analysis
algorithms. In In Proceedings of the International Conference on Software
Engineering, pages 491–500, 2004.
[84] Harold Ossher and Peri Tarr. Using subject-oriented programming to over-
come common problems in object-oriented software development/evolution.
In Proc. 21st Int’l Conf. Software Engineering, pages 687–688. IEEE Com-
puter Society Press, 1999.
[85] Ellen Van Paesschen. Advanced Round-Trip Engineering. PhD thesis, Vrije
UNiversiteit Brussel, 2006.
[86] Andy Podgurski and Lori A. Clarke. A formal model of program dependen-
cies and its implications for software testing, debugging, and maintenance.
IEEE Transactions on Software Engineering, 16(9):965 – 979, 1990.
[87] Klaus Pohl, Günter Böckle, and Frank van der Linden. Software Product
Line Engineering: Foundations, Principles and Techniques. Springer, 2005.
[88] Klaus Pohl, Gunter Bockle, and Frank van der Linden. Software Product
Line Engineering: Foundations, Principles and Techniques. Springer, July
2005.
214 BIBLIOGRAPHY
[90] Atul Prakash and Michael J. Knister. A framework for undoing actions in
collaborative systems. ACM Transactions on Computer-Human Interaction,
1(4):295 – 330, 1994.
[92] H. G. Rice. Classes of recursively enumerable sets and their decision prob-
lems. Transactions of the American Mathematical Society, 74(2):358 – 366,
March 1953.
[96] Barbara G. Ryder and Frank Tip. Change impact analysis for object-
oriented programs. In PASTE ’01: Proceedings of the 2001 ACM SIGPLAN-
SIGSOFT workshop on Program analysis for software tools and engineering,
pages 46–53, New York, NY, USA, 2001. ACM.
[98] Nathanael Shärli, Stéphane Ducasse, Oscar Nierstrasz, and Andrew Black.
Traits: Composable units of behavior. Technical report, Oregon Graduate
Institute School of Science and Engineering, 2002.
[101] Maximilian Stoerzer and Juergen Graf. Using pointcut delta analysis to
support evolution of aspect-oriented software. In ICSM ’05: Proceedings
of the 21st IEEE International Conference on Software Maintenance, pages
653–656, Washington, DC, USA, 2005. IEEE Computer Society.
BIBLIOGRAPHY 215
[102] Maximilian Störzer and Christian Koppen. Pcdiff: Attacking the fragile
pointcut problem, abstract. In European Interactive Workshop on Aspects
in Software, Berlin, Germany, September 2004.
[104] Peri Tarr, Harold Ossher, William Harrison, and Jr. Stanley M. Sutton. N
degrees of separation: multi-dimensional separation of concerns. In ICSE
’99: Proceedings of the 21st international conference on Software engineer-
ing, pages 107–119, New York, NY, USA, 1999. ACM.
[105] Sahil Thaker, Don Batory, David Kitchin, and William Cook. Safe compo-
sition of product lines. In GPCE ’07: Proceedings of the 6th international
conference on Generative programming and component engineering, pages
95–104, New York, NY, USA, 2007. ACM.
[108] Laurence Tratt and Roel Wuyts. Guest editors’ introduction: Dynamically
typed languages. IEEE Software, 24(5):28–30, 2007.
[110] Tijs van der Storm. Generic feature-based composition. In Markus Lumpe
and Wim Vanderperren, editors, Proceedings of the Workshop on Software
Composition (SC’07), volume 4829 of LNCS. Springer, 2007.
[112] John M. Vlissides, James O. Coplien, and Norman L. Kerth, editors. Pattern
Languages of Program Design 2. Addison–Wesley, Reading, MA, 1996.
[114] Roel Wuyts. Roeltyper, a fast type reconstructor for smalltalk. Technical
report, Université Libre de Bruxelles, 2005.
4. Peter Ebraert, Jorge Antonio Vallejos Vargas, Pascal Costanza, Ellen Van
Paesschen and Theo D’Hondt. Change-Oriented Software Engineering, In
”Proceedings of the 2007 International Conference on Dynamic Languages”,
published by ACM, 2007
5. Jorge Antonio Vallejos Vargas, Peter Ebraert, Brecht Desmet, Tom Van Cut-
sem, Stijn Mostinckx and Pascal Costanza. The Context-Dependent Role
Model, In ”Proceedings of the 7th IFIP International Conference on Dis-
tributed Applications and Interoperable Systems”, published by Springer
Verlag, 2007
218 List of Publications
10. Peter Ebraert, Yves Vandewoude, Theo D’Hondt and Yolande Berbers. Pit-
falls in unanticipated dynamic software evolution, In ”Proceedings of the
2rd Workshop on Reflection, AOP and Meta-Data for Software Evolution”,
published digitally, 2005
11. Peter Ebraert and Eric Tanter. A Concern-based Approach to Dynamic Soft-
ware Evolution, In ”Proceedings of the Dynamic Aspects Workshop”, pub-
lished digitally, 2004
12. Peter Ebraert and Tom Tourwe. A Reflective Approach to Dynamic Software
Evolution, In ”Proceedings of the 1st Workshop on Reflection, AOP and
Meta-Data for Software Evolution”, published digitally, 2004
13. Peter Ebraert, Tom Mens and Theo D’Hondt. Enabling Dynamic Software
Evolution through Automatic Refactorings, In ”Proceedings of the Workshop
on Software Evolution Transformations”, published digitally, 2004
14. Eric Tanter and Peter Ebraert. A Flexible Approach to Interactive Runtime
Inspection, In ”1st Workshop on Advancing the State-of-the-Art in Runtime
Inspection”, published digitally, 2003
2. Yves Vandewoude, Peter Ebraert, Theo D’Hondt and Yolande Berbers. In-
fluence of type systems on dynamic software evolution, In ”Poster proceed-
ings of the International Conference on Software Maintenance”, published
by IEEE Computer Society, 2005
3. Kris Steenhaut, Peter Ebraert, Jes Fink-jensen and Ann Nowe. Introducing
Elements Of Knowledge Management For E-learning, In ”Proceedings of the
IADIS International Conference”, published by IADIS, 2002
Biography
Peter Ebraert was born on January 14, 1980 in Brussels, Belgium. He holds a
licentiate’s degree of Science in Applied Computer Science, a European Master in
Object-Oriented Software Engineering degree and a Master in Business Adminis-
tration – all from the Vrije Universiteit Brussel. He graduated cum laude in July
2001 with a thesis titled “Program suggestions based on Community-Profiles”, su-
pervised by Prof. Theo D’Hondt. The same year, he started working in the IT sec-
tor while pursuing his economics studies in the evening. In July 2002, he obtained
his second diploma. After handing in a thesis titled “Tool Support for Partial
Behavioral Reflection” – which was again supervised by Prof. Theo D’Hondt – he
obtained his third diploma with magna cum laude. In January 2004, Peter started
working as a researcher in the PROG (programming technology) research group
at the VUB department of Computer Science and was funded by a grant from the
Institute for the Promotion of Innovation by Science and Technology in Flanders
(IWT). From January 2008 and on, he worked as a teaching assistent at the VUB
teaching several courses to first and second bachelor students in computer science.