CSC362 2004S, Class 27: Type Checking Admin: * Train: 12:40 * Sample lexer and parser coming "real soon now" * Forgot: No files, No sets, No packed * Wednesday we start "Stack Frames" Overview: * A quote * An example: Assignable records * Techniques for deciding type equivalence Strcpy is approximately defined as follows while (*s++ = *t++) ; /The Quote/ I thought you might enjoy this quote from Kernighan & Ritchie (2nd edition, p. 198). Many operators cause conversions and yield result types in a similar way. The effect is to bring operands into a common type, which is also the type of the result. This pattern is called the *usual arithmetic conversions* First, if either operand is a long double, the other operand is converted to a long double. Otherwise, if either operand is a double, the other is converted to double. Otherwise, if either operand is a float, the other is converted to float. Otherwise, the integral promotions are performed on both operands; then, if either operand is unsigned long int, the other is converted to unsigned long int. Otherwise, if one operand is long int and the other is unsigned int, the effect depends on whether a long int can represent all values of an unsigned int; if so, the unsigned int operand is converted to long int; if not, both are converted to unsigned long int. Otherwise, if one operand is long int, the other is converted to long int. Otherwise, if one operand is unsigned int, the other is converted to unsigned int. Otherwise, both operands have type int. Wasn't that fun? /The Example/ type t0 = record a: integer; b: integer end; t1 = record a: integer; b: real end; t2 = record a: integer; b: real end; t3 = record b: real; a; integer end; t4 = record c: integer; b: real end; t5 = record a: integer; b: real; c: integer; end; t6 = t1; var v0: t0; v1: t1; v2: t2; v3: t3; v4: t4; v5: t5; v6: t6; v7: record a: integer; b: real end; v8,v9: record a: integer; b: real end; Which of these do we expect to be assignable to others? What principles guide these choices? Similar question for procedure foo(v: t1) Which do you assume can be used as an actual parameter to foo? f: float f = 1; v1 := v0 No: The definitions are different Yes: We can coerce ints into reals v1 := v2 Yes: The two structures are defined the same No: The names of the types are different, and if the programmer gives 'em different names, she must mean they have different purposes v1 := v3 No: Order is important: We don't want to rearrange fields Yes: They have the same structure; Membership name is not an ordered relationship v1 := v4 Yes: Named differently, but the types match up No: If field names are different, there is clearly a different intent It probably would make little sense to allow both v1 := v3 and v1 := v4 (similar to the reason for disallowing v1 := v4). The allowance of v1 := v3 prioritizes names. The second prioritizes order. What do you do about both? Alternate example t1 = record a: int; b: int; end t2 = record b: int; c: int; end standard-point = record x: real; y: real end point2 = record radius: real; theta: real end Side note (see oge.c in the Examples directory): What happens in C? In C, you cannot assign two records of different types to each other, unless you have fun with pointers. v1 := v5 No: You don't know what to do with C Yes: v5 is like a *subclass* of v1 (it extends v1 with an extra field). We don't mind giving up some information when we assign in subclasses. v5 := v1 No: You don't know what to do with C Yes: Think of databases; You can allow default values for entries Yes: Not really a loss of information as C isn't undefined v1 := v6 v6 := v1 Yes: They implicitly name the same underlying type No: Different names mean different types A few basic principles we've seen: * It's okay to throw away information When designing a typing strategy, what is a possible overall theory? * Relationships between types can resemble the class relationships in an OO language: A value of a subtype can be assigned to a variable of a supertype * Different names imply different types (what does it say about aliasing) * Same structures imply same types * Can be difficult to type check recursively-defined types record link1 = value: int; next: pointer to link1; end; record link2 = value: int; next: pointer to link2; end; * (Almost) anything goes What kinds of questions might you have on assigning arrays? * Can you coerce an entire array of ints into an entire array of reals * What if the two arrays are different sizes? * What if two arrays have different indices but the same size? a1: array[1..10] of int; b1: array[5..14] of int; What does a1 = b1 mean?