
Project 1
Due February 11, 2009
11:59:59pm
Updates
Part 0: Warmup
Implement the following functions in OCaml. Do not use any functions
in the List module, i.e., write every function from scratch using just
list notation [...], ::, and pattern matching.
 Write a function prod l : int list > int that returns
the product of the elements of l. The function prod should
return 1 if the list is empty.
 Write a function addTail l e : 'a list > 'a > 'a list
that takes a list l and a single element e and
returns a new list where e is appended to the back
of l. For example, addTail [1;2] 3 =
[1;2;3].
 Write a function index l e : 'a list > 'a > int that
takes a list and a single element and returns the position of the last
occurrence of that element in the list (indexed by zero). You should
return 1 if the element is not in the list.
 Write a function unzip l : ('a*'b) list > ('a list)*('b
list) that given a list of pairs, returns a pair of lists with the
elements in the same order. For example, unzip [(1, 2); (3, 4)]
= ([1; 3], [2;4]).
 Write a function app_int f m n : (int>'a)>int>int>'a
list that returns the list [f m; f (m+1); ...; f n]. It
should return the empty list if n < m.
Write your solutions to this part of the project in a file warmup.ml.
Introduction
For this project, you will develop some functions for working with
boolean formulae, defined by the following OCaml data type:
type formula =
False
 True
 Var of char
 And of formula * formula
 Or of formula * formula
 Not of formula
 Forall of char * formula
 Exists of char * formula
Here False and True represent the obvious values.
Var c represents the boolean variable with name c
(notice that variable names can only be characters. The constructors
And, Or, and Not represent boolean
conjunction, disjunction, and negation, respectively. For example,
the mathematical formula (a or b) and c would be represented by
the OCaml value And(Or(Var 'a', Var 'b'), Var 'c'). (We'll
explain Forall and Exists in a moment.)
We will use associative lists, which are just lists of pairs,
to assign truth values to variables:
type assignment = (char * bool) list
Here if an assignment contains the pair (c,b), then
that assignment gives the variable represented by the character
c the value b. When working with the type
assignment, you will find the functions List.assoc,
List.mem_assoc, and related functions helpful. See the OCaml
library documentation for more details.
You may assume for purposes of this project that whenever you work
with an assignment, all listed variables are distinct (i.e.,
you don't need to worry about shadowing names).
The last two kinds of formula, Forall and
Exists, represent the similarly named quantifiers. The boolean
formula Forall(x, f) is true if f is true under all
assignments to x, i.e., if f is true when
x=true and when x=false. The boolean formula
Exists(x, f) is true if f is true either for
x=true or x=false. For example, the formula
Forall('x', Or(Var 'x', Var 'y')) is true under the
assignment [('y', true)] and false under the assignment
[('y', false)].
Part 1: Boolean Formulae
Write the following functions that work with boolean formulae:
 nnf : formula > bool. This function returns true if
the formula is in negation normal form (NNF). A formula is in
NNF if negation appears only "in front" of variables. For example,
Or(Not (Var 'x'), True) is in NNF, but Not(And(Var 'x',
False)) is not.
 to_nnf : formula > formula. Given an arbitrary
formula, this function returns an equivalent formula in NNF. To write
this function, you can use the following equivalences:
Not True  =  False
 Not False  =  True
 Not(Not f)  =  f
 Not(And(f1, f2))  =  Or(Not f1, Not f2)
 Not(Or(f1, f2))  =  And(Not f1, Not f2)
 Not(Forall(x, f))  =  Exists(x, Not f)
 Not(Exists(x,f))  =  Forall(x, Not f)

 eval : formula > assignment > bool. This function
evaluates the boolean formula on the given variable assignment and
returns the result as an OCaml bool. For example, given the
OCaml value And(Or(Var 'x', Var 'y'), Var 'z') and the
assignment [('x', true); ('y', false); ('z', true)], the
eval function should return true. Your function can
assume that all of the formula's free variables are
specified in the assignment.
 vars_of : formula > char list. This function takes a
formula and returns a list of the names of the free variables
of the formula. The free variables are those that are not bound by a
quantifier. For example, for Exists('x', Or(Var 'x', Var
'y')), you should return a list containing only 'y'.
The list should contain no duplicates. There is no requirement as to
the order that the variable names must appear in the list.
 sat : formula > assignment option. This function
returns Some a, where a is a satisfying assignment,
if the formula is satisfiable, or None otherwise. For
example, sat (Or(Var 'x', Var 'y')) could return three
things: Some ([('x', true); ('y', false)]), Some ([('x',
false); ('y', true)]), or Some ([('x', true); ('y',
true)]), whereas sat (And(Var 'x', Not (Var 'x'))) would
return None. If more than one assignment is possible, you
may return any assignment. You might find the vars_of
function handy here. Do not worry about the efficiency of this function.
Part 2: Binary Arithmetic with SAT
The sat function you wrote above is likely not very
efficient; given a formula with n free variables, it probably
always runs in O(2^n) time. That's fine for this project, and
that's the worst case bound, but there has been significant progress
in recent years in developing SAT solvers that can test for
satisfiability much more efficiently in the "common case." One of the
major applications of SAT solvers is in reasoning about the kinds of
arithmetic hardware does, which is all carried out by bit twiddling.
In this project, you will implement a model of hardware arithmetic,
and you can then use your (inefficient) sat function to
compute some interesting stuff.
The functions for this part will work with the following type:
type vec = formula list
A vec is a list of boolean formulae representing the bits of
a machine word, with the low order bit at the head of the list. For
example, we would represent the number 13 as x = [True; False;
True; True]. We could represent an unknown 4bit number as y
= [Var 'a'; Var 'b'; Var 'c'; Var 'd']. (We'll see the use of
this just below.) Below when we refer to x and y,
we'll mean these two vecs. For this problem, we will only
work with nonnegative numbers.
Write the following functions for type vec. For the first
few problems, you can just think of vec's as lists of
Trues and Falses.
 double : vec > vec. This function returns a
vec representing twice its argument. For example, double
[False; True] (which is 2) should return [False; False;
True] (which is 4). (Yes, this is really easy.)
 int_of_vec : vec > int. This function takes a
vec composed solely of Trues and Falses and
returns the integer equivalent. For example, int_of_vec [False;
True] should return 2. You don't need to handle the case when
some element of vec is neither True nor
False.
 vec_of_int : int > vec. This function takes a nonnegative
integer and returns the corresponding vec. For example,
vec 13 should return x above. Hint: You'll
probably want to use the infix operators mod and /.
 subst : assignment > vec > vec. This function
reduces the vec argument to a vec of all
Trues and Falses by replacing the variables in the
vec according to the assignment and then evaluating
each bit. For example, subst [('x', true); ('y', false)] [Var
'x'; True; And(Var 'y', True)] returns [True; True; False].
 zero : vec > formula. This function returns a boolean
formula representing whether vec represents zero, i.e., is
composed solely of False or formulae that are false. For
example, if y is the fourbit number defined above, zero y could return And(Not Var 'a', And(Not Var
'b', And(Not Var 'c', Not Var 'd'))). This is really cool: Once
we have this, we can ask a question like sat (zero y), and
the sat function will tell us, yes, there are choices for
Var 'a', Var 'b', Var 'c', and Var
'd' that make the formula true. When you're testing your code,
you can use the functions subst and int_of_vec above
to look at your answers more easily.
 bitand : vec > vec > vec. This function returns a new
vec representing the bitwise and of the two vectors. For
example, if x and y are as defined above, then bitand x y should return [And(True, Var 'a');
And(False, Var 'b'); And(True, Var 'c'); And(True, Var 'd')].
Now we can do an even cooler thing: we can ask a question like sat
(zero (bitand x y)), i.e., are there choices for variables
a..d such that if you and x with y, you get
zero. You can assume for this problem that the two bit vectors have
the same length.
 eq : vec > vec > formula. This function returns a
formula representing whether the two bit vectors are equal. For
example, eq [Var 'a'] [True] could return Or(And(Var 'a',
True), And(Not (Var 'a'), Not True)). (In other words, the two
vectors are equal if either both a and True are
true, or if both are false.) Now we can ask questions like, sat
(eq y (bitand x y)), i.e., is there a 4bit number such that if
you bitwise and it with x, you get itself.
You can assume for this problem that the two bit vectors have
the same length.
 add : vec > vec > vec. This function returns a new
vec representing the sum of the two vectors. You may assume
the two bit vectors have the same length. Since there may
be a carry out of the last bit, the resulting vector will have one
more element than the input vectors. You'll have to figure out the
formula for addition yourself. Hint: You'll probably want to write
a recursive helper function that has an extra parameter for the carry
bit.
 mul : vec > int > vec. This function mul a i
returns a new vec representing the product of the
a and i. Assume i is nonnegative.
Hint: For an efficient algorithm, use the following idea. If
i is divisible by two, then a*i is the same as
(a*2)*(i/2). Otherwise, i is odd. If i is
one, the product is a. Otherwise, the product is a*(i1)
+ a.
Part 3: Magic Squares
A magic square is an nbyn grid of the numbers 1 through n^2
such that every number appears exactly once and the sum of each row,
column, and diagonal is the same. For example, here is a 3x3 magic
square:
In this part, you will write a function that solves the magic squares
problem, using the machinery you developed in parts 1 and 2. In
particular, what we will do is "reduce" the problem of finding a
solution to the magic squares problem to a boolean formula. We can
then use the sat function to actually find a solution. Here
are the functions you should write:
 add_three : vec > vec > vec > vec. This function
returns a new vector that represents the sum of the three input
vectors. You can assume the three vecs have the same length.
 pad : vec > int > vec. The function pad v i
returns a new vec that is equal to v but whose
length is the greater of i and the length of v.
I.e., it pads v, if necessary, with extra Falses so
that it has i bits.
 is_digit : vec > formula. The input is a vec
of length 4 (i.e., exactly 4 boolean formulae). This function returns
a formula that is true if and only if the vec is greater than
or equal to 1 and less than or equal to 9.
 disjoint : vec list > formula. This function takes a
list of vecs and returns a formula representing whether all
the vecs are different from each other.
 is_magic : vec list > formula. This function takes a
list of exactly nine vecs and returns a formula representing
whether the list is a magic square. A list [v1; v2; v3; v4; v5;
v6; v7; v8; v9] represents the following square:
You can assume that the vecs in the list consist of exactly
four boolean formulae each, i.e., they are fourbit numbers.
You can try out your is_magic function by seeing if it can
decide that the square above is magic. You can also try replacing one
or two entires by variables, and then seeing if your code correctly
finds the right numbers to fill in. However, you'll have to wait a
long, long time if you try making a lot of the entries in the magic
square variables, since your sat function probably takes
exponential time.
What to Submit
Write your solutions to this part in a file boolean.ml.
Here is a very minimal skeleton for this
project.
Academic Integrity
The Campus Senate has adopted a policy asking students to include the
following statement on each assignment in every course: "I pledge on
my honor that I have not given or received any unauthorized assistance
on this assignment." Consequently your program is requested to
contain this pledge in a comment near the top.
Please carefully read the academic honesty section of the
course syllabus. Any evidence of impermissible cooperation on
projects, use of disallowed materials or resources, or unauthorized
use of computer accounts, will be submitted to the Student
Honor Council, which could result in an XF for the course, or
suspension or expulsion from the University. Be sure you understand
what you are and what you are not permitted to do in regards to
academic integrity when it comes to project assignments. These
policies apply to all students, and the Student Honor Council does not
consider lack of knowledge of the policies to be a defense for
violating them. Full information is found in the course
syllabusplease review it at this time.
