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)