Pattern-based design evolution using graph transformation

Abstract

In recent years, design patterns gain more interest in software engineering communities for both software development and maintenance. As a template to solve a certain recurring problem, a design pattern documents successful experiences of software experts and gradually becomes the design guidelines of software development. Applying design patterns correctly can improve the efficiency of software design in terms of reusability and enhance maintainability during reverse engineering. Software can be evolved when developers modify their initial designs as requirements change. For instance, a developer may add/delete a set of design elements, such as classes and methods. Modifications on software artifacts can introduce conflicts and inconsistencies in the previously applied design patterns, which are difficult to find and time-consuming to correct. This paper presents a graph-transformation approach to pattern level design validation and evolution. Based on a well founded formalism, we validate a given design by a graph grammar parser and automatically evolve the design at pattern level using a graph-transformation system. Rules for potential pattern evolutions are predefined. The graph-transformation approach preserves the integrity and consistency of design patterns in the system when designs change. A prototype system is built and a case study on the Strategy pattern demonstrates the feasibility of pattern-based design validation and evolution using graph transformation techniques.

Introduction

Software systems become increasingly complicated and hard to maintain due to the massive information in the system and complex system structure. There has been an urgent need for an efficient and effective method to ease the tedious work at software development and maintenance stages. The emergence of object-oriented design patterns [1] makes software development more efficient in terms of reusability because design patterns document the successful experience of experts and provide solutions to certain reoccurring problems in particular contexts. Application of design patterns facilitates software development in that it allows software engineers to communicate and collaborate with each other efficiently. Well documented design patterns also assist the comprehension of legacy programs in reverse engineering.

In addition to efficient software development methodologies, software systems should always be adaptable to evolve upon modification requests from users or designers. This requires a system to be extensible and flexible since we cannot know all the requirements and build a perfect system at the beginning [2]. Arthur et al. [3] defined software evolution as “a continuous change from a lesser, simpler, or worse state to a higher or better state” for software system. To efficiently achieve such an evolution, modifications to a system generally start from the design level that hides massive programming information because the size of a design is typically much smaller and more manageable than that of codes.

Since Gamma et al. [1] first introduced the well recognized design patterns, intensive research has been carried out on the application of design patterns. The wide use of design patterns requires an effective mechanism to validate software designs and allow designers to make modifications on them as system requirements change. On one hand, it is necessary to guarantee that a design complies with the structural integrity of the design patterns that have been applied. On the other hand, any change on the design should not violate the structural properties of existing design patterns in the system, since a local modification may have a chain effect on the whole system. Manually checking the impact of a single modification, however, is a time-consuming and error-prone process. In general, design evolutions that happen at pattern level includes refactoring [4] and design pattern evolution [5]. Refactoring is to find the “bad smell” in the system and reconstruct it in order to achieve better efficiency with external behaviors preserved. Design pattern evolution is to refine a design pattern according to requirements changes while maintaining the pattern's properties. A design pattern normally includes changeable and stable parts. The changeable part of a design pattern can be potentially adapted to several different applications, while the stable part will remain. More specifically, pattern participants, e.g. classes and relationships, may be added to/removed from a particular design pattern without violating the pattern's structural properties and constraints. We defined such a process as a pattern level design evolution, in which pattern participants in a system design are modified but the fundamental properties of the design are preserved at the pattern level.

As a de facto standard to visually modeling software systems, UML provides a set of intuitive notations to represent design patterns and corresponding designs. The lack of formal semantics, however, prevents UML from automatic validation and evolution. Dong et al. [5] automated the design evolution process as XSLT transformations that can transform the UML model of a design pattern application into the evolved UML model of the pattern. Both the original and evolved UML models are represented in an XMI format to facilitate the transformations. To take advantage of the graphical characteristics UML diagrams, we explore a graph-transformation approach to pattern level design validation and evolution.

Graph transformation, which offers a computational paradigm of mathematical precision and visual specification [6], provides an intuitive yet formal means to interpret and manipulate visual languages. In general, graph transformation defines computation in a multi-dimensional fashion based on a set of rewriting rules, i.e. productions. Each production consists of two parts: a left graph and a right graph, the difference between which visually indicates the changes generated by a computation. By representing a design as a graph, the problem of design evolution is converted to graph evolution, which can be naturally realized through graph transformation: the left graph of a production indicates the pre-condition of an evolution and the right graph represents the post-condition after an evolution. Applying graph transformation to design evolution can guarantee that the design after evolution still observes the structural properties of its underlying patterns. A graph grammar system [7] extends a graph transformation system by (1) defining an initial graph and (2) classifying terminal and non-terminal objects. In this way, a graph grammar abstracts the essential structures shared by a set of graphs. Therefore, we formalize the structure of a design pattern into a graph grammar, and correspondingly validate the structural integrity of a design through a parsing process, i.e. a sequence of graph-transformations. Using visual representation to interpret software evolution and validation improves the expressiveness to human's understanding and communication.

In summary, this paper presents a graph-transformation framework for pattern level design validation and evolution, which is characterized by a syntax-oriented graphical design environment facilitated by an automatic design evolution tool. The graphical design environment can verify whether a design observes the structural integrity of a design pattern while the evolution tool can guarantee that a design after evolution is still consistent with the structural properties of its underlying patterns. Validation of a design is a parsing process on a graph representing the design. In order to improve the performance of the parsing process, each design pattern defines one key structure. We first locate the key structure in a design and then initiate a parsing process from the key structure. The key structure can narrow down the parser's searching scope and thus achieve a better performance. Based on the characteristics of GoF design patterns, we categorize pattern level design evolutions into five types [11] (e.g. independent evolution and packaged evolution), which are applicable to different design patterns. Each evolution style in a specific design pattern is defined through graph-transformation. When an evolution is carried out through graph transformation, the syntactic correctness of the evolved design is guaranteed with respect to a design pattern.

The contributions of this paper are threefold:

• Formalizing design pattern structures using graphical representation.

• Validating patterns in a design by the spatial graph grammars.

• Realizing pattern-based design evolutions through graph-transformations.

The rest of the paper is organized as follows. Section 2 briefly introduces the Spatial Graph Grammar (SGG) [8] formalism and concepts of graph transformation. Section 3 explains the classification of design pattern evolutions. Section 4 presents the overview of our framework and investigates a graph-transformation approach to design pattern validation and evolution. Section 5 shows a prototype system and illustrates an example using the Strategy pattern. Section 6 reviews related work. Section 7 concludes this paper and discusses the future work.