Amy Moormann Zaremski

Signature and Specification Matching Degree Type: Ph.D. in Computer Science
Advisor(s): Jeannette Wing
Graduated: May 1996

Abstract:

Large libraries of software components hold great potential as a resource for software engineers, but to utilize them fully, we need to be able: (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:

• Foundational. Within a general, highly modular, and extensible framework, we define matching for two kinds of semantic information (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 modules.
• Applications. 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 each application.
• Engineering. We describe our implementations of function and module signature match, 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 component library.

Thesis Committee:
Jeannette M. Wing (Chair)
David Garlan
Peter Lee
Steven J. Garland (MIT)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Software reuse, software libraries, component retrieval, library indexing, subtyping, signature matching, specification matching