1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
|
<P>
<A NAME="alonzo"></A>
<P>
<CENTER><IMG SRC="../ss-pics/alonzo.jpg" ALT="figure: alonzo"></CENTER><P><CENTER>Alonzo Church
<BR>inventor of lambda calculus
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 9: Lambda</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 9</H2>
<H1>Lambda</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../simply.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew
Wright</A><BR>University of California, Santa Barbara</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/ssch09.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../ssch8/higher.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="bridge.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT
Press web page for <CITE>Simply Scheme</CITE></A>
</TABLE></TABLE>
<HR>
<A NAME="g1"></A>
<P>Let's say we want to add three to each of the numbers in a sentence. Using
the tools from Chapter 8, we would do it like this:
<P><PRE>(define (<A NAME="g2"></A>add-three number)
(+ number 3))
(define (<A NAME="g3"></A>add-three-to-each sent)
(every add-three sent))
> (add-three-to-each '(1 9 9 2))
(4 12 12 5)
</PRE>
<P>It's slightly annoying to have to define a helper procedure <CODE>add-three</CODE> just so we can use it as the argument to <CODE>every</CODE>. We're
never going to use that procedure again, but we still have to come up with a
name for it. We'd like a general way to say "here's the function I want
you to use" without having to give the procedure a name. In other words,
we want a general-purpose procedure-generating procedure!
<P><CODE>Lambda</CODE> is the name of a special form that generates procedures. It
takes some information about the function you want to create as arguments
and it returns the procedure. It'll be easier to explain the details after
you see an example.
<P><PRE>(define (add-three-to-each sent)
(every <U>(lambda (number) (+ number 3))</U> sent))
> (add-three-to-each '(1 9 9 2))
(4 12 12 5)
</PRE>
<P>The first argument to <CODE>every</CODE> is, in effect, the same procedure
as the one we called <CODE>add-three</CODE> earlier, but now we can use it without
giving it a name. (Don't make the mistake of thinking that <CODE>lambda</CODE> is
the argument to <CODE>every</CODE>. The argument is <EM>the procedure returned
by</EM> <CODE>lambda</CODE>.)
<P>Perhaps you're wondering whether "lambda" spells something backward.
Actually, it's the name of the Greek letter L, which looks like
this: λ. It would probably be more sensible if <CODE>lambda</CODE>
were named
something like <CODE>make-procedure</CODE>, but the name <CODE>lambda</CODE> is
traditional.<A NAME="text1" HREF="lambda#ft1">[1]</A>
<P>Creating a procedure by using <CODE>lambda</CODE> is very much like creating one
with <CODE>define</CODE>, as we've done up to this point, except that we don't
specify a name. When we create a procedure with <CODE>define</CODE>, we have to
indicate the procedure's name, the names of its arguments (i.e., the formal
parameters), and the expression that it computes (its body). With <CODE>lambda</CODE> we still provide the last two of these three components.
<P>As we said, <CODE>lambda</CODE> is a <A NAME="g4"></A><A NAME="g5"></A>special form. This means, as you
remember, that its arguments are not evaluated when you invoke it. The
first argument is a sentence containing the formal parameters; the second
argument is the body. What <CODE>lambda</CODE> returns is an unnamed procedure.
You can invoke that procedure:
<P><PRE>> ((lambda (a b) (+ (* 2 a) b)) 5 6)
16
> ((lambda (wd) (word (last wd) (first wd))) 'impish)
HI
</PRE>
<P>In real life, though, you're not likely to create a procedure with <CODE>lambda</CODE> merely to invoke it once. More often, we use <CODE>lambda</CODE> as in the
first example in this chapter, to provide a procedure as argument to a
higher-order function. Here are some more examples:
<P><PRE>> (every (lambda (wd) (se (first wd) wd (last wd)))
'(only a northern song))
(O ONLY Y A A A N NORTHERN N S SONG G)
> (keep (lambda (n) (member? 9 n)) '(4 81 909 781 1969 1776))
(909 1969)
> (accumulate (lambda (this that)
(if (> (count this) (count that)) this that))
'(wild honey pie))
HONEY
> (keep (lambda (person) (member? person '(john paul george ringo)))
'(mick smokey paul diana bill geddy john yoko keith reparata))
(PAUL JOHN)
> (keep (lambda (person) (member? 'e person))
'(mick smokey paul diana bill geddy john yoko keith reparata))
(SMOKEY GEDDY KEITH REPARATA)
</PRE>
<P><H2>Procedures That Return Procedures</H2>
<P>An even more powerful use of <CODE>lambda</CODE> is to provide the value returned
by some procedure that you write. Here's the classic example:
<P><PRE>(define (<A NAME="g6"></A>make-adder num)
(lambda (x) (+ x num)))
> ((make-adder 4) 7)
11
> (every (make-adder 6) '(2 4 8))
(8 10 14)
</PRE>
<P>The value of the expression <CODE>(make-adder 4)</CODE> is a <EM>procedure,</EM> not a number. That unnamed procedure is the one that adds 4 to
its argument. We can understand this by applying the substitution model to
<CODE>make-adder</CODE>. We substitute <CODE>4</CODE> for <CODE>num</CODE> in the body of <CODE>make-adder</CODE>; we end up with
<P><PRE>(lambda (x) (+ x 4))
</PRE>
<P>and then we evaluate that expression to get the desired procedure.
<P>Here's a procedure whose argument is a procedure:
<P><PRE>(define (<A NAME="g7"></A>same-arg-twice fn)
(lambda (arg) (fn arg arg)))
> ((same-arg-twice word) 'hello)
HELLOHELLO
> ((same-arg-twice *) 4)
16
</PRE>
<P>When we evaluate <CODE>(same-arg-twice word)</CODE> we substitute the procedure
<CODE>word</CODE> for the formal parameter <CODE>fn</CODE>, and the result is
<P><PRE>(lambda (arg) (word arg arg))
</PRE>
<P>One more example:
<P><PRE>(define (<A NAME="g8"></A>flip fn)
(lambda (a b) (fn b a)))
> ((flip -) 5 8)
3
> ((flip se) 'goodbye 'hello)
(HELLO GOODBYE)
</PRE>
<P><H2>The Truth about <CODE>Define</CODE></H2>
<P>Remember how we said that creating a procedure with <CODE>lambda</CODE> was a lot
<A NAME="g9"></A>
like creating a procedure with <A NAME="g10"></A><CODE>define</CODE>? That's because the notation
we've been using with <CODE>define</CODE> is an abbreviation that combines two
activities: creating a procedure and giving a name to something.
<P>As you saw in Chapter 7, <CODE>define</CODE>'s real job is to give a name
to some value:
<P><PRE>> (define pi 3.141592654)
> (* pi 10)
31.41592654
> (define drummer '(ringo starr))
> (first drummer)
RINGO
</PRE>
<P>
When we say
<P><PRE>(define (square x) (* x x))
</PRE>
<P>it's actually an abbreviation for
<P><PRE>(define square (lambda (x) (* x x)))
</PRE>
<P>In this example, the job of <CODE>lambda</CODE> is to create a procedure
that multiplies its argument by itself; the job of <CODE>define</CODE> is to name
that procedure <CODE>square</CODE>.
<P>In the past, without quite saying so, we've talked as if the name of a
<A NAME="g11"></A>
procedure were understood differently from other names in a program. In
thinking about an expression such as
<P><PRE>(* x x)
</PRE>
<P>we've talked about substituting some actual value for the <CODE>x</CODE>
but took the <CODE>*</CODE> for granted as meaning the multiplication function.
<P>The truth is that we have to substitute a value for the <CODE>*</CODE> just as we
do for the <CODE>x</CODE>. It just happens that <CODE>*</CODE> has been predefined to
have the multiplication procedure as its value. This definition of <CODE>*</CODE>
is <EM>global,</EM> like the definition of <CODE>pi</CODE> above. "Global" means
<A NAME="g12"></A>
<A NAME="g13"></A>
<A NAME="g14"></A>
that it's not a formal parameter of a procedure, like <CODE>x</CODE> in <CODE>square</CODE>,
but has a permanent value established by <CODE>define</CODE>.
<P>When an expression is evaluated, every name in the expression must have some
value substituted for it. If the name is a formal parameter, then the
corresponding actual argument value is substituted. Otherwise, the name had
better have a global definition, and <EM>that</EM> value is substituted. It
just so happens that Scheme has predefined a zillion names before you start
working, and most of those are names of primitive procedures.
<P>(By the way, this explains why when you make a typing mistake in the name of
a procedure you might see an error message that refers to variables, such as
"variable <CODE>frist</CODE> not bound." You might expect it to say "<CODE>frist</CODE>
is not a procedure," but the problem is no different from that of any other
name that has no associated value.)
<P>Now that we know the whole truth about <CODE>define</CODE>, we can use it in
combination with the function-creating functions in these past two chapters.
<P><PRE>> (define <A NAME="g15"></A>square (same-arg-twice *))
> (square 7)
49
> (define <A NAME="g16"></A>fourth-power (repeated square 2))
> (fourth-power 5)
625
</PRE>
<P>
<H2>The Truth about <CODE>Let</CODE></H2>
<P>In Chapter 7 we introduced <CODE>let</CODE> as an abbreviation for the
situation in which we would otherwise define a helper procedure in order to
give names to commonly-used values in a calculation. We started with
<P><PRE>(define (roots a b c)
(roots1 a b c (sqrt (- (* b b) (* 4 a c)))))
(define (roots1 a b c discriminant)
(se (/ (+ (- b) discriminant) (* 2 a))
(/ (- (- b) discriminant) (* 2 a))))
</PRE>
<P>and introduced the new notation
<P><PRE>(define (roots a b c)
(let ((discriminant (sqrt (- (* b b) (* 4 a c)))))
(se (/ (+ (- b) discriminant) (* 2 a))
(/ (- (- b) discriminant) (* 2 a)))))
</PRE>
<P>to avoid creating an otherwise-useless named procedure. But now
that we know about unnamed procedures, we can see that <CODE>let</CODE> is merely
an abbreviation for creating and invoking an anonymous procedure:
<P><PRE>(define (roots a b c)
<STRONG><BIG>(</BIG></STRONG>(lambda (discriminant)
(se (/ (+ (- b) discriminant) (* 2 a))
(/ (- (- b) discriminant) (* 2 a))))
<STRONG><BIG>(sqrt (- (* b b) (* 4 a c))))</BIG></STRONG>)
</PRE>
<P>What's shown in boldface above is the part that invokes the
procedure created by the lambda, including the actual argument expression.
<P>Just as the notation to define a procedure with parentheses around its name
is an abbreviation for a <CODE>define</CODE> and a <CODE>lambda</CODE>, the <CODE>let</CODE>
notation is an abbreviation for a <CODE>lambda</CODE> and an invocation.
<P><H2>Name Conflicts</H2>
<P>When a procedure is created inside another procedure, what happens if you
use the same formal parameter name in both?
<P><PRE>(define (f x)
(lambda (x) (+ x 3)))
</PRE>
<P>Answer: Don't do it.
<P>What actually happens is that the inner <CODE>x</CODE> wins; that's the one that is
substituted into the body. But if you find yourself in this situation, you
are almost certainly doing something wrong, such as using nondescriptive
names like <CODE>x</CODE> for your variables.
<P><H2>Named and Unnamed Functions</H2>
<P>Although you've been running across the idea of function since high school
algebra, you've probably never seen an <EM>unnamed</EM> function until now.
<A NAME="g17"></A>
<A NAME="g18"></A>
The high school function notation, <EM>g</EM>(<EM>x</EM>)=3<EM>x</EM>+8, requires you to
give the function a name (<EM>g</EM> in this case) when you create it. Most of the
functions you know, both in math and in programming, have names, such as
logarithm or <CODE>first</CODE>.<A NAME="text2" HREF="lambda#ft2">[2]</A>
<P>When do you want to name a function, and when not? It may help to think
about an analogy with numbers. Imagine if every Scheme number had to have a
name before you could use it. You'd have to say
<P><PRE>> (define three 3)
> (define four 4)
> (+ three four)
7
</PRE>
<P>This is analogous to the way we've dealt with procedures until now,
giving each one a name. Sometimes it's much easier to use a number
directly, and it's silly to have to give it a name.
<P>But sometimes it isn't silly. A common example that we've seen earlier is
<P><PRE>(define <A NAME="g19"></A>pi 3.141592654)
(define (<A NAME="g20"></A>circle-area radius)
(* pi radius radius))
(define (<A NAME="g21"></A>circumference radius)
(* 2 pi radius))
(define (<A NAME="g22"></A>sphere-surface-area radius)
(* 4 pi radius radius))
(define (<A NAME="g23"></A>sphere-volume radius)
(* (/ 4 3) pi radius radius radius))
</PRE>
<P>If we couldn't give a name to the number 3.141592654, then we'd
have to type it over and over again. Apart from the extra typing, our
programs would be harder to read and understand. Giving π a name makes
the procedures more self-documenting. (That is, someone else who reads our
procedures will have an easier time understanding what we meant.)
<P>It's the same with procedures. If we're going to use a procedure more than
once, and if there's a meaningful name for it that will help clarify the
program, then we define the procedure with <CODE>define</CODE> and give it a name.
<P><PRE>(define (square x) (* x x))
</PRE>
<P><CODE>Square</CODE> deserves a name both because we use it often and
because there is a good traditional name for it that everyone understands.
More important, by giving <CODE>square</CODE> a name, we are shifting attention
from the process by which it works (invoking the multiplication procedure)
to its <EM>purpose,</EM> computing the square of a number. From now on we
can think about squaring as though it were a Scheme primitive. This idea of
naming something and forgetting the details of its implementation is what
we've been calling "abstraction."
<P>On the other hand, if we have an unimportant procedure that we're using only
once, we might as well create it with <CODE>lambda</CODE> and without a name.
<P><PRE>> (every (lambda (x) (last (bl x))) '(all together now))
(L E O)
</PRE>
<P>We could have defined this procedure with the name <CODE>next-to-last</CODE>, but if we're never going to use it again, why bother?
<P>Here's an example in which we use an obscure unnamed function to help
us define one that's worth naming:
<P><PRE>(define (<A NAME="g24"></A>backwards wd) (accumulate (lambda (a b) (word b a)) wd))
> (backwards 'yesterday)
YADRETSEY
> (every backwards '(i saw her standing there))
(I WAS REH GNIDNATS EREHT)
</PRE>
<P><H2>Pitfalls</H2>
<P>It's very convenient that <CODE>define</CODE> has an abbreviated form to
define a procedure using a hidden <CODE>lambda</CODE>, but because there are two
notations that differ only subtly—one has an extra set of
parentheses—you could use the wrong one by mistake. If you say
<P><PRE>(define (pi) 3.141592654)
</PRE>
<P>you're not defining a variable whose value is a number. Instead
the value of <CODE>pi</CODE> will be a <EM>procedure.</EM> It would then be an error
to say
<P><PRE>(* 2 pi)
</PRE>
<P>When should the body of your procedure be a <CODE>lambda</CODE> expression?
It's easy to go overboard and say "I'm writing a procedure so I guess I
need <CODE>lambda</CODE>" even when the procedure is supposed to return a word.
<P>The secret is to remember the ideas of <EM>domain</EM> and <EM>range</EM> that
we talked about in Chapter 2. What is the range of the function
you're writing? Should it return a procedure? If so, its body might be a
<CODE>lambda</CODE> expression. (It might instead be an invocation of a
higher-order procedure, such as <CODE>repeated</CODE>, that returns a procedure.)
If your procedure doesn't return a procedure, its body won't be a <CODE>lambda</CODE> expression. (Of course your procedure might still use a <CODE>lambda</CODE>
expression as an argument to some <EM>other</EM> procedure, such as <CODE>every</CODE>.)
<P>For example, here is a procedure to keep the words of a sentence that contain
the letter <CODE>h</CODE>. The domain of the function is sentences, and its range
is also sentences. (That is, it takes a sentence as argument and returns a
sentence as its value.)
<P><PRE>(define (<A NAME="g25"></A>keep-h sent)
(keep (lambda (wd) (member? 'h wd)) sent))
</PRE>
<P>By contrast, here is a function of a letter that returns a
<EM>procedure</EM> to keep words containing that letter.
<P><PRE>(define (<A NAME="g26"></A>keeper letter)
(lambda (sent)
(keep (lambda (wd) (member? letter wd)) sent)))
</PRE>
<P>The procedure <CODE>keeper</CODE> has letters as its domain and procedures
as its range. The procedure <EM>returned by</EM> <CODE>keeper</CODE> has sentences
as its domain and as its range, just as <CODE>keep-h</CODE> does. In fact, we can
use <CODE>keeper</CODE> to define <CODE>keep-h</CODE>:
<P><PRE>(define keep-h (keeper 'h))
</PRE>
<P>Don't confuse the <EM>creation</EM> of a procedure with the <EM>invocation</EM> of one. <CODE>Lambda</CODE> creates a procedure. The procedure is
invoked in response to an expression whose first subexpression represents
that procedure. That is, the first subexpression could be the <EM>name</EM>
of the procedure, or it could be a <CODE>lambda</CODE> expression if you want to
create a procedure and invoke it right away:
<P><PRE>((lambda (x) (+ x 3)) 6)
</PRE>
<P>In particular, when you create a procedure, you specify its formal
parameters—the <EM>names</EM> for its arguments. When you invoke the
procedure, you specify <EM>values</EM> for those arguments. (In this example,
the <CODE>lambda</CODE> expression includes the formal parameter <CODE>x</CODE>, but the
invocation provides the actual argument <CODE>6</CODE>.)
<P><H2>Boring Exercises</H2>
<P>
<B>9.1</B> What will Scheme print? Figure it out yourself before you try it
on the computer.
<P><PRE>> (lambda (x) (+ (* x 3) 4))
> ((lambda (x) (+ (* x 3) 4)) 10)
> (every (lambda (wd) (word (last wd) (bl wd)))
'(any time at all))
> ((lambda (x) (+ x 3)) 10 15)
</PRE>
<P>
<B>9.2</B> Rewrite the following definitions so as to make the implicit <CODE>lambda</CODE>
explicit.
<P><PRE>(define (second stuff)
(first (bf stuff)))
(define (make-adder num)
(lambda (x) (+ num x)))
</PRE>
<P>
<B>9.3</B> What does this procedure do?
<P><PRE>(define (<A NAME="g27"></A>let-it-be sent)
(accumulate (lambda (x y) y) sent))
</PRE>
<P>
<H2>Real Exercises</H2>
<P><B>9.4</B> The following program doesn't work. Why not? Fix it.
<P><PRE>(define (<A NAME="g28"></A>who sent)
(every describe '(pete roger john keith)))
(define (<A NAME="g29"></A>describe person)
(se person sent))
</PRE>
<P>It's supposed to work like this:
<P><PRE>> (who '(sells out))
(pete sells out roger sells out john sells out keith sells out)
</PRE>
<P>
In each of the following exercises, write the procedure in terms of <CODE>lambda</CODE> and higher-order functions. Do not use named helper procedures.
If you've read Part IV, don't use recursion, either.
<P><B>9.5</B> Write <CODE>prepend-every</CODE>:
<A NAME="prependevery"></A>
<P><PRE>> (prepend-every 's '(he aid he aid))
(SHE SAID SHE SAID)
> (prepend-every 'anti '(dote pasto gone body))
(ANTIDOTE ANTIPASTO ANTIGONE ANTIBODY)
</PRE>
<P>
<B>9.6</B> Write a procedure <CODE><A NAME="g30"></A>sentence-version</CODE> that takes a function <EM>f</EM> as
its argument and returns a function <EM>g</EM>. <EM>f</EM> should take a single word as
argument. <EM>g</EM> should take a sentence as argument and return the sentence
formed by applying <EM>f</EM> to each word of that argument.
<A NAME="senver"></A>
<P><PRE>> ((sentence-version first) '(if i fell))
(I I F)
> ((sentence-version square) '(8 2 4 6))
(64 4 16 36)
</PRE>
<P>
<B>9.7</B> Write a procedure called <CODE><A NAME="g31"></A>letterwords</CODE> that takes as its
arguments a letter and a sentence. It returns a sentence containing only
those words from the argument sentence that contain the argument letter:
<A NAME="letwds"></A>
<P><PRE>> (letterwords 'o '(got to get you into my life))
(GOT TO YOU INTO)
</PRE>
<P>
<B>9.8</B> Suppose we're writing a program to play hangman. In this game one player
has to guess a secret word chosen by the other player, one letter at a time.
You're going to write just one small part of this program: a procedure that
takes as arguments the secret word and the letters guessed so far,
returning the word in which the guessing progress is displayed by including
all the guessed letters along with underscores for the not-yet-guessed ones:
<P><PRE>> (<A NAME="g32"></A>hang 'potsticker 'etaoi)
_OT_TI__E_
</PRE>
<P>Hint: You'll find it helpful to use the following procedure that determines
how to display a single letter:
<P><PRE>(define (<A NAME="g33"></A>hang-letter letter guesses)
(if (member? letter guesses)
letter
'_))
</PRE>
<P>
<B>9.9</B> Write a procedure <CODE><A NAME="g34"></A>common-words</CODE> that takes two sentences as
arguments and returns a sentence containing only those words that appear
both in the first sentence and in the second sentence.
<A NAME="commwds"></A>
<P>
<B>9.10</B> In Chapter 2 we used a function called <CODE>appearances</CODE> that returns
the number of times its first argument appears as a member of its second
argument. Implement <CODE><A NAME="g35"></A>appearances</CODE>.
<A NAME="appear"></A>
<P>
<B>9.11</B> Write a procedure <CODE><A NAME="g36"></A>unabbrev</CODE> that takes two sentences as
arguments. It should return a sentence that's the same as the first
sentence, except that any numbers in the original sentence should be
replaced with words from the second sentence. A number <CODE>2</CODE> in the first
sentence should be replaced with the second word of the second sentence, a
<CODE>6</CODE> with the sixth word, and so on.
<P><PRE>> (unabbrev '(john 1 wayne fred 4) '(bill hank kermit joey))
(JOHN BILL WAYNE FRED JOEY)
> (unabbrev '(i 3 4 tell 2) '(do you want to know a secret?))
(I WANT TO TELL YOU)
</PRE>
<P>
<B>9.12</B> Write a procedure <CODE>first-last</CODE> whose argument will be a sentence. It
should return a sentence containing only those words in the argument
sentence whose first and last letters are the same:
<P><PRE>> (<A NAME="g37"></A>first-last '(california ohio nebraska alabama alaska massachusetts))
(OHIO ALABAMA ALASKA)
</PRE>
<P>
<B>9.13</B> Write a procedure <CODE><A NAME="g38"></A>compose</CODE> that takes two functions <EM>f</EM> and <EM>g</EM>
as arguments. It should return a new function, the composition of its input
functions, which computes <EM>f</EM>(<EM>g</EM>(<EM>x</EM>)) when passed the argument <EM>x</EM>.
<P><PRE>> ((compose sqrt abs) -25)
5
> (define <A NAME="g39"></A>second (compose first bf))
> (second '(higher order function))
ORDER
</PRE>
<P>
<B>9.14</B> Write a procedure <CODE><A NAME="g40"></A>substitute</CODE> that takes three arguments, two
words and a sentence. It should return a version of the sentence, but with
every instance of the second word replaced with the first word:
<P><PRE>> (substitute 'maybe 'yeah '(she loves you yeah yeah yeah))
(SHE LOVES YOU MAYBE MAYBE MAYBE)
</PRE>
<P>
<B>9.15</B> Many functions are applicable only to arguments in a certain domain and
result in error messages if given arguments outside that domain. For
example, <CODE>sqrt</CODE> may require a nonnegative argument in a version of
Scheme that doesn't include complex numbers. (In <EM>any</EM> version of
Scheme, <CODE>sqrt</CODE> will complain if its argument isn't a number at all!)
Once a program gets an error message, it's impossible for that program to
continue the computation.
<P>Write a procedure <CODE><A NAME="g41"></A>type-check</CODE> that takes as arguments a
one-argument procedure <CODE>f</CODE> and a one-argument predicate procedure <CODE>pred</CODE>. <CODE>Type-check</CODE> should return a one-argument procedure that first
applies <CODE>pred</CODE> to its argument; if that result is true, the procedure
should return the value computed by applying <CODE>f</CODE> to the argument; if
<CODE>pred</CODE> returns false, the new procedure should also return <CODE>#f</CODE>:
<P><PRE>> (define <A NAME="g42"></A>safe-sqrt (type-check sqrt number?))
> (safe-sqrt 16)
4
> (safe-sqrt 'sarsaparilla)
#F
</PRE>
<P>
<B>9.16</B> In the language APL, most arithmetic functions can be applied either to a
number, with the usual result, or to a <EM>vector</EM>—the APL name for a
sentence of numbers—in which case the result is a new vector in which each
element is the result of applying the function to the corresponding element
of the argument. For example, the function <CODE>sqrt</CODE> applied to <CODE>16</CODE>
returns <CODE>4</CODE> as in Scheme, but <CODE>sqrt</CODE> can also be applied to a
sentence such as <CODE>(16 49)</CODE> and it returns <CODE>(4 7)</CODE>.
<P>Write a procedure <CODE><A NAME="g43"></A>aplize</CODE> that takes as its argument a
one-argument procedure whose domain is numbers or words. It should return
an APLized procedure that also accepts sentences:
<P><PRE>> (define <A NAME="g44"></A>apl-sqrt (aplize sqrt))
> (apl-sqrt 36)
6
> (apl-sqrt '(1 100 25 16))
(1 10 5 4)
</PRE>
<P>
<B>9.17</B> Write <CODE>keep</CODE> in terms of <CODE>every</CODE> and <CODE>accumulate</CODE>.
<P>
<HR>
<A NAME="ft1" HREF="lambda#text1">[1]</A> It comes from a branch of mathematical logic called
"lambda calculus" that's about the formal properties of functions.
The inclusion of first-class functions in Lisp was inspired by this
mathematical work, so Lisp borrowed the name <CODE>lambda</CODE>.<P>
<A NAME="ft2" HREF="lambda#text2">[2]</A> Professional mathematicians do have a
notation for unnamed functions, by the way. They write (<EM>x</EM> ↦ 3<EM>x</EM>+8).<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="../ssch8/higher.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="bridge.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|