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
|
<P>
<P><A NAME="typing"></A>
<P><CENTER><IMG SRC="../ss-pics/io.jpg" ALT="figure: io"></CENTER>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 20: Input and Output</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 20</H2>
<H1>Input and Output</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/ssch20.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="part6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch21/functions-implement.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>
<P>
<P>In the tic-tac-toe project in Chapter 10, we didn't write a complete game
program. We wrote a <EM>function</EM> that took a board position and <CODE>x</CODE>
or <CODE>o</CODE> as arguments, returning the next move. We noted at the time that
a complete game program would also need to carry on a <EM>conversation</EM>
with the user. Instead of computing and returning one single value, a
<A NAME="g1"></A><A NAME="g2"></A>conversational program must carry out a sequence of events in time,
reading information from the keyboard and displaying other information
on the screen.
<P>Before we complete the tic-tac-toe project, we'll start by
exploring Scheme's mechanisms for <A NAME="g3"></A><A NAME="g4"></A>interactive programming.
<P><H2>Printing</H2>
<A NAME="g5"></A>
<P>Up until now, we've never told Scheme to print anything. The programs we've
written have computed values and returned them; we've relied on the
read-eval-print loop to print these values.<A NAME="text1" HREF="io.html#ft1">[1]</A>
<P>But let's say we want to write a program to print out all of the words to
"99 Bottles of Beer on the Wall." We could implement a function to produce a
humongous <EM>list</EM> of the lines of the song, like this:
<P><PRE>(define (bottles n)
(if (= n 0)
'()
(append (verse n)
(bottles (- n 1)))))
</PRE>
<P><PRE>(define (verse n)
(list (cons n '(bottles of beer on the wall))
(cons n '(bottles of beer))
'(if one of those bottles should happen to fall)
(cons (- n 1) '(bottles of beer on the wall))
'()))
> (bottles 3)
((3 BOTTLES OF BEER ON THE WALL)
(3 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL)
(2 BOTTLES OF BEER ON THE WALL)
()
(2 BOTTLES OF BEER ON THE WALL)
(2 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL)
(1 BOTTLES OF BEER ON THE WALL)
()
(1 BOTTLES OF BEER ON THE WALL)
(1 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL)
(0 BOTTLES OF BEER ON THE WALL)
())
</PRE>
<P>The problem is that we don't want a list. All we
want is to print out the lines of the song; storing them in a data structure
is unnecessary and inefficient. Also, some versions of Scheme would print
the above list like this:
<P><PRE>((3 BOTTLES OF BEER ON THE WALL) (3 BOTTLES OF BEER) (IF ONE OF
THOSE BOTTLES SHOULD HAPPEN TO FALL) (2 BOTTLES OF BEER ON THE
WALL) () (2 BOTTLES OF BEER ON THE WALL) (2 BOTTLES OF BEER) (IF
ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL) (1 BOTTLES OF BEER ON
THE WALL) () (1 BOTTLES OF BEER ON THE WALL) (1 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL) (0 BOTTLES OF BEER
ON THE WALL) ())
</PRE>
<P>or even all on one line. We can't rely on Scheme's mechanism for
printing lists if we want to be sure of a particular arrangement on the
screen.
<P>Instead we'll write a program to <EM>print</EM> a verse, rather
than return it in a list:
<A NAME="g6"></A>
<P><PRE>(define (<A NAME="g7"></A>bottles n)
(if (= n 0)
'burp
(begin (verse n)
(bottles (- n 1)))))
(define (<A NAME="g8"></A>verse n)
(show (cons n '(bottles of beer on the wall)))
(show (cons n '(bottles of beer)))
(show '(if one of those bottles should happen to fall))
(show (cons (- n 1) '(bottles of beer on the wall)))
(show '()))
> (bottles 3)
(3 BOTTLES OF BEER ON THE WALL)
(3 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL)
(2 BOTTLES OF BEER ON THE WALL)
()
(2 BOTTLES OF BEER ON THE WALL)
(2 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL)
(1 BOTTLES OF BEER ON THE WALL)
()
(1 BOTTLES OF BEER ON THE WALL)
(1 BOTTLES OF BEER)
(IF ONE OF THOSE BOTTLES SHOULD HAPPEN TO FALL)
(0 BOTTLES OF BEER ON THE WALL)
()
BURP
</PRE>
<P>
Notice that Scheme doesn't print an outer set of parentheses.
Each line was printed separately; there isn't one big list containing all of
them.<A NAME="text2" HREF="io.html#ft2">[2]</A>
<P>Why was "burp" printed at the end? Just because we're printing things
explicitly doesn't mean that the read-eval-print loop stops functioning. We
typed the expression <CODE>(bottles 3)</CODE>. In the course of evaluating that
expression, Scheme printed several lines for us. But the <EM>value</EM> of
the expression was the word <CODE>burp</CODE>, because that's what <CODE>bottles</CODE>
returned.
<P><H2>Side Effects and Sequencing</H2>
<P>How does our program work? There are two new ideas here: <EM><A NAME="g9"></A><A NAME="g10"></A>side effects</EM> and <EM>sequencing.</EM>
<P>Until now, whenever we've invoked a procedure, our only goal has been to get
a return value. The procedures we've used compute and return a value, and do
nothing else. <CODE>Show</CODE> is different. Although every Scheme procedure
returns a value, the Scheme language standard doesn't specify what
value the printing procedures should return.<A NAME="text3" HREF="io.html#ft3">[3]</A> Instead, we are interested in their side effects. In other words,
we invoke <CODE>show</CODE> because we want it to <EM>do</EM> something, namely,
print its argument on the screen.
<P>What exactly do we mean by "side effect"? The kinds of procedures that
we've used before this chapter can compute values, invoke helper procedures,
provide arguments to the helper procedures, and return a value. There may be
a lot of activity going on within the procedure, but the procedure
affects the world outside of itself only by returning a value that some
other procedure might use. <CODE>Show</CODE> affects the world outside of itself
by putting something on the screen. After <CODE>show</CODE> has finished its
work, someone who looks at the screen can tell that <CODE>show</CODE> was
used.<A NAME="text4" HREF="io.html#ft4">[4]</A>
<P>
<P>Here's an example to illustrate the difference between values and effects:
<P><PRE>(define (<A NAME="g11"></A>effect x)
(show x)
'done)
(define (<A NAME="g12"></A>value x)
x)
> (effect '(oh! darling))
(OH! DARLING)
DONE
> (value '(oh! darling))
(OH! DARLING)
> (bf (effect '(oh! darling)))
(OH! DARLING)
ONE
> (bf (value '(oh! darling)))
(DARLING)
> (define (<A NAME="g13"></A>lots-of-effect x)
(effect x)
(effect x)
(effect x))
> (define (<A NAME="g14"></A>lots-of-value x)
(value x)
(value x)
(value x))
> (lots-of-effect '(oh! darling))
(OH! DARLING)
(OH! DARLING)
(OH! DARLING)
DONE
> (lots-of-value '(oh! darling))
(OH! DARLING)
</PRE>
<P>
This example also demonstrates the second new idea,
sequencing: Each of <CODE>effect</CODE>, <CODE>lots-of-effect</CODE>,
and <CODE>lots-of-value</CODE> contains more than one expression in
its body. When you invoke such a procedure, Scheme evaluates all
the expressions in the body, in order, and returns the value of the
last one.<A NAME="text5" HREF="io.html#ft5">[5]</A> This also
works in the body of a <CODE>let</CODE>, which is really the body of a
procedure, and in each clause of a <A NAME="g15"></A><CODE>cond</CODE>.<A NAME="text6" HREF="io.html#ft6">[6]</A>
<P>When we invoked <CODE>lots-of-value</CODE>, Scheme invoked <CODE>value</CODE> three times;
it discarded the values returned by the first two invocations, and returned
the value from the third invocation. Similarly, when we invoked <CODE>lots-of-effect</CODE>, Scheme invoked <CODE>effect</CODE> three times and returned the
value from the third invocation. But each invocation of <CODE>effect</CODE> caused
its argument to be printed by invoking <CODE>show</CODE>.
<P><H2>The <CODE><B>Begin</B></CODE> Special Form</H2>
<A NAME="beg"></A>
<P>The <CODE>lots-of-effect</CODE> procedure accomplished sequencing by having more
than one expression in its body. This works fine if the sequence of events
that you want to perform is the entire body of a procedure. But in <CODE>bottles</CODE> we wanted to include a sequence as one of the alternatives in an
<CODE>if</CODE> construction. We couldn't just say
<P><PRE>(define (bottles n) ;; wrong
(if (= n 0)
'()
(verse n)
(bottles (- n 1))))
</PRE>
<P>because <CODE>if</CODE> must have exactly three arguments. Otherwise,
how would <CODE>if</CODE> know whether we meant <CODE>(verse n)</CODE> to be the second
expression in the true case, or the first expression in the false case?
<P>Instead, to turn the sequence of expressions into a single expression, we
use the <A NAME="g16"></A><A NAME="g17"></A>special form <A NAME="g18"></A><CODE>begin</CODE>. It takes any number of
arguments, evaluates them from left to right, and returns the value of the
last one.
<P><PRE>(define bottles n)
(if (= n 0)
'burp
(begin (verse n)
(bottles (- n 1)))))
</PRE>
<P>(One way to think about sequences in procedure bodies is that
every procedure body has an invisible <CODE>begin</CODE> surrounding it.)
<P><H2>This Isn't Functional Programming</H2>
<P>Sequencing and side effects are radical departures from the idea of
<A NAME="g19"></A><A NAME="g20"></A>functional programming. In fact, we'd like to reserve the name <EM>function</EM> for something that computes and returns one value, with no side
effects. "Procedure" is the general term for the thing that <CODE>lambda</CODE>
returns—an embodiment of an algorithm. If the algorithm is the kind that
computes and returns a single value without side effects, then we say that
the procedure implements a function.<A NAME="text7" HREF="io.html#ft7">[7]</A>
<P>There is a certain kind of sequencing even in functional programming. If
you say
<P><PRE>(* (+ 3 4) (- 92 15))
</PRE>
<P>it's clear that the addition has to happen before the
multiplication, because the result of the addition provides one of the
arguments to the multiplication. What's new in the sequential programming
style is the <EM>emphasis</EM> on sequence, and the fact that the expressions
in the sequence are <EM>independent</EM> instead of contributing values to
each other. In this multiplication problem, for example, we don't care
whether the addition happens before or after the subtraction. If the
addition and subtraction were in a sequence, we'd be using them for
independent purposes:
<P><PRE>(begin
(show (+ 3 4))
(show (- 92 15)))
</PRE>
<P>This is what we mean by being independent. Neither expression
helps in computing the other. And the order matters because we can see
the order in which the results are printed.
<P><H2>Not Moving to the Next Line</H2>
<P>Each invocation of <CODE>show</CODE> prints a separate line. What if we
want a program that prints several things on the same line, like this:
<P><PRE>> (begin (show-addition 3 4)
(show-addition 6 8)
'done)
3+4=7
6+8=14
DONE
</PRE>
<P>We use <A NAME="g21"></A><CODE>display</CODE>, which doesn't move to the next line after
printing its argument:
<P><PRE>(define (<A NAME="g22"></A>show-addition x y)
(display x)
(display '+)
(display y)
(display '=)
(show (+ x y)))
</PRE>
<P>(The last one is a <CODE>show</CODE> because we <EM>do</EM> want to start
a new line after it.)
<P>What if you just want to print a blank line? You use <A NAME="g23"></A><CODE>newline</CODE>:
<P><PRE>(define (verse n)
(show (cons n '(bottles of beer on the wall)))
(show (cons n '(bottles of beer)))
(show '(if one of those bottles should happen to fall))
(show (cons (- n 1) '(bottles of beer on the wall)))
(newline)) ; replaces (show '())
</PRE>
<P>In fact, <CODE>show</CODE> isn't an official Scheme primitive; we wrote it
in terms of <CODE>display</CODE> and <CODE>newline</CODE>.
<P><H2>Strings</H2>
<P>Throughout the book we've occasionally used strings, that is, words enclosed in
double-quote marks so that Scheme will permit the use of punctuation or other
unusual characters. Strings also preserve the case of letters, so they can
be used to beautify our song even more. Since <EM>any</EM> character can be
in a string, including spaces, the easiest thing to do in this case is
to treat all the letters, spaces, and punctuation characters of each line of
the song as one long word. (If we wanted to be able to compute functions of
the individual words in each line, that wouldn't be such a good idea.)
<P><PRE>(define (<A NAME="g24"></A>verse n)
(display n)
(show " bottles of beer on the wall,")
(display n)
(show " bottles of beer.")
(show "If one of those bottles should happen to fall,")
(display (- n 1))
(show " bottles of beer on the wall.")
(newline))
</PRE>
<P><PRE>> (verse 6)
6 bottles of beer on the wall,
6 bottles of beer.
If one of those bottles should happen to fall,
5 bottles of beer on the wall.
#F ; or whatever is returned by (newline)
</PRE>
<P>
It's strange to think of "<CODE> bottles of beer on the wall,</CODE>" as a single word. But the rule is that
anything inside double quotes counts as a single word. It doesn't have to
be an English word.
<P><H2>A Higher-Order Procedure for Sequencing</H2>
<P>Sometimes we want to print each element of a list separately:
<P><PRE>(define (<A NAME="g25"></A>show-list lst)
(if (null? lst)
'done
(begin (show (car lst))
(show-list (cdr lst)))))
> (show-list '((dig a pony) (doctor robert) (for you blue)))
(DIG A PONY)
(DOCTOR ROBERT)
(FOR YOU BLUE)
DONE
</PRE>
<P>Like other patterns of computation involving lists, this one can be
abstracted into a higher-order procedure. (We can't call it a
"higher-order function" because this one is for computations with side
effects.) The procedure <CODE><A NAME="g26"></A><CODE>for-each</CODE></CODE> is part of standard Scheme:
<P><PRE>> (for-each show '((mean mr mustard) (no reply) (tell me why)))
(MEAN MR MUSTARD)
(NO REPLY)
(TELL ME WHY)
</PRE>
<P>The value returned by <CODE>for-each</CODE> is unspecified.
<P>Why couldn't we just use <CODE>map</CODE> for this purpose? There are two reasons.
One is just an efficiency issue: <CODE>Map</CODE> constructs a list containing the
values returned by each of its sub-computations; in this example, it would
be a list of three instances of the unspecified value returned by <CODE>show</CODE>. But we aren't going to use that list for anything, so there's no
point in constructing it. The second reason is more serious. In functional
programming, the order of evaluation of subexpressions is unspecified. For
example, when we evaluate the expression
<P><PRE>(- (+ 4 5) (* 6 7))
</PRE>
<P>we don't know whether the addition or the multiplication happens
first. Similarly, the order in which <CODE>map</CODE> computes the results for
each element is unspecified. That's okay as long as the ultimately returned
list of results is in the right order. But when we are using side effects,
we <EM>do</EM> care about the order of evaluation. In this case, we want
to make sure that the elements of the argument list are printed from left to
right. <CODE>For-each</CODE> guarantees this ordering.
<P><H2>Tic-Tac-Toe Revisited</H2>
<P>We're working up toward playing a game of tic-tac-toe against the computer.
But as a first step, let's have the computer play against itself. What we
already have is <CODE>ttt</CODE>, a <EM>strategy</EM> function: one that takes a
board position as argument (and also a letter <CODE>x</CODE> or <CODE>o</CODE>) and
returns the chosen next move. In order to play a game of tic-tac-toe, we
need two players; to make it more interesting, each should have its own
strategy. So we'll write another one, quickly, that just moves in the first
empty square it sees:
<P><PRE>(define (<A NAME="g27"></A>stupid-ttt position letter)
(location '_ position))
(define (<A NAME="g28"></A>location letter word)
(if (equal? letter (first word))
1
(+ 1 (location letter (bf word)))))
</PRE>
<P>Now we can write a program that takes two strategies as arguments and
actually plays a game between them.
<P><PRE>(define (<A NAME="g29"></A>play-ttt x-strat o-strat)
(play-ttt-helper x-strat o-strat '_________ 'x))
(define (<A NAME="g30"></A>play-ttt-helper x-strat o-strat position whose-turn)
(cond ((already-won? position (opponent whose-turn))
(list (opponent whose-turn) 'wins!))
((tie-game? position) '(tie game))
(else (let ((square (if (equal? whose-turn 'x)
(x-strat position 'x)
(o-strat position 'o))))
(play-ttt-helper x-strat
o-strat
(add-move square whose-turn position)
(opponent whose-turn))))))
</PRE>
We use a helper procedure because we need to keep track of two
pieces of information besides the strategy procedures: the current board
position and whose turn it is (<CODE>x</CODE> or <CODE>o</CODE>). The helper procedure
is invoked recursively for each move. First it checks whether the game
is already over (won or tied).<A NAME="text8" HREF="io.html#ft8">[8]</A>
If not, the helper procedure invokes the current player's strategy procedure,
which returns the square number for the next move. For the recursive call,
the arguments are the same two strategies, the new position after the move,
and the letter for the other player.
<P>We still need <CODE>add-move</CODE>, the procedure that takes a square and an old
position as arguments and returns the new position.
<P><PRE>(define (<A NAME="g33"></A>add-move square letter position)
(if (= square 1)
(word letter (bf position))
(word (first position)
(add-move (- square 1) letter (bf position)))))
> (play-ttt ttt stupid-ttt)
(X WINS!)
> (play-ttt stupid-ttt ttt)
(O WINS!)
</PRE>
<P><H2>Accepting User Input</H2>
<P>The work we did in the last section was purely functional. We didn't print
anything (except the ultimate return value, as always) and we didn't
have to read information from a human player, because there wasn't one.
<P>You might expect that the structure of an <EM>interactive</EM> game program
would be very different, with a top-level procedure full of sequential
operations. But the fact is that we hardly have to change anything to turn
this into an interactive game. All we need is a new "strategy" procedure
that asks the user where to move, instead of computing a move based on
built-in rules.
<P><PRE>(define (<A NAME="g34"></A>ask-user position letter)
(print-position position)
(display letter)
(display "'s move: ")
(read))
(define (print-position position) ;; first version
(show position))
</PRE>
<P>(Ultimately we're going to want a beautiful two-dimensional
display of the current position, but we don't want to get distracted by that
just now. That's why we've written a trivial temporary version.)
<P><PRE>> (play-ttt ttt ask-user)
____X____
O'S MOVE: <B>1</B>
O___XX___
O'S MOVE: <B>4</B>
O__OXXX__
O'S MOVE: <B>3</B>
OXOOXXX__
O'S MOVE: <B>8</B>
(TIE GAME)
</PRE>
<P>What the user typed is just the single digits shown in boldface at
the ends of the lines.
<P>What's new here is that we invoke the procedure <A NAME="g35"></A><CODE>read</CODE>. It waits for
you to type a Scheme expression, and returns that expression. Don't
be confused: <CODE>Read</CODE> does <EM>not</EM> evaluate what you type. It
returns exactly the same expression that you type:
<P><PRE>(define (<A NAME="g36"></A>echo)
(display "What? ")
(let ((expr (read)))
(if (equal? expr 'stop)
'okay
(begin
(show expr)
(echo)))))
</PRE>
<P><PRE>> (echo)
What? <B>hello</B>
HELLO
What? <B>(+ 2 3)</B>
(+ 2 3)
What? <B>(first (glass onion))</B>
(FIRST (GLASS ONION))
What? <B>stop</B>
OKAY
</PRE>
<P><H2>Aesthetic Board Display</H2>
<P>Here's our beautiful position printer:
<P>
<PRE>(define (<A NAME="g37"></A>print-position position)
(print-row (subword position 1 3))
(show "-+-+-")
(print-row (subword position 4 6))
(show "-+-+-")
(print-row (subword position 7 9))
(newline))
(define (<A NAME="g38"></A>print-row row)
(maybe-display (first row))
(display "|")
(maybe-display (first (bf row)))
(display "|")
(maybe-display (last row))
(newline))
(define (<A NAME="g39"></A>maybe-display letter)
(if (not (equal? letter '_))
(display letter)
(display " ")))
(define (<A NAME="g40"></A>subword wd start end)
((repeated bf (- start 1))
((repeated bl (- (count wd) end))
wd)))<A NAME="text9" HREF="io.html#ft9">[9]</A></PRE>
Here's how it works:
<P><PRE>> (print-position '_x_oo__xx)
|X|
-+-+-
O|O|
-+-+-
|X|X
</PRE>
<H2>Reading and Writing Normal Text</H2>
<P>The <CODE>read</CODE> procedure works fine as long as what you type looks like a
Lisp program. That is, it reads one expression at a time. In the
tic-tac-toe program the user types a single number, which is a Scheme
expression, so <CODE>read</CODE> works fine. But what if we want to read more than
one word?
<P><PRE>(define (music-critic) ;; first version
(show "What's your favorite Beatles song?")
(let ((song (read)))
(show (se "I like" song "too."))))
> (music-critic)
What's your favorite Beatles song?
<B>She Loves You</B>
(I like SHE too.)
</PRE>
<P>If the user had typed the song title in parentheses, then it would
have been a single Scheme expression and <CODE>read</CODE> would have accepted it.
But we don't want the users of our program to have to be typing parentheses
all the time.
<P>Scheme also lets you read one character at a time. This allows you to read
any text, with no constraints on its format. The disadvantage is that you
find yourself putting a lot of effort into minor details. We've provided a
procedure <CODE><A NAME="g41"></A><CODE>read-line</CODE></CODE> that reads one line of input and returns a
sentence. The words in that sentence will contain any punctuation
characters that appear on the line, including parentheses, which are not
interpreted as sublist delimiters by <CODE>read-line</CODE>. <CODE>Read-line</CODE> also
preserves the case of letters.
<P><PRE>(define (music-critic) ;; second version
(read-line) ; See explanation below.
(show "What's your favorite Beatles song?")
(let ((song (read-line)))
(show (se "I like" song "too."))))
> (music-critic)
What's your favorite Beatles song?
<B>She Loves You</B>
(I like She Loves You too.)
</PRE>
<P>Why do we call <CODE>read-line</CODE> and ignore its result at the
beginning of <CODE>music-critic</CODE>? It has to do with the interaction between
<CODE>read-line</CODE> and <CODE>read</CODE>. <CODE>Read</CODE> treats what you type as a
sequence of Scheme expressions; each invocation of <CODE>read</CODE> reads one of
them. <CODE>Read</CODE> pays no attention to formatting details, such as several
consecutive spaces or line breaks. If, for example, you type several
expressions on the same line, it will take several invocations of <CODE>read</CODE>
to read them all.
<P>By contrast, <CODE>read-line</CODE> treats what you type as a sequence of lines,
reading one line per invocation, so it does pay attention to line breaks.
<P>Either of these ways to read input is sensible in itself, but if you mix
the two, by invoking <CODE>read</CODE> sometimes and <CODE>read-line</CODE> sometimes in
the same program, the results can be confusing. Suppose you type a line
containing an expression and your program invokes <CODE>read</CODE> to read it.
Since there might have been another expression on the line, <CODE>read</CODE>
doesn't advance to the next line until you ask for the next
expression. So if you now invoke <CODE>read-line</CODE>, thinking that it will
read another line from the keyboard, it will instead return an empty list,
because what it sees is an empty line—what's left after <CODE>read</CODE> uses up
the expression you typed.
<P>You may be thinking, "But <CODE>music-critic</CODE> doesn't call <CODE>read</CODE>!"
That's true, but Scheme itself used <CODE>read</CODE> to read the expression that
you used to invoke <CODE>music-critic</CODE>. So the first invocation of <CODE>read-line</CODE> is needed to skip over the spurious empty line.
<P>Our solution works only if <CODE>music-critic</CODE> is invoked directly at a
Scheme prompt. If <CODE>music-critic</CODE> were a subprocedure of some larger
program that has already called <CODE>read-line</CODE> before calling <CODE>music-critic</CODE>, the extra <CODE>read-line</CODE> in <CODE>music-critic</CODE> would really
read and ignore a useful line of text.
<P>If you write a procedure using <CODE>read-line</CODE> that will sometimes be called
directly and sometimes be used as a subprocedure, you can't include an extra
<CODE>read-line</CODE> call in it. Instead, when you call your procedure directly
from the Scheme prompt, you must say
<P><PRE>> (begin (read-line) (my-procedure))
</PRE>
<P>Another technical detail about <CODE>read-line</CODE> is that since
it preserves the capitalization of words, its result may
include strings, which will be shown in quotation marks if you return the
value rather than <CODE>show</CODE>ing it:
<P><PRE>(define (music-critic-return)
(read-line)
(show "What's your favorite Beatles song?")
(let ((song (read-line)))
(se "I like" song "too.")))
> (music-critic-return)
What's your favorite Beatles song?
<B>She Loves You</B>
("I like" "She" "Loves" "You" "too.")
</PRE>
<P>We have also provided <CODE><A NAME="g42"></A><CODE>show-line</CODE>,</CODE> which takes a sentence
as argument. It prints the sentence without surrounding parentheses,
followed by a newline. (Actually, it takes any list as argument; it prints
all the parentheses except for the outer ones.)
<P><PRE>(define (<A NAME="g43"></A>music-critic)
(read-line)
(show "What's your favorite Beatles song?")
(let ((song (read-line)))
(show-line (se "I like" song "too."))))
> (music-critic)
What's your favorite Beatles song?
<B>She Loves You</B>
I like She Loves You too.
</PRE>
<P>The difference between <CODE>show</CODE> and <CODE>show-line</CODE> isn't
crucial. It's just a matter of a pair of parentheses. The point is that
<CODE>read-line</CODE> and <CODE>show-line</CODE> go together. <CODE>Read-line</CODE> reads a
bunch of disconnected words and combines them into a sentence. <CODE>Show-line</CODE> takes a sentence and prints it as if it were a bunch of
disconnected words. Later, when we read and write files in Chapter
22, this ability to print in the same form in which we read will be
important.
<P><H2>Formatted Text</H2>
<P>We've been concentrating on the use of sequential programming with explicit
<A NAME="spformat"></A>
printing instructions for the sake of conversational programs. Another
common application of sequential printing is to display tabular information,
such as columns of numbers. The difficulty is to get the numbers to line up
so that corresponding digits are in the same position, even when the numbers
have very widely separated values. The
<A NAME="g44"></A><CODE>align</CODE> function can be used to convert a number to a printable word
with a fixed number of positions before and after the decimal point:
<P><PRE>(define (square-root-table nums)
(if (null? nums)
'done
(begin (display (align (car nums) 7 1))
(show (align (sqrt (car nums)) 10 5))
(square-root-table (cdr nums)))))
> (square-root-table '(7 8 9 10 20 98 99 100 101 1234 56789))
7.0 2.64575
8.0 2.82843
9.0 3.00000
10.0 3.16228
20.0 4.47214
98.0 9.89949
99.0 9.94987
100.0 10.00000
101.0 10.04988
1234.0 35.12834
56789.0 238.30443
DONE
</PRE>
<P><CODE>Align</CODE> takes three arguments. The first is the value to be
displayed. The second is the width of the column in which it will be
displayed; the returned value will be a word with that many characters in it.
The third argument is the number of digits that should be displayed to the
right of the decimal point. (If this number is zero, then no decimal point
will be displayed.) The width must be great enough to include all the
digits, as well as the decimal point and minus sign, if any.
<P>As the program example above indicates, <CODE>align</CODE> does not print
anything. It's a function that returns a value suitable for printing with
<CODE>display</CODE> or <CODE>show</CODE>.
<P>What if the number is too big to fit in the available space?
<P><PRE>> (align 12345679 4 0)
"123+"
</PRE>
<P><CODE>Align</CODE> returns a word containing the first few digits,
as many as fit, ending with a plus sign to indicate that part of the value
is missing.
<P><CODE>Align</CODE> can also be used to include non-numeric text in columns. If
the first argument is not a number, then only two arguments are needed; the
second is the column width. In this case <CODE>align</CODE> returns a word with
extra spaces at the right, if necessary, so that the argument word will
appear at the left in its column:
<P><PRE>(define (<A NAME="g45"></A>name-table names)
(if (null? names)
'done
(begin (display (align (cadar names) 11))
(show (caar names))
(name-table (cdr names)))))
> (name-table '((john lennon) (paul mccartney)
(george harrison) (ringo starr)))
LENNON JOHN
MCCARTNEY PAUL
HARRISON GEORGE
STARR RINGO
DONE
</PRE>
<P>As with numbers, if a non-numeric word won't fit in the allowed
space, <CODE>align</CODE> returns a partial word ending with a plus sign.
<P>This <CODE>align</CODE> function is not part of standard Scheme. Most programming
languages, including some versions of Scheme, offer much more elaborate
formatting capabilities with many alternate ways to represent both numbers
and general text. Our version is a minimal capability to show the flavor
and to meet the needs of projects in this book.
<P><H2>Sequential Programming and Order of Evaluation</H2>
<P>Our expanded tic-tac-toe program includes both functional and sequential
parts. The program computes its strategy functionally but uses sequences
of commands to control the <EM><A NAME="g46"></A><A NAME="g47"></A>user interface</EM> by alternately
printing information to the screen and reading information from the keyboard.
<P>By adding sequential programming to our toolkit, we've increased our ability
to write interactive programs. But there is a cost that goes along with
this benefit: We now have to pay more attention to the order of events than
we did in purely functional programs.
<P>The obvious concern about order of events is that sequences of <CODE>show</CODE>
expressions must come in the order in which we want them to appear, and <CODE>read</CODE> expressions must fit into the sequence properly so that the user is
asked for the right information at the right time.
<P>But there is another, less obvious issue about order of events. When the
evaluation of expressions can have side effects in addition to returning
values, the order of evaluation of argument subexpressions becomes important.
Here's an example to show what we mean. Suppose we type the expression
<P><PRE>(list (+ 3 4) (- 10 2))
</PRE>
<P>The answer, of course, is <CODE>(7 8)</CODE>. It doesn't matter whether
Scheme computes the seven first (left to right) or the eight first (right to
left). But here's a similar example in which it <EM>does</EM> matter:
<P><PRE>(define (<A NAME="g48"></A>show-and-return x)
(show x)
x)
> (list (show-and-return (+ 3 4)) (show-and-return (- 10 2)))
8
7
(7 8)
</PRE>
<P>The value that's ultimately returned, in this example, is the same
as before. But the two numeric values that go into the list are also
printed separately, so we can see which is computed first. (We've shown
the case of right-to-left computation; your Scheme might be different.)
<P>Suppose you want to make sure that the seven prints first, regardless of
which order your Scheme uses. You could do this:
<P><PRE>> (let ((left (show-and-return (+ 3 4))))
(list left (show-and-return (- 10 2))))
7
8
(7 8)
</PRE>
<P>The expression in the body of a <CODE>let</CODE> can't be evaluated until
the <CODE>let</CODE> variables (such as <CODE>left</CODE>) have had their values computed.
<P>It's hard to imagine a practical use for the artificial <CODE>show-and-return</CODE> procedure, but a similar situation arises whenever we use
<CODE>read</CODE>. Suppose we want to write a procedure to ask a person for his or
her full name, returning a two-element list containing the first and last
name. A natural mistake to make would be to write this procedure:
<P><PRE>(define (ask-for-name) ;; wrong
(show "Please type your first name, then your last name:")
(list (read) (read)))
> (ask-for-name)
Please type your first name, then your last name:
<B>John
Lennon</B>
(LENNON JOHN)
</PRE>
<P>What went wrong? We happen to be using a version of Scheme that
evaluates argument subexpressions from right to left. Therefore, the word
<CODE>John</CODE> was read by the rightmost call to <CODE>read</CODE>, which provided the
second argument to <CODE>list</CODE>. The best solution is to use <CODE>let</CODE> as we
did above:
<P><PRE>(define (<A NAME="g49"></A>ask-for-name)
(show "Please type your first name, then your last name:")
(let ((first-name (read)))
(list first-name (read))))
</PRE>
<P>Even this example looks artificially simple, because of the two invocations
of <CODE>read</CODE> that are visibly right next to each other in the erroneous
version. But look at <CODE>play-ttt-helper</CODE>. The word <CODE>read</CODE> doesn't
appear in its body at all. But when we invoke it using <CODE>ask-user</CODE> as
the strategy procedure for <CODE>x</CODE>, the expression
<P><PRE>(x-strat position 'x)
</PRE>
<P>hides an invocation of <CODE>read</CODE>. The structure of <CODE>play-ttt-helper</CODE> includes a <CODE>let</CODE> that controls the timing of that <CODE>read</CODE>. (As it turns out, in this particular case we could have gotten away
with writing the program without <CODE>let</CODE>. The hidden invocation of <CODE>read</CODE> is the only subexpression with a side effect, so there aren't two
effects that might get out of order. But we had to think carefully about
the program to be sure of that.)
<P><H2>Pitfalls</H2>
<P>It's easy to get confused about what is printed explicitly by your
<A NAME="g50"></A>
program and what is printed by Scheme's read-eval-print loop. Until now,
<EM>all</EM> printing was of the second kind. Here's an example that doesn't
do anything very interesting but will help make the point clear:
<P><PRE>(define (name)
(display "MATT ")
'wright)
> (name)
MATT WRIGHT
</PRE>
<P>At first glance it looks as if putting the word "Matt" inside a
call to <CODE>display</CODE> is unnecessary. After all, the word <CODE>wright</CODE> is
printed even without using <CODE>display</CODE>. But watch this:
<P><PRE>> (bf (name))
MATT RIGHT
</PRE>
<P>Every time you invoke <CODE>name</CODE>, whether or not as the entire
expression used at a Scheme prompt, the word <CODE>MATT</CODE> is printed. But
the word <CODE>wright</CODE> is <EM>returned,</EM> and may or may not be printed
depending on the context in which <CODE>name</CODE> is invoked.
<P>A sequence of expressions returns the value of the <EM>last</EM>
expression. If that isn't what you want, you must remember the value you
want to return using <CODE>let</CODE>:
<P><PRE>(let ((result (compute-this-first)))
(begin
(compute-this-second)
(compute-this-third)
result))
</PRE>
<P>Don't forget that the first call to <CODE>read-line</CODE>, or any call to
<CODE>read-line</CODE> after a call to <CODE>read</CODE>, will probably read the empty
line that <CODE>read</CODE> left behind.
<P>Sometimes you want to use what the user typed more than once in your
program. But don't forget that <CODE>read</CODE> has an effect as well as a return
value. Don't try to read the same expression twice:
<P><PRE>(define (ask-question question) ;; wrong
(show question)
(cond ((equal? (read) 'yes) #t)
((equal? (read) 'no) #f)
(else (show "Please answer yes or no.")
(ask-question question))))
</PRE>
<P>If the answer is <CODE>yes</CODE>, this procedure will work fine. But if
not, the second invocation of <CODE>read</CODE> will read a second expression, not
test the same expression again as intended. To avoid this problem, invoke
<CODE>read</CODE> only once for each expression you want to read, and use <CODE>let</CODE>
to remember the result:
<P><PRE>(define (<A NAME="g51"></A>ask-question question)
(show question)
(let ((answer (read)))
(cond ((equal? answer 'yes) #t)
((equal? answer 'no) #f)
(else (show "Please answer yes or no.")
(ask-question question)))))
</PRE>
<P><H2>Boring Exercises</H2>
<P><B>20.1</B> What happens when we evaluate the following expression? What is printed,
and what is the return value? Try to figure it out in your head before you
try it on the computer.
<P><PRE>(cond ((= 2 3) (show '(lady madonna)) '(i call your name))
((< 2 3) (show '(the night before)) '(hello little girl))
(else '(p.s. i love you)))
</PRE>
<P>
<B>20.2</B> What does <CODE>newline</CODE> return in your version of Scheme?
<P><B>20.3</B> Define <CODE>show</CODE> in terms of <CODE>newline</CODE> and <CODE>display</CODE>.
<P>
<H2>Real Exercises</H2>
<P><B>20.4</B> Write a program that carries on a conversation like the following example.
What the user types is in boldface.
<P><PRE>> <B>(<A NAME="g52"></A>converse)</B>
Hello, I'm the computer. What's your name? <B>Brian Harvey</B>
Hi, Brian. How are you? <B>I'm fine.</B>
Glad to hear it.
</PRE>
<P>
<B>20.5</B> Our <CODE>name-table</CODE> procedure uses a fixed width for the column containing
the last names of the people in the argument list. Suppose that instead of
liking British-invasion music you are into late romantic Russian composers:
<P><PRE>> (name-table '((piotr tchaikovsky) (nicolay rimsky-korsakov)
(sergei rachmaninov) (modest musorgsky)))
</PRE>
<P>Alternatively, perhaps you like jazz:
<P><PRE>> (name-table '((bill evans) (paul motian) (scott lefaro)))
</PRE>
<P>Modify <CODE>name-table</CODE> so that it figures out the longest last
name in its argument list, adds two for spaces, and uses that number as the
width of the first column.
<P>
<B>20.6</B> The procedure <CODE>ask-user</CODE> isn't robust. What happens if you type
something that isn't a number, or isn't between 1 and 9? Modify it to check
that what the user types is a number between 1 and 9. If not, it should
print a message and ask the user to try again.
<P>
<B>20.7</B> Another problem with <CODE>ask-user</CODE> is that it allows a user to request a
square that isn't free. If the user does this, what happens? Fix <CODE>ask-user</CODE> to ensure that this can't happen.
<P>
<B>20.8</B> At the end of the game, if the computer wins or ties, you never find out
which square it chose for its final move. Modify the program to correct
this. (Notice that this exercise requires you to make <CODE>play-ttt-helper</CODE>
non-functional.)
<P>
<B>20.9</B> The way we invoke the game program isn't very user-friendly. Write a
procedure <CODE>game</CODE> that asks you whether you wish to play <CODE>x</CODE> or <CODE>o</CODE>, then starts a game. (By definition, <CODE>x</CODE> plays first.) Then write a
procedure <CODE>games</CODE> that allows you to keep playing repeatedly. It
can ask "do you want to play again?" after each game. (Make sure that
the outcome of each game is still reported, and that the user can choose
whether to play <CODE>x</CODE> or <CODE>o</CODE> before each game.)
<P>
<HR>
<A NAME="ft1" HREF="io.html#text1">[1]</A> The only
exception is that we've used <CODE>trace</CODE>, which prints messages about
the progress of a computation.<P>
<A NAME="ft2" HREF="io.html#text2">[2]</A> We know that it's still not as beautiful as can be, because of
the capital letters and parentheses, but we'll get to that later.<P>
<A NAME="ft3" HREF="io.html#text3">[3]</A> Suppose <CODE>show</CODE>
returns <CODE>#f</CODE> in your version of Scheme. Then you might see
<P><PRE>> (show 7)
7
#F
</PRE>
<P>But since the return value is unspecified, we try to write
programs in such a way that we never use <CODE>show</CODE>'s return value as the
return value from our procedures. That's why we return values like <CODE>burp</CODE>.<P>
<A NAME="ft4" HREF="io.html#text4">[4]</A> The term <EM>side</EM> effect is based on the idea that a
procedure may have a useful return value as its main purpose and may also
have an effect "on the side." It's a misnomer to talk about the
side effect of <CODE>show</CODE>, since the effect is its main purpose. But nobody
ever says "side return value"!<P>
<A NAME="ft5" HREF="io.html#text5">[5]</A> In Chapter 4, we said that the body of a
procedure was always one single expression. We lied. But as long
as you don't use any procedures with side effects, it doesn't do you
any good to evaluate more than one expression in a body.<P>
<A NAME="ft6" HREF="io.html#text6">[6]</A> For example:
<P><PRE>> (cond ((< 4 0)
(show '(how interesting))
(show '(4 is less than zero?))
#f)
((> 4 0)
(show '(more reasonable))
(show '(4 really is more than zero))
'value)
(else
(show '(you mean 4=0?))
#f))
(MORE REASONABLE)
(4 REALLY IS MORE THAN ZERO)
VALUE</PRE><P>
<A NAME="ft7" HREF="io.html#text7">[7]</A> Sometimes people sloppily
say that the procedure <EM>is</EM> a function. In fact, you may hear people
be <EM>really</EM> sloppy and call a non-functional procedure a function!<P>
<A NAME="ft8" HREF="io.html#text8">[8]</A> You wrote the procedures <CODE>already-won?</CODE> and <CODE>tie-game?</CODE> in Exercises <A HREF="../ssch10/ttt.html#tttwon">10.1</A> and <A HREF="../ssch10/ttt.html#ttttied">10.2</A>:
<P><PRE>(define (<A NAME="g31"></A>already-won? position who)
(member? (word who who who) (find-triples position)))
(define (<A NAME="g32"></A>tie-game? position)
(not (member? '_ position)))
</PRE><P>
<A NAME="ft9" HREF="io.html#text9">[9]</A> Alternate version:
<PRE>(define (subword wd start end)
(cond ((> start 1) (subword (bf wd) (- start 1) (- end 1)))
((< end (count wd)) (subword (bl wd) start end))
(else wd)))
</PRE>
<P>You can take your choice, depending on which you think is easier,
recursion or higher-order functions.
<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="part6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch21/functions-implement.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|