Repository navigation
Expand file tree
/
Copy paththinkapjava.tex
More file actions
12695 lines (9803 loc) · 387 KB
/
Copy paththinkapjava.tex
File metadata and controls
12695 lines (9803 loc) · 387 KB
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 Java: How to think like a computer scientist''
% Copyright (C) 2012 Allen B. Downey
% Permission is granted to copy, distribute, transmit and adapt
% this work under a Creative Commons
% Attribution-NonCommercial-ShareAlike 3.0 Unported License:
% http://creativecommons.org/licenses/by-nc-sa/3.0/
% If you are interested in distributing a commercial version of this
% work, please contact Allen B. Downey.
% The original form of this book is LaTeX source code. Compiling this
% LaTeX source has the effect of generating a device-independent
% representation of the book, which can be converted to other formats
% and printed.
% The LaTeX source for this book is available from http://thinkapjava.com
% and http://code.google.com/p/thinkapjava/source/checkout
% This book was typeset using LaTeX . The illustrations were
% drawn in xfig. All of these are free, open-source programs.
%%----------------------------------------------------------------
% How to compile this document:
% If your environment provides latex, makeindex, and dvips,
% the following commands should produce a Postscript version
% of the book.
% latex book
% makeindex book
% latex book
% dvips -o book.ps book
% You will also need the following (fairly standard) latex
% packages: url, epsfig, makeidx, fancyhdr
% This distribution also includes a Makefile that should
% compile both the Postscript and PDF versions of the book.
%%-----------------------------------------------------------------
\documentclass[12pt]{book}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{url}
\usepackage{fancyhdr}
\usepackage{verbatim}
\usepackage{moreverb}
\usepackage{hevea}
\usepackage{upquote}
\usepackage{graphicx}
\newcommand{\thetitle}{Think Java: How to Think Like a Computer Scientist}
\newcommand{\theversion}{5.1.2}
\newif\ifplastex
\plastexfalse
\ifplastex
% PLASTEX ONLY
\usepackage{localdef}
\maketitle
\else
% LATEX AND HTML
\newtheoremstyle{exercise}
{\topsep} % space above
{\topsep} % space below
{} % body font
{} % indent amount
{\bfseries} % head font
{.} % punctuation
{5pt} % head space
{} % custom head
\theoremstyle{exercise}
\newtheorem{exercise}{Exercise}[chapter]
\title{\thetitle}
\author{Allen B. Downey}
% these styles get translated in CSS for the HTML version
\newstyle{a:link}{color:black;}
\newstyle{pre}{color:darkgreen;font-size:110\%;}
\newstyle{tt}{color:darkgreen;font-size:110\%;}
\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
% define styles for syntax highlighting in code listings
\usepackage[usenames,dvipsnames]{color}
\usepackage{listings}
\lstset{
language=java,
basicstyle=\ttfamily,
commentstyle=\color{Green},
keywordstyle=\color{blue},
stringstyle=\color{Orange},
columns=fullflexible,
keepspaces=true,
showstringspaces=false,
aboveskip=4pt,
belowskip=-4pt
}
% enable pdf hyperlinks, table of contents, and document properties
\usepackage[pdftex]{hyperref}
\makeatletter
\hypersetup{%
pdftitle={\@title},
pdfauthor={\@author},
pdfsubject={Version \theversion},
pdfkeywords={},
bookmarksopen=false,
colorlinks=true,
citecolor=black,
filecolor=black,
linkcolor=black,
urlcolor=blue
}
\makeatother
\begin{document}
\frontmatter
% title page for the HTML version
\begin{htmlonly}
% TITLE PAGE FOR HTML VERSION
{\Large Think Java}
{\large Allen B. Downey}
Version \theversion
\setcounter{chapter}{-1}
\end{htmlonly}
% BEGINNING OF LATEXONLY
\input{latexonly}
\begin{latexonly}
%-half title--------------------------------------------------
%\thispagestyle{empty}
%
%\begin{flushright}
%\vspace*{2.5in}
%
%{\huge Think Java}
%
%\vspace{1in}
%
%{\LARGE How to Think Like a Computer Scientist}
%
%\vfill
%
%\end{flushright}
%--verso------------------------------------------------------
%%\clearemptydoublepage
%\cleardoublepage
%--title page--------------------------------------------------
\pagebreak
\thispagestyle{empty}
\begin{flushright}
\vspace*{2.5in}
{\huge Think Java}
\vspace{0.25in}
{\LARGE How to Think Like a Computer Scientist}
\vspace{1in}
{\Large
Allen B. Downey
}
\vspace{1in}
{\Large \theversion}
\vfill
\end{flushright}
%--copyright--------------------------------------------------
\pagebreak
\thispagestyle{empty}
Copyright \copyright ~2012 Allen Downey.
\vspace{0.25in}
Permission is granted to copy, distribute, transmit and adapt
this work under a Creative Commons
Attribution-NonCommercial-ShareAlike 3.0 Unported License:
\url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
If you are interested in distributing a commercial version of this
work, please contact Allen B. Downey.
The original form of this book is \LaTeX\ source code. Compiling this
\LaTeX\ source has the effect of generating a device-independent
representation of the book, which can be converted to other formats
and printed.
The \LaTeX\ source for this book is available from:
\url{http://thinkapjava.com}
This book was typeset using \LaTeX . The illustrations were
drawn in xfig. All of these are free, open-source programs.
\vspace{0.25in}
%-----------------------------------------------------------------
\end{latexonly}
\fi
% END OF THE PART WE SKIP FOR PLASTEX
\chapter{Preface}
\begin{quote}
``As we enjoy great Advantages from the Inventions of others,
we should be glad of an Opportunity to serve others by any
Invention of ours, and this we should do freely and generously.''
---Benjamin Franklin, quoted in {\em Benjamin Franklin} by
Edmund S. Morgan.
\end{quote}
\subsection*{Why I wrote this book}
This is the fifth edition of a book I started writing in 1999,
when I was teaching at Colby College. I had taught an introductory
computer science class using the Java programming language, but I
had not found a textbook I was happy with. For one thing,
they were all too big! There was no way my students would read
800 pages of dense, technical material, even if I wanted them to.
And I didn't want them to. Most of the material was too
specific---details about Java and its libraries that would be obsolete
by the end of the semester, and that obscured the material I really
wanted to get to.
The other problem I found was that the introduction to object-oriented
programming was too abrupt. Many students who were otherwise
doing well just hit a wall when we got to objects, whether we did
it at the beginning, middle or end.
So I started writing. I wrote a chapter a day for 13 days, and on
the 14th day I edited. Then I sent it to be photocopied and bound.
When I handed it out on the first day of class, I told the students
that they would be expected to read one chapter a week. In other
words, they would read it seven times slower than I wrote it.
\subsection*{The philosophy behind it}
Here are some of the ideas that make the book the way it is:
\begin{itemize}
\item Vocabulary is important. Students need to be able to talk
about programs and understand what I am saying. I try to
introduce the minimum number of terms, to define them carefully
when they are first used, and to organize them in glossaries
at the end of each chapter. In my class, I include vocabulary
questions on quizzes and exams, and require students to use
appropriate terms in short-answer responses.
\item To write a program, students have to understand the
algorithm, know the programming language, and they have to be
able to debug. I think too many books neglect debugging. This
book includes an appendix on debugging and an appendix on program
development (which can help avoid debugging). I recommend that
students read this material early and come back to it often.
\item Some concepts take time to sink in. Some of the more
difficult ideas in the book, like recursion, appear several times.
By coming back to these ideas, I am trying to give students a
chance to review and reinforce or, if they missed it the first time,
a chance to catch up.
\item I try to use the minimum amount of Java to get the
maximum amount of programming power. The purpose of this book
is to teach programming and some introductory ideas from computer
science, not Java. I left out some language features, like
the {\tt switch} statement, that are unnecessary, and avoided
most of the libraries, especially the ones like the AWT that have been
changing quickly or are likely to be replaced.
\end{itemize}
The minimalism of my approach has some advantages.
Each chapter is about ten pages, not including the exercises.
In my classes I ask students to read each chapter before we
discuss it, and I have found that they are willing to do that
and their comprehension is good. Their preparation makes
class time available for discussion of the more abstract material,
in-class exercises, and additional topics that aren't in the
book.
But minimalism has some disadvantages. There is not much here
that is intrinsically fun. Most of my examples demonstrate the
most basic use of a language feature, and many of the exercises
involve string manipulation and mathematical ideas. I think some
of them are fun, but many of the things that excite students
about computer science, like graphics, sound and network applications,
are given short shrift.
The problem is that many of the more exciting features involve
lots of details and not much concept. Pedagogically, that means
a lot of effort for not much payoff. So there is a tradeoff between
the material that students enjoy and the material that is most
intellectually rich. I leave it to individual teachers to find
the balance that is best for their classes. To help, the book
includes appendices that cover graphics, keyboard input and
file input.
\subsection*{Object-oriented programming}
Some books introduce objects immediately; others warm up with a more
procedural style and develop object-oriented style more gradually.
This book uses the ``objects late'' approach.
Many of Java's object-oriented features are motivated
by problems with previous languages, and their implementations
are influenced by this history. Some of these features are
hard to explain if students aren't familiar with the problems
they solve.
It wasn't my intention to postpone object-oriented programming.
On the contrary, I got to it as quickly as I could, limited by
my intention to introduce concepts one at a time, as clearly
as possible, in a way that allows students to practice each
idea in isolation before adding the next. But I have to admit
that it takes some time to get there.
\subsection*{The Computer Science AP Exam}
Naturally, when the College Board announced that the AP Exam
would switch to Java, I made plans to update the Java version of
the book. Looking at the proposed AP Syllabus, I saw that their
subset of Java was all but identical to the subset I had chosen.
During January 2003, I worked on the Fourth Edition of the book,
making these changes:
\begin{itemize}
\item I added sections to improve coverage of the AP syllabus.
\item I improved the appendices on debugging and program development.
\item I collected the exercises, quizzes, and exam questions I
had used in my classes and put them at the end of the appropriate
chapters. I also made up some problems that are intended to
help with AP Exam preparation.
\end{itemize}
Finally, in August 2011 I wrote the fifth edition, adding
coverage of the GridWorld Case Study that is part of the AP Exam.
\subsection*{Free books!}
Since the beginning, this book has been under a license that allows users
to copy, distribute and modify the book. Readers can download the
book in a variety of formats and read it on screen or print it.
Teachers are free to print as many copies as they need. And anyone is
free to customize the book for their needs.
People have translated the book into other computer languages
(including Python and Eiffel), and other natural languages (including
Spanish, French and German). Many of these derivatives are also
available under free licenses.
Motivated by Open
Source Software, I adopted the philosophy of releasing the
book early and updating it often. I do my best to minimize the
number of errors, but I also depend on readers to help out.
The response has been great. I get messages almost every day from
people who have read the book and liked it enough to take the trouble
to send in a ``bug report.'' Often I can correct an error
and post an updated version within a few minutes. I think of the
book as a work in progress, improving a little whenever I have time
to make a revision, or when readers send feedback.
\subsection*{Oh, the title}
I get a lot of grief about the title of the book. Not everyone
understands that it is---mostly---a joke.
Reading this book will probably not make you think like a computer
scientist. That takes time, experience, and probably a few more
classes.
But there is a kernel of truth in the title: this book is not
about Java, and it is only partly about programming. If it is
successful, this book is about a way of thinking. Computer scientists
have an approach to problem-solving, and a way of crafting solutions,
that is unique, versatile and powerful. I hope that this book
gives you a sense of what that approach is, and that at some
point you will find yourself thinking like a computer scientist.
\vspace{0.2in}
\begin{flushleft}
Allen Downey\\
Needham, Massachusetts\\
July 13, 2011
\end{flushleft}
\section*{Contributors List}
When I started writing free books, it didn't occur to me to keep
a contributors list. When Jeff Elkner suggested it, it seemed so
obvious that I am embarassed by the omission. This list starts
with the 4th Edition, so it omits many people who contributed
suggestions and corrections to earlier versions.
If you have additional comments, please send them to: \\
\href{mailto:feedback@greenteapress.com}{feedback@greenteapress.com}
\begin{itemize}
\item Ellen Hildreth used this book to teach Data Structures at
Wellesley College, and she gave me a whole stack of corrections,
along with some great suggestions.
\item Tania Passfield pointed out that the glossary of Chapter 4
has some leftover terms that no longer appear in the text.
\item Elizabeth Wiethoff noticed that my series expansion of
$\exp(-x^2)$ was wrong. She is also working on a Ruby version of
the book!
\item Matt Crawford sent in a whole patch file full of corrections!
\item Chi-Yu Li pointed out a typo and an error in one of the code
examples.
\item Doan Thanh Nam corrected an example in Chapter 3.
\item Stijn Debrouwere found a math typo.
\item Muhammad Saied translated the book into Arabic, and found
several errors.
\item Marius Margowski found an inconsistency in a code example.
\item Guy Driesen found several typos.
\item Leslie Klein discovered yet another error in the series expansion
of $\exp(-x^2)$, identified typos in the card array figures, and gave
helpful suggestions to clarify several exercises.
\end{itemize}
Finally, I wish to acknowledge Chris Mayfield for his significant
contribution to version 5.1 of this book. His careful review
lead to over one hundred corrections and improvements throughout.
Several new features include embedded hypertext links and cross
references, consistent layout of all exercises, and Java syntax
highlighting in code examples.
% endcontrib
% table of contents
\setcounter{tocdepth}{1}
\tableofcontents
% main matter
\mainmatter
\chapter{The way of the program}
\label{chap01}
The goal of this book is to teach you to think like a
computer scientist. I like the way computer scientists think because
they combine 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.
The single most important skill for a computer scientist is {\bf
problem-solving}. By that I mean 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, which is 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{What is a programming language?}
\index{programming language}
\index{language!programming}
The programming language you will be learning is Java, which is
relatively new (Sun released the first version in May, 1995). Java is
an example of a {\bf high-level language}; other high-level languages
you might have heard of are Python, C or C++, and Perl.
As you might infer from the name ``high-level language,'' there are
also {\bf low-level languages}, sometimes called machine
language or assembly language. Loosely-speaking, computers can only
run programs written in low-level languages. Thus, programs
written in a high-level language have to be translated before they can
run. This translation takes time, which is a small disadvantage
of high-level languages.
\index{portable}
\index{high-level language}
\index{low-level language}
\index{language!high-level}
\index{language!low-level}
The advantages are enormous. First,
it is {\em much} easier to program in a high-level language:
the program takes less time to write,
it's shorter and easier to read, and it's 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 only run
on 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 only used for
a few special applications.
\index{compile}
\index{interpret}
There are two ways to translate a program;
{\bf interpreting} and {\bf compiling}. An interpreter
is a program that reads a high-level program
and does what it says. In effect, it translates
the program line-by-line, alternately reading lines and
carrying out commands.
A compiler is a program that reads a high-level program and
translates it all at once, before running any of the commands.
Often you compile the program as a separate step, and then
run the compiled code later. In this case, the high-level
program is called the {\bf source code}, and the translated
program is called the {\bf object code} or the {\bf executable}.
Java is both compiled and
interpreted. Instead of translating programs into
machine language, the Java compiler generates {\bf byte code}.
Byte code is easy (and fast) to interpret, like machine language,
but it is also portable, like a high-level language. Thus,
it is possible to compile a program on one machine,
transfer the byte code to another machine,
and then interpret the byte code on the other machine. This
ability is an advantage of Java over many other
high-level languages.
\includegraphics{figs/java.pdf}
Although this process may seem complicated, in most program
development environments these steps
are automated for you. Usually you will only have to write a program
and press a button or type a single command to compile and run it. On
the other hand, it is useful to know what steps are
happening in the background, so if something goes wrong you can
figure out what it is.
\section{What is a program?}
A program is a sequence of instructions that specifies how to perform
a computation\footnote{This definition does not apply to all
programming languages; for alternatives, see
\url{http://en.wikipedia.org/wiki/Declarative_programming}.}. The
computation might be something mathematical, like solving a system of
equations or finding the roots of a polynomial, but it can also be a
symbolic computation, like searching and replacing text in a document
or (strangely enough) compiling a program.
\index{statement}
The instructions, which we will call {\bf statements}, look different
in different programming languages, but there are a few basic
operations most languages perform:
\begin{description}
\item[input:] Get data from the keyboard, or 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[testing:] Check for certain conditions and run the
appropriate sequence of statements.
\item[repetition:] Perform some action repeatedly, usually with
some variation.
\end{description}
That's pretty much all there is to it.
Every program you've ever used, no matter how complicated, is
made up of statements that perform these operations. Thus,
one way to describe programming is the process of breaking a
large, complex task up into smaller and smaller subtasks
until the subtasks are simple enough to be performed
with one of these basic operations.
\section{What is debugging?}
\index{debugging}
\index{bug}
For whimsical reasons,
programming errors are called {\bf bugs} and the process
of tracking them down and correcting them is called
{\bf debugging}.
There are three kinds of errors that can occur
in a program, and it is useful to distinguish them
to track them down more quickly.
\subsection{Syntax errors}
\index{syntax error}
\index{error!syntax}
The compiler can only translate a program if the program is
syntactically correct; otherwise, the compilation fails and
you will not be able to run your program. {\bf Syntax}
refers to the structure of your program and the rules about
that structure.
\index{syntax}
For example, in English, a sentence must begin with a capital
letter and end with a period. this sentence contains a syntax
error. So does this one
For most readers, a few syntax errors are not a significant
problem, which is why we can read the poetry of e e cummings
without spewing error messages.
Compilers are not so forgiving. If there is a single syntax
error anywhere in your program, the compiler will print an
error message and quit, and you will not be able to run
your program.
To make matters worse, there are more syntax rules in Java
than there are in English, and the error messages you get from
the compiler are often not very helpful. During the first
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{Run-time errors}
\label{run-time}
\index{run-time error}
\index{error!run-time}
\index{exception}
\index{safe language}
\index{language!safe}
The second type of error is a run-time error, so-called because
the error does not appear until you run the program. In Java,
run-time errors occur when the interpreter is running the byte
code and something goes wrong.
Java tends to be a {\bf safe}
language, which means that the compiler catches a lot of errors.
So run-time errors are rare, especially
for simple programs.
In Java, run-time errors are called {\bf exceptions},
and in most environments they appear as windows or dialog
boxes that contain information about what happened and what
the program was doing when it happened. This information is
useful for debugging.
\subsection{Logic errors and semantics}
\index{semantics}
\index{logic error}
\index{error!logic}
The third type of error is the {\bf logic} or {\bf semantic} error.
If there is a logic error in your program, it will compile and run
without generating 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 semantics, or meaning of the program, are wrong.
Identifying logic errors can be tricky because you have to work
backwards, 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 in this
class is debugging. Although debugging can be frustrating, it
is one of the most interesting, challenging, and
valuable parts of programming.
Debugging is like detective work. You are
confronted with clues and you have to infer the processes
and events that lead to the results you see.
Debugging is also like an experimental science. Once you have an idea
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.''
(From A.~Conan Doyle's {\em The Sign of Four}.)
\index{Holmes, Sherlock}
\index{Doyle, Arthur Conan}
For some people, programming and debugging are the
same thing. That is, programming is the process of gradually
debugging a program until it does what you want. The idea
is that you should always start with a working program that
does {\em something}, and make small modifications, debugging
them as you go, so that you always have a working program.
For example, Linux is an operating system that contains thousands of
lines of code, but it started out as a simple program Linus Torvalds
used to explore the Intel 80386 chip. According to Larry Greenfield,
``One of Linus's earlier projects was a program that would switch
between printing AAAA and BBBB. This later evolved to Linux''
(from {\em The Linux Users' Guide} Beta Version 1).
\index{Linux}
\index{Torvalds, Linux}
\index{Greenfield, Larry}
In later chapters I make more suggestions about debugging
and other programming practices.
\section{Formal and natural languages}
\index{formal language}
\index{natural language}
\index{language!formal}
\index{language!natural}
{\bf Natural languages} are the languages that people speak,
like English, Spanish, and French. They were not designed
by people (although people try to impose order on them);
they evolved naturally.
{\bf Formal languages} are languages designed by people for
specific applications. For example, the notation that mathematicians
use is a formal language that is particularly good at denoting
relationships among numbers and symbols. Chemists use a formal
language to represent the chemical structure of molecules. And
most importantly:
\begin{quote}
{\bf Programming languages are formal languages that have been
designed to express computations.}
\end{quote}
Formal languages have strict rules
about syntax. For example, $3+3=6$ is a syntactically correct
mathematical statement, but $3 \$ =$ is not. Also, $H_2O$ is a
syntactically correct chemical name, but $_2Zz$ is not.
Syntax rules come in two flavors, pertaining to tokens and structure.
Tokens are the basic elements of the language, like words and numbers
and chemical elements. One of the problems with $3 \$ =$ is that
$\$$ is not a legal token in mathematics (at least as far as I
know). Similarly, $_2Zz$ is not legal because there is no element with
the abbreviation $Zz$.
The second type of syntax rule pertains to the structure of a
statement; that is, the way the tokens are arranged. The statement
$3 \$ =$ is structurally illegal, because you can't have an equals
sign at the end of an equation. Similarly, molecular formulas
have to have subscripts after the element name, not before.
When you read a sentence in English or a statement in a formal
language, you have to figure out what the structure of the sentence is
(although in a natural language you do this unconsciously). This
process is called {\bf parsing}.
\index{parse}
Although formal and natural languages have features in
common---tokens, structure, syntax and semantics---there are
differences.
\index{ambiguity}
\index{redundancy}
\index{literalness}
\begin{description}
\item[ambiguity:] Natural languages are full of ambiguity, which
people deal with by using contextual clues and other information.
Formal languages are designed to be unambiguous, which means that
any statement has exactly one meaning, regardless of context.
\item[redundancy:] To make up for ambiguity and reduce
misunderstandings, natural languages are often redundant. Formal
languages are more concise.
\item[literalness:] Natural languages are full of idiom and
metaphor. Formal languages mean exactly what they say.
\end{description}
People who grow up speaking a natural language (everyone) often have a
hard time adjusting to formal languages. In some ways the difference
between formal and natural language is like the difference between
poetry and prose, but more so:
\index{poetry}
\index{prose}
\begin{description}
\item[Poetry:] Words are used for their sounds as well as for
their meaning, and the whole poem together creates an effect or
emotional response. Ambiguity is common and deliberate.
\item[Prose:] The literal meaning of words is more important
and the structure contributes more meaning.
\item[Programs:] The meaning of a computer program is unambiguous
and literal, and can be understood entirely by analysis of the
tokens and structure.
\end{description}
Here are some suggestions for reading programs (and other formal
languages). First, remember that formal languages are much more dense
than natural languages, so it takes longer to read them. Also, the
structure is important, so it is usually not a good idea to read
from top to bottom, left to right. Instead, learn to parse the
program in your head, identifying the tokens and interpreting the
structure. Finally, remember that the details matter. Little things
like spelling errors and bad punctuation, which you can get away
with in natural languages, can make a big difference in a formal
language.
\section{The first program}
\label{hello}
\index{hello world}
Traditionally the first program people write in a new language
is called ``hello world'' because all it does is display the
words ``Hello, World.'' In Java, this program looks like:
\begin{lstlisting}
class Hello {
// main: generate some simple output
public static void main(String[] args) {
System.out.println("Hello, world.");
}
}
\end{lstlisting}
%
This program includes features that are hard to explain to
beginners, but it provides a preview of topics we
will see in detail later.
Java programs are made up of {\bf class definitions}, which have
the form:
\index{class definition}
\index{definition!class}
\begin{lstlisting}
class CLASSNAME {
public static void main (String[] args) {
STATEMENTS
}
}
\end{lstlisting}
%
Here {\tt CLASSNAME} indicates a name chosen by the programmer.
The class name in the example is {\tt Hello}.
\index{class!name}
\index{public}
\index{static}
{\tt main} is a {\bf method}, which is a named collection of
statements. The name {\tt main} is special; it marks the place in the
program where execution begins. When the program runs, it starts at
the first statement in {\tt main} and ends when it finishes the last
statement.
\index{method}
\index{print}
\index{statement!print}
{\tt main} can have any number of statements, but the example has one.
It is a {\bf print statement}, meaning that it displays a message on
the screen. Confusingly, ``print'' can mean ``display something on
the screen,'' or ``send something to the printer.'' In this book I
won't say much about sending things to the printer; we'll do all our
printing on the screen. The print statement ends with a semi-colon
({\tt ;}).
{\tt System.out.println} is a method provided by one of Java's
libraries. A {\bf library} is a collection of class and method
definitions.
\index{library}
Java uses squiggly-braces (\{ and \}) to group things together. The
outermost squiggly-braces (lines 1 and 8) contain the class
definition, and the inner braces contain the definition of {\tt main}.
\index{braces, squiggly}
\index{squiggly braces}
\index{comment}
\index{statement!comment}
Line 3 begins with {\tt //}. That means it's
a {\bf comment}, which is a bit of
English text that you can put a program,
usually to explain what it does. When the compiler
sees {\tt //}, it ignores everything from there until the end
of the line.
\section{Glossary}
\begin{description}
\item[problem-solving:] The process of formulating a problem, finding
a solution, and expressing the solution.
\item[high-level language:] A programming language like Java that
is designed to be easy for humans to read and write.
\item[low-level language:] A programming language that is designed
to be easy for a computer to run. Also called ``machine
language'' or ``assembly language.''
\item[formal language:] Any of the languages people have designed
for specific purposes, like representing mathematical ideas or
computer programs. All programming languages are formal languages.
\item[natural language:] Any of the languages people speak that
have evolved naturally.
\item[portability:] A property of a program that can run on more