CS 3723
  Programming Languages  
  5. Python Debugging   

5.1. Fibonacci Numbers: The Fibonacci numbers are the sequence:

    f[0]=0, f[1]=1, f[2]=1, f[3]=2, f[4]=3, f[5]=5, f[6]=8, f[7]=13, f[8]=21, ...

where the sequence starts with 0 and 1, and each subsequent entry is the sum of the two previous ones. Here are four programs to calculate this sequence: a Java, a C, and a Python program, all array based, along with another Python program that is more like a linked list based version. Each program calculates and stores the first 17 Fibonacci numbers in an array (C or Java) or in a list (Python).

Fibonacci Sequence
Python: List as an Array Version Python: List as a Linked List 
# fib1.py: like an array
import sys # for sys.stdout.write
n = 17
f = [None]*n # empty array, size n
f[0] = 0
f[1] = 1
for i in range(2,n):
    f[i] = f[i-1] + f[i-2]

for i in range(0,n):
    sys.stdout.write(str(f[i]) + " ")
sys.stdout.write("\n")

# fib2.py: like a linked list
import sys # for sys.stdout.write
n = 17
f = [] # empty list
f.append(0)
f.append(1)
for dum in range(2,n): # dum unused
    # f[-1]=last elt,f[-2]=next to last
    f.append(f[-1] + f[-2])
for a in f:
    sys.stdout.write(str(a) + " ")
sys.stdout.write("\n")
Java Array Version C Array Version
// Fib.java: Java array version
public class Fib { 
   public static void main(String[] args){
      int n = 17;
      int[] f = new int[n];
      f[0] = 0; f[1] = 1;
      for (int i = 2; i < n; i++)
         f[i] = f[i-1] + f[i-2];
      for (int i = 0; i < f.length; i++)
         System.out.print(f[i] + " ");
      System.out.println();
   }
}
 
// fib.c: C array version
#include <stdio.h>
#define N 17
int main() {
   int f[N];
   f[0] = 0; f[1] = 1;
   int i;
   for (i = 2; i < N; i++)
      f[i] = f[i-1] + f[i-2];
   for (i = 0; i < N; i++)
      printf("%i ", f[i]);
   printf("\n");
}
Common Output
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

5.2. A Second Approach: Here's an idea for a simpler approach: Use single variables f, g, and h, that will always hold three successive Fibonacci numbers. Also (of course) we will always have h == f + g. So we start f and g equal to the first two Fibonacci numbers: 0 and 1. Then start a loop with the assignment h = f + g. Finally put the new value of h into g, and the value of g into f, and go back around the loop. For example, if f and g are 5 and 8, the h will be 13. Then we put the 13 into g and the 8 into f, so that f and g will be 8 and 13. Then go back around the loop. Here's a Python program that does this (Hey! This should work.):

Simple Python Version: fib.py
# fib.py: simple approach
import sys # for sys.stdout.write
f = 0
g = 1
sys.stdout.write("0 1 ")
while f < 1000:
    h = f + g
    sys.stdout.write(str(h) + " ")
    g = h
    f = g
sys.stdout.write("\n")



Output


% pythn fib.py
0 1 1 2 4 8 16 32 64 128 256 512 1024



But Rats!  Look at the output.  It's not right, but successive
powers of 2.  This is a standard debug problem: the program ran
but the output is wrong.  What to do? There are several approaches.
In a simple program like this one, temporary output
statements are bound to chase down the problem.  But there are
several higher-tech Python approaches.  One uses a special editor,
IDLE, which is available on many Python environments, but not on
ours. (Wikipedia says that IDLE has problems and is not
liked by everyone.)
Instead we'll try a debugger built into Python itself.



5.3. The
pdb Debugger: Put an "import pdb" and the
statement "pdb.set_trace()" at the beginning of the
program, as shown below.
This will stop the program and allow many of the standard
debugger things: single-step through the program, set
breakpoints, examine variables, etc. The example below shows
only a few of many options. [See pdb docs
for information about pdb from the Python home page.
Commands used by the debugger are at the end of the previous
link or here: 
Debugger Commands.]


In particular here, lines 3-4 set up the program to use the debugger
starting with the first statement on line 5.  Then line 19 starts the
program.  Each line is presented after "->" as it is ready
to be executed (but before execution).  Then the debugger prints
the prompt "(Pdb)" and waits for a command.  "s" means execute
the given line and go on to the next.  (Lines are presented
in the order of execution, not in the order in the program.)
"p f,g" means to print the values of those variables before
executing the line.  Line 33 is prepared to print the value of
h, but before that, line 34 asks to print values
for f, g, and h, which are printed in
red on line 35.  Then the "s" on line 36 says to execute lines 33,
which prints the "1" on line 37.  Finally line 38 shows the
next line ready for execution.





Python with
Debugger Enabled: fibpdb.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


# fibpdb.py: Python with debugger
import sys # for sys.stdout.write
import pdb # for debugging
pdb.set_trace() # start tracing
f = 0
g = 1
sys.stdout.write("0 1 ")
# value of f,g in blue below
while f < 1000:
    h = f + g
    # value of f,g,h in red below
    sys.stdout.write(str(h) + " ")
    g = h
    f = g
    # value of f,g,h in blue below
sys.stdout.write("\n")

Now start the interactive session:
% python fibpdb.py
-> f = 0
(Pdb) s
-> g = 1
(Pdb) s
-> sys.stdout.write("0 1 ")
(Pdb) s
0 1 
-> while f < 1000:
(Pdb) p f,g
(0, 1)
(Pdb) s
-> h = f + g
(Pdb) s
-> sys.stdout.write(str(h) + " ")
(Pdb) p f,g,h
(0, 1, 1)
(Pdb) s
1 
-> g = h
(Pdb) s
-> f = g
(Pdb) s

-> while f < 1000:
(Pdb) p f,g,h
(1, 1, 1)
(Pdb) s
-> h = f + g
(Pdb) s
-> sys.stdout.write(str(h) + " ")
(Pdb) p f,g,h
(1, 1, 2)
(Pdb) s
2 
-> g = h
(Pdb) s
-> f = g
(Pdb) s
-> while f < 1000:
(Pdb) p f,g,h
(2, 2, 2)
(Pdb) s
-> h = f + g
(Pdb) s
-> sys.stdout.write(str(h) + " ")
(Pdb) p f,g,h
(2, 2, 4)
(Pdb) s
4 
-> g = h
(Pdb) s
-> f = g
(Pdb) s
-> while f < 1000:
(Pdb) p f,g,h
(4, 4, 4)
(Pdb) s
-> h = f + g
(Pdb) s
-> sys.stdout.write(str(h) + " ")
(Pdb) p f,g,h
(4, 4, 8)
...



Try to figure out what the bug is before going on with this page.


 
 
 
 

 
 
 
 

 
 
 
 

 
 
 
 




5.4. The
Bug: This is a standard bug that I have often
introduced by mistake.
Suppose you have values in variables f, g, and h.
If you want to move a new value of h
into g, and the old value of g into f,
you must be aware that the above method is wrong:






Wrong!
Correct!
Also in Python


    g = h    
    f = g

    f = g    
    g = h

    f, g = g, h    
        (or)
    g, f = h, g



The code on the left moves the new value of h into g
as desired, but then
that same new value of h is propagated on into f,
instead of putting the old value of g into f.
On the right is Python's multiple assignment statement in
two versions (either one works here).  It gets the effect of
doing both assignments "at the same time".


Python's fancy multiple assignment statement
gives an even simpler version of the Fibonacci program:





Simplest Python
   Version (?): fibs.py


# fibs.py: short version
import sys # for sys.stdout.write
f, g = 0, 1
sys.stdout.write("0 1 ")
while f < 500:
    f, g = g, f+g
    sys.stdout.write(str(g) + " ")
sys.stdout.write("\n")



Output


% python fibs.py
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987





(Revision date: 2015-01-02.
Please use ISO 8601,
the International Standard.)