CSE 505 Homework 1: ML Exercises

Problem 1: Using types to think about programs

  1. Write ML functions with the following types:
    1. 'a -> 'a
    2. int * 'a -> 'a
    3. 'a * 'b * 'c -> 'c * 'b * 'a
    4. 'a list -> 'a
    5. unit -> 'a
  2. For each of the above types, would it have been possible to write a function that returned any value that is different from the one your function returned? If not, explain why not. If so, what else could it have possibly returned?

Problem 2: Tail-recursion

  1. Write a tail-recursive function to compute the n-th fibonacci number.
  2. Write a tail-recursive version of the list append function that we saw in class on Thursday. You may use an auxiliary data structure.
  3. Discuss briefly the relative space costs of the ordinary recursive vs. tail-recursive versions of the above.

Problem 3: Evaluating propositional formulas

Consider the following datatype representing "ground" formulas in propositional logic (with no variables):

datatype GForm =
         GConst of bool
       | GNot of GForm
       | GOr of GForm * GForm
       | GAnd of GForm * GForm

For example, the formula true and (false or not true) would be represented by the ML data structure

GAnd(GConst true, GOr(GConst false, GNot (GConst true)))
  1. Write the function evalGForm of type GForm -> bool, which evaluates ground propositional formulas.

Now, consider propositional formulas with variables:

datatype Formula =
         Const of bool
       | Var of string
       | Not of Formula
       | Or of Formula * Formula
       | And of Formula * Formula

Since we have variables, formulas can only be evaluated in an environment, which maps variables to values:

type Environment = (string * bool) list

Fundamentally, when one has variables in any language, whether propositional logic or a more complicated programming language, there are two ways to implement evaluation. First, one could pass the environment recursively through each evaluation step, and lookup variables on demand. (This is the approach we'll take in the Mini-ML evaluator.) The second approach is to substitute the actual value of each variable consistently throughout the expression, and then evaluate the resulting "ground" expression.

  1. Implement the function substVar, having type Environment * Formula -> GForm, which translates a Formula into the GForm that is equivalent to it in the given Environment. Use higher-order functions (like map, find, etc.) to manipulate the environment, to the extent possible and appropriate.

Problem 4: Simulating objects

In ML, you can simulate objects to some extent by using records of functions. Consider the following type for "functional points":

type Point = {
  x:unit -> real,
  y:unit -> real,
  translate:real * real -> Point,
  rotate   :real -> Point
  }

where x returns the x-coordinate, y returns the y-coordinate, translate returns a new point that is like the old point, but moved by the new x and y coordinates (i.e., if you take the point (-12, 3.1) and translate it by (2.5, 4.2), you get (-9.5, 7.3)), and rotate rotates the point about the origin by the specified number of radians.

Notice that the operations that would mutate a point in a traditional OO language instead return a copy of a new point. Hence, you could write the following code:

val p:Point = ...;

(* gets x value of p *)
val x_of_p    = (#x p)();

(* get a point like p, but rotated 180 degrees *)
val rotated_p = (#rotate p)(Math.PI);

Aside from the rather ugly syntax, we can use the record members as we would use message names (a.k.a. method names in Java, or virtual function names in C++) in object-oriented language. As in OO languages, the client is insulated from the implementation of the functions that implement these messages.

  1. Type the above Point type declaration into ML and try to evaluate it. Explain the error message you get. What feature, which ML type synonyms lack, do you need here?
  2. Define a Point type that fixes this problem. You may use any ML construct you know.
  3. Write the function makeRect:real * real -> Point, which takes x and y values and returns a Point with the given x and y values. This object should have an efficient translate implementation (two arithmetic operations).
  4. Write the function makePolar:real * real -> Point, which takes rho and theta values and returns a Point. The object resulting from a makePolar call should have an efficient rotate implementation (one arithmetic operation).
  5. Write down a ColoredPoint type, which is exactly like Point but contains an additional string field describing its color.
  6. Can you write a function polymorphic over Point and ColoredPoint type objects? Why not? What error does ML give you when you try?
chambers@cs.washington.edu