CS 61A Week 1 Lab and Homework Solutions ===FIRST LAB 1A===: 1. Nothing original. 2. If the last letter is Y, then we have to look at the next-to-last: (define (plural wd) (if (and (equal? (last wd) 'y) (not (vowel? (last (bl wd))))) (word (bl wd) 'ies) (word wd 's))) If you didn't think to use AND in that way, it can be done with nested IFs: (define (plural wd) (if (equal? (last wd) 'y) (if (vowel? (last (bl wd))) (word wd 's) (word (bl wd) 'ies)) (word wd 's))) Or, if that's too messy, with a subprocedure: (define (plural wd) (if (equal? (last wd) 'y) (y-plural (bl wd)) (word wd 's))) (define (y-plural prefix) (if (vowel? (last prefix)) (word prefix 'ys) (word prefix 'ies))) All of these assume the definition of vowel? in the handout. 3. There are, of course, many possible ways to write this. None is perfectly elegant. The difficulty is figuring out which of the three arguments is smallest, so you can leave it out of the computation. The way I like best, I think, is a little tricky: (define (sum-square-large papa mama baby) (define (square x) (* x x)) (cond ((> mama papa) (sum-square-large mama papa baby)) ((> baby mama) (sum-square-large papa baby mama)) (else (+ (square papa) (square mama))))) I think this way is pretty concise and easy to read. However, it's okay if you did it more straightforwardly like this: (define (sum-square-large a b c) (define (square x) (* x x)) (define (sumsq x y) (+ (square x) (square y))) (cond ((and (<= a b) (<= a c)) (sumsq b c)) ((and (<= b a) (<= b c)) (sumsq a c)) (else (sumsq a b)) )) If you didn't think of using AND to identify the conditions, it could also be done using nested IFs: (define (sum-square-large a b c) (define (square x) (* x x)) (define (sumsq x y) (+ (square x) (square y))) (if (>= a b) (if (>= b c) (sumsq a b) (sumsq a c)) (if (>= a c) (sumsq a b) (sumsq b c)))) Some people wanted to start by solving a subproblem: a function to find the two largest numbers. This can be done, but it's harder: (define (sum-square-large a b c) (define (square x) (* x x)) (define (sumsq nums) (+ (square (first nums)) (square (last nums)))) (define (two-largest a b c) (cond ((and (<= a b) (<= a c)) (sentence b c)) ((and (<= b a) (<= b c)) (sentence a c)) (else (sentence a b)))) (sumsq (two-largest a b c))) The trick here is that a function can't return two values, so two-largest has to return a sentence containing the two numbers. This hardly seems worth the effort, but the attempt to split the problem into logical pieces was well-motivated. It's a good idea in general, but it didn't work out well this time. See also: http://code.google.com/p/jrm-code-project/wiki/ProgrammingArt ===SECOND LAB 1B===: Problem 2: foo takes a number as input and outputs a number. bar takes a function as input and outputs a function. (bar foo) will return a function. If we call ((bar foo) 2), then certainly we are calling "bar". That's one. (bar foo) will return a new lambda procedure with which we call 2, that's another. When we call that returned lambda procedure, we then have to call the +, that's three. After calling the +, we now have to call foo, that's four total. No, (bar foo) will return (lambda (x) (foo (+ num 2))). And when you call that procedure with 3, you will get (foo 5) which is 10. On the other hand, (baz foo) will return (lambda (x) (+ (fn num) 2)). When you call that procedure with 3, you apply fn first to get 6, and your final answer is 8 by adding the 2 to 6. 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 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 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 # (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 # (((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 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.