- Assigned
- Monday, Sep 17, 2018
- Due
- Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
- Summary
- In the laboratory, you will explore the ways in which small tests can help you develop and update code. You will also familiarize yourself with the RackUnit unit testing library.

a. After starting DrRacket, add the following lines to your definitions pane and click run:

```
#lang racket
(require csc151)
(require rackunit)
(require rackunit/text-ui)
```

b. Read the following procedures to make sure that you understand what they do, and then add the code to your definitions pane.

```
;;; Procedure:
;;; bound-grade
;;; Parameters:
;;; grade, a real number
;;; Purpose:
;;; Bound grade to a number between 0 and 100, inclusive
;;; Produces:
;;; bounded, a real number
;;; Preconditions:
;;; [no additional]
;;; Postconditions:
;;; If 0 <= grade <= 100, bounded is grade.
;;; If grade < 0, bounded is 0.
;;; If grade > 100, bounded is 100.
(define bound-grade
(o (section min <> 100) (section max <> 0)))
;;; Procedure:
;;; drop-to-first-zero
;;; Parameters:
;;; lst, a list of numbers
;;; Purpose:
;;; Removes all of the elements up to and including the first zero.
;;; Produces:
;;; newlst, a list of numbers
;;; Preconditions:
;;; The list contains at least one zero.
;;; Postconditions:
;;; Suppose the first zero is at index z.
;;; (length newlst) = (- (length lst) z 1)
;;; For all i s.t. z < i < (length lst)
;;; (list-ref newlst (- i z 1)) = (list-ref lst z)
(define drop-to-first-zero
(lambda (lst)
(drop lst
(+ 1 (index-of 0 lst)))))
;;; Procedure:
;;; remove-negatives
;;; Parameters:
;;; lst, a list of real numbers
;;; Purpose:
;;; Remove all negative numbers from the list.
;;; Produces:
;;; newlst, a list of real numbers
;;; Preconditions:
;;; [No additional]
;;; Postconditions:
;;; The negative numbers have been dropped. That is, newlst contains
;;; no negative numbers.
;;; All other numbers have been retained. That is, if x appears k times in
;;; lst and x is not negative, then x appears k times in newlst.
;;; No additional numbers are in newlst. That is, if x appears k times in
;;; newlst then x appears k times in lst.
;;; Numbers retain their ordering. That is, if x appears before y in newlst,
;;; then x appeared before y in lst.
(define remove-negatives
(lambda (lst)
(drop-to-first-zero (sort (append (list 0) lst) <))))
```

Consider the preconditions and postconditions of `bound-grade`

. Can you
add any about the exactness or inexactness of the result? For example,
if the input is 50, an exact number, do you also expect the output to
be exact? If the input is -10.2, an inexact number, do you also expect
the output to be exact?

Conduct at least five experiments to verify that `bound-grade`

works
correctly. Your experiments should include

- A negative grade.
- A grade of 0. (We call this an “edge case” because it’s at the border between two different behaviors.)
- A grade somewhere between 0 and 100, exclusive.
- A grade of 100. (Our other edge case.)
- A grade greater than 100.

For example, we might conduct the second experiment as follows.

```
> (bound-grade 0.0)
```

Here is a test suite that includes some of the kinds of experiments you might have conducted.

```
(define tests-bound-grade
(test-suite
"tests of bound-grade"
(test-case "negative grades"
(check-= (bound-grade -3) 0 0)
(check-= (bound-grade -0.0001) 0 0.00000001)
(check-= (bound-grade -23213123) 0 0))
(test-case "zero"
(check-= (bound-grade 0) 0 0)
(check-= (bound-grade 0.0) 0 0))
(test-case "valid grade"
(check-= (bound-grade 42) 42 0)
(check-= (bound-grade 121/8) 121/8 0)
(check-= (bound-grade 0.00001) 0.00001 0.00000001)
(check-= (bound-grade 99.9999) 99.9999 0.00000001))
(test-case "100"
(check-= (bound-grade 100) 100 0)
(check-= (bound-grade 100.0) 100.0 0.00000001))
(test-case "too big"
(check-= (bound-grade 100.1) 100 0)
(check-= (bound-grade 12321312231) 100 0))))
```

a. Run the tests

```
> (run-tests tests-bound-grade)
```

b. Describe, as best you can, what kinds of “edge cases” and other issues this suite seems to be testing.

c. Other than being more comprehensive than your five or so experiments, what do you see as the advantages of this suite?

d. You may recall that `check-=`

permits a fourth parameter, which
explains conceptually what we are checking. Add those explanations.
to three or four of the more interesting checks. For example,

```
(check-= (bound-grade -0.0001) 0 0
"negative number very close to zero")
```

Here is the test suite for `remove-negatives`

that we presented in
the reading.

```
(define test-remove-negatives
(test-suite
"Tests of remove-negative"
(test-case
"small lists"
(check-equal? (remove-negatives (list))
(list)
"empty list")
(check-equal? (remove-negatives (list 3))
(list 3)
"singleton list - positive")
(check-equal? (remove-negatives (list 0))
(list 0)
"singleton list - zero")
(check-equal? (remove-negatives (list -1))
(list)
"singleton list - negative"))
(test-case
"all positive"
(check-equal? (remove-negatives (list 3 7 11))
(list 3 7 11)
"three elements"))
(test-case
"mixed"
(check-equal? (remove-negatives (list -1 3 7 11))
(list 3 7 11)
"negative at front of list")
(check-equal? (remove-negatives (list -1 3 -2 7 -3 11))
(list 3 7 11)
"alternating")
(check-equal? (remove-negatives (list -1 -2 -3 1 -2 -3 2 -3 -4 5))
(list 1 2 5)
"sequences of negatives"))
(test-case
"all negative"
(check-equal? (remove-negatives (list -1 -2 -3))
(list)
"boring"))))
```

a. Do you expect `remove-negatives`

to pass these tests?

b. Check your expectation experimentally. That is, run the tests.

c. Make note of any errors you encountered so that you can address them later. If you don’t encounter any errors, note that instead.

Comment out the definition of `remove-negatives`

. Then add the following
definition.

```
(define remove-negatives
(lambda (lst)
lst)) ; Cross our fingers that there are no negative numbers
```

a. What do you think will happen if we run the test suite using this new definition?

b. Check your answer experimentally.

c. Comment out this new, incorrect, definition and uncomment the previous definition.

As you saw, the test suite is good enough that it catches some errors in a
clearly incorrect implementation. But is it good enough? In particular
given that our original `remove-negatives`

passed all of the tests,
does that mean that we should be confident that it is correct?

What other tests would increase your confidence that `remove-negatives`

is correct? (Spend about three minutes coming up with those tests.)

Let’s consider the postconditions to reflect on whether we need more tests. Here are two postconditions.

```
;;; All other numbers have been retained. That is, if x appears k times in
;;; lst and x is not negative, then x appears k times in newlst.
;;; No additional numbers are in newlst. That is, if x appears k times in
;;; newlst then x appears k times in lst.
```

They basically say that we neither add nor remove numbers. It’s pretty clear that we’re not adding or removing numbers in our examples, since we’re giving an exact explanation of what the result should be. But they also suggest one other thing: The procedure should work if there are multiple copies of a number. Let’s add some more checks.

```
(check-equal? (remove-negatives (list 3 3 3 7 7 7 7 7 7 7 11))
(list 3 3 3 7 7 7 7 7 7 7 11)
"multiple copies")
(check-equal? (remove-negatives (make-list 20 83.5))
(make-list 20 83.5)
"multiple copies of one value")
(check-equal? (remove-negatives (list 1 -2 1 -3 1 2 3 -5 -5 3))
(list 1 1 1 2 3 3)
"multiple copies")
```

a. Do you expect `remove-negatives`

to pass these tests? Why or why
not?

b. Add these checks to the test suite. You might add a new test case for multiple copies or you might add them to the existing test cases. (Please try to keep them in an appropriate test case.)

c. Check your answer experimentally.

Our procedure has passed even more checks. We’re probably feeling pretty good right now. But we shouldn’t be. We’ve missed one important issue. Consider the last postcondition.

```
;;; Numbers retain their ordering. That is, if x appears before y in newlst,
;;; then x appeared before y in lst.
```

In some sense, we did check that postcondition. For example, wehn we
removed values from `(list -1 3 -2 7 -3 11)`

we ensured that
3 came before 7 came before 11 in the resulting list. However, there
is a flaw in all of those tests.

Do you know what it is?

Take a moment to think about it.

Then discuss it with your partner.

Then think another moment.

Then discuss it with your partner.

In case you didn’t figure it out in the previous exercise, here’s the major flaw: In every input, the non-negative numbers were already in order. Let’s create some more tests to see what happens if they are in other orders.

```
(check-equal? (remove-negatives (list 1 2 3 1))
(list 1 2 3 1)
"duplicates, not necessarily in order")
(check-equal? (remove-negatives (list 2 1 3 1))
(list 2 1 3 1)
"duplicates, not necessarily in order")
(check-equal? (remove-negatives (list 3 2 1 1))
(list 3 2 1 1)
"duplicates, in reverse order")
(check-equal? (remove-negatives (list 1 -4 -3 2 -2 3 1))
(list 1 2 3 1)
"duplicates, not necessarily in order")
(check-equal? (remove-negatives (list -5 2 -2 1 3 -1 1))
(list 2 1 3 1)
"duplicates, not necessarily in order")
(check-equal? (remove-negatives (list 3 -2 -2 -2 -2 2 1 1 -8))
(list 3 2 1 1)
"duplicates, in reverse order")
```

a. Do you expect `remove-negatives`

to pass all of these tests?

b. Check your answer experimentally.

`remove-negatives`

As you likely noted, the `remove-negatives`

we wrote did not preserve
the order of elements. Spend no more than five minutes trying to come
up with an approach (not necessarily code) that will preserve the order
of elements.

You’ve seen that it’s worthwhile thinking about additional tests. Before
we consider a possible implementation, write five or so additional tests
that you think will potentially stress `remove-negatives`

in other ways.

Here’s a solution one of the CSC 151 faculty came up with. We’re not sure it’s right.

```
;;; Procedure:
;;; real-part-<?
;;; Parameters:
;;; n1, a number
;;; n2, a number
;;; Purpose:
;;; Determine if the real part of n1 is less than the real part of n2
;;; Produces:
;;; lt?, a Boolean
;;; Preconditions:
;;; No additional
;;; Postconditions:
;;; If the real part of n1 is less than the real part of n2, then
;;; lt? is true (#t)
;;; Otherwise
;;; lt? is false (#f)
;;; Ponderings:
;;; Provides a mechanism for sorting complex numbers
(define real-part-<?
(lambda (n1 n2)
(< (real-part n1) (real-part n2))))
;;; Procedure:
;;; imaginary-part-<?
;;; Parameters:
;;; n1, a number
;;; n2, a number
;;; Purpose:
;;; Determine if the imaginary part of n1 is less than the imaginary part of n2
;;; Produces:
;;; lt?, a Boolean
;;; Preconditions:
;;; No additional
;;; Postconditions:
;;; If the real part of n1 is less than the real part of n2, then
;;; lt? is true (#t)
;;; Otherwise
;;; lt? is false (#f)
;;; Ponderings:
;;; Provides a mechanism for sorting complex numbers
(define imag-part-<?
(lambda (n1 n2)
(< (imag-part n1) (imag-part n2))))
;;; Procedure:
;;; remove-negatives
;;; ...
(define remove-negatives
(lambda (lst)
(map real-part
(sort (drop-to-first-zero
(sort (append (list 0)
(map +
lst
(map (section * <> 0+i)
(iota (length lst)))))
real-part-<?))
imag-part-<?))))
```

Here’s a slightly more readable version, but with less documentation. (Remember that you read Scheme expressions inside-out.)

```
(define remove-negatives
(lambda (lst)
(remove-imag-part
(sort-by-imag-part
(drop-to-first-zero
(sort-by-real-part
(append (list 0)
(annotate-with-indices lst))))))))
; Add indices to the numbers in a list, using the imaginary
; part of the list for the indices.
(define annotate-with-indices
(lambda (lst)
(map +
lst
(map (section * <> 0+i)
(iota (length lst))))))
; Remove the imaginary part of all values in a list.
(define remove-imag-part
(lambda (lst)
(map real-part lst)))
; Sort a list of complex numbers by the real part of each number.
(define sort-by-real-part
(lambda (lst)
(sort lst real-part-<?)))
; Sort a list of complex numbers by the imaginary part of each number.
(define sort-by-imag-part
(lambda (lst)
(sort lst imag-part-<?)))
```

a. Do you think this approach will work?

b. Check your answer experimentally.

c. Explain, in your own words, what this new version is doing. You may find it useful to try each procedure in turn.