9.3. A Set Constructor

This example describes a syntactic extension, set-of, that allows the construction of sets represented as lists with no repeated elements [17]. It uses define-syntax and syntax-rules to compile set expressions into recursion expressions. The expanded code is often as efficient as that which can be produced by hand.

A set-of expression takes the following form.

 (set-of value exp ...)

value describes the elements of the set in terms of the bindings established by the expressions exp …. Each of the expressions exp … can take one of three forms:

An expression of the form (x in s) establishes a binding for x to each element of the set s in turn. This binding is visible within the remaining expressions exp … and the expression value.
An expression of the form (x is e) establishes a binding for x to e. This binding is visible within the remaining expressions exp … and the expression value. This form is essentially an abbreviation for (x in (list e)).
An expression taking any other form is treated as a predicate; this is used to force refusal of certain elements as in the second of the examples below.

 (set-of x   (x in '(a b c))) ⇒ (a b c) (set-of x   (x in '(1 2 3 4))   (even? x)) ⇒ (2 4) (set-of (cons x y)   (x in '(1 2 3))   (y is (* x x))) ⇒ ((1 . 1) (2 . 4) (3 . 9)) (set-of (cons x y)   (x in '(a b))   (y in '(1 2))) ⇒ ((a . 1) (a . 2) (b . 1) (b . 2))

A set-of expression is transformed into nested let, named let, and if expressions, corresponding to each is, in, or predicate subexpression. For example, the simple expression

 (set-of x (x in '(a b c)))

is transformed into

 (let loop ((set '(a b c)))   (if (null? set)       '()       (let ((x (car set)))         (set-cons x (loop (cdr set))))))

The expression

 (set-of x (x in '(1 2 3 4)) (even? x))

is transformed into

 (let loop ((set '(1 2 3 4)))   (if (null? set)       '()       (let ((x (car set)))         (if (even? x)             (set-cons x (loop (cdr set)))             (loop (cdr set))))))

The more complicated expression

 (set-of (cons x y) (x in '(1 2 3)) (y is (* x x)))

is transformed into

 (let loop ((set '(1 2 3)))   (if (null? set)       '()       (let ((x (car set)))         (let ((y (* x x)))           (set-cons (cons x y)                     (loop (cdr set)))))))

Finally, the expression

 (set-of (cons x y) (x in '(a b)) (y in '(1 2)))

is transformed into nested named let expressions:

 (let loop1 ((set1 '(a b)))   (if (null? set1)       '()       (let ((x (car set1)))         (let loop2 ((set2 '(1 2)))           (if (null? set2)               (loop1 (cdr set1))               (let ((y (car set2)))                 (set-cons (cons x y)                           (loop2 (cdr set2)))))))))

These are fairly straightforward transformations, except that the base case for the recursion on nested named let expressions varies depending upon the level. The base case for the outermost named let is always the empty list (), while the base case for an internal named let is the recursion step for the next outer named let. In order to handle this, the definition of set-of employs a help syntactic extension set-of-help. set-of-help takes an additional expression, base, which is the base case for recursion at the current level.

 ;;; set-of uses helper syntactic extension set-of-help, passing it ;;; an initial base expression of '() (define-syntax set-of   (syntax-rules ()     (( e m ...)      (set-of-help e '() m ...)))) ;;; set-of-help recognizes in, is, and predicate expressions and ;;; changes them into nested named let, let, and if expressions. (define-syntax set-of-help   (syntax-rules (in is)     (( e base)      (set-cons e base))     (( e base (x in s) m ...)      (let loop ((set s))        (if (null? set)            base            (let ((x (car set)))              (set-of-help e (loop (cdr set)) m ...)))))     (( e base (x is y) m ...)      (let ((x y)) (set-of-help e base m ...)))     (( e base p m ...)      (if p (set-of-help e base m ...) base)))) ;;; set-cons returns the original set y if x is already in y. (define set-cons   (lambda (x y)     (if (memv x y)         y         (cons x y))))

Exercise 9.3.1.

Write a procedure, union, that takes an arbitrary number of sets (lists) as arguments and returns the union of the sets, using only the set-of syntactic form. For example:

 (union) ⇒ () (union '(a b c)) ⇒ (a b c) (union '(2 5 4) '(9 4 3)) ⇒ (2 5 9 4 3) (union '(1 2) '(2 4) '(4 8)) ⇒ (1 2 4 8)

Exercise 9.3.2.

A single-list version of map can (almost) be defined as follows.

 (define map1   (lambda (f ls)     (set-of (f x) (x in ls)))) (map1 - '(1 2 3 2)) ⇒ (-1 -3 -2)

Why does this not work? What could be changed to make it work?

Exercise 9.3.3.

Devise a different definition of set-cons that maintains sets in some sorted order, making the test for set membership, and hence set-cons itself, potentially more efficient.