Equivalence of expression in type checking

EQUIVALENCE OF EXPRESSIONS IN TYPE CHECKING

Type checker find whether two type expressions are equivalent or not. 
This type equivalence is of two categories:
  1. Structural equivalence 
  2. Name equivalence.
In type checking if two type expressions are equal then return a certain type else return type-error.

Structural equivalence:

Replace the named types by their definitions and recursively check the substituted trees. If type expressions are built from basic types and constructors then those expressions are called structurally equivalent.

Example:

S1

S2

Equivalence

Reason

Char

Char

S1 equivalent to S2

Similar basic types

Pointer (char)

Pointer (char)

S1 equivalent to S2

Similar constructor ptr to the char type

Name equivalence :

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.

Example:
typedef struct Node
{
int x;
} Node;
Node *first,*second;
Struct Node *last1,*last2;

The variables first and second are name equivalent similarly last1 and last2 are name equivalent.