Homework 9: Set Intersection

Assigned: Friday, February 23, 2007
Due: Friday, March 2, 2007 (Extended)

Summary: In this assignment, you will further explore issues pertaining to documentation, testing, and recursive procedures.

Purpose: To give you experience writing tests and documentation for an audience (me). To practice precondition checking.

Expected Time: One to three hours.

Collaboration: You may work in a group of any size between two and four, inclusive. You may consult others outside your group, provided you cite those others. You need only submit one assignment per group.

Submitting: Email me your work, using a subject of CSC151 Homework 9.

Warning: So that this exercise is a learning assignment for everyone, I may spend class time publicly critiquing your work.

Assignment

After graduation, you and your colleagues move to Schemeville to found a new company, Sets-R-Us. Your business plan is to develop a library of procedures for set manipulation and sell it to Scheme programmers all over the world (or maybe just computer science professors at Grinnell College). You know that you need thorough documentation and reliable code for your product to sell.

You decide to begin with the set intersection operation. You need to write a procedure, (intersect left right), that takes two lists of symbols as parameters and returns a list of which the elements are precisely those symbols that appear in both left and right. Although left and right might include duplicate symbols, the result of evaluating (intersect left right) should not.  

Note that the above description of intersect does not specify the order in which the symbols will occur in the result; your tests should not assume a particular order.  (In particular, you may use the test-permutation! procedure to test your code.)

1. The above description of the intersect procedure is clearly casual. Write formal documentation for intersect, using the six P's.

2. Write a test suite that will help you and your colleagues test for errors in an implementation of intersect. Note that you should be relatively confident that anything that passes your test suite is correct. (You might also want to be able to use this test suite to convince potential customers that your implementation is correct!)

   The test suite should use the unit-test.ss library for testing.

3. Finally, write your own version of intersect. If the user calls your procedure in ways that do not satisify the preconditions, your procedure should give a helpful error message. If you use the husk-and-kernel style (and I encourage you to do so), hide the kernel using letrec or named let.

Helpful Hints

Testing list operations with test-permutation!


The unit testing framework includes another keyword we haven't used yet: test-permutation! This lets you make sure an expression yields a list containing the correct items, but it doesn't care what order the items are in.

Here is a sample test suite using test-permutation!:

(load "/home/davisjan/csc/151/examples/unit-test.ss")
(begin-tests!)
(define one-to-five (list 1 2 3 4 5))
(test-permutation! (list 1 2 3 4 5) one-to-five)
(test-permutation! (list 1 3 5 2 4) one-to-five)
(test-permutation! (reverse one-to-five) one-to-five)
(test-permutation! (cdr one-to-five) one-to-five)     ; Should fail: missing an element
(test-permutation! null one-to-five)                  ; Should fail: missing all elements
(test-permutation! (list 6 5 1 4 2 3) one-to-five)    ; Should fail: extra element
(end-tests!)

The first three tests should succeed, because the expression to be tested gives a list that contains the elements 1, 2, 3, 4, and 5, even though they are not necessarily in that order. The rest of the tests should fail. (Of course, you shouldn't write tests that you expect to fail; I'm just trying to show you how test-procedure! works.)

What actually happens?  Let's see:

6 tests conducted.
3 tests failed.
No errors encountered.
3 other tests failed to give the expected result:
  For (cdr one-to-five) expected [(permutation-of (1 2 3 4 5))] got [(2 3 4 5)]
  For null expected [(permutation-of (1 2 3 4 5))] got [()]
  For (list 6 5 1 4 2 3) expected [(permutation-of (1 2 3 4 5))] got [(6 5 1 4 2 3)]
Sorry.  You'll need to fix your code.
> 

Yes, that is what I expected to happen.

The member? predicate

You will likely find it helpful to use a member? predicate, which you should have seen already. If you have difficulty finding your definition, here is one you may use (with proper attribution).

;;; Procedure:
;;;   member?
;;; Parameters:
;;;   val, a Scheme value
;;;   lst, a list of values
;;; Purpose:
;;;   Determine whether val appears in lst.
;;; Produces:
;;;   is-a-member, a Boolean
;;; Preconditions:
;;;   (none)
;;; Postconditions:
;;;   If there exists a position, p, such that
;;;     (equals? val (list-ref lst p))
;;;   then is-a-member is #t.
;;;   If there is no such position, then is-a-member is #f.
;;; Author:
;;;   Samuel A. Rebelsky
(define member?
  (lambda (val lst)
    (and (not (null? lst))
         (or (equal? val (car lst))
             (member? val (cdr lst))))))

Important Evaluation Criteria

In evaluating your work, I will ask myself, "Would I buy this code?" I will emphasize (a) the clarity and precision of your documentation, (b) the thoroughness of your tests, and (c) the correctness of your implementation.

I also plan to run most all the tests submitted on all of the implementations submitted. The authors of the test suites that correctly reject the most implementations are likely to receive some extra credit, as are the authors of the implementations that pass all of the test suites (including mine).

And yes, if you all write procedures that pass all of the correct test suites (including mine), then it is likely that you will all receive extra credit.