MiniML Evaluator

Due Monday, October 14 at 2pm

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/02au/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 future assignments, you'll add a type checker and a type inferencer.)

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

• 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();.
• interpreter.sml is the root file, that includes all the others, and then invokes the read-eval-print loop. Read it for commentary on how to run the MiniML interpreter. (It's probably not the best way to use ML's multi-file compilation system, so don't use it as an example of that!) The README file also gives an overview worth reading.
• 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. You won't need to modify any other file in the implementation.
• 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 compute 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 examples uses appear in the skeleton eval.sml file.
• alist.sml defines assoc_lists, which are the implementation of immutable, extensible maps used for environments. You won't need to look at this file, unless you want to see how environments are implemented, or you want to see how SML modules can be used.
• ml.mllex and ml.mlyacc are the specifications of the ML lexer and MiniML parser, respectively. These are compiled by the ml-lex and ml-yacc programs (invoked by build-parser.sh) into ml.ml{lex,yacc}.{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.