So far we have been computing only with integer, boolean and real data types. These basic data-types, along with the character data type, are supported by most programming languages. However, for more complex computations we need to deal with more structured forms of data. Examples of such structured data-types are rational and complex numbers, lists and sequences, polynomials, vectors and matrices, trees, stacks, queues, files etc. In this chapter we will see how structured data-types like rational and complex numbers, lists and sequences can be constructed out of the basic data-types. Our ultimate objective is to create a hierarchy of data-types, as shown in Figure 6.1, with more complex ones defined on top of simpler ones, so that the programs which use a particular data-type become independent of how the data-type is implemented. Complex computations which need to manipulate objects of these types can then be designed at a higher conceptual level in terms of these data types.
Any data-type which is not supported natively by a programming language is called an abstract data type. It includes a representation for items of the data type and associated operations on the items. An implementation of an abstract data type is called a data structure. In what follows we will illustrate the design of some abstract data types in both ML and Java .
