Programming Assignment #4 (200 Points)

Due: Fri, Feb 21, 5:00pm

The overall objectives of this assignment are:

to get a taste of commonly-used lexing and parsing tools that are used to implement the front-ends of programming languages; and
to fully understand the notion of scoping, binding, environments, and closures, by implementing an interpreter for a subset of ML.

Again, no individual function (or case within a match expression) requires more than 15-25 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

% make

to 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 clean

should 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 Material

The following sample lexers, parsers, interpreters may be helpful for reference as you work through this assignment.

Submission Instructions

1. Create zip file

Once you are finished, you must submit only the following three files:

nano.ml
nanoLex.mll
nanoParse.mly

Create a directory called solution/ and copy these three files into it.

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.mly

where firstname and lastname have your first and last names respectively.

2. Validate the zip file

Next, you will use the program validate_pa4 program to determine whether your zip file’s structure is well-formed. Do this by executing the UNIX shell command:

% validate_pa4 firstname_lastname_cse130_pa4.zip

The validate_pa4 program will output OK if your zip file is well-formed 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 file

Once 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.zip

turnin 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 Overview

In 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 Expressions

The 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
  | Nil

The 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 Values

NanoML 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) list

Intuitively, 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:

Closure (env, Some "f", "x", e) represents a function named "f" (for recursive functions) with argument "x" and body-expression e that was defined in an environment env.
Closure (env, None, "x", e) represents an anonymous (hence, non-recursive) function with argument "x" and body-expression e that was defined in an environment env.

The environment itself is a value of type env which is a phone-book represented as a list of string * value pairs that maps each bound name to its value.

Problem #1:
NanoML Lexer (`nanoLex.mll`) and Parser (`nanoParse.mly`)

The goal of this problem is to write a lexer and parser for NanoML using the ocamllex and ocamlyacc tools. In each subproblem, we will increase the complexity of the expressions parsed by your implementation. As before, we will use different syntax for NanoML that differs from the corresponding constructs in OCaml.

(A) 15 points

We will begin by making our parser recognize some of the simplest NanoML expressions: constants and variables.

Begin with nanoParse.mly and define tokens TRUE, FALSE, and Id. Note that a token Num is already defined. An Id token should have a single string argument, which holds the name of the variable (identifier) represented by the token.

Next, add rules to nanoLex.mll. A Num constant is a sequence of one or more digits. An Id is a letter (capital or lowercase) followed by zero or more letters or digits. The strings "true" and "false" should return the corresponding tokens TRUE and FALSE.

Finally, add a rule to nanoLex.mll to ignore whitespace which includes space, newline \n, carriage return \r, and tab \t.

Once you have implemented this functionality, you should get the following behavior. Note: In the following, $ denotes the UNIX shell prompt, and # is a nanoml.top prompt.

$ make
...

You should now (hopefully) have in your directory a file called nanoml.top, which is an OCaml shell that is pre-loaded with the modules corresponding to your NanoML implementation.

$ ./nanoml.top
NanoML 

$ ./nanoml.top 
        Objective Caml version 3.12.0

# NanoLex.token (Lexing.from_string "true");;
- : NanoParse.token = NanoParse.TRUE 

# Main.token_list_of_string "true false 12345 foo bar baz";;
- : NanoParse.token list =
      [NanoParse.TRUE; NanoParse.FALSE;
       NanoParse.Num 12345; NanoParse.Id "foo";
       NanoParse.Id "bar"; NanoParse.Id "baz"]

Now return to nanoParse.mly. Add rules to the parser so that true, false, integers, and identifiers are parsed into expressions of type Nano.expr as described above and shown in nano.ml.

Once you have implemented this functionality, you should get the following behavior (recall $ is the UNIX shell and # the OCaml prompt.)

$ make

(* hopefully this succeeds without errors. *)

$ ./nanoml.top
NanoML 

$ ./nanoml.top 
        Objective Caml version 3.12.0

# NanoParse.prog NanoLex.token (Lexing.from_string "true");;
- : Nano.expr = Nano.Bool true

# NanoParse.prog NanoLex.token (Lexing.from_string "false");;
- : Nano.expr = Nano.Bool false

# NanoParse.prog NanoLex.token (Lexing.from_string "   \n123");;
- : Nano.expr = Nano.Int 123

# NanoParse.prog NanoLex.token (Lexing.from_string "\rfoo");;
- : Nano.expr = Nano.Var "foo"

(B) 15 points

Add the following tokens to the lexer and parser:

String Token
let LET

rec REC

= EQ

in IN

function FUN

if IF

else ELSE

{ LBRACE

} RBRACE

( LPAREN

) RPAREN

Let-bindings (non-recursive and recursive), functions, and if-expressions should be parsed as expressions Nano.Let, Nano.LetRec, Nano.Fun, and Nano.If (of type Nano.expr).

That is,

a let-expression should have the form let <id> = <expr> in <expr>
a letrec-expression should have the form let rec <id> = <expr> in <expr>
a function expression should have the form function (<id>) { <expr> }
an if-expression should have the form if (<expr>) { <expr> } else { <expr> }

where <id> denotes any identifier from part (a), and <expr> denotes any expression form from all parts of this problem.

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")

(C) 15 points

Add the following tokens to the lexer and parser:

String Token
+ PLUS

- MINUS

* MUL

/ DIV

< LE LT

<= LT LE

!= 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)) { (1-z) } 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))

(D) 10 points

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")))))))

(E) 15 points

Add the following tokens to the lexer and parser:

String Token
[ ~~LBRACE~~ LBRACK

] ~~RBRACE~~ RBRACK

; 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))))

(F) 0 points

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

refactoring the syntax grammar to remove ambiguities and
declaring precedence and associativity rules to decide how to deal with any remaining ambiguities.

We won’t go into any of this trouble for this class, so we’ll just stick to our naive parser.

Problem #2:
NanoML Interpreter (`nano.ml`)

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 pre-loaded 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

(A) 25 points

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) list

Here, binop and expr are used to represent simple NanoML expressions.

An expression is either an integer constant, a variable, or a binary operator applied to two sub-expressions.
A value is an integer, and an environment is a list of pairs of variable names and values.

Use listAssoc to write an OCaml function

val lookup: string * env -> value

that 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 -> value

that 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".

(B) 25 points

Next, add support for the binary operators:

type binop = Plus | Minus | Mul | Div
           | Eq | Ne | Lt | Le | And | Or

This will require using the new kind of value, VBool:

type value = VInt of int
           | VBool of bool

The 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

(C) 25 points

Now consider the extended the types as shown below which includes the let-in expressions which introduce local bindings exactly as in OCaml.

type expr = ...
  | Let of string * expr * expr   
  | Letrec of string * expr * expr

The 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

(D) 25 points

Next, extend the evaluator so it includes the expresions corresponding to function definitions and applications.

type expr = ...
  | App of expr * expr 
  | Fun of string * expr

Naturally, 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 * expr

Recall 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.

If the function is anonymous or declared in a let-binding, the name component of the closure tuple should be None.
If the function is declared in a let-rec binding expression, then the name of the function should be Some f, where f is the name of the function (i.e. the variable bound in the let-rec 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)

(E) 30 points

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

(F — EXTRA CREDIT) 30 points

Extend your program to support operations on lists.

type binop = ...  | Cons

type expr = ...  | Nil

type value = ...  | VNil | VPair of value * value

In 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)

Additional Tests

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 ; done

should 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::[]))))

Programming Assignment #4 (200 Points)

Due: Fri, Feb 21, 5:00pm

Reference Material

Submission Instructions

1. Create zip file

2. Validate the zip file

3. Submit the zip file

NanoML Data Structures and Overview

NanoML Expressions

NanoML Values

Problem #1: NanoML Lexer (nanoLex.mll) and Parser (nanoParse.mly)

(A) 15 points

(B) 15 points

(C) 15 points

(D) 10 points

(E) 15 points

(F) 0 points

Problem #2: NanoML Interpreter (nano.ml)

(A) 25 points

(B) 25 points

(C) 25 points

(D) 25 points

(E) 30 points

(F — EXTRA CREDIT) 30 points

Additional Tests

Problem #1:
NanoML Lexer (`nanoLex.mll`) and Parser (`nanoParse.mly`)

Problem #2:
NanoML Interpreter (`nano.ml`)