## Computer Science & Engineering 505 Concepts of Programming Languages Assignment 6

Nov 19, 1997
Due: Nov 26

1. This question concerns abstract types and subtypes, parameterized types, and the contravariant rule. Suppose we have an abstract type `Stack` parameterized by `T`, the type of object that the stack contains. `Stack` has two operations: `push`, which takes a single argument of type `T` and doesn't return anything; and `pop`, which takes no arguments and returns an object of type `T`.

We also have an abstract type `Sink`, again parameterized by `T`. `Sink` has a single operation `push`, which takes a single argument of type `T` and doesn't return anything. (A `Sink` is like a `Stack` except that you can never get anything out of it.)

Finally, we have an abstract type `Source`, parameterized by `T`. `Source` has a single operation `pop`, which takes no arguments and returns an object of type `T`. (A `Source` is like a `Stack` except that you can never put anything into it -- it just produces objects of type `T`. Where they come from is a mystery never fully explained.)

Using the contravariant rule, what is the subtype relation between the following pairs of types? (The answer to each question would be either `X` is a subtype of `Y`, `Y` is a subtype of `X`, or neither is a subtype of the other.)

1. `Stack[Integer]` and `Stack[Number]`
2. `Sink[Integer]` and `Sink[Number]`
3. `Source[Integer]` and `Source[Number]`
4. `Stack[Integer]` and `Source[Number]`
5. `Stack[Number]` and `Source[Integer]`
6. `Stack[Integer]` and `Sink[Number]`
7. `Stack[Number]` and `Sink[Integer]`

2. The same as Question 1, except use the covariant rule. If the covariant rule gives an incorrect answer, give an example of a program that breaks; or one that will always execute without type errors, even though the covariant rule says it is incorrect.

3. Give two realistic examples of object-oriented programs in which static type checking is too restrictive. (You don't have to write out the program, just describe the situation.)

4. Consider the following definitions in Cardelli's applicative language. type object = (age:int) type vehicle = (age:int, speed:int) type car = (age:int, speed:int, fuel:string) /* make a new vehicle that is going faster */ val faster(x:vehicle) : vehicle = (age=x.age, speed=2*x.speed) val rec reallyfast(x:vehicle) : vehicle = reallyfast(age=x.age, speed=2*x.speed) /* identity function for vehicles */ val id(x:vehicle) : vehicle = x /* convert a car to use undleaded fuel */ val upgrade(x:car) : car = if x.fuel = "leaded" then (age=x.age, speed=x.speed, fuel="unleaded") else x val mycar = (age=10, speed=45, fuel="leaded") Given the above definitions, find the value of the following expressions. Also find the types of the expressions using the typechecking rules in Section 13 of the paper, showing how you used the rules. faster (upgrade mycar) upgrade (faster mycar) upgrade (id mycar) reallyfast mycar Hint: the value of a nonterminating computation is