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
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 1 ch 13: Planning</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 1:
<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT
<H1>Planning</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/v1ch13.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="../v1ch12/v1ch12.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch14/v1ch14.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>Program file for this chapter: <A HREF="poker.lg"><CODE>poker</CODE></A>
<P><CENTER><IMG SRC="ucb.jpg" ALT="figure: ucb"></CENTER>
<P>The picture above shows some of the architecture on the University of
California campus at Berkeley. At the left of the picture is South
Hall, one of the original campus buildings, with red brick, ivy, and
many chimneys. The white brick clock tower that dominates the center
of the picture is Sather Tower, popularly called the Campanile after
the building in Venice, Italy, on which it is modeled. Just to its
left is Evans Hall, the concrete fortress that houses the Mathematics
Department. Andrews Hall, at the very front of the picture,
is a small, one-floor building with an unusually shaped roof.
Stephens Hall, mostly hidden by the trees behind Andrews, is a
yellow-green zigzag.
<P>
<CENTER><IMG SRC="su1.jpg" ALT="figure: su1"></CENTER>
<P>
<CENTER><IMG SRC="su2.jpg" ALT="figure: su2"></CENTER>
<P>And here is a similar view of the Stanford University campus in
Palo Alto, California. Compared to the Berkeley buildings, the ones
you see here look very uniform. At the left in the first photo is
a corner of the Quadrangle, the central building complex of the campus.
The School of Education, down the path on the left, follows the same
pattern of rough tan stone with a sloping orange roof. The Meyer Library,
at the rear of the photo, follows the same color scheme, even though it's
obviously a more recent building. The second photo shows the new School
of Law. In this building the architect has clearly worked to combine
the same tan stone, orange roof theme with more modern details: the texture
of the stone is more uniform and the arches are less ornate.
Both of these campuses are the result of architectural planning, but
they illustrate two different <EM>styles</EM> of planning. The
Stanford campus was planned <EM>top-down;</EM> first came an overall
concept and then the details to fill in that concept. The Berkeley
campus was planned <EM>bottom-up;</EM> each new building was designed
to fit its architect's idea of the immediate, local situation. Some
of the individual buildings are quite beautiful, but it's those
buildings, rather than the campus as a unit, that attract attention.
<P>(I'm oversimplifying, of course. In a strictly top-down approach, the
entire campus would be laid out on paper before any building was
built. Adding new buildings later, even if they're made to fit in
with the old ones, means that the original plan was defective.
Instead of patching it up, a top-down purist would have the architects
begin all over again, allowing for more buildings from the beginning
of the design process. And in fact the original Berkeley campus was
much more uniform than the campus today, but very rapid growth led to
widespread changes in the original plan. Still, the difference in
architectural planning styles is striking and suggestive.)
<P>The same two planning strategies are possible in computer
programming. Suppose you want to write a program to play
tic-tac-toe, as I did in Chapter 6. You can start by saying,
"Let's see if I can draw the board." You'd write a procedure to draw the
four lines that make up the tic-tac-toe grid. Then you might write
procedures to draw an X and an O in the right size for the boxes you've
made. And so on. That would be a bottom-up design. Alternatively, you
might start by deciding on the major tasks that your program will have to
carry out. You might then write a top-level procedure like this:
<P><PRE>to ttt
drawboard
choose.x.o
playgame
end
to playgame
move "x
if winp "x [stop]
move "o
if winp "o [stop]
playgame
end
</PRE>
<P>In writing <CODE>ttt</CODE> and <CODE>playgame</CODE>, I've freely used
subprocedures that I haven't written yet. Later I could fill in the
gaps, writing procedures that will do exactly what's needed to fill
their places in the main procedure.
<P><H2>Structured Programming</H2>
<P>In recent years the majority of computer scientists have adopted a
school of thought called structured programming. This
phrase--the title of a 1972 book by O. J. Dahl,
Edsger Dijkstra,
and C. A. R. Hoare--describes an
uncompromising top-down philosophy of programming. Structured
programming is more than just the top-down idea, though; it also
includes rules for each step in the program development process. For
example, one potential problem with top-down programming is that it's
hard to test a procedure you've written until its subprocedures are
written also. (By contrast, a subprocedure can be tested before its
superprocedures are written.) Structured programming solves this
problem by recommending the use of <EM>stubs</EM>--preliminary
versions of the subprocedures that don't really do the job but
provide some result that allows the higher-level procedures to be
tested. For example, an operation that hasn't been written yet might
be replaced by a stub that always outputs zero, or the empty list, or
some other simple, appropriate value.
<P>More importantly, the structured programming approach tells us not to write
any procedures at all until we've first written a detailed specification of
the how the program should behave, and then a detailed plan of how it will
be organized to achieve that goal.
<P>The programming language Pascal was designed
by Niklaus Wirth in 1970
to promote a programming style and philosophy like that of
structured programming. Pascal is meant to teach
a top-down structured style by providing just the tools needed
for that approach but making it hard to program in other styles.
The widespread use of Pascal in college programming courses reflects
the popularity of the structured programming approach.
<P>(As I am preparing the second edition of this book in 1995, Pascal
is just beginning to lose ground as a teaching language; several competing
schools of thought about programming have led to diverse language choices.
The best known right now is the language C++, which exemplifies an <EM>
object oriented</EM> approach to program structure. Others are Ada and
Modula, two languages more or less in the Pascal tradition, and Scheme,
which is, like Logo, a dialect of Lisp and represents the artificial
intelligence tradition.)
<P><H2>Critique of Structured Programming</H2>
<P>One area of computer science in which the top-down approach has not
been accepted so enthusiastically is artificial intelligence. AI
researchers try to program computers to carry out ill-defined, complex
tasks (playing chess is a prototypical example) for which there is no
single, obvious method. In that kind of research project you can't
start by writing down on paper a complete specification of how the
finished program will be organized. Instead you start with a more or
less vague idea, you try programming it, and then you play around with
it to try to improve the results. That's one reason why the majority
of AI programs are written in Lisp, a language that is interactive,
so it encourages you to "program at the keyboard." Pascal, on the
other hand, was designed to
be a <EM>compiled</EM> language, in which you must write
an entire program before you can carry out a single instruction.
<P>Logo, a dialect of Lisp, was developed by artificial intelligence
researchers. Their idea was to see if they could use some of their
experience with the problem of trying to get computers to think in
order to help human beings learn to think more effectively--at least
about certain kinds of problems. You shouldn't be surprised,
therefore, to learn that Logoites tend not to be enthusiastic about
structured programming.
<P>It's not that we're against planning. On the contrary! Planning is
one of the most fundamental problem-solving skills. But there are
many kinds of planning. The kind in which every part of your
program's behavior is written down before you begin programming isn't
very realistic in many contexts. Even in the large-scale business or
government projects that structured programmers like to talk about,
it's very common that the ultimate users of a program change their
minds about how it should work, once they have some experience with
using it. The wise programmer will anticipate these changing
requirements in the original planning process. Still, one never
anticipates everything; a sensible person faced with an unexpected
change in requirements will be flexible
enough to modify the initial plan, not start all over again. And it's
even more true for people like you, who are just learning to program,
that the "goal" of a programming project is exploratory rather than
predetermined.
<P>Sometimes human lives depend on the correct operation of a computer
program. In one famous example, just about the time that the first edition
of this book was published, one person died and others were injured because
the program controlling a medical X-ray machine gave patients massive
overdoses of radiation. Certainly, any programming techniques that can help
prevent such accidents are valuable. Still, the techniques applicable to
life-or-death programming situations are not necessarily the best techniques
for beginning learners, nor even for experienced researchers who are
exploring a new area rather than writing production programs.
<P><H2>A Sample Project: Counting Poker Hands</H2>
<P>To make all this more concrete, I'd like to show you an actual planning
process for a programming project. I'm going to write a Logo program and
tell you what I'm doing as I go along. I am sitting at a rather crowded
desk; on my left is a microcomputer running Logo, and on my right is the
terminal with which I call up the large computer I use for text editing.
I'll switch back and
forth as I work.<SUP>*</SUP> Please understand
that I'm not showing you the Official Logo Programming Style. I'm showing
you one way in which one Logo programmer approaches a particular project.
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Home computers have become more
powerful since I wrote that in 1984. I can now run Logo in one window and
edit the book in another window on the same computer.</SMALL></BLOCKQUOTE></SMALL><P>The project I have in mind is to announce the value of a poker hand.
That is, the program should behave something like this:
<P><PRE>? <U>pokerhand [3s qc 3d 3h qd]</U>
full house (threes and queens)
? <U>pokerhand [4c 7h 5d 3c 6d]</U>
straight (seven high)
? <U>pokerhand [2h 10d 5s 6s 10s]</U>
pair of tens
?
</PRE>
<P>In imagining this sample dialogue, I'm doing a kind of
top-down planning. I've specified, for example, the form in which I
intend to represent a hand (a list of five cards) and a card (a word
combining a rank from
<P><PRE>[a 2 3 4 5 6 7 8 9 10 j q k]
</PRE>
<P>with a suit from
<P><PRE>[h s d c]
</PRE>
<P>standing for hearts, spades, diamonds, and clubs). I
suppose that means that I've decided we're playing five-card draw
poker rather than seven-card stud. But later I may want to think
again about that choice. I've also written down a few of the specific
messages the program can print, although I'm much less certain about
these. I may or may not actually bother with the details in
parentheses, for example.
<P>Okay, how will the program work? I envision a series of tests for
particular kinds of poker hands. So in my head there is a vague
procedure template like this:
<P><PRE>to pokerhand :cards
if royal.flushp :cards [print [royal flush] stop]
if fourp :cards [print [four of a kind] stop]
if straight.flushp :cards [print [straight flush] stop]
...
print [I suggest you fold.]
end
</PRE>
<P>This isn't something I'm ready to type into my computer.
I'm still thinking about how the details are likely to work out. One
thing that comes to mind is that, as it stands, there will be a great
duplication of effort. The test for a royal flush is just like the
test for a straight flush, plus a particular special condition (ace
high). I shouldn't really make that test twice. For that matter the
test for a straight flush is the test for a straight combined with
the test for a flush. I shouldn't have another instruction starting
<CODE>if straightp</CODE> repeating the same test.
<P><H2>An Initialization Procedure</H2>
<P>I also shouldn't read through the list representing the hand a million
times, each time pulling out the rank without the suit or vice versa.
It seems that I should begin by going through the hand <EM>once,</EM>
extracting various kinds of information into a bunch of variables.
I'll probably have <CODE>ranks</CODE> and <CODE>suits</CODE>, along with things like
<CODE>pairs</CODE>, which will list the ranks that appear twice in the
hand. I'm not sure exactly what variables I'll need, but I am now
impatient to start programming. What I'm going to do is write an
initialization procedure to set up all this information.
<P>In revising this chapter for the second edition, I find that I have
very different ideas about how to write this initialization procedure. But
I think that it's worthwhile, since this is a chapter about planning a
program and not about the finished product, to preserve my original version
and the reasoning that led me to write it. In the next section I'll show
another approach.
<P><PRE>to poker.init :cards ;; first edition version
make "ranks []
make "suits []
make "pairs []
make "threes []
make "fours []
read.cards :cards
end
</PRE>
<P><CODE>Read.cards</CODE>, when I write it, will insert new members into the lists
that <CODE>poker.init</CODE> sets up as empty lists. Why <CODE>pairs</CODE>, <CODE>
threes</CODE>, and <CODE>fours</CODE> but not, for example, <CODE>straights</CODE> and <CODE>
flushes</CODE>? Pairhood is a property of just part of a hand, whereas
straighthood is a property of the entire hand. It doesn't make sense to say
that three of the five cards form a straight. But the lists <CODE>:ranks</CODE>
and <CODE>:suits</CODE> will help in determining whether the hand is a straight or
a flush, respectively. For instance, a flush is a hand in which there is
only one suit, so if <CODE>:suits</CODE> turns out to be a list of length one, the
hand is a flush. A full house is a hand with one rank listed in <CODE>
:threes</CODE> and another listed in <CODE>:pairs</CODE>.
<P>I seem to be violating my own rules here, with all these explicit
assignments to variables that are not made <CODE>local</CODE>. But of
course the whole point of an initialization procedure is that the
variables will be used later by some other procedure, not this one or
one of its subprocedures. In a large project, it's typical for an
initialization procedure to assign values to nonlocal variables. If
I'm being careful, when I get around to writing the top-level <CODE>
pokerhand</CODE> I'll probably put <CODE>local</CODE> instructions for these
variables there.
<P>I can write <CODE>read.cards</CODE> without thinking about it at all, and I hope you
can too. It's one of the standard templates: "Do something to each
member of a list."
<P><PRE>to read.cards :cards
foreach :cards "read.card
end
</PRE>
<P>It's not obvious what goes inside <CODE>read.card</CODE>, but I can imagine
some of the instructions. So I'll start writing it anyway.
<P><PRE>to read.card :card
make "ranks fput butlast :card :ranks
make "suits fput last :card :suits
...
</PRE>
<P>Okay, time to do some thinking. I can see that there are going to be
a lot of those <CODE>make</CODE>, <CODE>fput</CODE> instructions. I should have a
subprocedure to handle it.
<P><PRE>to read.card :card
insert butlast :card "ranks
insert last :card "suits
...
</PRE>
<P>(By the way, do you see why I extract the rank of a card
with <CODE>butlast</CODE> rather than <CODE>first</CODE>? It wouldn't matter,
except for the tens where the rank is two digits. That is, the ten
of spades is represented by the word <CODE>10s</CODE>. The <CODE>first</CODE> of
that word is the single digit <CODE>1</CODE>; its <CODE>butlast</CODE> is <CODE>10</CODE>,
the number we really want.)
<P>I know that the second input to <CODE>insert</CODE> has to be the name of the
variable (like <CODE>"ranks</CODE>) and not the value of the variable (like <CODE>
:ranks</CODE>) because I've used techniques like this before. That input is going
to be used, among other things, as the first input to a <CODE>make</CODE>
invocation. <CODE>Make</CODE> needs the <EM>name</EM> of the variable in order to
be able to change its value. Although this particular notation is specific
to Logo, most programming languages have some way to distinguish between
<EM>call by value</EM> (<CODE>:ranks</CODE>) and <EM>call by name</EM> (<CODE>"ranks</CODE>)
or some similar mechanism to handle the special cases in which a
subprocedure must be able to modify a superprocedure's variable.
<P>What about <CODE>pairs</CODE> and so on? The idea is that if I've seen this
particular rank before, I should insert it in <CODE>pairs</CODE>:
<P><PRE>if memberp butlast :card :ranks [insert butlast :card "pairs]
</PRE>
<P>But there's a bug. If I put that instruction after the ones
I've already written, the rank will <EM>always</EM> be found in <CODE>
:ranks</CODE> because I've just put it there! Instead I have to put this
instruction <EM>before</EM> the one that inserts into <CODE>:ranks</CODE>.
In fact, the same problem will arise with the other lists. I have to
start by testing <CODE>:threes</CODE> and inserting into <CODE>:fours</CODE>, and
work my way down to <CODE>:ranks</CODE>. This illustrates a general rule:
<EM>Always make the most restrictive test first.</EM> I learned that
rule through hours of debugging earlier projects; now I recognize the
situation right away. Here's the finished procedure:
<P><PRE>to read.card :card
insert last :card "suits
if memberp butlast :card :threes [insert butlast :card "fours stop]
if memberp butlast :card :pairs [insert butlast :card "threes stop]
if memberp butlast :card :ranks [insert butlast :card "pairs stop]
insert butlast :card "ranks
end
</PRE>
<P>The <CODE>stop</CODE> commands are just for efficiency. Suppose
I've found a particular rank three times already in this poker hand,
and the card I'm looking at now is the fourth of the same rank. Then
the first <CODE>if</CODE> will succeed, since the rank was already a member
of <CODE>:threes</CODE>. If the <CODE>stop</CODE> command were omitted, I'd go on
to the next <CODE>if</CODE> instruction, which would find the rank in <CODE>
:pairs</CODE> and therefore insert it into <CODE>:threes</CODE>. But that's
unnecessary; if I've found the rank in <CODE>:threes</CODE>, there is no need
to insert it there again! In other words, if I'm
about to insert this card in the list of <CODE>fours</CODE>, there is no need
to check to see if it's in the lists of smaller runs of the same
rank. (Of course, it's sort of funny having <CODE>threes</CODE> and <CODE>
fours</CODE> as lists, since there can't be more than one of them in a
five-card poker hand! But this structure makes the instructions
pleasingly similar.)
<P>I notice another potential bug. When I add a rank to, for example,
<CODE>:threes</CODE>, I don't remove it from <CODE>:pairs</CODE>. So my data base
will claim that I have a pair as well as three of a kind. I could
write a <CODE>remove</CODE> procedure analogous to <CODE>insert</CODE>, but my guess
is that it won't be necessary. If I follow the "most restrictive
test first" principle later in the program, I'll know I have three of
a kind before I ever look at <CODE>:pairs</CODE>. If it turns out to be a
problem later, I'll fix it then.
<P>
I'm slightly annoyed that this procedure computes <CODE>butlast :card</CODE> so
many times. Perhaps it should be
<P><PRE>to read.card :card
local "rank
make "rank butlast :card
...
</PRE>
<P>But in fact I haven't bothered making that change.
<P>Finally, here is the missing subprocedure <CODE>insert</CODE>:
<P><PRE>to insert :item :list
if memberp :item thing :list [stop]
make :list fput :item thing :list
end
</PRE>
<P>The first instruction is there to ensure that nothing is
added to the same list twice. The <CODE>stop</CODE> commands I mentioned
earlier ought to ensure the same thing, except for the list <CODE>
:suits</CODE>. But since I need the instruction for that case anyway, I'll
take a "belt and suspenders" approach for all the lists.
<P>The input that I've called <CODE>item</CODE> here used to be called <CODE>
thing</CODE>, because I was thinking, "Insert a thing into a list." But I
found that using the procedure <CODE>thing</CODE> next to the variable <CODE>
thing</CODE> looked too confusing to me, even though it wouldn't have
bothered the Logo interpreter.
<P>I hope you noticed that the second instruction starts with <CODE>make :list</CODE>
rather than <CODE>make "list</CODE>. This is the indirect assignment technique
that I mentioned briefly in Chapter 3. Remember that the variable
<CODE>list</CODE> contains the <EM>name</EM> of another variable, such as <CODE>
threes</CODE>. It is that second variable whose value is changed.
For example,
<P><PRE>insert butlast :card "fours
</PRE>
<P>invokes <CODE>insert</CODE> with an input whose name is <CODE>list</CODE>
and whose value is <CODE>fours</CODE>. In this case, the <CODE>make</CODE>
instruction inside <CODE>insert</CODE> is equivalent to
<P><PRE>make "fours fput :item thing "fours
</PRE>
<P>or
<P><PRE>make "fours fput :item :fours
</PRE>
<P><H2>Second Edition Second Thoughts</H2>
<P>I wrote the first edition using versions of Logo without higher order
functions. These functions can be written in Logo, and in fact I did write
them later in the book, but I wasn't using them in this chapter. But in
retrospect, the style of creating a variable named <CODE>ranks</CODE> whose value
is an empty list, and then adding the rank of each card by reassigning a new
value to the variable, seems much harder to understand than this:
<P><PRE>to poker.init :cards
make "ranks map "butlast :cards
make "suits remdup map "last :cards
...
</PRE>
<P><CODE>Remdup</CODE> is an operation, primitive in Berkeley Logo, whose
output is the same as its input, but with duplicate members removed.
<P>As for <CODE>pairs</CODE>, <CODE>threes</CODE>, and <CODE>fours</CODE>, I think they are most
easily replaced by an array that keeps track of the number of times each
rank appears in the hand.
<P><PRE>to poker.init :cards ;; second edition version
make "ranks map [ranknum butlast ?] :cards
make "suits remdup map "last :cards
make "rankarray {0 0 0 0 0 0 0 0 0 0 0 0 0}
foreach :ranks [setitem ? :rankarray (item ? :rankarray)+1]
end
to ranknum :rank ;; turn rank to number
if :rank = "a [output 1]
if :rank = "j [output 11]
if :rank = "q [output 12]
if :rank = "k [output 13]
output :rank
end
</PRE>
<P>Since I want to use the card's rank as an index into an array,
I have to use a number from 1 to 13 to represent the ranks inside the
program, even though the person using the program will still represent a
rank in the more human-readable form of A for ace and so on.
<P>
<P>Where the first version of the program would test for four of a kind with
<P><PRE>if not emptyp :fours ...
</PRE>
<P>this new version will say
<P><PRE>if memberp 4 :rankarray ...
</PRE>
<P>Notice that my second thoughts are about low-level details of the program.
I haven't changed my mind about the big idea, which is to have a procedure
<CODE>poker.init</CODE> that examines the hand and converts the information into a
format in which the rest of the program can use it more easily. This is the
same idea I used in the tic-tac-toe program of Chapter 6, in which I
converted a human-readable "position" such as
<P><PRE>{x o 3 x x 6 7 8 o}
</PRE>
<P>into an internal list of "triples":
<P><PRE>[xo3 xx6 78o xx7 ox8 36o xxo 3x7]
</PRE>
<P>From now on, I won't show two versions of every procedure. I'll use the
revised data representation, even though the chapter tells the story of
how I wrote the older version of the program.
<P><H2>Planning and Debugging</H2>
<P>Ideally, according to structured programming, you should never have to
do any debugging. You should start with a complete, clear program
specification. Then you should use the approved style to translate
that specification into a program. Then you should be able to <EM>
prove</EM> mathematically that your program is correct! Debugging is a
relic of the dark ages.
<P>That's not the Logo approach. I've already done some debugging in
this project. Programming is sort of like real life: you don't always
get it right the first time. Structured programmers don't get it
right the first time either; the difference is that Logoites aren't
embarrassed about it. We think of debugging as part of the process of
solving problems in general.
<P>If you're a student in a school, the odds are that you aren't often
encouraged to accept debugging as valuable. When you hand in a paper
or a quiz, the teacher doesn't point out errors and invite you to try
again. Instead he marks your errors in red ink and takes off points
for them. You're taught that your work has to be perfect the first
time. One of the strong contributions that computer programming in
general, and Logo in particular, has made to education is to provide
one context in which you are shown a more realistic approach to making
and correcting mistakes.
<P><H2>Classifying Poker Hands</H2>
<P>The main thing remaining to be done in my project is the collection of
predicates like <CODE>fourp</CODE> and <CODE>royal.flushp</CODE> to check for
particular kinds of poker hands. I decided to write some of the easy
ones, namely the ones for multiples of the same rank.
<P>
<P><PRE>to fourp
output memberp 4 :rankarray
end
to threep
output memberp 3 :rankarray
end
to pairp
output memberp 2 :rankarray
end
to full.housep
output and threep pairp
end
</PRE>
<P>These are all pretty obvious. Notice, though, that one thing has
changed since my initial idea: these procedures don't take <CODE>:cards</CODE> as
an input. They don't examine the poker hand directly; they
examine the variables set up by the initialization procedure.
<P>
<P>Now I want to start putting all these pieces together, so I'm going to
write a preliminary version of <CODE>pokerhand</CODE>.
<P><PRE>to pokerhand :cards
poker.init :cards
if fourp [print [four of a kind] stop]
if full.housep [print [full house] stop]
if threep [print [three of a kind] stop]
if pairp [print ifelse paircount = 1 [one pair] [two pairs] stop]
print [something else]
end
to paircount
output count locate 2 1
end
to locate :number :index
if :index > 13 [output []]
if (item :index :rankarray) = :number ~
[output fput :index (locate :number :index+1)]
output locate :number :index+1
end
</PRE>
<P>If there's a pair, I can't simply use <CODE>memberp</CODE> to find out
how many pairs are in the hand. Instead, the procedure <CODE>locate</CODE> looks
at each member of <CODE>:rankarray</CODE> and outputs a list of all the ranks of
which there are exactly two cards in the hand. For this purpose I could
have had <CODE>locate</CODE> output the number of pairs, which would be a little
easier than computing the list of ranks of pairs. But I recall that I want
to be able to say things like "pair of sevens," and for that I'll need the
actual ranks.
<P>Let's try it:
<P><PRE>? <U>pokerhand [ah 2c 4d 2s 6h]</U>
I don't know how to one in pokerhand
[if pairp [print ifelse paircount = 1 [one pair] [two pairs] stop]]
</PRE>
<P>Looks like a bug. (This really happened; I'm not just making it
up to be able to talk about debugging!) The first step in solving a
problem like this is to read the error message carefully. This message
tells me that when the error happened, the immediately active procedure was
<CODE>pokerhand</CODE>. So that's where I should look for a mistake. (The exact
form of the message will be different in different versions of Logo, but
they'll all give you that piece of information. In Berkeley Logo, the error
message also includes the instruction line in which the error occurred.) I
then edited <CODE>pokerhand</CODE> and looked for the word <CODE>one</CODE>. I found it
in the list
<P><PRE>[one pair]
</PRE>
<P>which is one of the inputs to an <CODE>ifelse</CODE> operation. Aha! The
trouble is that <CODE>ifelse</CODE> <EM>evaluates</EM> whichever input is selected
by its predicate input, so it's trying to evaluate that list as a
Logo expression. What I meant was this:
<P><PRE>if pairp [print ifelse paircount = 1 [[one pair]] [[two pairs]] stop]
</PRE>
<P>Now it should evaluate <CODE>[[one pair]]</CODE> and come up with the
value <CODE>[one pair]</CODE> to use as the input to <CODE>print</CODE>. Let's try again:
<P><PRE>? <U>pokerhand [ah 2c 4d 2s 6h]</U>
one pair
? <U>pokerhand [2h 5d 2s 2c 7d]</U>
three of a kind
? <U>pokerhand [2h 5d 2s 2c 5h]</U>
full house
? <U>pokerhand [3h 4h 5h 6h 7h]</U>
something else
</PRE>
<P>So far so good, but of course there is more work to do. We need to
write <CODE>straightp</CODE>, <CODE>flushp</CODE>, and their combinations: straight
flush and royal flush. I think I shouldn't have an instruction in
<CODE>pokerhand</CODE> testing <CODE>royal.flushp</CODE> as I originally planned;
instead I should test for <CODE>straightp</CODE> and, if that's true, look
for special cases within that.
<P><PRE>to flushp
output emptyp butfirst :suits
end
</PRE>
<P>It's not so obvious how to write <CODE>straightp</CODE>. Here's my
plan: First, find the lowest-rank card in the hand. Then, in order to
have a straight, the next four ranks must also be present in the hand.
<P>»This isn't the only possible way to test for a straight; can you think
of, and implement, another?
<P><PRE>to straightp
output nogap (reduce "min :ranks) 5
end
to min :a :b
output ifelse :a < :b [:a] [:b]
end
to nogap :smallest :howmany
if :howmany=0 [output "true]
if not equalp (item :smallest :rankarray) 1 [output "false]
output nogap :smallest+1 :howmany-1
end
</PRE>
<P><CODE>Nogap</CODE> starts with the smallest rank in the hand and checks that there
is exactly one card in each of that and the next four ranks. It takes
advantage of the fact that I'm representing ranks internally as numbers;
it can just add 1 to a rank to get the next one in sequence. If
<CODE>:howmany</CODE> reaches zero, it means that we have indeed found all five
consecutive ranks in the hand. If one of the five desired ranks isn't in
the hand, or if the hand has more than one card in any of the ranks, then
the hand isn't a straight.
<P>There is one problem with this approach. The ace
can be used either high card (10-J-Q-K-A) or low card (A-2-3-4-5) in a
straight. <CODE>Straightp</CODE> thinks that the ace can only be the low card.
We'll fix that later.
<P>Now let's try some other cases. I've just added the line
<P><PRE>if straightp [print [straight] stop]
</PRE>
<P>to <CODE>pokerhand</CODE>. It doesn't much matter where I put that
line, because there is no danger of a straight also being found as a
multiple of any one rank. This instruction will be changed,
eventually, because we want to test for straight flush and so on. But
for now this will make it possible to debug <CODE>straightp</CODE>.
<P><PRE>? <U>pokerhand [3h 6d 7h 5c 4d]</U>
straight
? <U>pokerhand [3h 6d 7h 5c 8d]</U>
something else
</PRE>
<P>I picked those examples pretty much at random. It's a good idea,
when testing a procedure, to pick test cases "near the boundaries" of what
the program is supposed to accept. For example, what about an ace-low
straight, or a king-high? What about a hand in which "the next four
ranks" don't exist, because the lowest card is a Jack?
<P><PRE>? <U>pokerhand [ah 2d 3c 4c 5h]</U>
straight
? <U>pokerhand [9d 10c jh qh kh]</U>
straight
? <U>pokerhand [js jh qs qh kd]</U>
two pairs
</PRE>
<P>(Actually, that last example may never invoke <CODE>
straightp</CODE> at all, if the test for <CODE>pairp</CODE> comes first in <CODE>
pokerhand</CODE>.) Anyway, it
looks okay. I could try more examples but I think I believe it. I
now decide that the instruction I just put into <CODE>pokerhand</CODE> should
be
<P><PRE>if straightp [print ifelse flushp [[straight flush]] [[straight]] stop]
</PRE>
<P>and that it should be followed by
<P><PRE>if flushp [print [flush] stop]
</PRE>
<P>(The <CODE>if flushp</CODE> instruction has to come second because
of the principle of "most restrictive first." If that test came first,
a straight flush would be reported as just a flush.) Time for more
tests:
<P><PRE>? <U>pokerhand [3h 6h ah kh 7h]</U>
flush
? <U>pokerhand [3h 6h ad kh 7h]</U>
something else
? <U>pokerhand [3h 6h 4h 5h 7h]</U>
straight flush
? <U>pokerhand [3h 6h 4h 5s 7h]</U>
straight
</PRE>
<P>Now it's time to solve the problem of the ace-high straight.
It turns out to be easy; if the hand has an ace, then
I can use <CODE>nogap</CODE>, the subprocedure of <CODE>straightp</CODE> that
checks for consecutive ranks, to check for the four ranks from 10 to king.
<P><PRE>to ace.highp
if not equalp (item 1 :rankarray) 1 [output "false]
output nogap 10 4
end
</PRE>
<P>That's the end of the categories of poker hands, but to put it all
together requires a little editing of <CODE>pokerhand</CODE>:
<P><PRE>to pokerhand :cards
local [ranks suits rankarray]
poker.init :cards
if fourp [print [four of a kind] stop]
if full.housep [print [full house] stop]
if threep [print [three of a kind] stop]
if pairp [print ifelse paircount = 1 [[one pair]] [[two pairs]] stop]
if ace.highp [print ifelse flushp [[royal flush]] [[straight]] stop]
if straightp [print ifelse flushp [[straight flush]] [[straight]] stop]
if flushp [print [flush] stop]
print [nothing!]
end
</PRE>
<P><H2>Embellishments</H2>
<P>I've now done more or less what I set out to do. It took 14
procedures. I hope you have a feeling for the process of
switching back and forth between thinking about a particular
subproblem and thinking about the overall structure of the program.
<P>I haven't done every detail of what I first suggested. In particular,
I don't have the information about particular ranks in what I print.
I think perhaps that's more effort than this project seems worth to
me. (I'm not just being cute by saying "to me"; the point is that
a real poker enthusiast might want to spend a lot of time on this
program and make it as beautiful as possible.) But just to show how a
completed program can be modified, I'll make it print things like
<CODE>pair of sixes</CODE> instead of just <CODE>one pair</CODE>.
<P>First I have to be able to find words like "<CODE>sixes</CODE>" starting
with a rank indicator like <CODE>6</CODE>.
<P><PRE>to plural :rank
output item :rank [aces twos threes fours fives sixes
sevens eights nines tens jacks queens kings]
end
</PRE>
<P>The next step is to change one instruction in <CODE>pokerhand</CODE> to use
this new tool:
<P><PRE>if pairp [print ifelse paircount = 1
[sentence [pair of] plural first locate 2 1]
[[two pairs]]
stop]
</PRE>
<P>(If you were confused about the double square brackets
around <CODE>one pair</CODE> and <CODE>two pairs</CODE> before, seeing this new
version in which one of the possibilities is the output from a
procedure, not a literal list, might help.)
<P><PRE>? <U>pokerhand [ah 7s 3d 10c 7c]</U>
pair of sevens
</PRE>
<P>»If you're motivated, you can modify the messages for other categories
to include the specific rank information. You might want to change
"<CODE>nothing</CODE>" to "<CODE>queen high</CODE>," for example.
<P>»What if you wanted to use this program on a seven-card-stud hand? In
other words, instead of a list of five cards, you'd be given a list of
seven, from which you'd have to pick the best five. The main thing I
can think of is that you'd have to be more careful about the order of
the <CODE>if</CODE> instructions in <CODE>pokerhand</CODE>. I've said that you can
test <CODE>threep</CODE> either before or after <CODE>straightp</CODE> because they
can't both be true. But that's not the case for a seven-card hand:
<P><PRE>[3h 3s 3d 4d 5s 6h 7c]
</PRE>
<P>If you try this challenge, make sure your program announces
<P><PRE>[8s 9s 10s js qs kh ad]
</PRE>
<P>as a straight flush, not as an ace-high straight.
<P><H2>Putting the Project in a Context</H2>
<P>I wrote this program because I was looking for an example for this
book that would be not too long, not too short. That's kind of an
artificial reason for starting a project. In real life, if I wrote a
program like this one, it would be part of a larger program that
would actually <EM>play</EM> poker.
<P>In that context the problem would become very different. We wouldn't
want merely to print the designation of a hand; we'd want to be able
to compare several hands and announce a winner. To do that, we'd have
to attach something like a numerical ranking to the hand, which might
become the output from <CODE>pokerhand</CODE>. But it can't be just a single
number; there are too many possible hands to have a list of all of
them in rank order. Instead, the ranking of a hand might be a list of
numbers. <CODE>[5 7 10]</CODE> might mean that the hand is a full house (I'm
guessing that that would rank about fifth in value), with three sevens
and two tens. To compare two lists of numbers, compare their <CODE>
first</CODE>s; if those are equal, go on to compare the next members.
<P>The point is that I'm now back to something approaching top-down
planning. As the scale of the project becomes a lot bigger, that kind
of advance planning seems necessary. But this isn't really top-down
because comparing two hands is just one subproblem of playing poker.
Really, according to the top-down view, I should start by designing
the top-level procedure <CODE>poker</CODE>. Perhaps a first attempt might
look like this:
<P><PRE>to poker
deal.cards
bid
draw.more.cards
bid
pokerhand
end
</PRE>
<P>But it would be premature to type this into a computer. We
have to think about issues like these: Is the computer a player or
does it just deal and bank for the other players? How many people can
play? What is a good strategy for bidding?
<P>In the end it might turn out that the <CODE>pokerhand</CODE> we've just
written wouldn't fit into the larger project; it might have to be
rewritten for that context. To a structured programmer, the effort
we've put in would then be wasted. But I think that even if every
procedure had to be edited, I'd benefit from having taken the time to
understand how to solve this subproblem.
<P>
<TABLE width="100%"><TR><TD><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<TD align="right"><A HREF="../v1ch12/v1ch12.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch14/v1ch14.html"><STRONG>NEXT</STRONG></A>
</TABLE>
<P><H2>Program Listing</H2>
<PRE>
to pokerhand :cards
local [ranks suits rankarray]
poker.init :cards
if fourp [print [four of a kind] stop]
if full.housep [print [full house] stop]
if threep [print [three of a kind] stop]
if pairp [print ifelse paircount = 1 [[one pair]] [[two pairs]] stop]
if ace.highp [print ifelse flushp [[royal flush]] [[straight]] stop]
if straightp [print ifelse flushp [[straight flush]] [[straight]] stop]
if flushp [print [flush] stop]
print [nothing!]
end
to poker.init :cards
make "ranks map [ranknum butlast ?] :cards
make "suits remdup map "last :cards
make "rankarray {0 0 0 0 0 0 0 0 0 0 0 0 0}
foreach :ranks [setitem ? :rankarray (item ? :rankarray)+1]
end
to ranknum :rank
if :rank = "a [output 1]
if :rank = "j [output 11]
if :rank = "q [output 12]
if :rank = "k [output 13]
output :rank
end
to fourp
output memberp 4 :rankarray
end
to threep
output memberp 3 :rankarray
end
to pairp
output memberp 2 :rankarray
end
to full.housep
output and threep pairp
end
to paircount
output count locate 2 1
end
to locate :number :index
if :index > 13 [output []]
if (item :index :rankarray) = :number ~
[output fput :index (locate :number :index+1)]
output locate :number :index+1
end
to flushp
output emptyp butfirst :suits
end
to straightp
output nogap (reduce "min :ranks) 5
end
to min :a :b
output ifelse :a < :b [:a] [:b]
end
to nogap :smallest :howmany
if :howmany=0 [output "true]
if not equalp (item :smallest :rankarray) 1 [output "false]
output nogap :smallest+1 :howmany-1
end
to ace.highp
if not equalp (item 1 :rankarray) 1 [output "false]
output nogap 10 4
end
</PRE>
<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v1ch12/v1ch12.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch14/v1ch14.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|