CHAPTER 4: Types

4.3 Type Equivalence

Alternative resolutions of this issue of type equivalence have been put forward in a paper by Welsh, Sneeringer, and Hoare [WSH 77]. These are classified into two families, called name equivalence and structural equivalence.

Name equivalence is used in Ada. It is based on the principle that each type declaration declares a distinct type: hence two type declarations always declare two distinct types, even if the included type definitions are textually identical. Consequently, for two objects to have the same type, their declarations must refer to the same type name (whether directly, or indirectly by a subtype, as we shall see later).

Consider for example the declarations:

type COLOR is (WHITE, RED, YELLOW, GREEN, BLUE, BROWN, BLACK); type COLOUR is (WHITE, RED, YELLOW, GREEN, BLUE, BROWN, BLACK); TINT : COLOR := BROWN; SHADE : COLOR := RED; HUE, SPOT : COLOUR := GREEN;

Then, according to the above stated principle, COLOR and COLOUR are two distinct types; TINT and SHADE are of the same type (COLOR); HUE and SPOT are of the same type (COLOUR). Thus the following assignments are legal:

TINT := SHADE; SPOT := HUE;

On the other hand, SPOT and TINT are of different types, so that the following assignment is not allowed:

    SPOT  :=  TINT;        -- Illegal!

Structural equivalence refers to formulations in which some form of equivalence rule is defined between types on the basis of their structural properties. For example, in the case of enumeration literals several degrees of structural equivalence would be conceivable: the same number of literals (unlikely); the same literals, although not necessarily in the same order; textually identical, including spaces and line breaks and so on. For example COLOR and COLOUR would be considered as structurally equivalent for all but the last of these formulations.

We have rejected structural equivalence in order to avoid pattern- matching problems for the compiler and for the human reader: in the case of enumeration types, this could involve comparisons of very long lists of identifiers.

We also believe that structural equivalence tends to defeat the purpose of typing. Thus, objects could be considered as being of the same type because their structures happen to be identical - by accident - or because they have become identical as a result of textual modifications performed during program maintenance: in the case of enumeration types, after deleting or inserting a literal. Such objects could then be mixed unintentionally, without causing compiler diagnostics, and the error would go undetected.

Name equivalence is therefore both simpler and safer. If we want several objects to have the same type, then we must declare the type, thereby giving it a name, and we must subsequently refer to this name in the declarations of these objects.

Further arguments supporting name equivalence are presented in the sections concerning arrays (see 4.5.3) and records (see 4.6.1).