-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathbook.tex
18224 lines (14366 loc) · 527 KB
/
book.tex
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
% LaTeX source for ``Think Python: How to Think Like a Computer Scientist''
% Copyright (c) 2012 Allen B. Downey.
% License: Creative Commons Attribution-NonCommercial 3.0 Unported License.
% http://creativecommons.org/licenses/by-nc/3.0/
%
%\documentclass[10pt,b5paper]{book}
\documentclass[10pt]{book}
\usepackage[width=5.5in,height=8.5in,
hmarginratio=3:2,vmarginratio=1:1]{geometry}
% for some of these packages, you might have to install
% texlive-latex-extra (in Ubuntu)
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage{mathpazo}
\usepackage{url}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsthm}
%\usepackage{amssymb}
\usepackage{exercise} % texlive-latex-extra
\usepackage{makeidx}
\usepackage{setspace}
\usepackage{hevea}
\usepackage{upquote}
\usepackage{appendix}
\usepackage[bookmarks]{hyperref}
\title{Think Python}
\author{Allen B. Downey}
\newcommand{\thetitle}{Think Python: How to Think Like a Computer Scientist}
\newcommand{\theversion}{2.0.13}
\newcommand{\thedate}{June 2014}
% these styles get translated in CSS for the HTML version
\newstyle{a:link}{color:black;}
\newstyle{p+p}{margin-top:1em;margin-bottom:1em}
\newstyle{img}{border:0px}
% change the arrows
\setlinkstext
{\imgsrc[ALT="Previous"]{back.png}}
{\imgsrc[ALT="Up"]{up.png}}
{\imgsrc[ALT="Next"]{next.png}}
\makeindex
\newif\ifplastex
\plastexfalse
\begin{document}
\frontmatter
% PLASTEX ONLY
\ifplastex
\usepackage{localdef}
\maketitle
\newcount\anchorcnt
\newcommand*{\Anchor}[1]{%
\@bsphack%
\Hy@GlobalStepCount\anchorcnt%
\edef\@currentHref{anchor.\the\anchorcnt}%
\Hy@raisedlink{\hyper@anchorstart{\@currentHref}\hyper@anchorend}%
\M@gettitle{}\label{#1}%
\@esphack%
}
\else
% skip the following for plastex
\newtheorem{exercise}{Exercise}[chapter]
% LATEXONLY
\input{latexonly}
\begin{latexonly}
\renewcommand{\blankpage}{\thispagestyle{empty} \quad \newpage}
%\blankpage
%\blankpage
% TITLE PAGES FOR LATEX VERSION
%-half title--------------------------------------------------
\thispagestyle{empty}
\begin{flushright}
\vspace*{2.0in}
\begin{spacing}{3}
{\huge Think Python}\\
{\Large How to Think Like a Computer Scientist}
\end{spacing}
\vspace{0.25in}
Version \theversion
\thedate
\vfill
\end{flushright}
%--verso------------------------------------------------------
\blankpage
\blankpage
%\clearemptydoublepage
%\pagebreak
%\thispagestyle{empty}
%\vspace*{6in}
%--title page--------------------------------------------------
\pagebreak
\thispagestyle{empty}
\begin{flushright}
\vspace*{2.0in}
\begin{spacing}{3}
{\huge Think Python}\\
{\Large How to Think Like a Computer Scientist}
\end{spacing}
\vspace{0.25in}
Version \theversion
\thedate
\vspace{1in}
{\Large
Allen Downey\\
}
\vspace{0.5in}
{\Large Green Tea Press}
{\small Needham, Massachusetts}
%\includegraphics[width=1in]{figs/logo1.pdf}
\vfill
\end{flushright}
%--copyright--------------------------------------------------
\pagebreak
\thispagestyle{empty}
{\small
Copyright \copyright ~2012 Allen Downey.
\vspace{0.2in}
\begin{flushleft}
Green Tea Press \\
9 Washburn Ave \\
Needham MA 02492
\end{flushleft}
Permission is granted to copy, distribute, and/or modify this document
under the terms of the Creative Commons Attribution-NonCommercial 3.0 Unported
License, which is available at \url{http://creativecommons.org/licenses/by-nc/3.0/}.
The original form of this book is \LaTeX\ source code. Compiling this
\LaTeX\ source has the effect of generating a device-independent
representation of a textbook, which can be converted to other formats
and printed.
The \LaTeX\ source for this book is available from
\url{http://www.thinkpython.com}
\vspace{0.2in}
} % end small
\end{latexonly}
% HTMLONLY
\begin{htmlonly}
% TITLE PAGE FOR HTML VERSION
{\Large \thetitle}
{\large Allen B. Downey}
Version \theversion
\thedate
\setcounter{chapter}{-1}
\end{htmlonly}
\fi
% END OF THE PART WE SKIP FOR PLASTEX
\chapter{Preface}
\section*{The strange history of this book}
In January 1999 I was preparing to teach an introductory programming
class in Java. I had taught it three times and I was getting
frustrated. The failure rate in the class was too high and, even for
students who succeeded, the overall level of achievement was too low.
One of the problems I saw was the books.
They were too big, with too much unnecessary detail about Java, and
not enough high-level guidance about how to program. And they all
suffered from the trap door effect: they would start out easy,
proceed gradually, and then somewhere around Chapter 5 the bottom would
fall out. The students would get too much new material, too fast,
and I would spend the rest of the semester picking up the pieces.
Two weeks before the first day of classes, I decided to write my
own book.
My goals were:
\begin{itemize}
\item Keep it short. It is better for students to read 10 pages
than not read 50 pages.
\item Be careful with vocabulary. I tried to minimize the jargon
and define each term at first use.
\item Build gradually. To avoid trap doors, I took the most difficult
topics and split them into a series of small steps.
\item Focus on programming, not the programming language. I included
the minimum useful subset of Java and left out the rest.
\end{itemize}
I needed a title, so on a whim I chose {\em How to Think Like
a Computer Scientist}.
My first version was rough, but it worked. Students did the reading,
and they understood enough that I could spend class time on the hard
topics, the interesting topics and (most important) letting the
students practice.
I released the book under the GNU Free Documentation License,
which allows users to copy, modify, and distribute the book.
\index{GNU Free Documentation License}
\index{Free Documentation License, GNU}
What happened next is the cool part. Jeff Elkner, a high school
teacher in Virginia, adopted my book and translated it into
Python. He sent me a copy of his translation, and I had the
unusual experience of learning Python by reading my own book.
As Green Tea Press, I published the first Python version in 2001.
\index{Elkner, Jeff}
In 2003 I started teaching at Olin College and I got to teach
Python for the first time. The contrast with Java was striking.
Students struggled less, learned more, worked on more interesting
projects, and generally had a lot more fun.
\index{Olin College}
Over the last nine years I continued to develop the book,
correcting errors, improving some of the examples and
adding material, especially exercises.
The result is this book, now with the less grandiose title
{\em Think Python}. Some of the changes are:
\begin{itemize}
\item I added a section about debugging at the end of each chapter.
These sections present general techniques for finding and avoiding
bugs, and warnings about Python pitfalls.
\item I added more exercises, ranging from short tests of
understanding to a few substantial projects. And I wrote
solutions for most of them.
\item I added a series of case studies---longer examples with
exercises, solutions, and discussion. Some are based on
Swampy, a suite of Python programs I wrote for use in my classes.
Swampy, code examples, and some solutions are available from
\url{http://thinkpython.com}.
\item I expanded the discussion of program development plans
and basic design patterns.
\item I added appendices about debugging, analysis of algorithms, and
UML diagrams with Lumpy.
\end{itemize}
I hope you enjoy working with this book, and that it helps
you learn to program and think, at least a little bit, like
a computer scientist.
Allen B. Downey \\
Needham MA\\
Allen Downey is a Professor of Computer Science at
the Franklin W. Olin College of Engineering.
\section*{Acknowledgments}
Many thanks to Jeff Elkner, who
translated my Java book into Python, which got this project
started and introduced me to what has turned out to be my
favorite language.
\index{Elkner, Jeff}
Thanks also to Chris Meyers, who contributed several sections
to {\em How to Think Like a Computer Scientist}.
\index{Meyers, Chris}
Thanks to the Free Software Foundation for developing
the GNU Free Documentation License, which helped make
my collaboration with Jeff and Chris possible, and Creative
Commons for the license I am using now.
\index{GNU Free Documentation License}
\index{Free Documentation License, GNU}
\index{Creative Commons}
Thanks to the editors at Lulu who worked on
{\em How to Think Like a Computer Scientist}.
Thanks to all the students who worked with earlier
versions of this book and all the contributors (listed
below) who sent in corrections and suggestions.
\section*{Contributor List}
\index{contributors}
More than 100 sharp-eyed and thoughtful readers have sent in
suggestions and corrections over the past few years. Their
contributions, and enthusiasm for this project, have been a
huge help.
If you have a suggestion or correction, please send email to
{\tt [email protected]}. If I make a change based on your
feedback, I will add you to the contributor list
(unless you ask to be omitted).
If you include at least part of the sentence the
error appears in, that makes it easy for me to search. Page and
section numbers are fine, too, but not quite as easy to work with.
Thanks!
\begin{itemize}
\small
\item Lloyd Hugh Allen sent in a correction to Section 8.4.
\item Yvon Boulianne sent in a correction of a semantic error in
Chapter 5.
\item Fred Bremmer submitted a correction in Section 2.1.
\item Jonah Cohen wrote the Perl scripts to convert the
LaTeX source for this book into beautiful HTML.
\item Michael Conlon sent in a grammar correction in Chapter 2
and an improvement in style in Chapter 1, and he initiated discussion
on the technical aspects of interpreters.
\item Benoit Girard sent in a
correction to a humorous mistake in Section 5.6.
\item Courtney Gleason and Katherine Smith wrote {\tt horsebet.py},
which was used as a case study in an earlier version of the book. Their
program can now be found on the website.
\item Lee Harr submitted more corrections than we have room to list
here, and indeed he should be listed as one of the principal editors
of the text.
\item James Kaylin is a student using the text. He has submitted
numerous corrections.
\item David Kershaw fixed the broken {\tt catTwice} function in Section
3.10.
\item Eddie Lam has sent in numerous corrections to Chapters
1, 2, and 3.
He also fixed the Makefile so that it creates an index the first time it is
run and helped us set up a versioning scheme.
\item Man-Yong Lee sent in a correction to the example code in
Section 2.4.
\item David Mayo pointed out that the word ``unconsciously"
in Chapter 1 needed
to be changed to ``subconsciously".
\item Chris McAloon sent in several corrections to Sections 3.9 and
3.10.
\item Matthew J. Moelter has been a long-time contributor who sent
in numerous corrections and suggestions to the book.
\item Simon Dicon Montford reported a missing function definition and
several typos in Chapter 3. He also found errors in the {\tt increment}
function in Chapter 13.
\item John Ouzts corrected the definition of ``return value"
in Chapter 3.
\item Kevin Parks sent in valuable comments and suggestions as to how
to improve the distribution of the book.
\item David Pool sent in a typo in the glossary of Chapter 1, as well
as kind words of encouragement.
\item Michael Schmitt sent in a correction to the chapter on files
and exceptions.
\item Robin Shaw pointed out an error in Section 13.1, where the
printTime function was used in an example without being defined.
\item Paul Sleigh found an error in Chapter 7 and a bug in Jonah Cohen's
Perl script that generates HTML from LaTeX.
\item Craig T. Snydal is testing the text in a course at Drew
University. He has contributed several valuable suggestions and corrections.
\item Ian Thomas and his students are using the text in a programming
course. They are the first ones to test the chapters in the latter half
of the book, and they have made numerous corrections and suggestions.
\item Keith Verheyden sent in a correction in Chapter 3.
\item Peter Winstanley let us know about a longstanding error in
our Latin in Chapter 3.
\item Chris Wrobel made corrections to the code in the chapter on
file I/O and exceptions.
\item Moshe Zadka has made invaluable contributions to this project.
In addition to writing the first draft of the chapter on Dictionaries, he
provided continual guidance in the early stages of the book.
\item Christoph Zwerschke sent several corrections and
pedagogic suggestions, and explained the difference between {\em gleich}
and {\em selbe}.
\item James Mayer sent us a whole slew of spelling and
typographical errors, including two in the contributor list.
\item Hayden McAfee caught a potentially confusing inconsistency
between two examples.
\item Angel Arnal is part of an international team of translators
working on the Spanish version of the text. He has also found several
errors in the English version.
\item Tauhidul Hoque and Lex Berezhny created the illustrations
in Chapter 1 and improved many of the other illustrations.
\item Dr. Michele Alzetta caught an error in Chapter 8 and sent
some interesting pedagogic comments and suggestions about Fibonacci
and Old Maid.
\item Andy Mitchell caught a typo in Chapter 1 and a broken example
in Chapter 2.
\item Kalin Harvey suggested a clarification in Chapter 7 and
caught some typos.
\item Christopher P. Smith caught several typos and helped us
update the book for Python 2.2.
\item David Hutchins caught a typo in the Foreword.
\item Gregor Lingl is teaching Python at a high school in Vienna,
Austria. He is working on a German translation of the book,
and he caught a couple of bad errors in Chapter 5.
\item Julie Peters caught a typo in the Preface.
\item Florin Oprina sent in an improvement in {\tt makeTime},
a correction in {\tt printTime}, and a nice typo.
\item D.~J.~Webre suggested a clarification in Chapter 3.
\item Ken found a fistful of errors in Chapters 8, 9 and 11.
\item Ivo Wever caught a typo in Chapter 5 and suggested a clarification
in Chapter 3.
\item Curtis Yanko suggested a clarification in Chapter 2.
\item Ben Logan sent in a number of typos and problems with translating
the book into HTML.
\item Jason Armstrong saw the missing word in Chapter 2.
\item Louis Cordier noticed a spot in Chapter 16 where the code
didn't match the text.
\item Brian Cain suggested several clarifications in Chapters 2 and 3.
\item Rob Black sent in a passel of corrections, including some
changes for Python 2.2.
\item Jean-Philippe Rey at Ecole Centrale
Paris sent a number of patches, including some updates for Python 2.2
and other thoughtful improvements.
\item Jason Mader at George Washington University made a number
of useful suggestions and corrections.
\item Jan Gundtofte-Bruun reminded us that ``a error'' is an error.
\item Abel David and Alexis Dinno reminded us that the plural of
``matrix'' is ``matrices'', not ``matrixes''. This error was in the
book for years, but two readers with the same initials reported it on
the same day. Weird.
\item Charles Thayer encouraged us to get rid of the semi-colons
we had put at the ends of some statements and to clean up our
use of ``argument'' and ``parameter''.
\item Roger Sperberg pointed out a twisted piece of logic in Chapter 3.
\item Sam Bull pointed out a confusing paragraph in Chapter 2.
\item Andrew Cheung pointed out two instances of ``use before def.''
\item C. Corey Capel spotted the missing word in the Third Theorem
of Debugging and a typo in Chapter 4.
\item Alessandra helped clear up some Turtle confusion.
\item Wim Champagne found a brain-o in a dictionary example.
\item Douglas Wright pointed out a problem with floor division in
{\tt arc}.
\item Jared Spindor found some jetsam at the end of a sentence.
\item Lin Peiheng sent a number of very helpful suggestions.
\item Ray Hagtvedt sent in two errors and a not-quite-error.
\item Torsten H\"{u}bsch pointed out an inconsistency in Swampy.
\item Inga Petuhhov corrected an example in Chapter 14.
\item Arne Babenhauserheide sent several helpful corrections.
\item Mark E. Casida is is good at spotting repeated words.
\item Scott Tyler filled in a that was missing. And then sent in
a heap of corrections.
\item Gordon Shephard sent in several corrections, all in separate
emails.
\item Andrew Turner {\tt spot}ted an error in Chapter 8.
\item Adam Hobart fixed a problem with floor division in {\tt arc}.
\item Daryl Hammond and Sarah Zimmerman pointed out that I served
up {\tt math.pi} too early. And Zim spotted a typo.
\item George Sass found a bug in a Debugging section.
\item Brian Bingham suggested Exercise~\ref{exrotatepairs}.
\item Leah Engelbert-Fenton pointed out that I used {\tt tuple}
as a variable name, contrary to my own advice. And then found
a bunch of typos and a ``use before def.''
\item Joe Funke spotted a typo.
\item Chao-chao Chen found an inconsistency in the Fibonacci example.
\item Jeff Paine knows the difference between space and spam.
\item Lubos Pintes sent in a typo.
\item Gregg Lind and Abigail Heithoff suggested Exercise~\ref{checksum}.
\item Max Hailperin has sent in a number of corrections and
suggestions. Max is one of the authors of the extraordinary {\em
Concrete Abstractions}, which you might want to read when you are
done with this book.
\item Chotipat Pornavalai found an error in an error message.
\item Stanislaw Antol sent a list of very helpful suggestions.
\item Eric Pashman sent a number of corrections for Chapters 4--11.
\item Miguel Azevedo found some typos.
\item Jianhua Liu sent in a long list of corrections.
\item Nick King found a missing word.
\item Martin Zuther sent a long list of suggestions.
\item Adam Zimmerman found an inconsistency in my instance
of an ``instance'' and several other errors.
\item Ratnakar Tiwari suggested a footnote explaining degenerate
triangles.
\item Anurag Goel suggested another solution for \verb"is_abecedarian"
and sent some additional corrections. And he knows how to
spell Jane Austen.
\item Kelli Kratzer spotted one of the typos.
\item Mark Griffiths pointed out a confusing example in Chapter 3.
\item Roydan Ongie found an error in my Newton's method.
\item Patryk Wolowiec helped me with a problem in the HTML version.
\item Mark Chonofsky told me about a new keyword in Python 3.
\item Russell Coleman helped me with my geometry.
\item Wei Huang spotted several typographical errors.
\item Karen Barber spotted the the oldest typo in the book.
\item Nam Nguyen found a typo and pointed out that I used the Decorator
pattern but didn't mention it by name.
\item St\'{e}phane Morin sent in several corrections and suggestions.
\item Paul Stoop corrected a typo in \verb+uses_only+.
\item Eric Bronner pointed out a confusion in the discussion of the
order of operations.
\item Alexandros Gezerlis set a new standard for the number and
quality of suggestions he submitted. We are deeply grateful!
\item Gray Thomas knows his right from his left.
\item Giovanni Escobar Sosa sent a long list of corrections and
suggestions.
\item Alix Etienne fixed one of the URLs.
\item Kuang He found a typo.
\item Daniel Neilson corrected an error about the order of operations.
\item Will McGinnis pointed out that {\tt polyline} was defined
differently in two places.
\item Swarup Sahoo spotted a missing semi-colon.
\item Frank Hecker pointed out an exercise that was under-specified, and
some broken links.
\item Animesh B helped me clean up a confusing example.
\item Martin Caspersen found two round-off errors.
\item Gregor Ulm sent several corrections and suggestions.
\item Dimitrios Tsirigkas suggested I clarify an exercise.
\item Carlos Tafur sent a page of corrections and suggestions.
\item Martin Nordsletten found a bug in an exercise solution.
\item Lars O.D. Christensen found a broken reference.
\item Victor Simeone found a typo.
\item Sven Hoexter pointed out that a variable named {\tt input}
shadows a build-in function.
\item Viet Le found a typo.
\item Stephen Gregory pointed out the problem with {\tt cmp}
in Python 3.
\item Matthew Shultz let me know about a broken link.
\item Lokesh Kumar Makani let me know about some broken links and some
changes in error messages.
\item Ishwar Bhat corrected my statement of Fermat's last theorem.
% ENDCONTRIB
\end{itemize}
\normalsize
\clearemptydoublepage
% TABLE OF CONTENTS
\begin{latexonly}
\tableofcontents
\clearemptydoublepage
\end{latexonly}
% START THE BOOK
\mainmatter
\chapter{The way of the program}
The goal of this book is to teach you to think like a
computer scientist. This way of thinking combines some of the best features
of mathematics, engineering, and natural science. Like mathematicians,
computer scientists use formal languages to denote ideas (specifically
computations). Like engineers, they design things, assembling components
into systems and evaluating tradeoffs among alternatives. Like scientists,
they observe the behavior of complex systems, form hypotheses, and test
predictions.
\index{problem solving}
The single most important skill for a computer scientist is {\bf
problem solving}. Problem solving means the ability to formulate
problems, think creatively about solutions, and express a solution clearly
and accurately. As it turns out, the process of learning to program is an
excellent opportunity to practice problem-solving skills. That's why
this chapter is called, ``The way of the program.''
On one level, you will be learning to program, a useful
skill by itself. On another level, you will use programming as a means to
an end. As we go along, that end will become clearer.
\section{The Python programming language}
\index{programming language}
\index{language!programming}
The programming language you will learn is Python. Python is
an example of a {\bf high-level language}; other high-level languages
you might have heard of are C, C++, Perl, and Java.
There are
also {\bf low-level languages}, sometimes referred to as ``machine
languages'' or ``assembly languages.'' Loosely speaking, computers
can only run programs written in low-level languages. So
programs written in a high-level language have to be processed before
they can run. This extra processing takes some time, which is a small
disadvantage of high-level languages.
\index{portability}
\index{high-level language}
\index{low-level language}
\index{language!high-level}
\index{language!low-level}
The advantages are enormous. First, it is much easier to program
in a high-level language. Programs written in a high-level language
take less time to write, they are shorter and easier to read, and they
are more likely to be correct. Second, high-level languages are {\bf
portable}, meaning that they can run on different kinds of computers
with few or no modifications. Low-level programs can run on only one
kind of computer and have to be rewritten to run on another.
Due to these advantages, almost all programs are written in high-level
languages. Low-level languages are used only for a few specialized
applications.
\index{compile}
\index{interpret}
Two kinds of programs process high-level languages into low-level
languages: {\bf interpreters} and {\bf compilers}. An interpreter
reads a high-level program and executes it, meaning that it does what
the program says. It processes the program a little at a time,
alternately reading lines and performing computations.
Figure~\ref{fig.interpret} shows the structure of an interpreter.
\index{source code}
\index{object code}
\index{executable}
\begin{figure}
\centerline
{\includegraphics[scale=0.9]{figs/interpret.pdf}}
\caption{An interpreter processes the program a little at a time,
alternately reading lines and performing computations.}
\label{fig.interpret}
\end{figure}
A compiler reads the program and translates it completely before the
program starts running. In this context, the high-level program is
called the {\bf source code}, and the translated program is called the
{\bf object code} or the {\bf executable}. Once a program is
compiled, you can execute it repeatedly without further translation.
Figure~\ref{fig.compile} shows the structure of a compiler.
\begin{figure}
\centerline
{\includegraphics[scale=0.9]{figs/compile.pdf}}
\caption{A compiler translates source code into object code, which is
run by a hardware executor.}
\label{fig.compile}
\end{figure}
Python is considered an interpreted language because Python programs
are executed by an interpreter. There are two ways to use the
interpreter: {\bf interactive mode} and {\bf script mode}. In
interactive mode, you type Python programs and the interpreter displays
the result:
\index{interactive mode}
\index{script mode}
\begin{verbatim}
>>> 1 + 1
2
\end{verbatim}
%
The chevron, \verb">>>", is the
{\bf prompt} the interpreter uses to indicate that it is ready. If
you type {\tt 1 + 1}, the interpreter replies {\tt 2}.
\index{prompt}
Alternatively, you can store code in a file and use the interpreter to
execute the contents of the file, which is called a {\bf script}. By
convention, Python scripts have names that end with {\tt .py}.
\index{script}
To execute the script, you have to tell the interpreter the name of
the file. If you have a script named {\tt dinsdale.py} and you are
working in a UNIX command window, you type {\tt python
dinsdale.py}. In other development environments, the details of
executing scripts are different. You can find instructions for
your environment at the Python website \url{http://python.org}.
\index{testing!interactive mode}
Working in interactive mode is convenient for testing small pieces of
code because you can type and execute them immediately. But for
anything more than a few lines, you should save your code
as a script so you can modify and execute it in the future.
\section{What is a program?}
A {\bf program} is a sequence of instructions that specifies how to
perform a computation. The computation might be something
mathematical, such as solving a system of equations or finding the
roots of a polynomial, but it can also be a symbolic computation, such
as searching and replacing text in a document or (strangely enough)
compiling a program.
\index{program}
The details look different in different languages, but a few basic
instructions appear in just about every language:
\begin{description}
\item[input:] Get data from the keyboard, a file, or some
other device.
\item[output:] Display data on the screen or send data to a
file or other device.
\item[math:] Perform basic mathematical operations like addition and
multiplication.
\item[conditional execution:] Check for certain conditions and
execute the appropriate code.
\item[repetition:] Perform some action repeatedly, usually with
some variation.
\end{description}
Believe it or not, that's pretty much all there is to it. Every
program you've ever used, no matter how complicated, is made up of
instructions that look pretty much like these. So you can think of
programming as the process of breaking a large, complex task
into smaller and smaller subtasks until the subtasks are
simple enough to be performed with one of these basic instructions.
\index{algorithm}
That may be a little vague, but we will come back to this topic
when we talk about {\bf algorithms}.
\section{What is debugging?}
\index{debugging}
\index{bug}
Programming is error-prone. For whimsical reasons, programming errors
are called {\bf bugs} and the process of tracking them down is called
{\bf debugging}.
\index{debugging}
\index{bug}
Three kinds of errors can occur in a program: syntax errors, runtime
errors, and semantic errors. It is useful
to distinguish between them in order to track them down more quickly.
\subsection{Syntax errors}
\index{syntax error}
\index{error!syntax}
\index{error message}
Python can only execute a program if the syntax is
correct; otherwise, the interpreter displays an error message.
{\bf Syntax} refers to the structure of a program and the rules about
that structure.
For example, parentheses have to come in matching pairs, so
{\tt (1 + 2)} is legal, but {\tt 8)} is a {\bf syntax error}.
\index{syntax}
\index{parentheses!matching}
\index{syntax}
\index{cummings, e. e.}
In English, readers can tolerate most syntax errors, which is why we
can read the poetry of e. e. cummings without spewing error messages.
Python is not so forgiving. If there is a single syntax error
anywhere in your program, Python will display an error message and quit,
and you will not be able to run your program. During the first few
weeks of your programming career, you will probably spend a lot of
time tracking down syntax errors. As you gain experience, you will
make fewer errors and find them faster.
\subsection{Runtime errors}
\label{runtime}
The second type of error is a runtime error, so called because the
error does not appear until after the program has started running.
These errors are also called {\bf exceptions} because they usually
indicate that something exceptional (and bad) has happened.
\index{runtime error}
\index{error!runtime}
\index{exception}
\index{safe language}
\index{language!safe}
Runtime errors are rare in the simple programs you will see in the
first few chapters, so it might be a while before you encounter one.
\subsection{Semantic errors}
\index{semantics}
\index{semantic error}
\index{error!semantic}
\index{error message}
The third type of error is the {\bf semantic error}. If there is a
semantic error in your program, it will run successfully in the sense
that the computer will not generate any error messages, but it will
not do the right thing. It will do something else. Specifically, it
will do what you told it to do.
The problem is that the program you wrote is not the program you
wanted to write. The meaning of the program (its semantics) is wrong.
Identifying semantic errors can be tricky because it requires you to work
backward by looking at the output of the program and trying to figure
out what it is doing.
\subsection{Experimental debugging}
One of the most important skills you will acquire is debugging.
Although it can be frustrating, debugging is one of the most
intellectually rich, challenging, and interesting parts of
programming.
\index{experimental debugging}
\index{debugging!experimental}
In some ways, debugging is like detective work. You are confronted
with clues, and you have to infer the processes and events that led
to the results you see.
Debugging is also like an experimental science. Once you have an idea
about what is going wrong, you modify your program and try again. If
your hypothesis was correct, then you can predict the result of the
modification, and you take a step closer to a working program. If
your hypothesis was wrong, you have to come up with a new one. As
Sherlock Holmes pointed out, ``When you have eliminated the
impossible, whatever remains, however improbable, must be the truth.''
(A. Conan Doyle, {\em The Sign of Four})
\index{Holmes, Sherlock}
\index{Doyle, Arthur Conan}