Bachelor Thesis - Carnegie Mellon School of Computer Science

[Pages:56]University of Marburg

Department of Mathematics & Computer Science

Bachelor Thesis

Variability-Aware Interpretation

Author:

Jonas Pusch

October 11, 2012

Advisors:

Prof. Dr. Klaus Ostermann

University of Marburg Department of Mathematics & Computer Science

Prof. Dr. Christian Ka?stner

Carnegie Mellon University Institute of Software Research

Sebastian Erdweg, M.Sc.

University of Marburg Department of Mathematics & Computer Science

Pusch, Jonas: Variability-Aware Interpretation Bachelor thesis, University of Marburg, 2012.

CONTENTS

I

Contents

List of Figures

III

List of Listings

IV

List of Abbreviations

V

1 Introduction

1

1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Variability in Programs

5

2.1 Software Product Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Variability in Product Lines . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Testing Product Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Variability-Aware Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4.1 Abstract syntax trees . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4.2 Variability representation . . . . . . . . . . . . . . . . . . . . . . 11

2.5 TypeChef Variability-Aware Parser Framework . . . . . . . . . . . . . . . 13

3 Variability-Aware Interpreter

15

3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Evaluation

31

4.1 Method Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2 Comparing Runtimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.3 Subject Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

II

CONTENTS

4.3.1 Benchmarking specific cases . . . . . . . . . . . . . . . . . . . . . 33 4.3.2 Benchmarking generated product lines . . . . . . . . . . . . . . . 34 4.4 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.1 Single cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.2 Generated product lines . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.6.1 Threats to validity . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Future Work

41

6 Related work

42

7 Conclusion

43

LIST OF FIGURES

III

List of Figures

2.1 Product-line development process. . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Time/cost-effectiveness of different development approaches. . . . . . . . 6 2.3 Variability-aware analysis in comparison to brute-force analysis. . . . . . 10 2.4 Exemplary code fragment with its corresponding AST. . . . . . . . . . . 11 2.5 Variable code fragment and the corresponding AST with variability. . . . 11 2.6 UML model of conditional classes. . . . . . . . . . . . . . . . . . . . . . . 12

3.1 Architecture of the variability-aware interpreter. . . . . . . . . . . . . . . 16 3.2 Storing conditional values. . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Variability propagation in if statements. . . . . . . . . . . . . . . . . . . 18 3.4 Variability propagation in while loops. . . . . . . . . . . . . . . . . . . . 19 3.5 Variability propagation in blocks. . . . . . . . . . . . . . . . . . . . . . . 19 3.6 Variability affecting assertions. . . . . . . . . . . . . . . . . . . . . . . . . 20 3.7 Partial trace of program execution for two specific variants and in

variability-aware fashion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.8 While language syntax. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.9 Exemplary mapping over conditional structures. . . . . . . . . . . . . . . 28

4.1 Generating all possible program variants. . . . . . . . . . . . . . . . . . . 32 4.2 Hardware setup of the benchmark system. . . . . . . . . . . . . . . . . . 35 4.3 Results for early joining benchmark. . . . . . . . . . . . . . . . . . . . . 36 4.4 Results for late splitting benchmark. . . . . . . . . . . . . . . . . . . . . 37 4.5 Boxplot of runtimes for generated product lines benchmark. Some outliers

omitted. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Variability-aware interpretation speedup in relation to the number of vari-

ants for generated product lines benchmark. . . . . . . . . . . . . . . . . 38

IV

List of Listings

2.1 Exemplary ifdef statement. . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 Code example for early joining. . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Code example for late splitting. . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Language constructs of a variability-enriched While language in Scala. . 23 3.4 Parsing while- and block statements with the TypeChef Parser Framework 24 3.5 Method for processing statements in the variability-aware interpreter. . . 26 3.6 Value representation in the variability-aware interpreter. . . . . . . . . . 26 3.7 Method for evaluating expressions in the variability-aware interpreter. . . 28 3.8 Implementation of the variability-aware store. . . . . . . . . . . . . . . . 29 3.9 Execution of statements in the plain interpreter. . . . . . . . . . . . . . . 29 4.1 Measuring wall-clock time of interpreter execution. . . . . . . . . . . . . 32 4.2 Code fragment used for measuring the effect of early joining. . . . . . . . 33 4.3 Code fragment used for measuring the effect of late splitting. . . . . . . . 34 5.1 Object orientation for the variability-aware interpreter. . . . . . . . . . . 41

V

List of Abbreviations

SPL AST AOP FOP

software product line abstract syntax tree aspect-oriented programming feature-oriented programming

VI

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download