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.
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:
- a Rectangle
- a Circle
- 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
for all elements e and sets s?
(boolean=? (element-of? e (remove-element e s)) false)
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
Additional Problem 2:
A relation is a set of tuples, which in turn is a list of symbols:
;; A tuple is (list Symbol Symbol).
(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
(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.