The Structure of Specifications and Implementations of Data Abstractions.
Abstract
A data abstraction is a collection of sets together with a collection of functions. An intuitive abstraction is unconnected with formalism: the sets and functions are supposed to be known ab initio. Formal ideas enter when the abstraction is (i) implemented, a conventional program written to carry out the operations on actual data; and (ii) specified, a mathematical characterization given to precisely describe its sets and functions. The intuitive abstraction, an implementation, and a specification share a syntax that names the sets and functions, and gives the function domains and ranges (as set names). The central question for any particular example of syntax is whether the semantics of the three ideas correspond: does the collection of objects and operations a human being was thinking of behave in the way the implementation's data and procedures behave? Do the mathematical entities behave as imagined? The questions can never be answered precisely, because the intuitive abstraction is imprecise. On the other hand precise comparison of specification and implementation is possible. This paper presents an algebraic comparison of specifications with implementations. It is shown that these abstractions always overlap, and have a common (lattice) structure that is valuable in understanding the modification of code or specification.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1979
- Accession Number
- ADA077427
Entities
People
- Mark A. Ardis
- Richard G. Hamlet
Organizations
- University of Maryland