fasttest.plt : FastTest Random Test Case Generation

_fasttest.plt : FastTest Random Test Case Generation_

Written by: Carl Eastlund and Carter Schonwald
Bug reports: Send to Carl Eastlund '(cce @ ccs . neu . edu)
Keywords: _quickcheck_ _randomized_ _testing_

This software is distributed under a BSD-style license (see license.txt).

================================================================================

FastTest is a library for random generation of test cases for unit testing.  It
was inspired by the QuickCheck library for Haskell [1].  It includes two
libraries:

random.ss : Randomized generators for sets of data.
schemeunit.ss : SchemeUnit integration for testing based on generators.

[1] http://www.cs.chalmers.se/~rjmh/QuickCheck/

================================================================================

_random.ss : Random data generation_

This module provides tools for constructing random distributions of data.  It
introduces one new type: (Generator T), representing a random generator that
produces values of type T.  Any non-generator value may be used as a constant
generator which always produces that value.

The functions and macros provided by random.ss are described below.  Examples
show valid expressions followed by representative values they may produce.  Most
functions have two varieties: random-X, which provides a generator for some X,
and choose-X, which immediately generates an X.

In general, (choose-X ARG ...) = (generate (random-X ARG ...)).

--------------------

> (generator? v) : Boolean
  v : Any

Reports whether v is an explicit generator (a generator constructed with the
functions in this module).

Remember that non-generator values may be used as constant generators.  The
function nonrandom can be used to convert these to explicit generators.

Example: (generator? 'value) ;; #f
Example: (generator? (nonrandom 'value)) ;; #t
Example: (generator? (random-symbol)) ;; #t

--------------------

> (generate gen [pred count]) : T
  gen   : (Generator T)
  pred  : (-> T Boolean)   default (lambda (v) #t)
  count : Positive-Integer default (default-generate-attempts)

Constructs a random value from the given generator.  Retries up to count times
until the value satisfies the given predicate; raises an error if no satisfying
value is found.

Example: (generate 'value) ;; 'value
Example: (generate (nonrandom 'value)) ;; 'value
Example: (generate (random-symbol)) ;; 'X, 'Y
Example: (generate (random-int-between 1 100) even? 10) ;; 2, 88, 94, 26
Example: (generate (random-string) char?) ;; error

--------------------

> default-generate-attempts : (Parameter Positive-Integer)

This parameter controls the default number of attempts made to generate a random
value satisfying a given property.  The original value is 100.

--------------------

> (nonrandom v) : (Generator v)
  v : Any

Generates the given value deterministically.

Example: (generate (nonrandom 'value)) ;; 'value

--------------------

> (random-int-between i j) : (Generator Nat)
> (choose-int-between i j) : Nat
  i : Integer
  j : Integer >= i

Generates a random integer chosen uniformly between i and j, inclusive.
(choose-int-between i j) = (generate (random-int-between i j))

Example: (choose-int-between 1 10) ;; 7, 3, 10, 9, 1, 8

--------------------

> (random-size [minimum average]) : (Generator Nat)
> (choose-size [minimum average]) : Nat
  minimum [= 0] : Nat
  average [= 4] : Positive-Int

Generates potentially unbounded, but usually small, natural numbers, often
useful for determining the size of other random data.

Produces a geometric distribution with expectation (+ minimum average).  The
odds of producing each value (+ minimum k) for non-negative integer k are:
(* (expt (/ average (+ average 1)) k) (/ 1 (+ average 1)))

(choose-size minimum average) = (generate (random-size minimum average))

Example: (choose-size) ;; 0, 7, 1, 5, 13, 0
Example: (choose-size 10 2) ;; 12, 10, 14, 11

--------------------

> (random-boolean [prob]) : (Generator Boolean)
> (choose-boolean [prob]) : Boolean
  prob [= 1/2] : Real-in[0,1]

Generates booleans, choosing #t with the given probability and #f otherwise.
Defaults to fair choice.

(choose-boolean prob) = (generate (random-boolean prob))

Example: (choose-boolean) ;; #t, #f
Example: (choose-boolean 1/4) ;; #f, #t, #f, #f

--------------------

> (random-char [code-gen]) : (Generator Char)
> (choose-char [code-gen]) : Char
  code-gen [= (random-int-between (char->integer #\A) (char->integer #\Z))]
           : (Generator Nat)

Generates characters whose code is chosen from code-gen.

(choose-char code-gen) = (generate (random-char code-gen))

Example: (choose-char) ;; #\G, #\M, #\N, #\B
Example: (choose-char (random-int-between 32 126)) ;; #\c, #\9, #\space, #\A

--------------------

> (random-group-of make elem-gen [len-gen]) : (Generator (Groupof T))
> (choose-group-of make elem-gen [len-gen]) : (Groupof T)
  make : T ... -> (Groupof T)
  elem-gen : (Generator T)
  len-gen [= (random-size)] : (Generator Nat)

Generates a random collection of elements.  It chooses a number of elements from
len-gen, generates each from elem-gen, and passes them to the constructor make.

Example: (choose-group-of list (random-symbol)) ;; '(X), '(A B C)
Example: (choose-group-of cons (random-boolean) (nonrandom 2))
         ;; '(#t . #t), '(#t . #f), '(#f . #t), '(#f . #f)

> (random-list-of elem-gen [len-gen]) : (Generator (Listof T))
> (choose-list-of elem-gen [len-gen]) : (Listof T)

> (random-vector-of elem-gen [len-gen]) : (Generator (Vectorof T))
> (choose-vector-of elem-gen [len-gen]) : (Vectorof T)

> (random-string [char-gen len-gen]) : (Generator String)
> (choose-string [char-gen len-gen]) : String

> (random-bytes [byte-gen len-gen]) : (Generator Bytes)
> (choose-bytes [byte-gen len-gen]) : Bytes

  elem-gen : (Generator T)
  char-gen [= (random-char)] : (Generator Char)
  byte-gen [= (random-int-between 0 255)] : (Generator Byte)
  len-gen [= (random-size)] : (Generator Nat)

Generators for lists, vectors, strings, and byte strings, equivalent to
random-group-of or choose-group-of with the added first argument of list,
vector, string, or bytes, respectively.

--------------------

> (random-apply f gen ...) : (Generator B)
> (choose-apply f gen ...) : B
  f : A ... -> B
  gen ... : (Generator A) ...

Generates the result of applying f to random inputs chosen from each gen.

Example: (choose-apply cons (random-char) (random-string))
         ;; '(#\c . "+8Y")

> (random-list gen ...) : (Generator (list T ...))
> (random-vector gen ...) : (Generator (vector T ...))
  gen : (Generator T) ...

Generators for random heterogenous lists and vectors, equivalent to random-apply
with the added first argument of list or vector, respectively.

--------------------

> (random-symbol [name-gen]) : (Generator Symbol)
> (choose-symbol [name-gen]) : Symbol
  name-gen [= (random-string (random-char) 1)] : (Generator String)

Generates random interned symbols whose names are chosen from name-gen.
Equivalent to (random-apply string->symbol name-gen).

Example: (choose-symbol) ;; 'X, 'Y, 'CAT, 'DOG
Example: (choose-symbol (nonrandom "value")) ;; 'value

--------------------

> (random-uniform gen1 ... genK) : (Generator (Or T1 ... TK))
> (choose-uniform gen1 ... genK) : (Or T1 ... TK)
  gen1 ... genK : (Generator T1) ... (Generator TK)

Generates a value from a fairly chosen generator out of gen1 ... genK.

Example: (choose-uniform 'bat 'cat 'dog) ;; 'bat, 'cat, 'dog

--------------------

> (random-weighted weight1 gen1 ... weightK genK) : (Generator (Or T1 ... TK))
> (choose-weighted weight1 gen1 ... weightK genK) : (Or T1 ... TK)
  weight1 ... weightK : Positive-Rational
  gen1 ... genK : (Generator T1) ... (Generator TK)

> (random-weighted* (list pair1 ... pairK)) : (Generator (Or T1 ... TK))
> (choose-weighted* (list pair1 ... pairK)) : (Or T1 ... TK)
  pair1 ... pairK = (cons weight1 gen1) ... (cons weight1 genK)

Generates a value from a generator chosen with the associated weight.

Example: (choose-weighted 1 'bat 2 'cat 3 'dog) ;; 'cat, 'dog, 'bat, 'cat, 'dog
         (choose-weighted* '((1 . bat) (2 . cat) (3 . dog))) ;; as above

--------------------

> (random-recursive rec-gen [weight1 gen1] ... [weightK genK]) : (Generator T)
> (choose-recursive rec-gen [weight1 gen1] ... [weightK genK]) : T
  weight1 ... weightK : Positive-Rational
  gen1 ... genK : (Generator T)

This macro creates a generator for a recursive data structure whose clauses are
generated by gen1 ... genK with respective probabilities prob1 ... probK; the
recursive generator is in scope for gen1 ... genK under the name rec-gen.

(choose-recursive r [w g] ...) = (generate (random-recursive r [w g] ...))

Example:

(define-struct leaf () #f)
(define-struct node (left right) #f)

(choose-recursive tree-gen
  [2 (nonrandom (make-leaf))]
  [1 (random-apply make-node tree-gen tree-gen)])

;; Possible results:
;; (make-leaf),
;; (make-node (make-leaf) (make-leaf)),
;; (make-node (make-node (make-leaf) (make-leaf)) (make-leaf))

--------------------

> (random-function f) : (Generator (A ... -> B))
> (choose-function f) : A ... -> B
  f : A ... -> (Generator B)

Generates a function that produces random outputs.  For each set of inputs, the
resulting function will get the corresponding generator from f and produce a
value from it.  The function will memoize these values to produce consistent
results for any specific set of inputs.

Examples:

(define f
  (generate
   (random-function
    (lambda (n)
      (random-list-of (random-boolean) (nonrandom n))))))

      ;; Notice how (f 5) always produces the same list of 5 booleans:
(f 5) ;; '(#f #f #t #f #t)
(f 2) ;; '(#t #t)
(f 5) ;; '(#f #f #t #f #t)
(f 3) ;; '(#t #f #t)
(f 5) ;; '(#f #f #t #f #t)

--------------------

> (define-generator (name arg ...) (weight gen) ...) :: Macro
  name   :: Identifier
  arg    :: Identifier
  weight :: Expression[Non-Negative-Rational]
  gen    :: Expression[Generator]

Defines a potentially recursive generator function with the given clauses and weights.

Example:

(define-generator (random-sexp max-depth)
  [4 (random-symbol)]
  [(if (< max-depth 1) 0 1)
   (random-apply cons (random-sexp (- max-depth 1))
                      (random-sexp (- max-depth 1)))])

(random-sexp 2) ;; 'X, '(A . B), '((I . J) . K), '((F . O) . (U . R))

--------------------

> (let*-random ((var gen [pred count]) ...) body ...) ;; [] means optional
  var   :: Identifier
  gen   :: Expression[Generator]
  pred  :: Expression[Boolean]          default #t
  count :: Expression[Positive-Integer] default (default-generate-attempts)
  body  :: Expression

Binds random values in an expression.  Equivalent to:
(let* ((var (generate gen (lambda (var) pred) count)) ...) body ...)

Example:

(let*-random ((x (random-int-between 1 10))
              (y (random-int-between 1 15) (> y x) 10))
  (positive? (- y x)))

;; #t (rarely error)

================================================================================

_schemeunit.ss : Randomized SchemeUnit testing_

--------------------

> (check-randomly ((var gen [pred count]) ...) body ...) ;; [] means optional

This is equivalent to let*-random from random.ss (see above), except that it
annotates each binding with SchemeUnit's with-check-info form so they are
included in test case output.

> (test-randomly name count ((var gen [p c]) ...) body ...) ;; [] means optional
  name   :: Expression[String]
  count  :: Expression[Positive-Integer]
  body   :: Expression
  var, gen, p, c :: see check-randomly and let*-random

Creates a SchemeUnit test suite which runs count times; each time creates random
bindings for each clause and evaluates the body expressions.  The resulting test
suite is equivalent to:

(test-suite name
  (test-case "i" ;; for each 0 <= i < count
    (check-randomly ((var gen p c) ...) body ...))
  ...)

Example:

;; This tests whether list-ref produces a member of its list argument.
;; It generates a list of symbols of random length up to 100.
;; It generates a random index into the list, up to 99,
;; retrying up to 100 times to get an index under the list's length.
;; It then checks whether (list-ref elems index) is a member of elems.

(test-randomly "list-ref-produces-member" 100
  ([elems (random-list-of (random-symbol)
                          (random-int-between 1 100))]
   [index (random-int-between 0 99)
          (< index (length elems))
          100])
  (check memq (list-ref elems index) elems))