CMSC 221/321
Homework set 6
Due: Thursday, Nov 17, 2011 at midnight

6.1 [25]. Write a type checker in SML for the TFun language, extended
with paring (*) and sum (+) type operators and their associated
primitives and expression forms (call this TFun[*,+]).

The type checker will be a function that takes an expression e and a
type environment Γ and produces a type τ such that Γ ⊦ e: τ.  You will
need to define types for the abstract syntax of expressions and types,
and for typing environments (use an association list).  You will also
need to implement a mapping (Σ) from constants to their types
representing the "signature" of the language.

  type variable
  type const
  type expr
  type ty
  type tyenv = (variable * ty) list   (* Γ and Σ *)

The main function will have the following type:

  val typeOf: expr * tyenv -> ty

You can use the TFun abstract syntax types defined in prog_4_1.sml.
For 5 points extra credit, you can have your type checker handle the
extended TFun language defined in prog_4_2.sml, which includes a
Letrec construct.

To test your type checker, a file tfun-tests.sml is provided on
the homework web page.


6.2 [25]. Implement in SML a big-step environment-based CBV
(BSEv) evaluator for PTFun.  Start with the evaluator for basic
TFun provided in prog_4_2.sml, and add the new features for
recursion, products, sums, and recursive types one after another.
Finally, add support for polymorphism for 10 points extra credit.

The expressions defined in tfun-tests can also be used to
test your evaluator, but new tests are needed for products,
sums, recursive types and polymorphism.