Assignment 6: Static Types II
---

This is a **pair or solo Gradescope assignment**—you will submit 2 OCaml files (`a6.ml` and `a6test.ml`) and a README on Gradescope.

:::info
Recall that assignments, if completed as a pair, must be completed and submitted **together** rather than dividing work. See the syllabus for more.
:::

In this assignment, you will define OCaml functions (potentially with additional helper functions). Except where otherwise noted, you may use functions in OCaml’s library.

:::warning
For this assignment, I encourage you to reference any OCaml language documentation, the [free online OCaml textbook](https://cs3110.github.io/textbook/cover.html), and the class notes.
:::

Parts 1 & 2 (problems 1-4) cover material that is ==in scope for Quiz 2==.

Part 3 covers material (Streams) that is not in scope until Quiz 3.

# **Change Log**

I will avoid making changes to the assignment after it is posted, but any necessary changes will be added here:

# Setup

### Attribution

Part of this assignment are adapted from a [CS341](https://sites.google.com/cs.washington.edu/cse341autumn2024) assignment from the University of Washington.

### Stencil code

I've provided the following [starter code](https://drive.google.com/file/d/1RcHh8Qxlnm4MhJr2j0Waqr03XQDyv5N3/view?usp=sharing) (requires Wellesley access). Files you should edit are in green:

:::success
- `a6.ml`, where you should implement the required functions and any helper functions you'd like.
- `a6test.ml`, where you should write tests for each function.
:::
:::warning
- `a6.mli`, the interface (function type definitions) you should complete. Read, but do not edit, this file.
- `a6types.ml`, provided type definitions. Read, but do not edit, this file.
- `dune`, `dune-project` setup files so that you can test the project using `dune test`. Don't worry about reading or editing these, unless you are curious.
:::

## Setup

As with earlier OCaml assignments, navigate to the `a6` stencil directory before running `dune test`.

I suggest the following setup:

1. Download the stencil code and move it to your preferred location for CS251 work.
2. In VSCode, open a new window with `File > Open Folder...`. Select the `a6` stencil directory. You will then see all the files in the directory in the left-side navigation panel.
3. In VSCode, open a new terminal with `Terminal > New Terminal`. This will default to opening a terminal where the *working directory* is your `a6` stencil directory. From there, you can run `dune test`.
4. Additionally, you can hover over the top bar of the terminal to select an option to open a second terminal window. From there, you can run `utop` in order to interactively check program outputs in addition to tests.

### Before you submit

Make sure that you can run `dune test` from your `a6` directory without error. Do not modify `a6types.ml` and do not turn it in. Make sure you are able to see results from the Gradescope autograder.

# **Problems**

:::success
For each function, you should write your own tests in `a6test.ml` using the inline test style we have been using in class. If you are unsure about the expected result for specific inputs, please post a question on Zulip.
:::

# Part 1: Warmup: more functional OCaml

## **Problem 1**

Start your `README.txt` or `README.md` file and answer this question there.

:::success
Without using `utop` or the OCaml compiler, determine whether the following functions each type-check.

If they do type-check, provide the type of the function. If they do not type check, describe the specific type constraints that result in a contradiction. This should be more detailed than what the OCaml compiler would give you. You may do this by annotating the code with comments or by referencing line numbers.

(You may use `utop` to check your answer after completing the above exercise.)
:::

(* Function 1 *)
let rec f x =
  match x with
  | [] -> 0
  | h::t -> h::(f t)

(* Function 2 *)
let rec g a b c = g (a, b, c)

(* Function 3 *)
let rec h (a, b) = h (b, a)

## **Problem 2**

A [natural number](https://en.wikipedia.org/wiki/Natural_number) can be represented with the following recursive variant type in OCaml (as in `a6types.ml`):

type nat =
| Zero
| Succ of nat

That is, a natural number is either 0, or it is the successor of some other natural number.

:::success
Write the following functions using `nat`s:

- `add` should take two nats and produce a nat representing their sum
- `to_int` should take a `nat` and produce the equivalent `int`. For example, `to_int Zero` should produce `0` and `to_int (Succ (Succ Zero))` should produce `2`
- `from_int` should take an `int` and produce the equivalent `nat`. If the int is negative, raise the defined `NegativeInput` exception.
:::

:::warning
**Important Note**: Your implementations of all three of these functions **MUST** be *tail-recursive*. The autograder will test your code on very large inputs, so if your implementation is not tail-recursive, the tests will crash due to stack overflow. For example, `to_int (add (from_int 123456789) (from_int 123456789))` should produce `246913578` without error.
:::

## **Problem 3**

:::success
Write a function `sequence` that takes 3 `int` arguments called `spacing`, `low`, and `high`. It should return an `int list` of numbers from `low` to `high` (possibly including `high`) separated by `spacing` in sorted order. Assume `spacing` is positive.
:::

See the provided tests for a few examples.

The sample solution is 5 lines.

## **Problem 4**

:::success
Write a function `list_nth_mod` that takes a list `xs` and an `int` called `n`.
- If `n` is negative, you should raise a `NegativeInput` exception.
- If the list is empty, you should raise an `EmptyList` exception.
- Otherwise, return the ith element of the list where we count from zero and `i` is the remainder produced when dividing `n` by the length of `xs`.
:::

The sample solution is 6 lines and uses two functions from the standard library `List` module.

## **Problem 5**

:::success
Write a function `array_assoc` of type:

'a -> ('a * 'b) option array -> 'b option

The function takes a key `k` and an array `a`. It should behave like `List.assoc_opt` ([documentation](https://ocaml.org/manual/5.3/api/List.html)) except:

1. It processes arrays instead of lists.
2. It allows the elements of the array to be `None`, in which case it skips them.
:::

Your function should scan the array from left to right looking for a non-`None` pair whose first component is equal to `k`. Return `None` if no such pair exists. Return `Some v` where `v` is the second component of the first matching pair if it exists.

The sample solution is 12 lines and uses a local recursive helper function.

# Part 2: Mutation

A [_cache_](https://en.wikipedia.org/wiki/Cache_(computing)) is a useful concept across many areas of computer systems. The core idea of a cache is to keep around recently (or frequently) accessed results in an easier-to-access manner. A cache is typically smaller than the backing data source, so a subset of the total data is kept in the cache at once.

When a user tries to access data, if the data is in the cache, that saved result is returned (more quickly, because the cache is easier-to-access). This is called a "cache hit". If the data is not in the cache, then the request to access must instead go through the backing data structure, which is slower. This is called a "cache miss". Typically, including for this assignment, after any cache miss, that data item is then added to the cache (potentially, pushing other data out of the cache).

When caches are used to save results of earlier computation, this is also called [_memoization_](https://en.wikipedia.org/wiki/Memoization#:~:text=In%20computing%2C%20memoization%20or%20memoisation,the%20same%20inputs%20occur%20again.). In the next problem, you'll implement a simple cache for an associative array using references and a mutable array.

## **Problem 6**

:::success
Write a function `caching_assoc` of type:

('a * 'b) list -> int -> 'a -> 'b option

The function takes a list `xs` and an int `n` (you can assume `n` positive) and ==returns a function== that takes one argument `k` and returns the same thing that `List.assoc_opt k xs` would return. Review the list documentation to understand `List.assoc_opt`.

While it should have the same input/output behavior as `List.assoc_opt`, your function must implement an `n`-element cache of recent results to possibly make this function faster, rather than directly calling `List.assoc_opt` in all cases.
:::

Your function will probably only be faster if `xs` is long and the same few elements are accessed frequently. Your cache should be an array of length `n` that is allocated as soon as `caching_assoc` is partially applied to its first argument, and then used (and-possibly-mutated) each time the returned function is called.

The cache should start empty (all elements `None`). When the function returned by `caching_assoc` is called, it should first check the cache for the answer (using your previous function `array_assoc`). If there is a cache miss, your function should go to the backing data structure: in this case use `List.assoc_opt` on `xs` to get the answer. If the backing list returns an answer that is not `None`, then you should add the answer to the cache.

The cache slots should be used in a round-robin fashion (similar to a [circular buffer](https://en.wikipedia.org/wiki/Circular_buffer) or queue): the first time a pair is added to the cache, it is put in index 0, then the next pair in index 1, and so on up to index n-1 and then back to index 0 (replacing the pair already there), then index 1, etc. (Circular buffers are a useful data structure to learn, even if you have not seen them before)!

The sample solution is under 15 lines.

:::info
*Hint*: In addition to the array holding the cache, you may want a second mutable value to keep track of which cache index will be replaced next.
:::
:::info
*Hint*: To test your cache, it might be useful to add print expressions so that you know when you are using the cache and when you are not. Remove these print expressions before you submit. Alternatively, you can write a version of the function that returns a boolean for whether the result was retrieved from the cache, but again, remove this before submission.
:::

---
# Part 3: Streams

:::warning
Reminder: the following is covered by Quiz 3, not the upcoming Quiz 2.

We will cover streams in Monday's class.
:::

:::info
Note for some of these problems, the stencil code starts with:

Stream (fun () -> failwith "...not implemented")

This is just so that the function has the correct type for the autograder to build, even if you do not complete that problem.

You can replace that entire line with your solution, your answer does not need to start with `Stream`.
:::

## **Problem 7**

:::success
Write a function `stream_first_k_such_that` that takes arguments
- `p : 'a -> bool`
- `k : int`
- `s : 'a stream`

It returns a **list** (not a stream) holding the first `k` values produced by `s` on which `p` returns `true`, in the same order as they were produced by `s`.

Assume `k` is nonnegative.
:::

The sample solution is 8 lines.

*Note*: This function will be useful to test streams you define below.

*Note*: `stream_first_k_such_that` will run forever if `f` returns `false` for all elements of `s` except a finite number less than `k`. This is expected.

## **Problem 8**

:::success
Write a stream `funny_number_stream` that is like the stream of positive natural numbers (i.e., 1, 2, 3, 4, ...) except that numbers divisible by 6 are negated (i.e., 1, 2, 3, 4, 5, -6, 7, 8, 9, 10, 11, -12, 13, ...).
:::

The sample solution is 4 lines.

:::info
Hint: Remember that the argument to the `Stream` constructor is a thunk that returns a pair. The first element of this pair will be a number and the second argument will be another stream.
:::

## **Problem 9**

:::success
Write a stream `foo_then_bar`, where the elements of the stream alternate between the strings `"foo"` and `"bar"`, starting with `"foo"`.
:::

The sample solution is 4 lines.

## **Problem 10**

:::success
Write a function `cycle_lists` that takes two lists `xs` and `ys` and returns a stream. The lists may or may not be the same length, but assume they are both non-empty. The elements produced by the streams are pairs where the first component is from `xs` and the second component is from `ys`. The stream cycles forever through the lists.
:::

For example, if `xs` is `[1;2;3]` and `ys` is `[“a”;”b”]`, then the stream would produce

`[(1, "a"); (2, "b"); (3, "a"); (1, "b"); (2, "a"); (3, "b"); (1, "a"); (2, "b")]`

The sample solution is 4 lines, but is more complicated than the previous stream problems.

:::info
*Hint*: Use one of the functions you wrote in Part 1.
:::
:::info
*Hint*: Use a recursive helper function that takes a number `n` and calls itself with `n + 1` inside a thunk.
:::

---

# **Summary**

Evaluating a correct assignment solution should generate these bindings *or more general types* in addition to the bindings from the provided code.

val add : nat -> nat -> nat
val to_int : nat -> int
val from_int : int -> nat
val sequence : int -> int -> int -> int list
val list_nth_mod : 'a list -> int -> 'a
val array_assoc : 'a -> ('a * 'b) option array -> 'b option
val caching_assoc : ('a * 'b) list -> int -> 'a -> 'b option
val stream_first_k_such_that : ('a -> bool) -> int -> 'a stream -> 'a list
val funny_number_stream : int stream
val foo_then_bar : string stream
val cycle_lists : 'a list -> 'b list -> ('a * 'b) stream

Generating these bindings does not guarantee that your solutions are correct.

# Submission

Submit the following **3 files** on **Gradescope**:

:::success
- `a6.ml`
- `a6test.ml`
- A `README.txt` or `README.md` file that answers Question 1 and the following:
- Roughly how long did this assignment take you (in hours)?
- Which was the most challenging problem?
- Which was your favorite problem?
- Which resources did you find to be the most useful?
:::