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)))))