Understanding Structural Equivalence

Question

I have two types of structural equivalence ideas I am struggling to understand.

VAR_1 = int
VAR_2 = pointer to VAR_1

So here, I feel like they are structurally equivalent because the types would technically be both pointing to an integer type, correct?

but then if you had something like

VAR_3 = pointer to int

Does the pointer to an int versus an integer declaration make them inequivalent?

I am thinking that VAR_1 and VAR_2 are structually equivalent because they contain the same data in the correct order, but VAR_3 fails because it would need to not be a pointer?

Answer 1

Late to the party, but I just want to state that I disagree with the other answer.

While language implementation detail is important, ultimately structural equivalence is NOT just about the word length assigned to the type. If that was the case, you could even argue that float and int can be structurally equivalent in C since maybe some C compiler implements them using words with the same length.

If you are not still convinced, think about what happens when you increment a pointer-to-int versus an int.

int p=100;
int *q=100;
p++;    //p = 101
*q++;  // Pointer moves to the next int in memory adding int word length to the underlying stored value

I would in fact argue that a type system has much more to do with language semantics. Pointer-to-int semantics is different than int semantics in C. Therefore these two types are not structurally equivalent.

To answer your question, VAR_1 and VAR_2 are not structurally equivalent (one is int, the other is pointer to int). But VAR_2 and VAR_3 are structurally equivalent. Since they point to the same basic type in C.

Answer 2

This depends entirely on how the concepts of pointer and int are implemented, as well as what structural equivalence means in your particular scenario.

Structural typing is concerned with whether one thing has the same structure as another thing, which means the implementation of the individual structures matters a great deal.

Here is a quick pseudocode definition for both types.

int definition
    32 bit value

pointer definition
    32 bit value

Two different types, but they contain the exact same members, even though semantically they are treated differently (the pointer is assumed to hold a memory address). These are structurally equivalent.

Here's another implementation.

int definition
    32 bit value

pointer definition
    64 bit value

Those aren't structurally equivalent, even though they both have a member called 'value'. How about this?

int definition
    value
    other value

pointer definition
    other value
    value

These might not be considered the same because the members are in a different order, although they are named/typed the same.

My point is that this is entirely up to the implementors of whatever language or environment this is a part of and what things mean in that world.