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?