Data is all around us and the amount of data stored increases every single day. In today’s world, decisions must be data-driven and so it is imperative that we be able to process, analyze, and understand the data we collect. Other important factors include the security and privacy of data. Businesses and governments need to answer important questions such as “Where should this data be stored?”; “How should this data be stored?”; and even, “Should this data be stored at all?”. The answers to these questions for Health Canada and personal health data is very different from the answers Nintendo might come up with for the next Animal Crossing game.

We begin our study of computer science by developing definitions for different categories of data. A data type is a way of categorizing data. A description of a data type conveys two important pieces of information:

1. The allowed values for a piece of data.
2. The allowed operations we can perform on a piece of data.

For example, we could say that a person’s age is a natural number, which would tell us that values like 25 and 100 would be expected, while an age of -2 or “David” would be nonsensical. Knowing that a person’s age is a natural number also tells us what operations we could perform (e.g., “add 1 to the age”), and rules out other operations (e.g., “sort these ages alphabetically”).

In this section, we’ll review the common data types that we’ll make great use of in this course: numeric data, boolean data, textual data, and various forms of collections of data. Many terms and definitions may be review from your past studies, but be careful—they may differ slightly from what you’ve learned before, and it will be important to get these definitions exactly right.

Numeric data

Here are some types of numeric data, represented as familiar sets of numbers.

• A natural number is a value from the set \(\{0, 1, 2, \dots \}\). We use the symbol \(\N\) to denote the set of natural numbers. Note that our convention in computer science is to consider 0 a natural number!
• An integer is a value from the set \(\{\dots, -2, -1, 0, 1, 2, \dots \}.\) We use the symbol \(\Z\) to denote the set of integers.
• A rational number is a value from the set \(\{\frac{p}{q} \mid p, q \in \Z \text{ and } q \neq 0\}\)—that is, the set of possible fractions. We use the symbol \(\Q\) to denote the set of rational numbers.
• An irrational number is a number with a infinite and non-repeating decimal expansion. Examples are \(\pi\), \(e\), and \(\sqrt 2\). We use the symbol \(\overline{\Q}\) to denote the set of irrational numbers.
• A real number is either a rational or irrational number. We use the symbol \(\R\) to denote the set of real numbers.

Operations on numeric data

All numeric data types support the standard arithmetic operations (addition, subtraction, multiplication, division, and exponentiation), as well as the standard comparisons for equality (using \(=\)) and inequality (\(<\), \(\leq\), \(>\), \(\geq\)). And of course, you are familiar with many more numeric functions, like log and sin; these will come up throughout the course.

One additional arithmetic operation that may be less familiar to you is the modulo operator, which produces the remainder when one integer is divided by another. We’ll use the percent symbol \(\%\) to denote the modulo operator, writing \(a \% b\) to mean “the remainder when \(a\) is divided by \(b\)”. For example, \(10 \% 4 = 2\) and \(30 \% 3 = 0\).

Some arithmetic operations are undefined for particular numbers; for example, we can’t divide by zero, and we can’t take the square root of a negative number.

Boolean data

A boolean is a value from the set \(\{\text{True}, \text{False}\}\). Think of a boolean value as an answer to a Yes/No question, e.g. “Is this person old enough to vote?”, “Is this country land-locked?”, and “Is this service free?”.

Operations on boolean data

Booleans can be combined using logical operators. The three most common ones are:

• not: reverses the value of a boolean. “not True” is False, and “not False” is True.
• and: takes two boolean values and produces True when both of the values are True, and False otherwise. For example, “True and False” is False, while “True and True” is True.
• or: takes two boolean values and produces True when at least one of the values is True, and False otherwise. For example, “True or False” is True, while “False or False” is False.

Next week, we’ll discuss these logical operators in more detail and introduce a few others.

Textual data

A string is an ordered sequence of characters, and is used to represent text. A character can be more than just an English letter (\(a\), \(b\), \(c\), etc.): number digits, punctuation marks, spaces, glyphs from non-English alphabets, and even emojis are all considered characters, and can be part of strings. Examples include a person’s name, your chat log, and the script of Shakespeare’s Romeo and Juliet.

Writing textual data

We typically will surround strings with single-quotes to differentiate them from any surrounding text, e.g., ‘David’. We can also use double-quotes (“David”) to surround a string, but in this course we will generally prefer single-quotes for a reason we’ll discuss in Section 1.3.

A string can have zero characters; this string is called the empty string, and is denoted by `’ or the symbol \(\epsilon\).

Operations on textual data

Here are some common operations on strings. \(s\), \(s_1\), and \(s_2\) are all variables representing strings.

• \(|s|\): string length/size. Returns the the number of characters in \(s\).

• \(s_1 = s_2\): string equality. Returns whether \(s_1\) and \(s_2\) have the same characters, in the same order.

• \(s + t\): string concatenation. Returns a new string consisting of the characters of \(s\) followed by the characters of \(t\). For example, if \(s_1\) represents the string ‘Hello’ and \(s_2\) represents the string ‘Goodbye’, then \(s_1 + s_2\) is the string ‘HelloGoodbye’.

• \(s[i]\): string indexing. Returns the \(i\)-th character of \(s\), where indexing starts at 0. (So \(s[0]\) returns the first character of \(s\), \(s[1]\) returns the second, etc.) For example, if \(s\) represents the string ‘Hello’, then \(s[0]\) is ‘H’ and \(s[4]\) is ‘o’.

Set data (unordered distinct values)

A set is an unordered collection of zero or more distinct values, called its elements. Examples include: the set of all people in Toronto; the set of words of the English language; and the set of all countries on Earth.

Writing sets

We write sets using curly braces in two different ways:

1. Writing each element of the set within the braces, separated by commas. For example, \(\{1, 2, 3\}\) or \(\{\text{‘hi'}, \text{‘bye'}\}\).
2. Using set builder notation, in which we define the form of elements of a set using variables. We saw an example of this earlier when defining the set of rational numbers, \(\{\frac{p}{q} \mid p, q \in \Z \text{ and } q \neq 0\}\).

A set can have zero elements; this set is called the empty set, and is denoted by \(\{\}\) or the symbol \(\emptyset\).

Operations on set data

Here are some common set operations.\(A\) and \(B\) represent sets.

• \(|A|\): returns the size of set \(A\), i.e., the number of elements in \(A\).

• \(x \in A\): returns True when \(x\) is an element of \(A\); \(y \notin A\) returns True when \(y\) is not an element of \(A\).

• \(A \subseteq B\): returns True when every element of \(A\) is also in \(B\). We say in this case that \(A\) is a subset of \(B\).

  A set \(A\) is a subset of itself, and the empty set is a subset of every set: \(A \subseteq A\) and \(\emptyset \subseteq A\) are always True.

• \(A = B\): returns True when \(A\) and \(B\) contain the exact same elements.

The following operations return sets:

• \(A \cup B\), the union of \(A\) and \(B\). Returns the set consisting of all elements that occur in \(A\), in \(B\), or in both.

  Using set builder notation: \(A \cup B = \{x \mid x \in A \text{ or } x \in B\}\).

• \(A \cap B\), the intersection of \(A\) and \(B\). Returns the set consisting of all elements that occur in both \(A\) and \(B\).

  Using set builder notation: \(A \cap B = \{x \mid x \in A \text{ and } x \in B\}\).

• \(A \setminus B\), the difference of \(A\) and \(B\). Returns the set consisting of all elements that are in \(A\) but that are not in \(B\).

  Using set builder notation: \(A \setminus B = \{x \mid x \in A \text{ and } x \notin B\}.\)

• \(A \times B\), the (Cartesian) product of \(A\) and \(B\). Returns the set consisting of all pairs \((a, b)\) where \(a\) is an element of \(A\) and \(b\) is an element of \(B\).

  Using set builder notation: \(A \times B = \{(x, y) \mid x \in A \text{ and } y \in B\}.\)

• \(\cP(A)\), the power set of \(A\), returns the set consisting of all subsets of \(A\).Food for thought: what is the relationship between \(|A|\) and \(|\cP(A)|\)? For example, if \(A = \{1,2,3\}\), then \[\cP(A) = \big\{ \emptyset, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}.\]

  Using set builder notation: \(\cP(A) = \{S \mid S \subseteq A\}\).

List data (ordered values)

A list is an ordered collection of zero or more (possibly duplicated) values, called its elements. List data is used instead of a set when the elements of the collection should be in a specified order, or if it may contain duplicates. Examples include: the list of all people in Toronto, ordered by age; the list of words of the English language, ordered alphabetically, and the list of names of students at U of T (two students may have the same name!), ordered alphabetically.

Writing lists

Lists are written with square brackets enclosing zero or more values separated by commas. For example, \([1, 2, 3]\).

A list can have zero elements; this list is called the empty list, and is denoted by \([]\).

Operations on list data

Here are some common list operations.\(A\) and \(B\) represent lists.

• \(|A|\): returns the size of \(A\), i.e., the number of elements in \(A\) (counting all duplicates).

• \(x \in A\): same meaning as for sets.

• \(A = B\): \(A\) and \(B\) have the same elements in the same order.

• \(A[i]\): list indexing. Returns the \(i\)-th element of \(A\), where the indexing starts at 0. So \(A[0]\) returns the first element of \(A\), \(A[1]\) returns the second, etc.

• \(A + B\): list concatenation. Returns a new list consisting of the elements of \(A\) followed by the elements of \(B\). This is similar to set union, but duplicates are kept, and order is preserved.

  For example, \([1, 2, 3] + [2, 4, 6] = [1, 2, 3, 2, 4, 6]\).

Mapping data

Finally, a mapping is an unordered collection of pairs of values. Each pair consists of a key and an associated value; the keys must be unique in the mapping, but the values can be duplicated. A key cannot exist in the mapping without a corresponding value.

Mappings are used to represent associations between two collections of data. For example: a mapping from the name of a country to its GDP; a mapping from student number to name; and a mapping from food item to price.

Writing mappings

We use curly braces to represent a mapping. This is similar to sets, because mappings are quite similar to sets. Both data types are unordered, and both have a uniqueness constraint (a set’s elements are unique; a mapping’s keys are unique). Each key-value pair in a mapping is written using a colon, with the key on the left side of the colon and its associated value on the right. For example, here is how we could write a mapping representing the menu items of a restaurant: \[\{\text{`fries'}: 5.99, \text{`steak'}: 25.99, \text{`soup'}: 8.99\}.\]

Operations on mappings

Here are some common set operations.\(M\) and \(N\) represent mappings.

• \(|M|\): returns the size of the mapping \(M\), i.e., the number of key-value pairs in \(M\).
• \(M = N\): returns whether two mappings are equal, i.e., when they contain exactly the same key-value pairs.
• \(k \in M\): returns whether \(k\) is a key contained in the mapping \(M\).
• \(M[k]\): when \(k\) is a key in \(M\), this operation returns the value that corresponds to \(k\) in the mapping \(M\).

…and more!

The data types we’ve studied so far are not the only kinds of data that we encounter in the real world, but they do form a basis for representing all kinds of more complex data. We’ll study how to represent more complex forms of data later in this course, but here’s one teaser: representing image data.

Images can be represented as a list of integers. Each element in the list corresponds to a very tiny dot on your screen—a pixel. For each dot, three integer values are used to represent three colour channels: red, green, and blue. We can then add these channels together to get a very wide range of colours (this is called the RGB colour model). Somehow, our computers are able to take these sequences of integers and translate them into a sequence of visible lights and if these lights are arranged in a particular way, well, a cat appears!

References

1. Check out Our World in Data to see how data-driven research is being used to tackle global problems.
2. If you’d like to read more about the RGB colour model, the Wikipedia entry is a good start: https://en.wikipedia.org/wiki/RGB_color_model.

For the thousands of years of human history before the mid-twentieth century, humans collected, analysed, and created data by hand. Digital computers were a revolution not just in technology but in civilization because of their ability to store more data than could fit on all the sheets of paper in the world, and to perform computations on this data faster and more reliably than an army of humans. Today, we rely on complex computer programs to operate on data in a variety of ways, from sending messages back and forth with loved ones, organizing data in documents and media, to running simulations of physical, social, and biological systems.

Yet for all their computation power, computers have one fundamental limitation: they have no agency, no inherent ability to make decisions about what to do. All they can do is take a set of (possibly very complex!) instructions, what we call a computer program, and execute them—no more, and no less. And so if we, as computer scientists, want to harness the awesome power of computers, we need to learn how give these instructions in a way that a computer understands. We need to learn how to speak to a computer.

What is a programming language?

A programming language is a way of communicating a set of instructions to a computer. Like human languages such as English, a programming language consists of a set of allowed words and the rules for putting those words together to form phrases with a coherent meaning. In your past learning of a (human) language, you’ve likely referred to these rules as the grammar of a language. Unlike human languages, a programming language must be precise enough to be understood by a computer, and so operates with a relatively small set of words and very structured rules for putting them together. Learning a programming language can be frustrating at first, because even a slight deviation from these rules results in the computer being unable to comprehend what we’ve written. But our time and efforts spent mastering the rules of a programming language yield a wonderful reward: the computer will not just understand what we’re saying, but faithfully execute them.

A program is simply the text of the instructions we wish to instruct the computer to execute; we call this text program code to differentiate it from other forms of text. To write programs in a particular language, we need to understand two key properties of the language. The first is the syntax of a programming language, which is the name we give to the rules governing what constitutes a valid program in the language. Before a computer can execute a program, it must read the instructions for the program; the syntax of the programming language specifies the format of these instructions. The second concept is the semantics of a programming language, which refers to the rules governing the meaning of different instructions in the language. Once the computer has read the instructions in a program, it begins executing them. The language semantics specifies what the computer should do for each instruction.

The Python programming language

Just as there are thousands of human languages in the world today, each with their own vocabulary, grammar, and stylistic conventions, so too is there a plethora of programming languages that we can choose from. In this course, we’ll use the Python programming language, which offers a simple, beginner-friendly syntax and a set of language instructions whose semantics are both powerful and accessible.

Now, neither our computer hardware nor operating system understand the Python programming language. Instead, the creators of the Python language developed a program called the Python interpreter, whose job is to take programs written in the Python language and execute the instructions. So when you “download Python”, what you’re actually downloading and installing is this Python interpreter software. You can think of the Python interpreter as a mediator between you the programmer, writing communicating in Python, and the computer hardware that actually executes instructions.

There are two ways of writing code in the Python language to be understood by the interpreter. The first is to write full programs in the Python language, saving them as text files, Python programs use the .py file extension to distinguish them from other text files. and then running them through the Python interpreter. This is the standard way of writing programs: write the instructions, and then run them with the interpreter. The second way is to run the Python interpreter in an interactive mode, which we call the Python console or Python shell. In this mode, we can write small fragments of Python code and ask the Python interpreter to execute each fragment one at a time. The Python console is useful for experimenting and exploring the language, as you get feedback after every single instruction. The drawback is that interactions with the interpreter in the Python console are ephemeral, lost every time you restart the console. So we’ll use the following approach through the course: use the Python console to learn about and experiment with the Python language, and write full programs in .py files.

Data is all around us, but so are computers. If decisions must be data-driven then computers are an excellent tool for processing that data. Especially when we consider that computers are several orders of magnitude faster at computing data than a human. The problem is that computers need to be told exactly how to process the data, and we can do so using one of several programming languages. In this section, we see how data types are represented in Python and how we can use Python to perform operations for us. We’ll learn about some subtle, but crucial, differences between our theoretical definitions of data types from Section 1.1 and what Python can actually represent. But first, we’ll introduce some general terminology for using the interactive Python console.

The Python console

When we first start the Python console, we see the following:

>>>

The text >>> is called the Python prompt: the console is “prompting” us to type in some Python code to execute. If we type in a simple arithmetic expression,

>>> 4 + 5

and press Enter, we see the following output:

>>> 4 + 5
9

The interpreter took our bit of code, 4 + 5, and calculated its value, 9. A piece of Python code that produces a value is called an expression, and the act of calculating the value of an expression is called evaluating the expression.

The expression 4 + 5 looks simple enough, but technically it is formed from two smaller expressions—the numbers 4 and 5 themselves. We can ask Python to evaluate each of these, though the result is not very interesting.

>>> 4
4
>>> 5
5

A Python literal is the simplest kind of Python expression: it is a piece of code that represents the exact value as written. For example, 4 is an integer literal representing the number 4.

To sum up,The pun was not originally intended, but we are pointing it out… the expression 4 + 5 consists of two smaller expressions, the literals 4 and 5, joined together with the arithmetic operator +, representing addition. We’ll devote the rest of this section to exploring the different kinds of data types we can use in Python: both how to write their literals, and what operations we can perform on them.

Numeric data in Python (int, float)

Python has two data types for representing numeric data: int and float. Let’s start with int, which stands for “integer”, and is the data type that Python uses to represent integers.

An int literal is simply the number as a sequence of digits with an optional - sign, like 110 or -3421.

Python supports all of the arithmetic operations we discussed in Section 1.1. Here are some examples; try typing them into the Python console yourself to follow along!

>>> 2 + 3
5
>>> 2 - 5
-3
>>> -2 * 10
-20
>>> 2 ** 5  # This is "2 to the power of 5"
32

In the last prompt, we included some additional text—# This is "2 to the power of 5". In Python, we use the character # in code to begin a comment, which is code that is ignored by the Python interpreter. Comments are only meant for humans to read, and are a useful way of providing additional information about some Python code. We used it above to explain the meaning of the ** operator in our demo.

Python supports the standard precedence rules for arithmetic operations,sometimes referred to as “BEDMAS” or “PEMDAS” performing exponentiation before multiplication, and multiplication before addition and subtraction:

>>> 1 + 2 ** 3 * 5  # Equal to "1 plus ((2 to the power of 3) times 5)"
41

Just like in mathematics, long expressions like this one can be hard to read. So Python also allows you to use parentheses to group expressions together:

>>> 1 + ((2 ** 3) * 5)  # Equivalent to the previous expression
41
>>> (1 + 2) ** (3 * 5)  # Different grouping: "(1 plus 2) to the power of (3 times 5)"
14348907

When we add, subtract, multiply, and use exponentiation on two integers, the result is always an integer, and so Python always produces an int value for these operations. But dividing two integers certainly doesn’t always produce an integer—what does Python do in this case? It turns out that Python has two different forms of division. The first is the operator //, and is called floor division (or sometimes integer division). For two integers x and y, the result of x // y is equal to the quotient \(\frac{\texttt{x}}{\texttt{y}}\), rounded down to the nearest integer. Here are some examples:

>>> 6 // 2
3
>>> 15 // 2  # 15 ÷ 2 = 7.5, and // rounds down
7
>>> -15 // 2  # Careful! -15 ÷ 2 = -7.5, which rounds down to -8
-8

But what about “real” division? This is done using the division operator /:

>>> 5 / 2
2.5

This returns 2.5, which is a value of Python’s float type, which Python uses to represent arbitrary real numbers. A float literal is written as a sequence of digits followed by a decimal point (.) and then another sequence of digits. 2.5, .123, and 1000.00000001 are all examples of float literals.

All of the arithemtic operations we’ve looked at so far work with float values too:

>>> 3.5 + 2.4
5.9
>>> 3.5 - 20.9
-17.4
>>> 3.5 * 2.5
8.75
>>> 3.5 / 2.5
1.4
>>> 2 ** 0.5
1.4142135623730951

The last expression, 2 ** 0.5, calculates the square root of 2. However, this actually poses a problem for Python: since \(\sqrt 2\) is an irrational number, its decimal expansion is infinite, and so it cannot be represented in any finite amount of computer memory. More precisely, computers use a binary system where all data, including numbers, are represented as a sequence of 0s and 1s. This sequence of 0s and 1s is finite since computer memory is finite, and so cannot exactly represent \(\sqrt 2\). We will discuss this binary representation of numbers later this year.

] The float value that’s produced, 1.4142135623730951, is an approximation of \(\sqrt 2\), but is not equal to it. Let’s see what happens if we try to square it:

>>> 1.4142135623730951 * 1.4142135623730951
2.0000000000000004

This illustrates a fundamental limitation of float: this data type is used to represent real numbers, but cannot always represent them exactly. Rather, a float value approximates the value of the real number; sometimes that approximation is exact, like 2.5, but most of the time it isn’t.

3 vs. 3.0

Here’s an oddity:

>>> 6 // 2
3
>>> 6 / 2
3.0

Even though \(\frac{6}{2}\) is mathematically an integer, the results of the division using // and / are subtly different in Python. When x and y are ints, x // y always evaluates to an int, and x / y always evaluates to a float, even if the value of \(\frac{\texttt{x}}{\texttt{y}}\) is an integer! So 6 // 2 has value 3, but 6 / 2 has value 3.0. These two values represent the same mathematical quantity—the number 3—but are stored as different data types in Python, something we’ll explore more later in this course when we study how ints and floats actually work in Python.

Mixing ints and floats

So to summarize: for two ints x and y, x + y, x - y, x * y, x // y, and x ** y all produce ints, and x / y always produces a float. For two floats, it’s even simpler: all six of these arithmetic operations produce a float.Even //. Try it!

But what happens when we mix these two types? An arithmetic operation that is given one int and one float always produces a float. You can think of a float as a parasite—even in long arithmetic expressions where only one value is a float, the whole expression will evaluate to a float.

>>> 12 - 4 * 5 // (3.0 ** 2) + 100
110.0

Comparison operators

Finally, the numeric comparison operators are represented in Python as follows:

Here are a few examples:

>>> 4 == 4
True
>>> 4 != 6
True
>>> 4 < 2
False
>>> 4 >= 1
True

And returning to our discussion earlier, we can see that even though ints and floats are different types, Python can recognize when their values represent the exact same number:

>>> 4 == 4.0
True

In these examples, we’ve seen the values True and False produced as a result of these comparison expressions. You can probably tell exactly what they mean, but let’s take a moment to introduce them formally.

Boolean data in Python (bool)

In Python, boolean data is represented using the data type bool. Unlike the broad range of numbers we just saw, there are only two literal values of type bool: True and False.

There are three boolean operators we can perform on boolean values: not, and, and or.

>>> not True
False
>>> True and True
True
>>> True and False
False
>>> False or True
True
>>> False or False
False

One note about the or operator in Python is that it is the inclusive or, meaning it produces True when both of its operand expressions are True.

>>> True or True
True

Just as we saw how arithmetic operator expressions can be nested within each other, we can combine boolean operator expressions, and even the arithmetic comparison operators:

>>> True and (False or True)
True
>>> (3 == 4) or (5 > 10)
False

Textual data in Python (str)

All Python code is text that we type into the computer, so how do we distinguish between text that’s code and text that’s data, like a person’s name? Python uses the str (short for “string”) data type to represent textual data. A str literal is a sequence of characters surrounded by single-quotes ('). Python allows string literals to be written using either single-quotes or double-qutoes ("). We’ll tend to use single-quotes in this course to match how Python displays strings, as we’ll see in this section. For example, we could write this course’s name in Python as the string literal 'Foundations of Computer Science I'.

Now let’s see what kinds of operations we can perform on strings. First, we can compare strings using ==, just like we can for ints and floats:

>>> 'David' == 'David'
True
>>> 'David' == 'david'  # String comparisons are case-sensitive
False

Python supports string indexing to extract a single character from a string. Remember, string indexing starts at 0. s[0] represents the first character in the string s.

>>> 'David'[0]
'D'
>>> 'David'[3]
'i'

And Python supports concatenation using the familiar + operator:

>>> 'One string' + 'to rule them all.'
'One stringto rule them all.'
>>> 'One string ' + 'to rule them all.'  # Note the extra space!
'One string to rule them all.'

One operation that we did not cover in Section 1.1 is a fun quirk of Python: string repetition.

>>> 'David' * 3
'DavidDavidDavid'

And of course, all of these string operation expressions can be nested within each other:

>>> ('David' + 'Mario') * 3
'DavidMarioDavidMarioDavidMario'

Set data in Python (set)

Python uses the set data type to store set data. A set literal matches the notation we use in mathematics: the literal begins with a { and ends with a }, and each element of the list is written inside the braces, separated from each other by commas. For example, {1, 2, 3} is a set of ints, and {1, 2.0, 'three'} is a set of elements of mixed types.

Like other data types, sets can be compared for equality using ==. Remember that element order does not matter when comparing sets!

>>> {1, 2, 3} == {3, 1, 2}
True

Python also supports the “element of” (\(\in\)) set operation using the in operator.

>>> 1 in {1, 2, 3}
True
>>> 10 in {1, 2, 3}
False

Python also allows not and in to be combined to form an operator that corresponds to the set operation \(\notin\):

>>> 1 not in {1, 2, 3}
False
>>> 10 not in {1, 2, 3}
True

We’ll see in the next chapter how other set operations such as union and intersection are supported in Python.

List data in Python (list, tuple)

Python uses two different data types to store list data: list and tuple. list literals are written the same way as set literals, except using square brackets instead of curly braces. Lists support the same operations we saw for strings and sets earlier:

>>> [1, 2, 3] == [1, 2, 3]                          # List equality comparison; order matters!
True
>>> [1, 2, 3] == [3, 2, 1]
False
>>> (['David', 'Mario', 'Jacqueline', 'Diane'])[0]  # List indexing
'David'
>>> ['David', 'Mario'] + ['Jacqueline', 'Diane']    # List concatenation
['David', 'Mario', 'Jacqueline', 'Diane']
>>> 1 in [1, 2, 3]                                  # List "element of" operation
True

tuple literals are written using regular parentheses instead, but otherwise support the above operations as well.

>>> (1, 2, 3) == (1, 2, 3)                        # Tuple equality comparison
True
>>> (1, 2, 3) == (3, 2, 1)
False
>>> ('David', 'Mario', 'Jacqueline', 'Diane')[0]  # Tuple indexing
'David'
>>> ('David', 'Mario') + ('Jacqueline', 'Diane')  # Tuple concatenation
('David', 'Mario', 'Jacqueline', 'Diane')
>>> 1 in (1, 2, 3)                                # Tuple "element of" operation
True

So why does Python have two different data types that represent the same kind of data? There is an important technical distinction between list and tuple that we’ll learn about later in this course, but for now we’ll generally stick with list.

Mapping data in Python (dict)

Python stores mapping data using a data type called dict, short for “dictionary”. dict literals are written similarly to sets, with each key-value pair separated by a colon. For example, we can represent the mapping from the previous section with the dictionary literal {'fries': 5.99, 'steak': 25.99, 'soup': 8.99}. In this dictionary, the keys are strings, and the values are floats.

But if both sets and dictionaries use curly braces, then does the literal {} represent an empty set or an empty dictionary? The answer (for historical reasons) is an empty dictionary—Python has no literal to represent an empty set. Instead, we represent an empty set with set(), which is syntax we haven’t yet seen and will explore later.

Dictionaries also support equality comparison using ==. They support key lookup using the same syntax as string and list indexing:

>>> ({'fries': 5.99, 'steak': 25.99, 'soup': 8.99})['fries']
5.99

And finally, they support checking whether a key is present in a dictionary using the in operator:

>>> 'fries' in  {'fries': 5.99, 'steak': 25.99, 'soup': 8.99}
True

References

• CSC108 videos: Python as a Calculator (Part 1, Part 2, Part 3)
• CSC108 videos: Type bool (Part 1, Part 2, Part 3, Part 4)
• CSC108 videos: Type str (Part 1, Part 2)
• Appendix A.2 Python Built-In Data Types Reference

So far, we’ve been writing expressions in the Python console using only literals and operators. But as the computations we want to perform get more complex, relying on just literals and operators is very cumbersome. We can write very complex nested expressions, but this makes our code very hard to understand.

For example, suppose we’re given three points in the Cartesian plane \((1, 3)\), \((2, 5)\), \((10, -1)\) that form a path, and we want to find the length of this path.

We’d like to use this formula for the distance \(d\) between two points \((x_1, y_1)\) and \((x_2, y_2)\):

\[ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}. \]

We could write this as a single arithmetic expression and have Python evaluate it:

>>> ((1 - 2) ** 2 + (3 - 5) ** 2) ** 0.5 + ((2 - 10) ** 2 + (5 + 1) ** 2) ** 0.5
12.23606797749979

But typing in this expression is quite error-prone, and hard to understand. Just like in mathematics, we can improve our code by breaking down this problem into intermediate steps. Python (like all other programming languages) gives us a ways to bind values to names, so that we can refer to those values later on in subsequent calculations.

Variables

A variable is a piece of code that is a name that refers to a value. We create variables in Python using the syntax:

<variable> = <expression>

which is a form of Python code called an assignment statement. You might wonder why we use the term “statement” rather than “expression” for assignment. An expression is a piece of Python code that is evaluated to produce a value. When we execute an assignment statement, it doesn’t produce a value—it instead defines a variable.

Python executes an assignment statement in two steps:

1. First, the expression on the right-hand side of the = is evaluated, producing a value.
2. Second, that value is bound to the variable on the left-hand side.

After the assignment statement is executed, the variable may be used to refer to the value. Here’s how we can use variables to simplify the calculation above:

>>> distance1 = ((1 - 2) ** 2 + (3 - 5) ** 2) ** 0.5   # Distance between (1, 3) and (2, 5)
>>> distance2 = ((2 - 10) ** 2 + (5 + 1) ** 2) ** 0.5  # Distance between (2, 5) and (10, -1)
>>> distance1  # A variable is an expression; evaluating it produces the value it refers to
2.23606797749979
>>> distance2
10.0
>>> distance1 + distance2  # The total distance
12.23606797749979

Choosing good variable names

Because variables are used to store intermediate values in computations, it is important to choose good variable names so that you can remember what the purpose of each variable is. This might not seem that important in our above example because there were only two variables, but as you start writing larger programs, you’ll have to grapple with dozens, if not hundreds, of variables, and choosing good names will be paramount.

For now, we’ll introduce a few simple rules that you should follow when choosing variable names:

1. All variable names should use only lowercase letters, digits, and underscores. So distance1, not Distance1.

2. When a variable name consists of multiple words, write each word in lowercase and separate them with an underscore. You aren’t allowed to use spaces in variable names. For example, we might create a variable to refer to the total distance by doing

   >>> total_distance = distance1 + distance2

   We use the name total_distance rather than totaldistance or totalDistance (the latter is a naming style used in other programming languages, but not here).

3. Avoid single-letter variable names and non-standard acronyms/abbreviations, outside of some mathematical contexts.

   For example, we might have used d1 and d2 instead of distance1 and distance2 because d is the variable we used for distance in our above formula. However, we should not use td instead of total_distance, because a second person wouldn’t immediately understand what td stands for.

The value-based Python memory model

As our programs get larger, it is useful to have a principled way to keep track of the variables and data used by the programs. A memory model is a structured way of representing variables and data in a program. The term “memory” here refers to the computer memory used to actually store the data. For the next few weeks, we’re going to use the value-based Python memory model, which simply uses a table to represent the associations between variables and their associated values. For example, the value-based memory model for our above example is the following:

References

• CSC108 videos: Variable Assignment (Part 1, Part 2, Part 3)
• CSC108 videos: Assignment Statement Visualizer (Part 1)

To wrap up our introduction to data in Python, we’re going to learn about one last kind of expression that allows to build up and transform large collections of data in Python.

From set builder notation to set comprehensions

Recall set builder notation, which is a concise way of defining a mathematical set by specifying the values of the elements in terms of a larger domain. For example, suppose we have a set \(S = \{1, 2, 3, 4, 5\}\). We can express a set of squares of the elements of \(S\): \[\{ x^2 \mid x \in S \}.\]

It turns out that this notation translates naturally to Python! To start, let’s go into the Python Console and create a variable that refers to a set of numbers:

>>> numbers = {1, 2, 3, 4, 5}

Now, we introduce a new kind of expression called a set comprehension, which has the following syntax: Careful with this: even though set comprehensions also use curly braces, they are not the same as set literals. We aren’t writing out the individual elements separated by commas.

{ <expr> for <variable> in <collection> }

Evaluating a set comprehension is done by taking the <expr> and evaluating it once for each value in <collection> assigned to the <variable>. This is exactly analogous to set builder notation, except using for instead of \(|\) and in instead of \(\in\). Here’s how we can repeat our initial example in Python using a set comprehension:

>>> {x ** 2 for x in numbers}
{1, 4, 9, 16, 25}

Pretty cool, eh? If you aren’t sure exactly what happened here, it’s useful to write out the expanded form of the set comprehension:

   {x ** 2 for x in numbers}
== {1 ** 2, 2 ** 2, 3 ** 2, 4 ** 2, 5 ** 2}  # Replacing x with 1, 2, 3, 4, and 5.

It goes even further—we can use set comprehensions with a Python list as well.

>>> {x ** 2 for x in [1, 2, 3, 4, 5]}
{1, 4, 9, 16, 25}

In fact, as we’ll see later in this course, set comprehensions can be used with any “collection” data type in Python, not just sets and lists.

List and dictionary comprehensions

Even though set comprehensions draw their inspiration from set builder notation in mathematics, Python has extended them to other data types.

A list comprehension is very similar to a set comprehension, except its syntax uses square brackets instead of curly braces:

[ <expr> for <variable> in <collection> ]

Once again, <collection> can be a set or a list:

>>> [x + 4 for x in {10, 20, 30}]
[14, 24, 34]
>>> [x * 3 for x in [100, 200, 300]]
[300, 600, 900]

One word of warning: because sets are unordered but lists are ordered, you should not assume a particular ordering of the elements when a list comprehension generates elements from a set—the results can be unexpected!

>>> [x for x in {20, 10, 30}]
[10, 20, 30]

A dictionary comprehension is again similar to a set comprehension, but specifies both an expression to generate keys and an expression to generate their associated values:

{ <key_expr> : <value_expr> for <variable> in <collection> }

Out of all three comprehension types, dictionary comprehensions are the most complex, because the left-hand side (before the for) consists of two expressions instead of one. Here is one example of a dictionary comprehension that creates a “table of values” for the function \(f(x) = x^2 + 1\).

>>> {x : x ** 2 + 1 for x in {1, 2, 3, 4, 5}}
{1: 2, 2: 5, 3: 10, 4: 17, 5: 26}

Comprehensions with multiple variables

Our last example in this section will be to illustrate how multiple variables are used within the same comprehension expression. First, recall how we defined the Cartesian product of two sets using set builder notation: \[ A \times B = \{ (x, y) \mid x \in A \text{ and } y \in B \}.\] In this expression, the expression \((x, y)\) is evaluated once for every possible combination of elements \(x\) of \(A\) and elements \(y\) of \(B\).

The same holds for set, list, and dictionary comprehensions. We can specify additional variables in a comprehension by adding extra for <variable> in <collection> clauses to the comprehension. For example, if we define the following sets:

>>> nums1 = {1, 2, 3}
>>> nums2 = {10, 20, 30}

then we can calculate their Cartesian product using the following set comprehension: Remember, sets are unordered! Don’t get hung up on the unusual order in the output.

>>> {(x, y) for x in nums1 for y in nums2}
{(3, 30), (2, 20), (2, 10), (1, 30), (3, 20), (1, 20), (3, 10), (1, 10), (2, 30)}

In general, if we have a comprehension with clauses for v1 in collection1, for v2 in collection2, etc., then the comprehension’s inner expression is evaluated once for each combination of values for the variables. This illustrates yet another pretty impressive power of Python: the ability to combine different collections of data together in a short amount of code.

The physics behind how we perceive colour is incredibly interesting, but also complex. Humans have developed a broad range of names of colours to identify categories like “red” in everyday language. Although the names we use for colours vary widely from language to language! Yet these categories can be fairly broad and imprecise; useful for everyday communication, but not for computer graphics and design. So in this section, we’ll learn about how computers represent colour data.

Mathematics can help us represent colours by a combination of numbers; the rules for how numbers map to colours is called a colour model. Many colour models exist, but one of the most common is the RGB colour model. At some point in your youth, you may have discovered that mixing two colours together (i.e., with paint, crayons, etc.) produces a different colour. The RGB colour model is based on the same idea: each colour is represented by three numbers, one for the “amount” of red, green, and blue to be mixed together.

A common form of the RGB colour model in a computer is called the RGB24 colour model, and allows for each of the red, green, and blue amounts to be a number between 0 and 255, inclusive. Though RGB24 is quite common, software like Photoshop allow for a larger range of numbers, enabling more granularity it their colour representations. You can look up the term deep colour to find out more about more sophisticated colour models Formally, we can define the set \(S = \{0, 1, \dots, 255\}\) and \(\mathcal{C}\) to be the set of all possible colours in the universe. Then the RGB colour model is a function \(RGB_{24}: S \times S \times S \to \mathcal{C}\) that takes in red, green, and blue values from \(S\) and returns a colour. This \(RGB_{24}\) function is one-to-one, as every combination of (red, green, blue) values produces a different colour.

Colours in Python

The RGB24 colour model translates naturally to Python: we represent a colour value as a tuple of three integers, where each integer is between 0 and 255, inclusive. For example, we can use (0, 0, 0) to represent a pure black, and (181, 57, 173) to represent a shade of purple. Of course, just representing these values as tuples doesn’t automatically make them colours:

>>> (181, 57, 173)  # This tuple evaluates to... itself
(181, 57, 173)

But as you’ll see in your first tutorial this year, we can pass these tuples to operations that expect colour values, and get remarkable results.

References

• Hexadecimal Colors
• Color Theory

In the previous chapter, we began our study of programming in Python by studying three main ingredients: literals, operators, and variables. We can express complex computations using just these forms of Python code, but as the tasks we want to perform grow more complex, so too does the code we need to write. In this chapter, we’ll learn about using functions in Python to organize our code into useful logical blocks that can be worked on separately and reused again and again in our programs.

Review: Functions in mathematics

Before looking at functions in Python, we’ll first review some of the mathematical definitions related to functions from the First-Year CS Summer Prep.

Let \(A\) and \(B\) be sets. A function \(f : A \to B\) is a mapping from elements in \(A\) to elements in \(B\). \(A\) is called the domain of the function, and \(B\) is called the codomain of the function.

Functions can have more than one input. For sets \(A_1, A_2, \dots, A_k\) and \(B\), a \(k\)-ary function \(f: A_1 \times A_2 \times \dots \times A_k \to B\) is a function that takes \(k\) arguments, where for each \(i\) between \(1\) and \(k\), the \(i\)-th argument of \(f\) must be an element of \(A_i\), and where \(f\) returns an element of \(B\). We have common English terms for small values of \(k\): unary, binary, and ternary functions take one, two, and three inputs, respectively. For example, the addition operator \(+ : \R \times \R \to \R\) is a binary function that takes two real numbers and returns their sum. For readability, we usually write this function as \(x+y\) instead of \(+(x,y)\).

Python’s built-in functions in Python

We’ve seen that Python has many operators, like + that can be used on various data types. These operators are actually functions represented by symbols (e.g., addition through the + symbol). But there aren’t enough symbols to represent every function we could ever want. So Python also defines several functions that we can use to perform additional operations; these functions are called built-in functions, as they are made automatically available to us anywhere in a Python program. For example, the Python function abs takes a single numeric input and returns its absolute value. But how do we actually use it?

A Python expression that uses a function to operate on a given input is called a function call, and has the same syntax as mathematics: <function_name>(<argument>, <argument>, ...). For example, here are two examples of a function call expressions that call abs:

>>> abs(-10)  # Returns the absolute value of -10.
10
>>> abs(100)
100

Function calls are central to programming, and come with some new terminology that we’ll introduce now and use throughout the next year.

• In a function call expression, the input expressions are called arguments to the function call. Example: in the expression abs(-10), the -10 is the argument of the function call.
• When we evaluate a function call, we say that the arguments are passed to the function. Example: in abs(-10), we say that -10 is passed to abs.
• When the function call produces a value, we say that the function call returns a value, and refer to this value as the return value of the function call expression. Example: the return value of abs(-10) is 10.

In your mathematical studies so far, you’ve mainly studied unary numeric functions, i.e., functions that take in just one numeric argument and return another number. Examples include the sin and log functions. In programming, however, it is very common to work with functions that operate on a wide variety of data types, and a wide number of arguments. Here are a few examples of built-in functions that go beyond taking a single numeric argument:

• The len function takes a string or collection data type (e.g., set, list) and returns the size of its input. While we defined “size” of these data types back in Section 1.1, we didn’t cover them in Python in the last chapter because we were waiting to get to functions.

  >>> len({10, 20, 30})
  3
  >>> len('')
  0
  >>> len(['a', 'b', 'c', 'd', 'e'])
  5
  >>> len({'David': 100, 'Mario': 0})
  2

• The sum function takes a collection of numbers (e.g., a set or list whose elements are all numbers) and returns the sum of the numbers.

  >>> sum({10, 20, 30})
  60
  >>> sum([-4.5, -10, 2, 0])
  -12.5

• The sorted function takes a collection and returns a list that contains the same elements as the input collection, sorted in ascending order.

  >>> sorted([10, 3, 20, -4])
  [-4, 3, 10, 20]
  >>> sorted({10, 3, 20, -4})  # Works with sets, too!
  [-4, 3, 10, 20]

• The max function is a bit special, because there are two ways it can be used. When it is called with two or more inputs, those inputs must be numeric, and in this case max returns the largest one.

  >>> max(2, 3)
  3
  >>> max(-2, 10, 3, 0, 1, 7)
  10

  But max can also be called with just a single argument, a non-empty collection of numbers. In this case, max returns the largest number in the collection.

  >>> max({2, 3})
  3
  >>> max([-2, 10, 3, 0, 1, 7])
  10

• The range function we saw in the last chapter takes in two integers start and stop and returns a value representing a range of consecutive numbers between start and stop - 1, inclusive. For example, range(5, 10) represents the sequence of numbers 5, 6, 7, 8, 9. If start >= end, then range(start, end) represents an empty sequence.

One special function: type

The last built-in function we’ll cover in this section is type, which takes any Python value and returns its type. Let’s check it out: The term class that you see returned here is the name Python uses to refer to mean “data type”. More on this later.

>>> type(3)
<class 'int'>
>>> type(3.0)
<class 'float'>
>>> type('David')
<class 'str'>
>>> type([1, 2, 3])
<class 'list'>
>>> type({'a': 1, 'b': 2})
<class 'dict'>

If you’re ever unsure about the type of a particular value or variable, you can always call type on it to check!

Nested function calls

Just like other Python expressions, you can write function calls within each other, or mix them with other kinds of expressions.

>>> max(abs(-100), 15, 3 * 20)
100

However, just as we saw with deeply nested arithmetic expressions earlier, too much nesting can make Python expressions difficult to read and understand, and so it is a good practice to break down a complex series of function calls into intermediate steps using variables:

>>> v1 = abs(-100)
>>> v2 = 15
>>> v3 = 3 * 20
>>>> max(v1, v2, v3)
100

Methods: functions belonging to data types

The built-in functions we’ve studied so far all have one interesting property in common: they can all be given arguments of at least two different data types: for example, abs works with both int and float, len and sorted work with set list (and others), and type works with values of absolutely any data type. In fact, this is true for almost all built-in functions in Python, as part of the design of the language itself.

However, Python’s data types also support operations that are specific that that particular data type: for example, there are many operations we can perform on strings that a specific to textual data, and that wouldn’t make sense for other data types.

Python comes with many functions that perform these operations, but handles them a bit differently than the built-in functions we’ve seen so far. A function that is defined as part of a data type is called a method. The terms function and method are sometimes blurred in programming, particularly from language to language, but for us these terms have precise and distinct meanings! All methods are functions, but not all functions are methods. For example, the built-in functions we looked at above are all not methods. We refer to functions that are not methods as top-level functions. We’ll see later how we define functions and methods in Python, but for now let’s look at a few examples of methods.

One str method in Python is called lower, and has the effect of taking a string like 'David' and returning a new string with all uppercase letters turned into lowercase: 'david'. To call this method, we refer to it by first specifying the name of the data type it belongs to (str), followed by a period (.) and then the name of the method.

>>> str.lower('David')
'david'

Here are a few other examples of methods for different data types, just to give you a sense of the kinds of operations that are allowed.

>>> str.split('David wuz hear')           # str.split splits a string into words
['David', 'wuz', 'hear']
>>> set.union({1, 2, 3}, {2, 10, 20})     # set.union performs the set union operation
{1, 2, 3, 20, 10}
>>> list.count([1, 2, 3, 1, 2, 4, 2], 2)  # list.count counts the number of times a value appears in a list
3                                         # (remember, a list can have duplicates!)

References

• CSC108 videos: Functions (Part 1, Part 2, Part 3)
• Appendix A.1 Python Built-In Function Reference
• Appendix A.2 Python Built-In Data Types Reference (includes descriptions of methods)

Python provides many built-in top-level functions and methods for us, but as we start writing more code, it is essential for us to be able to create our own functions specific to the problem we are solving. In this section, we’ll learn how to define our own top-level functions in Python. And later on, we’ll study how to define our own data types and methods as well.

First, let’s recall how we define a function in mathematics. We first specify the function name, domain, and codomain: for example, \(f: \R \to \R\). Then, we write the function header and body, usually in a single line: for example, \(f(x) = x^2\). We do this so often in mathematics that we often take parts of this for granted, for example leaving out the domain/codomain specification, and usually choosing \(f\) as the function name and \(x\) as the parameter name. However, the functions we’ll implement in Python are much more diverse, and so it will be important to be explicit in every part of this process.

Defining a Python function

Here is the complete definition of a “squaring” function in Python. Take a moment to read through the whole definition, and then continue reading to learn about this definition’s different parts.

def square(x: float) -> float:
    """Return x squared.

    >>> square(3.0)
    9.0
    >>> square(2.5)
    6.25
    """
    return x ** 2

This function definition is the most complex form of Python code we’ve seen so far, so let’s break this down part by part.

1. The first line, def square(x: float) -> float: is called the function header. Its purpose is to convey the following pieces of information:

   • The function’s name (square).
   • The number and type of arguments the function expects. A parameter is a variable in a function definition that refers to a argument when the function is called. In this example, the function has one parameter with name x and type float.
   • The function’s return type, which is the type following the ->, float. In this example, the function’s parameter and return type are the same, but this won’t always be the case.

   The syntax for a function header for a unary function is:

   def <function_name>(<parameter_name>: <parameter_type>) -> <return_type>:

   Compared to our mathematical version, there are two main differences. First, we chose the name square rather than f as the function name; in Python, we will always pick descriptive names for our functions rather than relying on the conventional “\(f\)”. And second, we use data types to specify the function domain and codomain: the code x: float specifies that the parameter x must be a float value, and the code -> float specifies that this function always returns a float value.

   We can express this restriction in an analogous way to \(f: \R \to \R\) by writing float -> float; we call float -> float the type contract of the square function.

2. The next seven lines, which start and end with triple-quotes ("""), is called the function docstring. This is another way of writing a comment in Python: text that is meant to be read by humans, but not executed as Python code. The goal of the function docstring is to communicate what the function does.

   The first part of the docstring, Return x squared., is an English description of the function. The second part might look a bit funny at first, since it seems like Python code:Or more precisely, it looks like the Python console!

   >>> square(3.0)
   9.0
   >>> square(2.5)
   6.25

   This part of the docstring shows example uses of the function, just like the examples we showed of built-in functions in the previous section. You can read the first example literally as “when you type square(3.0) into the Python console, 9.0 is returned” and the second as “when you type square(2.5) into the Python console, 6.25 is returned”. These examples are called doctest examples, for a reason we’ll see in a future section. While a English description may technically be enough to specify the function’s behaviour, doctest examples are invaluable for aiding understanding of the function behaviour (which is why we use them in teaching as well!).

   The function docstring is indented inside the function header, as a visual indicator that it is part of the overall function definition. Unlike many other programming languages, this kind of indentation in Python is mandatory rather than merely recommended. Python’s designers felt strongly enough about indentation improving readability of Python programs that they put indentation requirements like this into the language itself.

3. The final line, return x ** 2, is called the body of the function, and is the code that is executed when the function is called. Like the function docstring, the function body is also indented so that it is “inside” the function definition.

   This code uses another keyword, return, which signals a new kind of statement: the return statement, which has the form:

   return <expression>

   When a return statement is executed, the following happens:

   1. The <expression> is evaluated, producing a value.
   2. That value is then returned to wherever the function was called. No more code in the function body is executed after this point.

What happens when a function is called?

In the previous section, we called built-in functions, and took for granted that they worked properly, without worrying about how they work. Now that we’re able to define our own functions, we are ready to fully understand what happens when a function is called.

As an example, suppose we’ve defined square as above, and then call it in the Python console:

>>> square(2.5)

When we press Enter, the Python interpreter evaluates the function call by doing the following:

1. Evaluate the argument 2.5, and then assign 2.5 to the function parameter x.
2. Evaluate the body of the square function, by doing:
   1. First evaluate x ** 2, which is 6.25 (since x refers to the value 2.5).
   2. Then stop executing the function body, and return the value 6.25 back to the Python console.
3. The function call square(2.5) evaluates to 6.25, and this is displayed on the screen.

As we observed in the previous section, we can combine multiple function calls within a single expression. What happens when we call square twice in the same expression? For example:

>>> square(2.5) + square(-1.0)

We can step through this as well; notice how we’ve duplicated the text from before to illustrate the similarities between calling square(2.5) and -square(-1.0).

1. Python evaluates the operands to + in left-to-right order, so evaluate square(2.5) first.
   1. Evaluate 2.5, and then assign 2.5 to the function parameter x.
   2. Evaluate the body of the square function, by doing:
      1. First evaluate x ** 2, which is 6.25 (since x refers to 2.5).
      2. Then stop executing the function body, and return the value 6.25 back to the Python console.
2. Nothing is displayed yet! There’s still square(-1.0) to be evaluated.
   1. Evaluate -1.0, and then assign -1.0 to the function parameter x.
   2. Evaluate the body of the square function, by doing:
      1. First evaluate x ** 2, which is 1.0 (since x refers to -1.0).
      2. Then stop executing the function body, and return the value 1.0 back to the Python console.
3. Now the expression to evaluate has been simplified to 6.25 + 1.0, which evaluates to 7.25. This value is displayed on the screen.

Defining functions in files

While it is possible to define functions directly in the Python console, this isn’t a good approach: every time we restart the Python console, we lose all our previous definitions. So instead, we save functions in files so that we can reuse them across multiple sessions in the Python console (and in other files).

For example, suppose we have the following file called my_functions.py:

def square(x: float) -> float:
    """Return x squared.

    >>> square(3.0)
    9.0
    >>> square(2.5)
    6.25
    """
    return x ** 2

In PyCharm, we can right-click and select “Run File in Python Console”. This will start the Python console and run our file, which then allows us to call our function square just like any built-in function:

>>> square(3.0)
9.0

Defining functions with multiple parameters

Let’s now look at a more complex example that will illustrate a function definition that takes in more than one parameter.

Recall the distance formula from Section 1.4 to calculate the distance between two points \((x_1, y_1), (x_2, y_2)\) in the Cartesian plane: \[d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\]

We’ll now write a function in Python that calculates this formula. This function will take two inputs, where each input is a tuple of two floats, representing the \(x\)- and \(y\)-coordinates of each point. When we define a function with multiple parameters, we write the name and type of each parameter using the same format we saw earlier, with parameters separated by commas from each other. Here is the function header and docstring:

def calculate_distance(p1: tuple, p2: tuple) -> float:
    """Return the distance between points p1 and p2.

    p1 and p2 are tuples of the form (x, y), where the x- and y-coordinates are points.

    >>> calculate_distance((0, 0), (3.0, 4.0))
    5.0
    """

In order to use the above formula, we need to extract the coordinates from each point. This is a good reminder of tuple indexing, and the fact that function bodies can consist of more than one statement. Remember: the function body’s statements are executed one at a time until a return statement is executed.

    # The start of the body of calculate_distance
    x1 = p1[0]
    y1 = p1[1]
    x2 = p2[0]
    y2 = p2[1]

Now that we have the four coordinates, we can apply the above formula and return the result

    # Continuing the function body
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

Putting this all together, we have:

def calculate_distance(p1: tuple, p2: tuple) -> float:
    """Return the distance between points p1 and p2.

    p1 and p2 are tuples of the form (x, y), where the x- and y-coordinates are points.

    >>> calculate_distance((0, 0), (3.0, 4.0))
    5.0
    """
    x1 = p1[0]
    y1 = p1[1]
    x2 = p2[0]
    y2 = p2[1]
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

Function reuse

Our above function body is perfectly correct, but you might notice that the ** 2 expressions exactly mimic the body of the first function we defined in this section: square. And so we can reuse the square function inside the body of calculate_distance:

def calculate_distance(p1: tuple, p2: tuple) -> float:
    """Return the distance between points p1 and p2.

    p1 and p2 are tuples of the form (x, y), where the x- and y-coordinates are points.

    >>> calculate_distance((0, 0), (3.0, 4.0))
    5.0
    """
    x1 = p1[0]
    y1 = p1[1]
    x2 = p2[0]
    y2 = p2[1]
    return (square(x1 - x2) + square(y1 - y2)) ** 0.5

This example of function reuse is quite small, but as our programs grow larger, it will be essential to organize our code into different functions. We’ll explore this idea in more detail, and other principles of good function and program design, throughout this course.

References

• CSC108 videos: Defining Functions (Part 1, Part 2)
• CSC108 videos: Docstrings and Function help (Video)
• CSC108 videos: Function Reuse (Part 1, Part 2, Example)

One of the key purposes of functions is to separate different computations in a program, so that we don’t have to worry about them all at once. When we write our code in separate functions, we can focus on working with just a single function, and ignore the rest of the code in other functions.

One way in which Python support this way of designing programs is through separating the variables in each functions so that a function call can only access its own variables, but not variables defined within other functions. In this section, we’ll explore how this works, learning more about how Python keep track of function calls and variables.

Example 1: introducing local variable scope

Consider the example from the previous section:

def square(x: float) -> float:
    """Return x squared.

    >>> square(3.0)
    9.0
    >>> square(2.5)
    6.25
    """
    return x ** 2

The parameter x is a variable that is assigned a value based on when the function was called. Because this variable is only useful inside the function body, Python does not allow it to be accessible from outside the body. We say that x is a local variable of square because it is limited to the function body. Here is another way to put it, using an important new definition. The scope of a variable is the places in the code where that variable can be accessed. A local variable of a function is a variable whose scope is the body of that function.

Let’s illustrate by first creating a variable in the Python console, and then calling square.

>>> n = 10.0
>>> result = square(n + 3.5)

We know that when square is called, its argument expression n + 3.5 is evaluated first, producing the value 13.5, which is then assigned to the parameter x. Now let’s consider what the memory model looks like when the return statement is evaluated. A naive diagram would simply show the two variables n and x and their corresponding values: We do not show result because it hasn’t been assigned a value yet; this only happens after square returns.

But this is very misleading! In our memory model diagrams, we group the variables together based on whether they are introduced in the Python console or inside a function:

We use the name __main__ to label the table for variables defined in the Python console. This is a special name in Python—more on this later. Inside the body of square, the only variable that can be used is x, and the outside in the Python console, the only variable that can be used is n. This may seem a tricky at first, but these memory model diagrams are a good way to visualize what’s going on. At the point that the body of square is evaluated, only the “square” table in the memory model is active:

But after square returns and we’re back to the Python console, the “square” table is no longer accessible, and only the __main__ table is active:

Trying to access variable x from the Python console results in an error:

>>> n = 10.0
>>> square(n + 3.5)
182.25
>>> x
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'x' is not defined

Example 2: duplicate variable names

The principle of “separate tables” in our memory model applies even when we use the same variable name in two different places. Suppose we modify our example above to use x instead of n in the Python console:

>>> x = 10.0
>>> result = square(x + 3.5)

Following the same reasoning as above, the argument expression x + 3.5 is evaluated to produce 13.5, which is then assigned to the parameter x. Does this modify the x variable in the Python console? No! They are different variables even though they share the same name.

We can confirm this after the function call is evaluated by checking the value of the original x.

>>> x = 10.0
>>> result = square(x + 3.5)
>>> result
182.25
>>> x
10.0

Here is what our memory model looks like after square has returned:

Example 3: (not) accessing another function’s variables

Our last example in this section involves two functions, one of which calls the other:

def square(x: float) -> float:
    """Return x squared.

    >>> square(3.0)
    9.0
    >>> square(2.5)
    6.25
    """
    return x ** 2


def square_of_sum(numbers: list) -> float:
    """Return the square of the sum of the given numbers."""
    total = sum(numbers)
    return square(total)

Let’s first call our new function square_of_sum in the Python console:

>>> nums = [1.5, 2.5]
>>> result = square_of_sum(nums)
>>> result
16.0

We can trace what happens at three points when we call square_of_sum:

From these diagrams, we see how the list [1.5, 2.5] is passed from the console to square_of_sum, and how the number 4.0 is passed from square_of_sum to square.

Now suppose we wanted to do something a bit silly: have square access total instead of x. We know from our memory model that these variables should be assigned the same value, so the program’s behaviour shouldn’t change, right?

def square(x: float) -> float:
    """Return x squared.

    >>> square(3.0)
    9.0
    >>> square(2.5)
    6.25
    """
    return total ** 2  # Now we're using total instead of x


def square_of_sum(numbers: list) -> float:
    """Return the square of the sum of the given numbers."""
    total = sum(numbers)
    return square(total)

Let’s see what happens when we try to call square_of_sum in the Python console now:

>>> nums = [1.5, 2.5]
>>> square_of_sum(nums)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 15, in square_of_sum
  File "<input>", line 9, in square
NameError: name 'total' is not defined

An error occurs! Let’s take a look at the state of memory when square is called (this is the same as above):

Well, there is indeed both a total variable and an x variable with the same value, 4.0. So why are we getting this error? Python’s rule for local scope: a local variable can only be accessed in the function body it is defined. Here, the statement return total ** 2 is in the body of square, but attempts to access the local variable of a different function (square_of_sum). When the Python interpreter attempts to retrive the value of total, it looks only in the scope of square, and doesn’t find total, resulting in a NameError.

The somewhat non-intuitive point about this behaviour is that this happens even when square_of_sum is still active. In our example, square is called from within square_of_sum, and so the variable total does exist in Python’s memory—it just isn’t accessible. While this might seem like a limitation of the language, it’s actually a good thing: this prevents you from accidentally using a variable from a completely different function when working on a function.

Summary

In this section, we learned about how Python handles local variables, by making them accessible only from within the function that they are defined. Though we hope this makes intuitive sense, some of the details and diagrams we presented here were fairly technical. We recommend coming back to this section in a few days and reviewing this material, perhaps by explaining in your own words what’s happening in each example. You can also practice drawing this style of memory model diagram for future code that you write.

So far we have learned about Python’s built-in functions and various data type methods. But these form a small fraction of all the functions that the Python programming language comes with. Python’s other functions (and even other data types) are separated into various modules, which is another name we give to Python code files. Unlike the functions and data types we’ve seen so far, these modules are not automatically loaded when run the Python interpreter, as they contain more specialized functions and data types. So in this section, we’re going to learn how to load one of these modules and use their definitions.

The import statement

To load a Python module, we use a piece of code called an import statement, which has the following syntax:

import <module_name>

For example, here is how we could load the math module in the Python console:

>>> import math

Like the other statements we’ve seen so far, import statements do not produce a value, but they do have an important effect. An import statement introduces a new variable (the name of the module being imported) that can be used to refer to all definitions from that module.

For example, the math module defines a function log2 which computes the base-2 logarithm of a number. To access this function, we use dot notation: This notation is the same as accessing data type methods, but log2 is not a method. It’s a top-level function, just one that happens to be defined in the math module.

>>> math.log2(1024)
10.0

What other functions are contained in the math module? We’ll make use of a few other later in this course, but if you’re curious you can call the special built-in function dir on the the module (or any other module) to see a list of functions and other variables defined in the module:

>>> dir(math)
['__doc__', '__loader__', '__name__', '__package__', '__spec__', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atan2', 'atanh', 'ceil', 'comb', 'copysign', 'cos', 'cosh', 'degrees', 'dist', 'e', 'erf', 'erfc', 'exp', 'expm1', 'fabs', 'factorial', 'floor', 'fmod', 'frexp', 'fsum', 'gamma', 'gcd', 'hypot', 'inf', 'isclose', 'isfinite', 'isinf', 'isnan', 'isqrt', 'ldexp', 'lgamma', 'log', 'log10', 'log1p', 'log2', 'modf', 'nan', 'perm', 'pi', 'pow', 'prod', 'radians', 'remainder', 'sin', 'sinh', 'sqrt', 'tan', 'tanh', 'tau', 'trunc']

Ignoring the first few with the double underscore, we see some familiar looking names, like ceil, floor, pi, and sin. We’ve linked to the documentation for the math module in the References section below.

The datetime module

Python comes with far more modules than we’ll have time to learn about in this course. However, just to illustrate the breadth of these modules, we’ll briefly introduce one more that will be useful occasionally throughout the course.

The datetime module provides not just functions but new data types for representing time-based data. The first data type we’ll study here is date, which is a data type that represents a specific date.

>>> import datetime
>>> canada_day = datetime.date(1867, 7, 1)  # Create a new date
>>> type(canada_day)
<class 'datetime.date'>
>>> term_start = datetime.date(2020, 9, 10)
>>> datetime.date.weekday(term_start)  # Return the day of the week of the date
3  # 0 = Monday, 1 = Tuesday, etc.

Note the double use of dot notation in that last expression. datetime.date is the data type being accessed, and .weekday accesses a method of that data type.

We can compare dates for equality using == and chronological order (e.g., < for comparing one date comes before another). We can also subtract dates, which is pretty cool:

>>> term_start - canada_day
datetime.timedelta(days=55954)

The difference between two dates is an instance of the datetime.timedelta data type, which is used to represent an interval of time. What the above expression tells us is that 55,954 days have passed between the first day of the fall semester and the day of Canada’s confederation. Fun fact: Canada’s confederation first consisted of only four provinces: Ontario, Quebec, Nova Scotia, and New Brunswick.

There’s a lot of Python out there—don’t worry!

Up to this point, we’ve covered several different data types, functions, methods, and now modules in Python. It might be starting to feel a bit daunting, and we wanted to take a moment to pause and look at the bigger picture. Our goal in showing you these elements of Python is not to overwhelm you, but instead to give you a taste of the language’s powerful computational capabilities. But this course is not about memorizing different functions, data types, and modules in Python! All throughout this course, you’ll have access to references and documentation that describe the functionality of these different elements, and will have lots of opportunities to practice using them. For now, all we want you to know is simply that these capabilities exist, how to experiment with them in the Python console, and how to look up information about them.

References

• datetime module documentation
• math module documentation

Often when beginners are tasked with writing a program to solve a problem, they jump immediately to writing code. Doesn’t matter whether the code is correct or not, or even if they fully understand the problem: somehow the allure of filling up the screen with text is too tempting. So before we go further in our study of the Python programming language, we’ll introduce the Function Design Recipe, a structured process for taking a problem description and designing and implementing a function in Python to solve this problem.

The Function Design Recipe by example

Consider the following example problem: write a function to determine whether or not a number is even. We’ll use this example to illustrate the five steps of the Function Design Recipe.

   """
   >>> is_even(2)
   True
   >>> is_even(17)
   False
   """

def is_even(value: int) -> bool:
    """
    >>> is_even(2)
    True
    >>> is_even(17)
    False
    """

def is_even(value: int) -> bool:
    """Return whether value is even.

    >>> is_even(2)
    True
    >>> is_even(17)
    False
    """

def is_even(value: int) -> bool:
    """Return whether value is even.

    >>> is_even(2)
    True
    >>> is_even(17)
    False
    """
    return value % 2 == 0

The importance of documenting your functions

The Function Design Recipe places a large emphasis on developing a precise and detailed function header and docstring before writing any code for the function body. There are two main benefits to doing this.

First, when you are given a programming task—“Write a function to do X”—you want to make sure you fully understand the goal of that function before trying to solve it. Forcing yourself to write out the function header and docstring, with examples, is an excellent way to reinforce your understanding about what you need to do.

Second, as you begin to work on larger projects and writing dozens or hundreds of functions, it is easy to lose track of what each function does. The function header and docstring serve as documentation for the function, communicating to others–and to your future self—what that function is supposed to to. Your choices for the function’s name, its parameter names, its type contract, its docstring examples, and its description, can make the difference between code that is easy to work on and maintain, and code that is undecipherable.

So the bottom line is you should follow this process for all of the functions you’ll write in this course, and beyond—trust us, it will save you lots of time and headaches!

References

• CSC108 videos: Function Design Recipe (Part 1, Part 2)

The last step of the Function Design Recipe is to test your code—but how? In this section, we’ll discuss the different strategies for testing code that you’ll use during the term, and beyond. As you write more and more complex programs in this course, it will be vital to maintain good habits to support you in your programming. One of these habits is developing good tests that will ensure your code is correct, and—often overlooked—using good tools to make those tests as easy to run as possible. You want to get in the habit of writing tests early in the process of programming, and running them as often as possible to detect coding errors as soon as you make them.

Doctests: basic examples in docstrings

By following the Function Design Recipe, you naturally create a few tests for each function in the form of doctest examples, the examples you write in the function docstring. The simplest form of testing your function is import your function into the Python console, and then manually evaluate each doctest example one at a time and compare the output with the expected output in the docstring. This is a form of manual testing, as it requires human interaction to complete. Manual testing is often tedious and error-prone, so while it may be good for a quick check, we can certainly do better.

Our first improvement is to use the Python library doctest, which can automatically extract doctest examples from docstrings and convert them into runnable tests. To use doctest, you can add the following code to the very bottom of any Python file: Don’t worry about the if __name__ == '__main__' part for now; we will discuss this later on.

if __name__ == '__main__':
    import doctest     # import the doctest library
    doctest.testmod()  # run the tests

Then when you run the file, all of the doctest examples are automatically run, and you receive a report about which tests failed.

One warning: in order to use doctest, your docstring examples must be correctly formatted and valid Python code. For more information about the doctest module, check out Appendix B.1 doctest.

Creating test suites with pytest

Though doctest is an extremely useful module, the examples we write in docstrings are only simple cases meant to illustrate typical uses of the function. As functions get more complex, we’ll require more extensive tests to verify that they are correct. We could put all these tests into the function docstrings, but that would make the docstrings far too long.

So instead, we will use another Python library, pytest, to write our tests in a separate file, and so include an exhaustive set of tests without cluttering our code files. Let’s illustrate this with an example. Suppose we have defined the following function in a files trues.py: We’ve not included the body of this function, as we do not need to know how a function is implemented in order to write tests for it!

# In file trues.py

def has_more_trues(booleans: list) -> bool:
    """Return whether booleans contains more True values than False values.

    >>> has_more_trues([True, False, True])
    True
    >>> has_more_trues([True, False, False])
    False
    """
    # Function body omitted

Now, we’ll see how to write tests for this function in a new file, which we’ll call test_trues.py. By convention, all Python modules which contain tests are named with the prefix test_. Now let us introduce some terminology. A unit test is a block of code that checks for the correct behaviour of a function for one specific input. A test suite is a collection of tests that check the behaviour of a function or (usually small) set of functions. Every test file contains a test suite.

In Python, we express a unit test as a function whose name starts with the prefix test_. The body of the function contains an assert statement, which is a new form of Python statement used to check whether some boolean expression is True or False. Here are two examples of unit tests we could write that are direct translations of the doctest examples from above:

# In file test_trues.py

from trues import has_more_trues


def test_mixture_one_more_true() -> None:
    """Test has_more_trues on a list with a mixture of True and False,
    with one more True than False.
    """
    assert has_more_trues([True, False, True])


def test_mixture_one_more_false() -> None:
    """Test has_more_trues on a list with a mixture of True and False,
    with one more False than True.
    """
    assert not has_more_trues([True, False, False])

These unit test functions are similar to the functions we’ve defined previously, with a few differences:

• Each test name and docstring documents what the test is by describing the test input.
• The return type of the test function is None, which is a special type that indicates that no value at all is returned by the function. Python’s None is a bit special, and we’ll see more of this later in the course. In the body of the test function, there is indeed no return statement—instead, there’s an assert.

So what exactly does an assert statement do? In Python, an assert statement has the form assert <expression>, and when executed it does the following:

1. First, it evaluates <expression>, which should produce a boolean value.

2. If the value is True, nothing else happens, and the program continues onto the next statement.

   But if the value is False, an AssertionError is raised. This signals to pytest that the test has failed.

So when pytest “runs” a unit test, what’s actually going on is it calls a test function like test_mixture_one_more_true. If the function call ends without raising an AssertionError, the test passes; if the function call does raise an AssertionError, the test fails. A single unit test function can contain multiple assert statements; the test passes if all of the assert statements pass, and fails if any of the assert statements raise an error.

Finally, how do we use pytest to actually run our unit test functions? Similar to doctest, we need to first import pytest and then call a specific test function.

# At the bottom of test_trues.py

if __name__ == '__main__':
    import pytest
    pytest.main(['test_trues.py'])

Now if we run this file, we see that our two unit test functions are run:

References

• CSC108 videos: Doctest (Part 1, Part 2)
• CSC108 videos: Writing a ‘__main__’ program (Part 1, Part 2)
• Appendix B.1 doctest
• Appendix B.2 pytest

There is another useful set of built-in functions that we have not yet discussed: functions that allow us to convert values between different data types. For example, given a string '10', can we convert it into the integer 10? Or given a list [1, 2, 3], can we convert it into a set {1, 2, 3}?

The answer to these questions is yes, and the way to do so in Python is quite elegant. Each data type that we have learned about so far, from int to dict, is also a function that takes an argument and attempts to convert it to a value of that data type.

Here are some examples: Some of these are more “obvious” than others. Don’t worry about the exact rules for conversions between types, as you won’t be expected to memorize them. Instead, we just want you to know that these conversions are possible using data types as functions.

>>> int('10')
10
>>> float('10')
10.0
>>> bool(1000)
True
>>> bool(0)
False
>>> list({1, 2, 3})
[1, 2, 3]
>>> set([1, 2, 3])
{1, 2, 3}
>>> set()  # Giving set no arguments results in the empty set
set()
>>> dict([('a', 1), ('b', 2), ('c', 3)])
{'a': 1, 'b': 2, 'c': 3}

In particular, str is the most versatile of these data types. Every value of the data types we’ve studied so far has a string represention which corresponds directly to how you would write the value as a Python literal.

>>> str(10)
'10'
>>> str(-5.5)
'-5.5'
>>> str(True)
'True'
>>> str({1, 2, 3})
'{1, 2, 3}'
>>> str([1, 2, 3])
'[1, 2, 3]'
>>> str({'a': 1, 'b': 2})
"{'a': 1, 'b': 2}"

Warning: conversion errors

You often have to be careful when attempting to convert between different data types, as not all values of one type can be converted into another. Attempting to convert an “invalid” value often results in a Python exception to be raised: These exceptions typically have type ValueError or TypeError.

>>> int('David')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: 'David'
>>> list(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not iterable

Preview: creating values of arbitrary data types

The ability to create values of a given type by calling the data type as a function is not unique to the built-in data types in this section. We’ve actually seen two examples of doing this so far in the course!

range revisited

Earlier, we saw that we could call range to create a sequence of numbers. But if you just try calling range by itself in the Python console, you see something kind of funny:

>>> range(5, 10)
range(5, 10)

Whereas you might have expected to see a list ([5, 6, 7, 8, 9]), in the Python console output it looks like nothing happened at all! This is because range is actually a type conversion function: Python also has a range data type that is distinct from lists (or other collection data types).

>>> five_to_nine = range(5, 10)
>>> type(five_to_nine)
<class 'range'>
>>> five_to_nine == [5, 6, 7, 8, 9]
False

datetime.date revisited

Recall an example from the last section in Section 2.4 Importing Modules:

>>> import datetime
>>> canada_day = datetime.date(1867, 7, 1)  # Create a new date
>>> type(canada_day)
<class 'datetime.date'>

In this case, the data type is datetime.date, and it is called on three arguments instead of one. In this context, datetime.date is called to create a new date value given three arguments (the year, month, and day). This is a more general form of type “conversion”, which created a data type of a new value given a single argument. And of course, this behaviour isn’t unique to datetime.date either. As we’ll see a bit later in this course, you’ll be able to take any data type—even ones you define yourself—and create values of that type by calling the data type as a function.

We have mentioned that computers use a series of 0s and 1s to store data. These 0s and 1s represent numbers. So then, how can numbers represent textual data (i.e., a string)? The answer is functions.

Once upon a time, humans interacted with computers through punched paper tape (or simply punched tape). A hole (or the lack of a hole) at a particular location on the tape represented a 0 or a 1 (i.e., binary). Today we would call each 0 or 1 a bit. Obviously, this is much more tedious than using our modern input peripherals: keyboards, mice, touch screens, etc. Eventually, a standard for representing characters (e.g., letters, numbers) with holes was settled on. Using only 7 locations on the tape, 128 different characters could be represented (\(2^7 = 128\)).

The standard was called ASCII (pronounced ass-key) and it persists to this day. You can think of the ASCII standard as a function with domain \(\{0, 1, \dots, 127\}\), whose codomain is the set of all possible characters. This function is one-to-one, meaning no two numbers map to the same character—this would be redundant for the purpose of encoding the characters. This standard covered all English letters (lowercase and uppercase), digits, punctuation, and various others (e.g., to communicate a new line). For example, the number 65 mapped to the letter 'A' and the number 126 mapped to the punctuation mark '~'.

But what about other languages? Computer scientists extended ASCII from length-7 to length-8 sequences of bits, and hence its domain increased to size 256 (\(\{0, 1, \dots, 255\}\)). This allowed “extended ASCII” to support some other characters used in similar Latin-based languages, such as 'é' (233), 'ö' (246), '€' (128), and other useful symbols like '©' (169) and '½' (189). But what about characters used in very different languages (e.g., Greek, Mandarin, Arabic)?

The latest standard, Unicode, uses up to 32 bits that gives us a domain of \(\{0, 1, \dots, 2^{32} - 1\}\), over 4 billion different numbers. This number is in fact larger than the number of distinct characters in use across all different languages! There are several unused numbers in the domain of Unicode—Unicode is not technically a function defined over \(\{0, 1, \dots, 2^{32} - 1\}\) because of this.

But with the pervasiveness of the Internet, these unused numbers are being used to map to emojis. Of course, this can cause some lost-in-translation issues. The palm tree emoji may appear different on your device than a friend’s. In extreme cases, your friend’s device may not see a palm tree at all or see a completely different emoji. Part of the process involves submitting a proposal for a new emoji. But the second half of that process means that computer scientists need to support newly approved emojis by updating their software. And, of course, in order to do that computer scientists need to have a firm understanding of functions!

Python’s Unicode conversion functions

Python has two built-in functions that implement the (partial) mapping between characters and their Unicode number. The first is ord, which takes a single-character string and returns its Unicode number as an int.

>>> ord('A')
65
>>> ord('é')
233
>>> ord('♥')
9829

The second is chr, which computes the inverse of ord: given an integer representing a Unicode number, chr returns a string containing the corresponding character.

>>> chr(65)
'A'
>>> chr(233)
'é'
>>> chr(9829)
'♥'

Unicode representations are a source of one common source of surprise for Python programmers: string ordering comparisons (<, >) are based on Unicode numeric values! For example, the Unicode value of 'Z' is 90 and the Unicode value of 'a' is 97, and so the following holds:

>>> 'Z' < 'a'
True
>>> 'Zebra' < 'animal'
True

This means that sorting a collection of strings can seem alphabetical, but treats lowercase and uppercase letters differently:

>>> sorted({'David', 'Mario', 'Jacqueline'})
['David', 'Jacqueline', 'Mario']
>>> sorted({'david', 'Mario', 'Jacqueline'})
['Jacqueline', 'Mario', 'david']

References

• ASCII Code: The extended ASCII table
• Unicode Character Table

As we get ready to write larger and more complex programs, we’re going to take a pause on programming to study formal mathematical logic. You might wonder what logic has to do with software development. As we’ll see over the course of this chapter, a firm understanding of logic allows us to precisely identify, define, and write boolean expressions and use them in our programs.

It might seem counter-intuitive to spend a whole chapter on logic, as bool is the simplest data type in Python. But writing boolean expressions that correctly capture definitions and conditions in a given problem domain can be tricky as these definitions and conditions grow in complexity. It will turn out to be very useful to have a formal mathematical language—logic—to express these complex boolean expressions before turning them into code.

Propositions

We will start our study in this chapter with propositional logic, an elementary system of logic that is a crucial building block underlying other, more expressive systems of logic that we will need in this course.

In the following sections, we describe the various operators we will use in this course. It is important to keep in mind when reading that these operators inform both the structure of formulas (what they look like) as well as the truth value of these formulas (what they mean: whether the formula is True or False based on the truth values of the individual propositional variables).

The basic operators NOT, AND, OR

We have seen these operators earlier when discussing different types of data. The fact that Python has specific keywords dedicated to these operators should at least hint that they are frequently used. Here, we spend some time introducing the operators more formally and developing our first truth tables.

The unary operator NOT (also called “negation”) is denoted by the symbol \(\lnot\). It negates the truth value of its input. So if \(p\) is True, then \(\lnot p\) is False, and vice versa. This is shown in the truth table at the side. In Python, we use the not keyword to represent this operation.

The binary operator AND (also called “conjunction”) is denoted by the symbol \(\land\). It returns True when both its arguments are True. In Python, we use the and keyword to represent this operation.

The binary operator OR (also called “disjunction”) is denoted by the symbol \(\lor\), and returns True if one or both of its arguments are True. In Python, we use the or keyword to represent this operation.

The truth tables for AND and NOT agree with the popular English usage of the terms; however, the operator OR may seem somewhat different from your intuition, because the word “or” has two different meanings to most English speakers. Consider the English statement “You can have cake or ice cream.” From a nutritionist, this might be an exclusive or: you can have cake or you can have ice cream, but not both. But from a kindly relative at a family reunion, this might be an inclusive or: you can have both cake and ice cream if you want! The study of mathematical logic is meant to eliminate the ambiguity by picking one meaning of OR and sticking with it. In our case, we will always use OR to mean the inclusive or, as illustrated in the last row of its truth table.The symbol \(\oplus\) is often used to represent the exclusive or operator, but we will not use it in this course. This is also the behaviour of the or operator in Python, which evaluates to True when both of its operands are True.

AND and OR are similar in that they are both binary operators on propositional variables. However, the distinction between AND and OR is very important. Consider for example a rental agreement that reads “first and last months’ rent and a $1000 deposit” versus a rental agreement that reads “first and last months’ rent or a $1000 deposit.” The second contract is fulfilled with much less money down than the first contract.

The implication operator

One of the most subtle and powerful relationships between two propositions is implication, which is represented by the symbol \(\Rightarrow\). The implication \(p \Rightarrow q\) asserts that whenever \(p\) is True, \(q\) must also be True. An example of logical implication in English is the statement: “If you push that button, then the fire alarm will go off.” In some contexts, we think of logical implication as the temporal relationship that \(q\) is inevitable if \(p\) occurs. But this is not always the case! Be careful not to confuse implication with causation. Implications are so important that the parts have been given names. The statement \(p\) is called the hypothesis of the implication and the statement \(q\) is called the conclusion of the implication.

How should the truth table be defined for \(p \Rightarrow q\)? First, when both \(p\) and \(q\) are True, then \(p \Rightarrow q\) should be True, since when \(p\) occurs, \(q\) also occurs. Similarly, it is clear that when \(p\) is True and \(q\) is False, then \(p \Rightarrow q\) is False (since then \(q\) is not inevitably True when \(p\) is True). But what about the other two cases, when \(p\) is False and \(q\) is either True or False? This is another case where our intuition from both English language it a little unclear. Perhaps somewhat surprisingly, in both of these remaining cases, we will still define \(p \Rightarrow q\) to be True.

The two cases when \(p\) is False but \(p \Rightarrow q\) is True are called the vacuous truth cases. How do we justify this assignment of truth values? The key intuition is that because the statement doesn’t say anything about whether or not \(q\) should occur when \(p\) is False, it cannot be disproven when \(p\) is False. In our example above, if the alarm button is not pushed, then the statement is not saying anything about whether or not the fire alarm will go off. It is entirely consistent with this statement that if the button is not pushed, the fire alarm can still go off, or may not go off.

The formula \(p \Rightarrow q\) has two equivalentHere, “equivalent” means that the two formulas have the same truth values; for any setting of their propositional variables to True and False, the formulas will either both be True or both be False. formulas which are often useful. To make this concrete, we’ll use our example “If you are a Pittsburgh Pens fan, then you are not a Flyers fan” from the introduction.

The following two formulas are equivalent to \(p \Rightarrow q\):

• \(\lnot p \lor q\). On our example: “You are not a Pittsburgh Pens fan, or you are not a Flyers fan.” This makes use of the vacuous truth cases of implication, in that if \(p\) is False then \(p \Rightarrow q\) is True, and if \(p\) is True then \(q\) must be True as well.

• \(\lnot q \Rightarrow \lnot p\). On our example: “If you are a Flyers fan, then you are not a Pittsburgh Pens fan.” Intuitively, this says that if \(q\) doesn’t occur, then \(p\) cannot have occurred either.

  This equivalent formula is in fact so common that we give it a special name: the contrapositive of the implication \(p \Rightarrow q\).

There is one more related formula that we will discuss before moving on. If we take \(p \Rightarrow q\) and switch the hypothesis and conclusion, we obtain the implication \(q \Rightarrow p\), which is called the converse of the original implication.

Unlike the two formulas in the list above, the converse of an implication is not logically equivalent to the original implication. Consider the statement “If you can solve any problem in this course, then you will get an A.” Its converse is “If you will get an A, then you can solve any problem in this course.” These two statements certainly don’t mean the same thing!

In Python, there is no operator or keyword that represents implication directly. If you do want to express an implication as a Python expression, we can use the first equivalent form from above, writing \(p \Rightarrow q\) as \(\lnot p \lor q\). This is less common in Python programs; however, implication has other uses in manipulating data and expressing algorithms that we’ll explore later in this course.

Biconditional (“if and only if”)

The final logical operator that we will consider is the biconditional, denoted by \(p \Leftrightarrow q\). This operator returns True when the implication \(p \Rightarrow q\) and its converse \(q \Rightarrow p\) are both True.

In other words, \(p \Leftrightarrow q\) is an abbreviation for \((p \Rightarrow q) \land (q \Rightarrow p)\). A nice way of thinking about the biconditional is that it asserts that its two arguments have the same truth value.

While we could use the natural translation of \(\Rightarrow\) and \(\land\) into English to also translate \(\Leftrightarrow\), the result is a little clunky: \(p \Leftrightarrow q\) becomes “if \(p\) then \(q\), and if \(q\) then \(p\).” Instead, we often shorten this using a quite nice turn of phrase: “\(p\) if and only if \(q\),” which is abbreviated to “\(p\) iff \(q\).”

In Python, we don’t need a separate operator to represent \(\Leftrightarrow\), since we can simply use == to determine whether two boolean values are the same!

Summary

We have now seen all five propositional operators that we will use in this course. Now is an excellent time to review these and make sure you understand the notation, meaning, and English words used to indicate each one.

While propositional logic is a good starting point, most interesting statements in mathematics contain variables over domains larger than simply \(\{\TRUE, \FALSE\}\). For example, the statement “\(x\) is a power of 2” is not a proposition because its truth value depends on the value of \(x\). It is only after we substitute a value for \(x\) that we may determine whether the resulting statement is True or False. For example, if \(x = 8\), then the statement becomes “8 is a power of 2”, which is True. But if \(x = 7\), then the statement becomes “7 is a power of 2”, which is False.

A statement whose truth value depends on one or more variables from any set is a predicate: a function whose codomain is \(\{\TRUE, \FALSE\}\). We typically use uppercase letters starting from \(P\) to represent predicates, differentiating them from propositional variables. For example, if \(P(x)\) is defined to be the statement “\(x\) is a power of \(2\)”, then \(P(8)\) is True and \(P(7)\) is False. Thus a predicate is like a proposition except that it contains one or more variables; when we substitute particular values for the variables, we obtain a proposition.

As with all functions, predicates can depend on more than one variable. For example, if we define the predicate \(Q(x,y)\) to mean “\(x^2 = y\),” then \(Q(5,25)\) is True since \(5^2 = 25\), but \(Q(5,24)\) is False.Just as how common arithmetic operators like \(+\) are really binary functions, the common comparison operators like \(=\) and \(<\) are binary predicates, taking two numbers and returning True or False.

We usually define a predicate by giving the statement that involves the variables, e.g., “\(P(x)\) is the statement ‘\(x\) is a power of 2.’” However, there is another component which is crucial to the definition of a predicate: the domain that each of the predicate’s variable(s) belong to. You must always give the domain of a predicate as part of its definition. So we would complete the definition of \(P(x)\) as follows:

\[P(x): \text{``$x$ is a power of 2,'' where $x \in \N$.}\]

Quantification of variables

Unlike propositional formulas, a predicate by itself does not have a truth value: as we discussed earlier, “\(x\) is a power of 2” is neither True nor False, since we don’t know the value of \(x\). We have seen one way to obtain a truth value in substituting a concrete element of the predicate’s domain for its input, e.g., setting \(x = 8\) in the statement “\(x\) is a power of 2,” which is now True.

However, we often don’t care about whether a specific value satisfies a predicate, but rather some aggregation of the predicate’s truth values over all elements of its domain. For example, the statement “every real number \(x\) satisfies the inequality \(x^2 - 2x + 1 \geq 0\)” doesn’t make a claim about a specific real number like 5 or \(\pi\), but rather all possible values of \(x\)!

There are two types of “truth value aggregation” we want to express; each type is represented by a quantifier that modifies a predicate by specifying how a certain variable should be interpreted.

Existential quantifier

One should think of \(\exists x \in S\) as an abbreviation for a big OR that runs through all possible values for \(x\) from the domain \(S\). For the previous example, we can expand it by substituting all possible natural numbers for \(x\):In this case, the OR expression is technically infinite, since there are infinitely many natural numbers. \[(0 \geq 0) \lor (1 \geq 0) \lor (2 \geq 0) \lor (3 \geq 0) \lor \cdots\]

Universal quantifier

One should think of \(\forall x \in S\) as an abbreviation for a big AND that runs through all possible values of \(x\) from \(S\). Thus, \(\forall x \in \N,~ x \geq 0\) is the same as \[(0 \geq 0) \land (1 \geq 0) \land (2 \geq 0) \land (3 \geq 0) \land \cdots\]

Python built-ins: any and all

In Python, the built-in function any allows us to represent logical statements using the existential quantifier. The function any takes a collection of boolean values and returns True when there exists a True value in the collection:

>>> any([False, False, True])
True
>>> any([])  # An empty collection has no True values!
False

This might not seem useful by itself, but remember that we can use comprehensions to transform one collection of data into another. For example, suppose are given a set of strings \(S\) and wish to determine whether any of them start with the letter 'D'. In predicate logic, we could write this as the statement \(\exists s \in S,~ s[0] = \text{‘D'}\). And in Python, we could do the following:

>>> strings = ['Hello', 'Goodbye', 'David']
>>> any([s[0] == 'D' for s in strings])
True

This example serves to highlight several elegant parallels between our mathematical statement and equivalent Python expression:

• \(\exists\) corresponds to calling the any function
• \(s \in S\) corresponds to for s in strings The naming conventions are a bit different, however: in mathematics, we tend to represent collections using capital letters, whereas in Python all variables are lower-case words.
• \(s[0] = \text{‘D'}\) corresponds to s[0] == 'D'

Similar to any, Python includes another built-in function all that can be used as a universal quantifier. The all function is given a collection of values and evaluates to True when every element has the value True. For example, if we wanted to express \(\forall s \in S,~ s[0] = \text{‘D'}\) in Python, we could write:

>>> strings = ['Hello', 'Goodbye', 'David']
>>> all([s[0] == 'D' for s in strings])
False

Of course, Python is more limited than mathematics because there are limits on the size of the collections, and so we cannot easily express existential statement quantified over infinite domains like \(\N\) or \(\R\). We’ll discuss this in more detail in a later section.

Writing sentences in predicate logic

Now that we have introduced the existential and universal quantifiers, we have a complete set of tools needed to represent all statements we’ll see in this course. A general formula in predicate logic is built up using the existential and universal quantifiers, the propositional operators \(\lnot\), \(\land\), \(\lor\), \(\Rightarrow\), and \(\Leftrightarrow\), and arbitrary predicates. To ensure that the formula has a fixed truth value, we will require every variable in the formula to be quantified.Other texts will often refer to quantified variables as bound variables, and unquantified variables as free variables. We call a formula with no unquantified variables a sentence. So for example, the formula \[\forall x \in \N,~ x^2 > y\] is not a sentence: even though \(x\) is quantified, \(y\) is not, and so we cannot determine the truth value of this formula. If we quantify \(y\) as well, we get a sentence: \[\forall x, y \in \N,~ x^2 > y.\]

However, don’t confuse a formula being a sentence with a formula being True! As we’ll see repeatedly throughout the course, it is quite possible to express both True and False sentences, and part of our job will be to determine whether a given sentence is True or False, and to prove it.

Commas: avoid them!

Here is a common question from students who are first learning symbolic logic: “does the comma mean ‘and’ or ‘then’?” As we discussed at the start of the course, we study to predicate logic to provide us with an unambiguous way of representing ideas. The English language is filled with ambiguities that can make it hard to express even relatively simple ideas, much less the complex definitions and concepts used in many fields of computer science. We have seen one example of this ambiguity in the English word “or,” which can be inclusive or exlusive, and often requires additional words of clarification to make precise. In everyday communication, these ambiguous aspects of the English language contribute to its richness of expression. But in a technical context, ambiguity is undesirable: it is much more useful to limit the possible meanings to make them unambiguous and precise.

There is another, more insidious example of ambiguity with which you are probably more familiar: the comma, a tiny, easily-glazed-over symbol that people often infuse with different meanings. Consider the following statements:

1. If it rains tomorrow, I’ll be sad.
2. David is cool, Toniann is cool.

Our intuitions tell us very different things about what the commas mean in each case. In the first, the comma means then, separating the hypothesis and conclusion of an implication. But in the second, the comma is used to mean and, the implicit joining of two separate sentences.Grammar-savvy folks will recognize this as a comma splice, which is often frowned upon but informs our reading nonetheless. The fact that we are all fluent in English means that our prior intuition hides the ambiguity in this symbol, but it is quite obvious when we put this into the more unfamiliar context of predicate logic, as in the formula: \[P(x), Q(x)\]

This, of course, is where the confusion lies, and is the origin of the question posed at the beginning of this section. Because of this ambiguity, never use the comma to connect propositions. We already have a rich enough set of symbols—including \(\land\) and \(\Rightarrow\)—that we do not need another one that is ambiguous and adds nothing new!

That said, keep in mind that commas do have two valid uses in predicate formulas:

• immediately after a variable quantification, or separating two variables with the same quantification
• separating arguments to a predicate

You can see both of these usages illustrated below, but please do remember that these are the only valid places for the comma within symbolic notation! \[\forall x, y \in \N,~ \forall z \in \R,~ P(x, y) \Rightarrow Q(x, y, z)\]

Manipulating negation

We have already seen some equivalences among logical formulas, such as the equivalence of \(p \Rightarrow q\) and \(\lnot p \lor q\). While there are many such equivalences, the only other major type that is important for this course are the ones used to simplify negated formulas. Taking the negation of a statement is extremely common, because often when we are trying to decide if a statement is True, it is useful to know exactly what its negation means and decide whether the negation is more plausible than the original.

Given any formula, we can state its negation simply by preceding it by a \(\lnot\) symbol: \[\lnot \big( \forall x \in \N,~ \exists y \in \N,~ x \geq 5 \lor x^2 - y \geq 30 \big).\] However, such a statement is rather hard to understand if you try to transliterate each part separately: “Not for every natural number \(x\), there exists a natural number \(y\), such that \(x\) is greater than or equal to \(5\) or \(x^2 - y\) is greater than or equal to 30.”

Instead, given a formula using negations, we apply some simplification rules to “push” the negation symbol to the right, closer the to individual predicates. Each simplification rule shows how to “move the negation inside” by one step, giving a pair of equivalent formulas, one with the negation applied to one of the logical operator or quantifiers, and one where the negation is applied to inner subexpressions.

• \(\lnot (\lnot p)\) becomes \(p\).
• \(\lnot (p \lor q)\) becomes \((\lnot p) \land (\lnot q)\).The negation rules for AND and OR are known as deMorgan’s laws.
• \(\lnot (p \land q)\) becomes \((\lnot p) \lor (\lnot q)\).
• \(\lnot (p \Rightarrow q)\) becomes \(p \land (\lnot q)\).Since \(p \Rightarrow q\) is equivalent to \(\lnot p \lor q\).
• \(\lnot (p \Leftrightarrow q)\) becomes \((p \land (\lnot q)) \lor ((\lnot p) \land q))\).
• \(\lnot (\exists x \in S,~ P(x))\) becomes \(\forall x \in S,~ \lnot P(x)\).
• \(\lnot (\forall x \in S,~ P(x))\) becomes \(\exists x \in S,~ \lnot P(x)\).

It is usually easy to remember the simplification rules for \(\land\), \(\lor\), \(\forall\), and \(\exists\), since you simply “flip” them when moving the negation inside. The intuition for the negation of \(p \Rightarrow q\) is that there is only one case where this is False: when \(p\) has occurred but \(q\) does not. The intuition for the negation of \(p \Leftrightarrow q\) is to remember that \(\Leftrightarrow\) can be replaced with “have the same truth value,” so the negation is “have different truth values.”

What about the quantifiers? Consider a statement of the form \(\lnot (\exists x \in S,~ P(x))\), which says “there does not exist an element \(x\) of \(S\) that satisfies \(P\).” The only way this could be true is for every element of \(S\) to not satisfy \(P\): “every element \(x\) of \(S\) does not satisfy \(P\).” A similar line of reasoning applies to \(\lnot (\forall x \in S,~ P(x))\).

Now we’re going to take a look at one of the most common steps in expressing statements in predicate logic and in processing large collections of data. At first glance these two might not appear that related, after going through this section you should be able to appreciate this elegant connection between predicate logic and data processing.

Expressing conditions in predicate logic

We saw in the last section that the universal quantifier \(\forall\) is used to express a statement of the form “every element of set \(S\) satisfies ____”. This works well when we use a predefined set for \(S\) (like the numeric sets \(\N\) or \(\R\)), but does not work well when we want to narrow the scope of our statement to a smaller set.

For example, consider the following statement: “Every natural number \(n\) greater than 3 satisfies the inequality \(n^2 + n \geq 20\).” The phrase “greater than 3” is a condition that modifies the statement, limiting the original domain of \(n\) (the natural numbers) to a smaller subset (the natural numbers greater than 3).

There are two ways we can represent such conditions in predicate logic. The first is to define a new set; for example, we could define a set \(S_1 = \{n \mid n \in \N \text{ and } n > 3\}\), and then simply write \(\forall n \in S_1,~ n^2 + n \geq 20\).

The second approach is to use an implication to express the condition. To see how this works, first we can rewrite the original statement using an “if … then …” structure as follows: “For every natural number \(n\), if \(n\) is greater than 3 then \(n\) satisfies the inequality \(n^2 + n \geq 20\).” We can translate this into predicate logic as \(\forall n \in \N,~ n > 3 \Rightarrow n^2 + n \geq 20\).

This works because the \(n > 3 \Rightarrow\) has a filtering effect, due to the vacuous truth case of implication. For the values \(n \in \{0, 1, 2\}\), the hypothesis of the implication, \(n > 3\) is False, and so for these values the implication itself is True. And then since the overall statement is universally quantified, these vacuous truth cases don’t affect the truth value of the statement.

The “forall-implies” structure is one of the most common forms of statements we’ll encounter in this course. They arise naturally any time a statement is universally quantified, but there are conditions that limit the domain that the statement applies to.

Filtering collections in Python

Now let’s turn our attention back to Python. Last chapter, we learned about several aggregation functions (like sum, max), and we’ve just learned about two more, any and all. Sometimes, however, we want to limit the scope of one of these functions to certain values in the input collection. For example, “find the sum of only the even numbers in a collection of numbers”, or “find the length of the longest string in a collection that starts with a 'D'”. For these problems, we can quickly identify which aggregation function is necessary, but the problem is in choosing the right argument to pass in.

This is where filtering appears. In programming, a filter operation is an operation that takes a collection of data and returns a new collection consisting of the elements in the original collection that satisfy some predicate (which can vary from one filter operation to the next).

There are different ways of accomplishing a filter operation in Python. The simplest one builds on what we’ve learned so far by adding a syntactic variation to comprehensions. We’ll use as our example a set comprehension here, but what we’ll discuss applies to list and dictionary comprehensions as well.

{<expression> for <variable> in <collection> if <condition>}

The new part, if <condition>, is a boolean expression involving the <variable>. This form of set comprehension behaves the same way as the ones we studied last chapter, except that <expression> only gets evaluated for the values of the variable that make the condition evaluate to True. Here are some examples to illustrate this:

>>> numbers = {1, 2, 3, 4, 5}  # Initial collection
>>> {n for n in numbers if n > 3}  # Pure filtering: only keep elements > 3
{4, 5}
>>> {n * n for n in numbers if n > 3}  # Filtering with a data transformation
{16, 25}

By combining these filtering comprehensions with aggregation functions, we can now achieve our goal of limiting the scope of an aggregation.

>>> numbers = {1, 2, 3, 4, 5}
>>> sum({n for n in numbers if n % 2 == 0})  # Sum of only the even numbers
6

The keyword if used in this syntax for filtering comprehensions is directly connected to our use of implication above. Just as we used the hypothesis \(n > 3 \Rightarrow\) to limit the scope of the universal quantifier to a subset of the natural numbers, here we use if n % 2 == 0 to limit the scope of the sum to just a subset of numbers.

Our final example in this section should make this connection even more explicit. Here’s how we could translate the statement \(\forall n \in S,~ n > 3 \Rightarrow n^2 + n \geq 20\) into a Python expression:

>>> numbers = {1, 2, 3, 4, 5, 6, 7, 8}
>>> all({n ** 2 + n >= 20 for n in numbers if n > 3})
True

So far, all of the function bodies we’ve written have consisted of a sequence of statements that always execute one after the other. This kind of code block is sometimes called a “straight line program”, since the statements form a linear path from one to the next. But sometimes we want to execute a statement or block of statements only some of the time, based on some condition.

This is similar to the implication operator we saw when discussing propositional logic. The implication \(p \Rightarrow q\) states that whenever \(p\) is True, \(q\) must also be True. In Python, what we would like to express is something of the form “Whenever \(p\) is True, then the block of code block1 must be executed”. To do so, we’ll introduce a new type of Python statement that play a role analogous to \(\Rightarrow\) in propositional logic.

The if statement

Python uses the if statement to express conditional execution of code. An if statement is a compound statement, meaning it contains other statements within it. Analogously, a expression like 3 + 4 is a compound expression, since it consists of smaller expressions (3 and 4). Here is our first syntax for an if statement:

if <condition>:
    <statement>
    ...
else:
    <statement>
    ...

The if statement uses two keywords, if and else. Careful: we saw the if keyword used earlier to express conditions in comprehensions. The use of if here is logically similar, but quite different in how Python interprets it. The <condition> following if must be an expression that evaluates to a boolean, called the if condition. This expression plays a role analogous to the hypothesis of an implication.

The statements on the lines after the if and else are indented to indicate that they are part of the if statement, similar to how a function docstring and body are indented relative to the function header. We call the statements under the if the if branch and the statements under the else the else branch.

When an if statement is executed, the following happens:

1. First, the if condition is evaluated, producing a boolean value.
2. If the condition evaluates to True, then the statements in the if branch are executed. If the condition evaluates to False, then the statements in the else branch are executed instead.

Let us consider an example. Suppose Toronto Pearson Airport (YYZ) has hired us to develop some software. The first feature they want is to show their clients if a flight is on time or delayed. The airport will provide us with both the time a flight is scheduled to depart and an estimated departure time based on the plane’s current GPS location. Our task is to report a status (as a string) to display a string. Here is the function header and docstring:

def get_status(scheduled: int, estimated: int) -> str:
    """Return the flight status for the given scheduled and estimated departure times.

    The times are given as integers between 0 and 23 inclusive, representing
    the hour of the day.

    The status is either 'On time' or 'Delayed'.

    >>> get_status(10, 10)
    'On time'
    >>> get_status(10, 12)
    'Delayed'
    """

Now, if we only needed to calculate a bool for whether the flight is delayed, this function would be very straightforward: simply return estimated <= scheduled, i.e., whether the estimated departure time is before or at the scheduled departure time. Boolean expressions like this are often useful first steps in implementing functions to determine different “cases” of inputs, but they aren’t the only step.

Instead, we use if statements to execute different code based on these cases. Here’s our implementation of get_status:

def get_status(scheduled: int, estimated: int) -> str:
    """..."""
    if estimated <= scheduled:
        return 'On time'
    else:
        return 'Delayed'

Our if statement uses the boolean expression we identified earlier (estimated <= scheduled) to trigger different return statements to return the correct string.

A simple control flow diagram

One useful tool for understanding if statements is drawing control flow diagrams to visualize the order in which statements execute. For example, here is a simple diagram for our get_status function above:

An if statement introduces a “fork in path” of a function’s control flow, and this is why we use the term branch for each of the if and else blocks of code.

Code with more than two cases

Now suppose Toronto Pearson Airport has changed the requirements of our feature. They’ve noticed that whenever a flight is delayed by more than four hours, the airline cancels the flight. They would like our get_status function to accommodate this change, so that the set of possible outputs is now {'On time', 'Delayed', 'Cancelled'}.

def get_status_v2(scheduled: int, estimated: int) -> str:
    """Return the flight status for the given scheduled and estimated departure times.

    The times are given as integers between 0 and 23 inclusive, representing
    the hour of the day.

    The status is 'On time', 'Delayed', or 'Cancelled'.

    >>> get_status_v2(10, 10)
    'On time'
    >>> get_status_v2(10, 12)
    'Delayed'
    >>> get_status_v2(10, 15)
    'Cancelled'
    """

Let’s consider what’s changed between this version and our previous one. If the estimated time is before the scheduled time, nothing’s changed, and 'On time' should still be returned. But when the estimated time is after the schedule time, we now need to distinguish between two separate subcases, based on the difference in time. We can express these subcases using nested if statements, i.e., one if statement contained in a branch of another:

def get_status_v2(scheduled: int, estimated: int) -> str:
    """..."""
    if estimated <= scheduled:
        return 'On time'
    else:
        if estimated - scheduled <= 4:
            return 'Delayed'
        else:
            return 'Cancelled'

This function body is correct, but just like with expressions, excessive nesting of statements can make code difficult to read and understand. So instead of using a nested if statement, we’ll introduce a new form of if statement that makes use of the elif keyword, which is short for “else if”.

if <condition1>:
    <statement>
    ...
elif <condition2>:
    <statement>
    ...
... # [any number of elif conditions and branches]
else:
    <statement>
    ...

When this form of if statement is executed, the following happens.

1. First, the if condition (<condition1>) is evaluated, producing a boolean value.
2. If the condition evaluates to True, then the statements in the if branch are executed. If the condition evaluates to False, then next elif condition is evaluated, producing a boolean.
3. If that condition evaluates to True, then the statements in that elif branch are executed. If that condition evaluates to False, then the next elif condition is evaluated. This step repeats until either one of the elif conditions evaluate to True, or all of the elif conditions have evaluated to False.
4. If neither the if condition nor any of the elif conditions evaluate to True, then the else branch executes.

Here is how we can use elif to rewrite get_status without nested if statements.

def get_status_v3(scheduled: int, estimated: int) -> str:
    """Return the flight status for the given scheduled and estimated departure times.

    The times are given as integers between 0 and 23 inclusive, representing
    the hour of the day.

    The status is 'On time', 'Delayed', or 'Cancelled'.

    >>> get_status_v3(10, 10)
    'On time'
    >>> get_status_v3(10, 12)
    'Delayed'
    >>> get_status_v3(10, 15)
    'Cancelled'
    """
    if estimated <= scheduled:
        return 'On time'
    elif estimated - scheduled <= 4:
        return 'Delayed'
    else:
        return 'Cancelled'

This code is logically equivalent to the previous version, but it’s easier to read because there’s no more nesting! Now, it is clear exactly what are the three possible branches of execution for this function.

Testing all the branches

Adding branching to our control flow makes our functions more complex, and so we need to pay attention to how we test our code. With functions that contain if statements, any one particular input we give can only test one possible execution path, so we need to design our unit tests so that each possible execution path is used at least once. This form of test design is called white box testing, because we “see through the box” and therefore can design tests based on the source code itself. In contrast, black box testing are tests created without any knowledge of the source code (so no knowledge of the different paths the code can take).

In our doctests for get_status_v3, we chose three different examples, each corresponding to a different possible case of the if statement. This was pretty straightforward because the code is relatively simple, but we’ll study later example of more complex control flow where it won’t be so simple to design test cases to cover each branch. In fact, the percentage of lines of program code that are executed when a set of tests for that program is called code coverage, and is a metric used to assess the quality of tests. While a set of tests may strive for 100% code coverage, this does not always occur as our programs grow in complexity. The concept of code coverage and other metrics used to evaluate tests is something we’ll only touch on in this course, but in future courses you’ll learn about this in more detail and even use some automated tools for calculating these metrics. In particular, even though code coverage is a commonly used metric, it is also criticized for giving a false sense of quality of a test suite. Just because all lines of code are executed at least once does not actually mean that the tests chosen cover all possible cases to consider for a program. We’ll see a simple example of this in the following section.

Building on our example

Toronto Pearson Airport is beginning to trust us with more data, and are requesting more complex features as a result. They now want us to write a function that determines how many flights are cancelled in a day. The airport will provide us with the data as a dictionary (i.e., dict), where the keys are unique flight numbers and the values for each flight number is a two-element list. The first element is the scheduled time and the second element is the estimated time. More succinctly, the data is a mapping of the form: { flight_number: [scheduled, estimated] }.

Unlike earlier, when our function input was only two integers, we are now working with a collection of data. Before we start trying to solve the problem, let’s create some example data in the Python console. Specifically, we’ll create a dictionary with values for three different Air Canada flight numbers.

>>> flights = {'AC110': [10, 12], 'AC321': [12, 19], 'AC999': [1, 1]}
>>> flights['AC110']
[10, 12]

We know that we can query the dictionary by providing an existing key. The value associated with a key is a list of integers, and we can index the list to retrieve those integers. Index 0 of the list refers to the flight number’s scheduled time, while index 1 refers to the estimated time. Let us call our get_status_v3 function for flight 'AC110':

>>> flight_ac110 = flights['AC110']
>>> get_status_v3(flight_ac110[0], flight_ac110[1])
'Delayed'

We’re making great progress! Instead of specifying the flight number ourselves (i.e., 'AC110'), we would instead like to substitute in different flight numbers based on the data we receive from the airport. We can do that using comprehensions. Let’s explore and see what we can get:

>>> {k for k in flights}
{'AC999', 'AC110', 'AC321'}
>>> {get_status_v3(flights[k][0], flights[k][1]) == 'Cancelled' for k in flights}
{False, True}
>>> [get_status_v3(flights[k][0], flights[k][1]) == 'Cancelled' for k in flights]
[False, True, False]

Our first set comprehension can get us the set of flight numbers, but that doesn’t tell us if the flight was cancelled or not. When we created our second set comprehension we could see that there was at least one flight cancelled. Remember that sets only contain unique elements, and this set consists of all possible boolean values. When we create a list comprehension, we can see that exactly one out of three flights were cancelled (there is one True value). But remember that the airport only wants to know how many flights were cancelled; a single integer value. Currently, we have a list of boolean values.

Let us now try to combine the first set comprehension with the second, using the filtering we learned in the last section.

>>> {k for k in flights if get_status_v3(flights[k][0], flights[k][1]) == 'Cancelled'}
{'AC321'}
>>> [k for k in flights if get_status_v3(flights[k][0], flights[k][1]) == 'Cancelled']
['AC321']

Excellent! We now have a set of flight numbers that were cancelled. To convert this into an integer, we can use the built-in len function on the set. Something to think about: does it matter if we use the list or set comprehension here? Let’s see what all this looks like in a function:

def count_cancelled(flights: dict) -> int:
    """Return the number of cancelled flights for the given flight data.

    flights is a dictionary where each key is a flight ID,
    and whose corresponding value is a list of two numbers, where the first is
    the scheduled departure time and the second is the estimated departure time.

    >>> count_cancelled({'AC110': [10, 12], 'AC321': [12, 19], 'AC999': [1, 1]})
    1
    """
    cancelled_flights = {k for k in flights
                         if get_status_v3(flights[k][0], flights[k][1]) == 'Cancelled'}
    return len(cancelled_flights)

Let’s review what we learned in this example:

• We can try to remember how we can use what we’ve learned by exploring in the Python console, well before starting to write the function. Here, we refreshed our memory on how we might look up values from dictionaries, index lists, call functions, create comprehensions, and filter collections.
• We can substitute in different values for a function’s input using comprehensions.
• We can reuse functions we’ve already created and tested (like get_status_v3) to help implement other functions.

In the last section we introduced if statements, a powerful Python structure that allowed us to perform conditional execution of blocks of code. But as we’ll see again and again in this course, expressive power comes with a cost: as our toolkit gets larger and the programming language features we use get more advanced, our programs also get larger and more complex; harder to read and reason about.

So every time we introduce a new part of the Python programming language, we’ll also take some time to discuss not just what it can do, but also how to use it in structured ways that minimize the complexity we create by using it, and how to reason about its behaviour formally using tools from mathematical logic.

Computing booleans: when if statements aren’t necessary

As our first example, consider the following function:

def is_even(n: int) -> bool:
    """Return whether n is even (divisible by 2)."""
    if n % 2 == 0:
        return True
    else:
        return False

When we first learn about if statements, it is tempting to use them whenever we think of different “cases” of inputs, like even vs. odd numbers in this example. But remember that if statements are fundamentally about taking boolean values and conditionally executing code (usually to generate other values). In cases where all we need is a boolean value, it is often simpler to write an expression to calculate the value directly, rather than using if statements.

In our example, the if statement is redundant and can be simplified just by returning the value of the condition:

def is_even(n: int) -> bool:
    """Return whether n is even (divisible by 2)."""
    return n % 2 == 0

Indeed, our earlier study of propositional logic should make us comfortable with the idea of treating booleans just like any other kind of value, and we should make full use of Python’s logical operators and, or, and not to combine them.

Consider this more complex example with nested if statements:

def mystery(x: lst, y: lst) -> bool:
    if x == []:
        if y == []:
            return True
        else:
            return False
    else:
        if y == []:
            return False
        else:
            return True

Here is a control flow diagram for this function, showing the four different possible execution paths.

To simplify this, we start with the first inner if statement on lines 3-6. This follows the same structure as our first example, and can be simplified to just return y == [].

The second inner if statement on lines 8-11 follows a similar structure, except that now the boolean that’s returned is the negation of the if condition. So we can simplify this as return not y == [], which we can simplify further using the != operator: return y != [].

So now we have this simplification of the function body:

def mystery(x: lst, y: lst) -> bool:
    if x == []:
        return y == []
    else:
        return y != []

But now how do we simplify this further? The idea here is to focus on the possible ways that mystery could return True. The if statement divides the inputs into two cases: when x == [] and the if branch executes, and when x != [] and the else branch executes. In the first case, when x == [], mystery returns the value of y == []. So one case for mystery returning True is when x == [] and y == []. Similarly, in the second case, when x != [], mystery returns y != [], and so the other case for mystery returning True is x != [] and y != [].

How should we combine these two cases? Because these are different cases, either one of them could occur, but we don’t expect both of them to occur (since x == [] and x != [] can’t both be true), and so we combine them using or:

def mystery(x: lst, y: lst) -> bool:
    return (x == [] and y == []) or (x != [] and y != [])

This simplification took a bit of work, but as a result we have a clearer picture of what this function does. We can illustrate this further by breaking up the nested expression using local variables with meaningful names.

def mystery(x: lst, y: lst) -> bool:
    both_empty = x == [] and y == []
    both_non_empty = x != [] and y != []
    return both_empty or both_non_empty

To check your understanding, try writing a docstring description for this function. You’ll probably find it at least a little easier to do for this version than the original. And while this is still a relatively small example, the same principle will often apply in the future, and so be on the lookout for if statements that you can simplify in this way. That said, this simplification won’t always apply or be appropriate, depending on the complexity of the branches of the statement. We’ll discuss this in more detail later.

Using if statements

if statements create branches in our code, allowing us to create more advanced functions. But more branches means more complexity because there are many possible paths that our function could take when called. To mitigate the complexity that comes with branching, we recommend two principles when working with if statements:

1. Prefer using a sequence of elifs rather than nested if statements. Overuse of nesting makes your code harder to understand, and can make the visual structure of your code more complex than necessary.
2. Write your conditions from most specific to most general. Order matters for these conditions, since they are checked one at a time in top-down order.

One small application of if statements that we’ve already taken for granted in this course is writing certain “boilerplate” code for running certain libraries on our file. For example, we saw in 2.6 Testing Functions I: doctest and pytest that we add the following code to our Python file to run the doctests in that file:

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Now that we’ve learned about if statements, we are ready to understand that first line, if __name__ == '__main__'.

import statements revisited

In 2.4 Importing Modules, we learned that an import statement is an instruction to the Python interpreter to find a Python module with a specified name and run it. This allows the program that executes the import statement to access the functions and data types defined within that module.

One consequence of this behaviour, though, is that by default all statements in the imported module are executed, not just function and data type definitions.

For example, suppose we had the following file useful.py:

# useful.py

def useful_function1(x: int) -> int:
    """...

    >>> useful_function1(1)
    110
    """
    # Body omitted


def useful_function2(s: str) -> str:
    """...

    >>> useful_function1('Hello')
    'Hello David'
    """
    # Body omitted


import doctest
doctest.testmod()

Note that here, the code to run doctest is not indented inside an if statement. It turns out that we can still run this file in the Python console, and the doctests will be run. However, these statements will also be executed every time useful.py is imported by another Python program. In other words, any time another program writes import useful, the doctests inside useful.py will be run, even though the doctests are not relevant for a program that just wants to use useful.py!

Enter __name__

To fix this problem, the Python interpreter creates a special variable called __name__ for each module when a program is run. Python uses the “double underscore” naming convention to denote special variable or function names. We’ll encounter a few more of these throughout the course. By default, the __name__ variable is set to the name of the module: the __name__ of useful.py is 'useful', and the __name__ attribute of math is 'math'.

>>> import math
>>> math.__name__
'math'

However, when you run a module (e.g., right-click and select “Run File in Python Console”), the Python interpreter overrides the default module __name__ and instead sets it to the special string '__main__'. And so checking the __name__ variable is a way to determine if the current module is being run, or whether it’s being imported by another module!

When we write if __name__ == '__main__', we are really saying, “Execute the following code if this module is being run, and ignore the following code if this module is being imported by another module”. The boolean expression __name__ == '__main__' evaluates to True in the former case, and False in the latter, and the conditional execution happens because of the if statement.

Organizing a Python file

We call this if branch (all the code under if __name__ == '__main__') the module’s main block. Here are some important conventions to follow for organizing a Python file with a main block:

1. The only code that goes outside of the main block are import statements (import ...), constant definitions (MY_CONSTANT = ...), function definitions (def ...), and data type definitions (class ...), which we will see in the next chapter.
2. Other code, like code for running doctest or pytest, goes inside the main block so that it is only executed when the module is run, and not when it is imported.
3. The main block goes at the bottom of the module.

One of the most central questions in software development is, “How do we know that the software we write is correct?” Certainly, writing test cases will ensure that our functions produce the expected output for specific situations. But as our programs increase in complexity, how confident can we be that our test cases are sufficient?

Function specifications and correctness

Before we address this question, we will formalize what it means for a program to be correct in the first place. Because functions are the primary way we organize programs, we’ll focus on what it means for an individual function to be correct.

A specification for a function consists of two parts:

1. A description of what values the function takes as valid inputs. We can represent this description as a set of predicates, where a valid input must satisfy all these predicates. We call these predicates the preconditions of the function.
2. A description of what the function returns/does, in terms of its inputs. For now, all of our Python functions only return values, and do nothing else. Later on in the course, we’ll study other kinds of function behaviour that could be included in a specification. We can represent this description as a set of predicates as well, that must all be satisfied by the return value of the function. We call these predicates the postconditions of the function.

With these two parts, a function’s specification defines what we expect the function to do. The job of an implementation of the function is to provide the Python code in the function body that meets this specification. We say that a function implementation is correct when the following holds: For all inputs that satisfy the specification’s preconditions, the function implementation’s return value satisfies the specification’s postconditions.

A function specification acts as a contract or agreement between the person who implements the function and the person who calls the function. For the person implementing the function, their responsibility is to make sure their code correctly returns or does what the specification says. When writing this code, they do not need to worry about exactly how the function is called and assume that the function’s input is always valid. So in fact, we have already seen several preconditions in this course. Every time we had a function description that said “assume X about the input(s)”, that was a precondition. For the person calling the function, their responsibility is to make sure they call the function with valid inputs. When they make this call, they do not need to worry about exactly how the function is implemented and assume that the function works correctly.

The concept of a function specification is a very powerful one, as it spreads the responsibility of function correctness across two parties that do their parts separately—as long as they both know what the function specification is. As a result, these specifications must be very precise. Outside of software, lawyers are hired to draft and review contracts to make sure that they are defensible in the eyes of the law. Similarly, programmers must behave as lawyers when designing software to write ironclad contracts that leave no ambiguity in what is expected of the user or how the software will behave. In this section, we introduce some new tools and terminology that can help our functions be more explicit in their requirements and behaviour.

Simple specifications

Even though we haven’t formally introduced the notion of a function specification until this section, you’ve been writing specifications all along simply by following the Function Design Recipe. Let’s take a look at an early example:

def is_even(n: int) -> bool:
    """Return whether n is even.

    >>> is_even(1)
    False
    >>> is_even(2)
    True
    """
    # Body omitted.

Here, the type contract and description actually form a complete specification of this function’s behaviour:

1. The type annotation of the parameter n tells us that the valid inputs to is_even are int values. The type annotation int is itself a precondition of the function.
2. Similarly, the type annotation for the return value tells us that the function will always return a bool. In addition, the description “Return whether n is even.” specifies the relationship between the function’s return value and its input. The doctest examples aid understanding, but are not strictly required to specify what this function does. The function description and return type annotation specify the postconditions of the function.

From this alone, we know what it means for this function to be implemented correctly, even if we can’t see the implementation.

is_even is implemented correctly when for all ints n, is_even(n) returns a bool that is True when n is even, and False when n is not even.

For example, suppose David has implemented this function. Mario loads this function implementation into the Python console and calls it:

>>> is_even(4)
False

In this case, 4 is an int, so Mario held up his end of the contract when he called the function. But the False return value is inconsistent with the function description, and so we know there must be an error in the implementation—David is at fault, not Mario.

Suppose David fixes his implementation, and asks Mario to try another call. Mario types in:

>>> is_even(4)
True

Okay pretty good, and now Mario tries:

>>> is_even([1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in is_even
TypeError: unsupported operand type(s) for %: 'list' and 'int'

In this case, the function did not produce a return value but rather an error (i.e., TypeError). Is David at fault again? No! Mario violated the function’s precondition by passing in a list rather than an int, and so he should have no expectation that is_even will meet its postcondition. Therefore, Mario (the caller of the function) caused the error.

Preconditions in general

All parameter type annotations are preconditions for a function. But often these type annotations are not precise enough to specify the exact set of valid inputs. Consider this function:

def max_length(strings: set) -> int:
    """Return the maximum length of a string in the set of strings.

    >>> max_length({'Hello', 'Mario', 'David Liu'})
    9
    """
    return max({len(s) for s in strings})

What happens when the set is empty? Let’s try it out in the console:

>>> empty_set = set()
>>> max_length(empty_set)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 7, in max_length
ValueError: max() arg is an empty sequence

We’ve obtained an error, rather than an int; this makes logical sense, because it is impossible to find the maximum value in a set that contains no values at all. But from a formal function specification sense, who is to blame: the function’s caller or the function’s implementer?

As it stands, the implementer is at fault because the only description of “valid inputs” given is the type annotation set; the empty set is still a set. So we need to update the specification to rule out this possibility, but how? You may recall that we’ve been adding extra “assumptions” on inputs for programming exercises in this course for the past few weeks already. What we’re learning here is how to formalize these assumptions into function docstrings. We encountered this issue in 3.3 Filtering Collections, when we wanted to restrict a statement to apply to a subset of our domain. Here we’re doing the same thing: making the set of valid function inputs more specific, because we only want to guarantee our implementation works correctly on those inputs. We add a precondition to the function docstring as follows:

def max_length(strings: set) -> int:
    """Return the maximum length of a string in the set of strings.

    Preconditions:
      - len(strings) > 0
    """
    return max({len(s) for s in strings})

Whenever possible, we’ll express these general preconditions as valid Python expressions involving the function’s parameters. Sometimes we’ll encounter a precondition that is extremely complex, in which case you can write them in English. In English, we would say that the full specification of max_length’s valid inputs is “strings is a set, and len(strings) > 0”. As functions get more complex, we can add additional preconditions by listing them under the header Preconditions: in the docstring. A function input is valid when it satisfies the type annotations and all general precondition expressions.

Note that adding the precondition to the docstring does not change the behaviour of the function. If an empty set is passed into the function by the user, the function will still produce the ValueError we saw above. However, now that the precondition has been documented in the function specification, if we call max_length(empty_set), we know that the error is entirely our fault because we violated a precondition.

Checking preconditions automatically with python_ta

While our previous example illustrates how to document preconditions as part of a function specification, it has one drawback: it relies on whoever is calling the function to read the documentation! Of course, reading documentation is an important skill for any computer scientist, but despite our best intentions we sometimes miss things. It would be nice if we could turn our preconditions into executable Python code so that the Python interpreter checks them every time we call the function.

One way to do this is to use an assert statement, just like we do in unit tests. Because we’ve written the precondition as a Python expression, we can convert this to an assertion by copy-and-pasting it at the top of the function body.

def max_length(strings: set) -> int:
    """Return the maximum length of a string in the set of strings.

    Preconditions:
      - len(strings) > 0
    """
    assert len(strings) > 0, 'Precondition violated: max_length called on an empty set.'
    return max({len(s) for s in strings})

Now, the precondition is checked every time the function is called, with a meaningful error message when the precondition is violated:

>>> empty_set = set()
>>> max_length(empty_set)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 7, in max_length
AssertionError: Precondition violated: max_length called on an empty set.

However, this approach is annoying and error-prone. First, we have to duplicate the precondition in two places. And second, we have increased the size of the function body with extra code. The python_ta library we use in this course has a way to automatically check preconditions for all functions in a given file. Here is an example:

def max_length(strings: set) -> int:
    """Return the maximum length of a string in the set of strings.

    Preconditions:
      - len(strings) > 0
    """
    return max({len(s) for s in strings})


if __name__ == '__main__':
    import python_ta.contracts
    python_ta.contracts.DEBUG_CONTRACTS = False  # Disable contract debug messages
    python_ta.contracts.check_all_contracts()

    max_length(set())

Notice that we’ve kept the function docstring the same, but removed the assertion. The function we call, python_ta.contracts.check_all_contracts, modifies our max_length function. That is, python_ta takes the function’s type contract and the preconditions it finds in the function docstring, and causes the function to check these preconditions every time the function is called! Let’s see what happens when we run this file:

Traceback (most recent call last):
...
AssertionError: max_length precondition "len(strings) > 0" violated for arguments {'strings': set()}.

Pretty cool! We’ll be using check_all_contracts for the rest of this course to help us make sure we’re sticking to the specifications we’ve written in our function header and docstrings when we call our functions. Moreover, check_all_contracts checks the return type of each function, so it’ll also work as a check when we’re implementing our functions to make sure the return value is of the correct type.

Preconditions as assumptions and restrictions

Preconditions allow the implementer of a function to specify assumptions about the function’s inputs, and so simplify the work of the implementer. On the other hand, preconditions place restrictions on the user of the function; the onus is on them to respect these preconditions every time the function is called. This often increases the complexity of the code that calls the function. For example, in our max_length function, the calling code might need an if statement to first check whether a set is empty before passing it to max_length.

When confronted with an “invalid input”, there is another strategy other than simply ruling out the invalid input with a precondition: explicitly defining some alternate function behaviour for this input. Here is another way we could define max_length:

def max_length(strings: set) -> int:
    """Return the maximum length of a string in the set of strings.

    Return 0 if strings is empty.
    """
    if strings == set():
        return 0
    else:
        return max({len(s) for s in strings})

Here, we picked a reasonable default value for max_length when given an empty set, This is very similar to how we define empty sums and products by a mathematical convention. and then handled that as an explicit case in our implementation by using an if statement. Our function implementation is more complex than before, but now another person can call our function on an empty set without producing an error:

>>> empty_set = set()
>>> max_length(empty_set)
0

You’re probably wondering: is this version of max_length better or worse than our original one with the precondition? This version resulted in a longer description and function body, but it also removed a possible error we might encounter when calling the function. On the other hand, is 0 really a “reasonable” value for the behaviour of this function? Because this is ultimately a design decision, there is no clear “right answer”—there are always trade-offs to be made. Rather than sticking with a particular rule (i.e., “always/never use preconditions”), it’s better to use broader principles to evaluate different choices. How much complexity is added by handling an additional input in a function implementation? Are there “reasonable” behaviours defined for a larger set of inputs than what you originally intended? The trade-offs are rarely clear cut.

That’s not all!

It turns out that with either of the “precondition” or “reasonable default” strategies, our specification of max_length is still incomplete. Before moving onto the next section, take a moment to study these implementations and try to guess what the gap might be!

Recall our definition of max_length from the previous section:

def max_length(strings: set) -> int:
    """Return the maximum length of a string in the set of strings.

    Preconditions:
      - len(strings) > 0
    """
    return max({len(s) for s in strings})

Let us introduce another issue:

>>> max_length({1, 2, 3})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <setcomp>
TypeError: object of type 'int' has no len()

Once again, our specification of valid inputs has failed us. The parameter type for max_length is set, and in Python sets can contain the values of many different types. It is not until the function description that we see that the parameter is not just any set, but specifically a set of strings. We could make this requirement more explicit by introducing another precondition, but there is a better approach. In this section, we’ll learn how to use Python’s typing module to increase the specificity of our type annotations.

The types in a collection

There are four collection types that have seen so far: set, list, tuple, and dict. These are analogous to the data types we’ve been using so far, with one key exception: we can specify the types of the values they can contained by writing them in square brackets. The table below shows these types and some examples; note that T, T1, etc. are variables that could be replaced with any data type.

For example:

• {'hi', 'bye'} has type set[str]
• [1, 2, 3] has type list[int]
• ('hello', True, 3.4) has type tuple[str, bool, float]
• {'a': 1, 'b': 2, 'c': 3} has type dict[str, int]

Here is how we can improve the type contract for max_length:

def max_length(strings: set[str]) -> int:
    """Return the maximum length of a string in the set of strings.

    Preconditions:
      - len(strings) > 0
    """
    return max({len(s) for s in strings})

General collections

Though indicating the type of the values inside a collection is useful, it is not always necessary. Sometimes we want to be flexible and say that a value must be a list, but we don’t care what’s in the list (could be a list of strings, a list of integers, or a list of strings mixed with integers). Or, we might want a list (or other collection) with elements of different types. In such cases, we will continue using the built-in types set, list, tuple, and dict, for these types annotations without additional information.

Applying what we’ve learned

Let us revisit a function we designed when discussing if statements:

def get_status_v3(scheduled: int, estimated: int) -> str:
    """Return the flight status for the given scheduled and estimated departure times.

    The times are given as integers between 0 and 23 inclusive, representing
    the hour of the day.

    The status is 'On time', 'Delayed', or 'Cancelled'.
    """

How can we improve the specification of this function? Looking at the type annotations we see that, since none are collection types, we cannot make them any more specific than they already are. Next, looking at the docstring we see that there is the potential for some preconditions: We kept the English description of what the times represent, but moved the Python-checkable part into formal preconditions.

def get_status_v3(scheduled: int, estimated: int) -> str:
    """Return the flight status for the given scheduled and estimated departure times.

    The times given represent the hour of the day.

    Preconditions:
      - 0 <= scheduled <= 23
      - 0 <= estimated <= 23
    """

Next let us revisit the count_cancelled function we designed:

def count_cancelled(flights: dict) -> int:
    """Return the number of cancelled flights for the given flight data.

    flights is a dictionary where each key is a flight ID,
    and whose corresponding value is a list of two numbers, where the first is
    the scheduled departure time and the second is the estimated departure time.

    >>> count_cancelled({'AC110': [10, 12], 'AC321': [12, 19], 'AC999': [1, 1]})
    1
    """
    cancelled_flights = {id for id in flights
                         if get_status2(flights[id][0], flights[id][1]) == 'Cancelled'}
    return len(cancelled_flights)

Here we can improve the type annotations. The first parameter is not just a dict, but a dict[str, list[int]]—that is, its keys are strings (the flight IDs), and the corresponding value is a list of integers. Does this type annotation mean that now the documentation describing the dictionary is irrelevant? No: while the type annotation gives some insight on the structure of the data, it does not provide domain-specific context, like the fact that the str keys represent flight IDs, or that the list values represent scheduled and estimated arrival departure times.

There is one more precondition that we can formalize, though: the length of each list in our dictionary. Every list should have length two, which translates naturally into a use of Python’s all function:

def count_cancelled(flights: dict[str, list[int]]) -> int:
    """Return the number of cancelled flights for the given flight data.

    flights is a dictionary where each key is a flight ID,
    and whose corresponding value is a list of two numbers, where the first is
    the scheduled departure time and the second is the estimated departure time.

    Precondition:
      - all(len(flights[k]) == 2 for k in flights)

    >>> count_cancelled({'AC110': [10, 12], 'AC321': [12, 19], 'AC999': [1, 1]})
    1
    """
    cancelled_flights = {id for id in flights
                         if get_status2(flights[id][0], flights[id][1]) == 'Cancelled'}
    return len(cancelled_flights)

References

• B.4 typing

Throughout this course, we will study various mathematical objects that play key roles in computer science. As these objects become more complex, so too will our statements about them, to the point where if we try to write out everything using just basic set and arithmetic operations, our formulas won’t fit on a single line! To avoid this problem, we create definitions, which we can use to express a long idea using a single term.This is analogous to using local variables or helper functions in programming to express part of an overall value or computation.

In this section, we’ll look at one extended example of defining our own predicates mathematically and in Python, and using them in our statements. Let us take some familiar terminology and make it precise using the languages of predicate logic and Python.

As you can see, using this new predicate makes our formula quite a bit more concise! But the usefulness of our definitions doesn’t stop here: we can, of course, use our terms and predicates in further definitions.

Expressing definitions in programs

As we just saw, in mathematics we can often express definitions as predicates, where an element of the domain (e.g., an integer) satisfies the predicate if it fits the definition. Because predicates are just functions, we can express these in programs as well. For example, let’s consider the divisibility predicate \(\mid\), where \(d \mid n\) means \(\exists k \in \Z,~ n = kd\) (for \(d, n \in \Z\)). Here is the start of a function design in Python:

def divides(d: int, n: int) -> bool:
    """Return whether d divides n."""

While we can use the modulo operator % to implement this function (more on this later), we’ll stick to remaining faithful to the mathematical definition as much as possible. Unfortunately, there is one challenge with translating the mathematical definition of divisibility precisely into a Python function. In mathematics we have no trouble at all representing an infinite set of numbers with the symbol \(\Z\); but in a computer program, we cannot represent infinite sets in the same way. Instead, we’ll use a property of divisibility to restrict the set of numbers to quantify over: when \(n \neq 0\), every number that divides \(n\) must lie in the range \(\{-|n|, -|n| + 1, \dots, |n| - 1, |n|\}\). We’ll actually prove this property later on!

But the next question is, how do we represent the set \(\{-|n|, -|n| + 1, \dots, |n| - 1, |n|\}\) in Python, when the \(n\) is given as a parameter? We can use the range data type: Remember the asymmetry here: the start argument is inclusive, but the end argument is exclusive.

possible_divisors = range(-abs(n), abs(n) + 1)

And then we can replace \(\Z\) by this variable in the definition of divisibility to obtain \(\exists k \in possible\_divisors,~ n = kd\). We can now translate this directly into Python code using what we learned earlier this chapter:

def divides(d: int, n: int) -> bool:
    """Return whether d divides n."""
    possible_divisors = range(- abs(n), abs(n) + 1)
    return any({n == k * d for k in possible_divisors})

Now let’s turn our attention to the definition of \(\mathit{IsPrime}\):

\[\mathit{IsPrime}(p): p > 1 \AND \big( \forall d \in \N,~ d \DIV p \IMP d = 1 \OR d = p \big), \qquad \text{where $p \in \Z$}.\]

Here’s a start for translating this definition into a Python function:

def is_prime(p: int) -> bool:
    """Return whether p is prime."""

Once again, we have a problem of an infinite set: \(\forall d \in \N\). We can use the same property of divisibility as above and note that the possible natural numbers that are divisors of p are in the set \(\{1, 2, \dots, p\}\). This is simpler than the version above because \(p \geq 1\). The quantified statement is a bit harder to translate because it contains an implication, so here we recall what we discussed in 3.3 Filtering Collections to use the if keyword in a comprehension to model implications. Here is our complete implementation of is_prime:

def is_prime(p: int) -> bool:
    """Return whether p is prime."""
    possible_divisors = range(1, p + 1)
    return (
        p > 1 and
        all({d == 1 or d == p for d in possible_divisors if divides(d, p)})
    )

Notice that just like the mathematical definition, in Python our implementation of is_prime uses the divides function. This is a great example of how useful it can be to divide our work into functions that build on each other, rather than writing all of our code in a single function. As we learn about more complex domains in this course, we’ll see this pattern repeat itself: definitions will build on top of one another, and you should expect that your functions will build on one another as well.

Divisibility and the remainder operation

You might have noticed that our definition of divides, though faithful to the mathematical definition, is not the same as how we’ve previously determined whether a number is divisible by 2 (i.e., is even).

def is_even(n: int) -> bool:
    """Return whether n is even."""
    return n % 2 == 0

In this case, we check whether n is divisible by 2 by checking whether the remainder when n is divided by 2 is 0 or not. It turns out that for non-zero \(d \in Z\), checking remainders is equivalent to the original definition of divisibility:

\[\forall n, d \in \Z,~ d \neq 0 \Rightarrow (d \mid n \Leftrightarrow n~\%~d = 0).\]

Note that when \(d = 0\), the remainder \(n~\%~d\) is undefined, and so we really do need the \(d \neq 0\) condition in the above statement.

We can use this observation to write an alternate implementation of the divides function:

def divides2(d: int, n: int) -> bool:
    """Return whether d divides n."""
    if d == 0:
        # This is the original definition.
        possible_divisors = range(-abs(n), abs(n) + 1)
        return any({n == k * d for k in possible_divisors})
    else:
        # This is a new but equivalent check.
        return n % d == 0