Today we're going to see how to implement a new abstraction:  
finite sets of integers.  We'll also see how to define a new
type (i.e., class) in Dylan.

Sets are generally useful for a variety of purposes in CS
  - many algorithms use sets
  - mathematicians use sets

We begin by writing out a contract for our set abstraction:

new type:  <set>

  empty-set -- has type <set> corresponds to {}

  (singleton i)  -- takes an integer i and returns a set corresponding to {i}
                        (i.e., the set that contains the single integer i).
  (union s t)  -- takes two sets and returns their union (s U t).

  (member? i s) -- returns true if i is a member of the set s.

  (filter s p)  -- filters a set using the predicate p.  
                   (filter s p) returns the set t = {i in s | p(i) is #t}

Note that a predicate is just a function that returns either true or
false.

Before we implement the abstraction, we note that we can already define
other set operations in terms of the abstraction.  For instance,
intersection and set-difference can be defined as follows:

;; returns the intersection of the sets s and t
;; i.e., {i in S | i in t}
(define (intersection <function>)
  (method ((s <set>) (t <set>))
    (filter s (method ((i <integer>)) (member? i t)))))

;; returns the set you get from removing all elements in t from s
;; i.e., {i in S | i not in t}
(define (set-difference <function>)
  (method ((s <set>) (t <set>))
    (filter s (method ((i <integer>) (not (member? i t)))))))

Now, how do we implement sets?  We have a variety of options.
One idea is to use lists of integers.  We could do so by 
defining sets as follows:

(define <set> <list>)

(define (empty-set <set>) '())

(define (singleton <function>)
  (method ((i <integer>)) (cons i '())))

(define (union <function>) append)

(define (member? <function>)
  (method ((i <integer>) (s <set>))
    (cond (((null? s) #f)
           ((= i (head s)) #t)
           (else: (member? i (tail s)))))))

(define (filter <function>)
  (method ((s <set>) (p <function>))
    (cond (((null? s) '())
           ((p (head s)) (cons (head s) (filter (tail s) p)))
           (else: (filter (tail s) p))))))

This certainly satisifies the contract.  But why?  After all,
if we calculate (union (singleton 3) (singleton 3)) we get
the list '(3 3) which has 3 in it twice.  However, a client
who's programming in terms of the abstractions alone cannot
_observe_ that 3 is in there twice.  They can only observe
what's in a set using member? and filter (the other functions
just build sets.)  And neither member? nor filter provides
a way to (directly) determine if 3 is in the list representing
the set more than once.

Of course, having duplicates in the list wastes space, though
it makes the implementation of, for instance, union a lot
easier.  An alternative approach is to use lists where no
element is duplicated.  This would save space.

How might we code this?  We only need to change the
definition of union, for this is the only place that
duplicates can arise.  One approach is to filter out
all of the duplicates in the first set before appending
the two sets together.  For instance, we could write:

(define (union <function>)
  (method ((s <set>) (t <set>)) 
     (append (set-difference s t) t)))

Now our implementation satisifies the invariant that
no integer occurs in a set more than once.

But a big drawback now is that we can break the invariant
by passing an arbitrary list to one of the operations 
which has duplicates (or in fact has something besides
an integer.)  How can we prevent this so that we can
maintain the proper invariant?

One approach is to define a new (abstract) type for set.
We can do so as follows:

(define-class <set> (<object>) (elements <list>))

This defines a new class, <set>, with one super-class
(<object>).  This just means that objects that are sets
are also <object>s.  In other words, we can pass a <set>
to anything that only expects an <object>.  The definition
also specifies that <set> values contain one slot
(also known as an instance variable or field).  The
slot is named "elements" and contains a list.

We'll study the more general form for creating classes
later on.

We create objects of type <set> using the operation make,
and by giving an initial value for each of the slots.
For example, we can define empty-set and singleton as
follows:

(define (empty-set <set>) (make <set> elements: '()))

(define (singleton <function>)
  (method ((i <integer>)) (make <set> elements: (cons i '()))))

To define member, we need some way to get at the list
of elements in a set.  We can do so by using the get-slot
operation:

(define (member? <function>)
  (method ((i <integer>) (s <set>))
    (bind-methods ((member-list? ((x <list>))
                     (cond (((null? x) #f)
                            ((= i (head x)) #t)
                            (else: (member-list? (tail x)))))))
      (member-list (get-slot elements: s)))))
                    ^^^^^^^^^^^^^^^^^^^^^
                    Notice the call to get-slot here

Similarly, we can define filter as:

(define (filter <function>)
  (method ((s <set>) (p <function>)
   (bind-methods ((filter-list ((x <list>))
                    (cond (((null? x) '())
                           ((p (head x)) (cons (head x) (filter-list (tail x)))
                           (else: (filter-list (tail x))))))))
      (make <set> elements: (filter-list (get-slot elements: s)))))))

Notice that we must make a new set out of the list of filtered
elements in order to satisfy the contract.

Now we can define intersection and set-difference as before:

(define (intersection <function>)
  (method ((s <set>) (t <set>))
    (filter s (method ((i <integer>)) (member? i t)))))

(define (set-difference <function>)
  (method ((s <set>) (t <set>))
    (filter s (method ((i <integer>) (not (member? i t)))))))

And we can define union as:

(define (union <function>)
  (method ((s <set>) (t <set>))
    (make <set> 
      elements: (append (get-slot elements: (set-difference s t))
                        (get-slot elements: t)))))