Final Data Types and Their Specification

Abstract

A data type specification is a description of the properties of a data abstraction for the benefit of its users and implementers.The data abstraction has realizations, all of which behave in a certain way.It is those properties implied by this behavior which we consider essential; properties specific to some realization are extraneous.The specification problem is to present all of the essential properties and no extraneous ones.We propose a specification method based upon the notion of "final data type."A final data type is the smallest structure having a given behavior; every other structure having that behavior maps onto it homomorphically.This property makes the final data type specification a particularly good source of information about the abstraction it realizes, and eliminates "implementation bias" from the method.