Structural equivalence and name equivalence

Question

I cannot understand exactly what name equivalence is. I am pretty sure that I have structural problems. For example, my professor gave the following:

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

a and b are both structural and equivalent names, while f and g are only structural equivalents. I do not understand why a and b will be equivalent to a name, but f and g are not.

Answer 1

Type equality

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

 x = y; 

here the value of the object y copied to the memory cells for the variable x .

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

Thus, the language translator must decide whether the two types are equal in some cases. Now we look at what it means to say that two types are "equal" (or equivalent).

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

Equivalence of names is the simplest: two types are equal if and only if they have the same name. Thus, for example, in 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 equivalence of names is used in the language, then x and y will be of the same type, and r and s will be of the same type, but the type of x or y will not be equivalent to the type of r or s . This means statements like

  x = y; r = s; 

will be valid but expressions like

  x = r; 

invalid (i.e. will not be accepted by the translator).

Using structural equivalence:, two types are equal if and only if they have the same “structure”, which can be interpreted differently. A rigorous interpretation will 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 types of the components must be the same and in the same order in the two types, but the names of the components may be different.

Having considered the above example again, using structural equivalence , the two types Stack and Set will be considered equivalent, which means that the translator accepts statements such as

 x = r; 

(Note that C does not support structural equivalence and will give an error for the above purpose.)

Answer 2

The concept of name equivalence makes the most sense if you are considering internal data structures that the compiler can use to represent types. Suppose types are represented as pointers to data structures. Also, suppose I implement type equivalence checking as a simple pointer comparison (e.g. name equivalence). Primitive types, such as integer and float , will be stored in some global environment, since there are only a finite number of them. In addition, if I compare integer with integer , they are guaranteed to be equivalent, because they point to the same structure due to this global environment.

However, since ref not a type constructor, not an atomic type, I can use it to create an infinite number of types (e.g. ref float , ref ref float , etc.). Therefore, we cannot store them in a global environment. One simple strategy that the compiler can take to control these types is to allocate a new structure whenever we encounter a type constructor, we allocate a new data structure for this type. Thus, a ref float instance will result in one new data structure, and another ref float instance will result in a completely new, different data structure. Pointers are not compared and therefore cannot be equivalent to names.

This is another piece of the puzzle that is the semantics of your assignment operator. This type alias is a simple copy of the pointer in the compiler, so if I write A=B , A always called the equivalent of B But to repeat, FA not the equivalent of the name of another instance of FA !

Answer 3

Consider the two definitions below.

 type student = record name, address : string age : integer type school = record name, address : string age : integer x : student; y : school; 

In the above example, the variables x and y will be considered different types with equivalent names: x uses the type declared in line 1; y uses the type declared in line 4. The equivalence of names is based on the assumption that if a programmer turns to writing two type definitions, then these definitions are probably intended to represent different types. (I'm not sure about the example you provided)

Link: Programming Languages ​​Pragmatics, M.L. Scott

Answer 4

a and b are alies, so they are equivalent to a name. f and g are wrong, they are not equivalent to a name.

Answer 5

In name type equivalence, two variables are of the same type if they are defined in the same declaration or in declarations that use the same type name. Therefore, the variables 'f' and 'g' in your example are equivalent. However, the variables 'a' and 'b' are not equivalent, as they have different type names. Moreover, if the type of structure is equivalent, two variables have the same type if they have the same structure. Thus, the variables 'a' and 'b' are equivalents, and the variables 'f' and 'g' are equivalents, because obviously the types with the same name have the same structure.

Link: Sebesta, Programming Language Concepts, 10th ed.