% LaTeX source for ``Think Python: How to Think Like a Computer Scientist''

% Copyright (c) 2008 Allen B. Downey.

% Permission is granted to copy, distribute and/or modify this

% document under the terms of the GNU Free Documentation License,

% Version 1.1 or any later version published by the Free Software

% Foundation; with no Invariant Sections, no Front-Cover Texts,

% and no Back-Cover Texts.

% This distribution includes a file named fdl.tex that contains the text

% of the GNU Free Documentation License. If it is missing, you can obtain

% it from www.gnu.org or by writing to the Free Software Foundation,

% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

%

%\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{pslatex}

\usepackage{url}

\usepackage{fancyhdr}

\usepackage{graphicx}

\usepackage{amsmath, amsthm, amssymb}

\usepackage{exercise} % texlive-latex-extra

\usepackage{makeidx}

\usepackage{setspace}

\usepackage{hevea}

\usepackage{upquote}

\title{Think Python}

\newcommand{\thetitle}{Think Python: How to Think Like a Computer Scientist}

\newcommand{\theversion}{1.1.22}

% 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

\begin{document}

\frontmatter

% LATEXONLY

\input{latexonly}

\newtheorem{ex}{Exercise}[chapter]

\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

\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

\vspace{1in}

{\Large

Allen Downey\\

}

\vspace{0.5in}

{\Large Green Tea Press}

{\small Needham, Massachusetts}

%\includegraphics[width=1in]{figs/logo1.eps}

\vfill

\end{flushright}

%--copyright--------------------------------------------------

\pagebreak

\thispagestyle{empty}

{\small

Copyright \copyright ~2008 Allen Downey.

Printing history:

\begin{description}

\item[April 2002:] First edition of {\em How to Think Like

a Computer Scientist}.

\item[August 2007:] Major revision, changed title to

{\em How to Think Like a (Python) Programmer}.

\item[June 2008:] Major revision, changed title to

{\em Think Python: How to Think Like

a Computer Scientist}.

\end{description}

\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 GNU Free Documentation License, Version 1.1 or

any later version published by the Free Software Foundation; with no

Invariant Sections, no Front-Cover Texts, and with no Back-Cover Texts.

The GNU Free Documentation License is available from {\tt www.gnu.org}

or by writing to the Free Software Foundation, Inc., 59 Temple Place,

Suite 330, Boston, MA 02111-1307, USA.

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

\setcounter{chapter}{-1}

\end{htmlonly}

\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.

Jeff and I revised the book, incorporated a case study by

Chris Meyers, and in 2001 we released {\em How to Think Like

a Computer Scientist: Learning with Python}, also under

the GNU Free Documentation License.

As Green Tea Press, I published the book and started selling

hard copies through Amazon.com and college book stores.

Other books from Green Tea Press are available at

\url{greenteapress.com}.

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.

Over the last five years I have continued to develop the book,

correcting errors, improving some of the examples and

adding material, especially exercises. In 2008 I started work

on a major revision---at the same time, I was

contacted by an editor at Cambridge University Press who

was interested in publishing the next edition. Good timing!

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 removed the material in the last few chapters about the

implementation of lists and trees. I still love those topics, but I

thought they were incongruent with the rest of the book.

\item I added more exercises, ranging from short tests of

understanding to a few substantial projects.

\item I added a series of case studies---longer examples with

exercises, solutions, and discussion. Some of them 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{thinkpython.com}.

\item I expanded the discussion of program development plans

and basic design patterns.

\item The use of Python is more idiomatic. The book is still about

programming, not Python, but now I think the book gets more leverage

from the language.

\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 an Associate Professor of Computer Science at

the Franklin W. Olin College of Engineering.

% \section*{For the teacher}

% Swampy and UML

% \section*{For the student}

% Try out examples.

% Do the in-chapter examples.

% Where to get the code.

\section*{Acknowledgements}

First and most importantly, I thank 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.

I also thank Chris Meyers, who contributed several sections

to {\em How to Think Like a Computer Scientist}.

And I thank the Free Software Foundation for developing

the GNU Free Documentation License, which helped make

my collaboration with Jeff and Chris possible.

\index{GNU Free Documentation License}

\index{Free Documentation License, GNU}

I also thank the editors at Lulu who worked on

{\em How to Think Like a Computer Scientist}.

I thank all the students who worked with earlier

versions of this book and all the contributors (listed

below) who sent in corrections and suggestions.

And I thank my wife, Lisa, for her work on this book, and Green

Tea Press, and everything else, too.

\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!

\small

\begin{itemize}

\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.0.

\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!

% 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 execute 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.

\beforefig

\centerline{\includegraphics[height=0.77in]{figs/interpret.eps}}

\afterfig

\index{source code}

\index{object code}

\index{executable}

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.

\beforefig

\centerline{\includegraphics[height=0.77in]{figs/compile.eps}}

\afterfig

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 prints

the result:

\index{interactive mode}

\index{script mode}

\beforeverb

\begin{verbatim}

>>> 1 + 1

2

\end{verbatim}

\afterverb

%

The chevron, {\tt >>>}, 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. In a UNIX command window, you would 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{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 sequence of statements.

\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. \index{syntax}

For example, parentheses have to come in matching pairs, so

{\tt (1 + 2)} is legal, but {\tt 8)} is a {\bf syntax error}.

\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}

\index{runtime error}

\index{error!runtime}

\index{exception}

\index{safe language}

\index{language!safe}

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.

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}

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 start with a

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.''

({\em The Linux Users' Guide} Beta Version 1).

\index{Linux}

Later chapters will 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 people speak,