Reusing Analogous Components.
AbstractUsing formal specifications to represent software components facilitates the determination of reusability because they more precisely characterize the functionality of the software, and the well-defined syntax makes processing amenable to automation. This paper presents an approach, based on formal methods, to the search, retrieval, and modification of reusable software components. From a two-tiered hierarchy of reusable software components, the existing components that are analogous to the query specification are retrieved from the hierarchy. The specification for an analogous retrieved component is compared to the query specification to determine what changes need to be applied to the corresponding program component in order to make it satisfy the query specification.
Introduction
The major objectives of a reuse system are to classify the reusable components, to retrieve
them from an existing library, and to modify the retrieved components to satisfy the query
specification [1, 2]. In previous investigations, the construction and retrieval processes have been
formally specified and implemented [3, 4, 5, 6]. From a set of reusable software components
formally specified, a two-tiered hierarchy of software components is constructed. The formal
specifications represent software that has been implemented and verified for correctness. The
lower-level hierarchy is created by a subsumption test algorithm that determines whether one
component is more general than another; this level facilitates the application of logical reasoning
techniques for a fine-grained, exact determination of reusable candidates. The higher-level hierarchy
provides a coarse-grained determination of reusable candidates and is constructed by applying a
hierarchical clustering algorithm to the most general components from the lower-level hierarchy.
The hierarchical structure provides a means for representing, storing, browsing, and retrieving
reusable components. Furthermore, the formal specifications provide a means for verifying that
a given software component correctly satisfies the current problem. Figure 1 shows the two-tiered
hierarchy of a set of container-based software components that are formally specified, where
rectangular nodes represent the specifications of individual components and oval nodes represent a
collection of specifications that have been clustered according to syntactic similarities.
Once the reusable components are retrieved, they typically cannot be used directly for the
implementation of the query specification.
Numerous software reuse projects have explored the use of analogy and other similarity-based
techniques to determine software reuse. Due to space constraints, the descriptions of the projects
are not given here, but may be found in [22]. This paper describes a new approach to retrieving
components based on analogies between existing and query specifications. This paper describes a
new approach to modifying retrieved components based on analogies between existing and query
specifications. Analogical relationships between the query specification and the specification of
the existing component can be used to guide the changes to the program code for the existing
specification. Analogical reasoning has long been recognized as an important tool to overcome the
search complexity of finding solutions to novel problems or inducing generalized knowledge from
experience [7]. Analogy presents a basic and challenging question: when are two specifications
(problem representations), for a given purpose, alike? [8].
The development of programs based on a series of transformations has been extensively
investigated [9, 10, 11, 12]. Program modification is different from traditional program
transformation because a program transformation is typically correctness preserving with respect to

Figure

1. The two-tiered hierarchy of ADT software components.
the original specification, but the program modification approach needs a program that satisfies its
original input-output specification along with the specification for a new program. Dershowitz [13]
developed an approach to program construction by modification based on the observation that
programmers only devote a limited amount of time and effort to newly develop code for a given
specification. Programmers often apply their knowledge about earlier programs to the development
of similar problems. Our work focuses on augmenting Dershowitz's methods in order to make it
amenable to automatic applications and facilitate software reuse.
The remainder of this paper is organized as follows. Section 2 presents the formal specification
notation used to describe a reusable software component. Section 3 presents the analogical matching
process, that is, how to find a set of analogical matches between an existing specification and the
query specification. Section 4 describes our program modification model based on analogy. Section 5
gives an example of modifying an analogous component based on the analogical matches between
the existing and query specifications. Section 6 describes related projects that have used analogy
or similarity-based techniques to determine software reuse. Section 7 gives concluding remarks and
briefly overviews future work.
Formal Specifications of Software Components
First-order predicate logic (FOPL) has been commonly used to specify programs [14, 15, 16, 17]. In
order to specify and reason about programs with data types other than arrays and simple variables,
sorts (types) are added to FOPL to obtain order-sorted predicate logic (OSPL). Moreover, order-sorted
specifications have been shown to be a useful tool for describing partially defined functions
and error handling in the specification of abstract data types [18, 19]. Order-sorted predicate logic
(OSPL) based on order-sorted specifications can be used to represent typed knowledge, where a
hierarchy gives the relationships among different types. A sort refers to the data types of a
given system. The sort hierarchy begins with primitive data types, such as int, float, and addr,
and is recursively built using structures, arrays, and sets. We use order-sorted predicate logic to
specify software components. The relationship between two components, that is, the reusability of
one component with respect to another, is based on the sort information and a logical subsumption
test applied to the specification body. For further details regarding the syntax and the semantics
of OSPL, the reader is referred to the Appendix.
In general, a software component can consist of requirements, design knowledge, code segments,
or test plans. A component can be used as the vehicle for encapsulation and data hiding, and it also
provides the basic unit of reusability. We define a component explicitly to be a user-defined type
whose behavior is described by a formal specification. The skeleton of a component specification is
shown as:
component component name identifier
f
inherit: component name identifier*
(method: method name identifier)*
The key word inherit indicates that the current component inherits the properties from the
components of previously defined components. The specifications in the method section define
the behavior of methods in this component. The format of a method specification is:
method method name((V ar : DomainSort)
requires pre-expression
modifies variables
ensures post-expression
The expressions used to specify a method of a given component, including pre-expression and
post-expression, are based on OSPL. For each method, the interface specifies both the domain sorts
and the range sort. The requires clause describes restrictions on the arguments, which defines how
the method may be invoked. Although equality is not defined in OSPL, the expressions containing
equality can always be transformed into pure OSPL expressions [20]. Variables that have a prime
latest value of a given variable. We interpret an omitted requires
clause as equivalent to "requires true." The ensures clause places constraints on the behavior of
the method. The requires and ensures clauses relate two states of the program: the state when
the method is called, which we call a precondition, and the state when it terminates, which we
call a postcondition. A requires clause only refers to the values in the precondition. An ensures
clause may refer to values in the pre- and the postconditions. A modifies clause describes which
variables can be changed. An omitted modifies clause is equivalent to the assertion modifies
nothing, meaning no objects are allowed to change in value during the execution of the method.
An example method specification for the component Stack is shown in Figure 2, which consists of
a function prototype followed by a body specified in terms of pre- and postconditions.
component Stack
f
method create:
modifies stack;
ensures
method destroy: (stack
modifies stack;
ensures trashed(stack);
method
requires :full(stack);
modifies stack;
ensures top(stack',newElement)
method
requires :empty(stack);
modifies stack;
ensures top(stack, topElement) "
method
requires :empty(stack);
ensures top(stack,topElement);

Figure

2. Component specification for Stack.

Figure

2 asserts that the method create is a constructor of this component, the method destroy
is a destructor of this component, the method push adds an element to a stack, the method detach
deletes an element from a stack, and the method topElement returns a top element belongs to some
stack. Moreover, the variables in the expressions without quantifiers are assumed to be universally
quantified.
3 Analogical Matching
An analogical match is defined to be a group of pairings between symbols in terms of candidate
and query specifications, where the pairings are based on some type of similarity. Consider
the following two expressions from the theory of abstract data types: f top(push(stack;
matching process may generate the following set of analogical
matches: ftop 7! head; push 7! enque; stack 7! queue; ff 7! fi; =7!=g: The above example exhibits
a bijective mapping between terms top(push(stack;
However, some features are needed in order to increase the flexibility of an analogical match.
For example,
ffl The variable, predicate, function, and constant symbols may be matched with different
variable, predicate, function, and constant symbols, respectively.
ffl The arguments for predicates and functions that are matched may be permuted by the
matching process. Since the argument order of functions and predicates is often arbitrary,
it is obviously unreasonable to insist that matches preserve argument order. Therefore, we
allow for permutations of arguments in order to increase the scope of applicability.
ffl Semantic information, such as the sort hierarchy and equivalence classes should be
incorporated into the analogical matching process.
ffl Techniques that seek syntactical similarities can be used to reduce the computational
complexity of the analogical matching process.
ffl Some symbols and terms may be left unmatched after the analogical matching process, i.e.,
loosening the restriction of bijective mapping.
In general, there is no universally accepted or recognized algorithm for determining software
reuse based on analogy. Furthermore, there is no formal theory or rule that rigorously describes
a process that will guarantee the generation of a useful analogical match [21]. Therefore, most
analogical matching algorithms use heuristics to direct searches for useful analogical matches. A
given heuristic captures system-defined criteria as to what constitutes a reasonable analogy.
3.1 Heuristics
Using the same example in the previous section:
A matching is an association between the two terms; i.e., a subset of the Cartesian product of
the sets of symbol occurrences in the terms. In this example, each term contains 6 symbols, so
the Cartesian product contains 6 \Theta 6 = 36 symbols, and hence has 2 36 subsets. Clearly, some
heuristics are needed to prune the search space.
When a heuristic is used in analogical reasoning systems, it must be determined as to what kind
of information the system should have to enhance the applicability of the heuristics, that is, what
contextual knowledge should be included in the heuristics. In order to develop a reuse system based
on analogy, it should support both the use of domain-specific knowledge and domain-independent
techniques in the search and the modification processes. It is assumed that the majority of the
domain-specific information is supplied interactively by the user, guided by a framework provided
by the domain-independent techniques.
associations are often believed to make good analogues, similarly, the matches
containing high proportions of identical associations make good analogies. Here, identical
associations refer to those that are purely based on syntactic information. We call this approach
the identity heuristic. However, most interesting analogies involve a significant proportion of non-identical
associations. The similarities are incorporated to determine which analogical match
is more promising. The similarity of a match can be defined by the distance between the
associated terms. (The definition of distance is defined in Section 3.2.) We call this heuristic the
similarity-based heuristic. This heuristic has already been incorporated into our system to classify
a set of software components and to retrieve a set of candidate components from a component
library [3, 4, 5, 6].
Another promising analogical approach is to consider matches that take into account the
structure of the terms. We call this approach a structure-based heuristic. Most analogical reasoning
systems use some form of structural mapping to find the analogies between two problems. One
approach is to make use of a sort hierarchy (i.e., primitive types as well as those types developed
constructively) or other type information to make a similarity judgement, thus earning the name
sort-based heuristic. We define two terms to be analogous if they have common ancestors in the sort
hierarchy. An analogical matching process should favor the association of two analogous terms.
There are some heuristic criteria that prefer matches between items of the same or similar types
according to an equivalence class partition of symbols (predicates, function symbols, or constants).
We call this approach the equivalence-based heuristic, which requires the system designers to define
the equivalence classes for the predicate and function symbols that specify the software components.
In our system [3, 4, 5, 6], the construction process assesses the equivalence class for each of the
predicates and functions and constructs a unified hierarchy of software components. For example,
both the function length(queue) that gives the length of a queue and the function size(stack)
that gives the size of a stack belong to the equivalence class cardinality(container) that gives
the cardinality of an entity container. In all the analogical matches considered in this reuse
framework, predicates are only mapped to predicates, operators are matched only to the operators
with the same number of arguments, and propositional connectives are mapped only to propositional
connectives.
Therefore, the analogical matching process begins by retrieving a set of components that have
some type of syntactic similarity as a means to filter the components considered for reuse. Based
on this set, analogies are sought between the query specification and the retrieved specifications.
The analogies found between specifications are then used to guide the changes to the corresponding
source code.
3.2 Computing Similarity
In this section, a simple evaluation method for computing similarity is given. A set of candidate
components that are similar to the query specification are retrieved from a software library based
on the degree of similarity between the existing specifications and the query specification. In this
paper, similarity is quantified by a nonnegative magnitude value called distance. Distances are
computed by several evaluation functions based on the knowledge available from a sort hierarchy
and the concept of an equivalence class. Conceptual distance between two terms is evaluated by
the distance of the shortest path between their corresponding sorts in the sort hierarchy, which
is used in turn to evaluate the similarity between the query specification and the specification of
existing components.
(Distance between two
Let the distance between two sorts s 1 and s 2 be denoted by D s
sorts. The distance from sort s 1 to sort s 2 is defined as the distance of the shortest path from s 1 to
s 2 in the sort hierarchy. If no such path exists, then the path value is set to +1. If s 1 and s 2 are
the same, then the distance is zero.

Figure

3 gives a simple sort hierarchy, in which Set is a subsort of Container, and
Partial-Order-Set is a subsort of Set and so on. The distance between the sort Stack and
the sort DoubleList is 3 according to Definition 1, i.e., D s (Stack;
Container
Stack Set List Queue
Partial-Order-Set Integer-Set DoubleList SingleList

Figure

3. A simple sort hierarchy.
(Distance between terms)
Let the distance between two terms t 1 and t 2 be denoted by D t refers
to terms. For some operator with at least one argument, let w 1 be the weight associated with the
operator and w 2 be the weight associated with its arguments. Assume 0  w i  1 for all i, and
1:0. The distance between two terms is defined as follows.
equivalence class) then % Terms in same equivalence class
considered similar
(3) if either t 1 or t 2 is a variable, then
\Theta w 2 .
Calculate recursively for functions
m\Thetan
\Theta w 2 .
where the weights w 1 and w 2 represent how the distances between the operators and their
corresponding arguments contribute to the distance between the terms t 1 and t 2 . These weights can
be provided either by the domain analysts or the component specifiers to reflect design decisions
or domain-specific information.
(Distance between expressions)
Let the distance between two expressions ff and fi be denoted by D e (ff; fi). The distance between
two expressions is defined as follows.
pred fi (same equivalence class) then D e (ff; fi) j 0.
pred fi then D e (ff; fi) j D t (ff; fi).
0:5.
where the binary operator op represents the predicate connectives: " (and),  (or), ) (implication),
and , (iff). Before computing the distance between two expressions, the input expressions should
be skolemized, hence, all variables are assumed to be universally quantified. Based on the distances
between terms and expressions, the distance between two methods can be defined as follows.
Definition 4 (Distance between two methods)
Let the distance between two methods m 1 and m 2 be denoted by Dm (m
is the precondition of m 1 (m 2 ), and post(m 1 is the postcondition of m 1 (m 2 ),
then the distance between two methods is as follows.
Finally, the distance between two components can be defined in terms of the distances of their
corresponding methods.
(Distance between two components)
Let the distance of two components C 1 and C 2 be denoted by D c (C 1 ; C 2 ). Provided that C 1 is a
candidate component, and C 2 is a query component (specification), then the distance between C 1
and C 2 is defined by:
min
3.3 Top-Down Matching Approach
The second step in the analogical matching process is to assess the analogical relationships
between the query specification and the specifications retrieved based on similarity. In the context
of recognizing reusable candidate specifications for solving query specifications, the analogical
matching process should have a flexible notion of an analogy-based match rather than imposing a
design bias towards any single heuristic. It should be easily tailorable to any particular domain-specific
strategies. The heuristics mentioned in Section 3.1 should be refined to be more specific.
That is, some numerical metric should be created to measure the usefulness of a given analogy.
Once a precise definition for the goodness of an analogy match is given, the analogy problem can
be regarded as an optimization problem. For an optimization problem, finding a global optimum
is not typically feasible, therefore we might want to generate a set of local optimal analogies. At
this point, the analogical matching process can be regarded as a recursive problem solving process.
The initial problem is to match the specifications of two terms. As the matching process continues,
new subproblems are produced and recursively solved. No new subproblems will be produced in
two cases:
(1) one of the subproblem's terms is a constant or variable;
(2) no new analogical match is applicable for this subproblem.
An analogical matching process generates a set of analogical matches between two input expressions.
Let a list of terms be of the form [t are terms. The empty list is denoted by
Similar to PROLOG's definition of lists, if list then head is the first element
of L and Tail is a list that is the same as L except that the first element head is deleted from the
list. We define the analogies of a pair of lists with the same length. The analogies of two lists with
different cardinality will be discussed later.
Definition 6 (The analogies between a pair of lists)
For two lists [a 1 ; a the following condition holds.
The above definition says that the result of applying an analogical matching to a pair of lists
is equal to the union of the results of matching the corresponding terms in the two input lists.
Since OSPL is used to express the behavior of software components, the object language of our
analogy system is based upon first-order logic with sort hierarchies. The sort- and equivalence-based
heuristics suggest the matches of two terms but the analogical matches are not limited to the terms
in the same equivalence class or the terms with the same sort. We explore how to incorporate
the properties of commutativity into the matching process, because it is unsatisfactory that the
analogical matches from a pair of terms be based on an arbitrary preservation of argument order.
The generation of subproblems from the matching process can be classified into two kinds of
branches: or-branch and and-branch. When we want to match terms containing a commutative
operator, the set of derived subproblems may suggest more than one way of solving the problem.
Therefore, the or-case applies, that is, the current problem should branch into a set of new
subproblems, each generating a new group of analogical matches. For example, consider the
following g. Since max and min are commutative operators,
the matching process produces a set of partial matches: fmax 7! ming.
Respectively, the matching process generates the following two or-branch subproblems:
h(y)]g.
Thus, the current state of matching between a pair of terms involves a set of partial matches and
two sets of or-branch subproblems. We only need to solve one of the or-branch subproblems in
order to proceed to the subsequent stages of the matching process. The or-branch subproblems are
generated by permuting the order of arguments to obtain new sets of argument mappings.
Let us consider another example: f f(i; are
not commutative operators, the matching process generates a set of partial matches: f7!?g;
and two and-branch subproblems are generated as follows: f [f(i; j)]; [h(i
)]g. such that the current problem is split into two new sets of subproblems,
with each represented as an and-branch together with a partial matching. The newly generated
matches from these two subproblems should not conflict with each other, that is, no inconsistent
analogical matches will be generated. We will define consistency shortly.
From the above examples, we may conclude that and-branch subproblems are generated
whenever the argument matching within an identical argument mapping is performed; or-branch
subproblems are generated whenever the matching process encounters commutative terms and
attempts to perform argument matching of permuted argument mappings of the terms. The terms
in the latter case include ordinary predicative connectives, for example, " and .
According to the previous discussion, we define the matchability of two expressions, i.e., as an
attempt to answer the question "when are two expressions matchable?" The following definition
checks the matchability of two expressions recursively, where the simplest notion of matchability
is that two terms have a common ancestor in the sort hierarchy or the two terms are in the same
equivalence class.
Two expressions t 1 and t 2 are matchable, denoted by matchable(t 1 ,t 2 ), iff one of the following
conditions holds.
are analogous, i.e., have a common ancestor in the sort hierarchy.
(2) either t1 ' term t 2 or t1 ' pred t 2 .
are in the same term or predicate equivalence class, respectively).
For an analogical matching process A and two inputs t 1 , t 2 , if t 1 is not matchable with t 2 then
returns an empty set. The definition of consistency for analogical matches is defined in
terms of conflicts, where a conflict occurs when a given term has more than one match in the set of
matches \Theta. Three separate cases are enumerated to indicate simple variables, functions, and lists
of expressions.
Definition 8 Conflict.
Let the match oe can both be simple identifiers,
functions, or lists of terms. oe 1 has a conflict with an existing set of matches \Theta, denoted by
one of the following conditions holds.
conflict(ff 7! gg; \Theta)
Therefore, a given match oe is consistent with a set of matches \Theta, when there are no conflicts
within \Theta.
Definition 9 Consistent.
Some match oe is consistent with an existing set of matches \Theta if oe has no conflicts with \Theta,
denoted by consistent(oe,\Theta). That is, consistent(oe; \Theta) j :conflict(oe; \Theta).
If the matching algorithm is restricted to the preservation of argument order, then the second
requirement of Definition 8 will never be applicable in the matching process.
Scoring function.
Let \Phi be a set of analogical matches of the form fx 1 7! y g. Then the score of \Phi is
computed by a scoring function
where distance function D is overloaded and applied to identifiers, functions, or lists of terms.
3.4 Matching Algorithm
An analogical matching process generates a set of analogical matches of two formally specified
input expressions. We define the application of an analogical matching process M to expressions
as follows. Given a matching subproblem that consists of a pair of specifications ff and fi as well
as an existing set of matches \Phi, the matching algorithm attempts to find a new set of consistent
matches and returns it to the user. We assume all variables of the pair of inputs have been either
skolemized or universally quantified. The algorithm, Match Expr, matches two expressions and is
given in Figure 4. The algorithm for matching two terms, Match Term, is given in Figure 5. The
algorithms are based on the analogical matching approach presented in Section 3.3.
Considering the algorithm for matching two expressions, if both inputs are terms then the
algorithm for matching two terms (Match Term) is invoked under the condition that these two
terms are matchable. Case 3 in Algorithm Match Expr gives an example of generating and-branch
subproblems, in which the consistency of the analogical matches between the corresponding items
in two input lists should hold. Cases 5, 6, and 7 in Algorithm Match Expr give the examples of
generating or-branch subproblems. The set of analogical matches with the smaller score is returned
to the calling function.
Let us consider the algorithm for matching two terms (Algorithm Match Term). Case 1 matches
two terms with either one of them being a variable, and the algorithm returns these two terms as
a new match if they are matchable. Similar to Case 3 in Algorithm 1, Case 3 in Algorithm
Match Expr matches two lists. Case 4 matches two operators and at least one of their arguments is
non-commutative. Case 5 matches two operators and both of the input operators have commutative
arguments. Case 6 matches two operators with different numbers of arguments.
Several heuristics are exploited in the matching algorithms. These two algorithms use a top-down
scheme to compare two input expressions or terms. The predicate connectives of two input
expressions or the functor symbols of two input terms should be matched before their arguments'
matchings are performed, hence a structure-based heuristic is applied. However, the commutativity
of the arguments is incorporated into the matching algorithms. If some term is a commutative
Algorithm 1 Match
Input: Two \Sigma-expressions
, and current partial matches \Phi.
4, be \Sigma-expressions; t, t 1
, and t 2
be \Sigma-terms.
Let\Omega and fi be the predicate connectives.
Output: A new set of partial matches.
Procedure:
begin
switch
case matching two terms
then return(Match
else return(\Phi);
case matching two empty lists
case 3 ([e 1
matching two lists of expressions
return(Match Expr (T ail
case matching two expressions
return(Match Expr
case 5 ((e
matching two expressions
Match
Match
case 6 ((e
matching an expression with a term
case 7 (t; (e
matching a term with an expression
end.

Figure

4. Matching two expressions.
Algorithm 2 Match
Input: Two terms and a set of partial matches \Phi.
Output: A new set of partial matches.
Procedure:
begin
case 1 either T 1 or T 2 is a variable:
g) else return(\Phi);
case
matching two empty lists
case 3 T matching two lists
return(Match
case
matching two operators either f or g is non-commutative
if consistent(ff 7! gg; \Phi)  (f ' term g)  (f ' pred g) then
return (Match
else return(;);
case
matching two commutative operators
if consistent(ff 7! gg; \Phi)  (f ' term g)  (f ' pred g) then
Match
Match
else return(;);
case 6 T
matching two operators with different numbers of arguments
return(Match
end.

Figure

5. Matching two terms.
operator, then several variations of the term with permuted arguments are created to generate the
or-branch subproblems, otherwise and-branch subproblems are generated for each pair of the input
arguments. The scoring function based on the distance notions is used to determine which
set of matches is returned, therefore, the similarity-based heuristic is incorporated into the matching
algorithms. The notion of equivalence class is used to determine if two functors can be matched, for
example Cases 4 and 5 in Algorithm Match Term, hence the equivalence-based heuristic is applied
in the algorithm for matching two terms.
The definition of predicate consistency is given in Definition 9. Therefore, implicitly, we
exclude the possibility of a mismatched analogical match that allows a mapping that is not one-
to-one, even though it may be a useful analogy in the real world. If mismatches are allowed
in the analogical matching algorithms, then a considerably large amount of domain knowledge
would need to be encoded in the system's knowledge base. Case 6 in Algorithm Match Term
deals with the condition when the arguments of two input terms have different sizes (m 6= n).
In this case, we need some transformation rules to "rephrase" the input terms to make their
arguments have the same cardinality. The transformation rules require domain knowledge. For
example, suppose we want to match
p a and c
d , since the functions square-root and division
have different numbers of arguments that need to be transformed. If the system has the rule
a
1 , then a match can be easily found: f= 7! =;
p a 7! c; 1 7! dg: If the system only
has the rule
a \Theta 1, then we have the following
Our algorithm provides a framework for a domain-independent matching process but the domain
knowledge is tailorable to more specific types of information. The complexity of this algorithm
increases when the matching process encounters a commutative operator. Let level(ff) denote the
"depth" of an operator ff. For example, the depth of a constant is 0, the depth of a
and level(op(arg )g. For each pair of commutative
operators ff and fi, the matching process generates two subproblems. Hence, this algorithm's upper
bound is minflevel(ff); level(fi)g \Theta 2 minflevel(ff);level(fi)g : For further details regarding the complexity
analysis of the algorithsm, please see [22]. In Algorithm Match Term, Case 5 always generates
two sets of analogical matches because, currently, the operators that are able to generate or-branch
subproblems are commutative and they consist of only two arguments. We assume that Case 6 of
Algorithm Match Term transforms the input terms to at most one pair of operators with the same
number of arguments.
Implementation
This section presents an implementation of the matching algorithm. A prototype system for
facilitating software reuse has been implemented in the Quintus ProWindows language, a dialect of
Prolog that supports the object-oriented organization of graphical elements. Our system provides
the functions of constructing the hierarchical library [3], retrieving the existing components that
have a logic-based generality relationship with the query component [5], and assisting users in the
modification of more general and analogous existing components to satisfy a query specification [6].
Let the existing specification Old Spec be the specification of the Stack class given in Figure 2.
A query specification Query Spec, the specification of DoubleList class, is given in Figure 6.
In addition to the constructor and destructor operations, this component defines four methods:
addAtHead, addAtTail, detachAtHead, and detachAtTail. For the purpose of conciseness, we
only consider the relationship between two methods Stack::push and DoubleList::addAtTail.
In order to find an analogous existing component based on the query specification for DoubleList,
we apply our matching algorithm to the methods of DoubleList. Figure 7 shows the results of the
application of the matching algorithm to the method DoubleList::addAtTail and the method
Stack::push.
The left part of Figure 7 displays the two-tiered hierarchy of a group of components described
by formal specifications. The Compute Analogies window displays the query and existing
components and methods, respectively. The Candidate Analogies window displays the matches
found by the Match Expr matching algorithm. The matches are helpful in terms of modifying the
existing components for reuse because the users may discover inherent similarities between two
components that have no logical relationships that can be found by automated reasoning. Given
these candidate matches, the user can reuse or redesign the query component. In this example, the
system, using Match Expr, suggests several matches that may be useful in the modification process.
For example, the result suggests that, in order to satisfy the query specification, the input object
should be changed from stack to dbllist and the new element should be added at the tail of
dbllist instead of the top of stack.
4 Program Modification Model
We regard the modification process as a problem solving process, where Figure 8 contains a
framework for modifying components based on analogies found between two formal specifications.
The "problems" in this process are defined by the specifications that represent reusable software
components and the "solutions" become the executable implementations of the corresponding
component DoubleList
f
method DoubleList
modifies dbllist: DoubleList;
ensures
method destroy: (dbllist
modifies dbllist;
ensures trashed(dbllist);
method DoubleList
modifies dbllist;
ensures head(dbllist',element)
method DoubleList
modifies dbllist;
ensures tail(dbllist',element)
method DoubleList
requires head(dbllist,element)
modifies dbllist;
ensures
method DoubleList
requires tail(dbllist,element)
modifies dbllist;
ensures

Figure

6. Component specification of DoubleList.

Figure

7. An implementation for matching process.
specifications. Because formal specifications are used as an indexing mechanism, more of the
traditional tasks such as classification, retrieval, search, and program modification are amenable to
automated reasoning techniques, which should greatly facilitate its scalability when compared to
keyword-based or manual approaches to software reuse.
The objective of software development in our context is to "solve" the problem defined by
specification Query Spec by finding an appropriate implementation. Old Spec is referred to as
a candidate specification whose implementation Old Program is known. An analogical matching
process is used to guide the modification process, to be performed by the software developer. A
set of analogical matches found between the two specifications is used as the basis for potential
changes to the existing specification and corresponding software component.
The satisfies relationship defines the relationship between the specification and implementation
modules. Given the specification of two methods, Old Spec and Query Spec, assume Old Spec is a
specification of the method of a given component in the library and Query Spec is the specification
Analogical matches
Query_Program
Old_Program
Query_Spec
Old_Spec
satisfies satisfies
Program
Analogical
Matching
Modification

Figure

8. Analogical Reuse Modification Process.
of a method of a query component. Let Old Program be an implementation that satisfies Old Spec.
Then the suggested steps of modifying an existing program Old Program to a new implementation
Query Program based on the analogical matches between Old Spec and Query Spec are as given
in

Figure

9.
For the method specification Old Spec in an existing component that is analogous to some
method specification Query Spec in a query component, a set of analogical matches \Theta can be
found by the analogical matching process, which is presented in Section 3. According to \Theta, the
existing implementation Old Program can be modified to be program Old Program'. In this step,
we can also rewrite any unexecutable statements in the modified program Old Program', e.g., type
incompatibility. Finally, Old Program' and Query Spec are supplied to a program synthesizer,
which can be either a semi-automated program synthesis system [12, 23] or a programmer using a
formal approach for program derivation [17, 24, 25, 26], in order to obtain a new implementation
Query Program that satisfies Query Spec.
Input: Old Spec, Query Spec, and Old Program.
Output: Query Program.
Procedure:
(1) Analogical Matching: find \Theta which is a set of analogical matches between
Old Spec and Query Spec.
(2) Program Replacement: refine Old Program to Old Program' according to \Theta.
(3) Program Adaption: synthesize new segments for Old Program' to obtain/derive
Query Program that satisfies Query Spec.

Figure

9. Modification process based on analogy.
If an analogical match between the candidate and query specifications can be found, then the
effort required to develop the appropriate implementation (Query Program) will be significantly
reduced since the needed changes at the specification level are clearly determined before any source
code is edited. We call this approach to the modification of an existing program based on an
analogical match between two specifications, the Analogical Reuse Modification Process (ARMP).
The problem of finding promising candidate specifications for some query specification from large
knowledge bases of known and implemented specifications is referred to as the base filtering
problem [27]. In our reuse system, a retrieval scheme based on the similarities among reusable
components finds a set of candidate specifications that are similar to the query specification. Our
retrieval process augments the ARMP model in the form of a pre-processing phase.
It is emphasized that because the reuse is fine-grained, that is, at the component level, a limited
amount of domain knowledge is needed in order to apply analogical reasoning. Furthermore in
comparison to current techniques for reuse, largely based on keyword searchers, specification-based
reuse can be at least as effective and, in addition, is more amenable to automated reasoning.
5 A Modification Example
Program modification is a combination of analogy, transformation, synthesis, and verification. In
this section, we give an example of program modification based on analogy. We show the matching
process plays an important role in the modification process. Consider the following specification of
a square root program:
are the pre- and postconditions of the square root program, respectively. We are
given two numbers a and e and the desired result is an approximation r, which is a real number, to
the square root of a with a tolerance value e. Assume we have an existing program that performs
real division as follows:
begin
while s ? e do
if d * (q+s)  c then q := q
od.
end.
Then we apply the matching process (Algorithm Match Expr) to the pair of postconditions of
these two programs (case 1), i.e., R 1 and R (j
g: If there is the
transformation rule:
a
1 , then a match can be found as follows (using Algorithm Match Term,
case
a 7! c; d 7!
The match is then applied to the real division program and it becomes
begin
while s ? e do
od.
end.
However, 1
a contains the expression
a which is the objective of the implemented
program so we need to rewrite the statement
a
by
which preserves the semantics but eliminates
p a from the program. (Squaring, addition, and
comparison are regarded as elementary operations.) We obtain the following program:
begin
while s ? e do
od.
end.
In this algorithm, the result r falls in the range [0,s), i.e., 0  r ! s. However, 0  r
1. Once a will never find the
desired answer. This problem can be solved by replacing the initialization command s := 1 by
s := a because the square root of a is bounded from above by a + 1. Consequently, the desired
program becomes
begin
while s ? e do
od.
end.
Despite the simplicity of this example, the potential benefits of program by modification is
apparent. In the example of this section, the programmer can save programming effort by reusing
the modified program instead of having to program everything from scratch. Once an analogical
match is found, the programmer has to develop only those parts of the program that cannot be
reused from the old one, which, hopefully, requires much less than that which is necessary to
generate the entire program.
The reuse framework has been applied to the development of graphical user interfaces
based on the specification of existing graphical components [6]. Formal specifications for Motif
widgets were constructed and applying the classification scheme were organized into a hierarchical
structure. Then the user query was structured in terms of high-level, implementation-independent
specifications. At the specification level, the user is not concerned with setting specific attribute
values for a given widget or how widgets can be combined to achieve a given behavior. Providing
a means for a user to classify, browse, and retrieve graphical components based on the behavior
or functionality enabled users to focus on the high level requirements of graphical interface. The
search mechanism determined whether a given component should be modified or combined with
other components to satisfy a query specification.
6 Related Work
This section contains descriptions of software reuse projects that use techniques similar to those
presented in the paper. Two major categories of reuse techniques are described. First, those
techniques that involve the use of analogy are discussed. Next, techniques that calculate similarity
between software components based on some representation of software are described.
6.1 Analogies between Specifications for Software Reuse
Dershowitz [28] suggested the formulation of a program by using analogies as a basic tool in program
abstraction. An analogy is first sought between the specifications of the given programs; this process
yields an abstract specification that may be instantiated to any of the given concrete specifications.
The analogy is then used as a basis for transforming the existing program into abstract schemas
helping to complete the analogy. A given concrete specification of a new problem may then be
compared with the abstract specification of the schema to suggest an instantiation of the schema
that yields a correct program.
The ROSE-2 project [29] is based on the knowledge-based refinement paradigm, which is a
software development process in which user-supplied requirements are used to select and customize
a high-level design. The paradigm is supported by a knowledge base of high-level design abstractions
called design schemas and refinement rules. The schemas and rules are used to customize the user's
designs to satisfy the user's requirements and design decisions.
Bhansali [30] describes the derivation of a concrete program from a semi-formal specification of a
problem. He used a transformational approach based on a set of transformational rules that produce
a top-down decomposition of a problem statement down to the level of target language primitives.
The top-down decomposition process combines ideas from research in planning to generate programs
efficiently. The reuse of domain specific knowledge is emphasized in this approach. APU is a system
that uses the proposed paradigm to synthesize UNIX programs (shell scripts) from semi-formal
specifications of programs.
Maiden and Sutcliffe [31] investigated the potential of specification reuse by analogy and its
possible benefits for requirements analysis. They have developed two real-world examples to
determine the potential for specification reuse by analogy. The first example illustrates an analogy
between an air-traffic controller (ATC) and a flexible manufacturing system (FMS). The second
example identifies analogies between the ATC and a classroom administration system (CAS), and
the FMS and the CAS. They propose a software engineering analogy model based upon three types
of knowledge: solution knowledge, domain knowledge, and goal knowledge.
Lung and Urban [32] have proposed an analogy model for software reuse. In addition to the
constraints proposed by Maiden and Sutcliffe, that added constraints to handle software analogy
analysis information due to the complexity of the software system. They have proposed an analogy-based
domain analysis method that can support a high level reuse across domains. The purpose is
to help users better understand a domain and support potential future reuse in a different domain.
CAReT is an analogy-based retrieval system applied to software design reuse, where design
cases (actual designs) and design schemas (templates) are available for reuse. The knowledge base
for CAReT consists of background knowledge and a design library. The background knowledge
contains a basic object lattice, a data type lattice, and isa-part-of hierarchies for composite types.
The design library consists of a set of domain dictionaries (one per design family) and bookkeeping
information that facilitate retrieval. A set of design schemas (templates) exists for an application
domain, where a domain-specific design schema corresponds to a design family and more specialized
schemas correspond to design sub-families. CAReT uses a two-phased approach to retrieval. First,
the description of the query design case is used to determine if it belongs in one of the design
families, where the dictionary entry for that design family provides the similar design cases or the
corresponding design schema. If that search fails, then analogy-based search is pursued. Object-type
and data-type lattices are used to establish relationships between the query design and designs
in the library. A similarity value is calculated between the new design case and those retrieved
from the design library.
A computational model of similarity has been developed to support the software reuse based on
analogy [33]. The Telos language [34] is used to describe similarity between different artifacts (code,
design or requirement specifications). The language is a structurally object oriented data model
with multiple and meta classification, multiple generalization and typed attribution. Abstractions
used by the model are classification, generalization/specialization, and attribution. There are four
basic categories of Telos objects used to calculate similarity (entity tokens, attribute tokens, entity
classes, and attribute classes). The model is based on similarity and distance functions. Distances
are calculated between objects (classes) with respect to identification, classification (hierarchies),
generalization, and attribution.
6.2 Similarity-Based Techniques for Software Reuse
A number of projects have used case-based reasoning (CBR)-like techniques to facilitate software
reuse. In general, CBR has five general characteristics [35]. First, CBR attempts to recall old
cases to help solve new problems. Next, understanding a new situation in terms of old cases, where
more old cases may be applicable as the problem becomes better understood. Third, CBR involves
adapting old cases to fit new needs. Fourth, during the processing of evaluating and adapting old
cases, there is potentially a process of "learning" to solve a given problem in a new or novel way,
information that can be used in the future. Finally, there is a need to be able to integrate the new
experience into memory properly. A hierarchy of cases is built in a bottom-up fashion from existing
cases in order to facilitate recall and retrieval [35]. Cases are clustered or generalized according to
a set of common features. Types of indices used for cases include goals, constraints, and feature
combinations that describe how a given problem can be solved.
The remainder of this section overviews several projects that use CBR-like techniques for
addressing the problem of software reuse. Based on the major characteristics of CBR systems,
the reuse framework shares similar objectives, but the means to achieving the goals differ. The
major difference is that the formal specifications of the software components are used as the
means for classification, retrieval, and adaptation of the software, where automated reasoning
applied to the logical and analogical relationships between the specifications is used to determine
the set of candidate components for reuse. Also, the relationships between the specifications is
used to determine the type of adaptation needed to modify an existing component to satisfy the
requirements of a new component.
The AI-Reuse System (AIRS) [37] supports the browsing of a software library for components
that meet a user-specified requirement. The representation scheme is similar to a frame-based
system, and the search mechanism is based on similarity computations, much like those used for
case-based reasoning systems [35]. A component is defined by a set of (feature,term) pairs. A
feature represents information with respect to a given classification scheme and is defined by a
set of related terms. Candidate reuse components are retrieved based on a degree of similarity
between target and source descriptions. Similarity is described in terms of a distance factor, which
is proportional to the amount of effort needed to compose or modify the existing components
to satisfy the target component. The effort calculation is based on information obtained from
experienced software developers and domain specialists.
Prieto-Diaz [38] developed a faceted classification scheme to support the storage and retrieval
of reusable software components, where facets refer to important keywords obtained from program
descriptions and documentation. This approach makes use of a faceted scheme, thesaurus, and a
conceptual distance graph. Each software component has an associated descriptor that consists of
ordered terms for each facet. The thesaurus is used to help refine the definition of the component
and provide context information. The conceptual distance graph provides a means to measure
the similarity between facet terms, which is used in turn to evaluate the similarity between
required software specifications and available components [37]. The faceted approach requires
domain analysis in constructing the conceptual graph. Conceptual distances are assigned based on
experience, intuition, and common sense.
LaSSIE (Large Software System Information Environment) [39] uses a semantic-net based
approach to provide a structured representation of knowledge that can be reasoned with respect to
its semantic information. A knowledge-base is used to store different types of information about
large, complex software systems, focusing on the programmer's view. A semantic-based search
algorithm using logical inferencing is used to retrieve information about large software components.
A frame-based language is used to represent classes of objects and their actions. Domain analysis
is used to extract descriptions about objects and actions based on information gained from reading
large volumes of architecture documents and comments in source code files. A frame definition
contains super-frames (more general classes) and then a set of restrictions on the parent frames
to create the more specialized object. Slots are used to contain constraints or restrictions on the
frames. Using this type of representation, a hierarchy of frames is created. Information in the
knowledge-base is application-specific in order to achieve invisibility across the different types of
software artifacts (source code, documentation, error reports, etc.)
Case Assisted Reuse of Object Library (CAROL) [40] supports the reuse of class descriptions in
Object-Oriented programming. CAROL computes the similarity between existing class descriptions
and a target class specification. The most similar descriptions are returned. A case consists of a set
of Prolog facts that describe the class in terms of its name, attributes, and relationships. Classes
are stored in case format in terms of class names, class type, instance variables and others. Class
methods are classified according to the type of processing performed on the variables in the method,
such as modifying an instance variable, checking an instance variable, or returning the variable.
An attribute oriented approach is used to search for reusable classes. Attributes include the class
name (taking into consideration synonyms), position in the class hierarchy, or attribute importance
based on user-defined weights. Users specify a target class with the assistance of templates.
ReqColl (Requirements Collector) [41] is a tool that facilitates the requirements capture and
analysis processes. Conceptual graphs (CG) [42] are used to capture domain information. A graph
matching algorithm is used to determine whether an existing CG matches the CG for a new problem
description. In ReqColl, the nodes are either concepts or relations from the problem description,
where relations define how concepts are related to one another. Concepts may either be objects or
actions from the problem domain. Both concepts and relations have associated types, and thus,
have respective type hierarchies defined by the isa relationship. Directed arcs are used to connect
concepts and relations. ReqColl stores patterns of CGs for specific application domains. After the
user describes the problem in terms of a CG, the ReqColl invokes a matching process that determines
whether the new CG matches a CG stored in the system. The graph matching algorithm uses a
recursive approach to calculate similarities between pairs of arcs and the subarcs of the respective
CGs. Heuristics are used as means to attempt to reduce the number of computations necessary to
find the best possible permutation of arc pairs. In the case that the two CGs do not have the same
number of arcs, the matching algorithm has a constant weight factor to account for all unmatched
arcs. Depending on the amount of similarity between the stored CG and newly user-created CG,
the user may wish to add information to the new CG to make it more closely fit the stored CG or
pursue the requirements analysis process without the use of an existing CG.
7 Conclusion
This paper described an approach for applying analogical reasoning to reusing software components
that are described by formal specifications. Our studies have demonstrated that analogical
matching of specifications can be an effective means of software reuse. Our investigations also
show that supporting the understanding of candidate analogies is an important factor of successful
specification-level reuse. The reuse framework has been applied to the development of graphical
user interfaces (GUIs) from existing graphical user interface components [6].
In general, an ARMP needs didactic support for comprehension of candidate specifications,
which requires an explanation facility to help the software developer understand the target domain
and the base specifications. Since an automated ARMP is unlikely to achieve a perfect match,
explanation from systems or domain experts will also be necessary for evaluating the appropriate
target specifications.
Currently, we are investigating software reuse and program adaptation when existing
specifications are more general or abstract than the query specification [43]. In future investigations,
more sophisticated knowledge will be incorporated into the evaluation function in order to increase
the number of analogy candidates retrieved for a query specification. We are also investigating
the specification of design-level descriptions of systems in order to perform a more coarse-grained
determination of reuse. At this level, it is envisioned that more domain-specific information will
be incorporated in determining reuse. In order to facilitate the construction of specifications of
reusable components, complementary investigations are being pursued in reverse engineering in
order to abstract formal specifications from existing software [44, 45, 46] and in the area of formal
construction of specifications from requirements models [47, 48].

Acknowledgements

The authors are very grateful for the detailed comments given by the anonymous reviewers, which
has helped to greatly improve the presentation of the paper. Also, the authors greatly appreciate
the assistance provided by David Leake, George Spanoudakis, and Igor Jurisica.



--R

"Identifying and Qualifying Reusable Software Components,"
"Reuse software: Issues and research directions,"
"Using Formal Methods to Construct a Software Component Library,"
"Formal methods applied to reuse,"
"Using Automated Reasoning to Determine Software Reuse,"
Applying Formal Methods to Software Reuse.
"A Paradigm for Reasoning by Analogy,"
"Computational Approaches to Analogical Reasoning: A Comparative Analysis,"
"Reusability through program transformations,"
"Automating the transformational development of software,"
"Reusing Software Developments,"
"KIDS: A semiautomatic program development system,"
The Evolution of Programs.
"An axiomatic basis for computer programming,"
A Discipline of Programming.

"Applying formal methods in automated software development,"
"Order-sorted algebra I: equational deduction for multiple inheritance, overloading, exceptions and partial operations,"
"Semantics of order-sorted specifications,"
"An order-sorted logic for knowledge representation systems,"
Automated Acquisition and Refinement of Reusable Software Design Components.
"Reusing analogous components,"
Synthesis of Procedural and Data Abstractions.
System Software Development Using VDM.
The Science of Programming.
"Fundamentals of deductive program synthesis,"
"Mechanisms of Analogical Reasoning,"
"Program Abstraction and Instantiation,"
"The ROSE-2 Strategies for Supporting High Level Software Design Reuse,"
"Domain-Based Program Synthesis Using Planning and Derivational Analogy,"
"Exploiting Reusable Specifications Through Analogy,"
"Analogical Approach for Software Reuse,"
"Similarity for analogical software reuse: A computational model,"
"Telos: Representing knowledge about information systems,"
Morgan Kaufman
"Representation and management issues for case-based reasoning systems,"
"Computing similarity in a reuse library system: An AI-based approach,"
"Implementing faceted classification for software reuse,"
"LaSSIE: a knowledge-based software information system,"
"Application of case-based reasoning (cbr) to software reuse,"
"Matching conceptual graphs as an aid to requirements re-use,"
information processing in mind and machine.
"A formal approach to reusing more general components,"
"Constructing formal specifications from program code,"
"A two-phase approach to reverse engineering using formal methods,"
"Strongest postcondition as the basis to reverse engineering,"
"A graphical environment for formally developing object-oriented software,"
"A formal semantics of object models,"
--TR

--CTR
Guifa Teng , Xiaodong Liu, Support software evolution with abstration rules and programming knowledge patterns, Focus on computational neurobiology, Nova Science Publishers, Inc., Commack, NY, 2004
program modification;analogical reasoning;software reuse;formal methods