Skip to content

Homework 7

Due: Sunday, October 26 11:59pm

Start with the template code here.

  • Replace each failwith "TODO" with your solution.
  • Be sure to test your solutions in utop or in tests alongside your submission. To load your file into utop, use #use "hw7.ml";;.
  • Submit your version of hw7.ml to the HW6 assignment on Gradescope. Only submit hw7.ml; NOT any other files or folders.
  • At the top of the template file, there is a comment for you to write in approximately how many hours you spent on the assignment. Filling this in is optional, but helpful feedback for the instructors.

Q1: Counters

In this problem, we have two implementations of a "counter": mk_counter_1 and mk_counter_2, both of type unit -> (int -> int):

let mk_counter_1 : unit -> (int -> int) = 
    let c = ref 0 in 
    fun _ -> 
        fun x ->
            c := !c + x;
            !c

let mk_counter_2 : unit -> (int -> int) = 
    fun _ -> 
        let c = ref 0 in 
        fun x ->
            c := !c + x;
            !c
When either function is called on (), it returns a function of type int -> int. This returned function accumulates a running sum of all inputs seen so far, and outputs that running sum. For example: 
let ctr = mk_counter_2 () in 
let _ = ctr 1 in 
let _ = ctr 2 in 
ctr 3
should output 6 (since 1 + 2 + 3 = 6).

However, mk_counter_1 and mk_counter_2 are not identical. In this problem, write a function 

let distingiush (ctr : unit -> int -> int) : int = failwith "TODO"
that returns a different value when called with mk_counter_1 and mk_counter_2. Your implementation of distinguish should NOT make reference to mk_counter_1 or mk_counter_2 directly, but only the passed-in counter ctr.

Grading Criteria: Q1

Whether distinguish mk_counter_1 = distinguish mk_counter_2 always returns false.

Q2: Aliasing

In this problem, we want to create a function f : int ref -> int ref -> int that has the following behavior: when called with c : int ref, holding initial contents v_c : int and d : int ref holding initial contents v_d : int, then:

  • After executing f c d, !c should be v_c + 1, and !d should be v_d + 1; and
  • The return value of f c d should return v_c + v_d + 2.

Q2.1

Design a test: 

let f_ok (f : int ref -> int ref -> int) (c : int ref) (d : int ref) : bool = failwith "TODO"
that checks whether f meets the above specification when called with c and d. Your function f_ok should call f on c and d, and test whether the two above properties hold about the return value and the new values of !c and !d --- and return true if and only if this is the case.

Grading Criteria: Q2.1

Whether f_ok precisely implements the two-part specification above.

Q2.2

Now, below is a function, incr2, which is an attempt at implementing this specification: 

let incr2 (c : int ref) (d : int ref) : int = 
    c := !c + 1;
    d := !d + 1;
    (!c + !d)

Even ignoring integer overflows, this specification is false for incr2. We can see this by specializing our function f_ok to incr2_ok: 

let incr2_ok : int ref -> int ref -> bool = f_ok incr2

Since incr2 is incorrect, there should be a way to call incr2_ok with inputs such that it returns false. Thus, design a function 

(* TODO: Explain why this is a good counter-example. *)
(* Should call incr2_ok e1 e2, for some expressions e1 and e2. *)
let incr2_counter_example () : bool = failwith "TODO"
which calls incr2_ok and makes it return false. Your function must return the boolean returned by incr2_ok, and it must return false. Additionally, include a comment above your function that explains why your incr2_ok returned false for your example.

Grading Criteria: Q2.2

Whether your counter-example demonstrates a call to incr2_ok that causes it to return false.

Q2.3

Design a new function 

let incr2_fixed (c : int ref) (d : int ref) : int = failwith "TODO"
that does meet the desired specification.

Grading Criteria: Q2.3

Whether incr2_fixed meets the specification described above.

Q3: Mutable Data Structures

Let's create a data structure for trees with mutable subtrees: 

type 'a mtree = MLeaf of 'a | MBranch of ('a mtree) ref * ('a mtree) ref
This is like an ordinary binary tree, but we store references to subtrees, rather than the actual subtree. (This is how algebraic data types are often represented in lower-level languages, like C and Rust, which are defined in terms of pointers.)

Q3.1 Every ordinary binary tree can be converted to an mtree. Implement it: 

type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree

let rec mtree_of_tree (t : 'a tree) : 'a mtree = failwith "TODO"

Grading Criteria: Q3.1

Whether mtree_of_tree is implemented correctly: the entire structure of the tree is reflected in the mtree.

Q3.2

We can define a sum function for mtrees holding integers as follows: 

let rec mtree_sum (t : int mtree) : int = 
    match t with 
    | MLeaf x -> x
    | MBranch (l, r) -> mtree_sum !l + mtree_sum !r

Unlike the corresponding sum function on an int tree, there are mtrees where mtree_sum will fail to terminate. Construct an example mtree below: 

let my_mtree () : int mtree = failwith "TODO"

Grading Criteria: Q3.2

Whether my_mtree constructs an mtree that causes mtree_sum to loop forever.

Q3.3

While mtree_sum might not terminate, it is still clearly a useful function. Let's fix the termination issue. Construct a function 

let rec mtree_sum_fixed (t : int mtree) : int option = failwith "TODO"
that returns None in the case where mtree_sum would not terminate; and otherwise, returns Some v, where v is the sum of the mtree. If mtree_sum would terminate on your mtree, then mtree_sum_fixed should not return None. (Hint: think of what caused my_mtree to cause mtree_sum to loop forever.)

Grading Criteria: Q3.3

Whether mtree_sum_fixed always terminates; returns None exactly when mtree_sum would loop forever; and returns Some v otherwise, where v is the sum of the mtree.