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