MiniML Evaluator

Due Monday, October 13, 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 from your UW CSE account in the directory /cse/courses/csep505/03au/hw1; it also is available as a zip file for download.  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 future assignments, you'll add a type checker and a type inferencer.)

The files

Here is a quick tour through the files of the MiniML implementation:

• MiniML.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=MiniML.x86-linux

  This will automatically start up the read-eval-print loop.  There are similar sample solutions available for Solaris (MiniML.sparc-solaris) and Windows (MiniML.x86-win32).
• README explains the structure of the code and gives instructions on how to run the MiniML interpreter, among other things.
• sources.cm defines the source files of the project, for use by SML's CM incremental compilation tool.
• miniml.sml is the root file, that compiles and loads all the others, and then invokes the read-eval-print loop.
• repl.sml defines the repl() function, which is the outer, "user interface" function that runs the MiniML read-eval-print loop. It repeatedly reads a line of input, calls the parser to parse the line into an internal AST representation, prints out the parsed AST, calls the evaluator to evaluate the AST, and then prints out the resulting value. You won't need to look at this file, for this first homework, although you'll extend it to add your typechecking phase in the next homework.
• eval.sml defines the evaluation functions. A number of cases have been stubbed out with ImplementMe exceptions; your task is to rewrite them as real code. This is the only file that you need to modify in this assignment.
• ast.sml defines the representation of ASTs. This is the main data structure over which your evaluator will operate. It also includes a CFG grammar specification of the syntax of MiniML. ast_print.sml defines print functions for ASTs. You won't need to modify these files, but you'll need to learn how to use the AST datatypes.
• value.sml defines the representation of values computed as a result of evaluating MiniML ASTs. Your evaluator will need to construct and manipulate these things. You won't need to modify these files, but you'll need to learn how to create and manipulate values.
• env.sml defines the Environment type, which is an immutable (but extensible) map from strings to values, and the functions on environments. You'll need to learn to use these functions. Some example uses appear in the skeleton eval.sml file.
• alist.sml defines assoc_lists, which are the implementation of immutable, extensible association lists used for environments. You won't need to look at this file, unless you want to see how environments are implemented.
• ml.lex and miniml.y are the grammar specifications for the ML lexer and MiniML parser, respectively. These are compiled by the ml-lex and ml-yacc tools (invoked automatically when compiling the program) into ml.lex.sml and miniml.y.{sml,sig}. The parser.sml file is a small wrapper defining the parse function. You don't need to look at any of these files.

The files are implemented in SML structures (a.k.a. modules).  Local open declarations (a.k.a. imports) are used to allow the body of one structure to reference things declared in a different structure conveniently.  You don't really need to know anything about structures, local, or open for this project; just write your code inside the body of the Eval structure in eval.sml.

Tips

• Scoping: 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.
• Recursion: If you don't do anything special, your interpreter will not properly support recursive functions. For this assignment, recursion is optional. You can get extra credit by implementing it, but you should not use side-effects to do so.
• Function invocation: 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.

What to turn in

You should turn in your version of the file eval.sml. In addition, we'd like you to answer the following questions:

1. Is it possible to support mutually recursive functions in the current syntax of the interpreter? Why or why not?
2. Consider the following code:

   val x = 3
   fun f() = x
   val x = 4
   f()

   The result of f() is 3, not 4. Explain why.
3. Consider the following code:

   fun f(x) = (let val x = 3 in x*x end) + x
   f(2)

   The result of f(2) is 11. In this invocation of f, the first two uses of x in the body have value 3, while the last use of x has value 2. How does the binding from x to 3 get removed from the environment in your interpreter?

How to turn in