Due date: 9/20 @ 5:00 pm

The goal of this problem set is to practice data-centric programming (also known as "structural recursion") using structures, lists, S-expressions, recursive data definitions.

Use the HtDP Intermediate Student programming language.

Warning: This problem set is labor-intensive for those of you who have little or no practice with Scheme programming.

EoPL Problems:

1.15 (1,2,8,9); 1.16 (1,2,3,4,5); 1.17 (1:see below); 1.18

---

Additional Problem 0:

Here is a recursively defined class of data:

(define-struct rectangle (x y width height))
(define-struct circle (x y radius))
(define-struct combination (top bot))

A Shape is one of:

1. a Rectangle
2. a Circle
3. a Combination of two Shapes: (make-combination Shape Shape)

A Rectangle is (make-rectangle Number Number Number Number).

A Circle is (make-circle Number Number Number).

Design the function area, which consumes a shape and computes the area that it covers (counting overlaps twice).

Design inside. The function consumes a shape and two numbers, which denote a position. It determines whether this position is inside the given shape (not on the border).

Design the function bb, which consumes a Shape and produces a bounding box. The latter is the smallest rectangle that includes the entire shape (overlapping broders).

---

The following additional problems should recall basic things about sets, finite functions (table), and relations. We will rely on those and a few more when we formulate operational semantics for programming languages.

Additional Problem 1:

A set is a collection of Xs that are all mutually distinct. The Xs are called elements.

You can represent a set of symbols as a list of symbols such that all symbols are pairwise not eq?.

Design the function element-of?, which determines whether a given element is in a given set.

Design the function add-element, which consumes a symbol and a set and constructs a new set that includes this symbol.

Design the function remove-element, which removes a given symbol from a given set. Hint: Is it always true that

 (boolean=? (element-of? e (remove-element e s)) false)

for all elements e and sets s?

Design the function union, which creates a set from the elements of two given sets.

Design the function intersect, which creates a set from the elements that are common to two given sets.

You can use your functions with arbitrary lists of symbols, such as '(a b a b), that are not representations of sets. What can go "wrong" when you do that? How could you ensure in Scheme that nobody ever "abuses" your functions in this manner?

Additional Problem 2:

A relation is a set of tuples, which in turn is a list of symbols:

;; A tuple is (list Symbol Symbol). 
;; Example:
(define a-tuple '(a b))

;; A relation is a set of tuples.

Design the function domain, which collects all firsts from a given relation in a set.

Design the function range, which collects all seconds from a given relation in a set.

Design the function at. It consumes a set Sand a relation R. Its purpose is to collect all the seconds from all tuples in R whose first is a member of S.

Design the function x. It consumes two sets and creates a relation that combines all elements from the first set with all elements from the second set. Example:

(equal? (x '(a b) '(x y z))
        '((a x) (a y) (a z) (b x) (b y) (b z)))

A relation is a function if every element in the domain is related to exactly one element in the range. Design the function function?, which consumes a relation and determines whether it is a function.

Additional Problem 3:

A finite function (or table) with respect to some universe set U is a relation R whose domain is a finite subset of U and for which we can always computationally pick an element in U that is not an element of the domain of R. Our representation of relations is naturally a representation of finite relations. If we choose the natural numbers N as the universe, we can make this representation a representation of finite functions.

Design the function next. It consumes a finite relation that relates natural numbers to symbols. It produces a natural number that is not in the domain of the given relation.

Design the function allocate. It consumes a symbol S and a finite relation R that relates natural numbers to symbols. It produces a relation that relates all elements in the domain of R to the same symbol as R and a natural number that doesn't occur in the domain of R to S.