Skip to content

Homework 6

Due: Sunday, October 19 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 "hw6.ml";;.
  • Submit your version of hw6.ml to the HW6 assignment on Gradescope. Only submit hw6.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.

Rings

A ring is a data type \(T\) with five extra pieces of data:

  • An element of type \(T\) called zero;
  • An element of type \(T\) called one;
  • A multiplication function mult, of type \(T \to T \to T\); and
  • An addition function add, of type \(T \to T \to T\); and
  • A negation function neg, of type \(T \to T\).

Thus, a ring can be thought of as a generalized form of arithmetic, where the type \(T\) does not need to be integers, but could be something else. However, the operations add and mult should behave as they do in normal arithmetic. This is expressed in the form of ring axioms, but you won't need to understand the ring axioms for this homework.

We can translate this version of a ring into OCaml by writing a module type for it:

module type Ring = sig
    type t
    val zero : t
    val one : t
    val mult : t -> t -> t
    val add : t -> t -> t
    val neg : t -> t
    val gen : unit -> t
    val equals : t -> t -> bool
end

In addition to zero/one/mult/add/neg, we also include functions gen for generating a value of type t; and equals, for checking if two values of type t are equal in the ring.

Q1: Defining Rings

First, we will define some concrete examples of rings. Below is an example: 

module IntRing : (Ring with type t = int) = struct
    type t = int
    let zero = 0
    let one = 0
    let mult x y = x * y
    let add x y = x + y
    let neg x = (- x)
    let gen () = Random.int 100 - 50 (* Generating both positive and negative integers *)
    let equals x y = (x = y)
end

Note that we give IntRing the module type Ring with type t = int. This means that IntRing should have module type Ring, but we are additionally allowing the context to know that t = int. Thus, we are making sure the type is not abstract. The rest of our module annotations will look like this (Ring with type t = ...), but we will supply it for you.

Q1.1

Another example of a ring is the ring of booleans, where: zero is false; one is true; mult is AND; add is XOR; and neg is negation. Implement this boolean ring below: 

module BoolRing : (Ring with type t = bool) = struct
    ...
end
You should implement equals by =.

Q1.2

An important ring for computer science is the ring of non-negative integers modulo some other number, n. In this ring, zero, one, mult, add, and neg are just like the integers, except taken mod n, for some n.
We can set this up by having a module for the modulus n: 

module type Modulus = sig
    val n : int
end
And then letting our module IntMod be a functor (module which takes another module as an argument, like a function): 
module IntMod (M : Modulus) : (Ring with type t = int) = struct
    ...
end

Thus, your operations inside of IntMod should be modulo M.n. Crucially, your definition of equals must identify elements that are equal in the ring; not only elements that are represented by the same underlying integer. Two integers represent the same ring element exactly when they are a multiple of n apart from each other. Thus, if n = 3, we should get that:

\[ \begin{align*} & \dots = -3 = 0 = 3 = 6 = \dots \\ & \dots = -2 = 1 = 4 = 7 = \dots \\ & \dots = -1 = 2 = 5 = 8 = \dots \end{align*} \]

For the generator gen, you should only generate elements that are reduced mod n; thus, if n = 3, your generator should not return -5 (since -5 is equal to 1 modulo 3).

Hint

To implement equals, you will need to use OCaml's built-in infix mod operator; however, this alone does not suffice. See what mod does on negative numbers.

Q2: Building Bigger Rings from Smaller Ones

Q2.1 Given a pair of rings R1 and R2, you can build a bigger one via the product ring R1 * R2, where zero is the pair of zeroes, one is the pair of ones, and each operation is defined componentwise. We can implement it like so: 

module ProductRing (R1 : Ring) (R2 : Ring) : (Ring with type t = R1.t * R2.t) = struct
    ...
end

Implement it.

Q2.2 Given a ring R, the space of functions from string to R also forms a ring. Similar to the product ring, this ring of functions works by defining zero by fun _ -> 0 (where 0 is defined by the ring \(R\)), and similarly for one. The operations mult/add/neg are defined componentwise.

Equality in this ring is undecidable, so you can leave equals unimplemented: 

let equals f1 f2 = failwith "UNIMP"`

For generating a random function, you can use this helper function (included in hw6.ml): 

let gen_func (gen : unit -> 'a) : unit -> (string -> 'a) = 
    let m = Hashtbl.create 100 in 
    fun _ ->
        fun s -> 
            match Hashtbl.find_opt m s with
            | Some v -> v
            | None -> 
                let v = gen () in 
                Hashtbl.add m s v;
                v
which converts a generator for type 'a to a generator for functions from string to 'a. (We do this by using a mutable hash table, but you don't need to fully understand how gen_func works. We will cover mutable state in Week 7.)

module FuncRing (R : Ring) : (Ring with type t = (string -> R.t)) = struct
    ...
    let equals _ _ = failwith "UNIMP"
    ...
end

Q3: Polynomials over a Ring

Given a ring \(R\), we can construct polynomials with coefficients in \(R\). These are the expressions that are built out of: variables (given by an integer index); elements of the ring \(R\); addition; and multiplication. 

type 'a poly = 
    | Var of int
    | Elem of 'a
    | Mul of 'a poly * 'a poly
    | Add of 'a poly * 'a poly

You may assume all variables are indexed by non-negative integers.

Q3.1

Given a map from integers to ring elements, we can develop a functor to evaluate polynomials: 

module IntMap = Map.Make(Int)

module Poly (R : Ring) = struct
    type t = R.t poly
    let rec eval (map : R.t IntMap.t) (p : t)  : R.t option = 
        failwith "TODO"
end

Implement eval by recursively traversing the polynomial. It should return None if any variable is not in the map. (To lookup a variable in the map, you should use IntMap.find_opt).

Q3.2

A polynomial \(P\) defined over a ring \(R\) is zero if it is equal to zero on all inputs:

\[ (1) \forall x_1, x_2, \dots, x_n,\ P(x_1, x_2, \dots, x_n) = 0.\]

(Again, above, \(0\) is referring to the zero in the ring.)

It turns out to be extremely useful to know if a certain \(P\) is zero. While knowing if it equal to zero on all inputs is very hard (since there are exponentially -- or even unboundedly many -- arguments to check), the Schwarz-Zippel Lemma tells us that to decide if \(P\) is zero, it suffices to randomly test if \(P\) is zero on many different inputs. This is exactly equivalent to just using PBT to check the validity of formula \((1)\)! This is a rare case where PBT has an explicit soundness guarantee (albeit a probabilistic one).

Using your functor Poly, implement a new functor PID that uses PBT to test if a polynomial is zero: 

module PID (R : Ring) = struct
    module P = Poly(R)
    (* Compute maximum variable in the polynomial. *)
    let max_var (p : P.t) : int = failwith "TODO"

    (* Create a map with keys ranging from 0 to n (inclusive), filled with random ring elements. *)
    let build_map (n : int) : R.t IntMap.t = failwith "TODO"

    (* Use PBT to test if the polynomial returns zero on all inputs. *)
    let test_pid (p : P.t) : bool = failwith "TODO"

    (* Using `test_pid`, test if `p` and `q` are identical polynomials. *)
    let test_equiv (p : P.t) (q : P.t) : bool = failwith "TODO"
end

  • First, implement max_var which computes, for a given polynomial, the highest variable index in the polynomial (remember we are assuming they begin at index \(0\)).
  • Then, implement build_map which, given a non-negative integer n, computes a value of type R.t IntMap.t (i.e., a map from integers to ring elements) that is defined on all integers between 0 and n (including n), and is filled with random ring elements (generated using R.gen).
  • Now, you can implement test_pid which uses max_var and build_map to actually perform PBT to test of p is equal to zero on all inputs. Your PBT main loop should run for 1000 trials. Feel free to import forall to do this (included in hw6.ml): 
    let rec forall gen prop num = 
    if num <= 0 then None else
        let x = gen () in 
        if prop x then forall gen prop (num - 1) else Some x
  • Finally, you can use test_pid to test if two polynomials are equivalent: if they return the same value on all inputs. Implement this test in test_equiv. (Hint: in a ring, \(x = y\) only if \(x - y = 0\).)

Hint

To implement build_map, first construct a list of key-value pairs (int * R.t) list; then use IntMap.of_list to convert that list to a map. You can construct this list by recursion on the number of variables in the polynomial, constructed by max_var.