CS 342 Additional Homework for Chapter 4 Due: May 11, 1992 General directions: be sure we have given you some specific help (either in recitation or personally) with each problem before solving these additional problems. 1. (to make up for problem 1, parts (a), (c), (e) on page 148) Do problem 1, parts (b), (f) and (g) on page 148-149. 2. this was extra credit 3. (to make up for problem 2 on page 149) Using the implementations of sets in the Scheme library, program subset*, such that (subset* s1 s2) returns T (true) if each element of s1 is a subset of some element of s2. Naturally, s1 and s2 have to be sets of sets. 4. (to make up for the iterate problem) For this problem, (set false '()) (set true 'T) For this problem you may *NOT* use "while". Define a function "until" that takes two functions with no arguments, The funciton "until" should be such that (until body (lambda (x) true)) returns the result of (body) and in general, (until body condition) equals (begin (set result (body)) (if (condition) result (until body condition))) assuming that the variable "result" is not used in body or condition. For example, (begin (set i 0) (until (lambda () (begin (set i (+ i 1)) i)) (lambda () (> i 3)))) returns 4. As another example (begin (set i 0) (until (lambda () (begin (set i (+ i 1)) i)) (lambda () (< i 0)))) is an infinite loop. 5. (to make up for problem 3 on page 149) A bag (or multi-set) can be described by a ``characteristic function'' (whose range is the natural numbers) that determines how many times an element occurs in the bag. For example, the function phi such that (phi 'coke) = (phi 'pepsi) = 6 and for all other arguments, x, (phi x) = 0 is the characteristic function for a bag containing 6 coke and 6 pepsi (i.e., a 6-pack of each). In the bag phi the ``number of occurrences'' of the symbol coke is 6. Allowing the user to construct a bag from a characteristic function gives one the power to construct bags that may ``contain'' an infinite number of elements (such as the bag in which each prime number n occur n times). Implement bags by implementing the following operations: (with-characteristic f), returns a bag that contains each x (f x) times. (union b1 b2), returns a bag containing all the elements of b1 and b2, where the number of occurrences of x in the result is the sum of the number of occurrences of x in b1 and b2. (intersect b1 b2), returns a bag containing all x such that x is both an element of b1 and of b2, where the number of occurrences of x in the result is the minimum of the number of occurrences of x in b1 and b2. (occurrences b e), returns the number of occurrences of e in b. 6. (to make up for problem 7 on page 150) a. Give a definition of dynamic scoping and static scoping. b. Illustrate your definition with an example that is different from the examples given in the textbook.