Change LogOverviewTypesCompiling, etc...ProblemsMP 8 – EvaluationCS 421 – Fall 2006Revision 1.5Assigned November 8, 2006Due November 28, 2006 23:59Extension 48 hours (20% penalty)1 Change Log1.0 Initial Release.1.5 Code in problem 11 now evaluates to hsome closurei instead of the incorrect hsome recvari. This was areflection of an error in the solution file. An updated grader should be posted within the week (11/21/06).2 OverviewPreviously, you created a lexer and a parser for FUN. Finally, your hard work will pay off – it is time to create anevaluator. Lexing, parsing, and type inferencing will be taken care of automatically. Your evaluator can assume thatits input is correctly typed.Your evaluator will be responsible for evaluating three kinds of things: programs, declarations, and expressions.At top level, your evaluator will be called on a program and on an empty memory. It will recurse on the parts of thatprogram, eventually returning the final memory (if your program terminates.)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.Take a look at the following types from expressions.ml:type exp = Var of string | Const of string |App of (exp*exp) | Fun of (string*exp) |Rec of (string*exp) | Comp of (decl*exp) |Natexp of int | Boolexp of bool | Stringexp of stringand decl = Let of (string*exp)type prog = decl listThese are the things that will serve as input to your evaluator.Now look at the following types defined in values.ml:type memory = (string*value) list(*our notion of a value*)and value = Nat of int | Bool of bool | String of string1| Pair of value*value| List 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 your evaluator in general, and output from your evaluator when evaluating declarations and programs. Forexample, one evaluates a declaration starting from some initial memory, and a final memory is returned.4 Compiling, etc...Just as in mp7, you will be given many files. You are only to modify mp8.ml, adding the functions requested. To testyour code, type gmake (or make on non-unix machines) and then ./fun, which is the executable produced.You can then enter in programs at the command prompt; they will be evaluated (or not evaluated) starting from theinitial memory. Each time, if evaluation is successful, the resulting memory will be displayed. Note that a programcan fail at any of several stages: lexing, parsing, type inferencing, or evaluation itself. Evaluation itself will tend tofail until you have solved at least some of the problems to come.The files are:fun.ml This file contains the main body of the fun executable. It handles lexing, parsing, and type inferences, andcalls your evaluation functions, while providing a friendly prompt to enter FUN concrete syntax.funlex.cmo, .cmi These files contains the compiled lexing code.funparse.cmo This file contains the compiled parsing code.expressions.ml This file contains type declarations related to expressions.infer.ml This file contains type inferencing code.Makefile This file is the makefile for compiling the code and producing the executable fun.mp8.ml This file contains the evaluator code, and is the only one you should modify.rubric.ml This file contains test code. It will be available in a few days, if it is not up yet.values.ml This file contains type declarations pertaining to values, functions for printing out values, and the threefunctions isnullary, isunary, and isbinary. The printing function are called in fun.ml and you do notneed to bother with them.5 ProblemsThese problems ask you to create an evaluator for FUN by writing the functions evalprog, eval decl, andeval exp as specified. In addition, you will be asked to implement the functions valnullary, valunary, andvalbinary.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 lecture the week of Nov. 7; see thelecture notes for details.Here are some guidelines:2• eval prog takes a program and a memory, and returns a memory• eval decl takes a declaration and a memory, and returns a memory• eval exp takes an expression and a memory, and returns an 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:p = programd = declarationm = memory (environment)e = expressionv = value– n = nat– b = bool– s = stringx = variable1. Nats, Bools, Strings (5 pts)Create eval exp ex m and make it handle nats, bools, and strings.(n, m) ⇓ n (b, m) ⇓ b (s, m) ⇓ s2. Declarations (5 pts)Implement eval decl d m, which takes a declaration and a memory and returns the memory resulting fromexecuting the declaration. Note that {x → v} is a memory binding the variable x to v, and {x → v} + m adds thisbinding to the memory m, resulting in a new memory.(e, m) ⇓ v(let x = e, m) ⇓ ({x → v} + m)3. Programs (5 pts)Implement eval prog p m, which takes a program and a memory and returns the memory resulting fromrunning the program.Note: eval prog will initially be given the empty memory.3(d, m) ⇓ m0((d; ; ), m) ⇓ m0(d, m) ⇓ m00(p, m00) ⇓ m0((d p), m) ⇓ m0> let x = 12 let b = true let s = "hello";;Thank you. Evaluating...result is:s -> "hello"b -> truex -> 124. Local declarations (5 pts)Extend eval exp ex m to handle local declarations.(d, m) ⇓ m0(e, m0) ⇓ v(d in e, m) ⇓ v> let _ = let x = 7 in 12;;Thank you. Evaluating...result is:_ -> 125. Variables (no recursion) (5 pts)Extend eval exp ex m to handle variables that are not recursive. These are variables in m which are not equalto rech...i, which is a special case to be handled later.(x, m) ⇓ vwhere x → v is in m, v not of the form rech...i> let _ = let x = 7 in x;;Thank you. Evaluating...result is:_ -> 746. Nullary constants (5 pts)Extend eval exp ex m to handle nullary (arity 0) constants. Additionally, implement valnullary c, whichtakes in a nullary constant and returns its
View Full Document
Unlocking...