CSE 505 Homework 2: Polymorphic typing, Scheme, Haskell

Due Tuesday, February 8, at the start of class

Problem 1: Eta-expansion

Type the following function into ML:

       fun f x y = (x,y);

Now imagine that we wanted to use partial application to create a new function g that takes a single argument y and returns the pair (3,y):

       val g = f 3;

What happens when you type this into ML? Explain the warning you get.

Now try using this function g to create the pair (3,7). Explain the error message you get.

One way to fix this type of problem is called eta expansion. Eta expansion converts an expression e to (fn y => e y). For example, if we wanted to create our function g, we could use eta expansion:

       val g = (fn y => (f 3) y);

Explain why this solves the problems you identified in parts a and b.

The same problem you discovered in parts a and b occurs with functions that return polymorphic functions. For example:

       fun f2 x = (fn y => (x,y)); 
       val g2 = f2 3;

Fortunately, we can use eta-expansion in this situation as well:

       val g2 = (fn y => (f2 3) y);

However, eta-expansion does not always preserve the semantics of the program.

Give an example of a situation where eta-expansion does not preserve the semantics of a program.

Problem 2: Types

Try each of the following functions in ML. For each function:
- If it type checks, explain why it has to have the type it has.
- If it does not type check, explain why not.
We are not interested in hearing how the type inference algorithm works on these functions (you'll get plenty of practice with that in Project 2!). Rather, we want you to explain, intuitively, why each function either must have the type it has, or why it can not have any type.
1. fun f x y = x (x y)
2. fun f x y = (x y) y
3. fun absorb x = absorb
4. fun create x = (create x) x

Problem 3: Types II

Give an ML function that leads the type inferencer to try to unify 'a == (int * 'a list), which violates the "occurs check". What error message does SML print?

Problem 4: Scheme continuations

call/cc and dynamic-wind can easily be used to implement exceptions as a user-level library. Here is one possible API:

(throw v): throw an exception, with argument (exception value) v.
(try f h): evaluate (f), returning its result if it returns normally. If f or a callee throws an exception that's not handled by some dynamically nested try, then evaluate (h v), where v is the exception value. Return the result of (h v) as the result of (try f h). (h v) may itself throw an exception, which is propagated to the try block enclosing this try.

Here is a trivial example of code that uses this API:

(define (apply-and-divide f x y default)
  (try (lambda ()                    ; body
         (if (= y 0)
             (throw 'divide-by-zero)
             (f (/ x y))))
       (lambda (exn)                 ; handler
         (if (= exn 'divide-by-zero)
             default
             (throw exn)))))

; returns #f due to divide-by-zero
(apply-and-divide
    (lambda (v) (* v 100))
    5 0 #f)

; exn 'random-error propagates to top-level.  Should print a message
; (using built-in display) and return nothing.
(apply-and-divide
    (lambda (v) (throw 'random-error))
    5 2 #f)

The above apply-and-divide function is roughly equivalent to the following ML code:

exception DivideByZero
fun applyAndDivide f x y default =
    (if y = 0 then raise DivideByZero
             else f (x / y))
    handle DivideByZero => default

Read the documentation for call/cc and dynamic-wind in the R5RS, and then do the following:

Implement try.
Implement throw.

Hint: these are the pieces you will need for your solution:

A stack of handlers.
A way to exit to top-level when an exception is raised and the handler stack is empty. Note that top-level evaluation is itself just a continuation...
try will use dynamic-wind to add and remove a handler around executing its body.
throw will pass the exception to the most recent handler.

You will need dynamic-wind in order to handle the case where the user invokes a continuation from inside the body of try. For example, consider the following code:

(call/cc (lambda (cont)
          (try (lambda () (cont "foobar"))
               (lambda (v) ("baz")))))

After evaluating this expression at toplevel, the handler stack should be empty.

Problem 5: Haskell type classes

In the previous assignment, you encoded objects using recursive records of functions, using ML datatypes to "close the loop" of recursion; and you encoded classes/constructors using functions that generated these records. In Haskell, the natural way to do "object-oriented programming" is with type classes, which directly support OO-like idioms.

Write a Point type class with all the operations of the Point type from the previous assignment.
Construct two instances of this type class that implement rectangular and polar representations. Note that we are asking for two instances of a type class (i.e., two types) rather than two instances of a type (i.e., two objects).
Write a Colored type class with only the operation getColor, which returns a string.
Write a ColoredPoint type class that extends both Colored and Point, and write an instance of this type class.

Test your type classes by writing a magnitude function over Points, and convince yourself that you can pass any Point to this class. Next, write a distance function that takes two Points of arbitrary (possibly different) representation and determines the (Euclidean) distance between them. Third, write a triangleArea function that takes three Points of arbitrary representation and determines the area of the triangle defined by those points. You do not have to turn these three functinos in.

Lastly, try to write a pairwiseDistances function that takes a list of Points of arbitrary representation, and computes the distance between all pairs of Points in the list.

Why can't you do this last task? Describe your answer in terms of what the type of pairwiseDistances would have to be. Here are some suggestions for how to think about this answer (you do not necessarily have to answer these following questions; they're just to help you think):
- Where would the type variable have to go? How would it have to be instantiated? Why is this outlawed by the Haskell type system?
- Why don't you have this problem with distance, triangleArea, quadrilateralArea, pentagonArea, etc.? What is it about lists (or, for that matter, arrays) that defeats the type system?

Turn-in instructions

Turn in:

Hard copy, in class, on the due date, of your code and English for the homework, with your name at the top. We suggest you use enscript -2r -DDuplex:true (see man enscript for details) to produce your code listings.
Email to KEUNWOO ONLY a single plain text file, containing all your answers and sample code, attached to an email with the exact subject line 505-hw2.

Code formatting guidelines

No line of code shall be more than 80 characters long. (This makes the output of enscript -2r readable.)
Every file shall have a banner comment at the top indicating your name and the name of the file.
All indentation shall be proper, using only spaces (no tabs; these break when people set tab width display to a different number of spaces). In emacs, you can use M-x untabify to convert tabs to spaces (or use Google to find .emacs incantatons that will automatically untabify any file you edit before you save it)

chambers@cs.washington.edu