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