CSE 341, Autumn 2005, Assignment 3ML - MiniML InterpreterDue: Thurs October 27, 10:00pmNote: This is a much longer assignment than anything we’ve seen up until now. You are given two weeksto complete this assignment, but I strongly encourage you to start early. Also, because this is a much morein-depth project, it will be worth three times as much as either of the first two homeworks.In this assignment, we will be writing an interpreter for MiniML, a subset of the ML language. We will bebuilding on assignment 2, so you are strongly encouraged to use your solution to that as a starting point.(You can also make use of the sample solution to assignment 2 if you would like, perhaps studying it to cleanup your own solution before using your code as a basis for this assignment.)To begin with, in assignment 2 we had to implement a datatype definition looking something like this:datatype exp =Var of string| Constant of int| Add of exp * exp| Sub of exp * exp| Mult of exp * exp| Negate of exp| Let of stmt list * expandstmt = Bind of string * exp;This was a good start, but now we want more functionality! Rather than simply evaluating expressions, wewant to eventually get a full-blown interpreter of a subset of ML, which we’ll call MiniML. The first steptoward this is to improve the exp datatype so that it includes not just integers but booleans as well. Soinstead of the Constant type, we want two types – Int and Bool.(Note that this means we need to change our environment to store string * exp pairs rather thanstring * int pairs. Although theoretically this means that the environment could store complex expres-sions like Add(Int 3, Int 4), in reality the only exp types which should go in the environment are thosethat cannot be simplified further, such as Int and Bool. See the hints section for more info on this.)Now that we have booleans, let’s add a few functions that take advantage of them. First, comparisonoperators LessThan, GreaterThan, and EqualTo. Also, we’ll want to do basic boolean logic, so we’ll needAnd, Or, and Not. Another useful ML operation is IfThenElse, which will take three arguments and, if thefirst one evaluates to Bool(true), return the second argument; otherwise it’ll return the third argument.At this point you’re probably thinking that exp is getting pretty big, but we aren’t done yet! Anotherimportant feature in ML is list manipulation. We’ve already seen in the quiz sections that we can build ourown list type, and that’s exactly what we’re going to do here. So, let’s add the following types to our expdefinition: Nil, Cons, Hd, Tl, and Null. (In this case, Nil stands for the ML constant nil, or [], while Nullstands for the ML function null which returns true if a list is empty.)Now that we’ve got our expanded exp datatype, let’s extend the eval function from assignment 2 so that ithandles these additional types. Instead of returning an int, make eval return an exp type in as simplifieda form as possible. (e.g., If the result is an int, return Int(n) for some n, if the result is a bool, returnBool(true) or Bool(false); if it’s a list, return either Nil or a Cons object, etc.)1Just like in assignment 2, if there is an unbound variable in the expression being evaluated, raise anUnboundVariable exception. If you ever encounter mismatched types, such as trying to add an Int and aBool, raise a TypeError exception.For example, the following code should result in r evaluating to Int(4).val e = Let([Bind("x", Int 3), Bind("y", Add(Int 5, Var "x"))],IfThenElse(LessThan(Var "x", Var "y"),Add(Var "x", Int 1),Sub(Var "y", Int 1)));val r = eval(e, [("x", Int 12)]);Up until now, the only type of stmt object we’ve seen is Bind, which just binds a value to a variable. Thisis all fine and dandy, but the real fun of ML lies in writing your own functions. (Hahaha... I crack me upsometimes.) We want the same functionality in MiniML! (Ok, that was just bad.) So, let’s extend the stmttype to include not only Bind but Fun as well.Like a Bind, a Fun also takes a string to identify the variable name to bind the function to. In addition, aFun needs a list of argument names (also represented as strings), and it needs an expression, of type exp,to evaluate.The tricky thing about functions, however, is that they are evaluated in the environment in which they weredeclared, not the one in which they’re called. We’ve already seen this sort of thing in class, but just as areview, x will be bound to 11 rather than 16 at the end of this code:val x = 3;val y = 6;fun plusx y = x + y;val x = 8;val y = 13;val x = plusx(x);What this means is that, when we encounter a function declaration (via a Fun statement), we need to save theenvironment. This is achieved through a closure. We discussed closures in lecture, but to recap: A closureis essentially a function tied to the environment in which it was declared. When a function is invoked, whatSML is really doing is extending the environment of its closure to include the function parameters, and thenevaluating the function expression in that environment.Closures are essentially expressions that just happen to be functions. When you declare functions in ML,the interpreter often spits back at you a statement similar to var f = fn : int -> int. Think of the fnas signifying that the value of f is a closure.Since closures are expressions, what this means is we need to add Closure to our exp datatype. Remember:closures take a variable name (which will be the name of the function), a list of parameter names, anexpression to evaluate, and an environment in which to evaluate them.This is all fine and dandy, but what good are functions if we can’t call them? So now we also want to addone final type to exp (I promise, this is it!), called ApplyFun. ApplyFun takes an exp which should evaluateto a closure, and also takes a list of exps which correspond to the parameters to that closure.When eval encounters an ApplyFun, the first thing it should do is evaluate the first argument and makesure it’s a Closure. Then all of the supplied function arguments need to be evaluated and added to the2closure’s environment. And in order for a function to be able to call itself recursively, it needs to be in itsown environment as well. This can be done by adding a binding between the function name (which should bepart of the Closure) and the Closure itself to the environment. Finally, after the closure’s environment isextended with the
View Full Document
Unlocking...