structural equivalence vs name equivalence

Question

I can't seem to grasp exactly what name equivalence is. I'm pretty sure I have structural down though. An example my professor gave was this:

 Type TI=integer
 Type TTI=TI

 a=integer
 b=TTI
 f= ref float
 g= ref float

a and b are both structural and name equivalent, while f and g are just structural equivalent.I don't understand why a and b would be name equivalent, but f and g aren't.

Answer 1

Type Equality

The meaning of basic operations such as assignment (denoted by = in C) is specified in a language definition. Thus, for example, the meaning of statements such as

x = y;

here the value of object y is copied into the memory locations for variable x.

However, before an operation such as an assignment can be accepted by the translator, usually the types of the two operands must be the same (or perhaps compatible in some other specified way).

Thus a language translator must decide whether two types are equal in some cases. We now consider what it means to say that two types are "equal" (or equivalent).

There are two standard ways to determine whether two types are considered the same: name equivalence and structural equivalence.

Name equivalence is the most straightforward: two types are equal if, and only if, they have the same name. Thus, for example, in the code (using C syntax)

   typedef struct {
           int data[100];
           int count;
           } Stack;

   typedef struct {
           int data[100];
           int count;
           } Set;

   Stack x, y;
   Set r, s;

if name equivalence is used in the language then x and y would be of the same type and r and s would be of the same type, but the type of x or y would not be equivalent to the type of r or s. This means that statements such as

   x = y;
   r = s;

would be valid, but statements such as

   x = r;

would not be valid (i.e., would not be accepted by a translator).

Using structural equivalence:, two types are equal if, and only if, they have the same "structure", which can be interpreted in different ways.
A strict interpretation would be that the names and types of each component of the two types must be the same and must be listed in the same order in the type definition.
A less stringent requirement would be that the component types must be the same and in the same order in the two types, but the names of the components could be different.

Again looking at the example above, using structural equivalence the two types Stack and Set would be considered equivalent, which means that a translator would accept statements such as

x = r;

(Note that C doesn't support structural equivalence and will give error for above assignment.)

Answer 2

Consider the two definitions bellow.

type student = record
    name, address : string
    age : integer

type school = record
    name, address : string
    age : integer

x : student;
y : school;

In the example above, variables x and y will be considered to have different types under name equivalence: x uses the type declared at line 1; y uses the type declared at line 4. Name equivalence is based on the assumption that if the programmer goes to the effort of writing two type definitions, then those definitions are probably meant to represent different types. (I'm not sure about the example you have given)

Reference: Programming Languages Pragmatics, by M.L. Scott

Answer 3

The notion of name equivalence makes the most sense if you consider the internal data structures a compiler might use to represent types. Suppose that types are represented as pointers to data structures. Furthermore, suppose that I implement type equivalence checking as a simple pointer comparison (e.g. name equivalence). Primitive types like integer and float would be stored in some global environment, since there are only a finite number of them. Furthermore, if I compare integer with integer, they’re guaranteed to be equivalent because they point to the same structure, by virtue of this global environment.

However, since ref is not a type constructor, not an atomic type, I can use it to create infinitely many types (e.g. ref float, ref ref float, etc). So we can’t store them all in a global environment. One easy strategy the compiler can adopt for managing these types is allocate a new structure whenever we encounter a type constructor, we allocate a new data structure for that type. So the instance of ref float would result in one new data structure, and the other instance of ref float would result in a completely new, different data structure. The pointer comparison fails, and so they fail to be name equivalent.

There’s one more piece to the puzzle, which is what the semantics of your assignment operator are. This type aliasing is a simple pointer copy in the compiler, so if I write A=B, A is always name equivalent to B. But, to reiterate, F A is not name equivalent to another instance of F A!