Chapter 1: Building Abstractions with Functions
Contents
2
1.1.1 Programming in Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.2 Installing Python 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.3 Interactive Sessions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.4 First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.5 Practical Guidance: Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2 The Elements of Programming
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.2 Call Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.3 Importing Library Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2.4 Names and the Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.5 Evaluating Nested Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2.6 Function Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.3.2 Calling User-Defined Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.3.3 Example: Calling a User-Defined Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.3.4 Local Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.3.5 Practical Guidance: Choosing Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.3.6 Functions as Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.3.7 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
1.4 Practical Guidance: The Art of the Function
18
1.4.1 Docstrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1.4.2 Default Argument Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
20
1.5.1 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
1.5.2 Compound Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
1.5.3 Defining Functions II: Local Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
1.5.4 Conditional Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
1.5.5 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
1.5.6 Practical Guidance: Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
25
1.6.1 Functions as Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
1.6.2 Functions as General Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
1.6.3 Defining Functions III: Nested Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
1.6.4 Functions as Returned Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
1.6.5 Lambda Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
1.6.6 Example: Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
1.6.7 Abstractions and First-Class Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
1
1.6.8 Function Decorators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
1.1 Introduction
Computer science is a tremendously broad academic discipline. The areas of globally distributed systems, artificial
intelligence, robotics, graphics, security, scientific computing, computer architecture, and dozens of emerging sub-
fields each expand with new techniques and discoveries every year. The rapid progress of computer science has
left few aspects of human life unaffected. Commerce, communication, science, art, leisure, and politics have all
been reinvented as computational domains.
The tremendous productivity of computer science is only possible because it is built upon an elegant and pow-
erful set of fundamental ideas. All computing begins with representing information, specifying logic to process it,
and designing abstractions that manage the complexity of that logic. Mastering these fundamentals will require us
to understand precisely how computers interpret computer programs and carry out computational processes.
These fundamental ideas have long been taught at Berkeley using the classic textbook Structure and Inter-
pretation of Computer Programs (SICP) by Harold Abelson and Gerald Jay Sussman with Julie Sussman. These lecture notes borrow heavily from that textbook, which the original authors have kindly licensed for adaptation
and reuse.
The embarkment of our intellectual journey requires no revision, nor should we expect that it ever will.
We are about to study the idea of a computational process. Computational processes are abstract
beings that inhabit computers. As they evolve, processes manipulate other abstract things called data.
The evolution of a process is directed by a pattern of rules called a program. People create programs
to direct processes. In effect, we conjure the spirits of the computer with our spells.
The programs we use to conjure processes are like a sorcerer’s spells. They are carefully composed
from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we
want our processes to perform.
A computational process, in a correctly working computer, executes programs precisely and accu-
rately. Thus, like the sorcerer’s apprentice, novice programmers must learn to understand and to
anticipate the consequences of their conjuring.
—Abelson and Sussman, SICP (1993)
1.1.1 Programming in Python
A language isn’t something you learn so much as something you join.
In order to define computational processes, we need a programming language; preferably one many humans
and a great variety of computers can all understand. In this course, we will learn the Python language.
Python is a widely used programming language that has recruited enthusiasts from many professions: web pro-
grammers, game engineers, scientists, academics, and even designers of new programming languages. When you
learn Python, you join a million-person-strong community of developers. Developer communities are tremen-
dously important institutions: members help each other solve problems, share their code and experiences, and
collectively develop software and tools. Dedicated members often achieve celebrity and widespread esteem for
their contributions. Perhaps someday you will be named among these elite Pythonistas.
The Python language itself is the product of a large volunteer community that prides itself on the diversity
of its contributors. The language was conceived and first implemented by Guido van Rossum in the late 1980’s.
The first chapter of his Python 3 Tutorial explains why Python is so popular, among the many languages available today.
Python excels as an instructional language because, throughout its history, Python’s developers have empha-
sized the human interpretability of Python code, reinforced by the Zen of Python guiding principles of beauty, simplicity, and readability. Python is particularly appropriate for this course because its broad set of features support a variety of different programming styles, which we will explore. While there is no single way to program in
Python, there are a set of conventions shared across the developer community that facilitate the process of reading,
2
understanding, and extending existing programs. Hence, Python’s combination of great flexibility and accessibil-
ity allows students to explore many programming paradigms, and then apply their newly acquired knowledge to
thousands of ongoing projects.
These notes maintain the spirit of SICP by introducing the features of Python in lock step with techniques for abstraction design and a rigorous model of computation. In addition, these notes provide a practical introduction
to Python programming, including some advanced language features and illustrative examples. Learning Python
will come naturally as you progress through the course.
However, Python is a rich language with many features and uses, and we consciously introduce them slowly
as we layer on fundamental computer science concepts. For experienced students who want to inhale all of the
details of the language quickly, we recommend reading Mark Pilgrim’s book Dive Into Python 3, which is freely available online. The topics in that book differ substantially from the topics of this course, but the book contains
very valuable practical information on using the Python language. Be forewarned: unlike these notes, Dive Into
Python 3 assumes substantial programming experience.
The best way to get started programming in Python is to interact with the interpreter directly. This section
describes how to install Python 3, initiate an interactive session with the interpreter, and start programming.
1.1.2 Installing Python 3
As with all great software, Python has many versions. This course will use the most recent stable version of
Python 3 (currently Python 3.2). Many computers have older versions of Python installed already, but those will
not suffice for this course. You should be able to use any computer for this course, but expect to install Python 3.
Don’t worry, Python is free.
Dive Into Python 3 has detailed installation instructions for all major platforms. These instructions mention Python 3.1 several times, but you’re better off with Python 3.2 (although the differences are insignificant for this
course). All instructional machines in the EECS department have Python 3.2 already installed.
1.1.3 Interactive Sessions
In an interactive Python session, you type some Python code after the prompt, >>>. The Python interpreter reads
and evaluates what you type, carrying out your various commands.
There are several ways to start an interactive session, and they differ in their properties. Try them all to find
out what you prefer. They all use exactly the same interpreter behind the scenes.
• The simplest and most common way is to run the Python 3 application. Type python3 at a terminal prompt
(Mac/Unix/Linux) or open the Python 3 application in Windows.
• A more user-friendly application for those learning the language is called Idle 3 (idle3). Idle colorizes
your code (called syntax highlighting), pops up usage hints, and marks the source of some errors. Idle is
always bundled with Python, so you have already installed it.
• The Emacs editor can run an interactive session inside one of its buffers. While slightly more challenging
to learn, Emacs is a powerful and versatile editor for any programming language. Read the 61A Emacs
Tutorial to get started. Many programmers who invest the time to learn Emacs never switch editors again.
In any case, if you see the Python prompt, >>>, then you have successfully started an interactive session.
These notes depict example interactions using the prompt, followed by some input.
>>> 2 + 2
4
Controls: Each session keeps a history of what you have typed. To access that history, press <Control>-P
(previous) and <Control>-N (next). <Control>-D exits a session, which discards this history.
1.1.4 First Example
And, as imagination bodies forth
The forms of things to unknown, and the poet’s pen
Turns them to shapes, and gives to airy nothing
3
A local habitation and a name.
—William Shakespeare, A Midsummer-Night’s Dream
To give Python the introduction it deserves, we will begin with an example that uses several language features.
In the next section, we will have to start from scratch and build up the language piece by piece. Think of this
section as a sneak preview of powerful features to come.
Python has built-in support for a wide range of common programming activities, like manipulating text, dis-
playing graphics, and communicating over the Internet. The import statement
>>> from urllib.request import urlopen
loads functionality for accessing data on the Internet. In particular, it makes available a function called
urlopen, which can access the content at a uniform resource locator (URL), which is a location of something
on the Internet.
Statements & Expressions. Python code consists of statements and expressions. Broadly, computer programs
consist of instructions to either
1. Compute some value
2. Carry out some action
Statements typically describe actions. When the Python interpreter executes a statement, it carries out the
corresponding action. On the other hand, expressions typically describe computations that yield values. When
Python evaluates an expression, it computes its value. This chapter introduces several types of statements and
expressions.
The assignment statement
>>> shakespeare = urlopen(’http://inst.eecs.berkeley.edu/~cs61a/fa11/shakespeare.txt’)
associates the name shakespeare with the value of the expression that follows. That expression applies the
urlopen function to a URL that contains the complete text of William Shakespeare’s 37 plays, all in a single
text document.
Functions. Functions encapsulate logic that manipulates data. A web address is a piece of data, and the text
of Shakespeare’s plays is another. The process by which the former leads to the latter may be complex, but we
can apply that process using only a simple expression because that complexity is tucked away within a function.
Functions are the primary topic of this chapter.
Another assignment statement
>>> words = set(shakespeare.read().decode().split())
associates the name words to the set of all unique words that appear in Shakespeare’s plays, all 33,721 of
them. The chain of commands to read, decode, and split, each operate on an intermediate computational
entity: data is read from the opened URL, that data is decoded into text, and that text is split into words. All of
those words are placed in a set.
Objects. A set is a type of object, one that supports set operations like computing intersections and testing
membership. An object seamlessly bundles together data and the logic that manipulates that data, in a way that
hides the complexity of both. Objects are the primary topic of Chapter 2.
The expression
>>> {w for w in words if len(w) >= 5 and w[::-1] in words}
{’madam’, ’stink’, ’leets’, ’rever’, ’drawer’, ’stops’, ’sessa’,
’repaid’, ’speed’, ’redder’, ’devil’, ’minim’, ’spots’, ’asses’,
’refer’, ’lived’, ’keels’, ’diaper’, ’sleek’, ’steel’, ’leper’,
’level’, ’deeps’, ’repel’, ’reward’, ’knits’}
is a compound expression that evaluates to the set of Shakespearian words that appear both forward and in
reverse. The cryptic notation w[::-1] enumerates each letter in a word, but the -1 says to step backwards
(:: here means that the positions of the first and last characters to enumerate are defaulted.) When you enter an
expression in an interactive session, Python prints its value on the following line, as shown.
4
Interpreters. Evaluating compound expressions requires a precise procedure that interprets code in a pre-
dictable way. A program that implements such a procedure, evaluating compound expressions and statements, is
called an interpreter. The design and implementation of interpreters is the primary topic of Chapter 3.
When compared with other computer programs, interpreters for programming languages are unique in their
generality. Python was not designed with Shakespeare or palindromes in mind. However, its great flexibility
allowed us to process a large amount of text with only a few lines of code.
In the end, we will find that all of these core concepts are closely related: functions are objects, objects are
functions, and interpreters are instances of both. However, developing a clear understanding of each of these
concepts and their role in organizing code is critical to mastering the art of programming.
1.1.5 Practical Guidance: Errors
Python is waiting for your command. You are encouraged to experiment with the language, even though you may
not yet know its full vocabulary and structure. However, be prepared for errors. While computers are tremendously
fast and flexible, they are also extremely rigid. The nature of computers is described in Stanford’s introductory
course as
The fundamental equation of computers is: computer = powerful + stupid
Computers are very powerful, looking at volumes of data very quickly. Computers can perform
billions of operations per second, where each operation is pretty simple.
Computers are also shockingly stupid and fragile. The operations that they can do are extremely rigid,
simple, and mechanical. The computer lacks anything like real insight .. it’s nothing like the HAL
9000 from the movies. If nothing else, you should not be intimidated by the computer as if it’s some
sort of brain. It’s very mechanical underneath it all.
Programming is about a person using their real insight to build something useful, constructed out of
these teeny, simple little operations that the computer can do.
—Francisco Cai and Nick Parlante, Stanford CS101
The rigidity of computers will immediately become apparent as you experiment with the Python interpreter:
even the smallest spelling and formatting changes will cause unexpected outputs and errors.
Learning to interpret errors and diagnose the cause of unexpected errors is called debugging. Some guiding
principles of debugging are:
1. Test incrementally: Every well-written program is composed of small, modular components that can
be tested individually. Test everything you write as soon as possible to catch errors early and gain
confidence in your components.
2. Isolate errors: An error in the output of a compound program, expression, or statement can typically
be attributed to a particular modular component. When trying to diagnose a problem, trace the error
to the smallest fragment of code you can before trying to correct it.
3. Check your assumptions: Interpreters do carry out your instructions to the letter --- no more and no
less. Their output is unexpected when the behavior of some code does not match what the programmer
believes (or assumes) that behavior to be. Know your assumptions, then focus your debugging effort
on verifying that your assumptions actually hold.
4. Consult others: You are not alone! If you don’t understand an error message, ask a friend, instructor,
or search engine. If you have isolated an error, but can’t figure out how to correct it, ask someone else
to take a look. A lot of valuable programming knowledge is shared in the context of team problem
solving.
Incremental testing, modular design, precise assumptions, and teamwork are themes that persist throughout
this course. Hopefully, they will also persist throughout your computer science career.
5
1.2 The Elements of Programming
A programming language is more than just a means for instructing a computer to perform tasks. The language also
serves as a framework within which we organize our ideas about processes. Programs serve to communicate those
ideas among the members of a programming community. Thus, programs must be written for people to read, and
only incidentally for machines to execute.
When we describe a language, we should pay particular attention to the means that the language provides
for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for
accomplishing this:
• primitive expressions and statements, which represent the simplest building blocks that the language
provides,
• means of combination, by which compound elements are built from simpler ones, and
• means of abstraction, by which compound elements can be named and manipulated as units.
In programming, we deal with two kinds of elements: functions and data. (Soon we will discover that they
are really not so distinct.) Informally, data is stuff that we want to manipulate, and functions describe the rules for
manipulating the data. Thus, any powerful programming language should be able to describe primitive data and
primitive functions and should have methods for combining and abstracting both functions and data.
1.2.1 Expressions
Having experimented with the full Python interpreter, we now must start anew, methodically developing the
Python language piece by piece. Be patient if the examples seem simplistic --- more exciting material is soon
to come.
We begin with primitive expressions. One kind of primitive expression is a number. More precisely, the
expression that you type consists of the numerals that represent the number in base 10.
>>> 42
42
Expressions representing numbers may be combined with mathematical operators to form a compound ex-
pression, which the interpreter will evaluate:
>>> -1 - -1
0
>>> 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128
0.9921875
These mathematical expressions use infix notation, where the operator (e.g., +, -, *, or /) appears in between
the operands (numbers). Python includes many ways to form compound expressions. Rather than attempt to
enumerate them all immediately, we will introduce new expression forms as we go, along with the language
features that they support.
1.2.2 Call Expressions
The most important kind of compound expression is a call expression, which applies a function to some arguments.
Recall from algebra that the mathematical notion of a function is a mapping from some input arguments to an
output value. For instance, the max function maps its inputs to a single output, which is the largest of the inputs.
A function in Python is more than just an input-output mapping; it describes a computational process. However,
the way in which Python expresses function application is the same as in mathematics.
>>> max(7.5, 9.5)
9.5
This call expression has subexpressions: the operator precedes parentheses, which enclose a comma-delimited
list of operands. The operator must be a function. The operands can be any values; in this case they are numbers.
6
When this call expression is evaluated, we say that the function max is cal