Formalization of Design Patterns by Means of Ontologies

Abstract

Design patterns have proven to be important building blocks and means of reuse in software design. However, the mere number of available design patterns complicates the decision-making which design pattern to choose and demands tools assisting in this process. We hence propose a knowledge- based formal representation of design patterns, a representation that is ac- cessible by tools. Existing approaches to formalizing design patterns gen- erally cover solely the formal description of the structure of design pat- terns. However, an important part of a design pattern description is the intent section, because the intent describes what the design pattern does and which design problems a pattern addresses. In this work, we develop a novel approach of formalizing design patterns by their intent. The formal representation is based on OWL, the web ontology language. The devel- oped ontology can serve as support for the decision-making of choosing the right design pattern. We furthermore develop a tool that uses the ontology as a knowledge-base. The tool allows the user to visually describe design problems and gives suggestions of design patterns that solve a given design problem.

i

ii

Acknowledgements

First of all I would like to thank my supervisor Steffen Zschaler for his valuable advice, his continues encouragement and the many hints that have improved this text. I would also like to thank Sebastian for reading this work and providing valuable suggestions. Finally, I would like to thank my friends, my whole family and–most important of all–my girlfriend Tatjana for their support. I would not have been able to complete this work without you.

iii

iv

Contents

1  Introduction  1

2  Related Work  3

2.1  Classification of Design Patterns  3

2.2  Ontological and Other Formal Approaches  7

3  Design Patterns  9

3.1  The GOF Pattern Catalogue  9

3.1.1  Abstract Factory  10

3.1.2  Builder  10

3.1.3  Factory Method  10

3.1.4  Prototype  11

3.1.5  Singleton  11

3.1.6  Adapter  11

3.1.7  Bridge  11

3.1.8  Composite  12

3.1.9  Decorator  12

3.1.10  Facade  12

3.1.11  Flyweight  13

3.1.12  Proxy  13

3.1.13  Chain of Responsibility  13

3.1.14  Command  14

3.1.15  Interpreter  14

3.1.16  Iterator  14

3.1.17  Mediator  15

3.1.18  Memento  15

3.1.19  Observer  15

3.1.20  State  16

3.1.21  Strategy  16

3.1.22  Template Method  16

3.1.23  Visitor  17

  v NA  

  vi CONTENTS  

4  Ontologies  19

4.1  The Web Ontology Language OWL  21

4.1.1  Classes  21

4.1.2  Properties  22

4.1.3  Individuals  23

4.1.4  The Manchester OWL Syntax  24

4.2  Other Ontology Languages  25

4.2.1  RDF and XML  25

4.2.2  RDFS  26

4.2.3  DAML OIL  26

4.3  Conclusions  26

5  Ontology Engineering Tools  29

5.1  Prot eg e  30

5.2  Querying and Inference Approaches  31

5.2.1  SPARQL and the Jena Framework  31

5.2.2  The Pellet DIG Reasoner  33

5.2.3  RacerPro  33

5.2.4  The nRQL Query Language  34

5.3  Conclusions  36

6  Developing the DPIO  39

6.1  Knowledge-Engineering Methodology  39

6.2  Domain and Scope of the Ontology  40

6.3  Competency Questions  41

6.3.1  Meta Questions  41

6.3.2  Questions in the Domain of Design Patterns  41

6.4  Initial Vocabulary  43

6.4.1  Intent Classification  43

6.5  Modeling the Ontology  43

6.5.1  Classes  44

6.5.2  Properties  45

6.5.3  Instances  46

6.5.4  Examples of Modeled Design Problems  46

6.6  Completeness of the Ontology  51

6.7  Conclusions  52

7  Evaluation  61

7.1  Formalization of Competency Questions  61

7.1.1  Meta Questions  61

7.1.2  Questions in the Domain of Design Patterns  63

7.2  Test of the Ontology  66

7.3  Conclusions  67

CONTENTS vii

8  The Design Pattern Wizard  69

8.1  Requirements  69

8.2  Architecture  70

8.3  The Wizard User Interface  76

8.4  Conclusions  79

9  Conclusions and Future Work  81

  Bibliography  89

viii

List of Figures

2.1  Zimmer s arrangement of design patterns in layers (from 57 )  5

4.1  The semiotic triangle (inspired by 52 1 )  20

5.1  Screenshot of the Prot eg e ontology editor  30

6.1  The parent classes of the three hierarchies Design Patterns  

  Design Problems and Problem Concepts  44

8.1  Use case diagram of the design pattern wizard  70

8.2  UML component diagram of the design pattern wizard  71

8.3  UML class diagram of the model of the design pattern wizard  74

8.4  UML class diagram of the tree model of the design pattern  

  wizard  75

8.5  UML communication diagram of the design pattern wizard  76

8.6  Screenshot of the Design Pattern Wizard  77

8.7  Screenshot of the dialog constraining a problem predicate  77

8.8  Screenshot of the dialog constraining a problem concept  78

8.9  Screenshot of the result window suggesting suitable design  

  patterns  78

  ix NA  

x LIST OF FIGURES

List of Tables

2.1  Classification of Design Patterns in Scope Purpose (from 27 )  4

4.1  Boolean class constructors in OWL in DL and in Manchester  

  OWL syntax  24

4.2  Restrictions in OWL in DL and in Manchester OWL syntax  24

6.1  The GOF design patterns taxonomy  53

6.2  The design problem taxonomy  54

6.3  The problem concept taxonomy  55

6.4  The control design problem taxonomy  56

6.5  The decoupling design problem taxonomy  56

6.6  The dependency design problem taxonomy  57

6.7  The state handling design problem taxonomy  57

6.8  The variant management design problem taxonomy  57

6.9  The OWL object properties used to model design problems  58

6.10  Matrix of the design pattern descriptions  59

  xi NA  

xii LIST OF TABLES

  Listings NA  

4.1  Class definition  22

4.2  Definition of subclasses  22

4.3  Definition of an object property  22

4.4  Restriction on a property  23

4.5  Instance definition  23

4.6  Complex class expression in Manchester OWL syntax  25

5.1  Simple SPARQL query  31

5.2  SPARQL query with advanced language constructs  32

5.3  Structure of a nRQL query  34

5.6  Example TBox query in nRQL  35

5.4  Example concept query atom in nRQL  35

5.5  RacerPro response to a nRQL query  35

5.7  Response of a TBox query in nRQL  36

5.8  Example query in nRQL using a conjunction of a concept  

  query atom and a role query atom  36

6.1  Definition of the class StrategyDesignPattern  46

6.2  Definition of the class AlgorithmDecoupling  47

6.3  Definition of the class AlgorithmSelection  48

6.4  Definition of the class AlgorithmVariation  48

6.5  Definition of the class BehavioralProblem  49

6.6  Template-structure of a nRQL query to retrieve all design  

  patterns that are a solution to some design problem  49

6.7  Definition of the class GOFPattern  50

7.1  nRQL query to retrieve all design patterns defined in the  

  ontology  62

7.2  nRQL query to retrieve all problem concepts defined in the  

  ontology  62

7.3  nRQL query to retrieve all properties defined in the ontology  62

7.4  nRQL query to retrieve all datatype properties of all GOF  

  patterns  63

7.5  nRQL query to retrieve all design patterns that are a solution  

  to varying something  63

7.6  nRQL query to retrieve all design patterns that are a solution  

  to control behavior  64

  xiii NA  

xiv LISTINGS

7.7 nRQL query to retrieve all design patterns that are a solution

to varying behavior and creating a product family. . . . . . . 64 7.8 nRQL query to retrieve all design patterns that are a solution

to having nothing to do with handling state. . . . . . . . . . . 65 7.9 nRQL query to retrieve all design patterns that are a solution

to handling state but are not the memento design pattern. . . 65 7.10 nRQL query to retrieve all design patterns that belong to the

structural category. . . . . . . . . . . . . . . . . . . . . . . . . 66 7.11 nRQL query to retrieve all design problems solved by the

Decorator design pattern. . . . . . . . . . . . . . . . . . . . . 66 7.12 Result set of the query of Listing 7.7. . . . . . . . . . . . . . . 67 7.13 Result set of the query of Listing 7.9. . . . . . . . . . . . . . . 67 8.1 StringTemplate template of the SPARQL query structure. . . 72 8.2 Sample SPARQL query. . . . . . . . . . . . . . . . . . . . . . 73

Chapter 1

Introduction

Since the publication of “Design Patterns: Elements of Reusable Object- Oriented Software” [27] 1 , design patterns have proven to be important building blocks and means of reuse in software design. A design pattern “systematically names, motivates, and explains a general design that ad- dresses a recurring design problem in object-oriented systems” [27]. While the GOF-book “only” contains 23 design patterns, the authors state that “it might be hard to find the one (design pattern) that addresses a par- ticular design problem especially if the catalogue is new and unfamiliar to you.” [27]. This statement has become particularly significant with the emergence of new design patterns since the publication of the GOF-book in 1995. Current design patterns have appeared in specific application domains (J2EE patterns [10, 11, 25], User-Interface patterns [39]), as language depen- dent patterns (also called idioms), as patterns at different abstraction levels (analysis, architectural patterns), or simply as large collections of design pat- terns in pattern catalogues [17, 50]. The mere number of available design patterns complicates the decision-making which design pattern to choose and demands tools assisting in this process. In addition, the structure of design pattern representations in pattern catalogues as narrative text serves as documentations to be read by humans. It is not a suitable representation to be used by tools. For this reason, a knowledge-based formal representa- tion of design patterns is needed, a representation that is accessible by tools.

Existing approaches to formalizing design patterns generally cover solely the formal description of the structure of design patterns. However, an im- portant part of a design pattern description is the intent section. It is a short statement describing what the design pattern does and which design problems it addresses. Therefore, this is the first section a developer reads

This book has become known as the GOF-book. The four authors Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides are known as the Gang-of-Four, or simply GOF.

1

2 CHAPTER 1. INTRODUCTION

when deciding which design pattern to choose for a given design problem. To the best of our knowledge, no work exists trying to formalize the intent of design patterns. Software tools based on such a formalization could en- able users to describe their design problems using terminology defined in a knowledge-base. The knowledge-base could be developed using ontologies, specifications of conceptualizations that have been proven to be suitable means for providing knowledge of an area of interest. A tool using such a knowledge-base would simplify the usage of ontology query languages by providing an easy-to-use front-end for visually formulating design problems. Furthermore, the tool would suggest matching design patterns given the user’s design problem description.

The goals of this work are:

• to classify the 23 GOF design patterns with respect to their intent,

• to derive an ontology formalizing the developed classification,

• to build a prototypical tool using the ontology that suggests design patterns for given design problems.

The main contribution of this work is an ontology formalizing the intent of design patterns, which we call Design Pattern Intent Ontology (DPIO).

The rest of this work is organized as follows: Chapter 2 describes related work. This work either presents approaches of classifying design patterns according to different criteria or it presents approaches of formalizing the structure of design patterns by means of ontologies and other formal lan- guages. Chapter 3 introduces the concept of design patterns. We further- more present the intent and the applicability of the 23 GOF design patterns. Chapter 4 introduces ontologies. We give a definition and present some of the established ontology languages. Chapter 5 presents tools that are used in ontology engineering. This includes the ontology editor Prot´ eg´ e, reason- ers and query languages for querying the ontology. In Chapter 6 we describe the development of the Design Pattern Intent Ontology. Domain and scope of the ontology are confined, the methodology of the development process is introduced and important concepts of the ontology are enumerated. Chap- ter 7 presents the evaluation of the developed ontology. In Chapter 8 we introduce the idea of the Design Pattern Wizard, a tool utilizing the de- veloped ontology. We describe the architecture, design decisions and some features of the user interface. Finally, Chapter 9 discusses the results of this work and presents ideas and prospects on future work.

Chapter 2

Related Work

Our survey of current work in design pattern formalization indicates that no other work before has tried to classify design patterns according to their intent by using ontologies. However, interesting work exists both in the area of design pattern categorization and in the area of design pattern formal- ization. In the following sections we categorize related work as work that describes approaches to classify design patterns and work that uses ontolog- ical or other formal or semi-formal approaches to describe design patterns.

2.1 Classification of Design Patterns

Christopher Alexander [9], who developed the first design pattern language for town planning and architectural design in 1977, provided a hierarchical structure to catalogue different patterns. In 1995, the idea of design pat- terns was applied to software engineering by Gamma et al. [27] in their design pattern catalogue, consisting of 23 general purpose patterns for ob- ject oriented design (depicted in Table 2.1). The Gang-Of-Four structures the patterns by two criteria: purpose and scope. The purpose of a design pattern can be creational, structural or behavioral. The scope criterion, on the other hand, divides patterns into class and object patterns. Class pat- terns contain patterns that deal with relationships between classes and their subclasses. In contrast, object patterns mainly deal with relationships be- tween objects, which can be changed at run-time and are more dynamic.

Creational class patterns defer a part of object creation to subclasses, whereas creational object patterns defer it to another object. Structural class patterns use inheritance to build a structure whilst structural object patterns use object reference for the same purpose. Behavioral class pat- terns distribute responsibility using inheritance to describe control flow and the handling of algorithms whereas behavioral object patterns use cooperat- ing objects to carry out a task that no single object can carry out alone.

3

4

Table 2.1: Classification of Design Patterns in Scope / Purpose (from [27])

Zimmer [57] takes the graph of relationships as a base of his work. He enhances the relationship graph from [27] by adding classifications to the relationships. He defines three categories of these connections:

• The relationship X uses Y in its solution indicates that Y can help to solve the problem that is addressed by X. Y can be used as part of the solution of X. A development tool can utilize this knowledge by checking the relationship in existing designs.

• X is similar to Y indicates a similarity in the problem solved by pattern X and Y. Thus, this relationship indicates an alternative or a choice of design patterns.

• The relationship X can be combined with y can help in finding other design patterns which are useful to combine with an existing one and thereby supports the retrieval of design patterns from catalogues.

Having identified these categories, Zimmer was able to rearrange the relationship-graph to make it easer to read. He discovered that the rela- tionship uses forms an acyclic graph that gives a partial ordered set. This allows the design patterns to be arranged in layers (see Figure 2.1). The following layers were identified:

• The layer Basic design patterns and techniques contains many patterns that are connected by other patterns from higher layers by

2.1. CLASSIFICATION OF DESIGN PATTERNS 5

Figure 2.1: Zimmer’s arrangement of design patterns in layers (from [57]).

uses-relationships. This means that the basic patterns help other patterns to solve their subproblems.

• The layer Design Patterns for typical software problems con- tains more specific patterns with respect to the lower level. It is not used by patterns from the basic layer, but from patterns of the same layer and above.

• The layer Design patterns specific to an application domain contains the most specific patterns. Thus, it contains only one pat- tern from the general purpose GOF-catalogue, the Interpreter design pattern.

This layering and relationship classification gives a straightforward overview of the catalogue. Zimmer’s approach makes it possible to gain a deeper un- derstanding of pattern relationships and the internal structure of a design pattern. Because it concentrates on the relationships between design pat- terns but not on intent and applicability, this approach does not help in choosing the right design pattern for a specific purpose.

Noble in [45] takes a similar approach Zimmer’s in classifying design patterns according to the relationships between patterns. He identifies three main relationships: uses, refines and conflicts:

6

• The uses-relationship has the same meaning as in [57]. A larger pat- tern with a more global impact uses a smaller pattern. For example, the Command design pattern can use the Memento pattern to main- tain state for revokable operations. Often, this kind of relationship can be found in the Related Pattern section of a pattern catalogue.

• The refines-relationship denotes that one pattern is a specialization of a more general, more simple, or more abstract pattern. We can say that X extends pattern Y. This relationship is similar to the inheri- tance mechanisms of object oriented programming languages.

• The conflicts-relationship implies that patterns provide mutually exclusive solutions to similar problems. A design pattern that con- flicts with another one is an alternative solution for the same problem. For example, the Factory Method design pattern conflicts with the Prototype pattern because both provide a solution to the problem of subclasses redefining the classes of objects created in superclasses.

The relationships Noble developed are useful to relate different patterns to each other. When a software developer has found an appropriate de- sign pattern for his design problem he could review related patterns to find possible alternatives. However, these relationships do not help the software developer with finding this initial pattern.

Tichy [55] has developed a catalogue listing over 100 patterns. He con- centrates on the problems a pattern solve and identified the following top- level categories:

• decoupling: which refers to dividing a software system into indepen- dent parts such that the parts can be built, changed, replaced, and reused independently;

• variant management whose patterns treat different but related ob- jects uniformly by factoring out their commonalities;

• state handling whose patterns allow the generic manipulation of ob- ject state;

• control whose patterns are used to control execution and method selection;

• virtual machine whose patterns simulate processors and interpret the grammar of a language;

• convenience patterns that are used to simplify coding by placing often-repeated code into a common place;

• compound patterns whose patterns themselves are composed of other design patterns;

• concurrency which controls parallel and concurrent execution, and

• distribution whose patterns solve problems germane to distributed systems.