1
The way of the program
1
1.1
What is a programming language? . . . . . . . . . . . . . . .
1
1.2
What is a program? . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
What is debugging? . . . . . . . . . . . . . . . . . . . . . . .
4
1.4
Formal and natural languages . . . . . . . . . . . . . . . . .
6
1.5
The first program . . . . . . . . . . . . . . . . . . . . . . . .
8
1.6
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.7
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2
Variables and types
13
2.1
More printing . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2
Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.3
Assignment
. . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.4
Printing variables . . . . . . . . . . . . . . . . . . . . . . . .
16
2.5
Keywords
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.6
Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
xii
Contents
2.7
Order of operations . . . . . . . . . . . . . . . . . . . . . . .
19
2.8
Operators for Strings . . . . . . . . . . . . . . . . . . . . . 20
2.9
Composition . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.10
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.11
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3
Methods
25
3.1
Floating-point . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.2
Converting from double to int . . . . . . . . . . . . . . . . 26
3.3
Math methods . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.4
Composition . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.5
Adding new methods . . . . . . . . . . . . . . . . . . . . . .
29
3.6
Classes and methods . . . . . . . . . . . . . . . . . . . . . .
31
3.7
Programs with multiple methods . . . . . . . . . . . . . . . .
32
3.8
Parameters and arguments . . . . . . . . . . . . . . . . . . .
33
3.9
Stack diagrams
. . . . . . . . . . . . . . . . . . . . . . . . .
34
3.10
Methods with multiple parameters . . . . . . . . . . . . . . .
35
3.11
Methods with results . . . . . . . . . . . . . . . . . . . . . .
36
3.12
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.13
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4
Conditionals and recursion
39
4.1
The modulus operator
. . . . . . . . . . . . . . . . . . . . .
39
4.2
Conditional execution . . . . . . . . . . . . . . . . . . . . . .
39
4.3
Alternative execution . . . . . . . . . . . . . . . . . . . . . .
40
Contents
xiii
4.4
Chained conditionals . . . . . . . . . . . . . . . . . . . . . .
41
4.5
Nested conditionals . . . . . . . . . . . . . . . . . . . . . . .
42
4.6
The return statement . . . . . . . . . . . . . . . . . . . . . .
43
4.7
Type conversion . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.8
Recursion
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.9
Stack diagrams for recursive methods . . . . . . . . . . . . .
46
4.10
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.11
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5
GridWorld: Part One
51
5.1
Getting started . . . . . . . . . . . . . . . . . . . . . . . . .
51
5.2
BugRunner . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
6
Fruitful methods
55
6.1
Return values . . . . . . . . . . . . . . . . . . . . . . . . . .
55
6.2
Program development . . . . . . . . . . . . . . . . . . . . . .
57
6.3
Composition . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.4
Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.5
Boolean expressions . . . . . . . . . . . . . . . . . . . . . . .
62
6.6
Logical operators . . . . . . . . . . . . . . . . . . . . . . . .
63
6.7
Boolean methods . . . . . . . . . . . . . . . . . . . . . . . .
63
6.8
More recursion . . . . . . . . . . . . . . . . . . . . . . . . . .
64
6.9
Leap of faith . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
6.10
One more example
. . . . . . . . . . . . . . . . . . . . . . .
68
6.11
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
6.12
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
xiv
Contents
7
Iteration
75
7.1
Multiple assignment . . . . . . . . . . . . . . . . . . . . . . .
75
7.2
Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
7.3
The while statement . . . . . . . . . . . . . . . . . . . . . . 76
7.4
Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
7.5
Two-dimensional tables . . . . . . . . . . . . . . . . . . . . .
81
7.6
Encapsulation and generalization
. . . . . . . . . . . . . . .
81
7.7
Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
7.8
More encapsulation . . . . . . . . . . . . . . . . . . . . . . .
83
7.9
Local variables . . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.10
More generalization . . . . . . . . . . . . . . . . . . . . . . .
84
7.11
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
7.12
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
8
Strings and things
91
8.1
Invoking methods on objects . . . . . . . . . . . . . . . . . .
91
8.2
Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
8.3
Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
8.4
Run-time errors . . . . . . . . . . . . . . . . . . . . . . . . .
93
8.5
Reading documentation . . . . . . . . . . . . . . . . . . . . .
95
8.6
The indexOf method . . . . . . . . . . . . . . . . . . . . . . 96
8.7
Looping and counting . . . . . . . . . . . . . . . . . . . . . .
96
8.8
Increment and decrement operators . . . . . . . . . . . . . .
97
8.9
Strings are immutable . . . . . . . . . . . . . . . . . . . . .
98
8.10
Strings are incomparable
. . . . . . . . . . . . . . . . . . .
99
8.11
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.12
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Contents
xv
9
Mutable objects
107
9.1
Points and Rectangles . . . . . . . . . . . . . . . . . . . . . 107
9.2
Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.3
Point objects . . . . . . . . . . . . . . . . . . . . . . . . . . 108
9.4
Instance variables . . . . . . . . . . . . . . . . . . . . . . . . 109
9.5
Objects as parameters
. . . . . . . . . . . . . . . . . . . . . 110
9.6
Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
9.7
Objects as return types . . . . . . . . . . . . . . . . . . . . . 111
9.8
Objects are mutable . . . . . . . . . . . . . . . . . . . . . . . 111
9.9
Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.10
null . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
9.11
Garbage collection
. . . . . . . . . . . . . . . . . . . . . . . 114
9.12
Objects and primitives . . . . . . . . . . . . . . . . . . . . . 115
9.13
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
9.14
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
10 GridWorld: Part 2
123
10.1
Termites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
10.2
Langton’s Termite . . . . . . . . . . . . . . . . . . . . . . . . 129
11 Create your own objects
131
11.1
Class definitions and object types . . . . . . . . . . . . . . . 131
11.2
Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
11.3
Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
11.4
More constructors . . . . . . . . . . . . . . . . . . . . . . . . 134
xvi
Contents
11.5
Creating a new object
. . . . . . . . . . . . . . . . . . . . . 135
11.6
Printing objects . . . . . . . . . . . . . . . . . . . . . . . . . 136
11.7
Operations on objects . . . . . . . . . . . . . . . . . . . . . . 137
11.8
Pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . 137
11.9
Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
11.10 Fill-in methods . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.11 Incremental development and planning . . . . . . . . . . . . 142
11.12 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . 143
11.13 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
11.14 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
11.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
12 Arrays
149
12.1
Accessing elements . . . . . . . . . . . . . . . . . . . . . . . 150
12.2
Copying arrays
. . . . . . . . . . . . . . . . . . . . . . . . . 151
12.3
for loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
12.4
Arrays and objects . . . . . . . . . . . . . . . . . . . . . . . 152
12.5
Array length . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
12.6
Random numbers . . . . . . . . . . . . . . . . . . . . . . . . 153
12.7
Array of random numbers
. . . . . . . . . . . . . . . . . . . 154
12.8
Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
12.9
The histogram . . . . . . . . . . . . . . . . . . . . . . . . . . 157
12.10 A single-pass solution . . . . . . . . . . . . . . . . . . . . . . 158
12.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
12.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Contents
xvii
13 Arrays of Objects
165
13.1
The Road Ahead . . . . . . . . . . . . . . . . . . . . . . . . 165
13.2
Card objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
13.3
The printCard method . . . . . . . . . . . . . . . . . . . . . 167
13.4
The sameCard method . . . . . . . . . . . . . . . . . . . . . 169
13.5
The compareCard method . . . . . . . . . . . . . . . . . . . 170
13.6
Arrays of cards . . . . . . . . . . . . . . . . . . . . . . . . . 171
13.7
The printDeck method . . . . . . . . . . . . . . . . . . . . . 173
13.8
Searching
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
13.9
Decks and subdecks . . . . . . . . . . . . . . . . . . . . . . . 177
13.10 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
13.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
14 Objects of Arrays
181
14.1
The Deck class . . . . . . . . . . . . . . . . . . . . . . . . . . 181
14.2
Shuffling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
14.3
Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
14.4
Subdecks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
14.5
Shuffling and dealing . . . . . . . . . . . . . . . . . . . . . . 185
14.6
Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
14.7
Class variables . . . . . . . . . . . . . . . . . . . . . . . . . . 189
14.8
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
14.9
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
xviii
Contents
15 Object-oriented programming
193
15.1
Programming languages and styles . . . . . . . . . . . . . . . 193
15.2
Object methods and class methods
. . . . . . . . . . . . . . 194
15.3
The toString method . . . . . . . . . . . . . . . . . . . . . 195
15.4
The equals method . . . . . . . . . . . . . . . . . . . . . . . 196
15.5
Oddities and errors . . . . . . . . . . . . . . . . . . . . . . . 197
15.6
Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
15.7
The class hierarchy . . . . . . . . . . . . . . . . . . . . . . . 199
15.8
Object-oriented design . . . . . . . . . . . . . . . . . . . . . 199
15.9
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
15.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
16 GridWorld: Part 3
203
16.1
ArrayList . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
16.2
Interfaces
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
16.3
public and private . . . . . . . . . . . . . . . . . . . . . . 206
16.4
Game of Life . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
16.5
LifeRunner . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
16.6
LifeRock
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
16.7
Simultaneous updates . . . . . . . . . . . . . . . . . . . . . . 209
16.8
Initial conditions
. . . . . . . . . . . . . . . . . . . . . . . . 210
A Graphics
213
A.1
Java 2D Graphics . . . . . . . . . . . . . . . . . . . . . . . . 213
A.2
Graphics methods
. . . . . . . . . . . . . . . . . . . . . . . 214
Contents
xix
A.3
Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.4
Color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
A.5
Mickey Mouse . . . . . . . . . . . . . . . . . . . . . . . . . . 216
B Input and Output in Java
221
B.1
System objects
. . . . . . . . . . . . . . . . . . . . . . . . . 221
B.2
Keyboard input . . . . . . . . . . . . . . . . . . . . . . . . . 222
B.3
File input . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
B.4
Catching exceptions . . . . . . . . . . . . . . . . . . . . . . . 223
C Program development
225
C.1
Strategies
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
C.2
Failure modes . . . . . . . . . . . . . . . . . . . . . . . . . . 226
D Debugging
229
D.1
Syntax errors
. . . . . . . . . . . . . . . . . . . . . . . . . . 229
D.2
Run-time errors . . . . . . . . . . . . . . . . . . . . . . . . . 233
D.3
Logic errors . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
xx
Contents