Modules via Concept Analysis.
AbstractWe describe a general technique for identifying modules in legacy code. The method is based on concept analysisa branch of lattice theory that can be used to identify similarities among a set of objects based on their attributes. We discuss how concept analysis can identify potential modules using both positive and negative information. We present an algorithmic framework to construct a lattice of concepts from a program, where each concept represents a potential module. We define the notion of a concept partition, present an algorithm for discovering all concept partitions of a given concept lattice, and prove the algorithm correct.
Introduction
Many existing software systems were developed using programming languages and paradigms that
do not incorporate object-oriented features and design principles. These systems often have a
monolithic style that makes maintenance and further enhancement an arduous task. The software
engineer's job would be less difficult if there were tools that could transform code that does not
make explicit use of modules into functionally equivalent object-oriented code that does make use
of modules (or classes). Given a tool to (partially) automate such a transformation, legacy systems
could be modernized, making them easier to maintain. The modularization of programs offers the
added benefit of increased opportunity for code reuse.
The major difficulty with software modularization is the accurate identification of potential
modules and classes. This paper describes how a technique known as concept analysis can help
automate modularization. The main contributions of this paper are:
ffl We show how to apply concept analysis to the modularization problem.
ffl Previous work on the modularization problem has made use only of "positive" information:
Modules are identified based on properties such as "function f uses variable x" or "f has
an argument of type t". It is sometimes the case that a module can be identified by what
values or types it does not depend upon - for example, "function f uses the fields of struct
queue, but not the fields of struct stack". Concept analysis allows both positive and
negative information to be incorporated into a modularization criterion. (See Section 3.2.)
ffl Unlike several previously proposed techniques, the concept-analysis approach offers the ability
to "stay within the system" (as opposed to applying ad hoc methods) when the first suggested
modularization is judged to be inadequate:
- If the proposed modularization is on too fine a scale, the user can "move up" the partition
lattice. (See Section 4.)
- If the proposed modularization is too coarse, the user can add additional attributes to
identify concepts. (See Section 3.)
ffl We have implemented a prototype tool that uses concept analysis to propose modularizations
of C programs. The implementation has been tested on several small and medium-sized
examples. The largest example consists of about 28,000 lines of source code. (See Section 5.)
As an example, consider the C implementation of stacks and queues shown in Figure 1. Queues
are represented by two stacks, one for the front and one for the back; information is shifted from the
front stack to the back stack when the back stack is empty. The queue functions only make use of
the stack fields indirectly - by calling the stack functions. Although the stack and queue functions
are written in an interleaved order, we would like to be able to tease the two components apart
and make them separate classes, one a client of the other, as in the C++ code given in Figure 2.
This paper discusses a technique by which modules (in this case C++ classes) can be identified in
code that does not delineate them explicitly. The resulting information can then be supplied to a
suitable transformation tool that maps C code to C++ code, as in the aforementioned example.
Although other modularization algorithms are able to identify the same decomposition [2, 14], they
are unable to handle a variant of this example in which stack and queue are more tightly intertwined
(see Section 3.2). In Section 3.2, we show that concept analysis is able to group the code from the
latter example into separate queue and stack modules.
Section 2 introduces contexts and concept analysis, and an algorithm for building concept
lattices from contexts. Section 3 discusses a process for identifying modules in C programs based
on concept analysis. Section 4 defines the notion of a concept partition and presents an algorithm
for finding the partitions of a concept lattice. Section 5 discusses the implementation and results.
Section 6 concerns related work.
define
struct stack f int* base; int* sp; int size;
struct queue f struct stack* front; struct stack* back;
struct stack* initStack(int sz)
f struct stack* (struct stack*)malloc(sizeof(struct stack));
return s; g
struct queue* initQ()
f struct queue* (struct queue*)malloc(sizeof(struct queue));
return q; g
int isEmptyStack(struct stack* s) f return (s-?sp == s-?base); g
int isEmptyQ(struct queue* q)
f return (isEmptyStack(q-?front) && isEmptyStack(q-?back)); g
void push(struct stack* s, int i)
no overflow check */
void enq(struct queue* q, int i) f push(q-?front, i); g
int pop(struct stack* s)
f if (isEmptyStack(s))
return -1;
return (*(s-?sp)); g
int deq(struct queue* q)
f if (isEmptyQ(q))
return -1;
if (isEmptyStack(q-?back))
push(q-?back, pop(q-?front));
return pop(q-?back); g

Figure

1: C code to implement a queue using two stacks.
define
class stack f
private:
int* base;
int
public:
stack(int new
int isEmpty() f return (sp == base); g
int pop() f
if (isEmpty())
return -1;
return (*sp);
void push(int i) f no overflow check
class queue f
private:
stack *front, *back;
public:
new stack(QUEUE SIZE); back = new stack(QUEUE SIZE); g
int isEmpty() f return (front-?isEmpty() && back-?isEmpty()); g
int deq() f
if (isEmpty())
return -1;
if (back-?isEmpty())
return back-?pop();
void enq(int i) f front-?push(i); g

Figure

2: Queue and stack classes in C++.
Concept analysis provides a way to identify sensible groupings of objects that have common attributes

To illustrate concept analysis, we consider the example of a crude classification of a group of
mammals: cats, chimpanzees, dogs, dolphins, humans, and whales. Suppose we consider five at-
tributes: four-legged, hair-covered, intelligent, marine, and thumbed. Table 1 shows which animals
are considered to have which attributes.
attributes
four-legged hair-covered intelligent marine thumbed
cats
chimpanzees
objects dogs
dolphins
humans
whales

Table

1: A crude characterization of mammals.
In order to understand the basics of concept analysis, a few definitions are required. We follow
the presentation in [11]. A context is a triple O and A are finite sets (the
objects and attributes, respectively), and R is a binary relation between O and A. In the mammal
example, the objects are the different kinds of mammals, the attributes are the characteristics
four-legged, hair-covered, etc. The binary relation R is given in Table 1. For example, the tuple
(whales, marine) is in R, but (cats, intelligent) is not.
A. The mappings
attributes of X) and -(Y (the common objects of Y ) form a Galois
connection. That is, the mappings satisfy:
and
(The mappings are antimonotone and extensive.) In the mammal example, oe(fcats;
fhair-coveredg and
A concept is a pair of sets - a set of objects (the extent) and a set of attributes (the intent)
That is, a concept is a maximal collection of objects
sharing common attributes. In the example, (fcats, dogsg, ffour-legged, hair-coveredg) is a concept,
whereas (fcats, chimpanzeesg, fhair-coveredg) is not a concept. A concept (X 0
) is a subconcept
of concept (X 1
(or, equivalently, Y 1
). For instance, (fdolphins, whalesg,
fintelligent, marineg) is a subconcept of (fchimpanzees, dolphins, humans, whalesg, fintelligentg).
The subconcept relation forms a complete partial order (the concept lattice) over the set of concepts.
The concept lattice for the mammal example is shown in Figure 3.
top (fcats; chimpanzees; dogs; dolphins; humans; whalesg; ;)
(fchimpanzees; dolphins; humans; whalesg; fintelligentg)
(fcats; chimpanzees; dogsg; fhair-coveredg)
(fchimpanzees; humansg; fintelligent; thumbedg)
(fdolphins, whalesg; fintelligent; marineg)
(fcats; dogsg; fhair-covered; four-leggedg)
bot (;; ffour-legged; hair-covered; intelligent; marine; thumbedg)

Figure

3: The concept lattice (and accompanying key) for the mammal example.
The fundamental theorem for concept lattices [12] relates subconcepts and superconcepts as
follows:
G
i2I
oe
i2I
i2I
The significance of the theorem is that the least common superconcept of a set of concepts can
be computed by intersecting their intents, and by taking the union of the extents and then finding
the common objects of the set of common attributes of that resulting union. An example of the
application of the fundamental theorem is as follows:
This computation corresponds to the fact that c 1 t c in the lattice shown in Figure 3.
There are several algorithms for computing a concept lattice from a given context [11]. We
describe a simple bottom-up algorithm here.
An important fact about concepts and contexts used in the algorithm is that, given a set of
objects X, the smallest concept with extent containing X is (-(oe(X)); oe(X)). Thus, the bottom
element of the concept lattice is (-(oe(;); oe(;)) - the concept consisting of all those objects that
have all the attributes (often the empty set, as in our example).
The initial step of the algorithm is to compute the bottom of the concept lattice. The next
step is to compute atomic concepts - smallest concepts with extent containing each of the objects
treated as a singleton set. The atomic concepts correspond to those nodes in the concept lattice
reachable from the bottom node in one step. Computation of some of the atomic concepts for the
mammal example is shown below:
The algorithm then closes the set of atomic concepts under join: Initially, a worklist is formed
containing all pairs of atomic concepts c) such that c 6- c 0 and c 0 6- c. While the worklist is not
empty, remove an element of the worklist (c 0
using the fundamental
theorem of concept analysis. If c 00 is a concept that is yet to be discovered then add all pairs of
concepts c) such that c 6- c 00 and c 00 6- c to the worklist. The process is repeated until the
worklist is empty.
The iterative step of the concept-building algorithm is illustrated below:
3 Using Concept Analysis to Identify Potential Modules
The main idea of this paper is to apply concept analysis to the problem of identifying potential
modules within monolithic code. An outline of the process is as follows:
1. Build a context, where objects are functions defined in the input program and attributes are
properties of those functions. The attributes could be any of several properties relating the
functions to data structures. Attributes are discussed in more detail below.
2. Construct the concept lattice from the context, as described in Section 2.
3. partitions - collections of concepts whose extents partition the set of ob-
jects. Each concept partition corresponds to a possible modularization of the input program.
Concept partitions are discussed in Section 4.
3.1 Applying concept analysis to the stack and queue example
Consider the stack and queue example from the introduction. In this section, we will demonstrate
how concept analysis can be used to identify the module partition indicated by the C++ code in

Figure

(page 4).
First, we define a context. Let the objects be ' 0
, and the attributes be ff 0
where the ' i
's and ff i
's correspond to functions and properties of functions as indicated by the
tables below:
return type is struct stack *
return type is struct initQ *
has argument of type struct stack *
has argument of type struct queue *
uses fields of struct stack
uses fields of struct queue
The context relation for the stack and queue example is then:
The next step is to build the concept lattice from the context, as described in Section 2. The
concept lattice for the stack and queue example, together with a key, identifying lattice-node labels
with corresponding concepts, is shown below:
bot (;; fff 0
g) empty concept
One of the advantages of using concept analysis is that multiple possibilities for modularization
are offered. In addition, the relationships among concepts in the concept lattice also offers insight
into the structure within proposed modules. For example, at the atomic level, initialization functions
(concepts c 0
and c 2
are distinct concepts from other functions (concepts c 1
and c 3
). The
former two concepts correspond to constructors and the latter two to member functions. Concept
corresponds to a stack module and c 5
corresponds to a queue module. The subconcept relationships
indicate that the stack concept consists of a constructor concept and a
member-function concept.
3.2 Adding complementary attributes to "untangle" code
The stack and queue example, as considered thus far, has not demonstrated the full power that
concept analysis brings to the modularization problem. It is relatively straightforward to separate
the code shown in Figure 1 into two modules, and techniques such as those described in [2, 14]
will also create the same grouping. In essence, the concept analysis described above emulates
these techniques. This shows that concept analysis encompasses previously defined methods for
modularization. We now show that concept analysis offers the possibility to go beyond previously
defined methods: It offers the ability to tease apart code that is, in some sense, more "tangled".
To illustrate what we mean by more tangled code, consider a slightly modified stack and queue
example. Suppose the functions isEmptyQ and enq have been written so that they modify the stack
fields directly (see Figure 4), rather than calling isEmptyStack and push. While this may be more
efficient, it makes the code more difficult to maintain - simple changes in the stack implementation
may require changes in the queue code. Furthermore, it complicates the process of identifying
separate modules. If we apply concept analysis using the same set of attributes as we did above,
attribute ff 4
("uses fields of struct stack") now applies to isEmptyQ and enq. Table 2 shows the
context relation for the tangled stack and queue code with the original sets of objects and attributes.
The resulting concept lattice is shown in Figure 5. Observe that concept c 5
can still be identified
with a queue module, but none of the concepts coincide with a stack module. In particular, even
though the extent of c 0
is finitStackg and the extent of c 2
is fisEmptyStack; push; popg, the concept
is not the stack concept: c 7
consists of initStack, isEmptyStack, isEmptyQ, push,
enq, and pop, which mixes the stack operations with some, but not all, of the queue operations.
int isEmptyQ(struct queue* q) f
return (q-?front-?sp == q-?front-?base && q-?back-?sp == q-?back-?base);
void enq(struct queue* q, int i) f

Figure

4: The queue and stack example revisited: "Tangled" C code.

Table

2: The context relation for the "tangled" stack and queue example.
top (f' 0
c 7
g) queue concept
c 6
bot (;; fff

Figure

5: The concept lattice (and corresponding key) for the "tangled" stack and queue example
using the attributes listed on page 8.
The problem is that the attributes listed on page 8 reflect only "positive" information. A
distinguishing characteristic of the stack operations is that they depend on the fields of struct
stack but not on the fields of struct queue. To "untangle" these components, we need to augment
the set of attributes with "negative" information - in this case the complement of "uses fields of
struct queue" (i.e., "does not use fields of struct queue"). The revised set of attributes and the
corresponding context relation are shown below:
return type is struct stack *
return type is struct initQ *
has argument of type struct stack *
ff 3 has argument of type struct queue *
uses fields of struct stack
uses fields of struct queue
ff 6 does not use fields of struct queue
ff 6
The resulting concept lattice (and corresponding key) is now:
top (f' 0
c 7
g) queue concept
stack concept
c 6
g) initStack
bot (;; fff 0
g) empty concept
This concept lattice contains all of the concepts in the concept lattice from Figure 5, as well as an
additional concept, c 4
, which corresponds to a stack module.
This modularization identifies isEmptyQ and enq as being part of a queue module that is
separate from a stack module, even though these two operations make direct use of stack fields.
This raises some issues for the subsequent C-to-C++ code-transformation phase. Although one
might be able to devise transformations to remove these dependences of queue operations on the
private members of the stack class (e.g., by introducing appropriate calls on member functions
of the stack class), a more straightforward C-to-C++ transformation would simply use the C++
friend mechanism, as shown in Figure 6.
3.3 Other choices for attributes
A concept is a maximal collection of objects having common properties. A cohesive module is a
collection of functions (perhaps along with a data structure) having common properties. Therefore,
when employing concept analysis to the modularization problem, it is reasonable to have objects
#define
class queue;
class stack f
friend class queue;
private:
int* base;
int
public:
stack(int new
int isEmpty() f return (sp == base); g
int pop() f
if (isEmpty())
return -1;
return (*sp);
void push(int i) f no overflow check
class queue f
private:
stack *front, *back;
public:
new stack(QUEUE SIZE); back = new stack(QUEUE SIZE); g
int
return (front-?sp == front-?base && back-?sp == back-?base);
void enq(int i) f
int deq() f
if (isEmpty())
return -1;
if (back-?isEmpty())
return back-?pop();

Figure

Queue and stack classes in C++ with friends.
correspond to functions. However, we have more flexibility when it comes to attributes. There are a
wide variety of attributes we might choose in an effort to identify concepts (modules) in a program.
Our examples have used attributes that reflect the way struct data types are used. But in some
instances, it may be useful to use attributes that capture other properties. Other possibilities for
attributes include the following:
ffl Variable-usage information: Related functions can sometimes be identified by their use of
common global variables. An attribute capturing this information might be of the form "uses
global variable x".
ffl Dataflow and slicing information can be useful in identifying modules. Attributes capturing
this information might be of the form "may use a value that flows from statement s" or "is
part of the slice with respect to statement s".
ffl Information obtained from type inferencing: Type inference can be used to uncover distinctions
between seemingly identical types [10, 9]. For example, if f is a function declared to
be of type int \Theta int ! bool, type inference might discover that f 's most general type is
of the form ff \Theta fi ! bool. This reveals that the type of f 's first argument is distinct from
the type of its second argument (even though they had the same declared type). Attributes
might then be of the form "has argument of type ff" rather than simply "has argument of
type int". This would prevent functions from being grouped together merely because of
superficial similarities in the declared types of their arguments.
ffl Disjunctions of attributes: The user may be aware of certain properties of the input program,
perhaps the similarity of two data structures. Disjunctive attributes allow the user to specify
properties of the form "- 1
or - 2
". For example, "uses fields of stack or uses fields of queue".
Any or all of these attributes could be used together in one context. This highlights one of the
advantages of the concept-analysis approach to modularization: It represents not just a single
algorithm for modularization; rather, it provides a framework for obtaining a collection of different
modularization algorithms.
4 Concept and Module Partitions
Thus far, we have discussed how a concept lattice can be built from a program in such a way that
concepts represent potential modules. However, because of overlaps between concepts, not every
group of concepts represents a potential modularization. Feasible modularizations are partitions:
collections of modules that are disjoint, but include all the functions in the input code. To limit
the number of choices that a software engineer would be presented with, it is helpful to identify
such partitions.
We now formalize the notion of a concept partition and present an algorithm to identify such
partitions from a concept lattice.
4.1 Concept partitions
Given a context (O; A;R), a concept partition is a set of concepts whose extents form a partition of
O. That is,
partition if and only if the extents of the
concepts cover the object set (i.e. S
O) and are pairwise disjoint (X
In terms of modularizing a program, a concept partition corresponds to a collection
of modules such that every function in the program is associated with exactly one module.
As a simple example, consider the concept lattice shown on page 11. The concept partitions
for that context are listed below:
ftopg
is the atomic partition. P 2
and P 3
are combinations of atomic concepts and larger concepts. P 4
consists of one stack module and one queue module. P 5
is the trivial partition: All functions are
placed in one module.
By looking at concept partitions, the software engineer can eliminate nonsensical possibilities.
In the preceding example, c 7
does not appear in any partition - if it did, then to what module
(i.e., nonoverlapping concept) would deq belong?
An atomic partition of a concept lattice is a concept partition consisting of exactly the atomic
concepts. (Recall that the atomic concepts are the concepts with smallest extent containing each
of the objects treated as a singleton set. For instance, see the atomic concepts in the mammal
example on page 7.) A concept lattice need not have an atomic partition. For example, the lattice
in

Figure

3 (page does not have an atomic partition: The atomic concepts are c 0
, and c 3
however, c 1
and c 3
overlap - the object "chimpanzees" is in the extent of both concepts.
The atomic partition of a concept lattice is often a good starting point for choosing a modularization
of a program. In order to develop tools to work with concept partitions, it is useful to be
able to guarantee the existence of atomic partitions. This can be achieved by augmenting a context
with negative information (similar to what we did in Section 3.2).
Given a context (O; A;R), a complement of an attribute a 2 A is an attribute a such that
Rg. That is, a is an attribute of exactly the objects that do not have
property a. For example, in the attribute table on page 11, ff 5
and ff 6
are complements.
Given a context the complemented extension of C is the the context C
Ag and R Rg. A complemented
extension of a context is the original context with the attribute set augmented by the addition of
a complement for every original attribute.
It is straightforward to see that every context has a complemented extension, and that the
concept lattice of a complemented extension has an atomic partition. Using this fact, we can now
present an algorithm to find the all the partitions of a concept lattice.
4.2 Finding partitions from a concept lattice
Given a concept lattice, we define the following relations on its elements: The set of immediate
suprema of concept x, denoted by sups(x), is the set of lattice elements y such that x - y and there
are no elements z for which x - z - y. The set of ancestors of x, denoted by ancs(x), is the set of
lattice elements y such that y - x and y 6= x.
[1] A / sups(?) // the atomic partition
[4] while W 6= ; do
remove some p from W
[6] for each c 2 p
for each c 0 2 sups(c)
are disjoint
[14] endif
[15] endif
[16] endfor
[17] endfor
[18] endwhile

Figure

7: An algorithm to find the partitions of a concept lattice.
The algorithm builds up a collection of all the partitions of a concept lattice. Let P be the
collection of partitions that we are forming. Let W be a worklist of partitions. We begin with
the atomic partition, which is the set of immediate suprema of the bottom element of the concept
lattice. P and W are both initialized to the singleton set containing the atomic partition.
The algorithm works by considering partitions from worklist W until W is empty. For each
partition removed from W , new partitions are formed (when possible) by selecting a concept of
the partition, choosing a supremum of that concept, adding it to the partition, and removing
overlapping concepts. The algorithm is given in Figure 7.
In the worst case, the number of partitions can be exponential in the number of concepts.
In such a case (or any case where the number of partitions is large), it is possible to adapt the
algorithm to work interactively. After each new partition is discovered, the algorithm would pause
for the user to consider that partition. If it is on too fine a scale, the user would allow the algorithm
to iterate further to find coarser-grained partitions.
5 Implementation and Results
We have implemented a prototype tool that employs concept analysis to propose modularizations
of C programs. It is written in Standard ML of New Jersey (version 109.24) and runs on a Sun
under Solaris 2.5.1.
The prototype takes a C program as input. The default object set is the set of all functions
defined in the input program. The default attribute set consists of one attribute of the form "uses
the fields of struct t" for each user-defined struct type (or equivalent typedef) in the input
program. The user has the option to include attributes of the form "has a parameter or return
type of type t." The context can be formed as is, or can be formed in fully complemented form,
where for each user-defined struct type, the attributes of the form"does not use fields of struct
t" (or "does not have a parameter or return type of type t") are included in the attribute set of
the context.
The context is then fed into a concept analyzer, which builds the concepts bottom up as described
in Section 2. The user can then view the concept lattice or feed the lattice into the parti-
tioner, which computes (depending on the user's choice) all possible partitions or one partition at
a time.
The examples in this paper were analyzed by the implementation. Preliminary results on
larger examples appear promising. In particular, we have used the prototype tool on the SPEC 95
benchmark go ("The Many Faces of Go"). The program consists of roughly 28,000 lines of C code,
372 functions, and 8 user-defined data types. The concept lattice for the fully complemented context
associated with these functions and data types consists of thirty-four concepts and was constructed
in seconds of user time (on a SPARCstation 10 with 64MB of RAM). The partitioner identified
possible partitions of the lattice in roughly the same amount of time.
5.1 Case study: chull.c
chull.c is a program taken from a computational-geometry library that computes the convex hull
of a set of vertices in the plane. The program consists of roughly one thousand lines of C code. It
has twenty-six functions and three user-defined struct data types: tVertex, tEdge, and tFace,
representing vertices, edges, and faces, respectively. The context fed into the concept analyzer
consisted of the twenty-six functions as the object set, six attributes ("uses fields of tVertex",
"does not use fields of tVertex", etc.), and the binary relation indicating whether or not function
f uses fields of one of the struct types. The concept analyzer built twenty-eight concepts and the
corresponding lattice in roughly one second of user time. The lattice appears in Figure 8. The
partitioner computed the 153 possible partitions of the concept lattice in roughly two seconds.

Figure

8: The concept lattice derived from chull.c.
The atomic partition groups the functions into the eight concepts listed in Table 3. This
partition indicates that the code does not cleanly break into three modules (e.g., one for each struct
type). However, assuming that the goal is to transform chull.c into an equivalent C++ program,
the eight concepts do suggest a possible modularization based on the three types: Concepts 2,
3, and 4 would correspond to three classes, for vertex, edge, and face, respectively; concept 1
would correspond to a "driver" module; and the functions in concepts 5 through 8 would form four
"friend" modules, where each of the functions would be declared to be a friend of the appropriate
classes.
concept number user-defined struct types functions
MakeVertex, ReadVertices, Collinear,
ConstructHull, PrintVertices
3 tEdge MakeEdge
4 tFace CleanFaces, MakeFace
5 tVertex, tEdge CleanVertices, PrintEdges
6 tVertex, tFace
Volume6, Volumed, Convexity,
PrintFaces
7 tEdge, tFace MakeCcw, CleanEdges, Consistency
8 tVertex, tEdge, tFace
Print, Tetrahedron, AddOne,
MakeStructs, Checks

Table

3: The atomic partition of the concept lattice derived for chull.c.
6 Related Work
Although there is a growing body of literature concerning module and abstract-data-type recovery
from non-modular code (e.g., [13, 6]), we are unaware of previous work on the problem involving
the use of concept analysis. Because modularization reflects a design decision that is inherently
subjective, it is unlikely that the modularization process can ever be fully automated. Given that
some user interaction will be required, the concept-analysis approach offers certain advantages over
other previously proposed techniques, namely, the ability to "stay within the system" (as opposed
to applying ad hoc methods) when the user judges that the modularization that the system suggests
is unsatisfactory. If the proposed modularization is on too fine a scale, the user can "move up" the
partition lattice. (See Section 4.) If the proposed modularization is too coarse, the user can add
additional attributes to generate more concepts. (See Section 3.) Furthermore, concept analysis
really provides a family of modularization algorithms: Rather than offering one fixed technique,
different attributes can be chosen for different conditions.
The work most closely related to ours is that of Liu and Wilde [8], which makes use of a table
that is very much like the object-attribute relation of a context. However, whereas our work uses
concept analysis to analyze such tables, Liu and Wilde propose a less powerful analysis. They
also propose that the user intervene with ad hoc adjustments if the results of modularization are
unsatisfactory. As explained above, the concept-analysis approach can naturally generate a variety
of possible decompositions (i.e., different collections of concepts that partition the set of objects).
The concept-analysis approach is more general than that of Canfora et al. [2], which identifies
abstract data types by analyzing a graph that links functions to their argument types and return
types. The same information can be captured using a context, where the objects are the functions,
and the attributes are the possible argument and return types (for example, attributes
in the attribute table on page 8). By adding attributes that indicate whether fields of compound
data types are used in a function, as is done in the example used in this paper, concept-analysis
becomes a more powerful tool for identifying potential modules than the technique described in [2].
The work described in [3] and [4] expands on the abstract-data-type identification technique described
in [2]: Call and dominance information is used to introduce a hierarchical nesting structure
to modules. It may be possible to combine the techniques from [3] and [4] with the concept-analysis
approach of the present paper.
The concept-analysis approach is also more general than technique used in the OBAD tool [14],
which is designed to identify abstract data types in C programs. OBAD analyzes a graph that
consists of nodes representing functions and struct types, and edges representing the use of internal
fields of a struct type by a function. This recovers similar information to a concept analysis in
which the attributes are exactly those indicating the use of fields of struct types (for example,
and ff 5
in

Table

3.1 on page 8). However, OBAD will stumble on tangled code like that in
the example discussed in Section 3.2. The additional discriminatory power of the concept-analysis
approach is due to the fact that it is able to exploit both positive and negative information.
In contrast with the approach to identifying objects described in [1], our technique is aimed at
analyzing relationships among functions and types to identify classes. In [1], the aim is to identify
objects that link functions to specific variables. A similar effect can be achieved via concept analysis
by introducing one attribute for each actual parameter.
There has been a certain amount of work involving the use of cluster analysis to identify potential
modules (e.g., [5, 1, 7]). This work (implicitly or explicitly) involves the identification of
potential modules by determining a similarity measure among pairs of functions. We are currently
investigating the link between concept analysis and cluster analysis.
Concept analysis has previously been applied in a software-engineering tool, albeit for a problem
much different from modularization: the NORA/RECS tool uses concept analysis to identify
conflicts in software-configuration information [11].

Acknowledgements

This work was supported in part by the National Science Foundation under grant CCR-9625667
and by the Defense Advanced Research Projects Agency under ARPA Order No. 8856 (monitored
by the Office of Naval Research under contract N00014-92-J-1937).
The comments of Manuvir Das on the work reported in the paper are greatly appreciated.



--R

A greedy approach to object identification in imperative code.
Experiments in identifying reusable abstract data types in program code.

Program comprehension through the identification of abstract data types.
System structure analysis: Clustering with data bindings.

Evaluating process clusters to support automatic program understanding.
objects in a conventional procedural language: An example of data design recovery.
Practical program understanding with type inference.
Program generalization for software reuse: From C to C
Reengineering of configurations based on mathematical concept analysis.
Restructuring lattice theory: An approach based on hierarchies of concepts.
Second Working Conference on Reverse Engineering.
Recovering abstract data types and object instances from a conventional procedural language.
--TR

--CTR
Peter Wendorff, A formal approach to the assessment and improvement of terminological models used in information systems engineering, ACM SIGSOFT Software Engineering Notes, v.26 n.5, Sept. 2001
Fuh-Gwo Chen , Ting-Wei Hou, Instruction-coated translation: an approach to restructure directly threaded interpreters with low cohesion, ACM SIGPLAN Notices, v.41 n.8, August 2006
Kamran Sartipi , Kostas Kontogiannis, A user-assisted approach to component clustering, Journal of Software Maintenance: Research and Practice, v.15 n.4, p.265-295, July
Andrew Sutton , Jonathan I. Maletic, Recovering UML class models from C++: A detailed explanation, Information and Software Technology, v.49 n.3, p.212-229, March, 2007
M. Di Penta , M. Neteler , G. Antoniol , E. Merlo, A language-independent software renovation framework, Journal of Systems and Software, v.77 n.3, p.225-240, September 2005
Andreas Christl , Rainer Koschke , Margaret-Anne Storey, Automated clustering to support the reflexion method, Information and Software Technology, v.49 n.3, p.255-274, March, 2007
Rainer Koschke , Gerardo Canfora , Jrg Czeranski, Revisiting the IC approach to component recovery, Science of Computer Programming, v.60 n.2, p.171-188, April 2006
Gerardo CanforaHarman , Massimiliano Di Penta, New Frontiers of Reverse Engineering, 2007 Future of Software Engineering, p.326-341, May 23-25, 2007
concept analysis;software restructuring;design recovery;reverse engineering;software migration;modularization