Exercise: spec game [✭✭✭]
Pair up with another programmer and play the specification game with them. Take turns being the specifier and the devious programmer. Here are some suggested functions you could use:
num_vowels : string -> int
is_sorted : 'a list -> bool
sort : 'a list -> 'a list
max : 'a list -> 'a
is_prime : int -> bool
is_palindrome : string -> bool
second_largest : int list -> int
depth : 'a tree -> int
Exercise: poly spec [✭✭✭]
Let's create a data abstraction (a module that represents some kind of data) for single-variable integer polynomials of the form \[c_n x^n + \ldots + c_1 x + c_0.\] Let's assume that the polynomials are dense, meaning that they contain very few coefficients that are zero. Here is an incomplete interface for polynomials:
(** [Poly] represents immutable polynomials with integer coefficients. *) module type Poly = sig (** [t] is the type of polynomials *) type t (** [eval x p] is [p] evaluated at [x]. Example: if [p] represents $3x^3 + x^2 + x$, then [eval 10 p] is . *) val eval : int -> t -> int end
(The use of
$ above comes from LaTeX, in which mathematical formulas are
surrounded by dollar signs. Similarly,
^ represents exponentiation
Finish the design of
Poly by adding more operations to the interface.
Consider what operations would be useful to a client of the abstraction:
- How would they create polynomials?
- How would they combine polynomials to get new polynomials?
- How would they query a polynomial to find out what it represents?
Write specification comments for the operations that you invent. Keep in mind the spec game as you write them: could a devious programmer subvert your intentions?
Exercise: poly impl [✭✭✭]
Implement your specification of
Poly. As part of your implementation,
you will need to choose a representation type
t. Hint: recalling
that our polynomials are dense might guide you in choosing a
representation type that makes for an easier implementation.
Exercise: int set rep [✭✭✭]
Consider this interface for integer sets.
Suppose that you wanted the
to_list implementation to
run in constant time, perhaps at the expense of other
operations being less efficient. Implement the interface in a file
intset.ml. First choose a representation type,
then document its abstraction function and representation
invariant. Inside the implementation, define a
function. Insert applications of it in the appropriate
places of your implementation to guarantee that all
input and output values satisfy the representation invariant.
Exercise: interval arithmetic [✭✭✭✭]
Specify and implement a data abstraction for interval arithmetic.
Be sure to include the abstraction function, representation invariant,
rep_ok. Also implement a
to_string function, or a
as seen in the notes on functors.
Exercise: association list maps [✭✭✭]
MyMap signature in maps.ml. Create two
implementations of it, both with the representation type
('k * 'v)
list. The functions in the interface should mostly be trivially
implementable with the association list functions in the standard
List module. Your first implementation should prohibit any key
from appearing twice in the list; and your second should allow it. Start
each implementation by documenting the AF and RI for
t, and only after
you do that, implement the functions.
Exercise: function maps [✭✭✭✭]
MyMap signature using the representation type
'k -> 'v.
That is, a map is represented as an OCaml function from keys to values.
Your solution will make heavy use of higher-order functions.
A Buggy Queue
buggy_queues.ml, which efficiently implements queues
with two lists—but with a couple bugs deliberately injected.
Exercise: AF and RI [✭]
TwoListQueue module documents an abstraction function
and a representation invariant, but they are not clearly identified
as such. Modify the comments to explicitly identify the abstraction
function and representation invariant.
Exercise: rep ok [✭✭]
rep_ok function for
TwoListQueue. Its type should be
-> t. It should raise an exception whenever the representation
invariant does not hold. Modify the other functions exposed by the
Queue signature to (i) check that
rep_ok holds for any queues passed
in, and (ii) check that
rep_ok also holds for any queues passed out.
Hint: you will need to add nine applications of
Exercise: test with rep ok [✭✭✭]
There are two bugs we deliberately injected into
are places where we failed to apply
norm to ensure that a queue is in
normal form. Figure out where those are by testing each operation of
TwoListQueue in the toplevel to see where your
rep_ok raises an
exception. Fix each bug by adding an application of
Hint: to find one of the bugs, you will need to build a queue of length at least 2.