Today in CS362: Type Equivalence (and More)

Admin
  Erik picks on Mark
  Questions on Project, Phase 2?
  Cool David Perry talks after break

Overview
  Review
    What is a Type?
    Purposes of Type Checking
    Phases of Type Checking
    Kinds of Types
  Type Coercion
  Type Equivalence

Review
  What is a Type?

* Set of values
* Set of restrictions on the use of values

  Purposes of Type Checking

* Help ensure more correct code
* Compiler needs type information to generate assembly
  code

  Phases of Type Checking

* Assigning types to values and expressions
* Verifying that values are of the correct types
* Observation: Determining types "on the fly"is 
  potentially hard. (Type inference)

  Kinds of Types

* Built-in primitive types (integers, reals)
* User defined enumerated types 
* Subrange types
* Built-in type constructors/combiners
  + Arrays
  + Records
  + Functions
* Unions (pascal and few other languages)
* Pointers
* User defined type constructors (not Pascal)

Type Coercion
* Sometimes a value of one type is being used as a value
  of another type, but the types are similar
* In Pascal
  var f : real;

  ...
  
  f := 1;
* In C
  int i;
  i = 'a';
* Does your language allow them?
* If so, how?
  + Implicit coercion
  + Explicit coercion with a "type cast" operation
* And what does it mean?
  + Convert between representations
  + Reinterpret the same sequence of bits
* Is it always safe to convert from integers to floats/reals?
  "NO! NO! THREE TIMES NO!" - MF
  + Sometimes floats are more approximate.
  + Can affect results when order of application is unclear
    f := a / b
    Do we (a) Convert a and b to floats and do float division
    (b) Do integer division and convert result to float?
  + Given the same number of bits to represent a float and
    an integer, it's clearly the case that some large integers
    will be seriously approximated.

Type Equivalence
* Two values of different but similar types
  + Can we assign on to another?
  + Can we call a procedure that expects one type with a
    value of another type?
type
  r: real;
  i: integer;
...
  r := i; { should probably be legal }
  i := r; { should probably not be legal }
   { More ambigous }

procedure p(f: real)
procedure q(j: integer)

  p(1); { Not clear whether the 1 is supposed to be int or real }
  p(i); { similar to the assignment question }
  q(r); { probably not, given that we've already allowed the first }

type
  rec1 = record a: integer, b: integer end;
  rec2 = record a: integer, b: integer end;

Should values of type rec1 and values of type rec2 be
mutually assignable?
* Yes, they have the same definition
* No, the programmer intends to store different types
  in them
* No, it makes it a pain in the neck to check if two
  things are the same.

  point = record x: integer, y: integer end;
  chrom_count = record x: integer, y: integer end;

  rec3 = record x: integer, y: integer end;

Should values of type rec1 and values of type rec3 be
mutually assignable?
* If we say yes to the previous question, we should say
  yes to this question.

f(x,y) = x^2 + y^2
f(r,theta) = r^2 + theta^2 [Math person]
x = r * cos theta
y = r * sin theta
f(r,theta) = (r costheta)^2 + (r sintheta)^2
  = r^2 * (cos theta ^2 + sin theta ^2)
  = r^2