Type CheckingType Checkingldots Type Checkingldots Type Checkingldots Type EquivalenceStructural Type EquivalenceName Type EquivalenceDeclaration Type EquivalenceType Equivalenceldots Structural Type EquivalenceStructural Type EquivalenceStructural Type EquivalenceName EquivalenceCase Study: CCase Study: Modula-3Modula-3Modula-3Readings and ReferencesHow Modula-3 Got Structural Type EquivalenceHow the language got its spotsIntroductionIntroductionIntroductionHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identityHow the types got their identity520 —Spring 2008 — 15CSc 520Principles of ProgrammingLanguages15 : Types — EquivalenceChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 15Type CheckingIn statically typed languages, when an object is defined,we must also give its type:TYPE equivalence = type;TYPE subrange = [from..to];TYPE enumeration = (id,id,...);TYPE array = ARRAY range OF type;TYPE record = RECORDfield : type;END;TYPE func = PROCEDURE (INTEGER):REAL;TYPE set = SET OF type;TYPE ptr = POINTER TO type;VAR name : type;PROCEDURE name (formal-list) [: type];[2]520 —Spring 2008 — 15Type Checking...In statically typed languages, whenever a typed objectus used, we must check that it occurs in the right typecontext:var x : integer;var y : record a:float; b:integer; end;beginx := y.a; (*⇐ error*)x := x + y.b;x := x + 5.0; (*⇐ error?*)end[3]520 —Spring 2008 — 15Type Checking...type compatibility — can an object of a certain type Tbe used in a certain context expecting a type U ?If T = U then, yes, of course.But, if T is almost the same as U , then what?type equivalence — what does it mean for two types Tand U to be equivalent?[4]520 —Spring 2008 — 15Type Checking...type conversion — how can we convert (cast) a valueof one type into another?type coersion — which automatic conversions betweentypes should the language allow?nonconverting type casts — what are theconsequences of allowing values to change typewithout conversion?type inference — given individual types of parts of anexpression, what is the type of the whole expression?[5]520 —Spring 2008 — 15Type Equivalence[6]520 —Spring 2008 — 15Structural Type Equivalencestructural equivalence — two types as the same if theyconsist of the same components.Example:TYPE T1 = RECORDa:INTEGER;b:ARRAY [0..10] OF CHAR;END;TYPE T2 = RECORDa:INTEGER;b:ARRAY [0..10] OF CHAR;END;Types T1 and T2 are equivalent.Algol-68, Modula-3, C, ML use structural typeequivalence.[7]520 —Spring 2008 — 15Name Type Equivalencename equivalence — each type declaration introducesa new type, distinct from all others.Example:TYPE T1 = ARRAY [0..10] OF CHAR;TYPE T2 = ARRAY [0..10] OF CHAR;Types T1 and T2 are not equivalent.Java and Ada use name equivalence.[8]520 —Spring 2008 — 15Declaration Type Equivalencedeclaration equivalence — two types are equivalent ifthey lead back to the same type.Example:TYPE T1 = ARRAY [0..10] OF CHAR;TYPE T2 = T1;TYPE T3 = T2;TYPE T4 = ARRAY [0..10] OF CHAR;Types T1, T2, T3 are equivalent.Pascal, Modula-2 use declaration equivalence.Type equivalence was left out of Pascal definition: someimplementations used name equivalence somestructural equivalence some declaration equivalence.[9]520 —Spring 2008 — 15Type Equivalence...TYPE T1 = RECORD a:CHAR; b:REAL END;TYPE T2 = RECORD a:CHAR; b:REAL END;VAR x1 : T1;VAR x2 : T2;VAR x3,x4: RECORD a:CHAR; b:REAL END;BEGINx1 := x2; (*OK, or not?*)x3 := x4; (*OK, or not?*)ENDname-equivalence: both assignments are illegal.declaration-equivalence: only 2nd assignment is legal.structural type equivalence: both assignments are legal.[10]520 —Spring 2008 — 15Structural Type EquivalenceTYPE Shape = OBJECTMETHOD draw (); · · ·METHOD move (X,Y:REAL); · · ·END;TYPE Cowboy = OBJECTMETHOD draw (); · · ·METHOD move (X,Y:REAL); · · ·END;VAR s:S; c:C;BEGIN s := c; (*OK?*) ENDIn Modula-3 (which uses structural equivalence) s andc are compatible! In Object-Pascal (which uses nameequivalence) they are not.[11]520 —Spring 2008 — 15Structural Type EquivalenceAre these types structurally equivalent:TYPE T1 = RECORDa : INTEGER;b : INTEGER;END;TYPE T2 = RECORDb : INTEGER;a : INTEGER;END;ML and Algol-68: NO, most other languages, YES.[12]520 —Spring 2008 — 15Structural Type EquivalenceAre these types structurally equivalent:TYPE T1 = ARRAY [1..10] OF CHAR;TYPE T2 = ARRAY [1..2*5] OF CHAR;TYPE T3 = ARRAY [0..9] OF CHAR;Algol-68: T1,T2,T3 are equivalent.Modula-2: T1,T2 are equivalent, T3 not.[13]520 —Spring 2008 — 15Name EquivalenceIs this assignment legal?TYPE celsius = REAL;TYPE farenheit = REAL;VAR c : celsius;VAR f : farenheit;c := f;In Modula-2, YES. This is a problem.In Ada, we can construct new types, which are notequivalent:type celsius is new integer;type farenheit is new integer;[14]520 —Spring 2008 — 15Case Study: CC uses a combination of declaration and structuralequivalence.Unions and structs use declaration equivalence.Pointers and arrays use structural equivalence.[15]520 —Spring 2008 — 15Case Study: Modula-3[16]520 —Spring 2008 — 15Modula-3TYPET1 = {A, B, C};T2 = {A, B, C};U1 = [T1.A..T1.C];U2 = [T1.A..T2.C];V = {A,B};T1 and T2 are the same type. Modula-3 uses structuraltype equivalence. Two types are the same if they lookthe same once they have been expanded.T1 and U1 are different types, one is an enumeration,the other a subrange.[17]520 —Spring 2008 — 15Modula-3TYPET = REF INTEGER;S = BRANDED "myType" REF INTEGER; (*ExplicitV = BRANDED REF INTEGER; (*Compiler-generatedBranded types are different from all other types. It is away of
View Full Document
Unlocking...