Programming Assignment #4 (200 Points)Due: Fri, Feb 21, 5:00pmThe overall objectives of this assignment are:
Again, no individual function (or case within a match expression) requires more than 1525 lines, so if you’re answer is longer, you can be sure that you need to rethink your solution. The template for the assignment, as well as several test cases is available as a single zip file pa4.zip that you need to download and unzip. In this assignment, we’ve provided a Makefile that will stitch together the pieces of your solution together. You will often run % maketo compile your code before running, as instructed throughout the assignment. This will produce many intermediate files (e.g. nanoml.top, nano.cmo, etc.) that you may want (or need) to remove before recompiling subsequent changes. Running % make cleanshould delete all the temporaries and leave you with only the important files, including your solutions. It is a good idea to start this assignment (the second problem, in particular) very early, since it will help clarify your understanding of ML for the midterm! Note: All the solutions can be done using the purely functional fragment of OCaml, using constructs covered in class, and most require the use of recursion. Solutions using imperative features such as references or while loops will receive no credit. Reference MaterialThe following sample lexers, parsers, interpreters may be helpful for reference as you work through this assignment. Submission Instructions1. Create zip fileOnce you are finished, you must submit only the following three files:
After creating and populating the directory as described above, create a zip file by going into the directory solution/ and executing the UNIX shell command: % zip firstname_lastname_cse130_pa4.zip nano.ml nanoLex.mll nanoParse.mlywhere firstname and lastname have your first and last names respectively. 2. Validate the zip fileNext, you will use the program validate_pa4 program to determine whether your zip file’s structure is wellformed. Do this by executing the UNIX shell command:% validate_pa4 firstname_lastname_cse130_pa4.zipThe validate_pa4 program will output OK if your zip file is wellformed and your solution is compiled. Otherwise, it will output some error messages. Before going to step 3, make sure that your zip file passes validate_pa4 program. Otherwise you get a zero for the whole assignment. If you have any trouble with this, refer to the instructions in step 1. 3. Submit the zip fileOnce you have created the zip file with your solutions, you will use the turnin program to submit this file for grading by going into the directory solution/ and executing the UNIX shell command: % turnin c cs130w p pa4 firstname_lastname_cse130_pa4.zipturnin will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your zip file. See the ACS Web page on turnin for more information on the operation of the program. NanoML Data Structures and OverviewIn Assignment #2, we started working with a small language called NanoML by writing a (simple) pretty printer. In this assignment, we return to NanoML, this time to write a lexer/parser which will read in NanoML programs and an evaluator that will evaluate, or interpret, them. NanoML ExpressionsThe language of expressions, defined in nano.ml, is as before with a few additions: type binary_operator = ...  Cons type expr = ...  LetRec of string * expr * expr  NilThe Cons operator, to be used inside binary operations, and the Nil expression are used to build lists. The LetRec construct is the recursive analog to Let. NanoML ValuesNanoML expressions evaluate to values, which we encode with the following OCaml datatype in the file nano.ml: type value =  VInt of int  VBool of bool  VNil  VPair of value * value  VClosure of env * string option * string * expr and env = (string * value) listIntuitively, the OCaml values VInt 4 and Bool true
represent the NanoML integer value 4 and boolean value true,
respectively. VNil and VPair are used to encode
NanoML lists.
More interestingly, closures (function values) in NanoML are represented as:
The environment itself is a value of type env which is a
phonebook represented as a list of Problem #1:

String  Token 

let  LET 
rec  REC 
=  EQ 
in  IN 
function  FUN 
if  IF 
else  ELSE 
{  LBRACE 
}  RBRACE 
(  LPAREN 
)  RPAREN 
Nano.Let
,
Nano.LetRec
,
Nano.Fun
, and
Nano.If
(of type Nano.expr
).
That is,
Once you have implemented this functionality and recompiled (by typing make
at
the UNIX prompt) you should get the following behavior at the ./nanoml.top
prompt:
# Main.token_list_of_string "let rec foo = function (x) { if (y) { z } else { w } } in foo";;  : NanoParse.token list = [NanoParse.LET; NanoParse.REC; NanoParse.Id "foo"; NanoParse.EQ; NanoParse.FUN; NanoParse.LPAREN; NanoParse.Id "x"; NanoParse.RPAREN; NanoParse.LBRACE; NanoParse.IF; NanoParse.LPAREN; NanoParse.Id "y"; NanoParse.RPAREN; NanoParse.LBRACE; NanoParse.Id "z"; NanoParse.RBRACE; NanoParse.ELSE; NanoParse.LBRACE; NanoParse.Id "w"; NanoParse.RBRACE; NanoParse.RBRACE; NanoParse.IN; NanoParse.Id "foo"] # Main.string_to_expr "let rec foo = function (x) { if (y) { z } else { w } } in foo";; Nano.LetRec ("foo", Nano.Fun ("x", Nano.If (Nano.Var "y", Nano.Var "z", Nano.Var "w")), Nano.Var "foo")
Add the following tokens to the lexer and parser:
String  Token 

+  PLUS 
  MINUS 
*  MUL 
/  DIV 
<  
<=  
!=  NE 
&&  AND 
  OR 
Add all of these as binary operators to your parser, producing values
of type Nano.binary_operator
.
Add support for binary expressions with the syntax
(<expr> <op> <expr>),
where <op> ranges over the operators above.
Each should result in a Nano.BinaryOp
expression with the
corresponding Nano.binary_operator
.
Note: Unlike in Assignment #2, we require parentheses around the entire expression. Also note that the arguments to these binary operators may be any expressions. (Type checking happens after lexing and parsing, so ((3 + true)  7) is just fine as far as the parser is concerned.)
Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# Main.token_list_of_string "+  /* < <= = && !=";;  : NanoParse.token list = [NanoParse.PLUS; NanoParse.MINUS; NanoParse.DIV; NanoParse.MUL; NanoParse.OR; NanoParse.LT; NanoParse.LE; NanoParse.EQ; NanoParse.AND; NanoParse.NE] # Main.string_to_expr "(x + y)";;  : Nano.expr = Nano.BinaryOp (Nano.Var "x", Nano.Plus, Nano.Var "y") # Main.string_to_expr "if ((x <= 4)) { (a  b) } else { (a && b) }";;  : Nano.expr = Nano.If (Nano.BinaryOp (Nano.Var "x", Nano.Le, Nano.Int 4), Nano.BinaryOp (Nano.Var "a", Nano.Or, Nano.Var "b"), Nano.BinaryOp (Nano.Var "a", Nano.And, Nano.Var "b")) # Main.string_to_expr "if ((4 <= z)) { (1z) } else { (4*z) }";;  : Nano.expr = Nano.If (Nano.BinaryOp (Nano.Int 4, Nano.Le, Nano.Var "z"), Nano.BinaryOp (Nano.Int 1, Nano.Minus, Nano.Var "z"), Nano.BinaryOp (Nano.Int 4, Nano.Mul, Nano.Var "z")) # Main.string_to_expr "let a = (6 / 2) in (a!=11)";;  : Nano.expr = Nano.Let ("a", Nano.BinaryOp (Nano.Int 6, Nano.Div, Nano.Int 2), Nano.BinaryOp (Nano.Var "a", Nano.Ne, Nano.Int 11))
Add rules to your parser to allow parenthesized expressions, that is, pairs of extra parentheses around any expression.
In addition, add a rule to your parser for function application. Unlike in Assignment #2, we will require parentheses around the entire application, not around the argument. That is, function application should be written (<expr> <expr>), which corresponds to calling the (function corresponding to the) left expression with the (argument corresponding to the) right expression.
Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# Main.token_list_of_string "() ( )";;  : NanoParse.token list = [NanoParse.LPAREN; NanoParse.RPAREN; NanoParse.LPAREN; NanoParse.RPAREN] # Main.string_to_expr "(f x)";;  : Nano.expr = Nano.App (Nano.Var "f", Nano.Var "x") # Main.string_to_expr "((function (x) { (x+x) }) (3*3))";;  : Nano.expr = Nano.App ( Nano.Fun ("x", Nano.BinaryOp (Nano.Var "x", Nano.Plus, Nano.Var "x")), Nano.BinaryOp (Nano.Int 3, Nano.Mul, Nano.Int 3)) # Main.string_to_expr "(((add3 (x)) y) z)";;  : Nano.expr = Nano.App ( Nano.App ( Nano.App (Nano.Var "add3", Nano.Var "x"), Nano.Var "y"), Nano.Var "z") # Main.filename_to_expr "tests/t1.ml";;  : Nano.expr = Nano.BinaryOp ( Nano.BinaryOp (Nano.Int 2, Nano.Plus, Nano.Int 3), Nano.Mul, Nano.BinaryOp (Nano.Int 4, Nano.Plus, Nano.Int 5)) # Main.filename_to_expr "tests/t2.ml";;  : Nano.expr = Nano.Let ("z1", Nano.Int 4, Nano.Let ("z", Nano.Int 3, Nano.Let ("y", Nano.Int 2, Nano.Let ("x", Nano.Int 1, Nano.Let ("z1", Nano.Int 0, Nano.BinaryOp ( Nano.BinaryOp (Nano.Var "x", Nano.Plus, Nano.Var "y"), Nano.Minus, Nano.BinaryOp (Nano.Var "z", Nano.Plus, Nano.Var "z1")))))))
Add the following tokens to the lexer and parser:
String  Token 

[  
]  
;  SEMI 
::  COLONCOLON 
Add rules to your lexer and parser to support parsing lists.
The :: operator should be treated as any other binary operator,
so should be fully parenthesized.
[] should be parsed as Nil
.
[a;b;c;d] should be parsed as if it were
(a::(b::(c::(d::[])))).
Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# Main.string_to_expr "(1::(3::(5::[])))";;  : Nano.expr = Nano.BinaryOp (Nano.Int 1, Nano.Cons, Nano.BinaryOp (Nano.Int 3, Nano.Cons, Nano.BinaryOp (Nano.Int 5, Nano.Cons, Nano.Nil))) # Main.string_to_expr "[1;3;5]";;  : Nano.expr = Nano.BinaryOp (Nano.Int 1, Nano.Cons, Nano.BinaryOp (Nano.Int 3, Nano.Cons, Nano.BinaryOp (Nano.Int 5, Nano.Cons, Nano.Nil))) # Main.string_to_expr "((1::(3::(5::[]))) = [1;3;5])";;  : Nano.expr = Nano.BinaryOp (Nano.BinaryOp (Nano.Int 1, Nano.Cons, Nano.BinaryOp (Nano.Int 3, Nano.Cons, Nano.BinaryOp (Nano.Int 5, Nano.Cons, Nano.Nil))), Nano.Eq, Nano.BinaryOp (Nano.Int 1, Nano.Cons, Nano.BinaryOp (Nano.Int 3, Nano.Cons, Nano.BinaryOp (Nano.Int 5, Nano.Cons, Nano.Nil))))
In this assignment, we’ve required function application and binary operation expressions to be fully parenthesized, so that it’s easier to write our parser. Clearly, it’s annoying to have to write so many parentheses everywhere in NanoML code, so we would want to rig our parser to allow parentheses to be omitted where possible.
Doing this often requires a careful mix of
In this problem, you will implement an interpreter for NanoML.
As above, $
denotes the UNIX shell
prompt, and #
is a nanoml.top prompt.
After you run
$ make ...you should (hopefully) have in your directory a file called nanoml.top, which is an OCaml shell that is preloaded with the modules corresponding to your NanoML implementation.
$ ./nanoml.top NanoML $ ./nanoml.top Objective Caml version 3.12.0 # Nano.Int 5;  : Nano.expr = Nano.Int 5
First consider the (restricted subsets of) types described below:
type binary_operator = Plus  Minus  Mul  Div type expr = Int of int  Var of string  BinaryOp of expr * binary_operator * expr type value = VInt of int type env = (string * value) listHere,
binop
and expr
are used to represent simple
NanoML expressions.
Use listAssoc
to write an OCaml function
val lookup: string * env > valuethat finds the most recent binding for a variable (i.e. the first from the left) in the list representing the environment. Use
lookup
to
write an OCaml function
val eval : env * expr > valuethat when called with the pair
(evn, e)
evaluates the NanoML
expression e
in the environment evn (i.e. uses evn
for the values of the free variables in e) and raises an exception
NanoMLEvalError ("variable not bound: x")
if the expression
contains a free variable "x"
that is not bound in
evn
.
Once you have implemented this functionality and recompiled, you should get the
following behavior at the ./nanoml.top prompt
(take a look at the helper functions plus
,
mul
, div
, and minus
in nano.ml):
# open Nano;; # let evn = [("z1",VInt 0); ("x",VInt 1); ("y",VInt 2); ("z",VInt 3); ("z1",VInt 4)];; val evn : (string * Nano.value) list = [("z1", VInt 0); ("x", VInt 1); ("y", VInt 2); ("z", VInt 3); ("z1", VInt 4)] # let e1 = minus (plus (Var "x") (Var "y")) (plus (Var "z") (Var "z1"));; val e1 : Nano.expr = BinaryOp (BinaryOp (Var "x", Plus, Var "y"), Minus, BinaryOp (Var "z", Plus, Var "z1")) # eval (evn, e1);;  : Nano.value = VInt 0 # eval (evn, Var "p");; Exception: Nano.NanoMLEvalError "variable not bound: p".
Next, add support for the binary operators:
type binop = Plus  Minus  Mul  Div  Eq  Ne  Lt  Le  And  OrThis will require using the new kind of
value
, VBool
:
type value = VInt of int  VBool of boolThe operators
Eq
and Ne
should work if both operands
are VInt
values, or if both operands are VBool
values.
The operators Lt
and Le
are only defined for
VInt
values, and And
and Or
are only
defined for VBool
values.
For all other (invalid) arguments, a NanoMLEvalError
exception should be
raised with an appropriate error message (of your choosing).
Next, implement the evaluation of If
expressions.
To evaluate If(p,t,f)
your evaluator should first evaluate
p
and if it evaluates to the true value (represented as
VBool
) then the expression t
should be evaluated and
its value returned as the value of the entire If
expression.
Instead, if p
evaluates to the false value, then
f
should be evaluated and that result should be returned. If
p
does not evaluate to a VBool
value, then your
evaluator should raise a NanoMLEvalError
exception carrying an
appropriate error message.
Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# open Nano;; # let evn = [("z1",VInt 0); ("x",VInt 1); ("y",VInt 2); ("z",VInt 3); ("z1",VInt 4)];; # let e1 = If (binop Lt (Var "z1") (Var "x"), binop Ne (Var "y") (Var "z"), Bool false);; val e1 : Nano.expr = If (BinaryOp (Var "z1", Lt, Var "x"), BinaryOp (Var "y", Ne, Var "z"), Bool false) # eval (evn, e1);;  : Nano.value = VBool true # let e2 = If (binop Eq (Var "z1") (Var "x"), binop Le (Var "y") (Var "z"), binop Le (Var "z") (Var "y"));; val e2 : Nano.expr = If (BinaryOp (Var "z1", Eq, Var "x"), BinaryOp (Var "y", Le, Var "z"), BinaryOp (Var "z", Le, Var "y")) # eval (evn, e2);;  : Nano.value = VBool false
Now consider the extended the types as shown below which includes the letin expressions which introduce local bindings exactly as in OCaml.
type expr = ...  Let of string * expr * expr  Letrec of string * expr * exprThe expression
Let ("x", e1, e2)
should be evaluated as the OCaml
expression let x = <e1> in <e2>.
Similarly, LetRec ("x", e1, e2)
should be evaluated as
let rec x = <e1> in <e2>.
(Since at this point, we do not support functions,
Let
and LetRec
should do the same thing.
Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# open Nano;; # let e1 = plus (Var "x") (Var "y");; val e1 : Nano.expr = BinaryOp (Var "x", Plus, Var "y") # let e2 = Let("x", Int 1, Let ("y", Int 2, e1));; val e2 : Nano.expr = Let ("x", Int 1, Let ("y", Int 2, BinaryOp (Var "x", Plus, Var "y"))) # eval ([], e2);;  : Nano.value = VInt 3 # let e3 = Let("x", Int 1, Let("y", Int 2, Let("z", e1, Let("x", plus (Var "x") (Var "z"), e1))));; val e3 : Nano.expr = Let ("x", Int 1, Let ("y", Int 2, Let ("z", BinaryOp (Var "x", Plus, Var "y"), Let ("x", BinaryOp (Var "x", Plus, Var "z"), BinaryOp (Var "x", Plus, Var "y"))))) # eval ([], e3);;  : Nano.value = VInt 6
Next, extend the evaluator so it includes the expresions corresponding to function definitions and applications.
type expr = ...  App of expr * expr  Fun of string * exprNaturally, to handle functions, you will need to extend the set of values yielded by your evaluator to include closures.
type value = ...  VClosure of env * string option * string * exprRecall that
App(e1, e2)
corresponds to the
ML expression <e1> <e2>
(i.e. applying the function <e1> to the argument
<e2>),
and Fun ("x", e)
corresponds to the OCaml function defined
fun x > <e>
(but written with different syntax in NanoML).
Functions values are represented as
Closure (evn, n, x, e)
, where evn
is the environment
at the point where that function was declared, and n
, x
,
and e
are the name, formal, and body expression of the function.
None
.
Some f
, where f
is the name of
the function (i.e. the variable bound in the letrec expression).
Extend your implementation of eval by adding the appropriate cases for the new type constructors. To start, assume the functions are not recursive. Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# open Nano;; # eval ([], Fun ("x", plus (Var "x") (Var "x")));;  : Nano.value = VClosure ([], None, "x", BinaryOp (Var "x", Plus, Var "x")) # eval ([], App (Fun ("x", plus (Var "x") (Var "x")), Int 3));;  : Nano.value = VInt 6 # let e3= Let("h", Fun( "y", plus (Var "x") (Var "y")), App (Var "f", Var "h"));; val e3 : Nano.expr = Let ("h", Fun ("y", BinaryOp (Var "x", Plus, Var "y")), App (Var "f", Var "h")) # let e2 = Let ("x", Int 100, e3);; val e2 : Nano.expr = Let ("x", Int 100, Let ("h", Fun ("y", BinaryOp (Var "x", Plus, Var "y")), App (Var "f", Var "h"))) # let e1 = Let ("f", Fun("g", Let("x", Int 0, App (Var "g", Int 2))), e2);; val e1 : Nano.expr = Let ("f", Fun ("g", Let ("x", Int 0, App (Var "g", Int 2))), Let ("x", Int 100, Let ("h", Fun ("y", BinaryOp (Var "x", Plus, Var "y")), App (Var "f", Var "h")))) # eval ([], e1);;  : Nano.value = VInt 102 # eval ([], LetRec ("f", Fun ("x", Int 0), Var "f"));;  : Nano.value = VClosure ([], Some "f", "x", Int 0)
Make the above work for recursively defined functions (declared with let rec). Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# open Nano;; # eval ([], LetRec ("fac", Fun ("n", If (eq (Var "n") (Int 0), Int 1, mul (Var "n") (App (Var "fac", minus (Var "n") (Int 1))))), App (Var "fac", Int 10)));;  : Nano.value = VInt 3628800
Extend your program to support operations on lists.
type binop = ...  Cons type expr = ...  Nil type value = ...  VNil  VPair of value * valueIn addition to the changes to the data types, add support for two NanoML functions hd and tl which do what the corresponding ML functions do.
Hint: You may choose to extend the type definitions of
expr
and/or value
; if you do, make sure to keep
all the existing constructors exactly as defined.
Once you have implemented this functionality and recompiled, you should get the following behavior at the ./nanoml.top prompt:
# open Nano;; # eval ([], cons (Int 1) (cons (Int 2) Nil));;  : Nano.value = VPair (VInt 1, VPair (VInt 2, VNil)) # eval ([], App (Var "hd", cons (Int 1) (cons (Int 2) Nil)));;  : Nano.value = VInt 1 # eval ([], App (Var "tl", cons (Int 1) (cons (Int 2) Nil)));;  : Nano.value = VPair (VInt 2, VNil)
The tests/ folder contains additional test cases. The following shell UNIX shell script
$ for i in `seq 1 14` ; do ./nanoml.byte tests/t$i.ml ; doneshould run on all of the tests in this folder:
$ ./nanoml.byte tests/t1.ml out: 45 ... $ ./nanoml.byte tests/t2.ml out: 0 ... $ ./nanoml.byte tests/t3.ml out: 2 ... $ ./nanoml.byte tests/t4.ml out: Error: Nano.NanoMLEvalError("variable not bound: p") ... $ ./nanoml.byte tests/t5.ml out: 6 ... $ ./nanoml.byte tests/t6.ml out: 102 ... $ ./nanoml.byte tests/t7.ml out: 20 ... $ ./nanoml.byte tests/t8.ml out: 55 ... $ ./nanoml.byte tests/t9.ml out: 3628800 ... $ ./nanoml.byte tests/t10.ml out: 110 ... $ ./nanoml.byte tests/t11.ml out: 55 ... $ ./nanoml.byte tests/t12.ml out: 3628800 ... $ ./nanoml.byte tests/t13.ml out: 59 ... $ ./nanoml.byte tests/t14.ml out: (1::(6::(7::(8::[]))))