Project 05

Purpose:
	In this phase of constructing the calculator language interpreter you will build the core of the interpreter, the expression evaluator, and wire it into the shell of the interpreter that you wrote in the last phase.
Expression Evaluation
	Your main task for this phase is to supply a functor which exports a single function: evaluate_cexpression. As its name implies, this function takes a cexpression and evaluates it, returning a datavalue (unless an error occurs, in which case a Runtime_Error is raised). Of course, since expressions may refer to global variables, functions, and (when evaluating the application of a user-defined function) parameters, the evaluator will need access to all these things. Therefore, the full type for evaluate_cexpression is as given in the following signature: signature EVALUATOR = sig type cexpression; type vname; type datavalue; type operator; exception Runtime_Error of string; exception Internal_Error of string; val evaluate_cexpression : (vname * datavalue) list -> (operator * vname list * cexpression) list -> cexpression -> datavalue; end; The first parameter is the current list of variable definitions. It holds all the global variables. If we are in the midst of evaluating the application of a function, it also holds the definitions of the formal parameters of the functions (ie, the formal parameter names paired with the actual parameter values). The second parameter is a list of the current function definitions. It only grows when a new function is defined at the top-level of the interpreter. The third parameter is the expression to be evaluated. You should implement this signature using a functor with the following heading: functor EvaluatorFun(structure AbstractSyntax : ABSYN structure ConcreteSyntax : CONCSYN sharing type AbstractSyntax.datavalue = ConcreteSyntax.number) = struct type cexpression = AbstractSyntax.cexpression type datavalue = AbstractSyntax.datavalue type vname = AbstractSyntax.vname type operator = AbstractSyntax.operator The concrete syntax structure is needed because it holds the definitions of the constructors used for datavalues (numbers).
Applying Built-In Operators
	Whenever you encounter an application of a built-in operator you must: Evaluate each of the two expressions being used as actual parameters, reducing each to a datavalue. Perform the appropriate arithmetic on the two resulting values. Note that the language supports both integer and real values but that the operators are untyped. Your evaluator should be written to keep integers as integers for as long as possible, but to automatically cast them to reals when they are paired with a real as the other operand of some built-in operator. You do not need to test whether a real has any decimal part. So, for instance, (+ 3.0 2) evaluates to 5.0. However, if one integer is divided by another it should result in a real result if necessary, but an integer if the division can be done correctly using integer division. In the calculator language, division by zero should be a runtime error. However, due to SML 96 using IEEE floating point for real arithmetic, while integer division by 0 will raise the exception Div, real division by 0.0 returns either inf (if the numerator is non-zero) or nan (if the numerator is 0.0) rather than raise an exception. Therefore, you should check for all attempts at division by zero yourself, and raise Runtime_Error rather than attempt the division. Note, you may find it useful to define a function like: val apply_built_in = fn : operator -> datavalue list -> datavalue (where the second parameter will always be a list of length two), which implements all the basic arithmetic.
Applying User-Defined Functions
	Whenever you encounter an application where the operator is not one of the built-in binary operators, you must: Look up the definition of the operator in the list of user-defined functions. Evaluate each of the expressions being used as actual parameters, reducing each to a datavalue. Set up a list of bindings of the formal parameter names (from the function definition) to the values computed for the actual parameters in the last step. Evaluate the expression for the body of the function, in an environment that includes the bindings set up in the last step. Note that the number of formal parameters must match the number of expressions sent as actual parameters. If not, a Runtime_Error should be raised. (This error is also raised if you ever need the value of a variable and can't find a defintion for it.)
The Interpreter
	You should modify your interpreter from the last project so that it now actually does something with the commands the user types. In order to keep track of the current environment, the function you wrote for the read-eval-print-loop should now take two arguments: the list of variable definitions, and the list of function defintions. These have the same types as given in the type of evaluate_cexpression above. When top_level calls your function the first time, it should send empty lists for each of these arguments. When the user enters a define command, a binding for the new variable (assigned the result of evaluating the expression they define it to) should be added to the front of the variable-definitions list in the recursive call. The function-definitions list is similarly augmented in the recursive call when a defun command is encountered. Note that if the user redefines a variable or function, it is not necessary to remove or change the old definition. Simply attach the new definition to the front of the list and make sure that when you search for definitions you take the first one you encounter. This also makes it possible for formal parameters to shadow the defintions of global variables during the evaluation of a function application. You should also update your interpreter to implement the bindings command. Of course, it should only print the active definitions. Definitions that have been shadowed by re-definitions should not be shown. The signature for the interpreter remains unchanged from the last phase: signature INTERPRETER = sig val top_level : unit -> unit end; The header for the functor implementing the signature should now look like: functor InterpreterFun(structure AbstractSyntax : ABSYN; structure ConcreteSyntax : CONCSYN; sharing type ConcreteSyntax.number = AbstractSyntax.datavalue; structure SexpParser : SEXPPARSER; structure SyntaxConverter : SYNTAXCONVERTER; sharing type AbstractSyntax.ccommand = SyntaxConverter.ccommand; sharing type SexpParser.sexp = SyntaxConverter.sexp; structure Evaluator : EVALUATOR; sharing type Evaluator.datavalue = AbstractSyntax.datavalue; sharing type Evaluator.cexpression = AbstractSyntax.cexpression; sharing type Evaluator.vname = AbstractSyntax.vname; sharing type Evaluator.operator = AbstractSyntax.operator; ) = If you would prefer, you may take the interpreter functor from the sample solution to the last phase as your starting point for this phase. (Note, as in Project 4, if you want to use the function sexpression_to_string to convert sexpressions to strings (for use in error messages, for instance) then you will also need to add the constraint: sharing type ConcreteSyntax.sexp = SyntaxConverter.sexp; before the last sharing constraint in the functor header above.)
What I have Provided:
	You are strongly encouraged to use the sample solution to the previous phase as a staring point: in particular, the provided syntax converter. Therefore, I have created a version of the SML-NJ interpreter with the parser structure SexpParser, the two syntax structures ConcreteSyntax and AbstractSyntax, and the SyntaxConverter structure already loaded. The executable (or a link to it) is in /cs/cs131/bin/sml-sexp. The file /cs/cs131/bin/sml-cs131 (which is the version loaded by emacs) has also been re-linked to this version. I have also provided an executable sample solution at /cs/cs131/bin/sml-soln. You can use this to test how your solution should behave (from the standpoint of user interaction). This launches directly into my solution's interpreter. We will test your solution (which should be a single file containing both functors and nothing else) by compiling it with the file /cs/cs131/proj_5/make_sml_soln.sml with your file used in place of the two .sml files currently used.
How To Proceed
	The best plan of attack for this phase is to proceed incrementally. Begin by leaving the type of your read-eval-print loop as it is, and write the evaluator so that it only deals with expressions built from numeric literals and the built-in operators. Once this works entirely, modify the types of the read-eval-print loop and the evaluator so that they take the list of variable definitions. Implement the functionality for the define command in the read-eval-print loop, and modify the evaluator so that it knows how to deal with variables in expressions. Finally, integrate the parameter for the list of function definitions, and implement the defun command and modify the evaluator so that it knows how to apply user-defined functions. If you follow this course you are much more likely to complete the whole assignment. And, if you don't complete the whole assignment, you are more likely to have a partial solution that works, at least for those features it tries to implement. If you try to attack the entire problem at once, you are more likely to end up with a submission that doesn't do anything right (including compile).

	This page copyright ©1998 by Joshua S. Hodas. It was built on a Macintosh. Last rebuilt on Wed, March 31, 1999 at 1:50 PM.
http://cs.hmc.edu/~hodas/courses/cs131/projects/project05.html