Formalization of Design Patterns by Means of Ontologies

Contents

1 Introduction

2 Related Work
2.1 Classification of Design Patterns
2.2 Ontological and Other Formal Approaches .

3 Design Patterns
3.1 The GOF Pattern Catalogue
3.1.1 Abstract Factory
3.1.2 Builder
3.1.3 Factory Method
3.1.4 Prototype
3.1.5 Singleton
3.1.6 Adapter
3.1.7 Bridge
3.1.8 Composite
3.1.9 Decorator
3.1.10 Facade
3.1.11 Flyweight
3.1.12 Proxy
3.1.13 Chain of Responsibility
3.1.14 Command
3.1.15 Interpreter
3.1.16 Iterator
3.1.17 Mediator
3.1.18 Memento
3.1.19 Observer
3.1.20 State
3.1.21 Strategy
3.1.22 Template Method
3.1.23 Visitor

4 Ontologies
4.1 The Web Ontology Language OWL
4.1.1 Classes
4.1.2 Properties
4.1.3 Individuals
4.1.4 The Manchester OWL Syntax
4.2 Other Ontology Languages
4.2.1 RDF and XML
4.2.2 RDFS
4.2.3 DAML+OIL
4.3 Conclusions

5 Ontology Engineering Tools
5.1 Protégé
5.2 Querying and Inference Approaches
5.2.1 SPARQL and the Jena Framework
5.2.2 The Pellet DIG Reasoner
5.2.3 RacerPro
5.2.4 The nRQL Query Language
5.3 Conclusions

6 Developing the DPIO
6.1 Knowledge-Engineering Methodology
6.2 Domain and Scope of the Ontology
6.3 Competency Questions
6.3.1 Meta Questions
6.3.2 Questions in the Domain of Design Patterns .
6.4 Initial Vocabulary
6.4.1 Intent Classification
6.5 Modeling the Ontology
6.5.1 Classes
6.5.2 Properties
6.5.3 Instances
6.5.4 Examples of Modeled Design Problems
6.6 Completeness of the Ontology
6.7 Conclusions

7 Evaluation
7.1 Formalization of Competency Questions
7.1.1 Meta Questions
7.1.2 Questions in the Domain of Design Patterns .
7.2 Test of the Ontology
7.3 Conclusions

8 The Design Pattern Wizard
8.1 Requirements
8.2 Architecture
8.3 The Wizard User Interface
8.4 Conclusions

9 Conclusions and Future Work

Bibliography

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.

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.

Chapter 1

Introduction

Since the publication of “Design Patterns: Elements of Reusable Object- Oriented Software” [27] ¹, 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 patterns39 ), 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

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égé, 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 Alexander9, 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.

illustration not visible in this excerpt

Table 2.1: Classification of Design Patterns in Scope / Purpose (from27 )

Zimmer57 takes the graph of relationships as a base of his work. He enhances the relationship graph from27 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 relationship 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

illustration not visible in this excerpt

Figure 2.1: Zimmer’s arrangement of design patterns in layers (from57 ).

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 understanding of pattern relationships and the internal structure of a design pattern. Because it concentrates on the relationships between design patterns but not on intent and applicability, this approach does not help in choosing the right design pattern for a specific purpose.

Noble in45 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:

- The uses-relationship has the same meaning as in57. 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 design 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.

Tichy55 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 independent parts such that the parts can be built, changed, replaced, and reused independently;
- variant management whose patterns treat different but related objects 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.

2.2. ONTOLOGICAL AND OTHER FORMAL APPROACHES 7

These top-level categories comprise further subcategories. The categories and their subcategories are mutually exclusive, i.e. a pattern should only belong to one category. For this reason, a category such as the compound patterns category has been introduced. Because a design pattern from such a category is composed of several patterns which belong to different categories, the compound pattern would have been placed into different cat- egories as well. The distribution of the patterns in the categories is also not balanced. Most of the patterns are located in the decoupling category, thus this category is by far the largest one. The advantage of Tichy’s catalogue is its ability to handle a large amount of patterns without feeling overwhelm- ing. It also concentrates on the problems solved by a pattern, making the catalogue ideal as a starting point to choose an adequate pattern for a given design problem.

Another interesting work was done by Birukou et al. in 200613. Their motivation is the unexperienced programmer who wants to choose the right design pattern for a given design problem. Instead of concentrating on an organizing principle for a pattern catalogue, they developed a system that assists the programmer in the choice of the right pattern. The system suggests a pattern based on the decision that other programmers have made in choosing a suitable pattern. This approach instruments the social and community aspects of programming. However, the authors assume a formal or semiformal description of the design problem to exist. Moreover, the system only works after the learning phase of the system is completed, i.e. a sufficient number of experienced programmers have contributed to the history of the selection process. The authors also have not evaluated the system with real users yet. It remains to be seen how good the system works in a real setting.

2.2 Ontological and Other Formal Approaches

Gross et.al. 28 propose an approach to graphically organize, analyze and refine non-functional requirements (NFRs) for the structuring, understand- ing, and applying of design patterns during design. Explicitly represented NFRs are used to support a “patterns-based approach to design”, by mak- ing the reasoning structures and design rationales behind a software de- sign explicit. NFRs that are discussed in design pattern descriptions (i.e. reusability, reduced coupling, consistency), are explicitly represented and the relations between NFRs are shown. The authors organize identified non-functional properties as goals to be achieved during design. These goals are organized in NFR goal graphs. Their semi-formal representation of de- sign goals provides abilities to better understand, discuss and analyze NFRs and related design decisions. While the semi-formal approach of28

ports the decision-making process of software design and the representation of NFRs, they do not have developed tool and knowledge based support yet.

Henninger et al. 32 is using an ontology-based metamodel to for- mally describe software patterns. The goal is to develop intelligent tools that provide a computational basis utilizing software patterns. As an use case they mention usability patterns. They base their core metamodel on properties such as hasProblem, hasSolution, hasContext, hasRationale, hasForces, properties that are developed from the original structure of the pattern description of9. They extend the core metamodel with properties that describe the relationships between patterns, such as uses, requires, alternative, and conflictsWith. The ontology they have developed does not so much concentrate on the support of selecting a suitable pattern for a given problem, but rather on the relationships between patterns. Fur- thermore, Henninger et.al. concentrate on the domain of usability patterns of web sites, but not on GOF patterns or design patterns in general. The main goal of their work is to define a shareable vocabulary in the domain of usability patterns. Furthermore, they do not describe how to query their ontology, nor do they describe how to model design problems in an ontol- ogy. A very similar approach to32 is44. They use ontologies to formalize hypermedia and web design patterns. The vocabulary is almost identical to 32 but includes additional concepts such as PatternComponent, Category, Problem and Solution. The scope of their work is the support of and an integration into hypermedia design tools.

Pereira de Medeiros et al.20 have developed the Kuaba Ontololgy, an ontology and design vocabulary to describe the design rationale of software design. The goal is to make explicit the decisions and justifications that have lead to a design. The formal description of the design rationale enables reuse at a high abstraction level. Important reasoning elements of the ontology are Question, Idea and Argument. The vocabulary defined in the Kuaba Ontology helps in the decision-making process of software design. Their work is not particularly focused on design patterns, but more on software design in general.

The work of Dietrich et al. 22 uses OWL to formally describe design patterns. However, only the structure of design patterns is considered, not the intent or applicability. They use their ontology to detect patterns in a piece of software, not to help in the selection process of a design pattern. Other approaches that use formal languages to describe the structure of design patterns include40 who developed a design pattern modeling lan- guage DPML, and [43, 53]. What is common to all this work is the sole concentration on the structural aspects of design patterns and the omission of the intent of design patterns.

Chapter 3 Design Patterns

A design pattern is “a solution to a problem in a context ”26. It is a way to achieve reusability in software design. As already mentioned in Section 2.1, design patterns first emerged in the context of architecture and town build- ing9. However, the idea of reusing design by applying patterns to recurring design problems has been ported to object-oriented software design by the so-called “Gang of Four” (GOF) in their book Design Patterns: Elements of Reusable Object-Oriented Software27. In the following section we summa- rize the intent and possible applications of the design patterns of the GOF book.

3.1 The GOF Pattern Catalogue

The GOF design patterns book describes a catalogue of 23 design patterns. Each description of a design pattern comprises a number of sections, includ- ing Intent, Also Known As, Motivation, Applicability, Structure, Partici- pants, Collaborations, Consequences, Implementation, Sample Code, Known Uses and Related Patterns. Sections such as Structure, Participants and Sample Code are mainly concerned with the structure of a design pattern. They are useful to apply a pattern in an application, once the selection process is finished and the developer is certain which design pattern is best suited for a given design problem. However, the main part of this work lies in the formalization of the intent of design patterns. Therefore in this section, we describe the intent and purpose of each design pattern of the GOF pattern catalogue. Other parts of a pattern description are omitted because they do not contribute to the understanding of how to choose the right design pattern for a given problem. We refer to27 for a complete description of each design pattern.

3.1.1 Abstract Factory

The intent of Abstract Factory is to “provide an interface for creating families of related or dependent objects without specifying their concrete classes”. Abstract Factory belongs to the group of Creational Patterns. The main focus of the pattern lies in the creation of product families. A typical ex- ample is the creation process of different look-and-feel classes for graphical user interfaces (GUI). There, the Abstract Factory interface provides the methods for creating the different theme widgets, and concrete factories are responsible for creating concrete widget classes of a specific theme. Clients are isolated from the product creation process, the responsibility of it is en- capsulated in the concrete factory. This makes it easy to exchange complete families of products, by simply exchanging a single concrete factory. On the other hand, it is difficult to add new kind of products, because in this case the interface of the abstract factory has to be changed or extended. Fur- thermore, all concrete factories that have implemented the Abstract Factory interface have to be altered as well.

3.1.2 Builder

The intent of Builder is to “separate the construction of a complex object from its representation so that the same construction process can create different representations”. The Builder belongs to the group of Creational Patterns. The pattern is applicable when the construction process should be independent of the representation of a complex object. This enables the existence of several representations of the complex object, without revealing the internal structure of the creation process. Often, the Builder is used for converters. Each converter encapsulates the process of creating a complex object. Clients can use different converters through a single interface. The Builder pattern serves a similar purpose as Abstract Factory in constructing complex objects. However, the Builder focusses more on constructing a complex object step by step, while the Abstract Factory constructs families of products.

3.1.3 Factory Method

The Factory Method “defines an interface for creating an object, but lets subclasses decide which class to instantiate”. It belongs to the group of Creational Patterns and enables classes to defer the instantiation process to subclasses. It is therefore also called a virtual constructor. Often, this pat- tern is used together with the Abstract Factory as the method that actually creates concrete classes. The Factory Method pattern can be applied when classes responsible for creating objects do not know the class of these ob- jects and subclasses should be able to decide which objects to create. This pattern is often used in frameworks and class libraries.

3.1. THE GOF PATTERN CATALOGUE 11

3.1.4 Prototype

The Prototype pattern “specifies the kinds of objects to create using a pro- totypical instance, and creates new objects by copying this prototype”. It belongs to the group of Creational Patterns. The key idea in this pattern is to create new instances of classes by copying (“cloning”) a prototypical instance. Thereby, the prototypical instance is getting copied and param- eterized with new values. The Prototype pattern is a competing pattern to Abstract Factory, but it can also used by Abstract Factory in providing new cloned instances from a prototypical object. The Prototype pattern is applicable when new instances of classes are expensive to create and all objects are similar to each other or when instances of classes only have a few different combinations of state.

3.1.5 Singleton

The Singleton “ensures a class only has one instance, and provides a global point of access to it”. It belongs to the group of Creational Patterns. When- ever it is important for a class that only one object is created from it, the Singleton pattern is the right choice. It provides a global view on this ob- ject and a well-defined access point for other objects. The Singleton has full control over how and when the single object is accessed. It can also be used to create more than one instance of a Singleton. In this case, the pat- tern controls how many instances are allowed of this class. The pattern is the implementation basis for many other patterns such as Abstract Factory, Builder and Prototype.

3.1.6 Adapter

The Adapter “converts the interface of a class into another interface clients expect”. It belongs to the group of Structural Patterns. Often, the Adapter is used in the domain of toolkits and frameworks. Communication between classes is based on well-defined interfaces. These interfaces cannot be altered easily, because often they are provided by a third party. The Adapter pattern enables classes with incompatible interfaces to work together by adapting one interface to the other. Another application area of the Adapter is the design of reusable classes that must be able to cooperate with unrelated or unforeseen classes.

3.1.7 Bridge

The intent of Bridge is to “decouple an abstraction from its implementation so that the two can vary independently”. It belongs to the group of Struc- tural Patterns. The Bridge pattern enables the separation of an abstraction from its implementation. This can be useful, if there is the need for more

flexibility than simple inheritance can provide, e.g., if there is more than one implementation for an interface. The management of abstraction and implementation in separate hierarchies enables the modification, extension and reuse of both hierarchies, independently. The Bridge pattern has an oppositional intent to the Adapter. Whereas the adapter makes unrelated classes work together after they are designed, the Bridge pattern is used to allow the variation of abstraction and implementation before the classes are designed.

3.1.8 Composite

The intent of Composite is to “compose objects into tree structures to repre- sent part-whole hierarchies”. It belongs to the group of Structural Patterns and allows clients to treat single objects as well as compositions of objects uniformly. The Composite pattern is applied whenever part-whole hier- archies are needed and to represent tree structures. The key idea of the Composite pattern is to represent both primitive objects and their contain- ers through an abstract interface. The operations defined in the abstract component interface defines methods for both handling primitives and com- posite objects in a unified way. The Decorator is often used together with Composite. In such a design, an abstract class will have some subclasses that are Decorators, and some that are Composites. While Composite is responsible for the object aggregation, Decorator adds, alters or extends responsibilities.

3.1.9 Decorator

The Decorator pattern “attaches additional responsibilities to an object dy- namically”. It belongs to the group of Structural Patterns and depicts a flexible alternative to subclassing for extending functionality of a class. This is especially useful if the additional functionality is not needed for every in- stance of a class, but only for individual objects. Because Decorators use the same interface as the class to be decorated, the decoration of an object is transparent to the client. Decorator delegates calls to the client by ei- ther only forwarding these calls or performing additional operations before forwarding. One disadvantage is that every method defined in the interface has to be forwarded whether it is being altered or only forwarded. Whereas Adapter changes the interface of an object, Decorator leaves the interface the same but changes the object’s responsibility.

3.1.10 Facade

The intent of Facade is to “provide a unified interface to a set of interfaces in a subsystem”. It belongs to the group of Structural Patterns. A facade is a higher-level interface that eases the use of a subsystem by providing a

3.1. THE GOF PATTERN CATALOGUE 13

single entry point to it and by providing only those methods a client needs. It delegates the calls from the subset of Facade methods to the actual methods of the subsystem. the facade also helps to simplify the communication of a client with the subsystem, because instead of knowing several classes of the subsystem the client only needs to know one facade to communicate with. Although Facade provides a single simple interface to clients, it does not hide the lower-level methods of the subsystem. In case a client needs direct access to them it is still able to directly use the methods of the subsystem. The Facade pattern also enables the layering of subsystems by providing an entry point to each subsystem level.

3.1.11 Flyweight

The intent of Flyweight is to “use sharing to support large numbers of fine- grained objects efficiently”. It belongs to the group of Structural Patterns. This pattern is useful when a large amount of objects is needed in an appli- cation, but the naive implementation would result in a high cost of memory. For example, the terminal symbols of the abstract syntax tree of an Inter- preter can be shared by using Flyweights. A Flyweight is a shared object that encapsulates some state that can be shared across some context. It is useful when the outsourcing of this state results in a decline in the number of objects needed.

3.1.12 Proxy

The intent of Proxy is to “provide a surrogate or placeholder for another object to control access to it”. It belongs to the group of Structural Patterns and defers the control of an object to a proxy object. The Proxy pattern can be used when the cost of creation and initialization is expensive. The Proxy pattern can defer the creation process until the object is actually needed. The Proxy object acts as an image that stands for the real object. There are several other use cases when to use Proxy: a protection proxy restricts the access of the original object, when objects have different access rights. A proxy can also be used as a smart reference to the original object by counting the number of references and freeing the object when there are no more references. A buffer proxy caches the access to the original object, a logging proxy logs the access and a remote access proxy provides the access to a remote object.

3.1.13 Chain of Responsibility

The Chain of Responsibility “avoids coupling the sender of a request to its receiver by giving more than one object a chance to handle the request”. It belongs to the group of Behavioral Patterns. By chaining receiver objects that are all able to handle the request, Chain of Responsibility decouples senders and receivers. The sender does not know in advance which receiver will take care of its request. The request is passed along the chain until one receiver handles it. This results in a loose coupling of sender and receiver. The possible disadvantage of this approach is that there is no guarantee that the request is taken care of by any receiver. The Chain of Responsibility pattern can be combined with Composite to chain together the parent with its children.

3.1.14 Command

The intent of Command is to “encapsulate a request as an object, thereby letting us parameterize clients with different requests, queue or log requests, and support revocable operations”. It belongs to the group of Behavioral Patterns. The Command pattern is applicable as an objectified callback function, when the creation of a command is not chronologically coupled with the execution of it, or if the execution of the command takes place in a different context. For example, an action is triggered in a user interface in response to some user input. If the action is put into a command object, the object can be passed around like any other object and can be executed in another part of the application. Mementos can be used together with the Command pattern to maintain state for revocable operations.

3.1.15 Interpreter

The intent of Interpreter is to “define a representation for the grammar of a given language along with an interpreter that uses the representation to interpret sentences in the language”. It belongs to the group of Behav- ioral Patterns. A recurring problem such as the searching for strings can be expressed as a simple language. The grammar of this language can be interpreted by the Interpreter pattern. Interpreter defines the grammar, represents sentences in this language and does the interpretation of them. This pattern makes it easy to change or extend the grammar of languages. Interpreter is applicable when the grammar is simple and efficiency is not a critical concern.

3.1.16 Iterator

The Iterator design pattern “provides a way to access the elements of an ag- gregate object sequentially without exposing its underlying representation”. It belongs to the group of Behavioral Patterns. The idea in this pattern is to hide the complexity of the aggregate object and to provide a simplified in- terface to access this object. Thereby, the traversal mechanism is separated from the object to traverse. Iterators are often used for the traversal of data structures such as lists or sets. They are also used to traverse the object structure of Composites or for the traversal of the abstract syntax tree of Interpreters. The Iterator pattern allows to access these data structures in a generic way that is independent of the internal implementation details.

3.1.17 Mediator

The Mediator pattern “promotes loose coupling by keeping objects from referring to each other explicitly, and it lets us vary their interaction in- dependently”. It belongs to the group of Behavioral Patterns and controls how objects communicate and cooperate. The Mediator pattern can help to structure and encapsulate the connection of many objects into a single me- diator object. The Mediator encapsulates collective behavior of distributed objects and therefore abstracts the cooperation of objects. A change of distributed behavior that would result in the change of all dependent dis- tributed objects can be done in one place: in the Mediator. Mediators are similar to Facades. Both are concerned with complexity handling of sub- systems. Whilst Mediator centralizes communication between colleagues, the Facade abstracts functionality of a subsystem and enables a simplified access to it.

3.1.18 Memento

The Memento pattern “captures and externalizes an object’s internal state so that the object can be restored to this state later, without violating en- capsulation”. It belongs to the group of Behavioral Patterns. The Memento pattern is applicable whenever an internal state of an object needs to be available at a later time. It provides a way to implement undo functionality. An object can be restored from the recorded state of the Memento object without exposing implementation details of this object. The Memento pat- tern can complement the State pattern. The objectified state of the State pattern can be externalized by Memento.

3.1.19 Observer

The intent of Observer is to “Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically”. It belongs to the group of Behavioral Patterns. The Observer pattern enables the notification of objects (observers), that are interested in the behavior of other objects (subjects), but it is not known how many observers exist. The Observer pattern can be used when one aspect of an abstraction is dependent on the other and both aspects should be varied independently. Observers can act as communication means between colleagues and Mediators.

3.1.20 State

The State pattern “allows an object to alter its behavior when its internal state changes. The object will appear to change its class”. It belongs to the group of Behavioral Patterns. The pattern is applicable when an object’s behavior depends on its state. State allows to alter this behavior at run- time, depending on its current state. It objectifies all state associated with an object into a separate State object. This enables easy addition of new state, because only a new subclass needs to be introduced. If the state consists of several transitions, these transitions are made explicit by the State pattern. Because State is an object, this object can also be shared among other objects. The State pattern is, in a way, the complement of the Flyweight. Where the State pattern enables the objectification of state, Flyweight explains when and how to share state.

The intent of the Strategy pattern is to “define a family of algorithms, encap- sulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it”. It belongs to the group of Be- havioral Patterns. Strategy defines an algorithm as an object that can be shared among other objects. This is useful when different algorithms need to be provided and different algorithms are appropriate at different times. The Strategy pattern makes it easy to define new algorithms and vary existing ones. An object can be configured with different algorithms and behaviors. If algorithms use data that clients should not know about, Strategies can be used to encapsulate this data and hide it from clients. Often, Strategy objects are realized as Flyweights. Strategy and Template Method are alter- native patterns. Both are concerned with algorithms. While the Strategy pattern encapsulates each algorithm in a separate object, Template Method allows to vary parts of an algorithm.

3.1.22 Template Method

The Template Method pattern “defines the skeleton of an algorithm in an operation, deferring some steps to subclasses”. It belongs to the group of Behavioral Patterns. Template Method allows subclasses to redefine certain steps of an algorithm without altering the structure of this algorithm. Invari- ant parts of the algorithm are defined in the superclass, while subclasses can decide how they implement the variable parts. It is the more general version of the Factory Method, because it does not restrict the pattern to creating something. It is applicable when code duplication is to be avoided. Differ- ences of existing code are factored out into new operations that are called by the superclass and are implemented by subclasses. Template Method is also a useful pattern when subclassing should be controlled and restricted to certain parts. Template Method calls “hook” operations—default operations that can be extended if needed and do nothing by default—which are the only operations that are allowed to be varied.

3.1.23 Visitor

The Visitor pattern “represents an operation to be performed on the el- ements of an object structure. It lets us define a new operation without changing the classes of the elements on which it operates”. The Visitor pat- tern belongs to the group of Behavioral Patterns. It is applicable whenever the easy addition of new operations to the elements of an object struc- ture is required. For example, the object structure of the Composite is often extended by operations defined in Visitors. The augmentation of ob- ject structures with new operations is possible without changing the object structure itself. The Visitor pattern thereby avoids the pollution of classes with unrelated operations by defining Visitor objects that are attached to the object structure. However, the object structure itself should not change its interface, because this would require to change the Visitor interface and with it all concrete Visitors. In this case, it is better to define the operations directly in the object structure.

Ontologies

A key issue in today’s information society is the efficient management of knowledge. Ontologies were developed by the Artificial Intelligence commu- nity to support the sharing and common understanding of domain knowledge 24. The most-cited definition of an ontology stems from Gruber29:

“An ontology is an explicit specification of a conceptualization. The term is borrowed from philosophy, where an ontology is a systematic account of Existence. For knowledge-based systems, what “exists” is exactly that which can be represented. When the knowledge of a domain is represented in a declarative for- malism, the set of objects that can be represented is called the universe of discourse. This set of objects, and the describable relationships among them, are reflected in the representational vocabulary with which a knowledge-based program represents knowledge. Thus, we can describe the ontology of a program by defining a set of representational terms. In such an ontology, definitions associate the names of entities in the universe of dis- course (e.g., classes, relations, functions, or other objects) with human-readable text describing what the names are meant to denote, and formal axioms that constrain the interpretation and well-formed use of these terms.”

Thus, an ontology makes the meaning, or the semantic of a domain ex- plicit. This enables agents—human or machine—to communicate with each other and to correctly interpret the semantic of a specific context. Figure 4.1 shows the problem of semantics, symbolized by the semiotic triangle. The concept of the semiotic triangle goes back to Aristotle and is described in detail in52. It shows the connection between symbol, concept and object.

In order to communicate, i.e. to transmit information, we use words, and, from a more abstract point of view, symbols. There is no inherent

Figure 4.1: The semiotic triangle (inspired by [52, 1])

illustration not visible in this excerpt

connection between words and real things. A symbol can stand for differ- ent objects. The receiver of the transmitted information has to process the information and has to interpret it to find a connection between the symbol and the concept it symbolizes. This enables him to decide which real thing the symbol stands for and which object the concept refers to. Hence, the receiver of a message tries to find out the semantics of a word. The map- ping from word to concept can be ambiguous because it can depend on the context of the statement the word is used in and the background knowledge of the message receiver. Consider the following sentence: “I am sorry to inform you that my cat has eaten your mouse.” A human reader would associate the word mouse with his pat—an animal often having soft gray or brown fur, a long hairless tail, and large ears. The reader would not hurry to her computer checking the computer mouse is still in place. Human read- ers are familiar with the fact that cats are predators eating small animals, not technical pointing devices attached to computers. However, this kind of information is not implicitly available to machines. But it can be made machine-understandable by means of ontologies.

An ontology is able to provide knowledge of an area of interest in a simplified, abstract way. This enables information systems to process this knowledge and reason about it. The represented knowledge is based on a conceptualization30. It contains all the objects, concepts, relationships and other entities that are assumed to exist in the domain. Therefore, a minimal ontology consists of a hierarchy of classes (concepts), properties (attached to the concepts and used to model relationships between them), and individuals (instances of the concepts).

4.1. THE WEB ONTOLOGY LANGUAGE OWL 21

In the following sections, we introduce OWL, the Web Ontology Lan- guage, a standardized ontology language that we later use to develop the Design Pattern Intent Ontology (DPIO) to solve the task of formalizing the intent of design patterns. We also introduce other established ontology lan- guages and motivate, why OWL is chosen for developing the DPIO.

The World Wide Web Consortium has developed the Web Ontology Language (OWL) as part of its Semantic Web vision. OWL has become a W3C recommendation in February 2004 [51, 2]. It builds on languages such as XML56, RDF54, RDFS14 and is a revision of DAML+OIL18, which is briefly mentioned in Section 4.2.

OWL comes in three increasingly expressive flavors, which are designed for different use cases.

- OWL Lite can be used to build simple classification hierarchies and simple constraints. It allows the quick development of thesauri and taxonomies. However, OWL Lite exhibits only a low formal expres- siveness and misses some formal features needed for the development of the DPIO.
- OWL DL stands for OWL description logic. It depicts a compromise of maximum expressiveness and computational completeness and decidability. This is an important feature to consider in order to utilize the power of a reasoner and for querying the ontology.
- OWL Full exhibits maximum expressiveness with no computational guarantees. It is therefore not a possible choice for the development of the DPIO.

In the following we give an introduction to some of the language fea- tures of OWL-DL that are later needed in the development of the Design Pattern Intent Ontology. The examples are mainly taken from the OWL pizza tutorial34.

4.1.1 Classes

4.1.1 Classes

Classes are defined in OWL by declaring the keyword owl:Class. Classes group individuals with shared properties. The most general class in OWL is owl:Thing, which is the superclass of all other classes. owl:Nothing on the other hand, is the class that has no instances and is the subclass of all OWL classes. An example for a simple class definition is:

illustration not visible in this excerpt

Listing 4.2: Definition of subclasses

A new class FruttiDiMare is introduced. With rdf:about="#Pizza", an existing class definition can be extended and FruttiDiMare can be made subclass of Pizza. This is a simple extension mechanism similar to object oriented programming that makes it possible to extend concepts from existing ontologies without the need to repeat the original definition.

4.1.2 Properties

Properties are used to model relationships between individuals or from individuals to data types. Object properties relate individuals of a class to others, datatype properties relate individuals to data types.

illustration not visible in this excerpt

Listing 4.3: Definition of an object property

An Object property rdf:ID="hasTopping" is created. From the domain rdfs:domain it can be inferred that a class with the property hasTopping is of type Pizza. The range rdfs:range of the property restricts to individuals of class PizzaTopping.

The next listing shows the usage of OWL properties:

[...]

---

¹ 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.