6.4 Type Names, Declarations and Recursive Types

Many languages like C allow user defined named complex types. In C, this is specified via typedef statement. You must have seen and used several examples of this kind of named types.

How do we check equivalence if named types are used?

Two approaches are possible:

Named equivalence: Treat named types as simple types and just check that two program components have the same name.

Structural equivalence: Replace the named type by their definitions (which may be a definition tree) and recursively check those trees.

For example, let us define two user-defined data types:

typedef float * series;
typedef float * sequence;

These two data types series sequence are different for named equivalence viewpoint, but same from structural equivalence consideration. Which of these two types of equivalence should we use? The answer is related to another facility of type definitions in many languages, called Recursive types.

6.4.1 Recursive Types

Consider our definition of Node:

typedef struct node_struct{
  struct node_struct *link[2];
  util u,v,w,x,y,z;
} Node;

The definition contains a self-reference while defining the link[2] fields, as the link array is defined as array of pointers to this struct itself. Thus the definition of Node is called a Recursive type.

If we try to represent the definition of Node as a graph having back-edges from pointer to the struct, then the tree_comp() will go into an unending loop which checking such a structure. The other possibility is that the pointer type constructor just records the name of the type to which it is pointing, as shown in following figure.

This means that we use named equivalence. Many languages which allow such recursive type definitions, including C, settle for a compromise solution. They use structural equivalence in all the cases except while comparing pointers within struct. If we want to use structural equivalence in all the cases, including the pointers in struct, then we have to somehow detect the definition loop. How this is to be done is left as an exercise for the readers.