Homework 5

Language: Intermediate Student with lambda

This homework provides more practice with randomized testing. If you’re having trouble with Lab 5, consider reading Random Testing Example (and maybe and Testing abs) before continuing the lab exercises.

1 Random Testing Example

Suppose you suspect that the abs function has the following property, which it obviously doesn’t have: for any integer i, applying abs to i produces i. The check-expect form (see the lab instructions for details) lets you test suspicions like this one by repeatedly applying them to randomly generated inputs.

The following code uses check-property to test the suspicion (the function abs-prop1) by applying it to 100 randomly generated integers (produced by bounded-random-integer).

; bounded-random-integer : number -> number

; Given a non-negative integer n, produces an integer in

; the open-interval (-n, n).

(define (bounded-random-integer n)

(if (zero? (random 2))

(- (random n))

(random n)))

(check-expect (bounded-random-integer 1)

0)

(check-expect (<= -10 (bounded-random-integer 10) 10)

true)

; abs-prop1: number -> boolean

; A predicate to check that |x| = x.

(define (abs-prop1 i)

(= (abs i) i))

(check-property 100

abs-prop1

(list (bounded-random-integer 10)))

Copy the code into DrScheme to see that the suspicion is incorrect.

2 Testing abs

The second random-bounded-integer test in the previous section checks a general property of the function’s result, because it cannot predict exactly which integer the function will produce. Another testing strategy is to rewrite random-bounded-integer in such a way that you can predict the exact result.

Rewrite random-bounded-integer to have the contract

  random-bounded-integer: number (number -> number) -> number

The second parameter is a function that random-bounded-integer should use in place of the built-in random for random number generation. Test random-bounded-integer by passing functions produced by make-fake-random as the second argument. Note that random-bounded-integer will still produce truly random results when passed the built-in random, so it remains useful for test case generation.

Next, use check-property to test whether abs has the following property: for any integer i, applying abs to i produces a positive number. (Use positive? to check abs’s result.) If the property turns out to be false, adjust it and test your revised property using check-property.

Note: the functions you write to test properties of other functions (e.g., abs-prop1 for abs) don’t need their own dedicated test cases; using them in the associated check-property is sufficient.

3 Testing Functions on Lists

Using random-integer from Lab 5, write the following function:

  random-list-of-numbers: (number -> number) -> (listof number)

random-list-of-numbers produces a random list of numbers using a strategy similar to the one suggested for random-integer in Lab 5. (That this same idea works for both lists and natural numbers isn’t too surprising, when you remember the data definition for natural numbers).

Next, write insertion sort and use check-property to test that the output is indeed sorted. If check-property finds a list for which your sort function appears to fail, copy the input list from check-property’s output, confirm that it is indeed your sort function – not your function for testing sorted-ness – that is wrong, and construct a check-expect using the failure-inducing list. (Follow this procedure whenever using check-property.)

Finally, write and test quicksort by checking that the result is indeed sorted and has the same length as the input list.

4 Testing closest-to-zero

Write a function to generate random cagey-old-list-of-numberss:

; an cagey-old-list-of-numbers (COLON) is either:

; - (cons number empty)

; - (cons number (cons number COLON))

Use check-property to test whether your implementation of closest-to-zero from the midterm always produces a number that is actually a member of the input COLON. If you already know your implementation has a bug, don’t fix it until random testing uncovers the bug.

(closest-to-zero colon) → number

colon : COLON

to find the number in colon that is closest to 0.