Signature and Specification Matching
Amy Moormann Zaremski
Large libraries of software components hold great
potential as a resource for software
engineers, but to utilize them fully, we need to be
(1) to locate components in the library;
(2) to organize the library in a way that facilitates
browsing and improves efficiency of retrieval; and
(3) to compare the description of a library
component to the description of what we want.
A key requirement in all of these problems is to be able to compare two
software components to see whether they match.
In this dissertation, we consider two different kinds of
semantic descriptions of components to determine
whether components match: signatures (type information) and
specifications (behavioral information). Semantic descriptions offer
advantages over either textual descriptions, such as
variable names, or structural descriptions, such as control flow graphs.
Using semantic information focuses on what the components do
rather than how they do it.
Signatures and specifications are natural ways
of describing software components and have
well-understood properties, such as type equivalence and logical relations
between formal specifications, that enable us both to define matches
precisely and to automate the match.
This dissertation makes the following contributions:
Within a general, highly modular, and extensible
framework, we define matching for two kinds of
(signatures and specifications) and two granularities of
components (functions and modules).
Each kind of matching has a generic form, within which all of the
matches are related and may, in some cases, be composed.
The orthogonality of the matches allows us to define match on
modules independently of the particular match used on functions in the
We show how the definitions of matching can be applied to
the problems of retrieval from libraries, indexing libraries, and
reuse of components.
We demonstrate the various signature and
specification matches with examples of typical uses in
We describe our implementations of function and module
function specification match, function signature-based
indexing, and function signature-based retrieval.
These implementations demonstrate the feasibility of our
approach and allow us to illustrate
the applications with results from a moderately-sized
Amy Moormann Zaremski,
Signature and Specification Matching,
Technical Report CMU-CS-96-103,
Carnegie Mellon Computer Science Department,
The full text of this paper is
to return to my home page. (Last modified 6/30/97)