HW4

Due: Monday, November 6, 11:59pm Pacific Time

Instructions

You will write and test 12 OCaml functions.

Important setup instructions: In this homework we are introducing a unit testing library. Run this command to install it.

opam install ppx_inline_test

You can then write lines in hw4tests.ml such as

let%test _ = sequence 1 3 2 = []

The let%test binding takes a boolean on the right hand side of the first equals sign and throws an error if it is false.

Run the tests with dune test and you will get an error if any of them fail.

We strongly recommend writing your tests in this new style, but it is not required. If for some reason you cannot get ppx_inline_test installed or working, you may use any other reasonable way of writing your tests (and in that case, you can delete the %test annotations from the provided tests).

The problems

Warmup

Write a function sequence of type that takes 3 int arguments called spacing, low, and high. Assume spacing is positive. The function returns an int list of numbers from low to high (including and possibly high) separated by spacing in sorted order.

See the provided tests for a few examples.

Sample solution: 5 lines.

Write additional tests to convince your reader that your function is correct.
Write a function string_append_map that takes a string list called xs and a string called suffix and returns a list of strings. Each element of the output should be the corresponding element of the input appended with suffix (with no extra space between the element and suffix).

Sample solution: 2 lines.

Write tests to convince your reader that your function is correct.
Write a function list_nth_mod that takes a list xs and an int called n. If n is negative, call
```
failwith "list_nth_mod: negative number"
```
Otherwise, if the list is empty, call
```
failwith "list_nth_mod: empty list"
```
Otherwise, return the \(i\)^th element of the list where we count from zero and \(i\) is the remainder produced when dividing n by the length of xs.

Sample solution is 6 lines and uses two functions from the standard library List module.

Write tests to convince your reader that your function is correct.

Streams

Write a function stream_first_k_such_that that takes arguments
- f : 'a -> bool
- k : int
- s : 'a stream
It returns a list (not a stream) holding the first k values produced by s on which f returns true, in the same order as they were produced by s.

Assume k is nonnegative.

Sample solution: 8 lines.

Write tests to convince your reader that your function is correct.

Note: This function will also 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.
Write a stream funny_number_stream that is like the stream of positive natural numbers (i.e., 1, 2, 3, ...) except that numbers divisble by 6 are negated (i.e., 1, 2, 3, 4, 5, -6, 7, 8, 9, 10, 11, -12, 13, ...).

Sample solution: 4 lines.

Write tests to convince your reader that your function is correct.

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.
Write a stream dan_then_dog, where the elements of the stream alternate between the strings "dan" and "dog", starting with "dan".

Sample solution: 4 lines.

Write tests to convince your reader that your function is correct.
Write a function stream_pair_all_with_one that takes a stream s and returns another stream. If s would produce \(v\) for its \(i\)^th element, then stream_pair_all_with_one should produce \((1, v)\) for its \(i\)^th element.

Sample solution: 4 lines.

Write tests to convince your reader that your function is correct.
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")]
```
Sample solution is 4 lines but is more complicated than the previous stream problems.

Write tests to convince your reader that your function is correct.

Hint: Use one of the functions you wrote in the Warmup section.

Hint: Use a recursive helper function that takes a number n and calls itself with n + 1 inside a thunk.

Memoization

For these problems you will need to know about OCaml arrays. They are exactly what you think they are: mutable sequences whose length is determined at allocation time. The syntax for array operations is:

Array.make n d allocates an array of length n where every element is equal to d.
a.(i) return the i^th element of the array a. Throws an exception if i is out of bounds.
a.(i) <- v overwrite the i^th element of the array a with new value v. Throws an exception if i is out of bounds.
Array.length a returns the length of the array a.
[|v1; v2; ...; vn|] an array literal. Note the vertical bar characters after the open square bracket and before the close square bracket. Otherwise the syntax is identical to list literals. Useful for tests.

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 except (1) it process arrays instead of lists and (2) it allows the elements of the array to be None in which case it skips them. It 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.

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

Write tests to convince your reader that your function is correct. (Array literals might be useful to construct your test data.)
Write a function caching_assoc of type
```
('a * 'b) list -> int -> 'a -> 'b option
```
The function takes a list xs and an int n (assume it is positive) and returns a function (!) that takes one argument k and returns the same thing that List.assoc_opt k xs would return. However, you should use an n-element cache of recent results to possible 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.) The 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 starts empty (all elements None). When the function returned by caching_assoc is called, it first checks the cache for the answer (using array_assoc). If it is not there, it uses List.assoc_opt on xs to get the answer, and if the answer is not None, then it adds the answer to the cache. The cache slots are used in a round-robin fashion: 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.

Sample solution is less than 15 lines.

Write tests to convince your reader that your function is correct.

Hint: In addition the array holding the cache, you will want a second mutable value to keep track of which cache index will be replaced next.

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.

Trefoil v1

Examine the provided token type in hw4types.ml. It has the following constructors:

Literal, which represents an integer literal from the program source
Plus, which represents "+"
Minus, which represents "-"
Mul, which represents "*"
Dot, which represents "."

Write a function tokenize of type string -> token list. The string argument represents the source code of a Trefoil v1 program. tokenize converts the source code into a list of tokens.

If you encounter any unexpected characters in the string, or if the input is otherwise malformed in any way, call failwith "tokenizing error".

For this homework, you do not need to be especially careful about detecting all possible errors or defending yourself from strange inputs. Just write straightforward code.

Sample solution is 15 lines and uses a local recursive helper function that takes a string list.

Write tests to convince your reader that your function is correct.

Hint: Split the input on spaces using a function from the standard library.

Hint: Use another standard library function to convert strings to integers.
Write a function interpret of type
```
int list -> token list -> int list
```
The first argument is the current stack. The second argument is the rest of the program tokens that still need to be interpreted. interpret iterates over the tokens and executes them on the current stack. Here's what each token should do:
- Literal n: push n on the stack
- Plus: pop two values off the stack, add them, and push the result on the stack
- Mul: similar to Plus but with multiplication
- Minus: pop two values off the stack, subtract the first from the second, and push the result. (Be careful about the order of which gets subtracted from which! James messed this up on an earlier version of this handout.)
- Dot: pop one value and print it to standard output
The stack is represented by an OCaml list. The top of the stack is the head of the list. To push onto the stack, just use ::. To pop the stack, use pattern matching to get the first element of the list.

If an operation requires elements on the stack but the stack is empty, call failwith "interpret: not enough stack elements".

When you get to the end of the token list, return the final stack.

Sample solution is between 8 and 12 lines and cleanly uses simultaneous pattern matching on the token list and the stack.

Write tests to convince your reader that your function is correct. (It's not easy to automatically test what gets printed to standard output. Check that what is being printed is correct manually. Instead, write tests that check that the final stack is as expected. In such tests it is useful not to print the final answer but to leave it on the stack so that the test can see it easily.)

Summary

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

val sequence : int -> int -> int -> int list
val string_append_map : string list -> string -> string list
val list_nth_mod : 'a list -> int -> 'a
val stream_first_k_such_that : ('a -> bool) -> int -> 'a stream -> 'a list
val funny_number_stream : int stream
val dan_then_dog : string stream
val stream_pair_all_with_one : 'a stream -> (int * 'a) stream
val cycle_lists : 'a list -> 'b list -> ('a * 'b) stream
val array_assoc : 'a -> ('a * 'b) option array -> 'b option
val caching_assoc : ('a * 'b) list -> int -> 'a -> 'b option
val tokenize : string -> token list
val interpret : int list -> token list -> int list

Notice all functions use currying for multiple arguments. Of course, generating these bindings does not guarantee that your solutions are correct.

Put your solutions to the problems in hw4.ml. Put your tests in hw4test.ml. Upload these files to Gradescope.

Do not modify hw4types.ml or hw4.mli and do not turn them in.