Week 5: more functions, scope, stack diagrams

Announcements

Quiz 2 on Friday
Lab 4 due Saturday
- lab 4 is functions and while loops, but we tell you exactly how to write the functions (what the params are, what it does, what it returns)
- lab 5 will be more functions, but not as much guidance on each function
- lab 7 will be yours to write (you design the functions and the whole program)

Monday

We started by looking at the countletter.py program from last time:

def main():
    phrase = "we love computer science"
    letter = "e"
    result = countletter(letter,phrase)
    print("Number of %s's: %d" % (letter, result))

def countletter(ch,txt):
    """return number of ch in txt"""
    count = 0
    for char in txt:
        if char == ch:
            count += 1
    return count

main()

Some questions students had from last time: - how do letter and phrase get transfered to the countletter() function? - how does the result (the count variable) get back to main()? - should I name the arguments the same as the parameters? - can I use phrase in the countletter() function?

stack diagrams and scope

All good questions! And we’ll use stack diagrams to understand what’s going on and answer these questions.

Understanding stack diagrams helps you see how the computer works, and why python does what it does. It will also be very valuable in week 11 when we learn recursion (functions calling multiple copies of themselves).

A "stack" is just a data structure used by many programs. A stack is useful because it keeps track of where we are, and allows backtracking (e.g., hitting "undo" in your editor, or hitting the "back" button on your browser).

If you think of a stack of books or a stack of trays, you generally add items to the stack and remove items from the stack at the top end. This is different from a queue data structure (like a line at the bank or the grocery store) where items (people) are added at the back of the queue and removed (they checkout or are served) from the front of the queue.

So for your browser, say you visit espn.com, then swarthmore.edu, then cnn.com, and finally google.com. At this point, the broswer stack would look like this, with the current site on the top of the stack, and your history recorded in the rest of the stack:

google.com
cnn.com
swarthmore.edu
espn.com

If you now hit the "back" button, the browser would "pop" the stack and remove the top item (google.com) and go to whatever is next on the stack (cnn.com).

As functions are executed in our program, they are placed on the top of the stack. When the function executing is done, it is removed from the top of the stack and the function below resumes execution. This is how the computer keeps track of the program flow.

For example, if you have a main() function called first, and then main() calls another function, say func1(), and before func1() returns it calls another function, say func2(), then at this point "the stack" would look like this:

func2
func1
main

In addition to just showing what functions are on the stack, we will also include their variables and what data they refer to.

Here is a stack diagram for the countletter.py program above, where I have stopped at the end of the count() function, just before it returns to main():

In the above diagram, the "stack" is on the left, with two functions currently on the stack, and the one on top is the function currently executing (i.e., main() has paused, and is waiting for countletter() to finish and return).

In each stack frame, for each function, we list the variables that are active, with arrows that point to the data they refer to. This data, shown off to the right, is technically stored in a different area of the computer’s memory (this whole diagram is a simplified view of the memory of the computer, as the program is executing).

So main() has just two variables: phrase and letter. The arrows show what values are currently stored in these variables.

The countletter() function has three variables: ch, txt, and count. Currently ch points to the same data as letter. This is how arguments and parameters pass data from main() to a function. Also, txt points to the same string as phrase.

The count variable initially stores a zero, but as the computer works through the function, step by step, it is updated each time another "e" is found in the txt string. This is shown by the crossed-out values, with the final value being 5. So at the end of the countletter function, the value that will be returned back to main (count) is 5.

So the rules for drawing the stack are as follows:

put the first function called (usually main()) on the stack
inside the stack frame, show any variables that are assigned, with arrows pointing to their values (off to the right)
if another function is called, make a new stack frame for that function on top of the stack
again, inside that frame, show any parameters and local variables, with arrows pointing to their initial values
work through each function, step-by-step, updating any variables and their data

Usually, on quizzes, we will ask you to stop updating the stack diagram before any functions finish and return. For completeness, if a function did finish and return, we would remove it (and all it’s variables) from the top of the stack. Any return value would usually be assigned back to a variable in the calling function. For example, in the above program, back in main(), the result variable would be assigned the value 5, since count is returned from the countletter() function.

mutable objects in function

What about this program? Can you draw the stack for this one? And what does the print(data) line show, after the call to bounds() in main()?

def main():
  data = [2,37,300,127,-1]
  print(data)
  changed = bounds(data,0,255)
  print(data)
  print("Number changed: %d" % (changed))

def bounds(L,min,max):
  """check that all items in list are within min/max"""

  numchanged = 0

  for i in range(len(L)):
    if L[i] < min:
      L[i] = min
      numchanged += 1
    elif L[i] > max:
      L[i] = max
      numchanged += 1

  # after loop, return how many were changed
  return numchanged

main()

Wednesday

review function worksheet

Here’s the functionWorksheet.py program that we started as a worksheet on Monday. Can you predict the output of the whole program? Can you draw the stack up to where function2() is about to return?

# ------------------------------------------------------ #
def function1(L, X, S):
  X = 100
  L = list("WXYZ")
  S = "pony"
  # draw what stack looks like at this point, before function ends
# ------------------------------------------------------ #
def printline(ch):
  print(50*ch)
# ------------------------------------------------------ #
def function2(L, X, S):
  X = X + 1
  L[0] = "hello"
  L[2] = "goodbye"
  L[4] = "lists are mutable!"
  S = S + "pony"
  # draw what stack looks like at this point, before function ends
# ------------------------------------------------------ #
def function3(mystring):
  newstr = "**" + mystring + "**"
  return newstr
# ------------------------------------------------------ #
def main():

  L = list("ABCDE")
  X = 42
  S = "Swarthmore"
  function1(L, X, S)
  print("L: %s" % (L))
  print("X: %d" % (X))
  print("S: %s" % (S))

  result = printline("!")
  print(result)
  printline("!")

  function2(L, X, S)
  print("L: %s" % (L))
  print("X: %d" % (X))
  print("S: %s" % (S))

  printline("#")
  S = function3(S)
  print("S: %s" % (S))

# ------------------------------------------------------ #
main()

After you have studied the program, run it and make sure you understand the output!

Here are the main points from the above program:

in python, lists are mutable. This is why function2() is able to change some of the items in L, and those changes are seen back in main() (when we print(L))
scope refers to where in a program a variable is active or accessible. Variables (and the data they reference) in one function are local (ie, not global) to that function. If you need the data from one function in another function, you should pass the data from function to function using arguments and parameters, or return the data from the called function back to the calling function
in python, a function returns None if you don’t explicitly return something (which is why you see None from the print(result) line in main()

start the `mathquiz.py` program

Let’s write a program to present the user with a simple math quiz, testing their multiplication knowledge. Here’s a quick example:

$ python3 mathquiz.py

Welcome to MathQuiz v0.1!

What factor would you like to work on? 4
- - - - - - - - - - - - - -
4 x 6? 35
....Nope. 4 x 6 = 24
- - - - - - - - - - - - - -
4 x 4? 16
....Correct!
- - - - - - - - - - - - - -
4 x 10? 40
....Correct!
- - - - - - - - - - - - - -
4 x 2? 8
....Correct!
- - - - - - - - - - - - - -

You got 3 out of 4 correct. Good work!

Start with just these requirements:

ask for a factor
keep asking simple multiplication questions (factor times a random number from 1-12) until they get 3 in a row correct

If you have time: add a results(numprob, numcorrect) function that takes two arguments/parameters: the total number of problems asked and the total number they got correct. This function should output a status message based on the percent correct:

All correct: Super!
greater than 80% correct: Good work!
greater than 50% correct: Not bad…
less that 50% correct: Keep trying…

This function should also print the "You got X out of Y correct" message.

Friday

Quiz 2 for the first half of class
review mathquiz.py program (see jk_mathquiz.py program)
intro to objects: strings and lists

objects and methods

Both python strings and python lists are examples of objects. An object is just some data plus some methods (similar to functions) wrapped up together into one thing. We’ll learn more about objects as we go. For now we just want to learn the syntax of using them: object.method()

example

>>> course = "Introduction to Computer Science"
>>> course.count("o")
4
>>> course.count("z")
0
>>> course.isalpha()
False
>>> course.upper()
'INTRODUCTION TO COMPUTER SCIENCE'

>>> grades = [88,90,78,99,93]
>>> grades.sort()
>>> print(grades)
[78, 88, 90, 93, 99]
>>> grades.append(75)
>>> print(grades)
[78, 88, 90, 93, 99, 75]

explanation/notes

The string methods used above are:

count() — returns the number of occurrences of the given substring
isalpha() — returns True if all characters in the string are letters
upper() — returns an uppercase version of the string

There are many other str methods. In string objects, the data are the characters in the string.

The list methods used above are:

sort() — sorts the list in place
append() — adds the given argument to the end of the list

In list objects, the data are the items in the list.

`object.method()` syntax

Methods are always called with the dot syntax: object.method()

Again, methods are similar to functions, except they are tied to the type of object, and are called with this special syntax.

common string methods

Strings are objects in Python, and thus have methods that we can invoke on them. There are a lot of methods in the str library for creating new string objects from existing string objects and for testing properties of strings. Keep in mind that strings are immutable!

Here are a few str methods that may be particularly useful (run help(str) in the python interpreter to see the full set):

str method	result
upper()	return copy of str converted to uppercase
lower()	return copy of str converted to lowercase
isalpha()	return True if string is all alphabetic characters
isdigit()	return True if string is all digits
count(sub)	return number of occurrences of sub
index(sub)	return index of first occurrence of sub
strip()	strip off leading and trailing whitespace
split()	split into list of "words" (see below)

str method

result

upper()

return copy of str converted to uppercase

lower()

return copy of str converted to lowercase

isalpha()

return True if string is all alphabetic characters

isdigit()

return True if string is all digits

count(sub)

return number of occurrences of sub

index(sub)

return index of first occurrence of sub

strip()

strip off leading and trailing whitespace

split()

split into list of "words" (see below)

>>> S = "we LOVE cs"
>>> S.upper()
'WE LOVE CS'
>>> S.lower()
'we love cs'
>>> S.isalpha()
False
>>> S.isdigit()
False
>>> S.count(" ")
2
>>> S.index("L")
3
>>> S.split()
['we', 'LOVE', 'cs']
>>> S = "   we love cs    "
>>> len(S)
17
>>> S = S.strip()
>>> len(S)
10
>>> print(S)
we love cs

common list methods

Lists are also objects in Python, and thus have methods that we can invoke on them. Here are a few that may be particularly useful (run help(list) in the python interpreter to see the full set):

list method	result
append(item)	add item to end of list
insert(index,item)	insert item at index
extend(L1)	add list L1 to original list
sort()	sort the list
reverse()	reverse the list
count(item)	return number of occurrences of item in list
index(item)	return index of first occurrence of item
pop(index)	remove and return item at index

list method

result

append(item)

add item to end of list

insert(index,item)

insert item at index

extend(L1)

add list L1 to original list

sort()

sort the list

reverse()

reverse the list

count(item)

return number of occurrences of item in list

index(item)

return index of first occurrence of item

pop(index)

remove and return item at index

>>> L = list("ABCDEFG")
>>> print(L)
['A', 'B', 'C', 'D', 'E', 'F', 'G']
>>> L.append("X")
>>> print(L)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'X']
>>> L.extend(["Y","Z"])
>>> print(L)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'X', 'Y', 'Z']
>>> L.reverse()
>>> print(L)
['Z', 'Y', 'X', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
>>> L.sort()
>>> print(L)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'X', 'Y', 'Z']
>>> L.count("E")
1
>>> L.index("E")
4
>>> L.pop(4)
'E'
>>> print(L)
['A', 'B', 'C', 'D', 'F', 'G', 'X', 'Y', 'Z']
>>> L.insert(1,"hello")
>>> print(L)
['A', 'hello', 'B', 'C', 'D', 'F', 'G', 'X', 'Y', 'Z']

To see the full documentation for both the str and list classes:

$ python3
>>> help(str)
>>> help(list)