MiniML Evaluator

Due Thursday, January 20, at the start of class

In this assignment, you will build an evaluator for MiniML, which is a subset of SML. You will start from a partial implementation that already includes a read-eval-print-loop user interface, a parser from text to abstract syntax trees (ASTs), a representation of the possible values resulting from evaluation, and various pretty-printing functions for ASTs and values. The partial implementation is available in /cse/courses/cse505/05wi/hw1. There is a skeleton for the evaluator (in file eval.sml), with a few cases implemented to get you started; you need to complete the implementation of the evaluator. The current evaluator raises ImplementMe in all cases that you need to write; your finished solution should not raise ImplementMe anywhere. (In the next project assignment, you'll add a type inferencer to the MiniML implementation.)

Some notes:

• You should make sure to implement lexical, as opposed to dynamic, scoping in your interpreter. This distinction is important for implementing the evaluation of function calls properly.
• Your interpreter should support self-recursive functions, but not mutually-recursive functions. There are several ways of implementing self-recursive functions; there are some hints in the comments in eval.sml about function declarations and calls about one possible strategy.
• You must implement the semantics of invoking the first function case whose pattern is matched by the argument value. The (partially implemented) matchPattern function in eval.sml will try to match a value to a pattern, raising a MatchFailure exception if this cannot be done. Therefore, a nice way to implement the function-case lookup semantics is as follows: Try to match the argument against the first case's pattern. If it succeeds, invoke the case's body in an appropriately extended environment. If it fails, handle the MatchFailure exception and (in the handler body) recursively try to match against the rest of the cases. If there are no more cases, then an EvalError should be reported.
• Use higher-order functions (i.e. functions that take functions as arguments or results), such as map and filter, wherever sensible.
• hw1solution.x86-linux is a Linux binary of the sample solution for this homework -- a complete MiniML evaluator. You can play around with this version to get a feel for how your evaluator should behave and to compare with your solution. To use it, invoke SML from a Linux machine as follows:

  	sml @SMLload=hw1solution.x86-linux

  Then you can start up the read-eval-print loop by executing repl();.
• See the file README for a quick overview of the files in the MiniML implementation, and instructions on how to run it.

Each student should complete the assignment independently.

To turn in your completed assignment, send an email to both klee@cs and miker@cs with each of your changed  files attached.