CSC302 2006S, Class 27: Types (3): Type Equivalence

Admin:
* Monday will be return homework and distribute exam day.
* There is therefore no reading for Monday.
* We may, nonetheless, begin our coverage of declarative languages on Monday.
* EC for attending some aspect of the African conference (e.g., the dance recital tonight)

Overview:
* Type Equivalence.
* Structural Equivalence, Revisited.
* Assignment Compatibility.
* Type Coercion.
* Design Issues.

Question: When is type A equivalent to type B?
* Can I assign a variable of type A to a variable of type B?
* Can I assign a call a function that expects type  A on a parameter of type B?
* When can I use the representation of type A in place of the representation of type B?
* In set theory, the answer is often easy: A and B are the same if they contain the same element.
  * Proving this equivalence is harder.
* In real languages, the answer is also often harder
type T1 = record x: int, y: int; end;
type T2 = record x: int, y: int; end;
type T3 = T1; // Alias
type T4 = T1; // Alias
type T5 = T3; // Alias
type T6 = record r: int, i: int; end;
type T7 = record y: int, x: int; end;
type T8 = record x: int, y: int; z: int; end;

For each Ti,Tj 
* can we assign a value of type Ti to a variable of type Tj?

* can we assign a value of type Tj to a variable of type Ti?

Why declare type aliases?
* Increases readability: instead of "int x", write "temperature x" or "cents x" or ...
* In C, use int32, int64, etc., instead of short, int, long
  * Aliasing different on different machines.

Most restrictive assignment scheme:
* Assignment only possible when i = j
* Programmers declaring different types are intending them to serve different purposes, so don't allow assignment

Most general assignment scheme
* Do we allow a value of type T8 to a variable of type Ti?
  * Seems that we may be losing a field
  * Note: 
  public class Point2D {
    int x;
    int y;
  }
  public class Point3D extends Point2D {
    int z;
  }
  Point2D planar;
  Point3D spatial;
  ...
  planar = spatial;
  * Java permits this (yay polymorphism)
  * We don't find that info is lost because planar now points to a Point3D, so no information is really lost
* Do we allow a value of type Ti to a variable of type T8?
  * May want to allow, but warn, since one field is unspecified.
  * May want to disallow, and require
    v8.x = vi.x;
    v8.y = vi.y;

Suppose we disallow the "different shape/size" assignment, but
allow the rest.

What does it mean when we set v1 to (x=10,y=5) and then write
v7 = v1 (v1 is in type T1, v7 is in type T7)?
    type T1 = record x: int, y: int; end;
    type T7 = record y: int, x: int; end;
Options
  v7 is (y=5, x=10) // preserve naming of fields
  v7 is (y=10, x=5) // preserve ordering of values
* We might prefer the latter since not every type uses the same field names
* We might prefer the former, since real programmers pay attention more to field names than to order of fields within a record.

Implies that we probably don't want the most general assignment.
It's also hard to tell whether some things are the same

type T10 = union null; record v: int; next: T10 end;
type T11 = union null; record v: int; next: T11 end;
type T12 = union null; record v: int; next: T13 end;
type T13 = union null; record v: int; next: T12 end;

The general equivalence that says "any two things with the same structure are the same" is called "structural equivalence"

One compromise "structure + field names"

Another compromise: "name equivalence": Ti and Tj are equivalent
only if unalias*(Ti) = unalias*(Tj)