This page intentionally left blank Python for Software Design

This page intentionally left blank

Python for Software Design
Python for Software Design is a concise introduction to software design
using the Python programming language. Intended for people with no
programming experience, this book starts with the most basic concepts
and gradually adds new material. Some of the ideas students find most
challenging, like recursion and object-oriented programming, are divided
into a sequence of smaller steps and introduced over the course of several
chapters. The focus is on the programming process, with special emphasis
on debugging. The book includes a wide range of exercises, from short
examples to substantial projects, so that students have ample opportunity
to practice each new concept.
Exercise solutions and code examples along with Swampy, a suite of
Python programs that is used in some of the exercises, are available from
thinkpython.com.
Allen B. Downey, Ph.D., is an Associate Professor of Computer Sci-
ence at the Olin College of Engineering in Needham, Massachusetts. He
has taught at Wellesley College, Colby College, and UC Berkeley. He
has a doctorate in computer science from UC Berkeley and a master’s
degree from MIT. Professor Downey is the author of a previous version
of this book, titled How to Think Like a Computer Scientist: Learning with
Python, which he self-published in 2001.

PYTHON FOR
SOFTWARE
DESIGN
How to Think Like a
Computer Scientist
Allen B. Downey
Olin College of Engineering

CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
First published in print format
ISBN-13 978-0-521-89811-9
ISBN-13 978-0-521-72596-5
ISBN-13 978-0-511-50155-5
© Allen B. Downey 2009
2009
Information on this title: www.cambridge.org/9780521898119
This publication is in copyright. Subject to statutory exception and to the 
provision of relevant collective licensing agreements, no reproduction of any part
may take place without the written permission of Cambridge University Press.
Cambridge University Press has no responsibility for the persistence or accuracy 
of urls for external or third-party internet websites referred to in this publication, 
and does not guarantee that any content on such websites is, or will remain, 
accurate or appropriate.
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
paperback
eBook (Adobe Reader)
hardback

Contents
Preface
page
xi
1
The Way of the Program
1
1.1
The Python Programming Language
1
1.2
What Is a Program?
3
1.3
What Is Debugging?
3
1.3.1 Syntax Errors
3
1.3.2 Runtime Errors
4
1.3.3 Semantic Errors
4
1.3.4 Experimental Debugging
4
1.4
Formal and Natural Languages
5
1.5
The First Program
6
1.6
Debugging
7
1.7
Glossary
8
1.8
Exercises
9
2
Variables, Expressions, and Statements
10
2.1
Values and Types
10
2.2
Variables
11
2.3
Variable Names and Keywords
13
2.4
Statements
13
2.5
Operators and Operands
14
2.6
Expressions
15
2.7
Order of Operations
15
2.8
String Operations
16
2.9
Comments
17
2.10 Debugging
17
2.11 Glossary
18
2.12 Exercises
19
v

vi
Contents
3
Functions
21
3.1
Function Calls
21
3.2
Type Conversion Functions
21
3.3
Math Functions
22
3.4
Composition
23
3.5
Adding New Functions
24
3.6
Definitions and Uses
26
3.7
Flow of Execution
26
3.8
Parameters and Arguments
27
3.9
Variables and Parameters Are Local
28
3.10 Stack Diagrams
29
3.11 Fruitful Functions and Void Functions
30
3.12 Why Functions?
31
3.13 Debugging
31
3.14 Glossary
32
3.15 Exercises
33
4
Case Study: Interface Design
35
4.1
TurtleWorld
35
4.2
Simple Repetition
36
4.3
Exercises
37
4.4
Encapsulation
38
4.5
Generalization
39
4.6
Interface Design
40
4.7
Refactoring
41
4.8
A Development Plan
42
4.9
Docstring
43
4.10 Debugging
43
4.11 Glossary
44
4.12 Exercises
44
5
Conditionals and Recursion
46
5.1
Modulus Operator
46
5.2
Boolean Expressions
46
5.3
Logical Operators
47
5.4
Conditional Execution
48
5.5
Alternative Execution
48
5.6
Chained Conditionals
49
5.7
Nested Conditionals
49
5.8
Recursion
50
5.9
Stack Diagrams for Recursive Functions
52
5.10 Infinite Recursion
52
5.11 Keyboard Input
53
5.12 Debugging
54
5.13 Glossary
55
5.14 Exercises
56

Contents
vii
6
Fruitful Functions
59
6.1
Return Values
59
6.2
Incremental Development
60
6.3
Composition
63
6.4
Boolean Functions
64
6.5
More Recursion
65
6.6
Leap of Faith
67
6.7
One More Example
67
6.8
Checking Types
68
6.9
Debugging
69
6.10 Glossary
70
6.11 Exercises
71
7
Iteration
73
7.1
Multiple Assignment
73
7.2
Updating Variables
74
7.3
The while Statement
75
7.4
break
76
7.5
Square Roots
77
7.6
Algorithms
79
7.7
Debugging
79
7.8
Glossary
80
7.9
Exercises
80
8
Strings
82
8.1
A String Is a Sequence
82
8.2
len
83
8.3
Traversal with a for Loop
83
8.4
String Slices
85
8.5
Strings Are Immutable
86
8.6
Searching
86
8.7
Looping and Counting
87
8.8
string
Methods
87
8.9
The in Operator
89
8.10 String Comparison
89
8.11 Debugging
90
8.12 Glossary
92
8.13 Exercises
92
9
Case Study: Word Play
95
9.1
Reading Word Lists
95
9.2
Exercises
96
9.3
Search
97
9.4
Looping with Indices
99
9.5
Debugging
100
9.6
Glossary
101
9.7
Exercises
101

viii
Contents
10
Lists
103
10.1
A List Is a Sequence
103
10.2
Lists Are Mutable
104
10.3
Traversing a List
105
10.4
List Operations
106
10.5
List Slices
106
10.6
List Methods
107
10.7
Map, Filter, and Reduce
108
10.8
Deleting Elements
109
10.9
Lists and Strings
110
10.10 Objects and Values
111
10.11 Aliasing
113
10.12 List Arguments
113
10.13 Debugging
115
10.14 Glossary
116
10.15 Exercises
117
11
Dictionaries
119
11.1
Dictionary as a Set of Counters
121
11.2
Looping and Dictionaries
123
11.3
Reverse Lookup
123
11.4
Dictionaries and Lists
124
11.5
Memos
126
11.6
Global Variables
128
11.7
Long Integers
129
11.8
Debugging
130
11.9
Glossary
131
11.10 Exercises
131
12
Tuples
133
12.1
Tuples Are Immutable
133
12.2
Tuple Assignment
135
12.3
Tuples as Return Values
136
12.4
Variable-Length Argument Tuples
136
12.5
Lists and Tuples
138
12.6
Dictionaries and Tuples
139
12.7
Comparing Tuples
141
12.8
Sequences of Sequences
142
12.9
Debugging
143
12.10 Glossary
144
12.11 Exercises
145
13
Case Study: Data Structure Selection
147
13.1
Word Frequency Analysis
147
13.2
Random Numbers
148
13.3
Word Histogram
149
13.4
Most Common Words
151

Contents
ix
13.5
Optional Parameters
152
13.6
Dictionary Subtraction
152
13.7
Random Words
153
13.8
Markov Analysis
154
13.9
Data Structures
155
13.10 Debugging
157
13.11 Glossary
158
13.12 Exercises
158
14
Files
159
14.1
Persistence
159
14.2
Reading and Writing
159
14.3
Format Operator
160
14.4
Filenames and Paths
161
14.5
Catching Exceptions
163
14.6
Databases
164
14.7
Pickling
165
14.8
Pipes
166
14.9
Writing Modules
167
14.10 Debugging
168
14.11 Glossary
169
14.12 Exercises
169
15
Classes and Objects
172
15.1
User-Defined Types
172
15.2
Attributes
173
15.3
Rectangles
174
15.4
Instances as Return Values
176
15.5
Objects Are Mutable
176
15.6
Copying
177
15.7
Debugging
179
15.8
Glossary
179
15.9
Exercises
180
16
Classes and Functions
182
16.1
Time
182
16.2
Pure Functions
183
16.3
Modifiers
184
16.4
Prototyping versus Planning
185
16.5
Debugging
187
16.6
Glossary
188
16.7
Exercises
188
17
Classes and Methods
189
17.1
Object-Oriented Features
189
17.2
Printing Objects
190
17.3
Another Example
192
17.4
A More Complicated Example
192

x
Contents
17.5
The Init Method
193
17.6
The __str__ method
194
17.7
Operator Overloading
195
17.8
Type-Based Dispatch
195
17.9
Polymorphism
197
17.10 Debugging
198
17.11 Glossary
199
17.12 Exercises
199
18
Inheritance
201
18.1
Card Objects
201
18.2
Class Attributes
202
18.3
Comparing Cards
204
18.4
Decks
205
18.5
Printing the Deck
205
18.6
Add, Remove, Shuffle, and Sort
206
18.7
Inheritance
207
18.8
Class Diagrams
209
18.9
Debugging
210
18.10 Glossary
211
18.11 Exercises
212
19
Case Study: Tkinter
214
19.1
GUI
214
19.2
Buttons and Callbacks
215
19.3
Canvas Widgets
216
19.4
Coordinate Sequences
217
19.5
More Widgets
218
19.6
Packing Widgets
220
19.7
Menus and Callables
223
19.8
Binding
223
19.9
Debugging
226
19.10 Glossary
227
19.11 Exercises
228