In this section we consider another Example, this time with sets. It considers several approaches to abstract data representation. We’re not focusing on symbols now, just considering them as something that we can use. This is an integration of several of the ideas we’ve seen so far.

Given that we’re building a system with an interface that shouldn’t need to change much, this is also a good time to consider how and what we do to test our system as it changes. Instead of just providing tests as a convenience, I think it’s time to examine the tests themselves. If you’ve been wanting more of the reasoning behind why my tests are structured a certain way, this will hopefully be a help, even if it represents a bit more work than just determining what the text expects. If you’re not interested in all that, skip on by it, but make sure to pay attention to the notes in the file, as not all the tests are meant to be mere checks for correctness.

I am trying to stick to the pattern of talking about testing in the ‘exercise’ post, and just solutions in the follow-up post. As this particular discussion of testing involves consideration of all the approaches, it may be easier to understand if you’ve already done some work on the exercises already. So from here in, there will be some knowledge of the exercises assumed.

The first set of tests are included and run before any of the exercises. This is a typical approach for several reasons. Firstly, this ensures for my sake (and yours) that I’ve faithfully copied the procedures from the text. Secondly, simply writing tests can provide insight into how the interface is meant to work. There’s still some potential for error when you get to writing new code, but looking at it from another point of view can often uncover very basic errors and hidden assumptions.

The first few tests use what I’ve called ‘fake’ sets. This is because those sets are built without using the proper method for building a set (i.e. adjoin-set). It doesn’t seem like a problem at first. If sets are just lists, it seems easy enough just to compare them to lists. Of course (spoilers), it clearly is going to become a problem: Later on, we do in fact move away from sets as simple lists.

One way to work around that problem is to create new ‘fake’ sets. That is the approach taken for the element tests, and it works fine. However, an alternate way is seen in the later series of tests. In those, we actually use a let to redefine our test sets within the test function. By building them at the time the test is run, we take advantage of the implementation changes made. As long as we interact with them only using the intended interface procedures, we won’t need to change these tests. What it does require is a function build-set that is changed along with the data representation.

However, we later find that even this approach won’t always let us re-use the tests. In the switch to ordered set data, we can no longer use symbolic data for testing, because our ordering is accomplished using the mathematical operators. That’s a case where we need to rewrite the tests to work with the changes in the implementation. It’s not unlike what happened when switching to infix notation in the previous section on symbolic differentiation.

There is also another place where we must be cautious when generating our test data. By relying on the interface to prepare our expected ‘correct’ values, we have to make sure that the interface itself is working properly. Otherwise the tests will be meaningless or just fail.

For instance, suppose adjoin-set is broken in such a way that it never adds elements, and just produces the empty set. Then there will be likely many tests that fail when they rely on build-set . But what is surprising and worrying is that a whole lot of those tests that depend on it would actually pass. Many tests will happily compare all the empty sets to each other and find them equal! In this case we have to make sure there’s a low-level test on adjoin-set to signal a problem there.

That does mean that, with some mistakes in the program, it won’t always be immediately obvious what caused a whole group of tests to fail. Knowledge of both the system and the means of testing is required to properly interpret test results, failing or passing. While it’s kind of a pain to figure out which simple test is the one to pay attention to, it’s better than not knowing about it at all until the problems are much harder to diagnose. Testing isn’t a way to fix bugs — it’s a means of finding them faster.

There does remain one problem with the set interface as given in the text. There is no easy way to determine what the result of an operation should be. We need to compare expected and actual results to determine if they match. When the sets are just simple lists, equal? works well enough. But what we really need is a procedure and a good definition for set equality, and thus sets-equal? is added.

(define (sets-equal? a b)
  (and (andmap (lambda (x) (element-of-set? x b)) (set->list a)) 
       (andmap (lambda (x) (element-of-set? x a)) (set->list b))
       )
  )

This uses an abstract idea of set equality, taking its cue from the common definition of set equality used in mathematics. Namely, two sets are considered equal only if they are subsets of each other. In other words, every element of set B is a member of set A, and every element of A is a member of set B. The and statement combines those two requirements, and they separately ensure for the two sets that the elements of the other set are elements of themselves. This definition ends up working for all the ways in which sets are represented in this section. While strictly speaking there was no requirement that ‘sets’ as defined in the book must behave that way, it’s not much of a surprise that they do.

That definition makes use of a function andmap, which is not necessarily standard for every Scheme interpreter. It is an accumulation function that tests every member of a list and then condenses it down to a single true (or false statement); it is true only if every member of the list passes that test. While simple, it’s a rather useful function, and I’ve included a version in the exercise file if your interpreter does not have it defined.

The last exercise here has enough room for alternate approaches that there are no testing methods provided. It might well resemble the set implementation, but it’s a case where you can structure the testing and the implementation however you like.

Exercises 2.3.3