Equality and Testing

Next: Intermezzo 3 Local Definitions and Up: Processing Two Complex Pieces Previous: Extended Exercise: Evaluating Scheme

Equality and Testing

Many of the functions we designed produce lists. When we test these functions, we must compare their results with the predicted value, both of which are lists. Comparing lists by hand is tedious and error-prone. Let's develop a function that consumes two lists of numbers and determines whether they are equal:

;; list=? : list-of-numbers list-of-numbers -> boolean
;; to determine whether a-list and another-list  
;; contain the same numbers in the same order 
(define (list=? a-list another-list) ...)

The purpose statement refines our general claim and reminds us that, for example, shoppers may consider two lists equal if they contain the same items, regardless of the order, but programmers are more specific and include the order in the comparison. The contract and the purpose statement also show that list=? is a function that processes two complex values, and indeed, it is an interesting case study.

Comparing two lists means looking at each item in both lists. This rules out designing list=? along the lines of replace-eol-with in section . At first glance, there is also no connection between the two lists, which suggests that we should use the modified design recipe.

Let's start with the table:

tabular20907

It has four cells, which implies that we need (at least) four tests and four cond-clauses in the template.

Here are five tests:

(list=? empty empty)

(not 
  (list=? empty (cons 1 empty)))

(not 
  (list=? (cons 1 empty) empty))

(list=? (cons 1 (cons 2 (cons 3 empty))) 
        (cons 1 (cons 2 (cons 3 empty))))

(not 
  (list=? (cons 1 (cons 2 (cons 3 empty))) 
          (cons 1 (cons 3 empty))))

The second and third show that list=? must deal with its arguments in a symmetric fashion. The last two show how list=? can produce true and false.

Three of the template's four cond-clauses contain selector expressions and one contains natural recursions:

(define (list=? a-list another-list)
  (cond 
    [(and (empty? a-list) (empty? another-list)) ...] 
    [(and (cons? a-list) (empty? another-list)) 
     ... (first a-list) ... (rest a-list) ...] 
    [(and (empty? a-list) (cons? another-list)) 
    ... (first another-list) ... (rest another-list) ...] 
    [(and (cons? a-list) (cons? another-list)) 
     ... (first a-list) ... (first another-list) ... 
     ... (list=? (rest a-list) (rest another-list)) ... 
     ... (list=? a-list (rest another-list)) ... 
     ... (list=? (rest a-list) another-list) ...]))

There are three natural recursions in the fourth clause because we can pair the two selector expressions and we can pair each parameter with one selector expression.

From the template to the complete definition is only a small step. Two lists can contain the same items only if they are both empty or constructed. This immediately implies true as the answer for the first clause and false for the next two. In the last clause, we have two numbers, the first of both lists, and three natural recursions. We must compare the two numbers. Furthermore, (list=? (rest a-list) (rest another-list)) computes whether the rest of the two lists are equal. The two lists are equal if, and only if, both conditions hold, which means we must combine them with an and:

(define (list=? a-list another-list)
  (cond 
    [(and (empty? a-list) (empty? another-list)) true] 
    [(and (cons? a-list) (empty? another-list)) false] 
    [(and (empty? a-list) (cons? another-list)) false] 
    [(and (cons? a-list) (cons? another-list)) 
     (and (= (first a-list) (first another-list)) 
          (list=? (rest a-list) (rest another-list)))]))

The other two natural recursions play no role.

Let us now take a second look at the connection between the two parameters. The first development suggests that the second parameter must have the same shape as the first one, if the two lists are to be equal. Put differently, we could develop the function based on the structure of the first parameter and check structure of the other one as needed.

The first parameter is a list of numbers, so we can reuse the template for list-processing functions:

(define (list=? a-list another-list)
  (cond 
    [(empty? a-list) ...] 
    [(cons? a-list) 
     ... (first a-list) ... (first another-list) ... 
     ... (list=? (rest a-list) (rest another-list)) ...]))

The only difference is that the second clause processes the second parameter in the same way as the first one. This mimics the development of hours->wages in section

Filling the gaps in this template is more difficult than for the first development of list=?. If a-list is empty, the answer depends on another-list. As the examples show, the answer is true if, and only if, another-list is also empty. Translated into Scheme this means that the answer in the first cond-clause is (empty? another-list).

If a-list is not empty, the template suggests that we compute the answer from

(first a-list), the first number of a-list;
(first another-list), the first number on another-list; and
(list=? (rest a-list) (rest another-list)), which determines whether the rest of the two lists are equal.

Given the purpose of the function and the examples, we now simply compare (first a-list) and (first another-list) and combine the result with the natural recursion in an and-expression:

(and (= (first a-list) (first another-list))
     (list=? (rest a-list) (rest another-list)))

While this step appears to be simple and straightforward, the result is an improper definition. The purpose of spelling out the conditions in a cond-expression is to ensure that all selector expressions are appropriate. Nothing in the specification of list=?, however, suggests that another-list is constructed if a-list is constructed.

We can overcome this problem with an additional condition:

(define (list=? a-list another-list)
  (cond 
    [(empty? a-list) (empty? another-list)] 
    [(cons? a-list) 
     (and (cons? another-list) 
          (and (= (first a-list) (first another-list)) 
               (list=? (rest a-list) (rest another-list))))]))

The additional condition is (cons? another-list), which means that list=? produces false if (cons? a-list) is true and (cons? another-list) is empty. As the examples show, this is the desired outcome.

In summary, list=? shows that, on occasion, we can use more than one design recipe to develop a function. The outcomes are different, though closely related; indeed, we could prove that the two always produce the same results for the same inputs. Also, the second development benefited from the first one.

Exercises Exercise 17.8.1

Test both versions of list=?. Solution

Exercise 17.8.2

Simplify the first version of list=?. That is, merge neighboring cond-clauses with the same result by combining their conditions in an or-expression; switch cond-clauses as needed; and use else in the last clause of the final version. Solution

Exercise 17.8.3

Develop sym-list=?. The function determines whether two lists of symbols are equal. Solution

Exercise 17.8.4

Develop contains-same-numbers. The function determines whether two lists of numbers contain the same numbers, regardless of the ordering. Thus, for example,

(contains-same-numbers (list 1 2 3) (list 3 2 1))

evaluates to true. Solution

Exercise 17.8.5

The class of numbers, symbols, and booleans are sometimes called atoms:

An atom is either

a number
a boolean
a symbol

Develop the function list-equal?, which consumes two lists of atoms and determines whether they are equal. Solution

A comparison between the two versions of list=? suggests that the second one is easier to understand than the first. It says that two compound values are equal if the second is made from the same constructor and the components are equal. In general, this idea is a good guide for the development of other equality functions.

Let's look at an equality function for simple Web pages to confirm this conjecture:

;; web=? : web-page web-page -> boolean
;; to determine whether a-wp and another-wp have the same tree shape 
;; and contain the same symbols in the same order 
(define (web=? a-wp another-wp) ...)

Recall the data definition for simple Web pages:

A Web-page (short: WP) is either

empty;
(cons s wp)
where s is a symbol and wp is a Web page; or
(cons ewp wp)
where both ewp and wp are Web pages.

The data definition has three clauses, which means that if we were to develop web=? with the modified design recipe, we would need to study nine cases. By using the insight gained from the development of list=? instead, we can start from the plain template for Web sites:

(define (web=? a-wp another-wp)
  (cond 
    [(empty? a-wp) ...] 
    [(symbol? (first a-wp)) 
     ... (first a-wp) ... (first another-wp) ... 
     ... (web=? (rest a-wp) (rest another-wp)) ...] 
    [else 
     ... (web=? (first a-wp) (first another-wp)) ... 
     ... (web=? (rest a-wp) (rest another-wp)) ...]))

In the second cond-clause, we follow the example of hours->wages and list=? again. That is, we say that another-wp must have the same shape as a-wp if it is to be equal and process the two pages in an analogous manner. The reasoning for the third clause is similar.

As we refine this template into a full definition now, we must again add conditions on another-wp to ensure that the selector expressions are justified:

(define (web=? a-wp another-wp)
  (cond 
    [(empty? a-wp) (empty? another-wp)] 
    [(symbol? (first a-wp)) 
     (and (and (cons? another-wp) (symbol? (first another-wp))) 
          (and (symbol=? (first a-wp) (first another-wp)) 
               (web=? (rest a-wp) (rest another-wp))))] 
    [else 
     (and (and (cons? another-wp) (list? (first another-wp))) 
          (and (web=? (first a-wp) (first another-wp)) 
               (web=? (rest a-wp) (rest another-wp))))]))

In particular, we must ensure in the second and third clause that another-wp is a constructed list and that the first item is a symbol or a list, respectively. Otherwise the function is analogous to list=? and works in the same way.

Exercises Exercise 17.8.6

Draw the table based on the data definition for simple Web pages. Develop (at least) one example for each of the nine cases. Test web=? with these examples. Solution

Exercise 17.8.7

Develop the function posn=?, which consumes two binary posn structures and determines whether they are equal. Solution

Exercise 17.8.8

Develop the function tree=?, which consumes two binary trees and determines whether they are equal. Solution

Exercise 17.8.9

Consider the following two, mutually recursive data definitions:

A Slist is either

empty
(cons s sl) where s is a Sexpr and sl is a Slist.

A Sexpr is either

a number
a boolean
a symbol
a Slist

Develop the function Slist=?, which consumes two Slists and determines whether they are equal. Like lists of numbers, two Slists are equal if they contain the same item at analogous positions. Solution

Now that we have explored the idea of equality of values, we can return to the original motivation of the section: testing functions. Suppose we wish to test hours->wages from section :

  (hours->wages (cons 5.65 (cons 8.75 empty)) 
                      (cons 40 (cons 30 empty))) 
= (cons 226.0 (cons 262.5 empty))

If we just type in the application into Interactions window or add it to the bottom of the Definitions window, we must compare the result and the predicted value by inspection. For short lists, like the ones above, this is feasible; for long lists, deep Web pages, or other large compound data, manual inspection is error-prone.

Using equality functions like list=?, we can greatly reduce the need for manual inspection of test results. In our running example, we can add the expression

(list=? 
  (hours->wages (cons 5.65 (cons 8.75 empty)) 
                      (cons 40 (cons 30 empty))) 
  (cons 226.0 (cons 262.5 empty)))

to the bottom of the Definitions window. When we click the Execute button now, we just need to make sure that all test cases produce true as their results are displayed in the Interactions window.

;; test-hours->wages : list-of-numbers list-of-numbers list-of-numbers -> test-result
;; to test hours->wages 
(define (test-hours->wages a-list another-list expected-result) 
  (cond 
    [(list=? (hours->wages a-list another-list) expected-result) 
     true] 
    [else 
     (list ``bad test result:'' a-list another-list expected-result)]))

Figure: A test function

Indeed, we can go even further. We can write a test function like the one in figure . The class of test-results consists of the value true and lists of four items: the string ``bad test result:'' followed by three lists. Using this new auxiliary function, we can test hours->wages as follows:

(test-hours->wages 
                        (cons 5.65 (cons 8.75 empty)) 
                        (cons 40 (cons 30 empty)) 
                        (cons 226.0 (cons 262.5 empty)))

If something goes wrong with the test, the four-item list will stand out and specify precisely which test case failed.

Testing with equal?: The designers of Scheme anticipated the need of a general equality procedure and provide:

;; equal? : any-value any-value -> boolean
;; to determine whether two values are structurally equivalent  
;; and contain the same atomic values in analogous positions

When equal? is applied to two lists, it compares them in the same manner as list=?; when it encounters a pair of structures, it compares their corresponding fields, if they are the same kind of structures; and when it consumes a pair of atomic values, it compares them with =, symbol=?, or boolean=?, whatever is appropriate.

Guideline on Testing

Use equal? for testing (when comparisons of values are necessary).

Unordered Lists: On some occasions, we use lists even though the ordering of the items doesn't play a role. For those cases, it is important to have functions such as contains-same-numbers (see exercise ) if we wish to determine whether the result of some function application contains the proper items.

Exercises Exercise 17.8.10

Define a test function for replace-eol-with from section using equal? and formulate the examples as test cases using this function. Solution

Exercise 17.8.11

Define the function test-list-pick, which manages test cases for the list-pick function from section . Formulate the examples from the section as test cases using test-list-pick. Solution

Exercise 17.8.12

Define test-interpret, which tests interpret-with-defs from exercise , using equal?. Reformulate the test cases using this function. Solution

Next: Intermezzo 3 Local Definitions and Up: Processing Two Complex Pieces Previous: Extended Exercise: Evaluating Scheme

PLT