# CSE 505 Final

December 12, 1997             Name:

110 minutes, open notes, 125 points total. Please write any long answers on the back of the exam or on separate pieces of paper!
1. (5 points) Consider the following claim.
"A simple model for interactive text-based I/O in a purely functional language is to represent the user's input and the system's output as lists of characters. A problem with this in Haskell is that, because of lazy evaluation, prompts printed by the program and inputs from the user may not be properly synchronized. However, this would not be a problem in a language with eager evaluation (call-by-value); if Haskell used eager evaluation we could easily model the user's input and the system's output as lists of characters."
Is this correct? Discuss.

2. (8 points) Suppose the following Haskell code for trees has been loaded. -- the tree datatype data Tree a = EmptyTree | Node a (Tree a) (Tree a) -- various tree traversal functions preorder EmptyTree = [] preorder (Node x left right) = [x] ++ preorder left ++ preorder right inorder EmptyTree = [] inorder (Node x left right) = inorder left ++ [x] ++ inorder right postorder EmptyTree = [] postorder (Node x left right) = postorder left ++ postorder right ++ [x] -- some sample trees t1 = Node 5 (Node 2 EmptyTree EmptyTree) (Node 8 EmptyTree EmptyTree) t2 = Node "squid" EmptyTree (Node "tuna" EmptyTree EmptyTree) What is the result of evaluting the following Haskell expressions? Give both the value and its type. If there is a compile-time type error, or a non-terminating computation, say so. If the result is an infinite data structure, give some initial parts of it. postorder preorder t1 Node 100 t1 t1 Node 100 t1 t2

3. (10 points) Suppose that you have defined a class Complex of complex numbers in Smalltalk, with instance variables `rPart` and `iPart` for the real and imaginary parts. Show the appropriate methods so that you can provide a class-specific initialization message, so that you can write `Complex r: 3.4 i: 5.0` to create a new complex number. Describe how the expression `Complex r: 3.4 i: 5.0` is evaluated (in particular, any metaclasses and where the methods are found).

4. (10 points) Describe how complex number creation and initialization might be handled in a prototype-based system with inheritance.

5. (10 points) Why is the lookup of an exception handler in Smalltalk done using dynamic rather than lexical scoping?

6. (9 points) This question concerns abstract types and subtypes, parameterized types, and the contravariant rule. Suppose we have an abstract type `Dictionary` parameterized by `K`, the types of the keys, and by `V`, the types of the values. `Dictionary` has two operations: `lookup`, which takes a single argument of type `K` and returns an object of type `V`; and `store`, which takes two arguments of types `K` and `V` respectively. Thus `lookup` looks up a key in the dictionary and returns the corresponding value, while `store` enters a new key-value pair in the dictionary, or replaces the value in an existing key-value pair.

We also have an abstract type `Array`, parameterized by a single type `T`. Array also has two operations: `lookup`, which takes a single argument of type `integer` and returns an object of type `T`; and `store`, which takes two arguments of types `integer` and `T` respectively.

Thus, an array is a kind of dictionary where the keys are restricted to being integers.

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`, they are equivalent (i.e. each is a subtype of the other), or neither is a subtype of the other.

1. `Dictionary[Object,Object]` and `Array[Object]`
2. `Dictionary[Integer,Object]` and `Array[Object]`
3. `Array[Integer]` and `Array[Object]`

7. (9 points) The same as the previous question, 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.

8. (10 points) Describe how Java handles the covariance/contravariance question. Consider both ordinary classes and arrays.

`void mytest(Object x)` is considered to be different from a method `void mytest(String x)` since one takes a parameter of type Object and the other a parameter of type String. In other words, if you have a method `void mytest(Object x)` in a class A and a method `void mytest(String x)` in a subclass of A, the `void mytest(String x)` method won't override the inherited one -- it's considered to be a different method. Also, it is an error in Java to have two methods with the same name and argument types but with different return types.

9. (10 points) Consider the following example of using F-bounded polymorphism in Pizza. (This is similar to the one in the lecture notes, except that we're allowing mutable sets here.) interface Comparable<A> { boolean less(A x); } interface Set<A implements Comparable<A>> { boolean contains(A x); /* test if a set contains x */ void add(A x); /* add x to the set */ } Add a specification for a method `max` for `Comparable` that finds the maximum of the receiver and the argument. Add specifications for a method `add_all` for `Set` that adds all of the elements in the argument (also a set) to the receiver, and another method `maximum` that finds the maximum element in a set.

10. (10 points) In the previous question, why did we need a parameter to the `Comparable` interface? What would be wrong with just writing interface Comparable { boolean less(Comparable x); } Give an example where this doesn't work right.

11. (10 points) This question should test your understanding of blocks in Smalltalk, in particular scope issues and returning from blocks.

Consider the following Smalltalk code. There is a class named `Squid`, with three methods named `method1`, `method2`, and `method3`.

Class Squid method1 | x | Transcript show: 'entering method 1'. x := 1. self method2. Transcript show: 'returning from method 1'. method2 | x | Transcript show: 'entering method 2'. x := 2. self method3: [Transcript show: 'x =' , x printString. ^nil]. Transcript show: 'returning from method 2'. method3: b | x | Transcript show: 'entering method 3'. x := 3. b value. Transcript show: 'returning from method 3'. If we evaluate `s method1` for an instance `s` of Squid, what is printed to the transcript? Explain your reasoning.

12. (10 points) For a conditional statement, Kaleidoscope requires that the truth or falsity of the condition be known at the time the conditional is executed. Thus if we define the following version of `not`: constructor my_not (b : boolean) = (c : boolean) if b then c=false else c=true; end constructor my_not; we can use it to find the value of `x` in the following equality constraint: x = my_not(false); but we can't use it to find the value of `y` here: true = my_not(y); Suppose Kaleidoscope were changed to remove this restriction, so that we wouldn't need to know the value of the conditional when it was encountered, and so we could find an appropriate value for `y` to satisfy the constraint. Briefly discuss the implications for the language semantics and implementation. (One paragraph is enough.)

13. (14 points) Tacky true/false questions!
1. Suppose we have an instance m of a Smalltalk class C, and we are evaluating `m display`. If we encounter the expression `super display` in the method for `display`, we'll look for a `display` method starting in C's immediate superclass.
2. In CLP(R) the assignment statement `X := X+5` is represented by temporarily asserting the constraint `Temp = X+5`, then retracting the constraint using backtracking, and finally asserting `X = Temp`.
3. Consider the simple language described in Cardelli's paper "A Semantics of Multiple Inheritance". Suppose that the value of an expression e is v. If we apply the typechecking function to e, it will return a type that is the same as or a subtype of the actual type of v.
4. Pizza is statically typed, eliminating the need for any runtime type tests.
5. Suppose that we had a version of Haskell that uses eager evaluation. If evaluating an expression e in Eager Haskell terminates without error and gives a value v, evaluating the same expression in normal Haskell will always terminate without error and give the value v.
6. The converse: If evaluating an expression e in normal Haskell terminates without error and gives a value v, evaluating the same expression in Eager Haskell will always terminate without error and give the value v.
7. CLP(R) in effect uses call-by-constraint for argument passing, where equality constraints are set up between the corresponding actual and formal parameters.