Type Checking CSc 520 Principles of Programming Languages 27 Types Equivalence Christian Collberg collberg cs arizona edu Department of Computer Science University of Arizona Copyright c 2005 Christian Collberg 520 Spring 2005 27 1 In statically typed languages when an object is defined we must also give its type equivalence type subrange from to enumeration id id array ARRAY range OF type record RECORD field 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 TYPE TYPE TYPE TYPE TYPE 520 Spring 2005 27 Type Checking In statically typed languages whenever a typed object us used we must check that it occurs in the right type context var x integer var y record a float b integer end begin x y a error x x y b x x 5 0 error end 520 Spring 2005 27 3 2 Type Checking type compatibility can an object of a certain type T be 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 T and U to be equivalent 520 Spring 2005 27 4 Type Checking type conversion how can we convert cast a value of one type into another type coersion which automatic conversions between types should the language allow Type Equivalence nonconverting type casts what are the consequences of allowing values to change type without conversion type inference given individual types of parts of an expression what is the type of the whole expression 520 Spring 2005 27 5 Structural Type Equivalence 520 Spring 2005 27 6 Name Type Equivalence structural equivalence two types as the same if they consist of the same components name equivalence each type declaration introduces a new type distinct from all others Example Example TYPE T1 RECORD a INTEGER b ARRAY 0 10 OF CHAR END TYPE T2 RECORD a INTEGER b ARRAY 0 10 OF CHAR END 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 Types T1 and T2 are equivalent Algol 68 Modula 3 C ML use structural type equivalence 520 Spring 2005 27 7 520 Spring 2005 27 8 Declaration Type Equivalence declaration equivalence two types are equivalent if they lead back to the same type Example TYPE TYPE TYPE TYPE T1 T2 T3 T4 ARRAY 0 10 OF CHAR T1 T2 ARRAY 0 10 OF CHAR Types T1 T2 T3 are equivalent Type 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 BEGIN x1 x2 OK or not x3 x4 OK or not END Pascal Modula 2 use declaration equivalence name equivalence both assignments are illegal Type equivalence was left out of Pascal definition some implementations used name equivalence some structural equivalence some declaration equivalence declaration equivalence only 2nd assignment is legal 520 Spring 2005 27 9 Structural Type Equivalence Shape OBJECT METHOD draw METHOD move X Y REAL END TYPE Cowboy OBJECT METHOD draw METHOD move X Y REAL END VAR s S c C BEGIN s c OK END TYPE In Modula 3 which uses structural equivalence s and c are compatible In Object Pascal which uses name equivalence they are not 520 Spring 2005 27 11 structural type equivalence both assignments are legal 520 Spring 2005 27 10 Structural Type Equivalence Are these types structurally equivalent TYPE T1 RECORD a b END TYPE T2 RECORD b a END INTEGER INTEGER INTEGER INTEGER ML and Algol 68 NO most other languages YES 520 Spring 2005 27 12 Structural Type Equivalence Are 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 Name Equivalence Is 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 not equivalent type celsius is new integer type farenheit is new integer 520 Spring 2005 27 13 520 Spring 2005 27 14 Case Study C C uses a combination of declaration and structural equivalence Unions and structs use declaration equivalence Case Study Modula 3 Pointers and arrays use structural equivalence 520 Spring 2005 27 15 520 Spring 2005 27 16 Modula 3 TYPE T1 A B C T2 A B C U1 T1 A T1 C U2 T1 A T2 C V A B Modula 3 TYPE T REF INTEGER S BRANDED myType REF INTEGER Explicit V BRANDED REF INTEGER Compiler generated Branded types are different from all other types It is a way of circumventing structural type equivalence T1 and T2 are the same type Modula 3 uses structural type equivalence Two types are the same if they look the same once they have been expanded T1 and U1 are different types one is an enumeration the other a subrange 520 Spring 2005 27 17 520 Spring 2005 27 18 Readings and References Read Scott pp 330 334 How Modula 3 Got Structural Type Equivalence 520 Spring 2005 27 19 520 Spring 2005 27 20 How the language got its spots From Chapter 8 Systems Programming with Modula 3 Edited by Greg Nelson Prentice Hall ISBN 0 13 590464 1 Anonymous I greatly welcomed the chance of meeting and hearing the wisdom of many of the original language designers I was astonished and dismayed at the heat and even rancour of their discussions Apparently the original design of ALGOL 60 had not proceeded in that spit it of dispassionate searchfor truth which the quality of the language had led me to suppose C A R Hoare Like many programming languages Modula 3 was designed by a committee The meetings were held at the DEC Systems Research Center in Palo Alto whose director Bob Taylor likes to record important events on videotape including our meetings 520 Spring 2005 27 21 Introduction At first we found the whirring of the cameras distracting but eventually we became used to it We even started to imagine that the tapes might be useful in university courses to teach students how real scientists approach problems of programming language design Unfortunately when we reviewed the tapes at the end of the project it was obvious that to show them to students was out of the question Such scenes would probably drive students out of computing if not all the way out of the sciences In fact to show the tapes to anybody at all would be highly embarrassing But our sense of duty to history prevailed and we resolved to provide the world with copies of the tapes Nobody was more disappointed than we when the secretary making the copies inadvertently turned the machine to erase instead of copy and the
View Full Document
Unlocking...