CSE 505 Final

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.

   Hint: Java supports overloading, so that a method

   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.