Partial Implementations of Abstract Data Types: Theory and Practice
Archer, Myla Marguerite
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69599
Description
Title
Partial Implementations of Abstract Data Types: Theory and Practice
Author(s)
Archer, Myla Marguerite
Issue Date
1988
Doctoral Committee Chair(s)
Kamin, Samuel
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
We propose the use of partial implementations of abstract data types as a solution to the partiality problem which arises in the top-down development of programs. In the main, this problem consists in the inability to implement all of an ideal abstract type by a program, though it has other aspects. We explain why we believe the partial implementation approach to be superior to other solutions to the partiality problem, and show how it can be used in a sound manner in the development process.
To study the practicality of the approach, we begin by considering what is required of a partial implementation, and develop two criteria which guarantee partial implementation: the H-criterion (for homomorphism), which comes closest to the usual criterion for total implementation, and the GH-criterion (for generalized homomorphism). We then investigate whether the methods for proving total implementation associated with several known specification methods can be adapted to methods for proving partial implementation by our criteria. We show that while those for equational specifications are not particularly suited to this purpose, those for other types of specifications, in particular, final algebra and pre-post specifications, are adaptable. We find the GH-criterion--which involves existence of a relation rather than a map with certain properties, and is nearly the most general possible criterion for partial implementation--to be more useful in many circumstances.
We then consider the problems that the partial implementation approach entails for parameterized types. In incremental program development, it is possible for the parameter to a parameterized type to be implemented before the parameterized type itself. The use of partial implementations thus implies the need to extend the usual semantics of specifications of parameterized types to allow for parameter algebras of arbitrary partiality. We attempt to de this for final algebra specifications and equational specifications. Our results show final algebra specifications to be more desireable for our purposes, since the natural extension to their semantics preserves implementations by the GH-criterion. For initial algebra specifications, the extension we obtain preserves implementations by the H-criterion, but not the GH-criterion, except for total algebra parameters.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
