CMSC 22300
Homework 3, Due 4/12/2012, 11pm

A template file tree.sml will be provided in your repository for
the code for problems 1 and 2.  The problem 3 solution should be
contained in a file types.txt in your homework3 directory.
For problem 4, a directory typecheck2 will contain the files for
the type checker. You will modify the file typecheck2/typecheck.sml.


1. [20] Here is a version of binary trees with values labeling
the leaf nodes:

datatype tree
  = Leaf of int
  | Node of tree * tree

We will call the "base" of such a tree the list of values at the
leaf nodes, going from left to right.

fun base (Leaf v) = [v]
  | base (Node(t1, t2)) = base t1 @ base t2

This implementation of base is not very efficient.  Define a better
fringe function that only needs to use :: to build the fringe list. 

Hint: Define a tail-recursive auxiliary function base1 with an
accumulator argument, and then define base in terms of base1
passing the appropriate initial value for the accumulator. Here
is a similar example involving reversing a list:

fun rev1(nil, ys) = ys
  | rev1(x::xs, ys) = rev1(xs, x::ys)

fun rev xs = rev1(xs, nil)


2. [25] Define a function equalBase on the trees from Problem 1
that tests whether two trees have the same base.

   equalBase : tree * tree -> bool

A straightforward way of doing this would be
  
   fun equalBase(t1,t2) = (base t1 = base t2)

But this is generally inefficient since if the bases differ it
should be possible to discover this without computing the complete
bases of both trees.  

Hint: The idea is a bit like the solution of Problem 1. The
function has to use auxiliary structures -- think stacks of subtrees.
The leaves of the two trees should be scanned from left to right
"in parallel".


3. [25] Without using the SML compiler to do it automatically (you are on
your honor!), compute the types of the variables defined by the following
declarations.

(a) fun f (x,y) = (x::y,nil::x);

(b) fun f v =
	let val x = (3,true)
	    fun g z = x::z
	 in g (v::nil)
	end;

(c) fun h w =
	let fun f(v,u) = (u,3)::v
	    fun g x = x::f (nil,"abc")
	 in g w
	end;

(d) fun D f g x = g (f x);  

(e) fun f x =
	let val y = x::nil
	    fun g z = (rev z, x) :: nil
	    fun h u = hd (g (u::x))
	 in h 1
        end;

4. [30] Extend the type checker of typecheck.sml (in the directory
typecheck2) for the expression language with an added declaration form
for recursive functions:

   datatype exp = .... (as before)

   and decl
     = Decl of var * exp             (* x = e *)
     | FunDecl of var * var * exp    (* fun f x = e or val rec f = fn x => e *)

Test your modified type checker by type checking (the abstract syntax form of):

   let fun fact n = if n = 0 then 1 else n * fact(n - 1)
    in fact 2

(you'll need to add minus (-) to the base context).

As an example, here is the declaration of the factorial function:

   fun fact x = if x = 0 then 1 else x * fact(x - 1)

and here is the decl data structure representing it:

    FunDecl("fact", "x", 
            If(App(Var "eqInt", Pair(Var "x", Num 0)),
               Num 1,
               App(Var "mult",
	           Pair(Var "x",
	                App(Var "fact", App(Var "minus", Pair(Var "x", Num 1)))))))

The key thing to note is that the variable denoting the recursive
function being defined (here "fact") can appear in the body
expression. The during the typing of the body, the function name has
a single type determined by unification, but once the definition has 
been typed, it is treated as a let declaration and the type of the
function can be generalized in the same way as ordinary let bindings.