__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.

- we can check that the integer values
- 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

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.

2004-12-02