[ ^ CSE 341, Winter 2004 home page ]

Homework 3

Due: Fri 30 Jan 2004

Turn in hard copy in class, and an electronic copy as an email attachment sent to Sandra.

Part 1: Search trees

The Ullman textbook section 6.3 describes the implementation of a search tree in ML wherein the user must pass a comparison function to each tree-handling function. In class, we discussed an implementation of search trees that stores the comparison function in the tree datatype. For this question, you will write several functions for manipulating trees in the style of the tree datatype we used in class.

Consider the following datatypes:

datatype 'a BTNode =
         Empty
       | Node of 'a * 'a BTNode * 'a BTNode;

datatype 'a BTree =
    Tree of { greaterThan:'a * 'a -> bool,
              equals:'a * 'a -> bool,
              root:'a BTNode };

1. Adapt the insert and delete functions in the textbook to use this datatype (note that we're using greaterThan rather than a "less than" function, as the textbook does). Each of these functions should return a BTree.
2. Write a function listToTree that uses foldl to produce a fresh tree from the values in any list. The user should provide the comparison functions.

3. Write a curried function treeFold that takes three arguments: a function, a base case, and a tree; and "folds" the tree, in a style analogous to the way foldl folds a list. The function should have the type:

   (('a * 'b * 'b) -> 'b) -> 'b -> 'a BTree -> 'b

   Note that the first argument, a function, takes the tree's element type ('a) and two values that result from folding the subtrees ('b).

4. Use treeFold to implement a function treeToList, which "flattens" trees in-order into a list.

Part 2: Expression evaluation

In this section, we will use the following datatypes, which represent a subset of ML's values, declarations, and expressions:

datatype Value =
         Integer of int
       | Boolean of bool;

datatype Decl = Val of string * Expr
and Expr =
    Const of Value
  | Var of string
  | OpAdd of Expr * Expr
  | OpNot of Expr
  | OpEq of Expr * Expr
  | Let of Decl * Expr
  | If of Expr * Expr * Expr;

This datatype represents the syntax tree of expressions and declarations. For example, the expression

let val x = 4+5 in x+x end

would be represented as follows:

Let(Val("x", OpAdd(Const(Integer(4)),Const(Integer(5)))),
    OpAdd(Var("x"), Var("x")));

Note that we only allow normal form let-expressions, which have exactly one declaration. (It is easy to see that more general let-expressions can always be rewritten into normal form.)

5. Write the Expr corresponding to the following ML expression:

   let val x = let val y = 5 in y+y end;
   in if x=10 then 25 else 30
   end

Because we have variables, expressions can only be evaluated in an environment; to represent environments we'll use an association list containing string * Value pairs:

type binding = (string * Value);
type environment = binding list;

6. Write a (curried) function lookup of type Environment -> string -> Value that, given an environment and a string, returns the value of the binding in that list with the string. When the value is not found in the environment, simply raise Fail "Undefined variable.".

7. Write the mutually recursive functions exprToString and declToString which translate an instance of Expr or Decl respectively into a string of ML code that means the same thing. For example, given the answer you wrote for question 5, ML should print the expression given above. Notes:

   • Don't worry about code that wouldn't typecheck in ML. Just print it.
   • Don't worry about pretty formatting (you don't have to add indentation, line breaks and such, but add parens to reflect order of evaluation).
   • You will need to write a helper function valueToString.

8. Consider the following skeleton of an eval function, which has type environment -> Expr -> Value and evaluates expressions:

   fun evalExp env (Const v) = v
     | evalExp env (OpAdd (e1, e2)) =
       (case (evalExp env e1, evalExp env e2) of
            (Integer i1, Integer i2) => Integer(i1 + i2)
          | _ => raise Fail "Adding non-ints.")
     | evalExp _ _ = raise Fail "Unimplemented operation";

   Add cases to this function to handle all the expressions in our datatype --- i.e., variable expressions, equality testing (of compatible values), logical negation, and let-expressions. Notes:

   • The two non-error cases above do not use or alter the environment; but some other cases will need to do so.
   • You will need to make evalExpr mutually recursive with a function declToBinding, which takes a declaration (e.g. the one nested in the let-expression) and returns a binding.
   • Again, do not worry about expressions that would be statically ill-typed in ML. Just evaluate them. If you attempt to do something ill-typed, like logically negating an integer, then raise an error using raise Fail "Type error".
   • You will find it very profitable to write a few test Exprs and manually compute the "right answers" for them before you start coding. exprToString and valueToString will also be useful as you debug your code.
   • You will need a helper function to detect whether two values are equal.