This note describes the random procedure in Chez Scheme and illustrates its use to performing unit tests and to generate random arithmetic expressions.
Chez Scheme’s predefined procedure random, when applied to a positive integer n, returns a random non-negative integer smaller than n:
> (random 5)
4
> (random 5)
0
> (random 5)
0
> (random 5)
3
> (random 5)
4
> (random 5)
1
> (random 5)
3
>
In all cases, the results of evaluating (random 5) range between 0 and 4. In particular, they range between 0 and 1 if we evaluate (random 2), as if we were flipping a coin.
Whatever.—popular saying
It is simple to compare two procedures that implement the factorial function – just pick an input at random, apply each procedure to this input, and compare the results:
(define random-test-fac
(lambda (fac1 fac2 max)
(let ([n (random max)])
(or (= (fac1 n)
(fac2 n))
n))))
A successful test yields #t, and an unsuccessful test yields the differing input.
We can also repeatedly compare two implementations of the factorial function:
(define random-test-fac-repeatedly
(lambda (fac1 fac2 max how-many-times)
(letrec ([visit (lambda (i)
(if (= i 0)
#t
(let ([result (random-test-fac fac1 fac2 max)])
(if (number? result)
result
(visit (- i 1))))))])
(visit how-many-times))))
A successful test yields #t, and an unsuccessful test yields the first differing input.
For example, consider the two following canonical implementations of the factorial function, one recursive and the other tail-recursive with an accumulator:
(define fac
(lambda (n)
(letrec ([visit (lambda (i)
(if (zero? i)
1
(* i (visit (- i 1)))))])
(visit n))))
(define fac_alt
(lambda (n)
(letrec ([walk (lambda (i a)
(if (zero? i)
a
(walk (- i 1) (* i a))))])
(walk n 1))))
Here is how to randomly sample numbers between 0 and 49 and test whether the two implementations agree on 20 of these numbers:
> (random-test-fac-repeatedly fac fac_alt 50 20)
#t
>
Harald (in thoughts): I wonder whether Loki has heard of this random procedure.
The two implementations agree. Yay.
Let us sample the distribution of the numbers yielded by random and visualize it. Given a non-negative integer, the following procedure, sample-random-2,
(define sample-random-2
(lambda (size-of-sample)
(letrec ([loop (lambda (i zeroes ones)
(if (= i 0)
(list (* (/ zeroes size-of-sample) 100.0)
(* (/ ones size-of-sample) 100.0))
(case (random 2)
[(0)
(loop (- i 1) (+ zeroes 1) ones)]
[else
(loop (- i 1) zeroes (+ ones 1))])))])
(loop size-of-sample 0 0))))
The following scenario visualizes this distribution, varying the size of the sample:
> (sample-random-2 10)
(50.0 50.0)
> (sample-random-2 100)
(53.0 47.0)
> (sample-random-2 1000)
(50.3 49.7)
> (sample-random-2 10000)
(49.38 50.62)
> (sample-random-2 100000)
(50.027 49.973)
> (sample-random-2 1000000)
(49.9981 50.0019)
>
To the naked eye, the distribution of 0‘s and 1‘s appears to be balanced.
Write a similar sampling procedure testing-random-3 that repeatedly calls random to generate 0, 1, and 2, tallies how many times each of 0, 1, and 2 is generated, and normalizes the three results as percentages. Does the distribution look balanced?
Random arithmetic expressions, especially when they can be arbitrarily large, are a boon for writing unit tests: they increase the probability of detecting a bug in the tested program, and also they make it possible to stress-test a program over large input data.
Let us revisit arithmetic expressions from Week 05:
The Scheme code for the present lecture note contains
Here are the generator and the unparser in action:
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(- 3 93)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
x0
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(+ 69 x0)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(let ([x2 (- x0 (+ 5 32))]) 76)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(let ([x2 (+ (- (- (- x0 x0) (+ x0 x0)) x0) x0)])
(let ([x3 (- x0 x0)]) x0))
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
49
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
x0
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
x0
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(+ (let ([x2 (- x0 37)])
(+ (let ([x3 (+ x0 x2)]) (- x2 x3))
(- (let ([x3 x0]) x2) (- x2 x0))))
48)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
x0
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(let ([x2 81]) 44)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(+ (+ 31 (- x0 63))
(let ([x2 (- 50 (- x0 72))])
(let ([x3 (+ (+ x2 x0) (- x0 x0))])
(let ([x4 (+ x3 x3)]) (+ x4 x4)))))
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
x0
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(let ([x2 (- (let ([x2 (+ 12 (- x0 x0))]) 90)
(+ (+ x0 (let ([x2 x0]) x2)) (+ 62 (+ x0 x0))))])
x0)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(+ (+ (+ x0 9) 8) 51)
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(+ (+ (let ([x2 (let ([x2 x0]) (let ([x3 x0]) x0))]) x2)
(- x0 (- (let ([x2 x0]) x2) (+ x0 x0))))
(- x0 85))
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
30
> (unparse-arithmetic-expression (make-random-arithmetic-expression 5))
(let ([x2 (let ([x2 25]) (- 12 (let ([x3 (+ x0 x2)]) 36)))])
21)
>
Observe, e.g., how let-expressions can occur anywhere, including in the header of another let-expression, as a definiens.
Modify the generator so that the depth of the resulting arithmetic expressions is the one that was specified, not at most the one that was specified.
Hint:
Modify the generator so that it yields closed expressions, i.e., expressions where all the variables are declared locally.
Hints:
Created [20 Oct 2025]