Type Equivalence

TYPE CHECKING RULES usually have the form

if two type expressions are equivalent

then return a given type

else return type_error

KEY IDEAS. The central issue is then that we have to define when two given type expressions are equivalent.

• The main difficulty arises from the fact that most modern languages allow the naming of user-defined types.
• For instance, in C and C++ this is achieved by the typedef statement.
• When checking equivalence of named types, we have two possibilities.

  Name equivalence.

  Treat named types as basic types. Therefore two type expressions are name equivalent if and only if they are identical, that is if they can be represented by the same syntax tree, with the same labels.

  Structural equivalence.

  Replace the named types by their definitions and recursively check the substituted trees.

STRUCTURAL EQUIVALENCE. If type expressions are built from basic types and constructors (without type names, that is in our example, when using products instead of records), structural equivalence of types can be decided easily.

• For instance, to check whether the constructed types array(n1,T1) and array(n2,T2) are equivalent
  • we can check that the integer values n1 and n2 are equal and recursively check that T1 and T2 are equivalent,
  • or we can be less restrictive and check only that T1 and T2 are equivalent.
• Compilers use representations for type expressions (trees or dags) that allow type equivalence to be tested quickly.

RECURSIVE TYPES. In PASCAL a linked list is usually defined as follows.

type link = ^ cell;
     cell = record
               info: type;
               next: link;
            end;

The corresponding type graph has a cycle. So to decide structural equivalence of two types represented by graphs PASCAL compilers put a mark on each visited node (in order not to visit a node twice). In C, a linked list is usually defined as follows.

struct cell {
    int info;
    struct cell *next;
};

To avoid cyclic graphs, C compilers

• require type names to be declared before they are used, except for pointers to records.
• use structural equivalence except for records for which they use name equivalence.