# Project 3

Due 11:59pm Thursday, March 28, 2013

## Introduction

In this project, you will gain experience writing code in OCaml. The focus of this project is getting used to OCaml's syntax, using recursion to work with lists, and using data types. You will also learn a little about programming language design.

## Project files

• Code skeleton (all files, including tests, in p3.zip)
• Files for command line submission (see "How to Submit" for usage)
• Public tests: copy your *.ml into the p3_public_tests directory and run the tests.

## Part 1: List Exercises

Write your solutions to this part in the file warmup.ml.

Implement the following functions in OCaml. Do not use any functions in the List or Array modules, i.e., write every function from scratch using just list notation [...], ::, and pattern matching. You should also not use the list concatenation operator @ from Pervasives. You are allowed to write separate helper functions if you like.

• Write a function prod l : int list -> int that returns the product of the elements of l. The function prod should return 1 if the list is empty.
• Write a function add_tail l e : 'a list -> 'a -> 'a list that takes a list l and a single element e and returns a new list where e is appended to the back of l. For example, add_tail [1;2] 3 = [1;2;3].
• Write a function fill x n : 'a -> int -> 'a list that returns a list containing n copies of x. For example, fill 42 3 returns [42; 42; 42]. If n is less than or equal to 0, return the empty list.
• Write a function rindex l e : 'a list -> 'a -> int that takes a list and a single element and returns the position of the last occurrence of that element in the list (indexed by zero). You should return -1 if the element is not in the list. Use structural equality (the = operator, not ==) for checking membership.
• Write a function even_elts l : 'a list -> 'a list that takes a list and returns a new list containing the 0th, 2nd, 4th, etc elements of l. For example, even_elts ['a';'b';'c';'d';'e'] should return ['a';'c';'e'].
• Write a function sublist n m l : int -> int -> 'a list -> 'a list that returns a new list containing the elements of l starting with element n, inclusive, and ending with element m, inclusive. For example, sublist 2 4 ['a'; 'b'; 'c'; 'd'; 'e'; 'f'] should return ['c'; 'd'; 'e']. Your function may do anything if n>m or if n or m are out of range for the list.
• Write a function rotate n l : int -> 'a list -> 'a list that returns a new list containing the same elements as l, "rotated" n times to the right. For example,
• rotate 0 [1;2;3;4] should return [1;2;3;4]
• rotate 1 [1;2;3;4] should return [4;1;2;3]
• rotate 2 [1;2;3;4] should return [3;4;1;2]
• rotate 3 [1;2;3;4] should return [2;3;4;1]
• rotate 4 [1;2;3;4] should return [1;2;3;4]
• etc.
The behavior of rotate for n less than 0 is the same is for n equal to 0.
• Write a function unzip l : ('a*'b) list -> ('a list)*('b list) that, given a list of pairs, returns a pair of lists with the elements in the same order. For example, unzip [(1, 2); (3, 4)] = ([1; 3], [2;4]).
• Write a function app_int f m n : (int->'a)->int->int->'a list that returns the list [f m; f (m+1); ...; f n]. It should return the empty list if n < m.

## Part 2: Regular Expressions, again!

Write your solutions to this part in the file regexp.ml. From here on out in the project, you can freely use any part of the OCaml standard library.

In Project 2, you developed code to implement regular expressions as NFAs and DFAs. One interesting design choice in that project was the way regular expressions were represented, which was as a set of classes REEpsilon, REConst, REStar, REUnion, and REConcat. Consider instead representing regular expressions in OCaml using the following data type:

```type regexp =
REEpsilon
| REConst of char
| REStar of regexp
| REUnion of regexp * regexp
| REConcat of regexp * regexp
```
For example, here is a table of regular expressions, and their representation in this data type:
 Regexp OCaml code empty string let r1 = REEpsilon c let r2 = REConst 'c' a|b let r3 = REUnion (REConst 'a', REConst 'b') abc let r4 = REConcat(REConst 'a', (REConcat(REConst 'b', REConst 'c'))) a*b let r5 = REConcat(REStar(REConst 'a'), REConst 'b')

For this part of the project, implement the functions check(e) and trans(e) again (yes, you read that right!). These functions should have the following types:

• check : regexp -> bool
• trans : regexp -> (char * regexp) list

The list of pairs returned by trans should be unique, i.e., it should not contain duplicates.

After you're done implementing these functions in OCaml, recall your experience writing them in Ruby. Which language were they easier to write in? Do you prefer having the code for check and trans grouped in one unit, as they are in OCaml, or spread among different classes, as they were in Ruby? Did the OCaml type system make it easier or more difficult to implement them? You don't need to submit your answers to these questions, but please do consider them.

## Part 3: Arithmetic Expressions

Write your solutions to this part in the file arith.ml.

In this part of the project, you will work with a data type that represents abstract syntax trees for arithmetic expressions that may contain variables:

```type expr =
Int of int
| Negate of expr
| Plus of expr * expr
| Minus of expr * expr
| Mult of expr * expr
| Var of string
```
For example, here are several expressions and their representation in OCaml using the above data type:
 Expression OCaml code 42 let e1 = Int 42 42 + 13 let e2 = Plus(Int 42, Int 13) 3 * (2 + 1) let e3 = Mult(Int 3, Plus(Int 2, Int 1)) 2 - (-4) let e4 = Minus(Int 2, Negate(Int 4)) x + y let e5 = Plus(Var "x", Var "y") foo * (3 + baz) let e6 = Mult(Var "foo", Plus(Int 3, Var "baz"))

If an arithmetic expression has a variable, then we can only decide what an expression "means" if we know the values of its variables. We will use a type

```  type assignment = (string * int) list
```
to represent an assignment of variable names (which are arbitrary strings) to integers. Here if an assignment contains the pair (x,n), then the assignment gives the variable named x the value n. The type assignment is a kind of associative list, and there are a number of functions for working with such lists available in the OCaml standard library, including List.assoc, List.mem_assoc, and others. See the OCaml library documentation for more information.
• Write a function no_mult : expr -> bool that returns true if the expression contains no occurrence of a value constructed with Mult, and false otherwise. For example, no_mult should return true for e1, e2, e4, and e5, and false for e3 and e6.
• Write a function vars_of : expr -> string list that returns a list containing the names of variables used in the expression. For example, vars_of e5 should return ["x"; "y"], and vars_of e2 should return []. The function vars_of should return a list in which each variable appears at most once, i.e., you should remove duplicates.
• Write a function eval : assignment -> expr -> int that returns the value an expression evaluates to. For example, here are some results of eval:
• eval [] e2 returns 55
• eval [] e4 returns 6
• eval [("x", 3); ("y", 4)] e5 returns 7
• eval [("foo", 10)] e6 aborts with an error
• eval [("foo", 10); ("x", 3); ("baz", 2)] e6 returns 50
If eval a e is called such that a variable in e does not occur in a, your program should use raise Not_found to throw an exception. In the case the same variable name appears multiple times in the assignment given to eval, your function should use the first or left-most assignment of the variable. This rule also applies to the (string * expr) list in subst (next).
• Write a function subst : expr -> (string * expr) list -> expr such that subst e s returns a new expression that is identical to e, except variables occurring in e have been replaced according to s. Here a pair ("x", e) occurring in s indicates that Var "x" should be replaced by the expression e. For example, subst e6 [("foo", Int 4)] should return Mult(Int 4, Plus(Int 3, Var "baz")). Note that your subst function should perform just one "level" of substitution. For example, subst (Plus(Var "v", Int 3)) [("v", Negate (Var "v"))] should return Plus(Negate (Var "v"), Int 3).

## Part 4: Language of Commands

Write your solution to this part in the file cmd.ml.

Finally, consider embedding arithmetic expressions in a simple programming language consisting of commands:

```type cmd =
Skip
| Assign of string * expr
| Seq of cmd * cmd
| IfNonZero of expr * cmd * cmd
| WhileNonZero of expr * cmd
```

Since commands work with variables, we always evaluate commands with respect to some assignment (the same type as in Part 3), and executing a command produces a new assignment. For this last part of the project, you must write a function exec : assignment -> cmd -> assignment that, given the current assignment of variables to values, executes the command and returns a new assignment of variables to values. Calling exec a c should do the following, based on the command c:

• Skip does nothing, returning a.
• Assign("x",e) evaluates e under the assignment a, and then returns a new assignment that is the same as a, except now "x" is mapped to the result of the evaluation.
• Seq(c1, c2) executes c1 under assignment a, producing a new assignment a1; executes c2 under assignment a1, producing a new assignment a2; and then returns a2.
• IfNonZero(e1,c1,c2) evaluates e1 under assignment a. If evaluation returns a non-zero value, then c1 is executed under assignment a, and otherwise c2 is executed under assignment a.
• WhileNonZero(e,c) evaluates e under assignment a. If that returns zero, assignment a is returned. Otherwise, c is executed once under assignment a, producing a new assignment a'. Then WhileNonZero(e,c) is executed under assignment a'.

Hint: Above we've basically just written the exec function for you, except we used English instead of OCaml. So all you need to do is translate that into OCaml. But you should also try to understand why the execution cases above make sense. Think about the following questions: If we added a form Block of cmd list, where the list contained many commands in sequence, how would you execute a Block? What about adding an Unless conditional form? Or a For loop, or a RepeatUntil loop? What other language features would be easy to add to this language of commands?

## Hints and Tips

• Start this project early! For many students, learning OCaml requires quite a leap in the way they approach programming, and you need to give yourself enough time to make that leap.
• When debugging type inference errors, consider adding type annotations on the function arguments to make more meaningful error messages. For example, suppose you have written
```let fill x n =
...
```
and the OCaml type checker is complaining that you have a type error in your code. Then we would suggest you rewrite the first part to indicate the expected types:
```let fill (x:'a) (n:int) : 'a list =
...
```
The type inference engine will probably give you more meaningful error messages now that it knows what you intend.
• When testing Part 4, we will plug in a correct arith.ml. While this should help make grading equitable, it also means you need to be extra careful not to change any of the interfaces we supply you with, since we will be relying on those in grading.

## Submission

You may either submit over the web or under command line interface.

### Submitting over the web

Put your files (warmup.ml, regexp.ml, arith.ml, cmd.ml) in a zip archive. Don't put things under a directory but on the top level.

Submit your archive directly to the submit server by clicking on the submit link in the column "web submission".

Next, use the submit dialog to submit your schedule.rb file directly.

Select your file using the "Browse" button, then press the "Submit project!" button.

### Submitting in command line interface

Make a directory and put your files in it. Download .submit and submit.jar in Project Files to the same directory. Then run the following command under that directory:

java -jar submit.jar

The first time you submit this way you will be asked to enter your directory ID and password. All files in the directory (and its subdirectories) will then be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

Successful submission # received for project 3