Today we covered roughly Hickey chap.6-6.4,6.6,7,8,9 in the OCaml part.
For this afternoon, consider the following exercises:
1. a. Write an optimizer for the arithmetic expressions (1 * e ~~~> e, ...)
b. Quickcheck your optimizer (which property should it have?)
2. a. Write an interpreter for the abstract machine
b. QuickCheck that evaluation and compilation+interpretation agrees
3. a. Extend exercises 1 and 2 with subtraction
b. QuickCheck your extension
4. Consider the following representation of Red-Black trees:
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
type color = R | B
type 'a tree = E | T of color * ('a tree) * 'a * ('a tree)
R stands for 'red' and B stands for 'black'
Trees are either
empty (the E constructor) or
non-empty (the T constructor, which expects a color, a left
sub-tree, a tree element, and a right sub-tree)
We can represent sets using this representation:
type 'a set = 'a tree
(* empty : 'a set *)
let empty = E
(* member : 'a -> 'a set -> bool *)
let rec member x s = match s with
| E -> false
| T (_,a,y,b) ->
if x < y then member x a else
if x = y then true else
(* x > y *) member x b
(* balance : color * ('a tree) * 'a * ('a tree) -> 'a tree *)
let balance t = match t with
| B, T(R, T(R,a,x,b), y, c), z, d
| B, T(R, a, x, T(R,b,y,c)), z, d
| B, a, x, T(R, T(R,b,y,c), z, d)
| B, a, x, T(R, b, y, T(R,c,z,d)) -> T(R, T(B,a,x,b), y, T(B,c,z,d))
| color, a, x, b -> T(color,a,x,b)
(* insert : 'a -> 'a set -> 'a set *)
let insert x s =
let rec ins s = match s with
| E -> T (R,E,x,E)
| T (color,a,y,b) -> if x < y then balance (color, ins a, y, b) else
if x = y then T (color,a,y,b) else
(* x > y *) balance (color, a, y, ins b) in
let make_black t = match t with
| E -> raise (Failure "cannot color empty tree")
| T (_,a,y,b) -> T (B,a,y,b) in
make_black (ins s)
which has been adapted from the Haskell code in the following paper:
https://wiki.rice.edu/confluence/download/attachments/2761212/Okasaki-Red-Black.pdf
Since 'insert' produces new trees, it should satisfy the red-black invariants:
Invariant 1: No red node has a red parent
Invariant 2: Every path from the root to an empty node contains the same number of black nodes
a. Write a predicate to check invariant 1
b. Write a predicate to check invariant 2.
What type should it have, so that we can check agreement between sub-trees?
c. Write a QCheck test based on a. and b.
For simplicity, you should not attempt to generate arbitrary trees
satisfying the invariants.
Instead generate a list of elements, 'insert' them all, and check that
the result satisfies the red-black invariants.
5. The default integer generator 'int' primarily generates large integers.
The 'small_int' generator on the other hand favors small numbers.
Program an alternative integer generator by combining different
generators such that the result has a reasonable chance of
generating both, as well as corner cases such as -1, 0, and 1.