Computer Science & Engineering 505
Concepts of Programming Languages
Assignment 6

Nov 9, 1994
Due: November 16, 1994

1. Suppose we are adding a class Complex to an object-oriented language with existing types Integer and Float. Explain how to make the + message work correctly using:
   1. the 'generality' message as used in the current version of Smalltalk
   2. double dispatching
   3. multi-methods (use Cecil syntax)
   You don't need to implement this (although the gung-ho Smalltalk programmers are welcome to do the first two).

2. This question concerns abstract types and subtypes, parameterized types, and the contravariant rule. Suppose we have an abstract type Dictionary parameterized by K, the type of the keys in the dictionary, and V, the type of the values in the dictionary. Dictionary has two operations: put, which takes two arguments of types K and V respectively and doesn't return anything; and at, which takes one argument of type K, and which returns something of type V.

   We also have an abstract type Array. Array is parameterized by a single type T, the type of element in the array. Arrays also have two operations: put, which takes two arguments of types Integer and V respectively and doesn't return anything; and at, which takes one argument of type Integer, and returns something of type V.

   Another type is BlackHole -- a dictionary that you can put things into, but not get them back. BlackHole is parameterized by K and V. BlackHole has one operation: put, which takes two arguments of types K and V respectively and doesn't return anything.

   Finally there is a type Random parameterized by K and V as usual. Random has one operation, namely at, which takes one argument of type K, and which returns something of type V (which it presumably generates randomly -- we don't get to tell it at any rate).

   Using the contravariant rule, what is the subtype relation between the following pairs of types? The answer to each question should be one of:

   • X is a subtype of Y
   • Y is a subtype of X
   • X is a subtype of Y and Y is a subtype of X (in other words, the two types are equivalent)
   • neither is a subtype of the other

   Assume that Number is a subtype of Object, and Integer is a subtype of Number.

   1. Dictionary[Integer,Object] and Array[Object]
   2. Dictionary[Number,Object] and Array[Object]
   3. Dictionary[Integer,Integer] and Array[Number]
   4. Dictionary[Integer,Number] and BlackHole[Integer,Object]
   5. Dictionary[Integer,Object] and BlackHole[Integer,Number]
   6. Dictionary[Integer,Number] and Random[Number,Object]
   7. Dictionary[Integer,Object] and Random[Integer,Integer]

3. The same as Question 2, 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.

4. 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.)