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
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 1 ch 5: Functions of Functions</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 1:
<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT
<H1>Functions of Functions</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls1.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"><BR>
<TR><TD align="right"><A HREF="../pdf/v1ch05.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v1ch4/v1ch4.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch6/v1ch6.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT
Press web page for Computer Science Logo Style</A>
</TABLE></TABLE>
<HR>
<P>
We now have many of the tools we need to write computer programs. We have
the primitive operations for arithmetic computation, the primitive
operations to manipulate words and sentences, and a way to choose between
alternative computations. One thing that we still lack is a way to deal
systematically with data <EM>aggregates</EM>--collections of data. We want
to be able to say "carry out this computation for each member of that
aggregate." Processing large amounts of data uniformly is one of the
abilities that distinguish computers from mere pocket calculators.
<H2>The Problem: <CODE>Initials</CODE></H2>
<P>
To make this concrete, we'll look at a very simple example. I'd like to
write a procedure that can figure out a person's initials, like this:
<PRE>
? <U>show initials [George Harrison]</U>
[G H]
</PRE>
<P>
One obvious approach is to find the initials of the first name and the
last name:
<PRE>
to initials :name
output sentence (first first :name) (first last :name)
end
</PRE>
<P>
The trouble is that this approach doesn't work for people with middle
names. We'd like our <CODE>initials</CODE> procedure to be able to handle
any length name. But it doesn't:
<PRE>
? <U>show initials [John Alec Entwistle]</U>
[J E]
? <U>show initials [Peter Blair Denis Bernard Noone]</U>
[P N]
</PRE>
<P>
What we want is this:
<PRE>
? <U>show initials.in.our.dreams [John Alec Entwistle]</U>
[J A E]
? <U>show initials.in.our.dreams [Peter Blair Denis Bernard Noone]</U>
[P B D B N]
</PRE>
<P>
If we knew that the input would have exactly five names, we
could extract the first letter of each of them explicitly. But you never
know when some smart alec will ask you to
<PRE>
show initials [Princess Angelina Contessa Louisa Francesca ~
Banana Fana Bo Besca the Third]
</PRE>
<H2>One Solution: Numeric Iteration</H2>
<P>
If you've programmed before in other languages, then one solution will
immediately occur to you. You create a variable <CODE>n</CODE> whose value
is the number of words in the input, then you have a variable <CODE>i</CODE>
that takes on all possible values from 1 to <CODE>n</CODE>, and you select
the <CODE>i</CODE>th word from the input and pull out its first letter.
Most languages have a special notation for this sort of computation:
<PRE>
for i = 1 to n : ... : next i <I>(BASIC)</I>
for 1 := 1 to n do begin ... end <I>(Pascal)</I>
for (i=1; i<=n; i++) { ... } <I>(C)</I>
</PRE>
<P>
All of these have the same meaning: Carry out some instructions
(the part shown as <CODE>...</CODE> above) repeatedly, first with the variable
named <CODE>i</CODE> having the value <CODE>1</CODE>, then with <CODE>i</CODE> equal to <CODE>2</CODE>,
and so on, up to <CODE>i</CODE> equal to <CODE>n</CODE>. This technique is called
<EM>numeric iteration.</EM> "Iteration" means repetition, and it's
"numeric" iteration because the repetition is controlled by a variable
that takes on a sequence of numeric values.
<P>
We can do the same thing in Logo, although, as we'll soon learn, it's not
the usual approach that Logo programmers take to this problem.
<PRE>
to initials :name
local "result
make "result []
for [i 1 [count :name]] ~
[make "result sentence :result first (item :i :name)]
output :result
end
</PRE>
<P>
(The reason I declare <CODE>result</CODE> as local, but not <CODE>i</CODE>,
is that Logo's <CODE>for</CODE> automatically makes its index variable local
to the <CODE>for</CODE> itself. There is no variable <CODE>i</CODE> outside
of the <CODE>for</CODE> instruction.)
<P>
The command <CODE>for</CODE> takes two inputs. The second input is an
instruction list that will be carried out repeatedly. The first input
controls the repetition; it is a list of either three or four members: a
variable name, a starting value, a limit value, and an optional increment.
(The variable named by the first member of the list is called the <EM>index
variable.</EM> For example:
<PRE>
? <U>for [number 4 7] [print :number]</U>
4
5
6
7
? <U>for [value 4 11 3] [print :value]</U>
4
7
10
</PRE>
<P>
In the first example, <CODE>number</CODE> takes on all integer values
between 4 and 7. In the second, <CODE>value</CODE>'s starting value is 4,
and on each repetition its new value is 3 more than last time.
<CODE>Value</CODE> never actually has its limiting value of 11; the next
value after 10 would have been 13, but that's bigger than the limit.
<P>
<CODE>For</CODE> can count downward instead of upward:
<PRE>
? <U>for [i 7 5] [print :i]</U>
7
6
5
? <U>for [n 15 2 -6] [print :n]</U>
15
9
3
? <U>for [x 15 2 6] [print :x]</U>
?
</PRE>
<P> The last example has no effect. Why? The increment of 6 implies that
this invocation of <CODE>for</CODE> should count upward, which means that the
<CODE>for</CODE> continues until the value of <CODE>x</CODE> is greater than
the limit, 2. But the starting value, 15, is <EM>already</EM> greater than
2.
<P> If no increment is given in the first input to <CODE>for</CODE>, then
<CODE>for</CODE> will use either <CODE>1</CODE> or <CODE>-1</CODE> as the
increment, whichever is compatible with the starting and limit values.
<P>
Although I've been using constant numbers as the starting value, limit
value, and increment in these examples, <CODE>for</CODE> can handle any Logo
expression, represented as a list, for each of these:
<PRE>
to spread :ends
for [digit [first :ends] [last :ends]] [type :digit]
print []
end
? <U>spread 19</U>
123456789
? <U>spread 83</U>
876543
</PRE>
<P>
More formally, the effect of <CODE>for</CODE> is as follows. First it creates the
local index variable and assigns it the starting value. Then <CODE>for</CODE>
carries out three steps repeatedly: testing, action, and incrementing. The
testing step is to compare the current value of the index variable with the
limit value. If the index variable has passed the limit, then the <CODE>for</CODE>
is finished. ("Passed" means that the index variable is greater than the
limit, if the increment is positive, or that the index variable is less than
the limit, if the increment is negative.) The action step is to evaluate
the instructions in the second input to <CODE>for</CODE>. The incrementing step is
to assign a new value to the index variable by adding the increment to the
old value. Then comes another round of testing, action, and incrementing.
<P>
So, for example, if we give Logo the instruction
<PRE>
show initials [Raymond Douglas Davies]
</PRE>
<P>
then the <CODE>for</CODE> instruction within <CODE>initials</CODE> is equivalent
to this sequence of instructions:
<PRE>
local "i ; initialize index variable
make "i 1
if (:i > 3) [stop] ; testing
make "result (se :result first "Raymond) ; action (result is [R])
make "i :i+1 ; incrementing (i is 2)
if (:i > 3) [stop] ; testing
make "result (se :result first "Douglas) ; action (result is [R D])
make "i :i+1 ; incrementing (i is 3)
if (:i > 3) [stop] ; testing
make "result (se :result first "Davies) ; action (result is [R D D])
make "i :i+1 ; incrementing (i is 4)
if (:i > 3) [stop] ; testing
</PRE>
<P>
except that the <CODE>stop</CODE> instruction in the testing step stops
only the <CODE>for</CODE> instruction, not the <CODE>initials</CODE> procedure.
<H2>Critique of Numeric Iteration</H2>
<P>
Computers were originally built to deal with numbers. Numeric iteration
matches closely the behind-the-scenes sequence of steps by which computers
actually work. That's why just about every programming language supports
this style of programming.
<P>
Nevertheless, a <CODE>for</CODE> instruction isn't anything like the way
you, a human being, would solve the <CODE>initials</CODE> problem without a
computer. First of all, you wouldn't begin by counting the number of words
in the name; you really don't have to know that. You'd just say, for
example, "First of Raymond is R; first of Douglas is D; first of Davies is
D." When you ran out of names, you'd stop.
<P>
The manipulation of the <CODE>result</CODE> variable to collect the results also
seems unnatural. You wouldn't think, "I'm going to start with an empty
result; then, whatever value <CODE>result</CODE> has, I'll throw in an R; then,
whatever value <CODE>result</CODE> now has, I'll throw in a D" and so on.
<P>
In fact, if you had to explain to someone else how to solve this problem,
you probably wouldn't talk about a sequence of steps at all. Rather, you'd
draw a picture like this one:
<P><CENTER><IMG SRC="initials.gif" ALT="<P>figure: initials"></CENTER>
<P>
To explain the picture, you'd say something like "Just take the
<CODE>first</CODE> of each word." You wouldn't even mention the need to put the
results together into a sentence; you'd take that for granted.
<P>
In Logo we can write an <CODE>initials</CODE> procedure using the same way of
thinking that you'd use in English:
<PRE>
to initials :name
output map "first :name
end
</PRE>
<P>
The <CODE>map</CODE> procedure means "collect the results of
doing <EM>this</EM> for each of <EM>those.</EM>"
<P>
As this example illustrates, <CODE>map</CODE> is easy to use. But it's a
little hard to talk about, because it's a function of a function. So first
we'll take a detour to talk more precisely about functions in general.
<H2>What's a Function?</H2>
<P>
A <EM>function</EM> is a rule for turning one value (called the
<EM>argument</EM>) into another. If
you've studied algebra you'll remember numeric function rules such as
<P><CENTER><I>f</I>(<I>x</I>) = 3<I>x</I>-6</CENTER>
<P>
but not all functions are numeric, and not all rules need be expressed as
algebraic formulas. For example, here is the Instrument function, which
takes a Beatle as its argument and returns his instrument:
<P><CENTER><TABLE>
<TR align="left">
<TH><U>argument</U>       </TH>
<TH><U>result</U></TH>
<TR>
<TD>John</TD>
<TD>rhythm guitar</TD>
<TR>
<TD>Paul</TD>
<TD>bass guitar</TD>
<TR>
<TD>George</TD>
<TD>lead guitar</TD>
<TR>
<TD>Ringo</TD>
<TD>drums</TD>
</TABLE></CENTER>
<P>
This particular function has only four possible arguments. Other
functions, like <I>f</I>(<I>x</I>) above, may have infinitely many possible arguments.
The set of possible arguments is called the <EM>domain</EM> of the
function. Similarly, the set of possible result values is called the
<EM>range</EM> of the function.*
<SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>It's a little awkward to talk about
the domain of a function that takes two arguments. That is, it's easy to
say that the domain of the function represented by the <CODE>first</CODE> operation
is words or lists, but how do we describe <CODE>item</CODE>? We could loosely say
"its domain is numbers and words or lists," but that sounds as if either
argument could be any of those. The most precise way to say it is this:
"The domain of <CODE>item</CODE> is pairs of values, in which the first member of
the pair is a positive integer and the second member is a word or list of
length greater than or equal to the first member of the pair." But for
ordinary purposes we just rephrase the sentence to avoid the word "domain"
altogether: "<CODE>Item</CODE> takes two inputs; the first must be a positive
integer and the second must be a word or list..."</SMALL></BLOCKQUOTE></SMALL>
<P>
Functions can be represented in many ways. (We've seen two in this
section: formulas and tables.) One way to represent a function is with a
Logo operation. Here are Logo representations of the two functions we've
discussed:
<PRE>
to f :x
output 3*:x - 6
end
to instrument :beatle
if :beatle = "John [output [rhythm guitar]]
if :beatle = "Paul [output [bass guitar]]
if :beatle = "George [output [lead guitar]]
if :beatle = "Ringo [output [drums]]
end
</PRE>
<P>
(What if we give <CODE>instrument</CODE> an input that's not in the
domain of the function? In that case, it won't output any value, and a Logo
error message will result. Some people would argue that the procedure
should provide its own, more specific error message.)
<P>
I've been careful to say that the Logo operation <EM>represents</EM> the
function, not that it <EM>is</EM> the function. In particular, two Logo
procedures can compute the same function--the same relationship between
input and output values--by different methods. For example,
consider these Logo operations:
<PRE>
to f :x to g :x
output 3*:x - 6 output 3 * (:x-2)
end end
</PRE>
<P>
The Logo operations <CODE>f</CODE> and <CODE>g</CODE> carry out two different
computations, but they represent the same function. For example, to compute
<CODE>f 10</CODE> we say 3×10=30, 30-6=24; to compute
<CODE>g 10</CODE> we say 10-2=8, 3×8=24. Different computations,
but the same answer. Functional programming means, in part, focusing our
attention on the inputs and outputs of programs rather than on the sequence
of computational steps.
<P>
Just as a Logo operation represents a function, the procedure's inputs
similarly <EM>represent</EM> the arguments to the corresponding function.
For example, that instrument function I presented earlier has Beatles (that
is to say, people) as its domain and has musical instruments as its range.
But Logo doesn't have people or instruments as data types, and so the
procedure <CODE>instrument</CODE> takes as its input <EM>the name of</EM> a
Beatle (that is, a word) and returns as its output <EM>the name of</EM> an
instrument (a sentence). Instrument is a function from Beatles to
instruments, but <CODE>instrument</CODE> is an operation from words to
sentences.
<P>
We're about to see a similar situation when we explore <CODE>map</CODE>.
The map function--that is, the function that <CODE>map</CODE>
represents--is a <EM>function of functions.</EM> One of the arguments to
the map function is itself a function. The corresponding input to Logo's
<CODE>map</CODE> procedure should be a procedure. But it turns out that
Logo doesn't quite allow a procedure to be an input to another procedure;
instead, we must use the <EM>name</EM> of the procedure as the input, just as
we use the name of a Beatle as the input to <CODE>instrument</CODE>.
<P>
I know this sounds like lawyer talk, and we haven't written any programs for
a while. But here's why this is important: In order to understand the
<EM>purpose</EM> of <CODE>map</CODE>, you have to think about the map
function, whose domain is functions (and other stuff, as we'll see in a
moment). But in order to understand the <EM>notation</EM> that you use with
<CODE>map</CODE> in Logo, you have to think in terms of the Logo operation,
whose input is words (names of procedures). You have to be clear about this
representation business in order to be able to shift mentally between these
viewpoints.
<H2>Functions of Functions: <CODE>Map</CODE></H2>
<P>
<CODE>Map</CODE> takes two inputs. The first is a word, which must be the name
of a one-input Logo operation. The second can be any datum. The output
from <CODE>map</CODE> is either a word or a list, whichever is the type of the
second input. The members of the output are the results of applying the
named operation to the members of the second input.
<PRE>
? <U>show map "first [Rod Argent]</U>
[R A]
</PRE>
<P>
In this example, the output is a list of two members, just as the second
input is a list of two members. Each member of the output is the result of
applying <CODE>first</CODE> to one of the members of <CODE>map</CODE>'s
second input.
<P>
Many people, when they first meet <CODE>map</CODE>, are confused by the
quoting of its first input. After all, I made a fuss back in Chapter
2 about the difference between these two examples:
<PRE>
? <U>print Hello</U>
I don't know how to Hello
? <U>print "Hello</U>
Hello
</PRE>
<P>
You learned that a quoted word means the word itself, while an unquoted word
asks Logo to invoke a procedure. But now, when I want to use the
<CODE>first</CODE> procedure as input to <CODE>map</CODE>, I'm quoting its
name. Why?
<P>
All that effort about the domains of functions should help you understand
the notation used here. Start by ignoring the Logo notation and think about
the domain of the map function. We want the map function to have
<EM>another function,</EM> the function "first" in this case, as one of its
arguments:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/mapfun.gif" ALT="<P>figure: mapfun"></CENTER>
<P>
It's tempting to say that in Logo, a function is represented by a procedure,
so <CODE>map</CODE> represents map, and <CODE>first</CODE> represents first.
If this were algebra notation, I'd say <I>map</I>(<I>first</I>, <I>Rod Argent</I>),
so in Logo I'll say
<PRE>
show map first [Rod Argent] ;; wrong!
</PRE>
<P>
But when a Logo instruction has two unquoted procedure names in a row, that
doesn't mean that the second function is used as argument to the first!
Instead, it means that <EM>the output from invoking</EM> the second function
is used as the argument to the first. In this case, we'd be
<EM>composing</EM> <CODE>map</CODE> and <CODE>first</CODE>:
<P><CENTER><IMG SRC="maperror.gif" ALT="<P>figure: maperror"></CENTER>
<P>
As the plumbing diagram shows, the list that we intended as the second input
to <CODE>map</CODE> actually ends up as the input to <CODE>first</CODE>, and
Logo will complain because <CODE>map</CODE> isn't given enough inputs.
<P>
Instead, as I said earlier, we must use <EM>the name of</EM> the
<CODE>first</CODE> procedure to represent it. That gives this diagram:
<P><CENTER><IMG SRC="mapoper.gif" ALT="<P>figure: mapoper"></CENTER>
<P>
Here's another simple example. Logo has a primitive operation
<CODE>uppercase</CODE> that takes a word as input, and outputs the same word
but in all capital letters:
<PRE>
? <U>print uppercase "young</U>
YOUNG
</PRE>
<P>
What if we want to translate an entire sentence to capital letters? The
<CODE>uppercase</CODE> primitive doesn't accept a sentence as its input:
<PRE>
? <U>show uppercase [neil young]</U>
uppercase doesn't like [neil young] as input.
</PRE>
<P>
But we can use <CODE>map</CODE> to translate each word separately and
combine the results:
<PRE>
? <U>show map "uppercase [neil young]</U>
[NEIL YOUNG]
</PRE>
<P>
Ordinarily <CODE>map</CODE> works with one-argument functions. But we can
give <CODE>map</CODE> extra arguments (by enclosing the invocation of
<CODE>map</CODE> in parentheses, as usual) so that it can work with
functions of more than one argument.
<PRE>
? <U>show (map "item [2 1 2 3] [john paul george ringo])</U>
[o p e n]
? <U>show (map "sum [1 2 3] [40 50 60] [700 800 900])</U>
[741 852 963]
</PRE>
<P>
Each input after the first provides values for one input to the mapped
function. For example, <CODE>[2 1 2 3]</CODE> provides four values for the
first input to <CODE>item</CODE>. The input lists must all have the same
length (two lists of length four in the <CODE>item</CODE> example, three
lists of length three in the <CODE>sum</CODE> example).
<P>
In the examples so far, the input data have been lists. Here's an example
in which we use <CODE>map</CODE> with words. Let's say we're writing a
program to play Hangman, the word game in which one player guesses letters
in a secret word chosen by the other player. At first the guesser sees only
a row of dashes indicating the number of letters in the word; for each
guess, more letters are revealed. We aren't going to write the entire
program yet, but we're ready to write the operation that takes the secret
word, and a list of the letters that have been guessed so far, and outputs a
row of letters and dashes as appropriate.
<PRE>
to hangword :secret :guessed
output map "hangletter :secret
end
to hangletter :letter
output ifelse memberp :letter :guessed [:letter] ["_]
end
? <U>print hangword "potsticker [e t a o i n]</U>
_ot_ti__er
? <U>print hangword "gelato [e t a o i n]</U>
_e_ato
</PRE>
<P>
Notice that <CODE>hangletter</CODE> depends on Logo's dynamic scope to have
access to <CODE>hangword</CODE>'s local variable named <CODE>guessed</CODE>.
<P>
» Write an operation <CODE>exaggerate</CODE> that takes a sentence as
input and outputs an exaggerated version:
<PRE>
? <U>print exaggerate [I ate 3 potstickers]</U>
I ate 6 potstickers
? <U>print exaggerate [The chow fun is good here]</U>
The chow fun is great here
</PRE>
<P>
It should double all the numbers in the sentence, and replace
"good" with "great," "bad" with "terrible," and so on.
<P>
A function whose domain or range includes functions is called a
<EM>higher order function.</EM> The function represented by
<CODE>map</CODE> is a higher order function. (We may speak loosely and say
that <CODE>map</CODE> is a higher order function, as long as you remember
that Logo procedures aren't really functions!) It's tempting to say that the
<CODE>map</CODE> procedure itself is a "higher order procedure," but in
Logo that isn't true. Procedures aren't data in Logo; the only data types
are words and lists. That's why the input to <CODE>map</CODE> is a word,
the name of a procedure, and not the procedure itself. Some languages do
treat procedures themselves as data. In particular, the language Scheme is
a close relative of Logo that can handle procedures as data. If this way of
thinking appeals to you, consider learning Scheme next!
<H2>Higher Order Selection: <CODE>Filter</CODE></H2>
<P>
The purpose of <CODE>map</CODE> is to <EM>transform</EM> each member of an
aggregate (a list or a word) by applying some function to it. Another
higher order function, <CODE>filter</CODE>, is used to <EM>select</EM> some
members of an aggregate, but not others, based on a criterion expressed as a
predicate function. For example:
<PRE>
? <U>show filter "numberp [76 trombones, 4 calling birds, and 8 days]</U>
[76 4 8]
to vowelp :letter
output memberp :letter "aeiou
end
? <U>show filter "vowelp "spaghetti</U>
aei
to beatlep :person
output memberp :person [John Paul George Ringo]
end
? <U>show filter "beatlep [Bob George Jeff Roy Tom]</U>
[George]
</PRE>
<P>
What happens if we use the <CODE>initials</CODE> procedure that we wrote with
people's names in mind for other kinds of names, such as organizations or
book titles? Some of them work well:
<PRE>
? <U>show initials [Computer Science Logo Style]</U>
[C S L S]
? <U>show initials [American Civil Liberties Union]</U>
[A C L U]
</PRE>
<P>
but others don't give quite the results we'd like:
<PRE>
? <U>show initials [Association for Computing Machinery]</U>
[A f C M]
? <U>show initials [People's Republic of China]</U>
[P R o C]
</PRE>
<P>
We'd like to eliminate words like "for" and "of" before taking the first
letters of the remaining words. This is a job for <CODE>filter</CODE>:
<PRE>
to importantp :word
output not memberp :word [the an a of for by with in to and or]
end
to initials :name
output map "first (filter "importantp :name)
end
? <U>show initials [Association for Computing Machinery]</U>
[A C M]
? <U>show initials [People's Republic of China]</U>
[P R C]
</PRE>
<H2>Many to One: <CODE>Reduce</CODE></H2>
<P>
Of course, what we'd <EM>really</EM> like is to have those initials in the
form of a single word: ACLU, CSLS, ACM, and so on. For this purpose we
need yet another higher order function, one that invokes a combining
function to join the members of an aggregate.
<PRE>
? <U>show reduce "word [C S L S]</U>
CSLS
? <U>show reduce "sum [3 4 5 6]</U>
18
? <U>show reduce "sentence "UNICEF</U>
[U N I C E F]
</PRE>
<P>
<CODE>Reduce</CODE> takes two inputs. The first must be the name of a
two-input operation; the second can be any <EM>nonempty</EM> word or list.
<PRE>
to acronym :name
output reduce "word initials :name
end
</PRE>
<P>
In practice, the first input to <CODE>reduce</CODE> won't be any old
operation; it'll be a <EM>constructor.</EM> It'll be something that doesn't
care about the grouping of operands; for example, <CODE>sum</CODE> is a good
choice but <CODE>difference</CODE> is problematic because we don't know
whether
<PRE>
reduce "difference [5 6 7]
</PRE>
<P>
means 5-(6-7) or (5-6)-7, and the grouping affects the answer. Almost
all the time, the constructor will be <CODE>word</CODE>,
<CODE>sentence</CODE>, <CODE>sum</CODE>, or <CODE>product</CODE>. But
here's an example of another one:
<PRE>
to bigger :a :b
output ifelse :a > :b [:a] [:b]
end
to biggest :nums
output reduce "bigger :nums
end
? <U>show biggest [5 7 781 42 8]</U>
781
</PRE>
<H2>Choosing the Right Tool</H2>
<P>
So far you've seen three higher order functions: <CODE>map</CODE>,
<CODE>filter</CODE>, and <CODE>reduce</CODE>. How do you decide which one to
use for a particular problem?
<P>
<CODE>Map</CODE> transforms each member of a word or list individually. The
result contains as many members as the input.
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/map.gif" ALT="<P>figure: map"></CENTER>
<P>
<CODE>Filter</CODE> selects certain members of a word or list and discards the
others. The members of the result are members of the input, without
transformation, but the result may be smaller than the original.
<P><CENTER><IMG SRC="filter.gif" ALT="<P>figure: filter"></CENTER>
<P>
<CODE>Reduce</CODE> transforms the entire word or list into a single result
by combining all of the members in some way.
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/reduce.gif" ALT="<P>figure: reduce"></CENTER>
<H2>Anonymous Functions</H2>
<P>
In several of the examples in this chapter, I've had to write "helper"
procedures such as <CODE>hangletter</CODE>, <CODE>importantp</CODE>, and
<CODE>bigger</CODE> that will never be used independently, but are needed
only to provide the function argument to a higher order function. It would
be simpler if we could avoid writing these as separate procedures.
<P>
Does that sound confusing? This is one of those ideas for which an example
is worth 1000 words:
<PRE>
to hangword :secret :guessed
output map [ifelse memberp ? :guessed [?] ["_]] :secret
end
</PRE>
<P>
Until now, the first input to <CODE>map</CODE> has always been a word,
used to represent the function with that word as its name. In this example
we see how a nameless function can be represented: as a list containing a
Logo expression, but with question marks where the function's argument
belongs. Such a list is called a <EM>template.</EM>
<PRE>
? <U>show filter [memberp ? [John Paul George Ringo]] ~</U>
<U>[Bob George Jeff Roy Tom]</U>
[George]
</PRE>
<P>
Anonymous functions of more than one argument are a little uglier. Instead
of <CODE>?</CODE> for the argument, you must use <CODE>?1</CODE> for the
first, <CODE>?2</CODE> for the second, and so on.
<PRE>
to biggest :nums
output reduce [ifelse ?1 > ?2 [?1] [?2]] :nums
end
</PRE>
<P>
Notice that the templates don't say <CODE>output</CODE>, as the named
procedures did. That's because procedures are made of
<EM>instructions,</EM> whereas these are <EM>expression</EM> templates.
When input values are "plugged in" for the question marks, the template
becomes a Logo expression, which means that when evaluated it has a value.
If the template said <CODE>output</CODE>, it would be saying to use that
value as the output <EM>from the procedure containing it!</EM> (I'm just
repeating the point made earlier that <CODE>output</CODE> immediately stops
the procedure it's in, even if there are more instructions below it.)
<H2>Higher Order Miscellany</H2>
<P>
<CODE>Map</CODE> combines the partial results into a list, if the second
argument is a list, or into a word, if it's a word. Sometimes this behavior
isn't quite what you want. An alternative is <CODE>map.se</CODE> (map to
sentence), which makes a sentence of the results. Here are some examples.
<PRE>
? <U>make "numbers [zero one two three four five six seven eight nine]</U>
? <U>show map [item ?+1 :numbers] 5789</U>
fiveseveneightnine
? <U>show map.se [item ?+1 :numbers] 5789</U>
[five seven eight nine]
? <U>show map [sentence (word "With ?) "You] [in out]</U>
[[Within You] [Without You]]
? <U>show map.se [sentence (word "With ?) "You] [in out]</U>
[Within You Without You]
? <U>show map.se [sentence ? "Warner] [Yakko Wakko Dot]</U>
[Yakko Warner Wakko Warner Dot Warner]
? <U>show map [sentence ? "Warner] [Yakko Wakko Dot]</U>
[[Yakko Warner] [Wakko Warner] [Dot Warner]]
</PRE>
<P>
As these examples show, sometimes <CODE>map</CODE> does what you want, but
sometimes <CODE>map.se</CODE> does, depending on the "shape" you want your
result to have. Do you want a word, a sentence, or a structured list?
<P>
Suppose we have two sets of things, and we want all the pairings of one of
these with one of those. An example will make clear what's desired:
<PRE>
? <U>show crossproduct [red blue green] [shirt pants]</U>
[[red shirt] [blue shirt] [green shirt] [red pants] [blue pants]
[green pants]]
</PRE>
<P>
This is a tricky example because there are two different mistakes
we could make. We don't want to "flatten" the result into a sentence:
<PRE>
[red shirt blue shirt green shirt red pants blue pants green pants]
</PRE>
<P>
but we also don't want all the shirts in one list and all the
pants in another:
<PRE>
[[[red shirt] [blue shirt] [green shirt]]
[[red pants] [blue pants] [green pants]]]
</PRE>
<P>
Here's the solution:
<PRE>
to crossproduct :these :those
output map.se [prepend.each :these ?] :those
end
to prepend.each :these :that
output map [sentence ? :that] :these
end
</PRE>
<P>» Notice that this solution uses both <CODE>map</CODE> and
<CODE>map.se</CODE>. Try to predict what would happen if you used
<CODE>map</CODE> both times, or <CODE>map.se</CODE> both times, or
interchanged the two. Then try it on the computer and be sure you
understand what happens and why!
<P>
By the way, this is a case in which we still need a named helper function
despite the use of templates, because otherwise we'd have one template
inside the other, and Logo couldn't figure out which <CODE>?</CODE> to
replace with what:
<PRE>
to crossproduct :these :those
output map.se [map [sentence ? ?] :these] :those ; (wrong!)
end
</PRE>
<P>
Just as <CODE>map.se</CODE> is a variant of <CODE>map</CODE>,
<CODE>find</CODE> is a variant of <CODE>filter</CODE>, for the situations in
which you only want to find <EM>one</EM> member that meets the criterion,
rather than all the members. (Perhaps you know in advance that there will
only be one, or perhaps if there are more than one, you don't care which you
get.)
<PRE>
to spellout :card
output (sentence (butlast :card) "of
(find [equalp last :card first ?]
[hearts spades diamonds clubs]))
end
? <U>print spellout "5d</U>
5 of diamonds
? <U>print spellout "10h</U>
10 of hearts
</PRE>
<P>
Sometimes what you want isn't a function at all. You want to take some
<EM>action</EM> for each member of an aggregate. The most common one is to
print each member on a separate line, in situations where you've computed a
long list of things. You can use <CODE>foreach</CODE> with an
<EM>instruction</EM> template, rather than an expression template as used
with the others. The template is the last argument, rather than the first,
to follow the way in which the phrase "for each" is used in English: For
each of these things, do that.
<PRE>
? <U>foreach (crossproduct [[ultra chocolate] pumpkin [root beer swirl]</U>
<U>ginger] [cone cup]) "print</U>
ultra chocolate cone
pumpkin cone
root beer swirl cone
ginger cone
ultra chocolate cup
pumpkin cup
root beer swirl cup
ginger cup
</PRE>
<P>
If you look closely at the letters on your computer screen you'll see that
they are made up of little dots. One simple pattern represents each letter
in a rectangle of dots five wide and seven high, like this:
<PRE>
* ***** ***** **** *****
* * * * * * * *
* * * * * * * *
***** **** * * * ***
* * * * * * * *
* * * * * * * *
* * ***** ***** **** *****
</PRE>
<P>
The following program allows you to spell words on the screen in big letters
like these. Each letter's shape is kept as the value of a global variable
with the letter as its name. (I haven't actually listed all 26 letters.)
The value is a list of seven words, each of which contains five characters,
some combination of spaces and asterisks.
<PRE>
<A name="say">to say :word</A>
for [row 1 7] [foreach :word [sayrow :row ?] print []]
print []
end
to sayrow :row :letter
type item :row thing :letter
type "| |
end
make "b [|*****| |* *| |* *| |**** | |* *| |* *| |*****|]
make "r [|*****| |* *| |* *| |*****| |* * | |* * | |* *|]
make "i [|*****| | * | | * | | * | | * | | * | |*****|]
make "a [| * | | * * | |* *| |*****| |* *| |* *| |* *|]
make "n [|* *| |** *| |** *| |* * *| |* **| |* **| |* *|]
? <U>say "brian</U>
***** ***** ***** * * *
* * * * * * * ** *
* * * * * * * ** *
**** ***** * ***** * * *
* * * * * * * * **
* * * * * * * * **
***** * * ***** * * * *
</PRE>
<P>» Modify the program so that <CODE>say</CODE> takes another input, a
number representing the size in which you want to print the letters. If the
number is 1, then the program should work as before. If the number is 2,
each dot should be printed as a two-by-two square of spaces or asterisks; if
the number is 3, a three-by-three square, and so on.
</LI>
<H2>Repeated Invocation: <CODE>Cascade</CODE></H2>
<P>
Finally, sometimes you want to compose a function with itself several times:
<PRE>
? <U>print first bf bf bf bf [The Continuing Story of Bungalow Bill]</U>
Bungalow
? <U>print first (cascade 4 "bf [The Continuing Story of Bungalow Bill])</U>
Bungalow
</PRE>
<P>
<CODE>Cascade</CODE> takes three inputs. The first is a number,
indicating how many times to invoke the function represented by the second
argument. The third argument is the starting value.
<PRE>
to power :base :exponent
output cascade :exponent [? * :base] 1
end
? <U>print power 2 8</U>
256
to range :from :to
output cascade :to-:from [sentence ? (1+last ?)] (sentence :from)
end
? <U>show range 3 8</U>
[3 4 5 6 7 8]
</PRE>
<P>
Like <CODE>map</CODE>, <CODE>cascade</CODE> can be used with extra inputs to
deal with more than one thing at a time. One example in which multi-input
<CODE>cascade</CODE> is useful is the Fibonacci sequence. Each number in
the sequence is the sum of the two previous numbers; the first two numbers
are 1. So the sequence starts
<P><CENTER>1,1,2,3,5,8,13,...</CENTER>
<P>A formal definition
of the sequence looks like this:
<P><CENTER><TABLE>
<TR><TD><I>F</I><SMALL><SUB>0</SUB></SMALL> = 1</TD>
<TR><TD><I>F</I><SMALL><SUB>1</SUB></SMALL> = 1</TD>
<TR><TD><I>F</I><SMALL><SUB>n</SUB></SMALL> = <I>F</I><SMALL><SUB>n-1</SUB></SMALL> +
<I>F</I><SMALL><SUB>n-2</SUB></SMALL>,       n>1</TD>
</TABLE></CENTER>
<P>In order to compute, say, <I>F</I><SMALL><SUB>23</SUB></SMALL>,
we must know both <I>F</I><SMALL><SUB>22</SUB></SMALL> and
<I>F</I><SMALL><SUB>21</SUB></SMALL>.
As we work our way up, we must
always remember the two most recent values, like this:
<P><CENTER><TABLE>
<TR>
<TH> </TH>
<TH>Most recent value      </TH>
<TH>Next most recent value</TH>
<TR>
<TD>start</TD>
<TD>1</TD>
<TD>0</TD>
<TR>
<TD>step 1</TD>
<TD>1</TD>
<TD>1</TD>
<TR>
<TD>step 2</TD>
<TD>2</TD>
<TD>1</TD>
<TR>
<TD>step 3</TD>
<TD>3</TD>
<TD>2</TD>
<TR>
<TD>step 4</TD>
<TD>5</TD>
<TD>3</TD>
<TR>
<TD>...</TD>
<TD>...</TD>
<TD>...</TD>
<TR>
<TD>step 22      </TD>
<TD><I>F</I><SMALL><SUB>22</SUB></SMALL></TD>
<TD><I>F</I><SMALL><SUB>21</SUB></SMALL></TD>
<TR>
<TD>step 23</TD>
<TD><I>F</I><SMALL><SUB>22</SUB></SMALL>+<I>F</I><SMALL><SUB>21</SUB></SMALL></TD>
<TD><I>F</I><SMALL><SUB>22</SUB></SMALL></TD>
</TABLE></CENTER>
<P>
To express this using <CODE>cascade</CODE>, we can use <CODE>?1</CODE> to
mean the most recent value and <CODE>?2</CODE> to mean the next most
recent. Then at each step, we need a function to compute the new
<CODE>?1</CODE> by adding the two known values, and a function to copy the
old <CODE>?1</CODE> as the new <CODE>?2</CODE>:
<PRE>
to fib :n
output (cascade :n [?1+?2] 1 [?1] 0)
end
? <U>print fib 5</U>
8
? <U>print fib 23</U>
46368
</PRE>
<P>
Another situation in which multi-input <CODE>cascade</CODE> can be useful is
to process every member of a list, using <CODE>?1</CODE> to remember the
already-processed ones and <CODE>?2</CODE> to remember the still-waiting
ones. The simplest example is reversing the words in a sentence:
<PRE>
to reverse :sent
output (cascade (count :sent)
[sentence (first ?2) ?1] []
[butfirst ?2] :sent)
end
? <U>print reverse [how now brown cow]</U>
cow brown now how
</PRE>
<P><CENTER><TABLE>
<TR align="left">
<TH> </TH>
<TH><CODE>?1</CODE></TH>
<TH><CODE>?2</CODE></TH>
<TR>
<TD>start</TD>
<TD><CODE>[]</CODE></TD>
<TD><CODE>[how now brown cow]</CODE></TD>
<TR>
<TD>step 1    </TD>
<TD><CODE>[how]</CODE></TD>
<TD><CODE>[now brown cow]</CODE></TD>
<TR>
<TD>step 2</TD>
<TD><CODE>[now how]</CODE></TD>
<TD><CODE>[brown cow]</CODE></TD>
<TR>
<TD>step 3</TD>
<TD><CODE>[brown now how]</CODE></TD>
<TD><CODE>[cow]</CODE></TD>
<TR>
<TD>step 4</TD>
<TD><CODE>[cow brown now how]</CODE>   </TD>
<TD><CODE>[]</CODE></TD>
</TABLE></CENTER>
<P>
Here is the general notation for multi-input <CODE>cascade</CODE>:
<PRE>
(cascade <U>howmany</U> <U>function1</U> <U>start1</U> <U>function2</U> <U>start2</U> ...)
</PRE>
<P>
There must be as many <TT><U>function</U></TT> inputs as
<TT><U>start</U></TT> inputs. Suppose there are <I>n</I> pairs of inputs;
then each of the <TT><U>function</U></TT>s must accept <I>n</I> inputs. The
<TT><U>start</U></TT>s provide the initial values for <CODE>?1</CODE>,
<CODE>?2</CODE>, and so on; each function provides the next value for one of
those. <CODE>Cascade</CODE> returns the final value of <CODE>?1</CODE>.
<H2>A Mini-project: Mastermind</H2>
<P>
It's time to put these programming tools to work in a more substantial
project. You're ready to write a computer program that plays a family of
games like Mastermind<SMALL><SUP>TM</SUP></SMALL>. The
computer picks a secret list of colors;
the human player makes guesses. (The number of possible colors can be
changed to tune the difficulty of the game.) At each turn, the program
should tell the player how many colors in the guess are in the correct
positions in the secret list and also how many are in the list, but not at
the same positions. For example, suppose the program's secret colors are
<PRE>
red green blue violet
</PRE>
and the player guesses
<PRE>
red orange yellow green
</PRE>
<P>
There is one correct-position match (red, because it's the first color in
both lists) and one incorrect-position match (green, because it's second in
the computer's list but fourth in the player's list).
<P>
In the program, to reduce the amount of typing needed to play the game,
represent each color as a single letter and each list of colors as a word.
In the example above, the computer's secret list is represented as
<CODE>rgbv</CODE> and the player's guess as <CODE>royg</CODE>.
<P>
There are two possible variations in the rules, depending on whether or not
color lists with duplications (such as <CODE>rgrb</CODE>, in which red
appears twice) are allowed. The program will accept a true-or-false input
to determine whether or not duplicates are allowed.
<P>
Here's an example of what an interaction with the program
should look like:
<PRE>
? <U>master "roygbiv 4 "false</U>
What's your guess?
<U>royg</U>
You have 1 correct-position matches
and 2 incorrect-position matches.
What's your guess?
<U>rogy</U>
You have 1 correct-position matches
and 2 incorrect-position matches.
What's your guess?
<U>orygbv</U>
You must guess exactly 4 colors.
What's your guess?
<U>oryx</U>
The available colors are: roygbiv
What's your guess?
<U>oryr</U>
No fair guessing the same color twice!
What's your guess?
<U>oryg</U>
You have 0 correct-position matches
and 3 incorrect-position matches.
What's your guess?
<U>rbyg</U>
You have 1 correct-position matches
and 2 incorrect-position matches.
What's your guess?
<U>boyg</U>
You have 0 correct-position matches
and 3 incorrect-position matches.
What's your guess?
<U>roby</U>
You have 1 correct-position matches
and 3 incorrect-position matches.
What's your guess?
<U>rybo</U>
You have 2 correct-position matches
and 2 incorrect-position matches.
What's your guess?
<U>ryob</U>
You win in 8 guesses!
?
</PRE>
<P>
If you prefer, just jump in and start writing the program. But I have a
particular design in mind, and you may find it easier to follow my plan.
The core of my program is written sequentially, in the form of a
<CODE>for</CODE> instruction that carries out a sequence of steps once for
each guess the user makes. But most of the "smarts" of the program are in
a collection of subprocedures that use functional programming style. That
is, these procedures are operations, not commands; they merely compute and
output a value without taking any actions. Pay attention to how these two
styles fit together. In writing the operations, don't use <CODE>make</CODE>
or <CODE>print</CODE>; each operation will consist of a single
<CODE>output</CODE> instruction.
<P>» The first task is for the computer to make a random selection from the
available colors. Write two versions: <CODE>choose.dup</CODE> that allows
the same color to be chosen more than once, and <CODE>choose.nodup</CODE>
that does not allow duplication. Each of these operations should take two
inputs: a number, indicating how many colors to choose, and a word of all
the available colors. For example, to choose four colors from the rainbow
without duplication, you'd say
<PRE>
? <U>print choose.nodup 4 "roygbiv</U>
briy
</PRE>
<P>
You'll find the Logo primitive <CODE>pick</CODE> helpful. It takes a
word or list as its input, and returns a randomly chosen member:
<PRE>
? <U>print pick [Pete John Roger Keith]</U>
John
? <U>print pick [Pete John Roger Keith]</U>
Keith
? <U>print pick "roygbiv</U>
b
</PRE>
<P>
Writing <CODE>choose.dup</CODE> is a straightforward combination of
<CODE>pick</CODE> and <CODE>cascade</CODE>.
<P>
<CODE>Choose.nodup</CODE> is a little harder. Since we want to eliminate
any color we choose from further consideration, it's plausible to use a
multi-input <CODE>cascade</CODE> sort of like this:
<PRE>
(cascade :number-wanted
[<U>add one color</U>] "
[<U>remove that color</U>] :colors)
</PRE>
<P>
If we always wanted to choose the first available color, this would be just
like the <CODE>reverse</CODE> example earlier. But we want to choose a
color randomly each time. One solution is to <EM>rotate</EM> the available
colors by some random amount, then choose what is now the first color. To
use that idea you'll need a <CODE>rotate</CODE> operation that rotates a
word some random number of times, like this:
<PRE>
? <U>rotate "roygbiv</U>
ygbivro
? <U>rotate "roygbiv</U>
vroygbi
? <U>rotate "roygbiv</U>
bivroyg
</PRE>
<P>
You can write <CODE>rotate</CODE> using <CODE>cascade</CODE> along with the
Logo primitive operation <CODE>random</CODE>. <CODE>Random</CODE> takes a
positive integer as its input, and outputs a nonnegative integer less than
its input. For example, <CODE>random 3</CODE> will output <CODE>0</CODE>,
<CODE>1</CODE>, or <CODE>2</CODE>.
<P>» The second task is to evaluate the player's guess. You'll need an
operation called <CODE>exact</CODE> that takes two words as inputs (you may
assume they are the same length) and outputs the number of correct-position
matches, and another operation called <CODE>inexact</CODE> that computes the
number of wrong-position matches. (You may find it easier to write a helper
procedure <CODE>anymatch</CODE> that takes two words as inputs, but outputs
the total number of matches, regardless of position.) Be sure to write
these so that they work even with the duplicates-allowed rule in effect.
For example, if the secret word is <CODE>rgrb</CODE> and the user guesses
<CODE>yrrr</CODE>, then you must report one exact and one inexact match, not
one exact and two inexact.
<PRE>
? <U>print exact "rgrb "yrrr</U>
1
? <U>print inexact "rgrb "yrrr</U>
1
? <U>print inexact "royg "rgbo</U>
2
</PRE>
<P>
<CODE>Exact</CODE> is a straightforward application of multi-input
<CODE>map</CODE>, since you want to look at each letter of the secret word
along with the same-position letter of the user's guess. My solution to
<CODE>anymatch</CODE> was to use <CODE>map</CODE> to consider each of the
available colors. For each color, the number of matches is the smaller of
the number of times it appears in the secret word and the number of times it
appears in the guess. (You'll need a helper procedure <CODE>howmany</CODE>
that takes two inputs, a letter and a word, and outputs the number of times
that letter occurs in that word.)
<P>» Up to this point, we've assumed that the player is making legitimate
guesses. A valid guess has the right number of colors, chosen from the set
of available colors, and (perhaps, depending on the chosen rules) with no
color duplicated. Write a predicate <CODE>valid.guessp</CODE> that takes a
guess as its input and returns <CODE>true</CODE> if the guess is valid,
<CODE>false</CODE> otherwise. In this procedure, for the first time in this
project, it's a good idea to violate functional programming style by
printing an appropriate error message when the output will be
<CODE>false</CODE>.
<P>» We now have all the tools needed to write the top-level game procedure
<CODE>master</CODE>. This procedure will take three inputs: a word of the
available colors, the number of colors in the secret word, and a
<CODE>true</CODE> or <CODE>false</CODE> to indicate whether or not duplicate
colors are allowed. After using either <CODE>choose.dup</CODE> or
<CODE>choose.nodup</CODE> to pick the secret word, I used a <CODE>for</CODE>
loop to carry out the necessary instructions for each guess.
<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v1ch4/v1ch4.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch6/v1ch6.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|