In case you have not noticed, I have not worked on the exercises from chapter 5 to chapter 7 yet. My goal is to speed up with the theory and then practice for a week. I will organize a session of “Code til you drop” with exercises from Chapter 5 to 8. I hope you can join. This will help us consolidate our knowledge before we tackle Chapter 9’s case study.
The title of chapter 7 is Iteration.
Here is a quick definition in order for us to start:
Iteration is the act of repeating a process with the aim of approaching a desired goal, target or result. Each repetition of the process is also called an “iteration”, and the results of one iteration are used as the starting point for the next iteration.
[…] With multiple assignment it is especially important to distinguish between an assignment operation [ “=” ] and a statement of equality [ “==” ].
Here is the definition that Professor Downey provides for multiple assignment.
Multiple assignment : Making more than one assignment to the same variable during the execution of a program [or code block]
7.2 Updating variables
Do you remember when we first saw this assignment statement “x = x + 1″ in Chapter 3? Today we learn that it is called an assignment update, since the new value of the variable x depends on the old value of x.
>>> x = x + 1 # Read, “get the current value of x, add one (1), and then update x with the new value”.
In order to update a variable, you must initialize the variable first. Otherwise, Python will not recognize the variable.
Python evaluates the right side before it assigns a value to x.
>>> x = 0 # Read, variable x gets the value of zero (0). This assignments is also considered as the initialization of variable x.
>>> x = x + 1 #”Updating a variable by adding one (1) is called an increment“.
>>> x = x 1 1 #”Updating a variable by subtracting one (1) is called an decrement“.
7.3 The while statement
Iteration : Repeated execution of a set of statements using either a recursive function call or a loop.
Python statements that make recursion easier are:
for statement : ” for i in range ( n ): “
while statement : ” while Boolean expression : “
Recursion versus For Loop versus While Loop
NOTE: I was looking for a way to improve the “countdown” function with a for loop, and I found inspiration in PythonicProse and Docs/Python.
Here is the flow of execution for the while loop:
Evaluate the condition, yielding True or False.
If the condition is false, exit the while statement and continue execution at the next statement.
If the condition is true, execute the body and loop back to step 1.
The loop’s body should aim to prove the condition false, so that the loop terminates. The body may do so by changing the value of one or more variables.
The objective is to avoid infinite loops.
Infinite loop : A loop in which terminating condition is never satisfied.
>>> def sequence (n):
… while n != 1:
… print n,
… if n%2 == 0: # n is even
… n = n/2
… else: #n is odd
… n = n * 3 + 1
…
>>> sequence (16)
16, 8, 4, 2
>>> sequence (3)
3, 10, 5, 16, 8, 4, 2
>>>
7.4 Break
The break statement can be used to exit a loop. To illustrate this notion, Professor Downey provides this example:
>>> while True:
… line = raw_input (‘> ‘)
… if line == ‘done’:
… break # The condition (if line == ‘done’) allows us to stop the condition affirmatively (“stop when this happens”).
… print line
…
> Hi there!
Hi there!
> done
>>>
The loop condition is True, which is always true, so the loop runs until it hits the break statement.
Each time through, it prompts the user with an angle bracket. If the user types done, the break statement exits the loop.
Exercise 7.1
Re-write the function print_n from Section 5.8 using iteration instead of recursion.
Exercise 7.1) Print_n using a while statement
I tried a couple of times to re-write the print_n function using a while statement. This helped me get it right :
First, it is useful to remind ourselves that the while statement will execute as long as the conditional is True.
So, we can include in the while-block whatever we want to do or display while the function is True.
In the print_n function from exercise 7.1, we want to print the variable s as long that the conditional ” n > 0 ” is True.
Second, a great quality of the while statement is that whenever the conditional is False it ends. Isn’t this great?
7.5 Square roots
Not long ago, I began reviewing some mathematical concepts in order to better tutor mathematics.
So, as we progress in learning the theory and logic behind Python, it amazes me to realize the closeness of mathematics and programming.
For instance, if we were to write a program that computes numerical results, we could use loops in order to start with approximate answers and iteratively improving it.
The book (Think Python) demonstrates this by working with the Newton’s method for computing a square root.
y = ( x + a/x )/2
Netwon’s Method
Professor Downey points out that we must be cautious to test float equality since “floating-point values are only approximately right”.
For instance, irrational numbers such as ∏ (pi) and √2, cannot be represented exactly with a float.
Rather than checking whether x and y are exactly equal, it is safer to use the built-in function abs to compute the absolute value, or magnitude, of the difference between them:
if abs (y – x) < epsilon:
break
Where epsilon has a value like 0.0000001 that determines how close is close enough.
Exercise 7.2) Encapsulate this loop in a function called square_root that takes a as a parameter, chooses a reasonable value of x, and returns an estimate of the square root of a.
In interactive mode (using Python in the Terminal), I wrote:
>>> a = 4.0
>>> x = 3.0
>>> while True:
… print x
… y = (x + a/x)/2
… if abs (y-x) < epsilon:
… break
… x = y
>>>
NOTE: I had the following error when I wrote the code block:
Traceback (most recent call last):
File “<stdin>”, line 4, in <module>
NameError: name ‘epsilon’ is not defined
>>>
So, I tried to write it in script mode (using Sublime Text and then executing it with the Terminal) and importing the math module.
Also, I looked for more information and I found an interesting/useful links:
Later, I realized that the variable named epsilon had to be set before hand. So, the code block can perfectly work in script or interactive mode.
7.6 Algorithms
So, here we are on the verge of understanding the algorithm notion. I asked countless times what was an algorithm. The best answer I got was that it was like a recipe. Fair enough. However, I could not understand why a simple recipe was so fascinating in the programming world.
Again, Professor Downey has done a tremendous work explaining the coveted notion. He starts his explanation by explaining what an algorithm is not. He provides the memorization of the multiplication tables as an example.
However, he points out an interesting fact. As kids, we developed shortcuts or tricks.
For example, to find the product of n and 9, you can write n – 1 as the first digit and 10 – n as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That’s an algorithm!
We can link this explanation with the recipe one. However, the later is crystal clear.
7.7 Debugging
The bigger the program is, the greater the possibility of making errors. Thus, we can say that a program’s length and the possibility of making an error are positively correlated.
Nevertheless, we can save time and many hair pulled by “debugging by bisection”. We can roughly cut the program in two and test one part and then the other. We can use the incremental development technique we learned in Chapter 6 and use the print statements to verify line by line (or small code blocks) if we want.
In this chapter, Allen B. Downey, the author draws attention to the fact that all the functions we have written so far are void (their return value is None).
It was a disappointing revelation. I thought I was already coding elaborate functions; specially with all the hair pulled on exercise 4.3.
By the way, last year I took an “Intro to Python” class with Girl Develop It . It was a hands on class. The Pythonista in charge, Bethany cleverly demonstrated how to jump into coding. Nevertheless, one of the notions I stumbled upon was the “return” concept. The idea of a “phantom” return that was somehow kept on hold without manifesting itself was a bit confusing.
Fortunately, Allen B. Downey, the author dedicates a whole chapter to fully explain return values and its ramifications.
6.1 Return values
[… ]in a fruitful function the return statement includes an expression. This statement means: “Return immediately from this function and use the following expression as a return value”
[It is important to note that] as soon as a return statement executes, the function terminates without executing any subsequent statements.
Code that appears after a return statement, or any other place the flow of execution can never reach, is called dead code.
None : A special value returned by functions that have no return statement or a return statement without an argument.
In order to excel as programmers, we should be able to foresee all possible paths that the program might take so it can hit a return statement.
In the example above, our function would be stuck if we asked for the absolute value of 0 (zero). We would get the return value None.
Exercise 6.1 Write a compare function that :
returns 1 if x > y,
returns 0 if x == y, and
returns -1 if x < y.
Exercise_6_1_compare
P.S. Have you ever wondered what is the difference between print statement and return statement in Python? For those who know the difference, this question might seem trivial. However, this is a perfectly pertinent question to ask.
When we use Python in interactive mode (Terminal running the Python interpreter), here are the scenarios:
Scenario no1 – Interactive mode
Code block #1: using the return statement
>>> def absolute_value(x):
… if x < 0:
… return -x
… if x > 0:
… return x
…
>>> absolute_value(3)
3
>>>
Scenario no2 – Interactive mode
Code block #2: using the print statement
>>> def absolute_value(x):
… if x < 0:
… print -x
… if x > 0:
… print x
…
>>> absolute_value(3)
3
>>>
Both code blocks give the exact same result. So, what is the difference? We can clearly see the difference using the script mode.
When we write code in script mode (with Sublime Text for instance), here are the scenarios:
Scenario no1 – Script mode
Code block #1: using the return statement
def absolute_value(x):
if x < 0:
return -x
if x > 0:
return x
absolute_value(3)
Since we wrote the code in Sublime Text (and saved it as a “abs_val.py” document for instance), we must verify the the outcome using the Terminal.
We travel in our terminal to find our “abs_val.py” document.
MacBook-Air-xxxx:Desktop xxxx$ python abs_val.py
The outcome will be … humm, nothing. Nothing appears on our screen.
If this is the first time it happens to you, you might say: “My code block did not work!”.
The good news is that it DID work. On the bright side, your program worked and the function evaluated abs_val(3). However, we did not ask our code block to print anything. Although the computation was correctly performed, nothing was demonstrated in the terminal.
Scenario no2 – Script mode
Code block #2: using the print statement
def absolute_value(x):
if x < 0:
print -x
if x > 0:
print x
absolute_value(3)
Again, we travel in our terminal to find our “abs_val.py” document.
MacBook-Air-xxxx:Desktop xxxx$ python abs_val.py
This time, we will see:
3
Which is the answer of abs_val(3).
To recapitulate, on the one hand, the return statement will execute the function and return the value without printing it (if you are in script mode). On the other hand, the print statement will print the return value you obtained from executing your function.
Does this help?
If you can explain it better, let me know as well.
6.2 Incremental development
As we write more elaborate programs, incremental development can be a way to tackle daunting programming challenges.
The goal of incremental development is to avoid long debugging sessions by adding and testing only a small amount of code at a time.
In order to demonstrate the reasoning behind incremental development, let us create a function capable of calculating the distance of two points.
Step 1 : If we follow George Polya’s method, the first step is to understand the problem or just the equation we are trying to translate into coding.
So, the Pythagorean theorem states that the hypotenuse (c) to the power of two (2) is equal to the sum of the square of side a and the square of side b.
c² = a² + b²
Pythagoream_Theorem
distance = ( ( x2 – x1 )2 + ( y2 – y1 )2 )1/2
NOTE: If you want to know how far the Pythagorean theorem can take you, I recommend to read Why Does E=mc2?: And Why Should We Care? written by Dr. Brian Cox and Professor Jeff Forshaw.
At this step we can establish the input (the parameters) and the output (that it the return value).
Parameters: two points
m = ( x1 , y1 ) n = ( x2 , y2 )
Return value: the distance from point m to point n
Step 2 : Elaborate a plan (according to Polya’s problem solving strategy).
The plan is to use incremental development in order to build the code block that calculates the distance of two points (m and n).
Step 3 : The third step is to carry out the plan:
Incremental plan – step (i): Start with a working program and make small incremental changes.
Verify that the function is syntactically correct.
>>> def distance (x1, y1, x2, y2):
… return 0.0
…
>>> distance (1, 2, 4, 6) #By using simple arguments, we can test the function easily.
0.0
>>>
Incremental plan – step (ii): Use temporary variables to hold intermediate values so you can display and check them.
Find the differences.
>>> def distance (x1, y1, x2, y2):
… dx = x2 – x1
… dy = y2 – y1
… print ‘dx is ‘, dx
… print ‘dy is ‘, dy
… return 0.0
…
>>> distance (1, 2, 4, 6)
dx is 3
dy is 4
0.0
>>>
[At this stage we know that] the function is getting the right arguments and performing the first computation correctly.
Incremental plan – step (iii): Use temporary variables to hold intermediate values so you can display and check them.
Compute the sum of the squares dx and dy :
Incremental plan – step (iv): Compute the square root of dsquared in order to find the distance between point m and n.
>>> import math #If you want to use the built-in function “sqrt” from Python, you must import the math module first.
>>> def distance (x1, y1, x2, y2):
… dx = x2 – x1
… dy = y2 – y1
… dsquared = dx**2 + dy**2
… result = math.sqrt(dsquared)
… return result
…
>>> distance (1, 2, 4, 6)
5.0
>>>
NOTE: The “print” statements we wrote in step (ii) and (iii) are useful for debugging. If the function is working, we can condense the code block by removing them.
Scaffolding : Code that is used during program development but it not part of the final version.
NYC scaffolding
Step 4 : Once the program is working, you might want to remove some of the scaffolding or consolidate multiple statements into compound expressions. The goal is to balance conciseness and easily comprehension of the code.
George Polya suggests to answer this question: How could it be better?
Exercise 6.2
This function is the exact same as the function “distance (x1, y1, x2, y2)”.
6.3 Composition
Composition : is the ability to call one function from within another.
Circle (xc, yc)
Step 1) Find the radius of the circle (which is the distance between two points).
In order to link the distance function and the area function, remember that the radius is our distance formula.
>>> def circle_area (xc, yc, xp, yp):
… radius = distance (xc, yc, xp, yp) #Consider the variable “radius” as a temporary variable
… result = area (radius) #Consider the variable “result” as a temporary variable
… return result
…
>>> circle_area (1, 2, 4, 6)
78.53981633974483
>>>
“How could it be better?”
If we want to answer the question, we can make our code block more concise by composing the function calls as follows:
Boolean functions are often used in conditional statements.
Exercise 6.3 Write a function is_between (x, y, z) that returns True if x ≤ y ≤ z or False otherwise.
>>> def is_between (x, y, z):
… return x <= y <= z
…
>>> is_between (1, 3, 9)
True
>>> is_between (3, 7, 4)
False
>>>
6.5 More recursion
Here is an exiting announcement from the author, Allen B. Downey:
We have only covered a small subset of Python, but you might be interested to know that this subset is a complete programming language, which means that anything that can be computed can be expressed in this language. Any program ever written could be rewritten using only the language features you have learned so far (actually, you would need a few commands to control devices like the keyboard, mouse, disks, etc., but that’s all).
The statement above was proven by Alan Turing. The author of the book (Think Python), Professor Downey recommends to read Michael Sipser’s book Introduction to the Theory of Computation to learn more about this computer science pioneer.
Who is Alan Turing?
Alan Mathison Turing (23 June 1912 – 7 June 1954) was a British mathematician, logician, cryptanalyst and computer scientist. He was influential in the development of computer science, giving a formalisation of the concepts of “algorithm” and “computation” with the Turing machine, which can be considered a model of a general purpose computer. Turing is widely considered to be the father of the theoretical computer science and artificial intelligence. Source: http://en.wikipedia.org/wiki/Alan_Turing
Moreover, the concepts learned that we have learned so far can be gauged with a few recursively defined mathematical functions.
A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is not very useful.
At this point, we are ready to apply the concepts we have learned so far to recursively mathematical functions.
A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is not very useful.
Professor Downey mentioned the word vorpal. I looked for the definition in Wikipedia just to realized that I was even more puzzled after I read it. Let us just stick to the definition provided by Professor Downey.
vorpal : An adjective used to described something that is vorpal.
Factorial function
0! = 1n! = n (n – 1)!
For instance:
Factorial function
If you can write a recursive definition of something, you can usually write a Python program to evaluate it.
Let us recall Polya’s first step to problem solving (or if we extrapolate, the first step into writing a programing function):
Step 1) Understand the problem (or the function you wish to write).
Understand how a factorial function works.
Decide what the parameters should be: A factorial takes an integer.
Decide how the result should look like: If the argument happens to be 0, the our function must return 1.
Step 2) Make a plan
The factorial function looks very similar to the countdown function that we wrote in Chapter 5, section 8. We might just go back in order to find some inspiration for our plan.
Stack diagram 3!
Step 3) Carry out the plan
>>> def factorial (n):
… if n == 0:
… return 1
… else: # Otherwise, execute a recursive call to find the factorial of n – 1 and then multiply by n.
… recurse = factorial (n-1)
… result = n * recurse
… return result
…
>>> factorial (3)
6
>>>
Step 4) Look back at your work. How can it be better?
In the Fibonacci sequence of numbers, each number is the sum of the previous two numbers. Fibonacci began the sequence […] with 1,1, 2, etc. […]
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 Source: Wikipedia / Fibonnacci
If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if you assume that the two recursive calls work correctly, then it is clear that you get the right result by adding them together.
6.8 Checking types
The built-in function isinstance is introduced in this section. The function verifies the type of argument.
On section 6.5, we developed a function called factorial. Let us take another step further and check the type of the argument and make sure it is positive.
Factorial function improved
>>> factorial (‘banana’)
Factorial is only defined for integers.
>>> factorial (3.5)
Factorial is only defined for integers.
>>> factorial (-1)
Factorial is not defined for negative integers.
>>> factorial (8)
40320
>>>
This program demonstrates a pattern sometimes called a guardian. The first two conditionals act as guardians [(not isinstance) and (elif n < 0)] , protecting the code that follows from values that might cause an error.
The guardians make it possible to prove the correctness of the code.
6.9 Debugging
Playing Lego with coding allows us to work on very small pieces of code. This makes debugging sessions less burdensome as it provides “natural checkpoints” for debugging.
If a function is not working, Professor Downey considers three possibilities:
Arguments: Verify that the function is getting the correct arguments.
A precondition is violated.
“To rule out the first possibility [Arguments], you can add a print statement at the beginning of the function and display the values of the parameters (and maybe their types)”.
We can also write code to verify the preconditions explicitly: “Add a print statement before each return statement that displays the return value”.
Function: Verify that the function is syntactically correct. A postcondition is violated.
The Picking Number strategy to verify code blocks can be an option to check the function’s results.
“If the function seems to be working, look at the function call to make sure the return value is being used correctly (or used at all!)”
Return value: Verify that the return value is what you expect (type and form) or how the return value is being used.
Trace the flow of execution by adding print statements.
Temporary variables often render debugging easier easier.
Python Project 