diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/61a-pages/Solutions/week2')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/61a-pages/Solutions/week2 | 509 |
1 files changed, 509 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week2 b/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week2 new file mode 100644 index 0000000..6cd2999 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week2 @@ -0,0 +1,509 @@ +CS 61A Week 2 Lab and Homework Solutions + +FIRST LAB: + +Problem 1: + +f Any definition at all will do: + (define f 'hello) f is hello + (define f (+ 2 3)) f is 5 + (define (f x) (+ x 7)) f is #<procedure f> + +(f) This expression says to invoke f as a procedure with no + arguments. For that to work, we must DEFINE f as a procedure + with no arguments: + (define (f) 'hello) (f) is hello + (define (f) (+ 2 3)) (f) is 5 + Each of these is shorthand for an explicit use of lambda: + (define f (lambda () 'hello)) + (define f (lambda () (+ 2 3)) + +(f 3) This expression says to invoke f as a procedure with an + argument, so we have to define it that way: + (define (f x) (+ x 5)) (f 3) is 8 + (define (f x) 'hello) (f 3) is hello + (define (f x) (word x x)) (f 3) is 33 + Again, these definitions are shorthand for lambda expressions: + (define f (lambda (x) (+ x 5))) + (define f (lambda (x) 'hello)) + (define f (lambda (x) (word x x))) + +((f)) This expression says, first of all, to compute the subexpression + (f), which invokes f as a procedure with no arguments. Then, the + result of that invocation must be another procedure, which is + also invoked with no arguments. So, we have to define f as a + procedure that returns a procedure: + (define (f) (lambda () 'hello)) ((f)) is hello + (define (f) (lambda () (+ 2 3))) ((f)) is 5 + Or without the shorthand, + (define f (lambda () (lambda () 'hello))) + (define f (lambda () (lambda () (+ 2 3)))) + Alternatively, we can let the procedure f return some procedure + we already know about, supposing that that procedure can be + invoked with no arguments: + (define (f) +) ((f)) is 0 + (define f (lambda () +)) + As a super tricky solution, for hotshots only, try this: + (define (f) f) ((f)) is #<procedure f> + (((f))) is.... ? + +(((f)) 3) Sheesh! F has to be a function. When we invoke it with no + arguments, we should get another function (let's call it G). + When we invoke G with no arguments, we get a third function + (call it H). We have to be able to call H with the argument 3 + and get some value. We could spell this out as a sequence of + definitions like this: + (define (h x) (* x x)) + (define (g) h) + (define (f) g) (((f)) 3) is 9 + Alternatively, we can do this all in one: + (define (f) (lambda () (lambda (x) (* x x)))) + or without the abbreviation: + (define f (lambda () (lambda () (lambda (x) (* x x))))) + +By the way, you haven't yet learned the notation for functions that accept +any number of arguments, but if you did know it, you could use + (define (f . args) f) +as the answer to *all* of these problems! + + +Problem 2: + +This is a "do something to every word of a sentence" problem, like +PL-SENT or SQUARES, but with two extra arguments. But it +also has a decision to make for each word (is this word equal to the +one we're replacing), like the filtering procedures EVENS, ENDS-E, etc., +so it takes the form of a three-branch COND: + +(define (substitute sent old new) + (cond ((empty? sent) '()) + ((equal? (first sent) old) + (se new (substitute (butfirst sent) old new))) + (else (se (first sent) (substitute (butfirst sent) old new))))) + + +Problem 3: + +Of course you could just try this on the computer, but you should understand +the results. + +(t 1+) means that we should substitute the actual argument, which is the +function named 1+, for t's formal parameter, which is f, in t's body, +which is (lambda (x) (f (f (f x)))). The result of the substitution is + + (lambda (x) (1+ (1+ (1+ x)))) + +Evaluating this produces a function that adds three to its argument, so +((t 1+) 0) is 3. + +(t (t 1+)) means to substitute (t 1+) for f in t's body. If we actually +substituted the lambda expression above for f three times, we'd get a +horrible mess: + + (lambda (x) ((lambda (x) (1+ (1+ (1+ x)))) + ((lambda (x) (1+ (1+ (1+ x)))) + ((lambda (x) (1+ (1+ (1+ x)))) + 0)))) + +but what's important is the function, not the expression that produced +the function, so we can just mentally give (t 1+) the name 3+ and then +the result we want is + + (lambda (x) (3+ (3+ (3+ x)))) + +and if we apply that function to 0 we'll get 9. + +For the final piece of the problem, we have to begin by computing (t t), which +is what we get when we substitute t for f in t's body: + + (lambda (x) (t (t (t x)))) + +Don't be confused! Even though this lambda expression has x as its formal +parameter, not f, the argument has to be a function, because we're going to +end up invoking t on that argument. In other words, (t t) returns as its +value a function that takes a function as argument. + +Now, ((t t) 1+) means to apply the function just above to the argument 1+ +which, in turn, means to substitute 1+ for x in the body: + + (t (t (t 1+))) + +Well, this isn't so hard; we've really already done it. (t 1+) turned +out to be 3+, and (t (t 1+)) turned out to be 9+. By the same reasoning, +this will turn out to be 27+ (that is, 9+ three times), so when we apply +this to 0 we get 27. + +Problem 4: + +This is actually the same as problem 2! The function S is identical to +1+, so the answers have to be the same. It's more work if you actually +substitute values into the body of s, but you can avoid all that if you +realize that these problems are identical in meaning. + +Problem 5: + +If (g) is a legal expression, then g takes ZERO arguments. +If ((g) 1) has the value 3, then (g) has a PROCEDURE as its value. +(If we'd asked for more than one word, you could say "a procedure +of one numeric argument that returns a number" or something.) + + +Problem 6: + +(define (make-tester who) + (lambda (x) (equal? x who))) + + + +HOMEWORK: + +Exercise 1.31(a): + +;; you only needed to hand in one version +;; but by now you're ready to understand both: + +;; recursive version: + +(define (product term a next b) + (if (> a b) + 1 ;; Note multiplicative identity is 1 not 0 + (* (term a) + (product term (next a) next b)))) + +;; iterative version: + +(define (product term a next b) + (define (iter a result) + (if (> a b) + result + (iter (next a) (* result (term a))))) + (iter a 1)) + +;; factorial + +(define (! n) (product (lambda (x) x) 1 1+ n)) + +;; pi +;; You have to run a few hundred terms to get a good approximation. +;; There are several possible ways to arrange the terms. Here is one +;; way, in which the first term is 2/3, the second is 4/3, etc. + +(define (pi terms) (* 4 (product + (lambda (x) (/ (* 2 (1+ (floor (/ x 2)))) + (1+ (* 2 (ceiling (/ x 2)))))) + 1 1+ terms))) + +;; Here is another way, in which the first term is (2/3)*(4/3), the +;; second is (4/5)*(6/5), etc. Notice that the value of a starts at +;; 3 and is increased by 2 for each new term. + +(define (pi terms) (* 4 (product + (lambda (x) (/ (* (-1+ x) (1+ x)) + (* x x) )) + 3 + (lambda (x) (+ x 2)) + terms ))) + +;; If you try to make it 2 * (4/3) * (4/3) * (6/5) * (6/5) * ... you'll +;; get the wrong answer, because you'll have one more number in the +;; numerator than in the denominator. + + + +Exercise 1.32(a): + +;; you only needed to hand in one version + +;; recursive form + +(define (accumulate combiner null-value term a next b) + (if (> a b) + null-value + (combiner (term a) + (accumulate combiner null-value term (next a) next b)))) + +;; iterative form + +(define (accumulate combiner null-value term a next b) + (define (iter a result) + (if (> a b) + result + (iter (next a) (combiner (term a) result)))) + (iter a null-value)) + +;; sum and product + +(define (sum term a next b) (accumulate + 0 term a next b)) + +(define (product term a next b) (accumulate * 1 term a next b)) + + + +Exercise 1.33: + +;; The problem only requires one version but this too can be +;; recursive or iterative. Recursive version: + +(define (filtered-accumulate combiner null-value term a next b predicate) + (cond ((> a b) null-value) + ((predicate a) + (combiner (term a) + (filtered-accumulate combiner + null-value + term + (next a) + next + b + predicate))) + (else (filtered-accumulate combiner + null-value + term + (next a) + next + b + predicate)))) + +;; Iterative version: + +(define (filtered-accumulate combiner null-value term a next b predicate) + (define (iter a result) + (cond ((> a b) result) + ((predicate a) (iter (next a) (combiner (term a) result))) + (else (iter (next a) result)))) + (iter a null-value)) + +;; (a) sum of squares of primes + +(define (sum-sq-prime a b) + (define (square x) (* x x)) + (filtered-accumulate + 0 square a 1+ b prime?)) + +;; (b) product of blah blah, using gcd from page 49 + +(define (prod-of-some-numbers n) + (filtered-accumulate * + 1 + (lambda (x) x) + 1 + 1+ + n + (lambda (x) (= 1 (gcd x n))))) + + +Exercise 1.40: + +(define (cubic a b c) + (lambda (x) (+ (* x x x) (* a x x) (* b x) c))) + + +Exercise 1.41: + +(define (double f) + (lambda (x) (f (f x)))) + + +Why does (((double (double double)) inc) 5) return 21 and not 13? +The crucial point is that DOUBLE is not associative. + +> (((double (double double)) inc) 5) +21 +> ((double (double (double inc))) 5) +13 + +DOUBLE turns a function into one that applies the function twice. +(DOUBLE DOUBLE) turns a function into one that applies the function +four times. +(DOUBLE (DOUBLE DOUBLE)) makes a function that applies (DOUBLE DOUBLE) +twice -- that is, make a function that applies the argument function +four times four times! + + + +Exercise 1.43: + +(define (repeated f n) + (lambda (x) + (if (= n 0) + x + (f ((repeated f (- n 1)) x))))) + +or + +(define (repeated f n) + (lambda (x) + (if (= n 0) + x + ((repeated f (- n 1)) (f x))))) + +or + +(define (repeated f n) + (if (= n 0) + (lambda (x) x) + (lambda (x) (f ((repeated f (- n 1)) x))))) + + +We didn't assign 1.42, but if you followd the hint about it in 1.43, +you'd end up with this: + +(define (repeated f n) + (if (= n 0) + (lambda (x) x) + (compose f (repeated f (- n 1))))) + + +1.46 + +This problem is a little complicated in its details because there are so +many different procedures involved, with different domains and ranges. +But don't let that keep you from seeing the beauty of this extremely +general method! + +(define (iterative-improve good-enough? improve) + (define (iterate guess) + (if (good-enough? guess) + guess + (iterate (improve guess)))) + iterate) + +(define (sqrt x) ;; compare to bottom of page 30 of SICP + ((iterative-improve (lambda (guess) (< (abs (- (square guess) x)) 0.001)) + (lambda (guess) (average guess (/ x guess)))) + 1.0)) + +Some people were confused about sqrt because the original good-enough? takes +two arguments, and iterative-improve only allows for one. But we are using +lexical scope so that the lambda expressions used as arguments to +iterative-improve have access to the starting value x. + +(define (fixed-point f first-guess) ;; compare to page 69 + ((iterative-improve (lambda (guess) (< (abs (- guess (f guess))) tolerance)) + f) + first-guess)) + +Here the structure is a little different from what's in the book, because +there is no variable NEXT to hold the next guess. The solution above computes +(f guess) twice for each guess. If you don't like that, you could use a more +complicated solution in which the argument to the good-enough procedure is a +sentence containing both old and new guesses: + +(define (fixed-point f first-guess) + ((iterative-improve (lambda (guesses) + (< (abs (- (first guesses) (last guesses))) tolerance)) + (lambda (guesses) + (sentence (last guesses) (f (last guesses))))) + (sentence first-guess (f first-guess)))) + +but I don't think the constant-factor efficiency improvement is worth the +added complexity of the code. + + +-------- + +2. EVERY: + +(define (every f sent) + (if (empty? sent) + '() + (se (f (first sent)) + (every f (butfirst sent)) ))) + + +-------- + +Extra for experts: + +This is a really hard problem! But its solution comes up enough in the +literature that it has a name: the Y combinator. First here's the +combinator alone: + +(lambda (f) (lambda (n) (f f n))) + +And here's the factorial function using it: + +( (lambda (f) (lambda (n) (f f n))) + (lambda (fun x) + (if (= x 0) + 1 + (* x (fun fun (- x 1))))) ) + +And now here's (fact 5): + +( ( (lambda (f) (lambda (n) (f f n))) + (lambda (fun x) + (if (= x 0) + 1 + (* x (fun fun (- x 1))))) ) + 5) + +The trick is that instead of the factorial function taking a number as an +argument, it takes TWO arguments, a function (which will really be itself when +called) and a number. The recursive call is done using the function provided +as argument. + +The job of the Y combinator is to provide the function with itself as an +argument. + +If that seems like a rabbit out of a hat, here's a longer explanation: + +The problem we're trying to solve is that factorial wants to be able to call +itself recursively, and to do that it has to have a name for itself. We have +two ways to give something a name, and one of them, DEFINE, is ruled out in +this problem. That leaves procedure invocation, which associates formal +parameters (the names) with actual arguments (the values). So we could +do this: + +((lambda (f n) (if (= n 0) 1 (* n (f f (- n 1))))) + (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1))))) + 5) + +to get the factorial of 5. Ordinarily we think of factorial as a function +of one argument (N); here we've added a formal parameter F whose value is +another copy of the same function. If you work through this expression, +you'll see that the first copy is called only for N=5; the other calls for +all smaller values of N use the second copy, because (unlike the first) it +is called with *itself* (the very same lambda-created procedure) as its +argument. + +Now, it's a little ugly having to type the procedure twice. Also, I sort of +half lied when I said there are only two ways to give something a name. +There's a kind of third way, LET, although that's really the same as creating +and calling a procedure; and LET is good at avoiding having to type something +twice. So you might be tempted to say + +(let ((fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))) + (fact 5)) + +But this doesn't work, because the name "fact" doesn't mean that lambda- +created procedure when the lambda expression is evaluated; that association +holds only in the body of the let. If that isn't clear, we can expand it: + +((lambda (fact) (FACT 5)) + (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) + +The capitalized FACT above is inside the lambda of which fact is the formal +parameter, so the (lambda (n) ...) procedure is substituted for it. But the +name "fact" also appears on the second line of the expression, in the actual +argument expression, and *that* isn't inside the (lambda (fact) ...), so +there is no substitution; it will look for a global name fact. Thus we have +to have F (in the original solution above) take *itself* as an argument, so +that the substitution happens in the right place. We could do that with a +LET form equivalent to the original solution: + +(let ((f (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1))))))) + (f f 5)) + +This one does work. Notice that the body of the let, (f f 5), is almost +like the Y combinator's body, except that the latter generalizes to a +function of N instead of having 5 built in, like this LET expression: + +(let ((f (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1))))))) + (lambda (n) (f f n))) + +Now just rearrange this to eliminate the LET abbreviation: + +((LAMBDA (F) (LAMBDA (N) (F F N))) + (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1)))))) + +This returns a function of N, the factorial function. And the capitalized +part is the Y combinator. |