Keith's Amazingly Supplementary Quiz One Review =============================================== ********************** READ THIS FIRST!!! ********************** The information in this packet is intended to SUPPLEMENT your studying. You should look through the practice problems beforehand to get a quick idea of what the questions will be like. And after you've studied everything, you can test your overall knowledge in specific areas. If you think doing all these problems will get you an A, think again. Old problems are just that: OLD problems. They have no bearing whatsoever, guard up or not, when you come up against NEW problems. Glance first, if you wish, but do your studying, then work through the stuff in here. If you have any questions about stuff in here, come talk to me...even if it's after the test, seeing as how there IS a final. (But don't think about it, yet. Forget I said it!) Bear in mind that many of these problems are very hard; there may even be some that would take you a considerable amount of time to work out. Don't panic should this be the case: while most of these are representative of actual "quiz problems", there are some that are just meant to get you thinking. (Usually these are examples from the text book, or from class.) Finally, don't think even for a second you'll be able to do ALL of the problems in this packet. In fact, that's not even the point. Find the areas you are weakest in, and work on selected problems in that section. Try not to spend too much time just idly doing problems if you can't extract the *concepts* they are trying to teach you. You have been warned. Do your best, sleep the night before, don't cram, and don't worry...good luck! ******************** HEY--DID YOU READ IT?! ******************** OVERVIEW Important things to know: 1. Scheme Other things to know: 1. Lambda substitution model, behavior of special forms 2. Recursion vs. iteration 3. Orders of growth: time and space 4. Higher order procedures 5. Box & pointer diagrams, your buddies cons, car, cdr, list, and append 6. Higher order list manipulation procedures 7. Abstraction ideas (including the pattern matcher from Problem Set 4!) 8. How to bribe your TA later ("Mmmmmm...dooo-nuts!!") LAMBDA SUBSTITUTION 1. The following are valid SCHEME expressions typed into a SCHEME read-eval-print prompt. For each one, write in the space provided what SCHEME will print in response. a. ==> ((lambda (x) 3) 7) b. ==> ((lambda (x f) (f (f x))) 3 (lambda (y) (+ y y))) c. ==> (let ((a 3)) (let ((a 4) (b a)) (list a b))) d. ==> ((lambda (+ x y) (+ y x)) / 3 6) e. ==> ((lambda () 3)) f. ==> (define one 'singleton) ==> (define okay 1) ==> (define all-right 2) ==> (define (careful a b c) (if a (b) (c))) ==> (careful (eq? one 'one) (lambda () 'okay) (lambda () all-right)) g. ==> ((lambda (a b) (b 3 a)) (lambda (x y) (+ 5 x)) (lambda (x y) (- 5 x))) h. ==> ((lambda (a b c d e) (cond ((= d 0) (a e 2)) ((= d 1) (b e 2)) ((= d 2) (c e 2)))) + * / 1 6) i. ==> ((lambda (a b) (b a)) 2 (lambda (x) (lambda (y) (+ x y)))) j. ==> (((lambda (x y) (lambda (f) (f x y))) 'a 'b) (lambda (x y) y)) 2. In Scheme, ``if'' and ``cond'' do very similar things. In fact, we might be tempted to define ``if'' as a procedure in terms of ``cond''. Consider the following definition: (define (new-if test-expr then-expr else-expr) (cond (test-expr then-expr) (else else-expr))) We also define ``(show x)'' to do the same thing as ``(write-line x)'', but make sure that it returns ``x''. (Remember that in many versions of Scheme, ``write-line'' returns [#undefined-value], or some similar unprintable object.) (define (show x) (write-line x) x) a. Assume that this particular version of Scheme evaluates its arguments left to right. What is printed when the following expressions are evalated by Scheme? 1. ==> (new-if (> 3 5) (show 'true) (show 'false)) 2. ==> (new-if 6 'true 'false) 3. ==> (define printing-if (lambda (test-expr) (new-if test-expr 'true (show 'false)))) ==> (printing-if (= 5 5)) b. Using our same ``new-if'', assume that we evaluate: (define (smart-/ x y) (new-if (zero? y) (write-line "attempted divide by zero") (/ x y))) What happens when we then evaluate ``(smart-/ 6 0)'' ? 3. For each definition below, give an expression involving an application of ``foo'' that evaluates to the number 6. In your expression, the only subexpressions that may appear as the operator subexpression of a compound expression are ``foo'', a primitive Scheme procedure, or a bound lambda variable. a. (define foo (lambda (x) (* 3 x))) b. (define foo (lambda (x) (x 2))) c. (define foo (lambda (x) (cond ((eq? (x) 'six) 6) (else false)))) d. (define foo (lambda (x) (x (lambda (y) (* y 2))))) e. (define foo (lambda () (let ((six (lambda () 6))) six))) RECURSIVE VS. ITERATIVE PROCESSES 1. The sine of a positive angle (specified in radians) can be computed by making use of the approximation sin(x) ~= x if x is sufficiently small, and the trigonometric identity: 3 sin(x) = 3*sin(x/3) - 4*sin (x/3) to reduce the size of the argument of sin. For purposes of this problem, an angle is considered "sufficiently small" if it is not greater than 0.1 radians. These ideas are incorporated in the following procedures: (define (cube x) (* x x x)) (define (poly x) (- (* 3 x) (* (cube x) 4))) (define (sine angle) (if (not (> angle 0.1)) angle (poly (sine (/ angle 3))))) a. How many times is the procedure poly applied when evaluating (sine 12.15)? b. What is the order of growth in space (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated? [Note: You can come back to this later, if you haven't studied orders of growth, yet... :^) ] In the final part of this problem, you will be asked to complete the definition of a procedure that generates an iterative process when computing the sine of an angle. This procedure definition is to be based on the following observation: Any positive angle a>=0 can be expressed as a = r * 3^p, where p is the smallest integer such that 3^p >= 10a, and 0<=r<=0.1 You are to define procedures power and res such that (power a) evaluates to p, and (res a) evaulates to r, e.g.: (power 0) -----> 0 (res 0) -----> 0 (power 0.05) --> 0 (res 0.05) --> 0.05 (power 0.1) ---> 0 (res 0.1) ---> 0.1 (power 2.7) ---> 3 (res 2.7) ---> 0.1 (power 3.0) ---> 4 (res 3.0) ---> 0.037037 ... c. Complete the definitions of procedures power and res in the space below. The processes which result from application of the procedures you define should be ITERATIVE. (define (power a) (define (res a) d. Complete the definition of the sine-i procedure below by filling in the expressions {a}, {b}, {c}, {d}, {e}, and {f} in the space provided. sine-i should approximate the sine of arbitrary positive angles (specified in radians) using the same trigonometric reduction employed in the sine procedure defined above, but it should generate an iterative process. You may use the procedures cube, poly, power, and res without defining them. (define (sine-i angle) (define (iter count result) (if (< count {a}) {b} (iter {c} {d}))) (iter {e} {f})) {a}: {b}: {c}: {d}: {e}: {f}: 2. In order to test out his understanding of Scheme for Quiz I, 6.001 student Sam N. Ticks [I hate these names...] decides to write a factorial procedure in as many different ways he can dream up. Below are thirteen of the procedures Sam thought of. For each procedure: o If the procedure is SYNTACTICALLY correct, state whether the procedure generates a recursive or an iterative process. o If the procedure computes factorials correctly, say so. o If the procedure doesn't work, describe what happens when the interpreter evaluates (FACT 5). a. (define (fact n) (define (loop num ans) (if (= num 0) 1 (loop (- num 1) (* num ans)))) (loop n 1)) b. (define (fact n) (define (loop num ans) (if (= num 0) 1 (* num (loop (- num 1) ans)))) (loop n 1)) c. (define (fact n) (define (loop num ans) (if (= num 0) ans (loop (- num 1) (* ans num)))) (loop n 1)) d. (define (fact n) (let ((result (fact (- n 1)))) (if (= num 0) 1 (* n result)))) e. (define (fact n) (define (loop num ans) (if (= num 0) ans (loop (= num 1) (* ans num))))) f. (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) g. (define (fact n) (define (loop num ans) (if (= n 0) ans (loop (- num 1) (* ans num)))) (loop n 1)) h. (define (fact n) (if (= n 0) 1 (let ((result (fact (- n 1)))) (* n result)))) i. (define (fact n) (define (loop num ans) (if (= num 0) answer (loop (- num 1) (* ans num)))) (loop n 1)) j. (define (fact n) (define (loop num ans) (if (= num 0) ans (loop num (* ans num)))) (loop n 1)) k. (define (fact n) (if (= n 0) 1 (let ((result (fact (- n 1)))) result))) l. (define (fact n) (define (loop num ans) (if (= num 0) ans (loop (- num 1) (* ans n)))) (loop n 1)) m. (define (fact n) (define (loop num ans) (if (= num 0) ans (loop (- num 1) ans))) (loop n 1)) ORDERS OF GROWTH 1. For each of the expressions below, fill in a,b,c,d,e, or f to indicate the smallest order of growth from the list below which applies: a. n^2 + 2n + 3 ____ c. n^2 + 2^n ____ b. 3n ____ d. lg (n^2) + lg n ____ (a) lg n (b) n lg n (c) n^2 (d) n^2 + n (e) n (f) 2^n 2. Determine the orders of growth in time and space for each of the following procedures. Bonus points if you trace through them with a sample call to verify. [Watch out! The last few get tricky!!] a. (define (blah n) (if (= n 0) 0 (+ 1 (blah (- n 1))))) b. (define (pow n) (define (iter x ans) (if (= x 0) ans (iter (- x 1) (+ 1 ans)))) (iter n 0)) c. (define (wham x) (cond ((= n 0) 0) ((even? n) (+ 1 (wham (/ n 2)))) (else (+ 1 (wham (/ (- n 1) 2)))))) d. (define (bam x) (cond ((= n 0) 0) ((even? n) (bam (/ n 2))) (else (bam (/ (- n 1) 2))))) e. (define (biff n) (if (= n 0) 0 (biff (- n 1)))) f. (define (fool n) (define (iter x) (if (= x 0) 0 (+ 1 (iter (- x 1))))) (iter n)) g. (define (thunk n) (if (= n 0) 0 (+ 1 (thunk (- (fool n) 1))))) h. (define (zap n) (if (= n 0) 1 (+ (zap (- n 1)) (zap (- n 1))))) 3. [Save this one until you've done list procedures, if you haven't yet.] Here are three possible implementations of how to extract the last element of a list: (define (last-1 lst) (if (null? (cdr lst)) (car lst) (last-1 (cdr lst)))) (define (last-2 lst) (nth (- (length lst) 1) lst)) (define (last-3 lst) (if (= (length lst) 1) (car lst) (last-3 (cdr lst)))) Assume the definitions of nth and length are just as you know them (ie: they needn't be re-written here...) a. Alyssa P. Hacker claims that these three procedures will take noticeably different amounts of time on long lists. Rank order the three procedures, from fastest to slowest: ____ fastest ____ middle ____ slowest b. For each of the three procedures, indicate the order of growth in time, as a function of the length of the list. You may choose from O(1), O(log n), O(n), O(n^2), and O(2^n). last-1: last-2: last-3: c. Repeat part b. for order of growth in space. last-1: last-2: last-3: HIGHER ORDER PROCEDURES 1. For each of the following expressions, indicate whether the outermost lambda is an example of a higher order procedure. You may assume that the procedure is to be applied in an error-free manner. Yes No ___ ___ a. (lambda (x y) (x y)) ___ ___ b. (lambda (x y) (lambda () (+ x y))) ___ ___ c. (lambda (x y) (+ x y)) ___ ___ d. (lambda (x y) ((lambda (f) (f x y)) +)) 2. Consider the following procedure definitions: (define compose (lambda (f g) (lambda (x) (f (g x))))) (define try (lambda (f n) (if (= n 0) (lambda (z) z) (compose f (try f (- n 1)))))) Indicate what will happen, or what will be returned, when each of the following expressions is evaluated: a. (try (* x 10) 5) b. (try (lambda (x) (* x 10)) 5) c. ((try (lambda (x) (* x 10)) 3) 5) d. (try compose 5) e. ((try compose 5) 3) f. Bonus question: If we were to change the testing expression in try from (= n 0) to (= n 1), what else would we have to modify in the procedure? 3. The following procedure ``accumulate'' applies a `term' procedure to each item in a list `lst' and combines the results by successively applying a `combiner' procedure, beginning with a given `null-value': (define (accumulate combiner null-value term lst) (if (null? lst) null-value (combiner (term (car lst)) (accumulate combiner null-value term (cdr lst))))) a. Essex Prussian asks Alyssa P. Hacker (ugh!!) to define a procedure ``cube-list-and-sum-squares'' that takes a list as an argument and returns a list of two elements: 1) a list of the cubes of the elements in the original list, and 2) the sum of the squares of the elements in the original list. e.g.: (cube-list-and-sum-squares '(1 2 3 4)) ==> ((1 8 27 64) 30) Alyssa defines the procedure straightforwardly as follows: (define (cube-list-and-sum-squares-1 lst) (list (map cube lst) (accumulate + 0 (lambda (n) n) (map square lst)))) Essex, who is a stickler about efficiency, notes that Alyssa's procedure works, but that it cdr's down the original list three times: once for each map, and once for accumulate. Essex asks Alyssa to write a version of cube-list-and-sum-squares that will only cdr down the given list once. Help her out by filling in the following code skeletion: (define (cube-list-and-sum-squares lst) (if (null? lst) ________________________________________________________ (let ((rec-result (cube-list-and-sum-squares (cdr lst)))) ________________________________________________________ ________________________________________________________ ________________________________________________________ ________________________________________________________))) b. Alyssa realizes later that she could satisfy Essex's efficiency criterion by writing cube-list-and-sum-squares directly in terms of acumulate. Show below what Alyssa has in mind: (define (cube-list-and-sum-squares1 lst) (accumulate ______________________________________________ ______________________________________________ ______________________________________________ lst)) c. During her lunch break, Alyssa gets a revelation, and realizes that map can also be redefined in terms of accumulate. Fill in the blank space on her napkin: (define (map func lst) (accumulate ______________________________________________ ______________________________________________ ______________________________________________ ______________________________________________)) 4. Horner's rule is a method for evaulating a polynomial 2 n-1 n a + a x + a x + ... + a x + a x 0 1 2 n-1 n for a given value of the variable x. The idea is to structure the computation as: a + x (a + x (a + x (... + (a + x a )...))) 0 1 2 n-1 n In other words, we multiply a(n) by x, add a(n-1), multiply the result by x, add a(n-2), and so on, until we reach a(0). Suppose that we represent polynomials as lists of n+1 elements, representing the coefficients ordered from a(0) to a(n). For example, the list (17 -10 0 3) represents the polynomial: 3 3x - 10x + 17 a. Complete the definition of the following procedure, which takes a polynomial and a number, and uses Horner's Rule to compute the value of the polynomial at that number: (define (horner poly x) (if (null? poly) ___________________________________________________ (____________ (car poly) ____________ (cdr poly) ____________))) b. Complete the following alternative definition of horner, which uses the accumulate procedure above: (define (horner poly x) (accumulate ______________________________________________ ______________________________________________ ______________________________________________ ______________________________________________)) 5. Consider this slightly more generic, non-list-oriented version of the accumulate procedure: (define (make-accumulator combiner initial-value) (lambda (a next b) (lambda (proc) (define (iter index result) (if (> index b) result (iter (next index) (combiner result (proc index))))) (iter a initial-value)))) Making use of this procedure, define a procedure w of one argument, n, that computes the following function of n, defined for n>=2: 2 2 2 2 / 4x6x8x...x2n \ 2 4 x6 x8 x...x(2n) w(n) = | ------------------ | = ---------------------- \ 3x5x7x...x(2n-1) / 2 2 2 2 3 x5 x7 x...x(2n-1) (You may use the square procedure w/o defining it, but must define any other procedures you use.) 6. a. Suppose we are given a numerical procedure ``f'' of one argument. We can approximate the derivative of ``f'' by the following mathematical approximation: df(x) f(x+dx) - f(x) ----- ~= -------------- dx dx where ``dx'' is some small constant. Write a procedure ``deriv'' that takes as argument a procedure ``f'' of one argument, and a spacing ``dx'', and returns a procedure for the approximation ``df(x)/dx''. For example, if we do: ==> (define g (deriv square .01)) then ==> (g 1) 2.01 ==> (g 2) 4.01 b. To get the nth derivative of a function ``f'', we can build on the idea of ``deriv''. Write a recursive proceudre that takes as input a procedure ``f'', an integer ``n'', and a spacing ``dx'', and returns a procedure that approximates the nth derivative of f. You may assume that ``deriv'' works as specified. (Do this without using ``repeat'' from earlier.) c. A Taylor series is a way of approximating a function, given by the following formula: 2 2 3 3 df(0) x d f(0) x d f(0) x f(x) ~= f(0) + ----- -- + ------ -- + ------ -- + ... dx 1! dx^2 2! dx^3 3! You are to write a procedure ``taylor'' that takes as arguments a procedure ``f'', a value ``n'', and a spacing ``dx''. It is to return a procedure that approximates ``f'' using the above formula, for the first ``n'' terms, where f(0) is the zeroth term, xdf(0)/dx is the first term, etc. You should do this using ``nth-deriv'' and you may also assume that ``expt'' and ``fact'' are available. For example, if we define: (define sin-approx (taylor sin 4 0.01)) then we should be able to use ``sin-approx'' as a numerical procedure of one argument that approximates the sine function, for example, by calling ``(sin-approx .5)'' or ``(sin-approx .9)''. d. Another way of implementing ``nth-deriv'' is to use the idea of repeating a procedure application. Consider the following code: (define (repeat f n) (if (= n 0) (lambda (z) z) (compose f (repeat f (- n 1))))) (define (compose f g) (lambda (x) (f (g x)))) One of the following definitions uses this idea to implement ``nth-deriv''. Circle the number of the correct definition: 1. (define (nth-deriv f n dx) (repeat deriv n)) 2. (define (nth-deriv f n dx) (repeat (deriv f dx) n)) 3. (define (nth-deriv f n dx) (repeat (lambda (h) (deriv h dx)) n)) 4. (define (nth-deriv f n dx) ((repeat (lambda (h) (deriv h dx)) n) f)) 5. (define (nth-deriv f n dx) ((repeat deriv n) f)) BOX & POINTER DIAGRAMS, LIST/PAIR BASICS 1. Suppose we have typed the following expression into Scheme: (define p (cons 'q (list (list '(p r) 'q)))) a. Draw the box and pointer diagram for p. b. Suppose we have typed the following expression into Scheme (define g (list 1 (+ 2 3) '(3 (+ 5 7)) 5)) Write all the distinct expressions involving g that evaluate to the number 5. The only procedures in these expressions should be car's and cdr's, AND they should contain no special forms. 2. Consider the following definitions: (define p (list cons +)) (define q '(cons +)) (define r (list 'cons '+)) Draw box & pointer diagrams, and give the Scheme result of each of the following expressions: a. ((car p) 3 4) b. ((cadr p) 3 4) c. ((car r) 3 4) d. ((cadr q) 3 4) 3. For each of the following, draw a representative BPD, and give a valid Scheme expression that will evaluate to the value 3. a. (cons 1 (cons 2 (cons 3 4))) b. (list 1 2 (cons 3 6)) c. (cons (list 2 1) (cons 4 3)) d. (append (list 1 2 3) (list 4 (cons 5 6))) e. (append (list 5) (list '(4 (list 3) (list 2)) 1 (cons -1 -2))) 4. (Some potluck questions:) 1. (cddadr ): (a) is equivalent to (cdr (car (cdr (cdr )))) (b) is an illegal expression in Scheme (c) is a special form (d) none of the above 2. Which of these statements evaluates to zero? (a) (if (eq? (list 'pizza) (list 'pizza)) 0 1) (b) (if 'false 0 1) (c) both a and b (d) neither a nor b 3. Which of the following statements is true? (a) (quote foo) is equivalent to '(foo) (b) (car ''(foo)) is foo (c) (car ''(foo)) is quote (d) none of the above HIGHER ORDER PROCEDURES REVISITED 1. Consider the following implementations of the ``reverse'' function, which reverses the elements of a list. For each one, explain why it doesn't work, and the easiest way to fix it. (a) (define (reverse-1 lst) (cond ((null? lst) nil) (else (reverse-1 (cdr lst)) (cons (car lst) (cdr lst))))) (b) (define (reverse-2 lst) (cond ((null? lst) nil) (else (cons (reverse-2 (cdr lst)) (car lst))))) (c) (define (reverse-3 lst) (rev-iter x '())) (define (rev-iter x acc) (if (null? x) '() (rev-iter (cdr x) (cons (car x) acc)))) 2. Consider the following implementations of a ``sort'' procedure, which are also broken. Each is expected to sort a list of numbers and return a new list whose elements are in increasing order. For each procedure, choose the best answer from the following choices for describing its behavior. (They may be used more than once.) 1. Procedure correctly sorts a list. 2. Procedure will fail on lists of length 1. 3. Procedure may enter an infinite loop. 4. Procedure produces some other error. 5. Procedure produces a sorted list as output, but some of the elements of the input list may be missing. 6. Procedure only guarantees that the largest element is at the end of the list. 7. Procedure only guarantees that the smallest element is at the beginning of the list. (a) (define (f1 lst) (cond ((null? lst) '()) ((null? (cdr lst)) lst) ((> (car lst) (cadr lst)) (cons (cadr lst) (f1 (cons (car lst) (cddr lst))))) (else (cons (car lst) (f1 (cdr lst)))))) (b) (define (f2 lst) (let ((lng (length lst))) (define (aux ls n) (if (= n 0) ls (aux (f2 ls) (- n 1)))) (aux lst lng))) (c) (define (f3 lst) (cond ((null? lst) '()) ((null? (cdr lst)) lst) ((> (car lst) (cadr lst)) (f3 (cdr lst))) (else (cons (car lst) (f3 (cdr lst)))))) (d) NOTE: ``Filter'' takes a predicate and a list as arguments, and returns the list of all the elements in the original list for which the predicate is true. See ABSTRACTION IDEAS/#6 for more. (You should be able to implement it fairly easily, but it isn't necessary to do so to do this problem; only to know how it works.) (define (f4 lst) (cond ((null? lst) '()) (else (let ((test (car lst))) (let ((up (filter (lambda (x) (> x test)) (cdr lst))) (down (filter (lambda (x) (<= x test)) (cdr lst)))) (append (f4 down) (cons test (f4 up)))))))) 3. Define map, which takes a function, and a list of numbers, and returns a list, whose elements are the values of the function applied to each of the numbers in the original list, e.g.: (map square '(1 4 5)) ==> (1 16 25) 4. Define a procedure apply-all, which takes a two lists of proceures, one of procedures, and another of numbers, and returns a list, whose elements are the values of the all of functions applied left-to-right to each of the numbers in the original list, e.g.: (apply-all (list square (lambda (z) (/ z 2)) 1+) (list 2 4 6)) ==> (3 9 19) 5. Define a procedure apply-all-to-all, which takes two lists, as does apply-all, but returns a *list of lists*, where each list represents each successive function applied to each of the elements in the second list, e.g.: [Bonus points if you can do it without using map....] (apply-all-to-all (list square 1+ even?) (list 2 5 6)) ==> ((4 25 36) (3 6 7) (#T () #T)) 6a. What is the result of evaluating the following expression? (map (lambda (x) (cons '+ x)) '((2 3) (4 5))) 6b. The mystery procedure is defined as: (define (mystery a b) (map (lambda (i) (map (lambda (j) (cons i j)) b)) a)) What is the result of evaluating (mystery '(- /) '((18 3) (20 4)))? 7. Write the procedure make-counter, which creates a procedure that takes a number n and returns a list of numbers counting down from n to 1, e.g.: ((make-counter) 5) ==> (5 4 3 2 1) . 8. Write the procedure deep-reverse, which, like reverse, reverses the elements of a list, but also reverse the elements of SUB-lists, e.g.: (deep-reverse '((1 (2 3)) 4 5)) ==> (5 4 ((3 2) 1)) 9. You have already seen the idea of using ``map'' to apply a procedure to a list of elements, thereby generating a new list of transformed elements. For some computations, however, it is useful to keep track of some state variables, upon which the computation of the next value in the list depends. Consider the following procedure that maps a GENERATOR down a list of elements, while passing along a set of intermediate state variables needed as part of the computation: (define (map-with-state generator next-state state lst) (if (null? lst) '() (cons (generator (car lst) state) ; create new element (map-with-state generator ; proc. for generating elts next-state ; proc. for updating state (next-state (car lst) state) ; new state (cdr lst))))) ; move down list For example, if we wanted to take a list of numbers as input, and return a new list in which each entry is the sum of the numbers up to that point in the first list, we could use: (map-with-state + + 0 '(1 2 3 4)) which would return the list (1 3 6 10). a. Given the following procedure for generating a list of integers: (define (ints-between a b) (if (> a b) '() (cons a (ints-between (+ a 1) b)))) write a procedure, using ``map-with-state'', that returns a list of the first n factorials, {1!,2!,...,n!}. Do this without using the function ``factorial''. b. Now suppose that we want to take a list of numbers as input, and return a new list where the ith element is the square of the difference be- tween the ith and i-1st elements of the input list (the first element of the output list should just be the square of the first element of the input list.) For example, applying the procedure to the list (1 3 2 4 7) should return the list (1 4 1 4 9). Using ``map-with-state'', write such a procedure: c. The Fibonacci numbers are defined by the following recurrence relation: { 0 n=0 f(n) = { 1 n=1 { f(n-1) + f(n-2) n>=2 We can generate a list of Fibonacci numbers using the idea of ``map-with-state.'' Complete the definition below so that ``n-fibs'' returns a list of Fibonacci numbers, {f(2),f(3),...,f(n)}: (define (n-fibs n) (map-with-state ________________________________________ ;; need to supply THREE args here ________________________________________ ________________________________________ ________________________________________ ________________________________________ ________________________________________ (ints-between 2 n))) ;; last of 4 args ABSTRACTION IDEAS 1. SHORTIES: Choose the BEST answer for each of the following questions: (i) In the Henderson picture language (described in leture and on Problem Set 3), primitive painters are represented as scheme procedures. this has the advantage that: 1. the means of abstraction can also be defined as scheme procedures. 2. painters can draw on non-rectangular frames. 3. the means of combination become easy to implement. 4. the means of combination can be recursive. 5. painters can be based on two-dimensional images as well as on line drawings. (ii) coercion is the process of: 1. forcing a procedure to take other procedures as arguments. 2. forcing data objects like rational numbers to reduce themselves to simplest possible terms. 3. forcing a data abstraction of one type to masquerade as a different type. 4. forcing a painter to draw itself inside a particular sized frame. 5. forcing every expression to return a value. 2. using the pattern matcher of problem set 4, we can attempt to match the following patterns with the expression ``(the black female population)''. in each case, indicate whether the pattern matches. If yes, what are the matches for the pattern variables? if no, what doesn't match? a. (the (? x) (? y) population) b. (the (?? x) population) c. (the (? x) population) d. (the (?? x) (?? y) population) 3. In Problem Set 4, you examined a database of census data, using a set of data abstractions provided for you. In this question, we explore a simple implementation of some of those abstractions. Remember that a ``block'' contained information about house-value, rent, persons-per-unit, and race-sex. Suppose we use the following constructor to create a block record: (define make-record list) and that we use the following constructor to create a field (one of ``house-value'', etc.): (define (make-field label data) (list label data)) For example, we might build a block record using: (define b (make-record (make-field 'house-value hvals) (make-field 'rent rvals) (make-field 'persons-per-unit pvals) (make-field 'race-sex rsvals))) where ``hvals'', ``rvals'', ``pvals'', and ``rsvals'' are some unspecified data structures. a. Draw a box and pointer diagram that represents ``b''. You may simply represent ``hvals'', ``rvals'', ``pvals'', and ``rsvals'' by enclosing each name in a circle, since we haven't specified their actual representation. (Note that this represents an abstraction violation, but the point is to look below the abstraction barrier in this case.) b. Corresponding to our constructors, we need some selectors. Corresponding to a field, we need a selector ``field-label'' that extracts the label of the field, and a selector ``field-data'' that extracts that actual data of the field. Define these: (define field-label ) (define field-data ) Since a record consists of a number of fields, we need two selectors: ``record-first-field'' should extract the first field in the record, and ``record-rest-fields'' should return a record containing all but the first field. We also need a predicate ``record-empty?'' that indicates whether there are any remaining fields in the record. Define these: (define record-first-field ) (define record-rest-fields ) (define record-empty? ) c. In the problem set, we used selectors such as ``pop-data/house-value'' to get the field corresponding to the house value data out of a record. Write the selector ``pop-data/house-value'' which takes as input a record and returns the data of the field with label ``house-value''. In our implementation, we can't rely on fields being stored in any particular order. In manipulating fields and record you may ONLY use the selectors and constructors defined above. (define (pop-data/house-value b) ) d. Our selectors for fields have a very similar structure, so we can generalize our method for constructing such selectors. Write a pro- edure called ``make-field-extractor'' that takes as input a label for a field, and returns as output a selector that will extract that data. For example, your procedure should support the following behavior: (define pop-data/house-value (make-field-extractor 'house-value)) Write your procedure here: (define (make-field-extractor name) ) e. Much of the manipulation we did on our data records involved things like summing up the number of units in a block that satisfied some test, e.g.: (sum-selected-record-fields (pop-data/house-value block) house-value-desc-list (lambda (x) (< 100 x 200))) returned the number of houses in ``block'' with value between 100,000 & 200,000 dollars. Remember that ``house-value-desc-list'' was given by: (define house-value-desc-list (list 0 15 20 25 30 35 40 45 50 60 75 100 125 150 175 200 250 300 400 500)) Similarly, we had: (define rent-desc-list (list 0 100 150 200 250 300 350 400 450 500 550 600 650 700 750 1000)) and we could use: (sum-selected-record-fields (pop-data/rent block) rent-desc-list (lambda (x) (< x 500))) to get the number of rental units in the block for which the monthly rent is less than 500 dollars. We have not yet specified the actual data representation to be used for the ``data'' portion of a field, e.g.: the actual representation of the number of rental units in each category. Suppose we decide to represent the ``data'' as an ordered list, where each entry in the list corresponds to the corresponding entry in the description list. For example, if ``data'' is the list (20 10 30 ...) then there are 20 houses with value between 0 and 14,999 dollars, 10 houses with value between 15,000 and 19,999 and so on. Fill in the blanks below to complete the definition for ``sum-selected- record-fields'' that will correctly use this representation: (define (sum-selected-record-fields data desc pred) (cond ((null? data) __________________________________________ __________________________________________) ((pred (car desc)) ; know this is a list (+ _______________________________________ _______________________________________ _______________________________________)) (else _______________________________________ _______________________________________ _______________________________________))) 4. A binary mobile consists of two branches, a left branch, and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We will represent a binary mobile as a pair of branches: (define (make-mobile left right) (cons left right) We will represent a branch as a list of two elements: a length (which must be a number) and a submobile, which may be either a number (representing a single weight) or another mobile: (define (make-branch len submobile) (list len submobile)) a. Supply the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch. Also, define a predicate single-weight? which tests if a mobile is a single weight. b. Using your selectors, define the procedure total-weight that returns the total-weight of a binary mobile. c. A mobile is said to be balanced if: a) the length of the left branch multiplied by the total weight hanging from the left branch is equal to the length of the right branch multiplied by the total weight hanging from the right branch, and b) each of the submobiles hanging off its branches is balanced. Define a predicate that tests whether a binary mobile is balanced. d. Suppose we consider a full binary mobile, that is, one in which each level is full of only submobiles, except the bottom level, which contains only weights. If we evaluate total-weight on such a mobile, what is the order of growth of the procedure, both in tme and in space, measured in terms of the number of levels n of the mobile? e. Suppose the representation of mobiles is changed so that the constructors are now: (define (make-mobile left right) (list left right)) (define (make-branch len submobile) (cons len submobile)) how much do you need to change your programs to convert to the new representation? 5. An ordered set is an ordered sequence of objects, with constructor adjoin-set, selectors first-elt and rest-elts, a base abstraction the-empty-set, and a test for the base abstraction empty-set?. The contract associated with the abstraction is: For any object x and any ordered set s, then: o (first-elt (adjoin-set x s)) returns the value of x, and o (rest-elts (adjoin-set x s)) returns the value of s. Given below are three different representations of ordered sets. For each one, we have provided the definition of the constructor adjoin-set. You are to supply the corresponding definitions of the selectors first-elt and rest-elts. a. Representation 1: (define (adjoin-set x s) (cons s x)) (define (first-elt s) ________________________ ) (define (rest-elts s) ________________________ ) b. Representation 2: (define (adjoin-set x s) (list x s)) (define (first-elt s) ________________________ ) (define (rest-elts s) ________________________ ) c. Representation 3: (define (adjoin-set x s) (lambda (m) (cond ((eq? m 'first) x) ((eq? m 'rest) s) (else (error "not a set"))))) (define first-elt s) ________________________ ) (define rest-elts s) ________________________ ) d. The procedure process-two-sets takes as arguments a procedure p, together with two ordered sets A and B, that have the same number of elements. It returns a new ordered set whose ith element is p(Ai,Bi), that is, p applied to the ith element of A and the ith element of B. For example, if A={1,2,3}, B={10,20,30}, and p is addition, then process-two-sets should return the set {11,22,33}. Complete the following definition of process-two-sets. Be sure to define and use correct data abstractions, so your definition will work with any valid representation of ordered sets: (define (process-two-sets set1 set2 combining-operation) ) 6. Flower-expert is a procedure that carries on a dialogue of the following kind (what the user types is printed in capital letters): ==> (FLOWER-EXPERT) (what color flower?) RED rose (what color flower?) YELLOW daffodil (what color flower?) SPOTTED unknown (what color flower?) RED carnation (what color flower?) WHITE rose and so on. The proecdure uses a list called field-guide, which matches flowers and their colors. Note that a kind of flower may appear more than once if the flower can have more than one color: (define field-guide '((rose red) (rose white) (daffodil yellow) (carnation red) (carnation pink))) Here is the flower-expert procedure: (define (flower-expert) (define (flower-loop flower-data) (display '(what color flower?)) (let ((color (read))) (let ((result (flower-find color flower-data))) (display result) (flower-loop flower-data)))) (flower-loop field-guide)) The main work of this procedure is done by flower-find, which returns a randomly chosen flower that has the desired color. Flower-find uses the procedure filter. Filter takes a predicate and a list as arguments, and returns the list of all the elements in the original list for which the predicate is true. Flower-find also uses the procedure pick-random, which picks a random item from a given list. a. Complete the following definition of flower-find by filling in the missing expressions: (define (flower-find color data) (let ((possible (filter ____________________________________ data))) (if (null? possible) 'unknown (____________________________________)))) b. Describe how to change the program so that when it can't find a flower of the desired color, it asks the user for the name of a flower of that color, which it will then remember. The program should work like this: ==> (FLOWER-EXPERT) (what color flower?) RED rose (what color flower?) SPOTTED (sorry i dont know that) (please type in the name of a spotted flower) LILY (what color flower?) RED carnation (what color flower?) SPOTTED lily and so on. In your answer, you should explain in detail how you would change any of the above procedures, as well as describe any new procedures you will need to write. (If you describe changes to a procedure, you need not recopy the entire procedure--just show the changed parts.) c. Suppose we now want to write the procedure filter, which takes a predicate and a list as arguments, and returns the list of all the elements in the original list for which the predicate is true. Write a version of filter that engenders a recursive process AND one that engenders an iterative process. (define (filter proc lst) ;; RECURSIVE ) (define (filter proc lst) ;; ITERATIVE ) 7. Now that you've implemented filter...consider these three procedures: o filter-no-duplicates is like filter, except that each item appears at most once in the result list, regardless of how many times it appears in the input list. The order of the elements in the resulting list does not matter. For example: (filter-no-duplicates odd? '(1 2 1 3 4 5 5 6 7 8 5)) could return (1 3 5 7) or (3 5 1 7), etc. o filter-tree takes two inputs--a predicate and a tree (that is, a list of lists). Filter-tree returns the list of those atoms in the tree for which the predicate is true. The order of the elements in the resulting list does not matter, but each element should appear in the list the same number of times as it appeared in the tree. For example, (filter-tree odd? '(1 ((2 1) 3 4) 5 (((5) 6 7 8) 5))) could return (1 1 3 5 5 7 5) or (3 5 5 5 7 1 1), etc. o Filter-tree-no-duplicates is like filter-tree, except that each item appears at most once in the result list, regaredless of how many times it appears in the input list. For example, when called on the list above, it would return (1 3 5 7) or (3 5 7 1), etc. For the remainder of this problem, you are to implement these three procedures. However, we do NOT want you to implement them independntly as three separate, monolithic procedures. Instead, we want you to decide upon a couple of meaningful pieces from which these three procedures can be implemented, then implement these pieces as procedures, and then implement the three procedures in terms of these pieces. (You may also use filter as a piece without re-defining it.) For each of the pieces that you implement, provide a clear specification of what it is supposed to do (one or two sentences). 8. Using the square-limit language... a. Consider the implementations used in Problem Set 3 for representing frames and vectors. One of the procedures you used, called ``beside'', took two painters (procedures) as arguments, and returns a new painter that contained the two original ones placed side by side in the same frame. Fill in the missing code below to recreate this procedure: (define (beside painter1 painter2) Data Structures: (lambda (frame) ================ (painter1 (make-frame frame: make-frame, frame-origin, frame-edge1, ______________________________ frame-edge2 ______________________________ vectors: make-vect, vector-xcor, vector-ycor ______________________________ operations: vector-add, ______________________________ vector-sub, vector-scale ______________________________ ______________________________ ______________________________)) (painter2 (make-frame ______________________________ ______________________________ ______________________________ ______________________________ ______________________________ ______________________________ ______________________________)) b. Now use this procedure and the analogous ``below'' (which takes ``painter1'' and ``painter2'', and produces ``painter1'' below ``painter2'') to recreate the ``right-split'' and ``up-split'' procedures, demonstrated in lecture: (define (right-split painter n) (define (right-split painter n) (if (= n 1) (if (= n 1) ____________________________ ____________________________ ____________________________ ____________________________ ____________________________ ____________________________ ____________________________ ____________________________ ____________________________ ____________________________ ____________________________)) ____________________________)) 9. How to write a program that will generate English sentences.... We will represent a sentence as consisting of a noun phrase and a verb phrase. A noun phrase will consist of either a noun, or an adjective followed by a noun phrase. A verb phrase will consist of either a verb or a verb followed by an adverb. Representing words as Lisp symbols, we can define a dictionary of words, stored in a list, as follows: (define noun-list (list 'dog 'cat 'professor 'student 'rat)) (define verb-list (list 'ran 'ate 'slept 'drank)) (define adjective-list (list 'red 'slow 'dead)) (define adverb-list (list 'quickly 'happily 'well)) Phrases can be represented as lists of words; for example, (ate) and (ate quickly) are verb phrases, and (professor) and (slow dead professor), are noun phrases. Now, we can construct procedures noun-phrase and verb-phrase, which generate noun and verb phrases, to construct sentences, as follows: ==> (define (sentence) (append (append '(the) (noun-phrase)) (verb-phrase))) sentence ==> (sentence) (the cat slept quickly) ==> (sentence) (the dead professor drank well) In order to facilitate selecting elements at random, you can use the pick-random procedure you saw in problem set 4: (define (pick-random lst) (nth (random (length lst)) lst)) a. So, the problem: how can we write the procedures noun-phrase and verb-phrase? To start, write a procedure called noun (with no parameters) that selects a noun from noun-list at random. Do the same for the other parts of speech. b. For a little more help, let's add the procedure either, which takes as arguments two procedures with no parameters, and at random calls either one or the other of them: (define (either a b) (if (= (random 2) 0) (a) (b))) Now, using this procedure, you should be able to write the procedure verb-phrase, which returns a list representing a verb phrase. Then do the same for noun-phrase. c. Supposing we want to expand this system so it also includes transitive and intransitive verbs. Describe what modifications you would make to the procedures we have already, and what you would have to write in addition.