Tutorial: Programming in Python and Sage

This tutorial is an introduction to basic programming in Python/Sage. The reader is supposed to know the elementary notions of programming but is not supposed to be familiar with the Python language. The memo given here are far from being exhaustive. In case you need a more complete tutorial, you can have a look at the Python Tutorial. Also Python's documentation and in particular the standard library can be useful.

A :ref:`more advanced tutorial <tutorial-objects-and-classes>` presents the notions of objects and classes in Python.

System Message: ERROR/3 (tutorial-programming-python.rst, line 20); backlink

Here is a further list of resources for people wanting to learn Python:

• Learn Python in 10 minutes ou en français Python en 10 minutes
• Dive into Python is a Python book for experienced programmers. Also available in French, Plongez au coeur de Python, and other languages.
• Discover Python is a series of articles published in IBM's developerWorks technical resource center.

Data structures

In Python, typing is dynamic; there is no such thing as declaring variables. The function type returns the type of an object obj. To convert an object to a type typ just write typ(obj) as in int("123"). The command isinstance(ex, typ) returns whether the expression ex is of type typ. Specifically, any value is an instance of a class and there is no difference between classes and types.

The symbol = denotes the affectation to a variable; it should not be confused with == which denotes mathematical equality. Inequality is !=.

The standard types are bool, int, list, tuple, set, dict, str.

• The type bool (Booleans) takes two values: True and False. The boolean operator are denoted by their names or, and, not.

• Sage uses exact arithmetic on the integers. For performance reason, it uses its own type named Integer (whereas python uses the types int and long).

• A list is a data structure which groups values. It is constructed using brackets as in [1, 3, 4]. The range function creates integer lists. One can also create lists using list comprehension:

  [ <expr> for <name> in <iterable> (if <condition>) ]
  
  

  For example:

  {{{id=0| [ i^2 for i in range(10) if i % 2 == 0 ] /// [0, 4, 16, 36, 64] }}}

• A tuple is very similar to a list; it is constructed using parentheses. The empty tuple is obtained by () or by the constructor tuple(). If there is only one element, one has to write (a,). A tuple is immutable (one cannot change it) but it is hashable (see below). One can also create tuples using comprehensions:

  {{{id=1| tuple(i^2 for i in range(10) if i % 2 == 0) /// (0, 4, 16, 36, 64) }}}

• A set is a data structure which contains values without multiplicities or order. One creates it from a list (or any iterable) with the constructor set(). The elements of a set must be hashable:

  {{{id=2| set([2,2,1,4,5]) /// set([1, 2, 4, 5]) }}}

• A dictionary is an association table, which associate values to keys. Keys must be hashable. One creates dictionaries using the constructor dict, or using the syntax:

  { key1 : value1, key2 : value2 ...} 
  
  

  For example:

  {{{id=3| age = {'toto' : 8, 'mom' : 27}; age /// {'toto': 8, 'mom': 27} }}}

• Quotes (simple ' ' or double " ") encloses character strings. One can concatenate them using +.

• For lists, tuples, strings, and dictionaries, the indexing operator is written l[i]. For lists, tuples, and strings one can also uses slices as l[:], l[:b], l[a:], or l[a:b]. Negative indices start from the end.

• The len function returns the number of elements of a list, a tuple, a set, a string, or a dictionary. One writes x in C to tests whether x is in C.

• Finally there is a special value called None to denote the absence of a value.

Control structures

In Python, there is no keyword for the beginning and the end of an instructions block. Blocks are delimited thanks to indentation. Most of the time a new block is introduced by :. Python has the following control structures:

• Conditional instruction:

  if <condition>:
      <instruction sequence>
  [elif <condition>:
      <instruction sequence>]*
  [else:
      <instruction sequence>]
  
  

• Inside expression exclusively, one can write:

  <value> if <condition> else <value>
  
  

• Iterative instructions:

  for <name> in <iterable>:
      <instruction sequence>
  [else:
      <instruction sequence>]
  
  

  while <condition>:
      <instruction sequence>
  [else:
      <instruction sequence>]
  
  

  The else bloc is executed at the end of the loop if the loop is ended normally, that is neither by a break nor an exception.

• In a loop, continue jumps to the next iteration.

• An iterable is an object which can be iterated through. Iterable types include lists, tuples, dictionaries, and strings.

• An error (also called exception) is raised by:

  raise <ErrorType> [, error message]
  
  

  Usual errors includes ValueError and TypeError.

Functions

Note

Python functions vs. mathematical functions

In what follows, we deal with functions is the sense of programming languages. Mathematical functions are handled by sage in a different way. In particular it doesn't make sense to do mathematical manipulation such as additions or derivations on Python functions.

One defines a function using the keyword def as

def <name>(<argument list>):
     <instruction sequence>

The result of the function is given by the instruction return. Very short functions can be created anonymously using lambda (remark that there is no return here):

lambda <arguments>: <expression>

Note

(functional programming)

Functions are objects as any other objects. One can assign them to variables or return them.

Exercises

Lists

Creating Lists I: [Square brackets]

Example:

Exercise: Create the list $[63, 12, -10, 'a', 12]$, assign it to the variable L, and print the list.

Exercise: Create the empty list (you will often need to do this).

Creating Lists II: range

The range function provides an easy way to construct a list of integers. Here is the documentation of the range function:

range([start,] stop[, step]) -> list of integers

Return a list containing an arithmetic progression of integers.
range(i, j) returns [i, i+1, i+2, ..., j-1]; start (!) defaults to 0.
When step is given, it specifies the increment (or decrement). For
example, range(4) returns [0, 1, 2, 3].  The end point is omitted!
These are exactly the valid indices for a list of 4 elements.

Exercise: Use range to construct the list $[1,2,ldots,50]$.

Exercise: Use range to construct the list of even numbers between 1 and 100 (including 100).

Exercise: The step argument for the range command can be negative. Use range to construct the list $[10, 7, 4, 1, -2]$.

Creating Lists III: list comprehensions

List comprehensions provide a concise way to create lists from other lists (or other data types).

Example We already know how to create the list $[1, 2, dots, 16]$:

Using a list comprehension, we can now create the list $[1^2, 2^2, 3^2, dots, 16^2]$ as follows:

Exercice:

The sum of the squares of the first ten natural numbers is

System Message: ERROR/3 (tutorial-programming-python.rst, line 301)

Unknown directive type "math".

.. math:: (1^2 + 2^2 + ... + 10^2) = 385

The square of the sum of the first ten natural numbers is

System Message: ERROR/3 (tutorial-programming-python.rst, line 305)

Unknown directive type "math".

.. math:: (1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is

System Message: ERROR/3 (tutorial-programming-python.rst, line 310)

Unknown directive type "math".

.. math:: 3025 - 385 = 2640

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Filtering lists with a list comprehension

A list can be filtered using a list comprehension.

Example: To create a list of the squares of the prime numbers between 1 and 100, we use a list comprehension as follows.

Exercise: Use a list comprehension to list all the natural numbers below 20 that are multiples of 3 or 5. Hint:

• To get the remainder of 7 divided by 3 use 7%3.
• To test for equality use two equal signs (==); for example, 3 == 7.

Nested list comprehensions

List comprehensions can be nested!

Examples:

Exercise:

A Pythagorean triple is a triple $(x,y,z)$ of positive integers satisfying $x^2+y^2=z^2$. The Pythagorean triples whose components are at most $10$ are:

System Message: ERROR/3 (tutorial-programming-python.rst, line 398)

Unknown directive type "math".

.. math:: [(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]\,.

Using a filtered list comprehension, construct the list of Pythagorean triples whose components are at most $50$.

Accessing individual elements of lists

To access an element of the list, use the syntax L[i], where $i$ is the index of the item.

Exercise:

1. Construct the list L = [1,2,3,4,3,5,6]. What is L[3]?

   {{{id=23| /// }}}

2. What is L[1]?

   {{{id=24| /// }}}

3. What is the index of the first element of L?

   {{{id=25| /// }}}

4. What is L[-1]? What is L[-2]?

   {{{id=26| /// }}}

5. What is L.index(2)? What is L.index(3)?

   {{{id=27| /// }}}

Modifying lists: changing an element in a list

To change the item in position i of a list L:

Modifying lists: append and extend

To append an object to a list:

To extend a list by another list:

Modifying lists: reverse, sort, ...

Concatenating Lists

To concatenate two lists, add them with the operator +. This is not a commutative operation....

Slicing Lists

You can slice a list using the syntax L[start : stop : step]. This will return a sublist of L.

Exercise: Below are some examples of slicing lists. Try to guess what the output will be before evaluating the cell.

Advanced exercise: The following function combines a loop with the some of the list operations above. What does the function do?

Tuples

A tuple is an immutable list. That is, it cannot be changed once it is created. The syntax for creating a tuple is to the use parentheses.

We can create a tuple from a list, or vice-versa.

Tuples behave like lists in many respects:

Trying to modify a tuple will fail.

Generators

"Tuple-comprehension" does not exist. The syntax produces something called a generator. A generator allows you to process a sequence of items one at a time. Each item is created when it is needed, and then forgotten. This can be very efficient if we only need to use each item once.

at 0x...> }}} {{{id=56| g = (i^2 for i in range(5)) g[0] /// Traceback (most recent call last): TypeError: 'generator' object is unsubscriptable }}} {{{id=57| [x for x in g] /// [0, 1, 4, 9, 16] }}}

g is now empty.

{{{id=58| [x for x in g] /// [] }}}

A nice 'pythonic' trick is to use generators as the argument to functions. We do not need double parentheses for this.

{{{id=59| sum( i^2 for i in srange(100001) ) /// 333338333350000 }}}

Dictionaries

A dictionary is another built-in data type. Unlike lists, which are indexed by a range of numbers, dictionaries are "indexed" by keys, which can be any immutable object. Strings and numbers can always be keys (because they are immutable). Dictionaries are sometimes called "associative arrays" in other programming languages.

There are several ways to define dictionaries. One method is to use braces, {}, with comma-separated entries given in the form key:value.

{{{id=60| d = {3:17, "key":[4,1,5,2,3], (3,1,2):"goo", 3/2 : 17} d /// {3/2: 17, 3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]} }}}

Dictionaries behave as lists and tuples for several important operations.

Operation	Syntax for lists	Syntax for dictionaries
Accessing elements	list[3]	D["key"]
Length	len(list)	len(D)
Modifying	L[3] = 17	D["key"] = 17
Deleting items	del L[3]	del D["key"]

{{{id=61| d[10]='a' d /// {3/2: 17, 10: 'a', 3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]} }}}

A dictionary can have the same value multiple times, but each key can only appear once and must be immutable.

{{{id=62| d = {3: 14, 4: 14} d /// {3: 14, 4: 14} }}} {{{id=63| d = {3: 13, 3: 14} d /// {3: 14} }}} {{{id=64| d = {[1,2,3] : 12} /// Traceback (most recent call last): TypeError: unhashable type: 'list' }}}

Another way to add items to a dictionary is with the update() method:

{{{id=65| d = {} d /// {} }}} {{{id=66| d.update( {10 : 'newvalue', 20: 'newervalue', 3: 14, 'a':[1,2,3]} ) d /// {'a': [1, 2, 3], 10: 'newvalue', 3: 14, 20: 'newervalue'} }}}

We can iterate through the keys, or values, or both, of a dictionary.

{{{id=67| d = {10 : 'newvalue', 20: 'newervalue', 3: 14, 'a':[1,2,3]} /// }}} {{{id=68| [key for key in d] /// ['a', 10, 3, 20] }}} {{{id=69| [key for key in d.iterkeys()] /// ['a', 10, 3, 20] }}} {{{id=70| [value for value in d.itervalues()] /// [[1, 2, 3], 'newvalue', 14, 'newervalue'] }}} {{{id=71| [(key, value) for key, value in d.iteritems()] /// [('a', [1, 2, 3]), (10, 'newvalue'), (3, 14), (20, 'newervalue')] }}}

Exercise: Consider the following directed graph.

Create a dictionary whose keys are the vertices of the above directed graph, and whose values are the lists of the vertices that it points to. For instance, the vertex 1 points to the vertices 2 and 3, so the dictionary will look like:

d = {  ..., 1:[2,3], ... } 

{{{id=72| /// }}}

Then try

{{{id=73| g = DiGraph(d) g.plot() /// }}}

Using Sage types: The srange command

Example: Construct a $3 times 3$ matrix whose $(i,j)$ entry is the rational number $frac{i}{j}$. The integer generated by range are python int. As a consequence, dividing them does euclidian division.

{{{id=74| matrix([[ i/j for j in range(1,4)] for i in range(1,4)]) /// [1 0 0][2 1 0][3 1 1] }}}

Whereas Dividing sage Integer gives a fraction

{{{id=75| matrix([[ i/j for j in srange(1,4)] for i in srange(1,4)]) /// [ 1 1/2 1/3][ 2 1 2/3][ 3 3/2 1] }}}

Modifying lists has consequences!

Try to predict the results of the following commands.

{{{id=76| a = [1, 2, 3] L = [a, a, a] L /// [[1, 2, 3], [1, 2, 3], [1, 2, 3]] }}} {{{id=77| a.append(4) L /// [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] }}}

Now try these:

{{{id=78| a = [1, 2, 3] L = [a, a, a] L /// [[1, 2, 3], [1, 2, 3], [1, 2, 3]] }}} {{{id=79| a = [1, 2, 3, 4] L /// [[1, 2, 3], [1, 2, 3], [1, 2, 3]] }}} {{{id=80| L[0].append(4) L /// [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] }}}

You can use the command deepcopy to avoid these issues.

{{{id=81| a = [1,2,3] L = [deepcopy(a), deepcopy(a)] L /// [[1, 2, 3], [1, 2, 3]] }}} {{{id=82| a.append(4) L /// [[1, 2, 3], [1, 2, 3]] }}}

The same issues occur with dictionaries.

{{{id=83| d = {1:'a', 2:'b', 3:'c'} dd = d d.update( { 4:'d' } ) dd /// {1: 'a', 2: 'b', 3: 'c', 4: 'd'} }}}

Loops and Functions

For more verbose explanation of what's going on here, a good place to look is at the following section of the Python tutorial: http://docs.python.org/tutorial/controlflow.html

While Loops

While loops tend not to be used nearly as much as for loops in Python code.

{{{id=84| i = 0 while i < 10: print i i += 1 /// 0123456789 }}} {{{id=85| i = 0 while i < 10: if i % 2 == 1: i += 1 continue print i i += 1 /// 02468 }}}

Note that the truth value expression in the while loop is evaluated using bool().

{{{id=86| bool(True) /// True }}} {{{id=87| bool('a') /// True }}} {{{id=88| bool(1) /// True }}} {{{id=89| bool(0) /// False }}} {{{id=90| i = 4 while i: print i i -= 1 /// 4321 }}}

For Loops

Here is a basic for loop iterating over all of the elements in the list l:

{{{id=91| l = ['a', 'b', 'c'] for letter in l: print letter /// abc }}}

The range function is very useful when you want to generate arithmetic progressions to loop over. Note that the end point is never included:

{{{id=92| range? /// }}} {{{id=93| range(4) /// [0, 1, 2, 3] }}} {{{id=94| range(1, 5) /// [1, 2, 3, 4] }}} {{{id=95| range(1, 11, 2) /// [1, 3, 5, 7, 9] }}} {{{id=96| range(10, 0, -1) /// [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] }}} {{{id=97| for i in range(4): print i, i*i /// 0 01 12 43 9 }}}

You can use the continue keyword to immediately go to the next item in the loop:

{{{id=98| for i in range(10): if i % 2 == 0: continue print i /// 13579 }}}

If you want to break out of the loop, use the break keyword:

{{{id=99| for i in range(10): if i % 2 == 0: continue if i == 7: break print i /// 135 }}}

If you need to keep track of both the position in the list and its value, one (not so elegant) way would be to do the following:

{{{id=100| l = ['a', 'b', 'c'] for i in range(len(l)): print i, l[i] /// }}}

It's cleaner to use enumerate which provides the index as well as the value:

{{{id=101| l = ['a', 'b', 'c'] for i, letter in enumerate(l): print i, letter /// }}}

You could make something similary to the enumerate function by using zip to zip two lists together:

{{{id=102| l = ['a', 'b', 'c'] for i, letter in zip(range(len(l)), l): print i, letter /// }}}

For loops work using Python's iterator protocol.  This allows all sorts of different objects to be looped over.  For example,

{{{id=103| for i in GF(5): print i, i*i /// 0 01 12 43 44 1 }}}

How does it work?

{{{id=104| it = iter(GF(5)); it /// }}} {{{id=105| it.next() /// 0 }}} {{{id=106| it.next() /// 1 }}} {{{id=107| it.next() /// 2 }}} {{{id=108| it.next() /// 3 }}} {{{id=109| it.next() /// 4 }}} {{{id=110| it.next() /// Traceback (most recent call last): StopIteration }}}

..skip

{{{id=111| R = GF(5) R.__iter__?? /// }}}

yield provides a very convient way to produce iterators.  We'll see more about it in a bit.

Exercices

For each of the following sets, compute the list of its elements and their sum. Use two different ways, if possible: with a loop and using lists comprehension:

1. n premiers termes de la série harmonique

System Message: WARNING/2 (tutorial-programming-python.rst, line 1268)

Enumerated list ends without a blank line; unexpected unindent.

System Message: ERROR/3 (tutorial-programming-python.rst, line 1268)

Unknown directive type "math".

.. math:: \sum_{ i=1} ^n \frac{ 1} { i} 

1. les entiers impair entre 1 et n;
2. les n premiers entiers impairs;
3. les entiers entre 1 et n et qui ne sont divisibles ni par 2 ni par 3 ni par 5;
4. les n premiers entiers qui ne sont divisibles ni par 2 ni par 3 ni par 5.

Functions

Functions are defined using the def statement, and values are returned using the return keyword:

{{{id=112| def f(x): return x*x /// }}} {{{id=113| f(2) /// 4 }}} {{{id=114| def fib(n): if n <= 1: return 1 else: return fib(n-1) + fib(n-2) /// }}} {{{id=115| [fib(i) for i in range(10)] /// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] }}}

Functions are first class objects like any other.  For example, they can be passed in as arguments to other functions:

.. link

{{{id=116| f /// }}} {{{id=117| def compose(f, x, n): for i in range(n): x = f(x) return x /// }}} {{{id=118| compose(f, 2, 3) /// 256 }}} {{{id=119| def add_one(x): return x + 1 /// }}} {{{id=120| compose(add_one, 2, 3) /// 5 }}}

You can give default values for arguments in functions:

{{{id=121| def add_n(x, n=1): return x + n /// }}} {{{id=122| add_n(4) /// 5 }}} {{{id=123| add_n(4, n=100) /// 104 }}} {{{id=124| add_n(4, 1000) /// 1004 }}}

You can return multiple things from a function:

{{{id=125| def g(x): return x, x*x /// }}} {{{id=126| g(2) /// (2, 4) }}} {{{id=127| type(g) /// }}} {{{id=128| a,b = g(100) /// }}} {{{id=129| a /// 100 }}} {{{id=130| b /// 10000 }}}

You can also take variable number of arguments and keyword arguments in a function:

{{{id=131| def h(*args, **kwds): print type(args), args print type(kwds), kwds /// }}} {{{id=132| h(1,2,3,n=4) /// (1, 2, 3) {'n': 4} }}}

Let's use the yield instruction to make an generator for the Fibonacci numbers up to n:

{{{id=133| def fib_gen(n): if n < 1: return a = b = 1 yield b while b < n: yield b a, b = b, b+a /// }}} {{{id=134| for i in fib_gen(50): print i /// 112358132134 }}}

Exercices

1. Write a function is_even returning True if n is even and False otherwise.
2. Write a function every_other which takes a list l and returns a list containing every other element of l
3. Write a function computing the n-th Fibonacci number. Try to improve performance.