9512.net
ÌðÃÎÎÄ¿â
µ±Ç°Î»ÖÃ£ºÊ×Ò³ >> >>

# Object-oriented software evolution

Object-Oriented Software Evolution

Karl J. Lieberherr Cun Xiao Northeastern University, College of Computer Science Cullinane Hall, 360 Huntington Ave., Boston MA 02115 lieber@corwin.CCS.northeastern.EDU cunxiao@corwin.CCS.northeastern.EDU phone: (617) 437 2077 January 25, 1993
Texed at 14:13 January 25, 1993 Copyright c 1991 Karl Lieberherr

Abstract
We review propagation patterns for describing object-oriented software at a higher level of abstraction than the one used by today's programming languages. A propagation pattern de nes a family of programs from which we can select a member by giving a class dictionary graph which details the structure of behavior through part-of and inheritance relationships between classes. The paper introduces three concepts: evolution histories, growth-plans and a propagation directive calculus. Evolution histories describe a sequence of development phases of an object-oriented program, each phase being executable and therefore testable. To keep the programs exible and short, we describe them in terms of propagation patterns. Each phase of an evolution history is tested in small steps which are constrained by class dictionary graphs belonging to a growth-plan. Propagation directives are useful both for describing propagation patterns and growth-plans and therefore we endow propagation directives with su cient expressiveness by giving a formal calculus applicable to object-oriented programming in general. A propagation directive is a succinct description of a family of submodels for a given family of data models.

Index Terms: Programming and design abstractions, adaptive software, propagation patterns, program families, delayed binding, testing object-oriented programs, Demeter Method.

1 Introduction
In his paper Par79], Parnas gave the motivation for this paper when he wrote: \In my experience, identi cation of the potentially desirable subsets of a software system] is a demanding intellectual exercise in which one rst searches for the minimal subset that might conceivably perform a useful service and then searches for a set of minimal increments to the system." In his book on object-oriented design Boo91], Grady Booch writes: \... with object-oriented design we never encounter a \big-bang" event of system integration. Instead, the development process results in the incremental production of a series of prototypes, which eventually evolve into the nal implementation." Readers not familiar with object-oriented analysis, design and programming are referred to books such as Cox86, Mey88, CY90, WBWW90, JCJO92, Boo91].
Supported in part by the National Science Foundation under grant numbers CCR-9102578 (Software Engineering) and CDA9015692 (Research Instrumentation). Demeter is a trademark of Northeastern University.

1

We came up with the technique presented in this paper, while teaching object-oriented programming to experienced software developers who were familiar with languages such as C or Pascal. We observed that they tended to develop their projects in chunks which were too big, following the programming style from their C or Pascal experience. This leads to delays and unreliable code and also sometimes to discouragement since the projects looked like big mountains. Therefore we invented evolution histories and growth plans to help the programmers to climb the mountain in small controlled phases with positive feedback after each testing phase. According to our experience, this proves to be a psychologically useful help and leads to better programs faster.

1.1 Beyond object-oriented programming
We describe software using propagation pattern programs LXSL91, Lie92, LHSLX92] which are an improved form of object-oriented programs. Every object-oriented program is a propagation pattern program, but even the best object-oriented programs get a low score if viewed as propagation pattern programs. Although objectoriented programs are easier to reuse than programs which are not written in an object-oriented style, objectoriented programs are still very rigid and hard to evolve. The key reason is that object-oriented programs contain a lot of redundant information about class relationships. Our experience shows that for most application domains, object-oriented programs can be made signi cantly more general and extensible by expressing them as propagation pattern programs. A key feature of object-oriented programming is that methods are attached to classes (C++, Smalltalk, Ei el, Beta) or to a group of classes (CLOS). This leads to programs which are hard to maintain since details of the class structure are encoded into the methods repeatedly. This paper goes beyond object-oriented programming, yet it builds on all the advantages of the object-oriented paradigm. We show how propagation patterns delay the binding of methods to classes beyond program-writing time. A propagation pattern describes a family of programs using only minimal assumptions on a class structure. We can select a member of the family by providing a speci c class structure which satis es the assumptions. Propagation patterns o er signi cant advantages to the software developer: Early payo . Propagation pattern programs contain as a special case ordinary object-oriented programs. The worst-style propagation patterns are programs written in one of today's object-oriented programming languages. Therefore, propagation patterns should be used in any project where an object-oriented programming language is used. Propagation patterns do not compromise execution e ciency; they are easy to learn and will pay o in the rst project. Adaptiveness. For many changes to the structure of input, intermediate and output objects, propagation patterns adapt without modi cation. Extensibility. Propagation patterns can be easily modi ed to better meet particular needs. Reduced size of software. Propagation patterns are often signi cantly shorter than their object-oriented program counterparts. The reason is that a propagation pattern is a description of an object-oriented program and is therefore at a higher level of abstraction. We illustrate propagation patterns with a simple example. A propagation pattern implements a \responsibility", e.g., void print vertices() to print all the vertices in a given graph object. To implement such a responsibility, we need the collaboration of a group of classes. We could itemize the collaborating classes, but that would defeat our goal of having adaptive software. Instead, we make only minimal assumptions on the class structure and we provide a succinct description of the group of collaborating classes in the form of a traversal speci cation. The following construct, called a propagation directive,

from Graph through -> to Vertex

*,neighbors,*

2

speci es that we need the collaboration of all classes \between" Graph and Vertex which are linked by the neighbors relationship. The propagation directive also de nes traversal code for traversing Graph-objects and for nding all the Vertex-objects in them which are reachable through the neighbors relationship. This traversal code de nes much of the functionality we need for the vertex printing problem, but it is not su cient. We need a notation to annotate the traversal code so that it satis es our current needs. In our example, we need only one annotation for Vertex which prints the vertex. The responsibility void print vertices() together with the propagation directive and the annotation constitutes a simple example of a propagation pattern. This propagation pattern de nes an in nite family of programs for printing the vertices of graphs. It is an in nite family of programs since we only encoded minimal assumptions on the class structure into our program. Next we would like to select a member of this family. A selection is accomplished by writing a class structure which satis es the assumptions: We need a class Graph which contains a nested Vertex class reachable through a neighbors relationship. We will soon encounter such a class structure in Fig. 5.

1.2 Example of software evolution
Functional complexity

Cycle?checking on graphs with edges of two kinds Cycle?checking on graphs with edges of one kind DFT traversal on graphs with edges of one kind DFT traversal on trees
Input complexity

trees

graphs with edges of one kind

graphs with edges of two kinds

Figure 1: Simplifying the cycle checking problem Finding a minimal subset of a software system can be done in two ways: We simplify with respect to the data and/or with respect to the functionality. Fig. 1 gives an example. Suppose that we have to write a cycle checker for directed graphs which have two kinds of edges. Data simpli cation means that we only consider a subset of all possible inputs. A data simpli cation would be to consider rst only graphs which have one kind of directed edge. Functionality simpli cation means that we keep the data the same, but we simplify the problem. For example, instead of writing a cycle checker directly, we rst write a traversal algorithm for the graphs. Later this traversal algorithm will be enhanced to a cycle checker. Finally, further data simpli cation leads to the simple problem of writing a traversal algorithm on trees. Data simpli cation normally implies functionality simpli cation. When one implements the four design phases shown in Fig. 1, at each phase the rst step is to produce a list of classes with their part-of and kind-of relationships to describe all the objects for the current phase. The description we use is called a class dictionary graph, which is shown in Fig. 2 for the rst phase. The vertices stand for classes. The vertices drawn as 2 stand for concrete vertices, called construction vertices. stand for abstract vertices, called alternation vertices. The double-shafted The vertices drawn as arrows(=)) stand for kind-of relationships. The single-shafted arrows(?!) stand for part-of relationships. This class dictionary graph in Fig. 2 describes all graph objects with one kind of edges, including tree objects. 3

Input
graph

start

source neighbors

Vertex
name

first

Vertex_List
rest

Ident

Vertex_Empty

Vertex_NonemptyList

Figure 2: Class dictionary graph tree Class dictionary graphs serve multiple roles in software development. During analysis, design and programming they serve to describe a common vocabulary. However, since class dictionary graphs describe the structure of objects in detail, they pose a threat to the reusability of the software. Once the software is developed in terms of those details, it will be hard to maintain when the class structure changes. Fortunately, often the software for a speci c functionality does not really depend on all the details. Therefore we view class dictionary graphs as very volatile and overspeci ed artifacts and in this paper we introduce a method for writing the software with minimal dependency on class dictionary graphs. Indeed, we write our software parameterized by class dictionary graph types which describe families of class dictionary graphs to which the software can be applied. Besides serving as a common vocabulary, class dictionary graphs have a second role: they are used to integrate all the programs, each one using only a part of the information in the class dictionary graph, into an executable program tailored to the class dictionary graph. The bene t of the method is that we can write adaptive software. After having the class dictionary graph for the rst design phase, one then writes methods associated with the various classes to implement the desired functionality. Instead of writing a complete C++ program, we prefer to use an abstract description (see Fig. 3) of a C++ program, called a component, which is parameterized by the class dictionary graph1 , such as the one in Fig. 2. A component is a named group of propagation patterns. We use C++ as the implementation language throughout the following examples. Of course the method we introduce is programming language independent. To explain propagation patterns we use the example in Fig. 3 and we explain them in the context of the class dictionary graph in Fig. 2. The program in Fig. 3 implements depth- rst traversal of trees only. The C++ member functions corresponding to the propagation patterns in Fig. 3 and the class dictionary graph in Fig. 2 are in Fig. 4.2 Each operation signature is propagated along the paths de ned by the from clauses. The paths specify traversals of objects de ned by the class dictionary graph. Each class on a path gets a member function with the signature and the default body for the traversal. We can use three kinds of code fragments, primary, before and after, to modify the traversals. Each code fragment has a body enclosed by begin and end which contains a sequence of C++ statements. The before code fragment of class C will modify the existing function body of class C; the before code fragment of class C will be put at the beginning of the existing function body of class C; the after code fragment will be appended to the end of the existing function body of class C. If there is no from clause in a propagation pattern, only the classes speci ed by code fragments will have the member functions with the signature.
1 We extended class dictionary graphs to schemas by adding derived edges. But for simplicity, schemas and class dictionary graphs can be treated as the same in this paper. 2 It is important that the class dictionary graph in Fig. 2 is only one example of a schema to which the component can be applied. Therefore we use the keyword schema examples in the component de nition.

4

According to the class dictionary graph in Fig. 2, an Input-object has two part-objects, a Graph-object which is being traversed and a Vertex-object which is the starting vertex of the traversal. The program starts from an Input-object by calling the method init() of class Input. The program then goes to the Vertex-object start by calling the method dft. At each Vertex-object, its corresponding Adjacencyobject is found and visited. And the traversal continues by going to the Vertex-objects which are the neighbors of the Adjacency-object.

component tree dft schema examples tree operation void init() primary Input begin start->dft(graph); end operation void dft(Graph g) from Adjacency through -> , neighbors, to Vertex primary Vertex begin end operation void visit(Graph primary Adjacency begin

Component speci cation

Explanation
init is only defined for class Input. The method body in C++ is specified within and and is called the of Input.

begin end primary code fragment

Traverse an Adjacency-object and locate all the Vertex-objects which are reachable through the neighbors relationship. For each such Vertex-object, find and visit the corresponding Adjacency-object in graph g. The argument g must be an object which is a tree.

g)

At each Adjacency-object which is being visited, print it out and continue the traversal. g print is a predefined function.

v)

Traverse a Graph-object and locate all the Adjacency-objects. For each such Adjacency-object check whether its source has the same name as v. If the answer is positive, return the Adjacency-object(Efficiency could be improved).

a This is not a violation of the Law of Demeter Bud91, LH89a], since Adjacency can be viewed as a computed immediate part-class of Vertex.

Figure 3: The C++ program description for DFT algorithm on trees The methods with the signature, void find(Adjacency *&adj,Vertex *v), are used to nd the Adjacencyobject of a given Vertex-object v. After reaching each Adjacency-object contained in the Graph-object, we compare the object v with the Vertex-object of the current Adjacency-object. If they are the same, then we have found the Adjacency-object. We prefer to use a description of a C++ program (e.g. Fig. 3), as opposed to a C++ program itself (e.g. Fig. 4). The description gives a high-level abstraction of a C++ program, which provides for delayed binding of methods to classes and which leads to software which is smaller and easier to reuse. For example, the description 5

void Input::init() f

start->dft(graph); g
g f fg
//virtual

a

voidVertex List::dft(Graph *g)

voidVertex NonemptyList::dft(Graph *g) first->dft(g); rest->dft(g);

f

g

void Vertex::dft(Graph *g) f

g

f fg
//virtual

f

g

aAll the lines which are not in the bold font are generated.

Figure 4: The C++ program for DFT algorithm on trees

6

in Fig. 3 does not mention the two list structures which are explicitly traversed in Fig. 4. Only when we use the class dictionary graph of Fig. 2 to interpret the propagation patterns, the classes for the list structures get methods as shown in Fig. 4. If the representation of the list structures is changed, the description can still be reused without change.
Input
start graph

source name adjacencies rest first marked neighbors

Ident

Graph

first

Mark

Vertex_List

rest

MarkUnset

MarkSet

Vertex_Empty

Vertex_NonemptyList

component 1 graph dft schema examples 1 graph dft reuse component tree dft operation void init() before Input begin this->init mark(); end operation void init mark() from Input to Adjacency primary Adjacency begin this ->set marked(new MarkUnset()); end operation void visit(Graph *g) from Adjacency through -> , marked, carry Adjacency adj along from Adjacency to MarkUnset at Adjacency begin adj = this; end primary MarkUnset begin end primary Adjacency default

Component speci cation

Reuse component tree_dft by adding new methods and adding new code fragments or overwriting old code fragments. Before the traversal starts, all marks are initialized by init_mark.

Explanation

Traverse a Input-object and locate all the Adjacency-objects. Initialize the Adjacency-objects as unmarked.

Traverse an Adjacency-object and locate all the objects reachable through the marked relationship. Take the Adjacency-object (with name adj) along. It will be available at vertex MarkUnset.

end

At the MarkUnset-object, mark and print adj and continue traversal from adj. Between Adjacency and MarkUnset there must be an alternation class for the delayed binding of visit. Since we moved the visiting code from Adjacency to MarkUnset, we need the default functionality for Adjacency: marked->visit(g,adj).

Figure 6: The traversal algorithm on graphs with edges of one kind

8

Input
graph

start

Vertex
name source

Ident

neighbors

first

Vertex_List

rest

rest

marked

MarkSet Unfinished MarkUnset

Vertex_NonemptyList

Mark

Figure 7: Class dictionary graph 1 graph cycle for cycle checking on graphs with edges of one kind

component graph cycle schema examples 1 graph cycle, 2 graph reuse component 1 graph dft(dft => cyclecheck) operation void visit(Graph *g) primary MarkSet begin end after MarkUnset begin adj->set marked(new Finished()); end
graph cycle cout << cycle found at ; adj->g print();

Component speci cation

Reuse component 1_graph_dft, rename the method name from visit to cyclecheck. MarkSet must be reachable from Adjacency through the marked relationship.

Explanation

end

Figure 8: Cycle-checking on graphs with edges of one kind and graphs with edges of two kinds

9

Input
start graph

Ident
name

marked

source neighbors

Graph
rest

first

Neighbors

first

Mark A_Neighbors Unfinished Finished
a_neighbors b_neighbors

B_Neighbors

rest

Vertex_NonemptyList

Total size of code fragments (characters)

Cycle?checking on 2?graphs Cycle?checking on 1?graphs

584 414
DFT on trees

DFT on 1?graphs

235

8

12

13

1-graphs: graphs with edges of one kind. 2-graphs: graphs with edges of two kinds. Figure 10: Evolution history

Number of Imaginary Vertices and Labels

1.3 Software testing
Each component in an evolution history is tested individually, but it may be possible to reuse inputs from previous components. We want to test a component incrementally, initially with very simple inputs which exercise only part of the propagation patterns. Then we make the inputs more and more complex until all of the propagation patterns have been su ciently exercised. The test phases are naturally described by a so-called growth plan which is itself expressed in terms of succinct graph representations as they are used in propagation patterns.

1.4 Overview
In this paper we give a succinct representation of data models and their submodels to make the software evolution process easier. Our description of software evolution is not intended as a comprehensive method for developing object-oriented systems. Our method contains important new features and it is intended to be used in conjunction with comprehensive software development methods, such as the Objectory Method by Ivar Jacobson JCJO92]. We assume that we have derived a schema, e.g., from the use-cases in the Objectory method, and that we need to provide application-speci c functionality, e.g., to implement a use-case. The common approach today is to de ne methods and to attach them to speci c classes. Our experience with large software systems shows that it is far better to leave the assignment of methods to classes to a tool. Instead of writing methods ourselves, we write abstract descriptions, called propagation patterns, of an unspeci ed number of methods. There are at least two reasons for this: Avoiding redundancy. Consider the methods of two object-oriented programs, one for printing an object of class A and one for nding all objects of some other class in objects of class A. Those two programs, if written in a straight11

forward way by traversing objects of class A, both contain detailed information on the structure of class A. This situation is typical in object-oriented programs and therefore, class structure information is heavily redundant in today's object-oriented software, making it hard to evolve! Schema information is unstable. Part-of and kind-of relationships between classes are constantly changing during the life-time of software. Therefore, we use schema information sparingly in our programs (propagation patterns). Indeed, the schema information in our programs we view as constraints on the schemas which can be applied to our programs. When the schema information changes, we can apply the new schema to our program provided that the new schema satis es the constraints spelled out in the program. Therefore, a propagation pattern describes a family of programs, one for each schema which is compatible with the program. A simpli ed diagram in Fig. 11 illustrates the process of our method.
Problem A

Evolution history
component for A1

Data and functionality simplification
Design Decision

reuse

reuse
component for A3

(problem decomposition)
A1 A2 A3 A4 A5

component for A2

Implement
reuse
component for A5

reuse
component for A4 Schema example Propagation patterns

Inputs Functionality

A sequence of partial class dictionary graphs

test plan for the schema example

Figure 11: Problem solving Evolution histories are useful for designing, implementing and testing of object-oriented software. Developing Designs Evolution histories are helpful for software designs by avoiding starting from scratch. Evolution histories are helpful for making the addition of functionality and data in small incremental steps. Later, this leads to easier code development. Developing Code Evolution histories help software developers to grow software in small incremental steps which can be tested individually. Propagation patterns make such a process even easier. 12

Testing and Debugging Software Evolution histories make it easier for the developer to test and debug a program incrementally. At each phase of an evolution history, the growth-plan for a class dictionary graph can be used to test software in a systematic way. A sequence of inputs corresponding to the growth phases of a class dictionary graph can be used to test the smallest number of additional classes on successive test runs. For example, if a program correctly processed the test inputs for the rst 5 growth phases but failed to process the test input for the 6th growth phase, we would probably want to examine the methods injected into the classes introduced at growth phase 6. Explaining Software An evolution history proposes a useful order for explaining existing software. Dividing Systems into Layers An evolution history is e ectively proposing how to layer software. Learning a Language. A growth-plan proposes a useful order for learning the language de ned by a class dictionary. A set of class de nitions can be viewed as a language de nition San82], Joh88], Lie88]. The relationship between complex objects and their constituents parallels the linguistic relation between large phrases and smaller phrases that compose them. Therefore, a class dictionary de nes a grammar for a domain speci c language. This work is part of a project on the Demeter System which consists of the Demeter Method and the Demeter Tools. The Method is programming-language independent; the Tools support the Method. The Demeter System/C++ applies the Method to C++ software development and the Demeter Tools/C++ allow the checking of high-level designs and code generation. The tools support developing adaptive software with propagation patterns. This paper introduces the following new material which has not been included in other papers on the Demeter System: 1. Succinct representation of submodels of data models (the propagation directive calculus). 2. A precise de nition of growth-plans based on the de nition of partial class dictionary graphs in LX93]. 3. The concept of a minimally adequate test set for a growth-plan. We reuse the de nition of class dictionary graphs from LX93, Ber91, LBSL91], of object graphs from LX93, LBSL91], of semi and partial class dictionary graphs from LX93], and of simple propagation directives from LXSL91]. The rest of the paper is organized as follows: Section 2 reviews a sequence of three increasingly more speci c graph structures for modelling object-oriented programs: semi-class dictionary graphs, partial class dictionary graphs and class dictionary graphs. We also review object graphs, a graph structure for modelling objects. We show how class dictionary graphs and object graphs are related through the concept of containment paths. Section 3 introduces a calculus for succinct representations of semi-class dictionary graphs. Section 4 introduces growth-plans which help to structure the testing of object-oriented applications. Section 5 discusses related work. The conclusions are in section 6 and the appendix proves two NP-completeness results related to nding growth plans and to evaluating succinct representations of class structures.

2 Data modeling for object-oriented design
During the object-oriented programming process, each entity of the problem domain is represented by a set of objects. Each object has some attributes and some operations which will be performed on it. In many objectoriented programming languages, objects are grouped into classes, and inheritance is introduced to abstract 13

their similarities. The Demeter model, which describes the important structures used in the Demeter Method, has been developed for such a domain. Part-of relations and is-a/kind-of relations are used to describe relationships between classes. In LBSL91, Ber91], class dictionary graphs are introduced based on these two kinds of relations, and the is-a relations are expressed by alternation edges. Later we found that is-a relations are not enough for describing the properties of inheritance, in terms of de ning objects and describing programs. We split an is-a relation into an alternation relation and inheritance relation. This results in a generalized structure, called semi-class dictionary graph, which is used for de ning behavior and object sets. A summary of the structures used in this paper is given in Table 1 on page 29.

2.1 Semi-class dictionary graphs and class dictionary graphs
In this section we introduce graph structures which need to be manipulated during object-oriented software development. We rst introduce semi-class dictionary graphs which serve later as abstractions of object-oriented programs. A semi-class dictionary graph, combined with annotations which focus on the interesting aspects of a task, de nes an executable program. Semi-class dictionary graphs are also used to de ne partial class dictionary graphs which de ne sets of objects. Partial class dictionary graphs will be used in this paper to control the testing process for object-oriented programs. Finally, partial class dictionary graphs are used to de ne class dictionary graphs which serve as abstractions for application-speci c class libraries which only contain generic functionality for manipulating objects, such as copying, printing, comparing, accessing, constructing etc. The vertices and edges in a semi-class dictionary graph are used in many di erent ways. A vertex may represent a class or a set of objects. An edge may represent an instance variable, a function call or a selection of subobjects. It will be obvious from the context which interpretation we refer to.
Input
graph start

source neighbors

Vertex
name

rest first

Vertex_List Ident
rest

Vertex_Empty

Vertex_NonemptyList

Figure 12: A semi-class dictionary graph Fig. 12 shows a semi-class dictionary graph in which each vertex corresponds to a class and each edge corresponds to a relation between classes. We call vertices Graph, Adjacency_NonemptyList and Adjacency_Empty construction vertices (drawn as ). Alternation vertices cannot 2 ), and we call vertex Adjacency_List an alternation vertex(drawn as be instantiated; they serve for abstraction. Construction vertices can be instantiated. Graph has a nonempty list of adjacencies, called Adjacency_NonemptyList. Adjacency_Non-emptyList contains at least one element which is an adjacency, and a list of the rest of adjacencies represented by Adjacency_List. All these three relations are part-of relations which are drawn as single-shafted arrows(?!). They are called 14

De nition 1 A semi-class dictionary graph is a tuple = (V C; V A; ; EC; EA; EI ) with nitely many labeled vertices in the disjoint sets V C and V A. We de ne V = V C V A. V C is a set of vertices called construction vertices. V A is a set of vertices called alternation vertices. EC is a ternary relation on V V , called construction edges. is a nite set of construction edge labels. EA is a binary relation on V A V , called alternation edges. EI is a binary relation on V V A, called inheritance edges.
Alternation classes cannot be instantiated; they are abstract, but de ne indirectly a set of objects. In Fig. 12, alternation edge Adjacency_List=) Adjacency Empty expresses that an object of class Adjacency Empty is also an object (but not an instance) of alternation class Adjacency_List. Alternation-reachable de ned below is the re exive transitive closure of the relation EA. When vertex w is alternation-reachable from vertex v, an object of w is also an object of v.

De nition 2

from vertex v if

In a semi-class dictionary graph

= (V C; V A; ; EC; EA; EI ), a vertex w is alternation-reachable

v = w or v=)w 2 EA or 9w0 s.t. w is alternation-reachable from w0 and w0 is alternation-reachable from v.
+ We write v=)w if w is alternation-reachable from v. We write v=)w if w is alternation-reachable from v via more than one alternation edge.

Each object belonging to an alternation vertex A is an instance of a vertex which is alternation-reachable from vertex w. The relation inherits de ned below is the re exive transitive closure of the relation EI.

De nition 3

In a semi-class dictionary graph = (V C; V A; ; EC; EA; EI ), a vertex v inherits from vertex w if

v = w or w 2 EI or v 9w0 s.t. v inherits from w0 and w0 inherits from w.
We write v
*

w if v inherits from w. We write v

+

w if v inherits from w via more than one inheritance edge.

15

The semi-class dictionary graphs which appear in applications always satisfy the following two axioms. We say a semi-class dictionary graph is legal if it satis es 2 independent axioms called the Cycle-Free Alternation and Inheritance Axiom and Unique Label Axiom. A legal semi-class dictionary graph = (V C; V A; ; EC; EA; EI) with V = V C \ V A satis es:

Cycle-Free Alternation and Inheritance Axiom

Unique Label Axiom (see Fig. 13) 8v; w; w0; x; y 2 V; l 2 : if v * w or w=)v, v * w0 or w0 =)v, then l l l l w ?! x; w0 ?! y 2 EC implies w ?! x = w0 ?! y (i:e:; w = w0 and x = y):
x l w w¡¯ l y

There are no alternation cycles and no inheritance cycles, i.e., 6 9v 2 V : v=+ v or v )

+

v;

v

Figure 13: Forbidden graph From now on, when we refer to a semi-class dictionary graph, we mean a legal semi-class dictionary graph. Reachability is an important concept for graphs, and it has a special meaning in semi-class dictionary graphs. The intuition behind the containment path concept introduced below, is to de ne the set of classes which are needed to build objects of a given class. The set of vertices which are reachable (by a containment path) from a given vertex V , de nes the set of classes whose instances may appear as (nested) parts of V -objects. We also use the reachability concept to specify propagation patterns, for example in Fig. 3. Further motivation for the containment path concept is in Section 2.4.

De nition 4

l For an edge e = v=)w 2 EA or e = v ?! w 2 EC or e = v w 2 EI in a semi-class dictionary graph = (V C; V A; ; EC; EA; EI ), we call v the start vertex of e, and w the end vertex of e. A containment path p is a sequence of edges from EC EA EI , such that the end vertex of each edge in p is the start vertex of the next edge in p if there is one, and p must be in (EA j (EI ) EC ) . In other words, a containment path is a path consisting of construction, alternation and inheritance edges, which satis es the following two properties: an inheritance edge is immediately followed by either a construction edge or an inheritance edge, and the path cannot end with an inheritance edge. The length of containment path p is the number of edges in p. Vertex w is reachable from vertex v if there is a containment path from v to w. Any vertex v 2 V C V A is always reachable from itself via a path of length 0. In order to write containment paths of length 0 and of length greater than 0 in a same form, we use

to express a path from v0 to vn . If n is 0, then it represents a containment path of length 0. We have introduced three kinds of paths: alternation paths, inheritance paths and containment paths. Alternation paths are a special kind of containment paths. Inheritance paths are not containment paths. When we refer to a path p, we mean a containment path, unless we explicitly mention that p is an inheritance path. A cycle in a semi-class dictionary graph is a containment path of length more than 0 from some vertex v back to v.

v0 e1 v1 ::: vi?1 ei vi ::: en vn

16

Semi-class dictionary graphs are not always meaningful for de ning objects. An example of such a semi-class dictionary graph is one which contains two vertices which are in an alternation relationship, but not in an inheritance relationship. Partial class dictionary graphs are a minimal structure su cient for de ning objects.

De nition 5 A partial class dictionary graph P = (V CP ; V AP ; P ; ECP ; EAP ; EIP ) anchored at vertex v0 is a semi-class dictionary graph with the following four properties (VP = V CP V AP ):
1. 8w 2 VP 9v 2 VP : v is reachable from v0 via a containment path and w is reachable from v via an inheritance path. In other words, all vertices in the partial class dictionary graph are reachable from anchor v0 by a containment path followed by an inheritance path. v 2 EIP . 2. 8v=)w 2 EAP : w In other words, alternation edges imply inheritance edges. 3. 8v 2 V AP 9w 2 VP : w v 2 EIP . In other words, there is no alternation vertex without an incoming inheritance edge. l 4. 8v 2 V AP : v = v0 or 9w=)v 2 EAP or 9w ?! v 2 ECP implies 9v0 2 VP s:t: v=)v0 2 EAP : In other words, if an alternation vertex is "used" (i.e., it is v0 or has some incoming construction or alternation edge in P ), then this vertex must have at least one outgoing alternation edge in P . The vertices incident with the edges are also in P.

The intuition of the rst property is that we want to use P to de ne only objects which are instances of vertex v0. The reason for the second property is that the inheritance ancestors have the common structures and behaviors of their inheritance descendants. The reason of the third property is that every alternation vertex must play a role in de ning objects. The reason for the fourth property is that an alternation vertex, corresponding to an uninstantiable class, has to have at least one immediate alternation descendant if vertex v is used as construction or alternation descendant or if v is the vertex we want to build objects of.

De nition 6 A class dictionary graph
such that

= (V C; V A; ; EC; EA; EI ) is a union of partial class dictionary graphs

v=)w 2 EA iff w

v 2 EI:

This de nition is equivalent to the class dictionary graph de nition given in earlier papers Ber91, LX93, etc.]. Those papers also contain further motivations. w, occurs whenever the alternation edge w=)v Since in class dictionary graphs the inheritance edge, say v occurs and vice versa, we usually do not draw inheritance edges in class dictionary graphs as shown in Fig 2. Sometimes when you select several vertices to analyze and implement a part of a system, you need to nd all the required vertices and associated edges. Partial class dictionary graphs of a given class dictionary graph provide such functionality. They are also useful for planning object-oriented systems LH89b]. Informally, a partial class dictionary graph anchored at class C, contains enough classes to build some C-object.
For a class dictionary graph = (V C ; V A ; ; EC ; EA ; EI ), a partial class dictionary graph P = (V CP ; V AP ; P ; ECP ; EAP ; EIP ) of anchored at vertex v0 is a partial class dictionary graph with VP = V CP V AP , which has the following four properties: 1. P is anchored at v0 , i.e. v0 2 Vp . 2. V CP V C , V AP V A , ECP

De nition 7

EC , EAP

EA , EIP

EI and

P

17

Class Dictionary Graph G

G Partial Class Dictionary Graphs of G Anchored at v Partial Class Dictionary Graphs

Semi?class Dictionary Graphs

Figure 14: The relations between concepts
w 2 EI : v w 2 EIP : 3. 8v 2 VP 8v In other words, if a (construction or alternation) vertex v is contained in VP then all inheritance edges outgoing from v in are in P . l l 4. 8v 2 VP 8v ?! w 2 EC : v ?! w 2 ECP : In other words, if a (construction or alternation) vertex v is contained in VP then all construction edges outgoing from v in are in P .
The vertices incident with the edges are also in P.

The reason for the fourth property is that part-of relations between classes are required. Fig. 14 shows the relations between the concepts we introduced so far.

2.2 Object graphs
In this section we formally de ne the set of objects de ned by a partial class dictionary graph and therefore also by a class dictionary graph. We rst de ne three technical concepts: associated, Parts and PartClusters before we de ne object graphs. An associated set of a class de nes the set of instantiable subclasses of the class. Parts de nes the set of parts of a class with their names and types. PartClusters is a generalization of Parts where the part types are given by a set of instantiable classes, using the de nition of associated. The object graph de nition is split into two parts: rst we de ne the structure of object graphs without reference to a partial class dictionary graph and then we introduce the legality of an object-graph with respect to a partial class dictionary graph. JF88] describes the accepted programming rule: \Inherit only from abstract classes". We enforce this rule, since construction vertices can be instantiated, while alternation vertices are not instantiable. All the objects in this model are instantiated from construction vertices. For any vertex v in a class dictionary graph , if we know the set S of all the construction vertices which are alternation-reachable from v, we will know all the possible objects of vertex v. The set S is called the associated set of vertex v.

De nition 8

The associated set of a vertex v 2 V is

A(v) = fv0 j v0 2 V C and v=)v0 g:

18

l Next we introduce the Parts function. The construction edge v ?! w describes a part-of relationship of vertex v with vertex w. The relation is called l. Such relationships can be inherited by inheritance descendants. It is convenient to have the pair (l; w), called a part, which means the relation with vertex w, called l. Therefore each vertex has the parts of its own or inherited from its inheritance ancestors. Consider the class dictionary graph in Fig. 9. Vertex B_Neighbors has two parts, which are (a neighbors; Vertex List) and (b neighbors; Vertex List). Please notice that the rst part is inherited from vertex Neighbors.

v 2V,

De nition 9

Let P be the partial class dictionary graph (V C; V A; ; EC; EA; EI ) anchored at some vertex. For any

Parts(v) = f(l; w) j 9v0 : v

*

l v0 and v0 ?! w 2 EC g:

The PartClusters function is a generalization of the Parts function. For an object of a given vertex, each immediate part-object corresponds to an object of a part class. The function Parts is not su cient to de ne what kind of objects can be in each part. Therefore we replace w with A(w) in the previous de nition to obtain the de nition of part clusters. The result indicates the classes which may be instantiated for each part.
any v 2 V ,

De nition 10 Let P be the partial class dictionary graph (V C; V A; ; EC; EA; EI ) anchored
PartClusters(v) = f(l; A(w)) j 9v0 : v
*
l v0 and v0 ?! w 2 EC g:

at some vertex. For

For example, PartClusters(B Neighbors) = f (a neighbors; fVertex Empty; Vertex NonEmptyListg); (b neighbors; fVertex Empty; Vertex NonEmptyListg) g: Fig. 15 shows an object of class Input, usually called an Input-object. The graph is called an object graph. Each vertex in the object graph corresponds to an instantiation of a construction vertex. Each edge is an instance of a part-of relation. We use i0start i18 to represent the edge from vertex i0 to vertex i18 with label ?! start. In the picture, i0 is the object identi er of the Input-object. And similarly for i1, i2 and etc.

De nition 11 An object graph is a graph H = (W; S; H ; E; ) with vertex sets W , S and edge label set H satisfying the following properties:
1. The function : W ! S maps each vertex of H to a vertex in S . 2. E is a ternary relation on W W H . 3. 8v; w; w0 2 W 8l 2 H :

l l l l v ?! w; v ?! w0 2 E implies v ?! w = v ?! w0 (i.e., w = w0 ):

The rst property says that a vertex in an object graph is an instantiation of a construction vertex. The second property is motivated by the observation that the edges in object graphs are derived from construction edges 19

i0: Input
start

i18: Vertex
name

i19: Ident "1"

graph

marked

i5: MarkUnset

i1:Graph

source rest neighbors

i6: Vertex
name

i7: Ident "1"

rest first

i8: A_Neighbors i9: Vertex_Empty
a_neighbors

marked

i12: Vertex
source neighbors

name

i13: Ident "2"

i14: B_Neighbors

i15: Vertex_Empty

a_neighbors

b_neighbors

i18:Vertex_Empty
rest

i16: Vertex_NonemptyList
first

i19:Ident "1"

name

i17:Veretx

Figure 15: An object of class Input

20

of a class dictionary graph. The third property tells that there are no two edges with the same label outgoing from a vertex in an object graph. Not all object graphs with respect to a partial class dictionary graph are legal. Intuitively, the object structure has to be consistent with the class de nitions and all the classes in S have to be construction classes.

De nition 12 An object graph H = (W; S; H ; E; ) anchored at w0 is a legal v0-object with respect to a partial class dictionary graph P anchored at v0 where P = (V C; V A; ; EC; EA; EI ), if H satis es the following (9! means \there exists exactly one"):
1. S V C and H and 2. 9v 2 V C : v is alternation-reachable from v0 and v = (w0 ), 3. 8 2 W 9!v 2 S s.t. ( ) = v and (a) 8( ; ; l) 2 E : 9!(l; A) 2 PartClusters(v) s.t. ( ) 2 A (b) 8(l; A) 2 PartClusters(v) : 9! 2 W s.t. ( ) 2 A and ( ; ; l) 2 E .

The de nition requires that every vertex in W must be an instance of some construction vertex in the class dictionary graph. The object graph in Fig. 16a is not legal, since vertex Vertex has one part. The object graph in Fig. 16b is not legal, since MarkSet is not in A(Ident), which is fIdentg.
i17: Vertex i17: Vertex
name

i20:MarkSet

(a)

(b)

Figure 16: Illegal objects From now on, when we talk about object graphs we mean that they are legal object graphs, unless we explicitly mention illegality. Next we formally de ne all the object graphs of a class dictionary graph . In database terminology, Objects( ) represents all instances of object base schema .

De nition 13 Let class dictionary graph
An An
-object graph

be (V C; V A; ; EC; EA; EI ).

anchored at , where 2 V C , is an object graph anchored at with ( ) = . -object graph anchored at , where 2 V A, is a -object graph for some 2 V C s.t. =) . 8 2 V C; Objects ( ) = fojo is an -object graphg. 8 2 V A; Objects ( ) = Su2A( ) Objects(u): S Objects ( ) = u2V C Objects(u):

21

Vertex_List

Vertex_List

rest first name

rest first name

Vertex_NonemptyList
(a)

Vertex

Ident

Vertex_NonemptyList

Vertex
(b)

Ident

Vertex_List

Vertex_Empty

Vertex_List

Vertex_Empty

rest first name

rest first name

Vertex_NonemptyList
(c)

Vertex

Ident

Vertex_NonemptyList
(d)

Vertex

Ident

Figure 17: Illustration of partial class dictionary graphs

2.3 Inductiveness of class dictionary graphs
To reduce the complexity of building objects from class dictionary graphs and the software associated with them, we require that class dictionary graphs be inductive. Consider the class dictionary graph in Fig. 17a. Fig. 17b shows the only partial class dictionary graph anchored at vertex Vertex_NonemptyList. Vertex Vertex_NonemptyList forces all the outgoing construction and inheritance edges. Since vertex Vertex_List has an incoming construction edge, it must have the outgoing alternation edge Vertex_List=) Vertex_NonemptyList. Consider the class dictionary graph in Fig. 17c. Fig. 17d shows one of the partial class dictionary graphs anchored at vertex Vertex_NonemptyList. Vertex Vertex_NonemptyList forces all the outgoing construction and inheritance edges. Since vertex Vertex_List has an incoming construction edge, it must have at least one outgoing alternation edge. In this picture, we take alternation edge Vertex_List=) Vertex_Empty. In the class dictionary graph of Fig. 17a, a Vertex_NonemptyList-object must contain a Vertex-object and a Vertex_List-object. A Vertex_List-object must always be a Vertex_Non-emptyList-object | an in nite recursion. In Fig. 17b, this in nite recursion is expressed in the partial class dictionary graph of vertex Vertex_NonemptyList, because the cycle ,
Vertex NonemptyList
rest ?! Vertex List=)Vertex NonemptyList;

is forced be to included. In the class dictionary graph of Fig. 17c, a Vertex_NonemptyList-object must contain a Vertex-object and a Vertex_List-object. But a Vertex_List-object can be a Vertex_Empty-object. In this case, we don't have an in nite recursion. In Fig. 17c, the partial class dictionary graph of vertex Vertex_NonemptyList shows that we can have a Vertex_NonemptyList-object which is a list containing only one element, a Vertex-object. The Vertex_Empty-object is used here for the end of the list. Comparing the two class dictionary graphs in Fig. 17a and Fig. 17c, we can only build cyclic Vertex_Listobjects from the rst class dictionary graph in Fig. 17a; while we can build non-cyclic Vertex_List-objects of 22

any size based on the Vertex_List-objects of smaller size for the second class dictionary graph. We call the class dictionary graph in Fig. 17c, an inductive class dictionary graph; the rst class dictionary graph is not inductive.

De nition 14 A class dictionary graph is inductive if for all vertices v there exists at least one cycle-free partial class dictionary graph anchored at v.
Recall that cycle-free is de ned in terms of containment paths. The purpose of the inductiveness property for a class dictionary graph is 1. to guarantee that the inductive de nitions of the objects which are associated with the vertices of the class dictionary graph, have a base case. Informally, inductiveness disallows classes which have only circular objects. Inductiveness is important to avoid in nite loops in the traversals de ned by propagation patterns. 2. to exclude certain useless symbols HU79, page 88] from the grammar corresponding to a class dictionary graph Lie88]. There are two kinds of useless symbols: the ones which cannot be reached from the start symbol and the ones which are involved in an in nite recursion. The inductiveness property excludes useless symbols of the in nite recursion kind.

2.4 Containment paths and object paths
Relationships between containment paths and object paths are analyzed in this subsection. A containment path is a path in a class dictionary graph, while an object path is a path in an object graph. An object path has the standard graph-theoretic de nition: it is a sequence of adjacent edges in an object graph. One important use of containment paths is to de ne traversals of objects. A containment path is like a non-deterministic program which de nes a pattern of how to traverse objects. One containment path usually de nes many di erent traversals, i.e. many di erent object paths which we call instances of the containment path. Some of the containment paths uniquely de ne one object path for a given object and we call those containment paths completed. We de ne that an object path is the instantiation of a containment path if essentially the construction edges encountered in the containment path match the edges encountered in the object graph. Next we informally derive the containment path concept from a set of requirements. In order to describe the traversal of objects, we need a path concept PATH at the class level. The path concept PATH represents a set of paths and needs to have the following three properties: 1. if there is a path from A to B satisfying PATH, then there exists an A-object which contains a nested B-object. 2. the concatenation of any two paths satisfying PATH, which are from A to B and from B to C, is a path from A to C satisfying PATH. 3. we want to have the weakest path concept: if P is a path concept satisfying 1. and 2. then any path which satis es P also satis es PATH. The motivation for the rst condition is that we want to use paths satisfying PATH to traverse objects and to nd appropriate subobjects. The second condition is needed since we are de ning operations on semiclass dictionary graphs and propagation schemas which involve the concatenation of paths. Namely, we use existing object traversal descriptions to construct a bigger and more complex traversal description. The third is motivated by imposing the least amount of restrictions. The containment path concept is the weakest concept which satis es the three properties. Suppose we give a weaker path concept which allows that alternation edges can follow inheritance edges in a path. The restriction 23

on paths in a regular expression would be (EA j EI j EC) . In other words, there is no restriction at all. Based on this weaker concept, if there is a path from vertex A to B, it is not true that there is a path in an object graph, which goes from an A-object to a B-object. An example is shown in Fig. 18.
Vertex_List

rest

first

Vertex
name

Ident

Vertex_Empty

Vertex_NonemptyList

Figure 18: Weaker path concept =) Vertex_NonemptyList is a weaker path, but no Vertex_Empty-object can contain a -object. Therefore the containment path concept is the weakest path concept to describe the containment relationships between objects, in other words, to describe possible paths between objects. We continue with the path instantiation concept which shows how a containment path describes object traversals. The following discussions are in the context of a partial class dictionary graph, because partial class dictionary graphs are the weakest concept to de ne objects. To check whether an object path instantiates a containment path we perform two tasks recursively (see Fig. 19). First, we skip all consecutive alternation edges (if there are any) in the containment path. Then we check whether there is an alternation path from the target of the last alternation edge to the construction vertex of which the rst object in the object path is an instance of. Second, we nd the rst construction edge in the containment path and we check that the label of the construction edge and the label of the rst edge in the object path coincide. Now we eliminate in the containment path all edges we have visited including the rst construction edge. In the object path we eliminate the rst edge and we continue with the checking recursively. More precisely:
Vertex_Empty Vertex_List Vertex_NonemptyList

De nition 15 Given a containment path p = v0 e1 v1 ::: vi?1 ei vi ::: vn in a partial class dictionary graph P and an object path p0 = w0 e01 w1 ::: wj?1 e0j wj ::: wm in a legal object O of P where n m 0, vi (0 i n) and ei (1 i n) are vertices and edges in P , wj (0 j m) and e0j (1 j m) are vertices and edges in O, object path p0 instantiates containment path p, if the following conditions hold:
1. Find the longest path v0 e1 v1 ::: vr?1 er vr of consecutive alternation edges starting at v0 . If there are no alternation edges, then r = 0. The following must hold:

vr =) (w0 ):
2. If m > 0, then there must be a construction edge in p; let es be the rst construction edge. Assuming es = l1 ls vs?1 ?! vs and e01 = w0 ?! w1, we have 0 (a) ls = l1 and (b) object path w1 ::: wj?1 e0j wj ::: wm instantiates containment path vs ::: vi?1 ei vi ::: vn
0

A consequence of the de nition is that (w1 ) 2 A(v ) but (w0 ) 2 A(v ?1 ) does not always hold (v is the target of the rst construction edge e in de nition 15). For example, Fig. 19 illustrates an example in which the object path from w0 to w3 instantiates the containment path from v0 to v6. (w1 ) is in A(v1 ), but (w2 ) is not in A(v5 ).
s s s s

24

Containment path fromv 0 to v 6 which is also a partial class dictionary graph anchored at v 0

v0

l

1

v1 l
3

v3

v5 l6

¦Ë( w0)
Object path from w0 to w 3

v2

= ¦Ë(w )
1

v4

=

¦Ë(w2)

v6

= ¦Ë( w )
3

w0

l1

w1

l3

w2

l

6

w3

Figure 19: Path instantiations A containment path may describe several traversals. For example, consider the class dictionary graph in Fig. 9 and the containment path Neighborsa neighbors Vertex_List. This containment path describes the traver?! sal which goes from an A_Neighbors-object to a Vertex_Empty-object, or from a B_Neighbors-object to a Vertex_NonemptyList-object. If we want to have a containment path which describes exactly the traversal from an A_Neighbors-object to a Vertex_Empty-object, we have to use the containment path Neighbors=) a neighbors A_Neighbors Neighbors ?! Vertex_List=) Vertex_Empty. We call this containment path com?! pleted, and it is the completion of Neighborsa neighbors Vertex_List. A completed containment path uniquely de nes an object path. Informally, a containment path is completed, if in the containment path we cannot take an alternation edge to an alternation vertex and then immediately follow an outgoing construction or inheritance edge. The containment path must end at a construction vertex. More formally:

De nition 16 Let p be a containment path and p = v e v ::: vi? ei vi ::: vn. p is completed, if the following
conditions hold:
0 1 1 1

1. vn is a construction vertex and 2. if ei is an alternation edge and vi is an alternation vertex, then i + 1 < n and ei+1 is also an alternation edge.

To better describe the relationship between containment paths and object paths, we introduce the completion of a containment path. A containment path p1 is the completion of a containment path p2, if there exists an object path which is an instantiation of both p1 and p2 , and both containment paths must contain the same sequence of construction edges. Furthermore, every alternation vertex v on p1 preceded by an incoming construction and alternation edge must be followed by an outgoing alternation edge. Therefore each such alternation vertex can reach a construction vertex (instantiable) through an alternation path. Formally, 25

De nition 17 Given two containment paths p
2 2 2 2

1 1 1 2 2 = v0 e1 v1 ::: vi1?1 e1 vi1 ::: vn and p2 = v0 e2 v1 ::: 1 i 1 vi?1 ei vi ::: vm in a partial class dictionary graph P where m 0 and n 0, containment path p1 is a completion of a containment path p2 if the following three conditions hold: 1 1 2 2 1 1. v0 = v0 and vn =)vm and 2. p1 is completed and 3. if p2 contains construction edges, p1 contains exactly the same construction edges and in the same order.

The following theorems describe correspondences between containment paths and object paths.
a unique completed containment path p in P such that p instantiates p.

Theorem 1 For a partial class dictionary graph P and0 a legal object O of P and an object path p0 in O there exists
The proof is by contradiction. If there would be more than one completed containment path, then the Unique Label Axiom would be violated. 2

Theorem 2 For every containment path p in a partial class dictionary graph P , there exists a legal object O of P and 0 0
a path p in object O so that p instantiates p.

The proof is by the induction on the number of construction edges on the path. 2 Based on the property of the regular expression (EA j (EI) EC) , we have the following properties of containment paths: 1. Containment paths are closed under concatenation. 2. Splitting a containment path after a construction or alternation edge yields two containment paths. We will build the propagation schema calculus and the propagation directive calculus based on the properties of containment paths discussed in this section.

2.5 Demeter data model summary and extension
So far we only dealt with pure class dictionary graphs which contain construction and alternation vertices and edges. However, in practice we also use optional parts, repetition vertices (for possibly empty and nonempty lists) Lie88]. We outline how we can simulate those extensions with the pure model for the purpose of propagation patterns and growth-plans. In Fig. 20b, the two vertices drawn as are called repetition vertices. Repetition vertex Adjacency_NonemptyList represents a list which contains one or more Adjacency. Repetition vertex Vertex_List represents a list is called an optional construction edge, which contains zero or more Vertex-objects. The edge drawn as which means that an Adjacency-object may or may not contain a Mark-object. The equivalent representation in the pure model is shown in Fig. 20. Table 1 gives a summary of the six increasingly more speci c axiomatic structures used in our method. Semi-class dictionary graphs are a generalization of partial class dictionary graphs, and they in turn are a generalization of class dictionary graphs. Semi-class dictionary graphs are used in the software development process for several purposes: 26

Input
graph

start

Vertex
name source

Ident

neighbors

first

Vertex_List

rest

rest

marked

Mark Unfinished

MarkSet

Vertex_NonemptyList

(a)

Input
graph

start

Vertex
name source

Ident

neighbors

marked

Vertex_List MarkSet Unfinished MarkUnset

Mark

Finished

(b)

Figure 20: Data model extension

27

behavior (not formalized in this paper) Behavior is expressed by selecting edges in a semi-class dictionary graph. Both the selection of a construction and an inheritance edge represents a function call. The selection of a construction edge represents a call for a part and an inheritance edge represents a call to the superclass. The selection of an alternation edge does not represent a call, but it means that the function is late bound. Independent of an edge selection, the classes which are alternation-reachable from a class C inherit from C. subsets of objects (partial class dictionary graphs) A subset of objects is de ned by selecting edges. Selecting a construction edge means that the part is selected. All construction edges outgoing from a selected vertex must be selected. Selecting an alternation edge means that an alternative may be selected. Objects of the selected alternative may be substituted for objects of the class at the source of the alternation edge. Selecting an inheritance edge means that the parts of the target class of the edge are inherited. All inheritance edges outgoing from a selected vertex must be selected. Selecting an alternation edge means that the corresponding inheritance edge is also selected. static class structure (class dictionary graph) Here no selection takes place; we use a complete class dictionary graph. The presence of a construction edge means that a data member will be de ned. An alternation edge implies an inheritance relationship between the two classes. An alternation edge is selected if and only if the corresponding inheritance edge is selected.

3 A succinct representation of semi-class dictionary graphs
After having introduced semi-class dictionary graphs, class dictionary graphs, object graphs and their relationships through the containment path concept, we are now ready to study succinct representations of semi-class dictionary graphs. The motivation for succinctness is that we want to avoid detailed descriptions of graph structures by giving explicitly all the edges and all the vertices. Experience shows that object-oriented programs often only use a small subset of the class structure in an interesting way. With the succinct graph descriptions introduced in this section, we can focus on the interesting parts of the class structures which usually de ne much larger class structures. One succinct description provides an in nite family of class structures. We rst give an example of the use of succinct descriptions for specifying a test phase for our earlier DFT program. In order to test the DFT algorithm for trees in Fig. 3, we may rst use a tree containing only one vertex. Fig. 21 shows a partial class dictionary graph of the class dictionary graph in Fig. 2 anchored at Input. This partial class dictionary graph de nes tree objects with only one vertex. The description in Fig. 22 applied to the class dictionary graph in Fig. 2 exactly describes this partial class dictionary graph. We call the succinct description in Fig. 22 a propagation directive which says that we only take all the containment paths starting from vertex Input bypassing alternation edges Adjacency_List=) Adjacency_NonemptyList and Vertex_List=) Vertex_NonemptyList. The resulting partial class dictionary graph in Fig. 21 is simply the union of these containment paths plus all the inheritance paths which are forced to be included. We also use propagation directives to succinctly describe propagation patterns. Fig. 23 shows a propagation pattern from the example of the DFT algorithm on trees. The propagation directive in this propagation pattern describes the semi-class dictionary graph in Fig. 24. The semi-class dictionary graph shows how to traverse the nested Vertex-objects, which represent the neighbors of an Adjacency-object. The translated C++ code, shown in Fig. 24, de nes the same traversal. The code fragment within begin and end is an annotation to the traversal speci cation and it speci es the statements to be executed when a Vertex-object is reached. 28

semi-class dictionary programming with propagation patterns LXSL91]. graphs and propagation schemas Propagation pattern speci cations de ne semi-class dictionary graphs

Structure

Demeter Data Model Summary Applications

partial class dictio- growth plans LH89b], inductiveness axiom and object nary graphs graphs. class graphs dictionary classes in some object-oriented programming language.
A growth plan is a sequence of partial class dictionary graphs. Inductiveness is de ned in terms of existence of cycle-free partial class dictionary graphs.

called propagation graphs. The propagation graphs are mapped into object-oriented programs.

inductive class inductive object graphs. Objects are de ned inductively. dictionary graphs class dictionaries Lie88] application-speci c object language. LL(1) class dictionar- object construction from sentences. ies
Table 1: The summary

Alternation vertices correspond to abstract classes. Construction vertices correspond to concrete classes. Alternation edges correspond to inheritance relations. Construction edges correspond to part-of relations.

A class dictionary de nes both a class dictionary graph and a language. An LL(1) class dictionary is not ambiguous, i.e. the printing function is one-to-one.

Input
graph

start

Vertex
source name

neighbors

Vertex_List Ident

Vertex_Empty

Figure 21: A partial class dictionary graph used for testing program 29

from Input bypassing =>

Figure 22: A propagation directive

operation void dft(Graph g) from Adjacency through -> , neighbors, to Vertex primary Vertex begin end

Figure 23: A propagation pattern We consider propagation directives as a succinct representation of semi-class dictionary graphs. As shown in the previous examples, propagation directives are robust and easy to reuse. In order to e ectively use them in software design, implementation and testing, we developed a propagation directive calculus.
void Adjacency::dft(Graph *g) { neighbors?>dft(g); }

Vertex

neighbors rest

Vertex_List
void Vertex_List::dft(Graph* g) { }

Vertex_NonemptyList

void Vertex_NonemptyList::dft(Graph *g) { first?>dft(g); second?>dft(g); }

Figure 24: The translated C++ code and corresponding semi-class dictionary graph

3.1 Simple propagation directives
We use the following strategy for introducing propagation directives. First we de ne simple propagation directives which use xed vertex sets as sources and targets. A simple propagation directive is de ned in terms of path constraints and we show how a simple propagation directive de nes an in nite family of graphs, called propagation schemas, from which we can select a member by providing a compatible semi-class dictionary graph to the propagation directive. Then we de ne a propagation schema calculus with three operations (merge, join, connect) which allow us to compose graphs. This graph composition is mirrored in composing programs which traverse objects. Next we introduce three vertex selectors which allow us to describe graph vertex sets in a generic way. Those 30

vertex selectors are used to de ne propagation directives and their mappings into propagation schemas. Finally, the three operations de ned for the propagation schema calculus are now lifted to the propagation directive calculus level. Each simple propagation directive, (F; c; T), has three components. F is a set of vertices from which the containment paths start; T is a set of vertices at which the containment paths end; c is an additional constraint which all the containment paths have to satisfy. For example, the propagation directive in Fig. 23 can be written as (fAdjacencyg; through(
neighbors

?! ); fVertexg):

We call through( neighbors ) a constraint saying that all of the containment paths should contain the con?! struction edges with label neighbors.

3.1.1 Path constraints
In order to reuse propagation directives again and again on di erent class dictionary graphs, we make propagation directives and propagation patterns independent of class dictionary graphs. We can view all the class dictionary graphs which appear in the previous examples as typical representatives of those class dictionary graphs on which the propagation directives can be reused. The typical class dictionary graphs serve as concrete examples to understand and reuse the propagation patterns. Therefore we call all the vertices, edges and labels of construction edges in propagation directives imaginary vertices, edge patterns and imaginary labels, respectively.
~ ~ De nition 18 V is the set of all the imaginary vertices. ~ is the set of all the imaginary labels. E is the set of edge patterns de ned as
l ~ ~ E = fv =) w or v ?! w or v ~ ~ ~ ~ ~

~ w j v; w 2 f g V and ~ 2 f g ~ g: ~ ~ ~ l

For example, neighbors is a construction edge pattern which represents any construction edge with the ?! label neighbors. We say the edge pattern neighbors matches the construction edge Adjacencyneighbors ?! ?! neighbors Vertex_list in Fig. 2, and also matches the construction edge Adjacency ?! Neighbors in Fig. 9.

De nition 19 An edge pattern e 2 E~ matches an edge e in a semi-class dictionary graph S if ~
1. e = v=)w, e = v =) w, v = v or v = , w = w or w = ~ ~ ~ ~ ~ ~ ~ 2. e = v w, e = v ~ ~ w, v = v or v = , w = w or w = ~ ~ ~ ~ ~ ~ l l 3. e = v ?! w, e = v ?! w, v = v or v = , ~ = l or ~ = , w = w or w = ~ ~ ~ ~ ~ l l ~ ~

Now we are ready to de ne path constraints which are used to compose propagation directives. We want to constrain paths in at least two ways: we force them through an edge (using the through predicate) or we make them avoid an edge (using the bypassing predicate). The meaning of through is that the argument edge must be present in a path; the meaning of bypassing is that the argument edge must be absent from a path. The following de nition is more general in that it allows a set of one-argument boolean functions to constrain the paths. 31

De nition 20 Let F

~ 1 be a set of one-argument boolean functions and let E be the set of edge patterns. C (F1 ) is the set of constraints, which is de ned as follows 1. true; false 2 C (F1 ) ~ 2. f (e) 2 C (F1 ) where f 2 F1 , e 2 E 3. if c1 ; c2 2 C (F1 ) then (a) (not c1 ) 2 C (F1 ) (b) (c1 and c2 ) 2 C (F1 )

Not all constraints are meaningful for a semi-class dictionary graph. For example, bypassing( vertex ) is not ?! meaningful for the class dictionary graph in Fig. 2, because there is no construction edge with label vertex. A constraint is meaningful for a semi-class dictionary graph S if it is compatible with S.

De nition 21
1. 2. 3. 4. 5.

A constraint c 2 C (F1 ) is compatible with a semi-class dictionary graph S = (V C; V A; ; EC; EA; EI ) if

c = true or c = false or c = f (e), f 2 F1 and e matches some edge in S or c = c1 and c2 and both c1 and c2 are compatible with S or c = not c1 and c1 is compatible with S .

When we apply a simple propagation directive (F; c; T) to a semi-class dictionary graph, we take all the containment paths from some vertex in F to some vertex in T satisfying the constraint c, and merge them together to have a semi-class dictionary graph. Below is satis ability formally de ned for paths.

De nition 22 A path p of a semi-class dictionary graph S satis es a compatible constraint c 2 C (fthrough; bypassingg)
if 1. 2. 3. 4. 5.

c = true or c = bypassing(e) and p does not contain any edge in S that matches e or c = through(e) and p contains at least one edge in S that matches e or c = c1 and c2 and p satis es c1 and p satis es c2 or c = not c1 and p is a path of S not satisfying c1 .

Based on the meaning of the two boolean functions, through and bypassing, we have the following property for a given semi-class dictionary graph,

not through(e) = bypassing(e): The edge constraint formulas and their semantics for f through, bypassingg contain the boolean formulas and li their semantics as a special case. Consider the semi-class dictionary graph in Fig. 25 with edges e = A ?! B. The variable of the boolean formulas are through(e ), and not and and have the same meaning as in boolean
i

formulas.

i

32

e1

A
ei

B

... ...
en

Figure 25: Example for boolean formulas

3.1.2 Directives
Several simple propagation directives have been introduced, such as (fAdjacencyg; bypassing( neighbors ); fVertexg): ?! We formally de ne SPD as the set of all simple propagation directives.

De nition 23 The set of simple propagation directives SPD is
~ SPD = f(F;c; T ) j F V ; T

~ V and c 2 C (fthrough; bypassingg)g:

Similar to the compatibility of constraints, a propagation directive, such as (fAirplaneg, true, f Wheelg), is not meaningful for the class dictionary graph in Fig. 2, because the class dictionary graph does not contain vertices called Airplane and Wheel. (fVertexg, true, f Inputg) is not meaningful for the class dictionary graph either, since there is no containment path from Vertex to Input. A propagation directive is meaningful for a semi-class dictionary graph, if it is compatible with the semi-class dictionary graph.
S = (V C; V A; ; EC; EA; EI ) if

De nition 24 A simple propagation directive (F; c;T ) is compatible with a semi-class dictionary graph
1. F V C V A and T V C V A and 2. c is compatible with S and 3. 8v 2 F 8w 2 T : there exists at least one containment path in S from v to w satisfying c.

3.1.3 Simple semantic evaluator
Before we formally explain how to apply a simple propagation directive to a semi-class dictionary graph, we de ne the union operator on semi-class dictionary graphs which constructs a new semi-class dictionary graph by taking the union of the arguments.

De nition 25 Consider two semi-class dictionary graphs, S1 = (V C1 ; V A1 ; 1 ; EC1 ; EA1 ; EI1 ) and S2 = (V C2 ; V A2 ; 2 ; EC2 ; EA2 ; EI2 ). We de ne the union operator as follows, S1 S2 = (V C1 V C2 ; V A1 V A2 ; 1 2 ; EC1 EC2 ; EA1 EA2 ; EI1 EI2 ):
33

De nition 26 Given a class dictionary graph S and a simple propagation directive (F; c;T ) compatible with S , we
rst get all satis ed containment paths by the operator de ned below, (F;c; T ) S = fp j p is a containment path satisfying c from f 2 F to t 2 T g Then all the satis ed containment paths are merged into a semi-class dictionary graph S 0 by the operator (F;c; T ) S = (S 0 ; F; T ) where S 0 = (V C (p); V A(p); (p); EC (p); EA(p); EI (p)):

propagate. The result of (F; c; T ) S is a triple.

called

p2(F;c;T ) S

V C (p) is the set of all the construction vertices on p. V A(p) is the set of all the alternation vertices on p. (p) is the set of all the construction edge labels used in p. EC (p) is the set of all the construction edges on p. EA(p) is the set of all the alternation edges on p. EI (p) is the set of all the inheritance edges on p.

The resulting semi-class dictionary graph S 0 (i.e., the rst component of (F; c; T) S) is the merge of all the containment paths satisfying c from vertices in F to vertices in T. Then it is natural to put S 0 , F and T together to have a triple. We call the triple a propagation schema. F and T are included for the purpose of composing propagation schemas. Formally speaking,

De nition 27 A propagation schema PS is a triple (S; F; T ), where
1. S is a semi-class dictionary graph and 2. F and T are subsets of V (S ). F is called the source port of PS ; T is called the target port of PS . source(PS ) = F and target(PS ) = T .

Not all propagation schemas are meaningful. A meaningful propagation schema should be generated by applying some propagation directive (F; c; T) to a semi-class dictionary graph. This is regulated by the axiom below. Legal Propagation Schema Axiom: A propagation schema (S; F; T) is legal, if 1. 8f 2 F 8t 2 T: there exists at least one containment path in S from f to t, 2. 8v 2 V (S)9f 2 F 9t 2 T: there exists a containment path p in S from f to t such that v is on p. We represent an illegal propagation schema as ^. ; When a propagation directive (F; c; T) is not compatible with a semi-class dictionary graph S, we can express it by writing (F; c; T) S = ^: ; The propagate operator has one disadvantage: the union of the containment paths may result in a graph which contains more containment paths. In other words, the propagation schema de ned by a propagation directive may contain more containment paths than speci ed by the directive. This situation has to be avoided and it is studied in Xia93].

34

3.2 Propagation schema calculus
It is quite useful to use existing propagation schemas to compose new propagation schemas. We introduce three operators on propagation schemas, which are +, 1 and . The operator + \merges" its two operands; the operator 1 \joins" its two operands; and the operator \connects" its two operands by suitable paths. We can look at as the operator taking two arguments, a semi-class dictionary graph S and a constraint c. Di erent S and c determine di erent ways to connect its two operands.
S;c S;c S;c

tors as follows:
1

De nition 28 For two given propagation schemas, PS
1 2 1 2 1 1 2 1 2 1 1 2 1

1

= (S1 ; F1 ; T1 ) and PS2 = (S2 ; F2; T2 ), we de ne three opera2 1 2

8 ; ; < (S S ; F F ; T ) if PS 6= ^ and PS 6= ^, and T = T 1. PS + PS = (S S ; F ; T T ) if PS 6= ^ and PS 6= ^, and F = F ; ; :^ ; otherwise ^ 6 ^ 2. PS 1 PS = (S S ; F ; T ) if PS = ; and PS 6= ; and T = F ^ ; otherwise 8 < PS 1 ((T ; c; F ) S ) 1 PS if PS = ; and PS 6= ^ and (T ; c; F ) is 6 ^ ; 3. PS S;c PS = compatible with S :^ ; otherwise
2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 1 2 1 2

where S is a semi-class dictionary graph and c is a path constraint.

The rst de nition has the property that if one of the rst two cases applies then the result has the two properties of the Legal Propagation Schema Axiom. The result is unde ned only if the third case applies. Similarly, the second and third de nitions have the property that if the rst case applies then the result has the two properties of the Legal Propagation Schema Axiom. The result is unde ned only if the second case applies. The three operators are illustrated in Fig. 26. Each propagation schema is a unit with a source port and a target port. Each port is de ned by a nonempty set of vertices. The addition of PS1 and PS2 is the union of source ports, target ports and containment paths separately. The join of PS1 and PS2 is to plug PS2 into PS1, when the target port of PS1 is the same as the source port of PS2. The connection of PS1 and PS2 through falls into two steps: 1. construct a new propagation schema from S by taking the target port of PS1 as its source port, the source port of PS2 as its target port and following constraint c. 2. plug the three propagation schemas together with the new one in between. The following rules are useful to analyze and simplify the composition of propagation schemas.
S;c

Commutative Laws

1. PS1 + PS2 = PS2 + PS1 2. PS1 1 PS2 = PS2 1 PS1 i source(PS1) = target(PS2 ) = source(PS2) = target(PS1 ). 3. PS1 PS2 = PS2 PS1 if source(PS1) = source(PS2) and target(PS2) = target(PS1).
S;c S;c

Associative Laws
1. PS1 + (PS2 + PS3 ) = (PS1 + PS2) + PS3 2. PS1 1 (PS2 1 PS3) = (PS1 1 PS2) 1 PS3 35

propagation schema (S,F,T) semi?class dictionary graph S

source port F

target port T

F1

F2

F1

F2

F1

F2

F1 = F2

T1

T2

T1 = T2

T1

T2

T1

T2

F1 F1 F1 F2 F1 F2

S,c

T1

T2 T2

T1

T2 T2

Figure 26: Propagation schema calculus 3. PS1
S1 ;c1

(PS2

S2 ;c2

PS3 ) = (PS1

S1 ;c1

PS2 )

S2 ;c2

PS3

Distributive Laws
(PS1 + PS2 ) 1 PS3 = (PS1 1 PS3 ) + (PS2 1 PS3 ) i target(PS1) = target(PS2) = source(PS3) PS1 1 (PS2 + PS3) = (PS1 1 PS3 ) + (PS1 1 PS3 ) i source(PS2) = source(PS3) = target(PS1) (PS1 + PS2 ) PS3 = (PS1 PS3) + (PS2 PS3 ) PS1 (PS2 + PS3 ) = (PS1 PS2) + (PS1 PS3 ) PS1 + (PS2 1 PS3) = (PS1 + PS2 ) 1 (PS1 + PS3) i source(PS3) = target(PS2) and source(PS1) source(PS3) = target(PS1) target(PS2) 6. PS1 + (PS2 PS3 ) = (PS1 + PS3 ) (PS1 + PS3) if source(PS1) source(PS3) = source(PS3) and target(PS1) target(PS3) = target(PS2) 1. 2. 3. 4. 5.
S;c S;c S;c S;c S;c S;c S;c S;c

Idempotent Laws
1. PS1 + PS1 = PS1 2. PS1 1 PS1 = PS1 i source(PS1) = target(PS1) 3. PS1 PS1 = PS1 if PS1 = (S1 ; F1; T1) and (T1 ; c; F1) is compatible with S and (T1 ; c; F1) S = (S 0 ; T1 ; F1) and S1 + S 0 = S1 .
S;c

36

3.3 Propagation directives
Suppose that we have a large complex semi-class dictionary graph S and we want to apply di erent propagation directives to S to have various propagation schemas for di erent purposes. Sometimes we may want rst to use a propagation directive on S to trim S to a simpler propagation schema, and then we can more easily write propagation directives which will be applied to the simpler propagation schema to obtain the desired result. For the same reasons as we need a propagation schema calculus, we need a propagation directive calculus to compose propagation directives. Therefore we introduce a set of more general propagation directives, which cover simple propagation directives. But rst we introduce vertex selectors which are used to construct propagation directives. We use three kinds of vertex selectors which allow us to generically choose sets of vertices. The rst selector simply selects a set of vertices from a semi-class dictionary graph. The second one selects a set of vertices which are reachable from a given set through paths satisfying a constraint. The third selector chooses all the vertices of a given semi-class dictionary graph. This set of vertex selectors is called V S. The diamond operator is used to apply a vertex selector from V S to a semi-class dictionary graph.

De nition 29 V S is a set of vertex selectors of the following three forms. is an operator to select vertices from a given semi-class dictionary graph.
0 ~ 1. rV where V V and V 6= ; For any semi-class dictionary graph S , 0 rV S =

V if V

; otherwise

V (S )

c 2. rV For any semi-class dictionary graph S , c rV

In other words, we take all the vertices which are reachable from vertices in V via containment paths of length 0.

c. 3. r

In other words, we take all the vertices which are reachable from vertices in V through containment paths satisfying For any semi-class dictionary graph S , In other words, we take all the vertices from S .

( fr j r is reachable from some v 2 V via some containment path if V V (S ) S = satisfying path constraint cg ; otherwise

r S = V (S ):

We give more general propagation directives which cover simple propagation directives.

De nition 30 The set of propagation directives PD is

PD = f(f; c; t) j f; t 2 V S and c 2 C (fthrough; bypassingg)g:

For any semi-class dictionary graph S , the propagate operator is de ned on propagation directives as (f;c; t) S = (f S; c; t S ) S where (f S; c; t S ) is a simple propagation directive. (f; c;t) is compatible with S if (f;c; t) S 6= ^. ;

37

Four operators are introduced below to compose propagation directives. The operators, +, 1 and correspond to the operators, +, 1 and in the propagation schema calculus. The propagate operator is generalized.
c S;c

De nition 31 PDE is the set of propagation directive expressions, which is de
1. 2. 3. 4. 5.

ned as

PD 2 PDE , d1 + d2 2 PDE if d1 ; d2 2 PDE , d1 1 d2 2 PDE if d1 ; d2 2 PDE d1 c d2 2 PDE if d1 ; d2 2 PDE . c is a path constraint. d1 d2 2 PDE if d1 ; d2 2 PDE

We generalize the propagate operator to propagation schemas and propagation directive expressions. Suppose (S 0 ; F; T) is a propagation schema, S is a semi-class dictionary graph or a propagation schema. We have 1. 2. 3. 4. 5. d1 (S 0 ; F; T) = d1 S 0 (d1 + d2) S = d1 S + d2 S (d1 1 d2) S = d1 S 1 d2 S (d1 d2) S = (d1 S) (d2 S) (d1 d2 ) S = d1 (d2 S)
c S;c

Not all propagation directive expressions can be meaningfully applied to a semi-class dictionary graph. A propagation directive expression d is compatible with a semi-class dictionary graph S i d S 6= ^. A ; propagation directive expression d is consistent if there exists a semi-class dictionary graph which is compatible with d. A propagation directive expression d is compatible with a propagation schema (S; F; T) i d is compatible with S. Propagation expressions have much more expressive power than simple propagation directives. For example, for any given semi-class dictionary graph S, (r ; true; r ) S = (S; V (S); V (S)). In other words, the result contains exactly the semi-class dictionary graph S. If (r ; true; r0 ) is compatible with a semi-class dictionary graph S where T = ftg, then vertex t is reachable from every vertex in S via some containment path. t is called a sink of semi-class dictionary graph S. We cannot use any simple propagation directive to express that. We list several rules which the four operators satisfy (without proof). The rules are useful for constructing propagation directive expressions.
T

Commutative Laws

1. d1 + d2 = d2 + d1 The following three equalities do not always hold. 1. d1 1 d2 = d2 1 d1 2. d1 d2 = d2 d1 3. d1 d2 = d2 d1
c c

38

Associative Laws
1. 2. 3. 4. d1 + (d2 + d3) = (d1 + d2) + d3 d1 1 (d2 1 d3 ) = (d1 1 d2) 1 d3 d1 (d2 d3) = (d1 d2) d3 d1 1 (d2 2 d3) = (d1 1 d2)
c c c

c2

d3

Distributive Laws
1. 2. 3. 4. (d1 + d2) 1 d3 = (d1 1 d3 ) + (d2 1 d3): d1 1 (d2 + d3) = (d1 1 d2 ) + (d1 1 d3): (d1 + d2) d3 = (d1 d3 ) + (d2 d3): d1 (d2 + d3) = (d1 d2 ) + (d1 d3):
c c c c c c

The following two equalities do not always hold. 1. (d1 + d2) d3 = (d1 d3) + (d2 d3 ): 2. d1 (d2 + d3 ) = (d1 d2) + (d1 d3 ):

Idempotent Laws
1. d1 + d1 = d1 2. d1 d1 = d1 Similar to the reason in the propagation schema calculus, the following two equalities do not always hold. 1. d1 1 d1 6= d1 2. d1 d1 6= d1
c

Absorption Laws
1. d1 (d1 + d2 ) = d1 The following two equalities do not always hold. 1. d1 + (d2 d1 ) = d1 2. d1 + (d1 d2) = d1
c

39

3.4 Simplifying propagation directives
Given a propagation directive, we always have to simplify it before it is applied to a semi-class dictionary graph. The theorem below gives the simplifying rules.

Theorem 3 Suppose that f and t are vertex selectors and c is a constraint. We always have
1. (f;c1 or c2 ; t) = (f; c1 ; t) + (f; c2 ; t) where c1 or c2 = not (not c1 and not c2 ) 2. (f;c1 and c2 ; t) = (f; c1 ; t) (f; c2 ; t)

3.5 Extended propagation schemas
For a given propagation schema PS = (S; F; T) computed from a class dictionary graph G, semi-class dictionary graph S is not always a partial class dictionary graph anchored at some vertex v satisfying the four properties mentioned in De nition 7. For example, the propagation schema shown in Fig. 27a is the result of applying the propagation directive in Fig. 22 to the class dictionary graph in Fig. 2. But the resulting semi-class dictionary graph is not a partial class dictionary graph anchored at any vertex with respect to the class dictionary graph in Fig. 2. The reason is Adjacency_List and Vertex_Empty Vertex_List, that the two inheritance edges, Adjacency_Empty are not present in the semi-class dictionary graph in Fig. 27a. By adding the two inheritance edges, we obtain a partial class dictionary graph anchored at Input shown in Fig. 27b. In this example, it is not possible to nd a propagation directive expression d such that when d is applied to class dictionary graph tree in Fig. 2 we get a partial class dictionary graph anchored at Input in Fig. 27b. To solve this problem, we rst apply d to class dictionary graph tree to get propagation schema PS. Then based on the third property in De nition 7 we add all the forced inheritance edges to PS. We called the result an extended propagation schema PS 0 . Finally we check whether the semi-class dictionary graph in PS 0 is a partial class dictionary graph anchored at Input with respect to class dictionary graph tree.

De nition 32 For a propagation schema (S; F;T ) computed from a class dictionary graph G where S = (V C; V A; ; EC; EA; EI ) and S 0 = (V C 0 ; V A0 ; 0 ; EC 0 ; EA0 ; EI 0 ), its extended propagation schema (S 0 ; F; T ) is obtained in the following two steps. 1. First we make PS 0 the same as PS , i.e., V C = V C 0 and V A = V A0 and = 0 and EC = EC 0 and EA = EA0 and EI = EI 0 . 2. Then for any vertex v in V C V A and any vertex w in V C 0 V A0 , if w v 2 EI then we add w v to EI 0 0 or V A0 depending whether v is in V C 0 or V A0 . and v to V C

Therefore to check whether when a propagation directive expression d is applied to a class dictionary graph G we get a partial class dictionary graph anchored at vertex v with respect to G, we check the extended propagation schema of d G instead. In the next section, we will use extended propagation schemas to construct growth plans.

40

Input
graph

start

source

Vertex
name

neighbors

Vertex_List Ident

Vertex_Empty

(a)

Input
graph

start

Vertex
source name

neighbors

Vertex_List Ident

(b)

Vertex_Empty

Figure 27: Partial class dictionary graph derived from a propagation schema

41

4 Propagation patterns and test plans
We use propagation directives, a robust and reusable representation, to describe semi-class dictionary graphs, instead of explicitly selecting every single edge. A propagation directive de nes a set of containment paths which select a group of edges. The propagation directive calculus is used to precisely construct the desired paths for a family of class dictionary graphs. A containment path exactly describes a traversal of objects. We will informally show how propagation directives are used in propagation patterns, and how propagation directives de ne a growth-plan which is used to test software.

4.1 Propagation patterns
Propagation patterns can express any C++ program, but propagation patterns are much more robust through late binding of methods to classes. A propagation pattern such as the one in Fig. 28(from Fig. 3) de nes a family of C++ programs from which we can select members by giving a class dictionary graph. We have seen earlier how the class dictionary graph in Fig. 2 selects the C++ program in Fig. 24. Next we use the class dictionary graph in Fig. 9 to select a C++ program which is shown in Fig. 29. This injection into di erent class structures is a part of the process when component graph_cycle is reused inside component 2_graph_cycle.

operation void dft(Graph from Adjacency through -> , neighbors, to Vertex primary Vertex begin end

g)

Traverse an Adjacency-object and locate all the Vertex-objects which are reachable through the neighbors relationship. For each such Vertex-object, find and visit the corresponding Adjacency-object in graph g.

Figure 28: An propagation pattern for the DFT algorithm The semi-class dictionary graph in Fig. 29 shows the propagation schema de ned by the propagation directive of the propagation pattern. The equivalent C++ member functions are also shown in the gure. Construction edges are translated into function calls to the immediate part-objects. Inheritance edges are translated into function calls to superclasses. Alternation edges are interpreted as delayed binding of methods. LXSL91] describes formally how propagation schemas are translated into equivalent C++ code. In the rest of this paper, we will focus on how propagation directives are used to de ne object sets in software testing.

4.2 Test plan design
After a program has been modi ed, it needs to be tested. This is an important and expensive part in software maintenance. Software testing is the primary method by which testers establish con dence in the correctness of software DO91]. In this paper, we propose a robust way to describe the domain of test inputs. We will not talk about how to choose input sets from the domain. When we select the C++ program, by using the class dictionary graph in Fig. 9, from a family of C++ programs de ned by component graph_cycle in Fig. 8, we want to test the program incrementally. Initially we use very simple inputs which exercise only a part of the propagation patterns. Then we make the inputs more and more 42

void Adjacency::dft(Graph *g) { neighbors?>dft(g); }
neighbors

Neighbors void A_Neighbors::dft(Graph *g) { this?>Neighbors::dft(g); } A_Neighbors
a_neighbors

void Neighbors::dft(Graph *g) { a_neighbors?>dft(g); } void B_Neighbors::dft(Graph *g) { b_neighbors?>dft(g); this?>Neighbors::dft(g); } B_Neighbors
b_neighbors

Vertex_List

void Vertex_List::dft(Graph* g) { }
rest

Vertex_NonemptyList

first

void Vertex_NonemptyList::dft(Graph *g) { first?>dft(g); second?>dft(g); }

Vertex

Figure 29: Propagation schema

43

complex until all of the propagation patterns have been su ciently exercised. We organize the inputs in the following sequence: 1. 2. 3. 4. trees with one vertex and no edges, trees, graphs with edges of one kind and graphs with edges of two kinds.

Each test phase contains a set of inputs which can be used for testing. We can use a partial class dictionary graph to describe the set of test inputs. Sometimes, a partial class dictionary graph can not describe exactly the desired object set. The constraints which cannot be expressed by the partial class dictionary graph can be checked by additional code.
P1:
Input
start graph

Ident
name

marked

source neighbors

Graph
rest

first

Neighbors

Mark A_Neighbors
a_neighbors

Figure 30: Growth phase one Fig. 30, Fig. 31 and Fig. 32 contain three partial class dictionary graphs of 2_graph (Fig. 9) anchored at vertex Input. The partial class dictionary graph P1 of Fig. 30 de nes objects which are trees with one vertex and no edges; the partial class dictionary graph P2 of Fig. 31 de nes both objects which are trees and objects which are graphs with edges of one kind3; the partial class dictionary graph P3 of Fig. 32 de nes objects which are graphs with edges of two kinds3. Since the partial class dictionary graph of Fig. 31 de nes both objects which are trees and objects which are graphs with edges of one kind, we need a program (in Fig. 33) to check whether an Input-object represents a tree. Instead of listing the three exact partial class dictionary graphs, we use propagation directives to describe them. Propagation directives are robust and reusable descriptions. For example, during the early software development
3

The parts of the class dictionary graph which have been added at this phase are circled by dotted lines.

44

P2:

Input
start graph

marked name source neighbors adjacencies rest first

Ident

Graph

Neighbors

first

Mark A_Neighbors Unfinished

a_neighbors

rest

Vertex_Empty

Vertex_NonemptyList

Figure 31: Growth phases two

P3:

Input
start graph

name source neighbors adjacencies rest first marked

Ident

Graph

first

Neighbors

Mark A_Neighbors Unfinished
a_neighbors b_neighbors

B_Neighbors

rest

Vertex_Empty

Vertex_NonemptyList

Figure 32: Growth phase three 45

component tree check schema examples 2 graph reuse component 1 graph dft operation void visit(Graph *g) primary MarkSet begin end
tree check

Component speci cation

Explanation

An Adjacency-object cannot be visited twice in a tree.

end

cout << The input is not a tree\n''; exit(0);

Figure 33: Checking the tree property period, the class structure keeps being changed due to some re nement and improvement in the requirements, design and implementation. We use propagation directives d1, d2 and d3 to construct the three partial class dictionary graphs. Vertex selec0 tors from de nition 29 play a prominent role in de ning the directives. They are d1 = (rfInputg; c1; rf1 Inputg), 0 0 2 3 d2 = (rfInputg; c2; rfInputg), d3 = (rfInputg; c3; rfInputg) where
c c c

c1 = bypassing( =)MarkSet) and bypassing( =)Finished), c2 = bypassing( =) B Neighbors) and c3 =bypassing( =) Adjacency NonemptyList) and bypassing( =)Vertex NonemptyList): First we use propagation directive d1 to take out vertices MarkSet and Finished from class dictionary graph 2 graph. The extended propagation schema (de ned in Section 3.5) of d1 2 graph is P3. Based on propagation directives d1 , we give propagation directive d2 to take away vertex B_Neighbors. The extended propagation schema of (d2 d1 ) 2 graph is P2. Based on propagation directives d1 and d2, we give propagation directive d3 to take away alternation edges Adjacency_List=) Adjacency_NonemptyList and Vertex_List=) Vertex_NonemptyList. The extended propagation schema of (d3 d2 d1) 2 graph is P1. Generally, based on the dependencies between propagation patterns, we can always decompose a given system written with propagation patterns into small controllable units. To test the units independently, we may provide auxiliary propagation patterns. We call each such unit a test unit. After successfully testing these units, we integrate them into bigger test units. This process continues until the whole system is completely tested. Evolution histories introduced in this paper help to organize testing. Component graph_cycle in Fig. 8 is a test unit with an input argument of type Input. If this test unit is considered large, it can be decomposed. For example, the propagation pattern of find is a test unit with two input arguments of type Graph and of type Vertex and with outputs of type Adjacency. Once this propagation pattern is tested, we can continue to test component graph_cycle. To test each test unit, we construct a sequence of increasingly more complex partial class dictionary graphs for each input argument of the test unit. Formally, consider a test unit U belonging to a component which is applied to class dictionary graph G. Test unit U is the implementation of a function F : I1 ::: I ::: I ?! O. O is the type of its outputs and I , 1 i q, is the type of its ith input argument. I , 1 i q, is a vertex in G. For the ith input argument, we construct a sequence of partial class dictionary graphs of G anchored at I for de ning I -object sets. The sequence of partial class dictionary graphs anchored at I is called the growth plan GP anchored at I with respect to G. We call all the growth plans GP , 1 i q, together a test plan of the test unit.
i q i i i i i i i i

46

A growth plan GP anchored at vertex v with respect to a class dictionary graph G is a sequence of partial class dictionary graphs, P1; :::;Pi; :::;Pn , anchored at v with respect to G. v-Objects(Pi+1 ) v-Objects(Pi ), i.e. partial class dictionary graph Pi+1 de nes more v-objects than partial class dictionary graph Pi (1 i n). Let U be a test unit U : I1 ::: Ii ::: Iq ?! O with Ii 2 V (G), O 2 V (G), 1 i q. Test unit U belongs to a component applied to a class dictionary graph G. A test plan TP of U is a list of GP1 , ..., GPq where GPi , 1 i q, is a growth plan anchored at Ii with respect to G.

De nition 33

In the above example, we have a test plan containing one growth plan. The growth plan contains three growth phases de ned by three propagation directive expressions, (d3 d2) d1, d2 d1, d1. The second growth phase de ned by d2 d1 de nes both trees and graphs with edges of one kind. We use the program in Fig. 33 to subdivide this growth phase into two subdivisions. The rst one de nes the set of tree objects, and the second one de nes the objects of graphs with edges of one kind. Therefore we have a sequence of four increasingly more complex object sets to test the cycle checker. In this paper we do not give a comprehensive method for nding good test units and how to nd suitable test objects for them. It is a di cult task, even at the level of logical circuits, to nd a \small" number of inputs which exercise all parts of a given circuit properly. More information on testing object-oriented software is in Ber93]. However, we focus on a metric for growth plans and on a simple requirement which the test inputs must satisfy in order to give a very minimal test coverage. A growth-plan anchored at v is complete if any v-object which can be used for testing must be a legal object of some partial class dictionary graph anchored at v in the growth-plan. In other words, a complete growth-plan anchored at v covers all the v-objects which may be used as inputs for testing. The last partial class dictionary graph in a growth-plan with respect to class dictionary graph G is not necessarily G. The reason is that G may contain auxiliary classes which are not needed for describing input objects. For example, the class dictionary graph in Fig. 9 contains class Finished which does not appear in the last growth-phase in Fig. 32.

De nition 34 A growth-plan GP anchored

at v in a class dictionary graph G is complete if the last partial class dictionary graph anchored at v is of maximum size.

A growth-plan which consists of a long sequence of slowly increasing partial class dictionary graphs is good. The reason is that in general the addition of a small number of classes and edges requires a small amount of additional code to be tested. We try to test in small incremental steps to avoid testing software in big chunks. Therefore we minimize the complexity of a growth-plan GP anchored at v in a class dictionary graph G by minimizing the metric (GP) de ned below.

P E(G) j (GP) = j V (G) j + jm
n i

=1

i

There are n growth phases in GP. m is the number of subdivision of growth phase i. V (G) is the set of vertices in G. E(G) is the set of edges in G. For testing propagation patterns, the metric (GP) has to be re ned. We motivate this statement by two examples, but we don't give a formal generalization. Consider a class dictionary graph in Fig. 34 de ning a Company class and the propagation pattern in Fig. 35 which sums all the salaries. Since the only interesting work is done in class Number, it would not be useful to include in the growth-plan several phases anchored at Company and only the last one including class Number. All the phases, except the last one, would simply test the default traversal code. But that code is unlikely to fail since it is provided by the semantics of propagation patterns.
i

47

Company

hires

Employees

Employee

salary

amount Number Salary

Figure 34: Class dictionary graph for computing the total salary

operation void add salary(int& s) from Company to Salary to Number primary Number begin s = s + val; end
Figure 35: Adding salaries By a similar argument, it would not be useful to include in the growth-plan several phases all anchored at Customer and all containing both Company and Number. It would be good enough to run the program on the last phase. If there is a mistake in the salary addition, it would be easy to locate the only class where there could be an error, namely class Ident. Therefore, for testing propagation patterns it is not always important that the (GP) metric be minimized; it is sometimes possible to combine several phases into one. Next we discuss minimal requirements on test inputs. Given a legal v-object O of a class dictionary graph G, we can e ciently nd a partial class dictionary graph P anchored at v and of minimum size such that O is a legal object of P. We call the process of nding the minimum partial class dictionary graph EXTRACT(G; O). Once we have designed a test plan, we need to select enough input objects de ned by each partial class dictionary graph for testing. How many objects do we need to select? To answer the question, we give a minimal requirement for test inputs.

De nition 35 A set of input objects Oi (1 i n) of a partial class dictionary graph P is minimally adequate if

the union of all the partial class dictionary graphs obtained from applying the process EXTRACT(P; Oi ) (1 i n) on each input object Oi is P .

We have experimented with algorithms for automatic growth-plan design LH89b], but they turned out not to be useful. The reason is that writing a good growth-plan requires knowledge of the semantics of the application. Therefore, we leave now growth-plan design to the human designer, but we supply a checker which checks the consistency of the growth-plan and test input sets. Given a class dictionary graph G and a propagation directive expression d which is compatible with G, the extended propagation schema of d G is not always a partial class dictionary graph. But for designing a growthplan we expect the result to be a partial class dictionary graph. One way to solve this problem is to design 48

an algorithm to add more vertices and edges to have a partial class dictionary graph. We call this process completion. Unfortunately it is an NP-complete problem4 to nd a minimum number of vertices and edges to have a partial class dictionary graph. Although we could use a search algorithm to complete, the result would not always be useful in practice. Therefore we require users to write an appropriate propagation directive expression to yield a partial class dictionary graph.

5 Related work
There exists a large body of related work some of which we discuss below.

Modules

Stepwise re nement

The primary form of abstraction in most object-oriented programming languages is the class. However reusable software components, in general, are much more complex than classes KG87], for example, Ada packages. The major di erence between components introduced in this paper and Ada packages is that we use a class dictionary category as a parameter of a component, instead of types. A class dictionary category is expressed in terms of constraints, such as path constraints. When a component is rst developed for a class dictionary graph, we write the propagation patterns in the component in a generic way, in the sense of making propagation directives and code fragments minimally dependent on the class dictionary graph. When a new class dictionary graph is applied to the component, like the instantiation of a package, the component is adapted to the new environment through analogical reasoning. Therefore a component in fact represents a family of in nitely many reusable programs. In contrast, when a generic Ada package is instantiated, there is no adaptation of the program based on analogical reasoning. A signi cant di erence between Components and \modules" and their interconnection languages PDN86] are that each component describes a family of reusable programs, and that each component, after being applied to a class dictionary graph, can be executed and tested so that software developers can check their designs and have more con dence to move on. This will shorten feedback cycles during software development. The development of a complex system needs simpli cation Wir71]. A big complex problem is simpli ed and decomposed into smaller and simpler subproblems through data and functionality simpli cation; subproblems are re ned step by step and integrated to solve the original problem. This creates more possibilities to reuse components which appear at several re nement levels. Evolution histories are used for describing re nements and Components are a structuring mechanism for describing the building blocks of evolution histories. During a software life-cycle, the software often needs restructuring due to improvements of its design and new requirements Cas92, Gra92]. With this in mind, software developers can write components with minimal assumptions on the class structure so that components can be re ned and reused easily as illustrated in the examples of this paper. The painful source code scavenging can be avoided. In the new environment, the constraints on test input sets in terms of propagation directives can also be reused.

Class restructuring

Reuse

The papers in Fre86] describe a considerable amount of previous work. Our work has one distinguishing feature: The adaptiveness of programs by analogical reasoning based on a path concept in data models. Propagation patterns may be used to describe families of ordinary application frameworks JF88, BO92]. There are several di erences between application frameworks and propagation patterns:

4

See Section 7.

49

Application frameworks reuse object code while propagation patterns rely on the reuse of source code. A propagation pattern usually implements a signature in terms of propagation which will a ect the implementation in the new class structure. Propagation patterns are written in terms of a schema which acts as generator of generators, the generators being propagation patterns. Propagation patterns are at a higher level of abstraction than application frameworks since they adapt to changing class structures. Application frameworks are rigid artifacts while propagation patterns are exible structures which adjust more easily to change. In propagation patterns, signatures are strongly localized.

Using schemas for programming

In the database eld, our work builds on techniques for data navigation in the hierarchical database model. Tsichritzis and Lochovsky write in TL82]: "The restrictions on the connections between records in a hierarchical data model permits the selection of a set of records according to hierarchical paths." In MS89], Markowitz and Shoshani state: \In order to express database queries, users are often required to remember and understand large, complex database structures. It is important to relax this requirement by allowing users to express concise (abbreviated) queries, so that they can manage with partial or even no knowledge of the database structure". We share the same intuition, but not only for querying a database, but for programming in general. Schema evolution is an important topic for object-oriented data bases DZ91]. Propagation patterns facilitate evolution of the dynamic part of a schema. In AB92], Aksit and Bergmans write: \Many object-oriented methods ... expound the importance of domain knowledge while preparing the user's requirement speci cations. Integrating the domain knowledge with these speci cations, however, can create an excessive number of objects, although only a few of these objects may be relevant to the problem ..." Propagation patterns address the issue on focusing on the interesting objects. The imaginary classes and relationships focus on what is important to the problem and the \unimportant" classes are either ignored or code is produced automatically for them. A propagation pattern is a view of an integrated (and properly extended) domain model. Rumbaugh Rum88] has proposed an operation propagation mechanism. The most signi cant di erence is that his is run-time based while our mechanism is compile-time based and geared towards a new method for developing object-oriented software. In HO91], Harrison and Ossher propose a means of propagating messages between objects that are widely separated in the network of objects that contain them.

Programming by example

Meta-level software structures

Propagation patterns are self-contained speci cations which de ne requirements for schemas which can be used with them. A propagation pattern is usually developed and tested for an example schema, although a propagation pattern works for many more schemas. Therefore, propagation pattern programming is an advanced form of programming by example. Programming by example was an active topic in the early 1970s BK76]. Programs were derived from examples of inputs and corresponding outputs. In our case, we write a program for a sample data structure and we automatically generalize this program to other data structures.

Rao Rao91] de nes implementational re ection as re ection involving inspection and/or manipulation of the implementational structures of other systems used by a program. He argues that implementation architectures be made explicit and open, allowing customization. Propagation patterns follow this approach. A key question behind writing generic software is: what is the level of \instantiation-look-ahead" which is needed for writing a generic algorithm. If the generic algorithm needs to account for each possible use, 50

Programs parameterized by schemas

then it will be di cult to write and reuse. It is our experience that propagation patterns have a small \instantiation-look-ahead". For example, writing generic algorithms in contract form HHG90, Hol92] requires more planning on how the contract will be used. Compare the implementations of cycle-checking in Hol92] and the solution presented in this paper. However, contracts and propagation patterns can be combined in a useful way which is a topic for further research.

Generic parsers, scanners, printers, attribute grammar evaluators (or their generator versions), are all examples of programs parameterized by schema-like information. With propagation patterns we provide a generic mechanism for writing the above programs in a more generic way. For example, if a generic parser is properly written with propagation patterns, we get a family of generic parsers which can parse generically for a large variety of grammar structures.

6 Conclusions
It has been a long time e ort to increase software productivity and maintainability. The main contributions of this paper are that we allow a programmer to incrementally write succinct high-level representations of programs so that his/her programs can be easily adapted to new environments and evolved, and to constrain object descriptions through growth-plans for program testing. Therefore development productivity and software maintainability are increased. This paper formalizes important parts of the Demeter Method which is under development at Northeastern University since 1985. The Demeter Method promotes a new paradigm for software development which accomplishes much of the work by manipulating graphical structures LXSL91, LHSLX92, Lie92, HSX91]. The Method introduces delayed binding of methods to classes which signi cantly raises the level of abstraction since programs can be written without extensive hardwiring of class structures in them. The higher level of abstraction leads to software which is more reusable in a variety of changing class structures. At the implementation level, the higher level of abstraction requires an additional binding time, which we call propagation time. Since much of the programming task is done by manipulating graphs, the Demeter program description language has facilities to succinctly express and manipulate graph structures as described in this paper. Of course, not all the programming can be done just by manipulating graphs which de ne object traversals. Therefore there is a program fragment composition facility which allows to express the code needed for the \interesting" classes. Traversal code can be either annotated by adding code before and/or after the default traversal code, or overridden by providing new code. The Demeter Method starts from objects whose structure is described at the class level by class dictionary graphs. Once we have the important class relationships in rm place, we use a program description notation to de ne the program we want. This is much more productive than writing the program directly in a programming language since many methods in object-oriented programs contain trivial code WH91]. When we write the program description we only make "minimal" assumptions on the class structure since it is very likely to change (especially, since the initial class structure was obtained without paying very detailed attention to the functionality). Our research group has used propagation patterns extensively in our work. Hundreds of attendees of our courses have used propagation patterns successfully in their projects. For example, Sagesser Sag91] has implemented propagation patterns for Turbo Pascal which help him to do his client projects faster and also to react faster to requirement changes. We plan to develop the Demeter Method in the following directions: 1. An e cient mechanism to retrieve reusable components from a large component library. 2. A disciplined mechanism to personalize and adapt reusable components. 51

Acknowledgements
An early version of this paper, using a di erent growth-plan concept, was written jointly with Carl Woolf LW89]. The anonymous reviewers have given very detailed feedback on previous versions of the paper which has significantly improved the presentation. The axioms for class dictionary and object graphs are key ingredients to other papers where we present results of the theory of class dictionary graphs LBSL91, BL91, LX93]. Propagation patterns, which are only de ned informally in this paper, were developed jointly with Ignacio Silva-Lepe. We would like to thank Paul Bergstein, Walter Hursch, Linda Keszenheimer and Greg Sullivan for their help. Many thanks to Cristina Isabel Videira Lopes. She has given us detailed feedback on the paper. This work is supported in part by National Science Foundation under grant numbers Grant CCR-9102578 and CDA-9015692, IBM Corporation, Mettler-Toledo AG and Citibank.

7 Appendix: NP-completeness
We discuss two NP-complete problems related to designing growth plans and evaluating propagation directives.

7.1 Partial class dictionary graph completion
Suppose we want to use a propagation directive expression d to de ne a growth phase. When a propagation directive expression d is applied to a class dictionary graph and the result is not a partial class dictionary graph, we want to nd a minimum number of vertices and edges which will be added to the semi-class dictionary graph so that we get a partial class dictionary graph. Unfortunately, there is no fast way of doing it, because it is an NP-equivalent problem GJ79].5 We rst reduce the above problem to computing a partial class dictionary graph with a minimum number of vertices. We show that computing a partial class dictionary graph with a minimum number of vertices is NP-equivalent. This means that the problem at hand is representative of the di culty of problems in the class NP (non-deterministic polynomial-time) which contains a huge class of practically interesting problems. A standard technique to prove NP-equivalence of a minimization problem is to introduce a decision version of the minimization problem and to prove the decision version NP-complete. The NP-equivalence follows from a binary search argument. We use the following decision version of the minimum partial class dictionary graph problem: INSTANCE: Given a class dictionary graph D, a vertex v 2 V , positive integer k. QUESTION: Are there k or fewer vertices of D which de ne a partial class dictionary graph of D anchored at v?
D

MINIMUM PARTIAL CLASS DICTIONARY GRAPH

Claim 1 MINIMUM PARTIAL CLASS DICTIONARY GRAPH is NP-complete.
Proof: The problem is clearly in NP. We show that a polynomial algorithm for MINIMUM PARTIAL CLASS DICTIONARY GRAPH implies a polynomial algorithm for MINIMUM COVER. MINIMUM COVER is wellknown to be NP-complete GJ79].
5 NP-equivalence is a generalization of NP-completeness. Basically, a problem is NP-equivalent, if the existence of a polynomial algorithm to solve it would imply that P=NP.

52

M A1 A2 A3

x1 1 0 1

x2 0 1 1

Figure 36: Minimum Cover Example INSTANCE: Collection C of subsets of a set S, positive integer k. QUESTION: Does C contain a cover for S of size k or less, that is, a subcollection of C which contains at most k sets whose union is S? To describe the reduction, we use the following example. MINIMUM COVER: k = 1. A1 contains x1 . A2 contains x2 . A3 contains x1 and x2. Entry M is 1 if and only if x is an element of A . See Fig. 36. The minimum solution is to choose A3 . We express now an instance of MINIMUM COVER directly as an instance of MINIMUM PARTIAL CLASS DICTIONARY GRAPH using the above example as a guide. This example shows the relationship between a cover and a partial class dictionary graph in general: A cover of size k translates into a partial class dictionary graph of size 1 + e + k (number of vertices), where e is the number of elements in S. The MINIMUM COVER instance given above translates into the class dictionary graph in Fig. 37a.
i;j j i

MINIMUM COVER

Cover
x1 x2 x1

Cover
x2

X1

X2

X1

X2

A1

A3 (a)

A2

A3 (b)

Figure 37: Minimal covering The minimum for the MINIMUM PARTIAL CLASS DICTIONARY GRAPH instance is achieved for k = 4 and is in Fig. 37b. The technique shown in this example can be applied to any instance of the MINIMUM COVER problem. 2 It is interesting to notice from our reduction that the MINIMUM PARTIAL CLASS DICTIONARY problem is NP-complete even for class dictionary graphs which do not use recursion. Repetition allows to express the Kleene operations. Those class dictionary graphs de ne regular languages. Although, in this case, recursion does not in uence the NP-completeness of the problem, it strongly in uences the size and running-time of the algorithms for solving the problem.

53

7.2 Evaluating constraints in propagation directives
Let's consider constraints in simple propagation directives, and let's look at an extreme case shown in Fig. 25. Although the class dictionary graph is very simple, it is an NP-complete problem to evaluate a path constraint in terms of e1 ; e2; :::; e . In this special case, the path satis ability problem is essentially the normal satis ability problem: Is there a satisfying assignment di erent from all \false" GJ79]? In practice, we currently use constraints in the forms of c1 and c1 and c2 , where c1 and c2 can be
n

through(e1 ) or ::: or through(e ) or ::: or through(e ) or bypassing(e1) and ::: and bypassing(e ) and ::: and bypassing(e ).
i i i i

For this special case, the path satis ability problem has an e cient solution.

References
AB92] Ber91] Ber93] BK76] BL91] BO92] Boo91] Bud91] Cas92] Cox86] CY90] DO91] DZ91] Mehmet Aksit and Lodewijk Bergmans. Obstacles in object-oriented software development. In
Object-Oriented Programming Systems, Languages and Applications Conference, in Special Issue of SIGPLAN Notices, pages 341{358, Vancouver, Canada, 1992. ACM Press. Paul Bergstein. Object-preserving class transformations. In Object-Oriented Programming Systems, Languages and Applications Conference, in Special Issue of SIGPLAN Notices, pages 299{

313, Phoenix, Arizona, 1991. ACM Press. SIGPLAN Notices, Vol. 26, 11 (November). Edward V. Berard. Essays on Object-Oriented Software Engineering. Prentice-Hall, 1993. A.W. Biermann and R. Krishnasawamy. Constructing programs from example computations. IEEE Transactions on Software Engineering, SE-2(3):141{153, Sept. 1976. Paul Bergstein and Karl Lieberherr. Incremental class dictionary learning and optimization. In European Conference on Object-Oriented Programming, pages 377{396, Geneva, Switzerland, 1991. Springer Verlag Lecture Notes 512. Don Batory and Sean O'Malley. The design and implementation of hierarchical software systems with reusable components. ACM Transactions on Software Engineering and Methodology, 1(4):355{398, October 1992. Grady Booch. Object-Oriented Design With Applications. Benjamin/Cummings Publishing Company, Inc., 1991. Timothy Budd. An Introduction to Object-Oriented Programming. Addison Wesley, 1991. Eduardo Casais. An incremental class reorganization approach. In European Conference on ObjectOriented Programming, pages 114{132, Utrecht, The Netherlands, 1992. Springer Verlag Lecture Notes 615. Brad J. Cox. Object-Oriented Programming, An evolutionary approach. Addison Wesley, 1986. Peter Coad and Edward Yourdon. Object-Oriented Analysis. Yourdon Press, 1990. second edition. Richard A. DeMillo and A. Je erson O utt. Constraint-based automatic test data generation. IEEE Transactions on Software Engineering, 17(9), September 1991. Christine Delcourt and Roberto Zicari. The design of an integrity consistency checker (ICC) for an object-oriented database system. In European Conference on Object-Oriented Programming, pages 377{396, Geneva, Switzerland, 1991. Springer Verlag. 54

Fre86] GJ79] Gra92] HHG90]

HO91] Hol92] HSX91] HU79] JCJO92] JF88] Joh88] KG87] LBSL91]

Peter Freeman. Tutorial: Software Reusability. IEEE Press, 1986. Michael R. Garey and David S. Johnson. Computers and Intractability. Freeman, 1979. Justin O. Graver. The evolution of an object-oriented compiler framework. Software{Practice and Experience, 22(7):519{535, July 1992. Richard Helm, Ian M. Holland, and Dipayan Gangopadhyay. Contracts: Specifying behavioral compositions in object-oriented systems. In Object-Oriented Programming Systems, Languages and Applications Conference, in Special Issue of SIGPLAN Notices, pages 169{180, Ottawa, 1990. ACM Press. Joint conference ECOOP/OOPSLA. William Harrison and Harold Ossher. Structure-bound messages: Separating navigation from processing. Submitted for publication, 1991. Ian M. Holland. Specifying reusable components using contracts. In European Conference on Object-Oriented Programming, pages 287{308, Utrecht, Netherlands, 1992. Springer Verlag Lecture Notes 615. Walter L. Hursch, Linda M. Seiter, and Cun Xiao. In any CASE: Demeter. The American Programmer, 4(10):46{56, October 1991. John E. Hopcroft and Je rey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. Ivar Jacobson, Magnus Christerson, Patrik Jonsson, and Gunnar Overgaard. Object-Oriented Software Engineering. Addison-Wesley, 1992. Ralph E. Johnson and Brian Foote. Designing reusable classes. Journal of Object-Oriented Programming, 1(2):22{35, June/July 1988. Steven C. Johnson. Yacc Meets C++. Computing Systems, The Journal of the USENIX Association, 1(2):159{168, Spring 1988. Gail E. Kaiser and David Garlan. MELDing Data Flow and Object-Oriented Programming. In
Object-Oriented Programming Systems, Languages and Applications Conference, in Special Issue of SIGPLAN Notices, volume 22, pages 254{267, Orlando, Florida, 1987. ACM SIGPLAN Notices.

Karl J. Lieberherr, Paul Bergstein, and Ignacio Silva-Lepe. From objects to classes: Algorithms for object-oriented design. Journal of Software Engineering, 6(4):205{228, July 1991. LH89a] Karl J. Lieberherr and Ian Holland. Assuring good style for object-oriented programs. IEEE Software, pages 38{48, September 1989. LH89b] Karl J. Lieberherr and Ian Holland. Tools for preventive software maintenance. In Conference on Software Maintenance, pages 2{13, Miami Beach, Florida, October 16-19, 1989. IEEE Press. LHSLX92] Karl J. Lieberherr, Walter Hursch, Ignacio Silva-Lepe, and Cun Xiao. Experience with a graphbased propagation pattern programmingtool. In International Workshop on CASE, pages 114{119, Montreal, Canada, 1992. IEEE Computer Society. Lie88] Karl J. Lieberherr. Object-oriented programming with class dictionaries. Journal on Lisp and Symbolic Computation, 1(2):185{212, 1988. Lie92] Karl J. Lieberherr. Component enhancement: An adaptive reusability mechanism for groups of collaborating classes. In J. van Leeuwen, editor, Information Processing '92, 12th World Computer Congress, pages 179{185, Madrid, Spain, 1992. Elsevier. 55

LW89] LX93] LXSL91] Mey88] MS89] Par79] PDN86] Rao91] Rum88] Sag91]

Karl Lieberherr and Carl Woolf. Grammar-based planning for object-oriented applications. Technical Report NU-CCS-89-11, Northeastern University, Feb. 1989. Karl J. Lieberherr and Cun Xiao. Formal Foundations for Object-Oriented Data Modeling. IEEE Transactions on Knowledge and Data Engineering, June 1993. Karl Lieberherr, Cun Xiao, and Ignacio Silva-Lepe. Propagation patterns: Graph-based speci cations of cooperative behavior. Technical Report NU-CCS-91-14, Northeastern University, September 1991. Bertrand Meyer. Object-Oriented Software Construction. Series in Computer Science. Prentice Hall International, 1988. Victor M. Markowitz and Arie Shoshani. Abbreviated query interpretation in entity-relationship oriented databases. Lawrence Berkeley Lab., Berkeley, CA, 1989. David L. Parnas. Designing software for ease of extension and contraction. IEEE Transactions on Software Engineering, SE-5(2):128{138, March 1979. Ruben Prieto-Diaz and James M. Neighbors. Module interconnection languages. Journal of Systems and Software, 6(4):307{334, November 1986. Ramana Rao. Implementation Re ection in Silica. In European Conference on Object-Oriented Programming. Springer Verlag, 1991. James Rumbaugh. Controlling propagation of operations using attributes on relations. In ObjectOriented Programming Systems, Languages and Applications Conference, in Special Issue of SIGPLAN Notices, pages 285{297, San Diego, 1988. ACM.

Walter Sagesser. Documentation for Adapted Demeter Tools/Turbo Pascal. AD-APPLI-SOFT: Steigstr. 14, CH-8610 Uster, Switzerland, Dec. 1991. San82] David Sandberg. LITHE: A language combining a exible syntax and classes. In ACM Symposium on Principles of Programming Languages, pages 142{145, Albuquerque, New Mexico, 1982. ACM. TL82] Dennis Tsichritzis and Frederick Lochovsky. Data Models. Software Series. Prentice-Hall, 1982. WBWW90] Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener. Designing Object-Oriented Software. Prentice Hall, 1990. WH91] Norman Wilde and Ross Huitt. Maintenance support for object-oriented programs. In Conference on Software Maintenance, pages 162{170, Sorrento, Italy, 1991. IEEE Press. Wir71] Niklaus Wirth. Program development by stepwise re nement. Communications of the ACM, 14(4), April 1971. Xia93] Cun Xiao. Foundations for adaptive software. Technical report, Northeastern University, 1993. Ph.D. thesis in preparation.

56

Contents
1 Introduction
1.1 1.2 1.3 1.4 2.1 2.2 2.3 2.4 2.5 Beyond object-oriented programming : Example of software evolution : : : : : Software testing : : : : : : : : : : : : : Overview : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

1
2 3 11 11

2 Data modeling for object-oriented design
Semi-class dictionary graphs and class dictionary graphs Object graphs : : : : : : : : : : : : : : : : : : : : : : : : Inductiveness of class dictionary graphs : : : : : : : : : Containment paths and object paths : : : : : : : : : : : Demeter data model summary and extension : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

13
14 18 22 23 26

3 A succinct representation of semi-class dictionary graphs
3.1 Simple propagation directives : : : 3.1.1 Path constraints : : : : : : 3.1.2 Directives : : : : : : : : : : 3.1.3 Simple semantic evaluator : 3.2 Propagation schema calculus : : : 3.3 Propagation directives : : : : : : : 3.4 Simplifying propagation directives 3.5 Extended propagation schemas : :

28
30 31 33 33 35 37 40 40

4 Propagation patterns and test plans

42

4.1 Propagation patterns : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42 4.2 Test plan design : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42

5 Related work 6 Conclusions 7 Appendix: NP-completeness

49 51 52

7.1 Partial class dictionary graph completion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52 7.2 Evaluating constraints in propagation directives : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 57

List of Figures
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Simplifying the cycle checking problem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Class dictionary graph tree : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : The C++ program description for DFT algorithm on trees : : : : : : : : : : : : : : : : : : The C++ program for DFT algorithm on trees : : : : : : : : : : : : : : : : : : : : : : : : : Class dictionary graph 1 graph dft for graphs with edges of one kind : : : : : : : : : : : : The traversal algorithm on graphs with edges of one kind : : : : : : : : : : : : : : : : : : : Class dictionary graph 1 graph cycle for cycle checking on graphs with edges of one kind : Cycle-checking on graphs with edges of one kind and graphs with edges of two kinds : : : : Class dictionary graph 2 graph for cycle checking on graphs with two kinds of edges : : : : Evolution history : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Problem solving : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : A semi-class dictionary graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Forbidden graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : The relations between concepts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : An object of class Input : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Illegal objects : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Illustration of partial class dictionary graphs : : : : : : : : : : : : : : : : : : : : : : : : : : Weaker path concept : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Path instantiations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Data model extension : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : A partial class dictionary graph used for testing program : : : : : : : : : : : : : : : : : : : A propagation directive : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : A propagation pattern : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : The translated C++ code and corresponding semi-class dictionary graph : : : : : : : : : : : Example for boolean formulas : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Propagation schema calculus : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Partial class dictionary graph derived from a propagation schema : : : : : : : : : : : : : : : An propagation pattern for the DFT algorithm : : : : : : : : : : : : : : : : : : : : : : : : : Propagation schema : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Growth phase one : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 4 5 6 7 8 9 9 10 11 12 14 16 18 20 21 22 24 25 27 29 30 30 30 33 36 41 42 43 44

31 32 33 34 35 36 37

Growth phases two : : : : : : : : : : : : : : : : : : : : Growth phase three : : : : : : : : : : : : : : : : : : : Checking the tree property : : : : : : : : : : : : : : : Class dictionary graph for computing the total salary : Adding salaries : : : : : : : : : : : : : : : : : : : : : : Minimum Cover Example : : : : : : : : : : : : : : : : Minimal covering : : : : : : : : : : : : : : : : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

45 45 46 48 48 53 53

List of Tables
1 The summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29

59

ÔÞÖúÉÌÁ´½Ó

¸ü¶àÏà¹ØÎÄÕÂ£º
Ïã¸ÛÀí¹¤´óÑ§-Èí¼þ½ø»¯ÓëÎ¬»¤1
Conservation of familiarity Unit 1 : SOFTWARE EVOLUTION 1.4 Approaches / Techniques 1.4.2 REBOOT REBOOT = Reuse Based on Object-Oriented Techniques The ...
51CTOÏÂÔØ-ºÃµÄÈí¼þÈËÔ±Ò»Éú±Ø¿´µÄÁùÊ®±¾Êé
µÚ 2 °æ) ¡±(Object-Oriented Software Construction, Second Edition ) 68 ¡¾...( The Design and Evolution of C++) 84 ¡¾45¡¿ ¡°C++ ±à³ÌË¼Ïë(2ND)¡±(...
Èí¼þ¹¤³Ìxc
software architecture Explain object-oriented development in brief Object-...40%are testing costs.For custom software,evolution costs ofen exceed development...
Software Engineering
Software Engineering A Practitioner¡¯s Approach (6th Edition) Object-Oriented ...Software Evolution The Law of Continuing Change (1974): E-type systems ...
software engineering
validation and evolution and represents them as separate process phases such ...4) Pipe filter architecture Chapter 7 1¡¢OOD: Object-oriented design 2¡¢...
JOLT»ñ½±Í¼Êé
Evolution of C++ Thinking in C++ About Face: The Essentials of User ...Software Engineering What Every Programmer Should Know About Object-Oriented ...