(see submission instructions below)

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

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 68 of the Academic Regulations section (PDF) of the 2007-2008 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 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/NJ 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.

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 two files
misc.ml, test.ml, that you need to download.
The first four 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**. Feel free
to use any library functions that you want.

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 fourth 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 `pa3_solution/`, inside which you will
place the file:
` misc.ml`.
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>_pa3.zip` by going into
the directory ` solution ` and executing
the UNIX shell command:

` zip <LastName>_<FirstName>__pa3.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 pa3
<LastName>_<FirstName>_pa3.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: Warm-Up ` (misc.ml) `

### (a)** 10 points **

Fill in the skeleton given for `sqsum `, which uses `fold`
to get an Ocaml function ` sqsum: int list -> int ` that
takes a list of integers ` [x1;...;xn]) ` and returns the integer:
` x1^2 + ... + xn^2 `.
Your task is to fill in the appropriate values for
(1) the folding function `f` and
(2) the base case `base`.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# sqsum [];;`

- : int = 0

# sqsum [1;2;3;4] ;;

- : int = 30

# sqsum [-1;-2;-3;-4] ;;

- : int = 30

### (b)** 20 points **

Fill in the skeleton given for `pipe`, which uses `fold`
to get an Ocaml function ` sqsum: ('a -> 'a) list -> ('a -> 'a)
`. The function `pipe` takes a list of functions takes a
list of integers ` [f1;...;fn]) ` and returns a function `f`
such that for any `x`, the application `f x` returns the
result `fn(...(f2(f1 x)))`.
Again, your task is to fill in the appropriate values for
(1) the folding function `f` and
(2) the base case `base`.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# pipe [] 3;;`

- : int = 3

# pipe [(fun x-> 2*x);(fun x -> x + 3)] 3 ;;

- : int = 9

# pipe [(fun x -> x + 3);(fun x-> 2*x)] 3;;

- : int = 12

## Problem #2: Big Numbers ` (misc.ml) `

As you may have noticed, the Ocaml type ` int ` only contains values
upto a certain size. For example, entering ` 9999999999 ` results in
the message ` int constant too large `. You will now implement
functions to manipulate large numbers represented as lists of integers.
### (a)** 5 + 5 points**

Use the function ` clone ` to write a function ` padZero : int
list * int list -> int list * int list ` which takes two lists:
` ([x1,...,xn],[y1,...,ym])` and adds zeros in front to make the lists
equal. Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# padZero ([9;9],[1;0;0;2]);;`

- : int list * int list = ([0;0;9;9],[1;0;0;2])

# padZero ([1;0;0;2],[9;9]);;

- : int list * int list = ([1;0;0;2],[0;0;9;9])

Now write a function ` removeZero : int list -> int list `, that
takes a list and removes a prefix of trailing zeros.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# removeZero ([0;0;0;1;0;0;2]);;`

- : int list = [1;0;0;2]

# removeZero ([9;9]);;

- : int list = [9;9]

# removeZero ([0;0;0;0]);;

- : int list = []

### (b)** 15 points**

Suppose we use the list `[d1;d2;d3;...;dn]`, where each ` di
` is in the range [0..9], to represent the
(positive) integer `d1d2d3...dn`. For example, the list
`[9;9;9;9;9;9;9;9;9;9]` represents the integer 9999999999.
Fill out the implementation for ` bigAdd : int list * int list ->
int list `, so that it takes a pair of integer lists, where each
integer is in the range [0..9] and returns the list corresponding to the
addition of the two big integers. Again, you have to fill in the
implementation to supply the appropriate values to ` f, b, args `.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# bigAdd ([9;9],[1;0;0;2]);;`

- : int list = ([1;1;0;1])

# bigAdd ([9;9;9;9],[9;9;9]);;

- : int list = ([1;0;9;9;8])

### (c)** 10 + 10 points **

Next you will write functions to multiply two big integers. First write
a function ` mulByDigit : int list * int -> int list ` which
takes a tuple of a big integer and an (integer) digit, and returns the
big integer list which is the result of multiplying the big integer with
the digit. Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# mulByDigit ([9;9;9;9],9);;`

- : int list = [8;9;9;9;1]

Now, using the function `mulByDigit`, fill in the implementation of
`bigMul : int list * int list -> int list * int list `. Again,
you have to fill in implementations for ` f , base , args ` only.
Once you are done, you should get the following behaviour at the prompt:
`
# bigMul ([9;9;9;9],[9;9;9;9]);;`

- : int list = [9;9;9;8;0;0;0;1]

# bigMul ([9;9;9;9;9],[9;9;9;9;9]);;

- : int list = [9;9;9;9;8;0;0;0;0;1]

## Problem #3: Regular Expressions` (misc.ml) `

The function `exact_match: string -> string -> bool` takes as
input a regular expression string, and returns a function, which takes a
string, and returns true iff the string matches the regular expression
exactly. Consider the behavior of `is_uint` which is equal to
`exact_match "[0-9]+"`. It returns true for exactly those strings
that correspond to a non-empty sequence of digits, i.e. for those strings
that correspond to unsigned integers.
### (a)** 5 points **

Next fill in the skeleton using a regular expression describing
integers, to get a Ocaml function `is_int : string -> bool`, such
that `is_int s` returns true iff `s` corresponds to an integer.
An integer is defined as a sequence of at least one decimal digits preceded
by an optional minus sign.
A regular expression for such integers is `"^-?[0-9]+$"`.
For more information on Ocaml regular expressions,
see here.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# is_int "-12" ;;`

- : bool = true

# is_int "ucsd" ;;

- : bool = false

### (b)** 10 points **

Now fill in the regular expression template to get an
Ocaml function `is_sentence: string -> bool` that takes a
string `s` and returns `true` if `s` is a
sentence and `false` otherwise. A sentence is defined as a
sequence of words separated by spaces. A word is a sequence of
letters. The first word in a sentence must be capitalized and the
sentence must end with a period. No other punctuation is allowed.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# is_sentence "Ocaml is fun." ;;`

- : bool = true

# is_sentence "Mugatu." ;;

- : bool = true

# is_sentence "this is the end" ;;

- : bool = false

# is_sentence "29" ;;

- : bool = false

### (c)** 10 points **

Now fill in the regular expression templates `sign`, `num`
and `expo` to get an Ocaml function `is_float: string -> bool`
that takes a string `s` and returns `true` if `s` is a
string corresponding to a floating point number and `false` otherwise.
A floating point number is defined as an
optional `sign` which is an ` + ` or `-`,
followed by a `num` which is a decimal point with a non-empty
sequence of digits on at least one side,
followed by an optional `expo`nent which is an
` E ` or e followed by an optional sign followed by an
integer.
Once you have implemented the function, you should get the following
behavior at the Ocaml prompt:

`
# is_float "1.0" ;;`

- : bool = true

# is_float "-1." ;;

- : bool = true

# is_float "-.8" ;;

- : bool = true

# is_float "2.e-10" ;;

- : bool = true

# is_float "-3.14E10" ;;

- : bool = true

# is_float "." ;;

- : bool = false

# is_float "e12" ;;

- : bool = false

# is_float "12" ;;

- : bool = false

# is_float "-" ;;

- : bool = false