CSE 130 - Programming Assignment #4


60 points

Must be turned in no later than 4:59:59 PM on 02/16/2007
(see submission instructions below)

(click your browser's refresh button to ensure that you have the most recent version)

Note: See this for instructions on starting OCaml in the ACS lab machines. To download and install OCaml version 3.09.03 on your home machines see the instructions here. Remember that this is only to enable you to play with the assignment at home: the final version turned in must work on the ACS Linux machines.

Integrity of Scholarship

University rules on integrity of scholarship will be strictly enforced. By completing this assignment, you implicitly agree to abide by the UCSD Policy on Integrity of Scholarship described beginning on page 62 of the Academic Regulations section (PDF) of the 2002-2003 General Catalog, in particular, "all academic work will be done by the student to whom it is assigned, without unauthorized aid of any kind."

You are expected to do your own work on this assignment; there are no group projects in this course. You may (and are encouraged to) engage in general discussions with your classmates regarding the assignment, but specific details of a solution, including the solution itself, must always be your own work. Incidents that violate the University's rules on integrity of scholarship will be taken seriously: In addition to receiving a zero (0) on the assignment, students may also face other penalties, up to and including, expulsion from the University. Should you have any doubt about the moral and/or ethical implications of an activity associated with the completion of this assignment, please see the instructors.

Code Documentation and General Requirements

Code for all programming assignments should be well documented. A working program with no comments will receive only partial credit. Documentation entails writing a description of each function/method, class/structure, as well as comments throughout the code to explain the program logic. Comments in OCaml are enclosed within (* *), and may be nested. It is understood that some of the exercises in this programming assignment require extremely little code and will not require extensive comments.

While few programming assignments pretend to mimic the "real" world, they may, nevertheless, contain some of the ambiguity that exists outside the classroom. If, for example, an assignment is amenable to differing interpretations, such that more than one algorithm may implement a correct solution to the assignment, it is incumbent upon the programmer to document not only the functionality of the algorithm (and more broadly his/her interpretation of the program requirements), but to articulate clearly the reasoning behind a particular choice of solution.

Assignment Overview

The overall objective of this assignment is to expose you to some advanced features of OCaml such as higher-order functions, abstract datatypes and modules, as well as to fully understand the notion of scoping, binding, environments and closures, by implementing a mini-ML interpreter. Again, no individual function requires more than 10-15 lines, so if you're answer is longer, you can be sure that you need to rethink your solution. The assignment is spread over three files misc.ml, ml.ml, test.ml, that you need to download. The first two files contain several skeleton OCaml functions, with missing bodies, i.e. expressions, which currently contain the text raise Failure "to be written" . Your task is to replace the text in those files with the the appropriate OCaml code for each of those expressions.

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.

Assignment Testing and Evaluation

Your functions/programs must compile and/or run on a Linux ACS machine (e.g. ieng6.ucsd.edu , as this is where the verification of your solutions will occur. While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission. You should test your code in the directories from which the zip files (see below) will be created, as this will approximate the environment used for grading the assignment.

Most of the points, except those for comments and style, will be awarded automatically, by evaluating your functions against a given test suite. The file test.ml contains a very small suite of tests which gives you a flavor of of these tests. At any stage, by typing at the UNIX shell :

ocaml test.ml | grep "130>>" > log
you will get a report on how your code stacks up against the simple tests.

The last line of the file log must contain the word "Compiled" otherwise you get a zero for the whole assignment. If for some problem, you cannot get the code to compile, leave it as is with the raise ..., with your partial solution enclosed below as a comment. There will be no exceptions to this rule. The second last line of the log file will contain your overall score, and the other lines will give you a readout for each test. You are encouraged to try to understand the code in test.ml, and subsequently devise your own tests and add them to test.ml, but you will not be graded on this.

Alternately, inside the OCaml shell, type (user input is in red):

# #use "test.ml";;
- : int * int = (...,...)
and it should return a pair of integers, reflecting your score and the max possible score on the sample tests. If instead an error message appears, your code will receive a zero.

Submission Instructions

1. Create the zip file for submission

Your solutions to this assignment will be stored in separate files under a directory called pa4_solution/, inside which you will place the files: misc.ml, ml.ml . The two files listed above are the versions of the corresponding supplied file that you will have modified. There should be no other files in the directory.

After creating and populating the directory as described above, create a zip file called <LastName>_<FirstName>_pa4.zip by going into the directory solution and executing the UNIX shell command:

zip <LastName>_<FirstName>_pa4.zip *

2. Submit the zip file via the turnin program

Once you've 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 <LastName>_<FirstName>_pa4.zip

The turnin program 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 tar file. See the ACS Web page on turnin for more information on the operation of the program.

Problem #1: ML-nano (ml.ml)

In this problem, you will implement an interpreter for a small fragment of ML.

(a) 15 points

    type binop = Plus | Minus | Mul | Div 

    type expr = Const of int 		
	| Var of string                 
	| Bin of expr * binop * expr    
	| IfZero of expr * expr * expr 

    type value = Int of int		
    type env = (string * value) list
First consider the types described above: binop, expr are used to capture simple ML expressions. Each expression is either an integer constant, a variable, a binary operator applied to two sub-expressions or an "ifzero-then-else" expression. The last case IfZero(e1,e2,e3) evaluates to e2 if e1 evaluates to 0 and to e3 otherwise. A value is an integer, and an environment is a list of pairs of variable names and values. Use listAssoc to write a function 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. Using this function, write a function eval : env * expr -> value that when called with the pair (evn,e) evaluates an ML-nano expression e of the above type, in the environment evn , and raises an exception MLFailure ("variable not bound: x") if the expression contains an unbound variable. In particular, notice that there is a declaration exception MLFailure of string at the top of the ml.ml file. This declares an exception called MLFailure that can be instantiated with a string parameter. You can raise this exception, passing it a string s with the following instruction: raise (MLFailure s). Once you have implemented the function, you should get the following behavior at the OCaml prompt:

# let evn =[("z1",Int 0);("x",Int 1);("y",Int 2);("z",Int 3);("z1",Int 4)];;
- : = ... ...
# let e1 =Bin(Bin(Var "x",Plus,Var "y"), Minus, Bin(Var "z",Plus,Var "z1"));;
- : = ... ...
# eval (evn,e1);;
- : value = Int 0
# eval (evn,IfZero(e1,Var "y",Var "x"));;
- : value = Int 2
# eval (evn,IfZero(Var "x",Var "y",Var "p"));;
Exception: MLFailure "Variable not bound: p".

(b) 15 points

    type expr = ...
	| Let of binding * expr   
    and binding = Val of string * expr 
Now consider the extended the types as shown above to include "let-in-end" expressions that introduce local bindings exactly as in OCaml. Extend your function eval by filling in the implementation for addBind : env * binding -> env which takes an environment and a binding and returns the environment resulting from adding the new binding to the old environment. Using the function addBind extend eval so that it handles the Let (b,e) which should be evaluated as the ML expression let b1 in e . When you are done, you should see the following at the OCaml prompt.

# let e1 = Bin(Var "x",Plus,Var "y");;
val e1 = ... : ...
# let b1 = Val("x",Const 1);;
val b1 = ... : ...
# let b2 = Val("y",Const 2);;
val b2 = ... : ...
# let b3 = Val("z",e1);;
val b3 = ... : ...
# let b4 = Val("x",Bin(Var "x",Plus,Var "z"));;
val b4 = ... : ...
# let e2 = Let(b1,Let(b2,Let(b3,Let(b4,e1))));;
val b5 = ... : ...
# eval ([],e2);;
- : value = Int 6

(c) 15 points

    type expr = ...
		| App of expr * expr 
    and binding = Val of string * expr
	        | Fun of string * string * expr
    type value = Int of int
		   | Closure of (env * string * string * expr)
We now extend the above types so that there is an expression for function application: App(e1,e2) corresponds to applying e2 to the function e1 , we allow function declarations via the binding Fun (f,x,e) where f,x,e are respectively the function name, the formal parameter and body-expression of the function. For now, assume the function is not recursive -- i.e. there is no application of f inside its body. However, functions do have values represented by the Closure (evn,f,x,e) where evn is the environment at the point where that function was declared, and f,x,e are name, formal and body expression of the function. Extend your implementation of eval,addBind by adding the appropriate cases for the new type constructors. When you are done, you should get the following at the OCaml prompt:

# let b1 = Fun("f","g",Let(Val ("x", Const 0),App(Var "g", Const 2)));;
val b1 = ...
# let b2 = Val("x", Const 100);;
val b2 = ...
# let b3 = Fun("h","y",Bin(Var "x", Plus, Var "y"));;
val b3 = ...
# eval (exec ([],[b1;b2;b3]), App(Var "f", Var "h"));;
val it = Int 102

(d) 15 points

Make the above work for recursively defined functions. When you are done, you should see the following at the OCaml prompt.

# let bfac = Fun("fac","n",
IfZero(Var "n",
Const 1,
Bin(Var "n",Mul,App(Var "fac",Bin(Var "n",Minus,Const 1)))));;

val bfac = ...
# eval (exec ([],[bfac]), App(Var "fac", Const 10));;
val it = Int 3628800