abstract data type

views updated

abstract data type A data type that is defined solely in terms of the operations that apply to objects of the type without commitment as to how the value of such an object is to be represented (see data abstraction).

An abstract data type strictly is a triple (D,F,A) consisting of a set of domains D, a set of functions F each with range and domain in D, and a set of axioms A, which specify the properties of the functions in F. By distinguishing one of the domains d in D, a precise characterization is obtained of the data structure that the abstract data type imposes on d.

For example, the natural numbers comprise an abstract data type, where the domain d is {0,1,2,…} and there is an auxiliary domain {TRUE,FALSE} The functions or operations are ZERO, ISZERO, SUCC, and ADD and the axioms are: ISZERO(0) = TRUE ISZERO(SUCC(x)) = FALSE ADD(0,y) = y ADD(SUCC(x),y) = SUCC(ADD(x,y)) These axioms specify precisely the laws that must hold for any implementation of the natural numbers. (Note that a practical implementation could not fulfill the axioms because of word length and overflow.) Such precise characterization is invaluable both to the user and the implementer. Sometimes the concept of function is extended to procedures with multiple results.