Today's lecture is (again) roughly based on Sec.3-4 of the attached paper
Testing Monadic Code with QuickCheck
Koen Claessen and John Hughes
Haskell Workshop 2002
Note: The paper's code is in the programming language Haskell,
but if you are curious I encourage you to have a look.
Below I also attached the original QuickCheck paper
QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs
Koen Claessen and John Hughes
ICFP 2000
For reference OCaml's queue implementation from the standard library
is available here:
https://github.com/ocaml/ocaml/blob/trunk/stdlib/queue.ml
It is based on mutable, singly-linked lists with a recorded length
field.
As exercises I ask you to consider the following:
1. Extend the MyQueue interface and implementation in exercise1.ml with two operations:
val clear : 'a t -> unit
Discard all elements from a queue.
val length : 'a t -> int
Return the number of elements in a queue.
by forwarding calls to the Queue implementation from
http://caml.inria.fr/pub/docs/manual-ocaml/libref/Queue.html
Then extend the alternative model-based tester of queues
(symbolic representation, generator, printer, model, ...) to test
that these implementations behave according to your model.
2. Implement a shrinker for lists of queue commands.
Like our generator, your shrinker should be careful not to produce
sequences with a Pop command in an empty queue.
Check that it works, e.g., by introducing an error in the algebraic
specification and observing the produced counterexamples.
3. Write a model-based test of OCaml's hashtables
described here: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html
module Hashtbl :
sig
type ('a, 'b) t
val create : ?random:bool -> int -> ('a, 'b) t
val clear : ('a, 'b) t -> unit
val add : ('a, 'b) t -> 'a -> 'b -> unit
val find : ('a, 'b) t -> 'a -> 'b
val mem : ('a, 'b) t -> 'a -> bool
val remove : ('a, 'b) t -> 'a -> unit
...
end
Utilizing the helper function elements:
let elements h = Hashtbl.fold (fun key v acc -> (key,v)::acc) h [];;
the hashtables can used as follows:
# let h = Hashtbl.create ~random:false 42;;
val h : ('_a, '_b) Hashtbl.t =
# Hashtbl.add h "hej" 34;;
- : unit = ()
# elements h;;
- : (string * int) list = [("hej", 34)]
# Hashtbl.add h "sdf" 56;;
- : unit = ()
# elements h;;
- : (string * int) list = [("hej", 34); ("sdf", 56)]
# Hashtbl.clear h;;
- : unit = ()
# elements h;;
- : (string * int) list = []
You should start simple (select only a few operations).
Then
- create a symbolic representation of commands
- write a printer (to print counterexamples)
- write an interpreter of commands
- design a model of hashtables and implement the operations
- test agreement using one of the two approaches we've discussed
- ...
If you introduce small errors in your model can the tests catch them?