**NOTE:** To get the code provided for problem 2 to work on Windows/Mac please install ImageMagick 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.

The objective of this assignment is for you to have fun learning about recursion, recursive datatypes, and make some pretty cool pictures.All the problems require relatively little code ranging from 2 to 10 lines. If any function requires more than that, you can be sure that you need to rethink your solution.

The assignment is in the single zip file

that you need to download. After downloading to an appropriate directory, unzip it thus:

`> unzip pa2.zip`

and out come tumbling several files including

`tester.ml`

, which is a dummy tester that you will use to check your assignments before submitting,`test.ml`

, which contains some sample tests for you to start with, placeholders where you will fill in new tests,`misc.ml`

,`expr.ml`

and`art.ml`

which contains several skeleton Ocaml functions with missing bodies that you will fill in.

All but the first file contain expressions of the form:

`failwith "TBD: ..."`

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, while loops or library functions will receive **no credit** It is a good idea to start this assignment early; ML programming, while quite simple (when you know how), often seems somewhat foreign at first, particularly when it comes to recursion and list manipulation.

Your functions/programs **must** compile and/or run on a **ACS Linux** machine (e.g. `ieng6.ucsd.edu`

) as this is where your solutions will be checked. 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, will be awarded automatically, by **evaluating your functions against a given test suite**. `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 > 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 the log file contains a line WARNING: Your tests are not valid then there is a problem with one or more tests and you may not get the points for them**

If for some problem, you cannot get the code to compile, leave it as is with the `failwith ...`

with your partial solution enclosed below as a comment.

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 `tester.ml`

, but you will not be graded on this.

Alternately, inside the OCaml shell, type:

```
# #use "test.ml";;
.
.
.
val it = (...,...) : 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.

Your solutions to this assignment will be stored in separate files under a directory called `solution/`

, inside which you will place the files:

`test.ml`

`tester.ml`

`misc.ml`

`expr.ml`

`art.ml`

`art_g_sample.jpg`

`gray1.jpg`

`gray2.jpg`

`gray3.jpg`

`color1.jpg`

`color2.jpg`

`color3.jpg`

There should be **no other files in the directory**

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_pa2.zip * `

where `firstname`

and `lastname`

have your first and last names respectively.

Next, you will use the program `validate_pa2`

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

`validate_pa2 firstname_lastname_cse130_pa2.zip`

The `validate_pa2`

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_pa2`

program. **Otherwise you get a zero for the whole assignment.

If you have any trouble with this, refer to the instructions in step 1.

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 cs130f -p pa2 firstname_lastname_cse130_pa2.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.

For each problem below, in addition to writing code, you will be writing tests by filling in the templates as described below. Note that

When writing tests, do not use the same values as in the

`sampleTests`

or you will get a zero for that problem.We will run

*everyone’s*code against*everyone’s*tests. The tests will then be ranked by the maximum number of failures they induce. If one of your tests is among the top-10 failure-inducing tests, you get 25 points (in addition to the points for writing valid tests.)

We say that a function is *tail recursive* if every recursive call is a tail call whose value is immediately returned by the procedure. See these two handouts for more details on what a tail-recursive function is in Ocaml.

Without using any built-in ML functions, write a *tail-recursive* Ocaml function

`val assoc : int * string * (string * int) list -> int `

or more generally,

`val assoc : 'a * 'b * ('b * 'a) list -> 'a `

that takes a triple `(v, k, [(k1,v1);...;(kn,vn)])`

and finds the first `ki`

that equals `k`

. If such a `ki`

is found, then the function should return `vi`

, otherwise, the default value `v`

is returned.

Once you have implemented the function, you should get the following behavior at the ML prompt:

```
# assoc (-1,"william",[("ranjit",85);("william",23);("moose",44)]);;
- : int = 23
# assoc (-1,"bob",[("ranjit",85);("william",23);("moose",44)]);;
- : int = -1
```

In the file `test.ml`

write down five (5) tests for the `assoc`

by filling in the input and output expressions appropriately following the example shown above for `sampleTests`

.

Without using any built-in ML functions, **modify the skeleton** for `removeDuplicates`

to obtain a function of type

`val removeDuplicates : int list -> int list`

or more generally,

`val removeDuplicates : 'a list -> 'a list`

such that `removeDuplicates xs`

returns the list of elements of `xs`

with the duplicates, i.e. second, third, etc. occurrences, removed, and where the remaining elements appear in the same order as in `xs`

.

For this function only, you may use the library functions `List.rev`

and `List.mem`

. Once you have implemented the function, you should get the following behavior at the ML prompt:

```
# removeDuplicates [1;6;2;4;12;2;13;6;9];;
- : int list = [1;6;2;4;12;13;9]
```

In the file `test.ml`

write down five (5) tests for the `removeDuplicates`

by filling in the input and output expressions appropriately following the example shown above for `sampleTests`

.

Without using any built-in ML functions, or the `while`

or `for`

construct, write a tail-recursive ML function:

`val wwhile : (int -> int * bool) * int -> int`

or more generally,

`val wwhile : ('a -> 'a * bool) * 'a -> 'a `

such that `wwhile (f, x)`

returns `x'`

where there exist values `v_0`

,…,`v_n`

such that

`x`

is equal to`v_0`

`x'`

is equal to`v_n`

- for each
`i`

between`0`

and`n-2`

, we have`f v_i`

equals`(v_i+1, true)`

`f v_n-1`

equals`(v_n, false)`

.

Your function should be tail recursive. Once you have implemented the function, you should get the following behavior at the ML prompt:

```
# let f x = let xx = x*x*x in (xx, xx < 100);;
- val f : int -> int * bool = fn
# wwhile (f,2);;
- : int = 512
```

In the file `test.ml`

write down five (5) tests for the `wwhile`

by filling in the input and output expressions appropriately following the example shown above for `sampleTests`

.

Without using any built-in ML functions, **modify the skeleton** for `fixpoint`

to obtain a function

`val fixpoint: (int -> int) * int -> int `

or more generally,

`val fixpoint: ('a -> 'a) * 'a -> 'a `

such that `fixpoint (f, x0)`

returns the first `xi`

where

`xi`

is equal tyo`f x_i-1`

, and, furthermore,`f xi`

is equal to`xi`

Once you have implemented the function, you should get the following behavior at the ML prompt:

```
# let g x = truncate (1e6 *. cos (1e-6 *. float x));;
val f : int -> int = fn
# fixpoint (g, 0);;
- : int = 739085
# let collatz n = match n with 1 -> 1 | _ when n mod 2 = 0 -> n/2 | _ -> 3*n + 1;;
val collatz: int -> int = fn
# fixpoint (collatz, 1) ;;
- : int = 1
# fixpoint (collatz, 3) ;;
- : int = 1
# fixpoint (collatz, 48) ;;
- : int = 1
# fixpoint (collatz, 107) ;;
- : int = 1
# fixpoint (collatz, 9001) ;;
- : int = 1
```

In the file `test.ml`

write down five (5) tests for the `fixpoint`

by filling in the input and output expressions appropriately following the example shown above for `sampleTests`

.

At the end of this assignment, you should be able to produce pictures of the kind shown below. To do so, we shall devise a grammar for a certain class of expressions, design an ML datatype whose values correspond to such expressions, write code to evaluate the expressions, and then write a function that randomly generates such expressions and plots them thus producing random psychedelic art.

The expressions described by the grammar:

```
e ::= x
| y
| sin (pi*e)
| cos (pi*e)
| ((e + e)/2)
| e * e
| (e<e ? e : e)
```

where pi stands for the constant 3.142, are functions over the variables x,y, which are guaranteed to produce a value in the range [-1,1] when x and y are in that range. We can represent expressions of this grammar in ML using values of the following datatype:

```
type expr = VarX
| VarY
| Sine of expr
| Cosine of expr
| Average of expr * expr
| Times of expr * expr
| Thresh of expr * expr * expr * expr
```

First, write a function

`val exprToString : expr -> string`

to enable the printing of expressions. Once you have implemented the function, you should get the following behavior at the ML prompt:

```
# let sampleExpr1 = Thresh(VarX,VarY,VarX,(Times(Sine(VarX),Cosine(Average(VarX,VarY)))));;
- : expr = ...
# exprToString sampleExpr1
- : string = "(x<y?x:sin(pi*x)*cos(pi*((x+y)/2)))"
```

Next, write a function

`val eval : expr * float * float -> float`

such that `eval (e, vx, vy)`

returns the result of evaluating the expression `e`

at the point `(vx, vy)`

that is, evaluating the result of `e`

when `VarX`

has the value `vx`

and `VarY`

has the value `vy`

. You should use Ocaml functions like, `sin`

, and `cos`

to build your evaluator. Recall that `Sine(VarX)`

corresponds to the expression `sin(pi*x)`

Once you have implemented the function, you should get the following behavior at the ML prompt:

```
# eval (Sine(Average(VarX,VarY)),0.5,-0.5);;
- : float = 0.0
# eval (Sine(Average(VarX,VarY)),0.3,0.3);;
- : float = 0.809016994375
# eval (sampleExpr,0.5,0.2);;
- : float = 0.118612572815
```

At the ML prompt, enter:

`# use "art.ml";; emitGrayscale (eval_fn sampleExpr, 150, "sample") ;;`

to generate the grayscale image `art_g_sample.jpg`

in your working directory. To receive full credit, this image must look like the leftmost grayscale image displayed above. Note that this requires your implementation `eval`

to work correctly. A message `Uncaught exception ...`

is an indication that your `eval`

is returning a value outside the valid range `[-1.0,1.0]`

.

Next, you must fill in an implementation for the function

`val build: int * (int * int -> int) -> expr`

The function `build`

is called with the pair of arguments `(rand, depth)`

.

`rand`

is a random number generator of type`int * int -> int`

. Each call`rand (i,j)`

returns a random integer between`i`

and`j`

inclusive. Use this function to randomly select operators when composing subexpressions to build up larger expressions.`depth`

is a a maximum nesting dept; a random expression of depth`d`

is built by randomly composing sub-expressions of depth`d-1`

and the only expressions of depth`0`

are`VarX`

and`VarY`

.

With this in place you can generate random art using the functions

```
val doRandomGray : int * int * int -> unit
val doRandomColor : int * int * int -> unit
```

Each function takes as a parameter a triple `(depth, seed1, seed2)`

where `depth`

is the depth of the expression to be generated and `seed1`

, `seed2`

are two seeds for the random number generator. The functions generate JPEG files called `art_g_<depth>_<seed1>_<seed2>.jpg`

and `art_c_<depth>_<seed1>_<seed2>.jpg`

respectively. The first is a gray scale image, built by mapping out a single randomly generated expression over the plane, and the second is a color image built using three functions for the intensities of red, green and blue.

Play around with how you generate the expressions, using the tips below.

- Depths of 8-12 produce interesting pictures, but play around!
- Make sure your expressions don’t get
*cut-off*early with`VarX`

,`VarY`

as small expressions give simple pictures. - Play around to bias the generation towards more interesting operators.

Name your best three color files `color1.jpg`

, `color2.jpg`

, `color3.jpg`

and save their parameters, i.e. the depth and the seeds in the bodies of `c1`

, `c2`

, `c3`

respectively. Name your best three gray files `gray1.jpg`

, `gray2.jpg`

, `gray3.jpg`

and save their parameters in the bodies of `g1`

, `g2`

, `g3`

.

Finally, add **two** new operators to the grammar, i.e. to the datatype, by introducing two new datatype constructors, and adding the corresponding cases to `exprToString`

, `eval`

, and `build`

. The only requirements are that the operators must return values in the range `[-1.0,1.0]`

if their arguments (ie `VarX`

and `VarY`

) are in that range, and that one of the operators take **three** arguments, i.e. one of the datatype constructors is of the form: `C of expr * expr * expr`

You can include images generated with these new operators when choosing your best images for part (c).

The creators of the **best five** images, will get extra credit. Be creative!