Change LogOverviewTypesCompiling, etc...Running MicroMLGiven FilesProblemsMP 8 – An Evaluator for MicroMLCS 421 – Spring 2007Revision 1.1Assigned April 11, 2007Due April 18, 2007 23:59Extension 48 hours (20% penalty)1 Change Log1.0 Initial Release.1.1 Correct code examples.2 OverviewPreviously, you created a lexer and a parser for MicroML. Finally, your hard work will pay off – it is time to create anevaluator. Lexing, parsing, and type inferencing will be taken care of automatically (you have already implementedthese parts in previous MPs). Your evaluator can assume that its input is correctly typed.Your evaluator will be responsible for evaluating two kinds of things: declarations, and expressions. At top level,your evaluator will be called on a declaration or an expression and on an empty memory. It will recurse on the parts,eventually returning the final memory.3 TypesFor this assignment, one should note the difference between expressions and values. An expression is a syntax tree,like 2 + (4 ∗ 3) or (3 < 4), whereas a value is a single object, like 14 or true. A value is the result of evaluating anexpression; or it can be a closure.Take a look at the following types from mp8comon.ml:type exp = Unit| Bool of bool| Char of char| Int of int| Real of float| String of string| Pair of exp*exp| Id of string| LetIn of dec*exp| App of exp*exp| Fn of string*exp| IfThenElse of exp*exp*expanddec = Valbind of (string*exp)| Valbindrec of (string*exp)| Local of (dec*dec)| Seq of (dec*dec)1These are the things that will serve as input to your evaluator.Now look at the following types defined in mp8common.ml:type memory = . . .(*our notion of a value*)and value = Unitval| Intval of int| Boolval of bool| Stringval of string| Realval of float| Charval of char| BuiltInOpval of string| Pairval of value*value| Listval of value list| Closure of string*exp*memory| Recvar of string*exp*memoryThe type value is output from your evaluator when evaluating expressions. The type memory serves as bothinput to evaluator in general, and output from your evaluator when evaluating declarations and programs. For example,one evaluates a declaration starting from some initial memory, and a final memory is returned.One interacts with memories, as we did with environments MP5, using the following functions, pre-defined inmp8common.ml:(*memory operations*)val make_mem : string -> value -> memory = <fun>val lookup_mem : memory -> string -> value option = <fun>val sum_mem : memory -> memory -> memory = <fun>val ins_mem : memory -> string -> value -> memory = <fun>val pervasive_memory : (string*value) list =[("and",Closure ("b1", Fn ("b2", IfThenElse (Id "b1", Id "b2", Bool false)), []));("or",Closure ("b1", Fn ("b2", IfThenElse (Id "b1", Bool true, Id "b2")), []));("not", Closure ("b", IfThenElse (Id "b", Bool false, Bool true), []));("nil", Listval []); ("+", BuiltInOpval "+"); ("-", BuiltInOpval "-");("*", BuiltInOpval "*"); ("/", BuiltInOpval "/"); ("<", BuiltInOpval "<");(">", BuiltInOpval ">"); ("<=", BuiltInOpval "<=");(">=", BuiltInOpval ">="); ("mod", BuiltInOpval "mod");("div", BuiltInOpval "div"); ("+.", BuiltInOpval "+.");("-.", BuiltInOpval "-."); ("*.", BuiltInOpval "*.");("/.", BuiltInOpval "/."); ("**", BuiltInOpval "**");("::", BuiltInOpval "::"); ("head", BuiltInOpval "head");("tail", BuiltInOpval "tail"); ("=", BuiltInOpval "=");("ˆ", BuiltInOpval "ˆ"); ("fst", BuiltInOpval "fst");("snd", BuiltInOpval "snd")]4 Compiling, etc...For this MP, You will only have to modify mp8-skeleton.ml (first convert it to mp8.ml), adding the functions re-quested. To test your code, type make and the three needed executables will be built: mp8int, mp8intSol and2grader. The first two are explained below. grader checks your implementation against the solution for a fixed setof test cases as given in the tests file.4.1 Running MicroMLThe given Makefile builds executables called mp8int and mp8intSol. The first is an executable for an inter-active loop for the evaluator built from your solution to the assignment and the second is one built from the standardsolution. If you run ./mp8int or ./mp8intSol, you will get an interactive screen, much like the OCaml interac-tive screen. You can type in MicroML declarations followed by a semicolon, and they will be evaluated, and the finalmemory will be displayed.At the command prompt, the programs will be evaluated (or fail evaluation) starting from the initial memory(Mp8common.pervasive memory). Each time, if evaluation is successful, the resulting memory will be dis-played. Note that a program can fail at any of several stages: lexing, parsing, type inferencing, or evaluation itself.Evaluation itself will tend to fail until you have solved at least some of the problems to come.4.2 Given Filesmp8-skeleton.ml: This file contains the evaluator code. This is the ONLY file that you will have to modify. Changethe name of the file to mp8.ml and work on it.mp8int.ml: This file contains the main body of the mp8int and mp8intSol executable. It handles lexing, parsing,and type inferences, and calls your evaluation functions, while providing a friendly prompt to enter MicroMLconcrete syntax.mp8lex.cmo, .cmi: These files contain the compiled lexing code.mp8yacc.cmo: This file contains the compiled parsing code.5 ProblemsThese problems ask you to create an evaluator for MicroML by writing the functions eval dec, and eval exp asspecified. In addition, you will be asked to implement the function app builtin.Modify only these functions. Do not modify any other code in mp8.ml or any other file. You may, however,add your own helper functions to mp8.ml.For each problem, you should refer to the list of rules given as part of the problem. The rules specify how evaluationshould be carried out, using natural semantics. Natural semantics were covered in the class; see the lecture notes fordetails.Here are some guidelines:• eval dec takes a declaration and a memory, and returns a memory• eval exp takes an expression and a memory, and returns a valueThe problems are ordered such that simpler and more fundamental concepts come first. For this reason, it isrecommended that you solve the problems in the order given. Doing so may make it easier for you to test yoursolution before it is completed.Here is a key to interpreting the rules:d = declarationm = memory (environment)e = expression3v = value– n = integer– b = bool– r = real– c = character– s = stringx = identifier/variablet =
View Full Document