Data Structures and Functional Programming CS 3110, Fall 2013 Version: 6

Problem Set 4 Due at 11:59 PM, Thursday, October 17 Last Modified: October 22, 2013

Instructions
Compile Errors
All code you submit must compile. Programs that do not compile will be heavily penalized. If your submission does not compile, we will notify you immediately. You will have 48 hours after the submission date to supply us with a patch. If you do not submit a patch, or if your patched code does not compile, you will receive an automatic zero.

Naming
We will be using an automatic grading script, so it is crucial that you name your functions and order their arguments according to the problem set instructions, and that you place the functions in the correct files. Incorrectly named functions are treated as compile errors and you will have to submit a patch.

Code Style
Finally, please pay attention to style. Refer to the CS 3110 style guide and lecture notes. Ugly code that is functionally correct may still lose points. Take the extra time to think out the problems and find the most elegant solutions before coding them up. Good programming style is important for all assignments throughout the semester.

Late Assignments
Please carefully review the course website’s policy on late assignments, as all assignments handed in after the deadline will be considered late. Verify on CMS that you have submitted the correct version, before the deadline. Submitting the incorrect version before the deadline and realizing that you have done so after the deadline will be counted as a late submission.

Getting started
This problem set is long; we recommend you start thinking about all of the parts early. Parts two and three depend on part one, but you only need to implement one of the modules (Floats) in part one to get started on them. The things you have to do are indicated by “Exercise” in the writeup, and are labeled “TODO” in the release code. The GUI for this problem set requires some additional OCaml libraries; the file README.txt in the release contains instructions for compiling and running the project. 1

Introduction
In many applications, users want to rearrange a collection of geometric shapes while keeping them from overlapping with each other. For example, users like to rearrange windows on their desktops while keeping each window entirely visible. Without an automated way to keep them from overlapping, users must carefully adjust the boundaries of the windows if they want to avoid large gaps between the windows. The same user interface feature is useful in other applications, such as computer aided design, graphics applications, and games. In this assignment, you will be building a library that allows users to drag and drop shapes while keeping them from intersecting each other. You will use the library to build a simple “tangrams” game. The correctness of geometric algorithms depends on the properties of the numbers used to represent the coordinates of the shapes. You will implement a variety of number types to investigate the tradeoffs of various representations. Finally, this assignment contains a small problem related to mutability.

Part One: Numbers
For this portion of the assignment, you will implement a variety of modules, each defining a representation of a set of numbers and the operations available for those numbers. Your number modules will each implement one of the following interfaces (we have provided these signatures in numbers.ml): • A Quotient represents a set of elements, which we will refer to as numbers. The only operation provided by Quotient is the (===) function, which defines the notion of equality for the set of numbers. • Just as Quotient defines a notion of equality between numbers, Group defines a notion of addition. In addition to the (+) operation, Group requires a number called zero, and for each number x, an additive inverse -x . Note that OCaml writes the negation operation as (~-). That is, (~-) x is the same as -x. • Ring extends Group by adding a notion of multiplication. It also requires a multiplicative identity called one. • A Field is a ring where every number x has a multiplicative inverse x −1 . This allows us to define division: x/y is just x y −1 . • OrderedRing and OrderedField add a notion of ordering to rings and fields respectively. We only require implementors to provide a function that determines if a number is negative, but comparison operations like () can be defined in terms of is_non_neg (you will do this in exercise 2 below). • NiceRing and NiceField require additional useful functions: the ability to convert a number to an OCaml float, and a function for printing a number onto the console. You can 2

register these formatting functions with the OCaml toplevel using the #install_printer command; this will cause the toplevel to use that function to print out values of your number type. See the toplevel documentation and the documentation for the OCaml Format module for more details. These concepts (with the exception of NiceRing and NiceField) are borrowed from the field of abstract algebra1 . In the same way that modular programming allows us to apply single functions to a large number of data types, these modular definitions have allowed algebraists to prove single theorems that apply to a large number of mathematical structures. In order for the operations defined by these concepts to make sense, they must obey certain properties (axioms). For reference, we have provided modules that encode these properties as functions. For example, the multiplication operation only makes sense if it is commutative, associative, distributes over addition, and if one is a multiplicative identity. These properties are tested (for individual numbers) by the times_commutative, times_associative, times_distributive and times_identity functions. A module R that implements Ring is only valid if for all inputs a, b, and c, each of the functions of the RingProperties (R) module return true. Similarly, the other Properties modules (QuotientProperties, GroupProperties, FieldProperties, and so on) encode the properties of the other module types.

Exercise 1: Simple number types
Implement the following modules and functors in numbers.ml (you may want to implement some of these in terms of others): • module Ints : NiceRing, using int as the number type. • module Integers : NiceRing, using large integers as the number type. You may either use your implementation of big integers from problem set 2, or OCaml’s built-in Big_int module. • module Floats : NiceField, using float as the number type. Because floating point arithmetic is inexact, you should consider two floats to be equal if they differ by less than 10−6 . Warning: This should be your only number module that uses the float type (with the exception of the float_of_number functions). • module Root23 : NiceRing that contains numbers of the form a + b 2 + c 3 + d 6 where a,b,c and d are integers. In addition to the NiceRing functions, this module should expose the numbers sqrt2, sqrt3 and sqrt6 representing 2, 3 and 6 respectively.

note that our groups are technically Abelian groups, and our rings are technically commutative rings with identity

1

3

Hint 1: a 1 + a 2 2 + a 3 3 + a 6 6 is zero if and only if a 1 , a 2 , a 3 and a 6 are zero. This fact may help you with Root23.(===). Hint 2: For Root23.is_non_neg, try working out the solution for numbers of the form a + b 2 first, and then writing numbers in the form (a + b 2) + (c + d 2) 3. • module FieldOfFractions (R : NiceRing) : NiceField should represent numbers as fractions of R.numbers. You are not required to store the fractions in lowest terms. • module Rationals : NiceField should implement the rational numbers. You are not required to store the fractions in lowest terms. • module Rot15 : NiceField should contain the rationals as well as the numbers cos 45◦ , sin 45◦ , cos 30◦ , and sin 30◦ . Hint: these can all be expressed in terms of 2 and 3.

You may find the include and open statements useful for this problem (and throughout the remainder of the problem set).

Exercise 2: Implement utility functors
In our definitions of Quotient, Group, Ring and so on, we provided a minimal set of functions; this makes it easier to implement these interfaces. For example, a module that implements OrderedRing only needs to provide the is_non_neg function; but when using numbers from ordered fields, it is useful to have ordering functions such as (>), (=), and (