FUNCTIONS
4.1 Function Definition: Syntax and Semantics
4.2 Function Execution
4.3 Recursion
4.4 Creating Python Modules
4.5 Program Design Using Functions – Example: The Game of Nim
4.6 Summary
In this chapter
There is a large and useful set of functions built into Python. These are sometimes simply there for the using, like print and input, and sometimes are part of a module that must be imported, like random. However, as large as this collection of functions is, it is impossible that it will include everything that every programmer needs. At some point there will be a need to create a function that does something new, and Python should permit this.
Why would a programmer want to create a function of their own? It is partly out of convenience; if some section of code can be invoked as a function instead of being repeated many times, then there will be less typing involved. It is also to support more correct programs: a small code unit like a function can be very thoroughly tested and nearly guaranteed to be correct. And it is also to support reuse of working code: once a function is tested, it can be placed in a collection of code (module) and used again and again instead of being rewritten many times.
A function is really just some code that has a name, and can be executed simply by invoking that name. It usually represents some task that has to be done fairly frequently, but that’s not a requirement. Some functions are invoked (or called) only once. In this context a function is a way to break up a long piece of code into many shorter pieces which, as has been pointed out, are easier to test and maintain.
A function should also have one single task, or at least one main task. That task should be represented in the function name. A function named maximum should have the task of locating the maximum of something; a function named cosine should calculate the cosine of an angle. If a function is named wilma it tells another programmer who is reading the code nothing about the what the program is doing, and if a function named cosine computes the square root of a number then it is not just uninformative but misleading. Never mind that the Python language does not insist that names be informative; there is a social compact between programmers that says that you should be as clear as possible about what your code is doing.
The fact that many functions return a value has been skipped over, but it is a key part of the function construct. The code within the function has a purpose, and often that purpose is concentrated in the return value. However it works, and whatever the code looks like, the purpose of the cosine function is to return a single value that is the mathematical cosine of a given angle. The nature of the function is encapsulated in that value. There are some functions that do not explicitly return a value; such a function might be called to print an error message or draw a graphical object in a window. Even if it is not specifically declared in the definition, all functions return something. If not defined, then it returns a value called None.
Enough exposition—how can functions be declared and used in Python?
4.1 FUNCTION DEFINITION: SYNTAX AND SEMANTICS
Unlike in the cases of if statements or for statements, a function definition does not involve the word “function.” As an example of a simple definition in Python, imagine a program that needs a function to print twenty “#” characters on a line. It could be defined as:
def pound20 ():
for i in range(0,20):
print ("#", end="")
The word def is known to Python and always begins the definition of a function. This is followed by the name of the function, in this case pound20 because the function prints 20 pound characters (also known as a hash characters or octothorpe). Then comes the list of parameters, which can be thought of as a tuple of variable names. In this case the tuple is empty, meaning that nothing is passed to the function. Finally comes the “:” character that defines a new suite that comprises the code belonging to the function. From here on the code is indented one more level, and when the indentation reverts to the original level the function definition is complete.
Calling this function is a matter of using its name as a statement or in an expression, being careful to always include the tuple of parameters. Even when the tuple is empty, it helps distinguish a function from a variable. A call to this function would be:
pound20 ()
and the result would be that 20 “#” characters would be printed on one line of the output console.
A function can be given or passed one or more values that will determine the result of the function. A function cosine, for example, would be passed an angle, and that angle would be used to compute the cosine. Each call to cosine passing a different value can yield a different result. In the case of the function that prints pound characters, it might be useful to pass it the number of pound characters to print. It should not be called pound20 anymore because it does not always print 20 characters. It will be called poundn this time:
def poundn (ncharacters):
for i in range(0,ncharacters):
print ("#", end="")
The variable ncharacters that is given in parentheses after the function name is called a parameter or an argument, and indicates the name by which the function will refer to the value passed to it. This name is known only inside of the function, and while it can be modified within the function, this modification will not have any bearing on anything outside. The call to poundn must now include a value to be passed to the function:
poundn (3)
When this call is performed, the code within poundn begins executing, and the value of ncharacters is 3, the value that was passed. It prints 3 characters and returns. A subsequent call to poundn could be passed a different number, perhaps 8, and then ncharacters would take on the value 8 and the function would print 8 characters. It will print as many characters as requested through the parameter.
4.1.1 Problem: Use poundn to Draw a Histogram
In Chapter 2, a simple histogram was created from some print statements and loops. The same code was repeated many times, one for each histogram bar. As it happens the character used to draw the histogram bars was the pound character, so the function poundn could be used as a basis for a histogram program. As a reminder, here is the output that is desired:
Earnings for WidgetCorp for 2016
Dollars for each quarter
==============================
Q1: ######## 190000
Q2: ################ 340000
Q3: ########################################## 873000
Q4: #################### 439833
Each pound character represents $20000, and there are four variables that hold the profit for each of the four quarters: q1, q2, q3, and q4. Given these
criteria, a solution using poundn would call the function four times, once for each quarter:
print ("Earnings for WidgetCorp for 2016")
print (" Dollars for each quarter ")
print (" ===============================")
q1 = 190000 # The dollar amounts for profits
q2 = 340000 # in each of the four quarters of 2016
q3 = 873000
q4 = 439833
print ("Q1: ", end="")
poundn(int(q1/20000)) # Raw dollar amount is divided by
# 20000
# to yield the number of characters.
print (" ", q1)
print ("Q2: ", end="")
poundn (int(q2/20000))
print (" ", q2)
print ("Q3: ", end="")
poundn (int(q3/20000))
print (" ", q3)
print ("Q4: ", end="")
poundn (int(q4/20000))
print (" ", q4)
Each profit value must be scaled by dividing by 20000, just as happened before. In this case the resulting value is passed to poundn indicating the number of “#” ’s to draw.
4.1.2 Problem: Generalize the Histogram Code for Other Years
Any company will need to do financial reports every year at least. Hiring a programmer to do this task on a computer is not a reasonable thing to do, because computers can be made to do this job in a very general way. For example, given that each year will have four quarters and each quarter will have a profit, why not store these data as a list? Each year will have one list containing four items, and the name of the variable could initially be related to the year:
profit2016 = [190000, 340000, 873000, 439833]
The profit for the first quarter is profit2016[0], the second quarter is profit2016[1], and so on. Using this variable means passing one of the elements of the list to poundn instead of a simple variable, but that is fine, it’s a legal expression. So drawing the characters for the first quarter would be done with the following code:
poundn(int(profit2016[0]/20000))
Now consider what else gets printed. To print everything for the first quarter the code was:
print ("Q1: ", end="")
poundn(int(profit2016[0]/20000))
print (" ", q1)
This means that the label on the left, “Q1,” the parameters to poundn, and the actual value of the profit are needed. All of these are available, and can be provided within a simple loop. Assuming that the loop variable i runs from 0 to 3, the code within that loop that duplicates the previous example can be constructed one line at a time. In each iteration the quarter is i+1 because i starts at 0; convert that to a string and build the label “Q1 : ” from it:
print (Q1: ", end="")
print ("Q"+str(i+1)+": ", end="")
This is probably the trickiest part. The label string is constructed from the letter “Q,” a number between 1 and 4 indicating the quarter, and “:” for the terminal string. They are simply concatenated together in the print statement.
Now call poundn as before:
poundn(int(profit2016[i]/20000))
poundn(int(profit2016[i]/20000))
finally, print the raw dollar value on the right:
print (" ", q1)
print (" ", profit2016[i])
So, using this plan the entire histogram can be drawn using only four statements:
for i in range(0,4):
print ("Q"+str(i+1)+": ", end="")
poundn(int(profit2016[i]/20000))
print (" ", profit2016[i])
That’s pretty brief, readable, and general. Still, there’s another step. Since this will be done every year, why not create a function that takes the data and the year as parameters, and do the whole job? It shall be called pqhistogram:
def pqhistogram (profit, year):
print ("Earnings for WidgetCorp for "+str(year))
print (" Dollars for each quarter ")
print (" ==============================")
for i in range(0,4):
print ("Q"+str(i+1)+": ", end="")
poundn(int(profit[i]/20000))
print (" ", profit[i])
The function pqhistogram produces the same output as did the original program, and does so more generally and concisely. This function also brings to light two new ideas. One is that it is possible to pass more than one parameter to a function. The second is that it is possible to call a function from within another function; in this case poundn is called from inside of pqhistogram. The call is made after defining the list that contains the profit values:
profit2016 = [190000, 340000, 873000, 439833]
pqhistogram (profit2016, 2016)
It is important to note that the parameters are positional; that is, the first value passed will correspond to the first name in the parameter list, and the second to the second. This is the default for functions with any number of parameters.
|
Note |
A def statement is not a declaration. Such things are foreign to Python. A def statement executes, and it “creates” a new function each time it is executed. This is an advanced topic, and will be handled later. |
4.2 FUNCTION EXECUTION
When a function is called, the first statement of that function starts to execute, and it continues statement by statement through the code until the last statement of that function or until it returns prematurely. When that last statement executes, then execution will continue from the place where it was called. As a function can be called from many places, Python has to remember where the function was called so that it can return. Parameters can be expressions or variables, and normally differ each time the function is called. Functions can also access variables defined elsewhere.
Most importantly, and a factor that has not been dealt with yet, is that functions return values.
4.2.1 Returning a Value
All functions return a value, and as such can be treated within expressions as if they were variables having that value. So, assuming the existence of a cosine function, it could be used in an expression in the usual ways. For example:
x = cosine(x)*r
if cosine(x) < 0.5:
print (cosine(x)*cosine(x))
In these cases the value returned by the function is used by the code to calculate a further value or to create output. The expression “cosine(x)” resolves to a value of some Python type. The most common purpose of a function is to calculate a value, which is then returned to the calling part of the program and can possibly be used in a further calculation. But how does a function get its value? In a return statement.
The return statement assigns a value and a type to the object returned by the function. It also stops executing the function and resumes execution at the location where the function was called. A simple example would be to return a single value, such as an integer or floating point number:
return 0
returns the value 0 from a function. The return value could be an expression:
return x*x + y*y
A function has only one return value, but it can be of any type, so it could be a list or tuple that contains multiple components:
return (2,3,5,7,11)
return ["fluorine","chlorine","bromine","iodine","astatine"]
Expressions can include function calls, so a return value can be defined in this way as well; for example:
return cosine(x)
One of the simplest functions that can be used as an example is one that calculates the square of its parameter. It nonetheless illustrates some interesting things:
def square (x):
return x*x
The print statement:
print (square(12))
will print:
144
Interestingly, the statement:
print(square(12.0))
results in:
144.0
The same function returns an integer in one case and a float in the other. Why? Because the function returns the result of an expression involving its parameter, which in one case was an integer and in the other was real. This implies that a function has no fixed type, and can return any type at all. Indeed, the same function can have return statements that return an integer, a float, a string, and a list independent of type of the parameter passed:
def test (x): # Return one of four types depending on x
if x<1:
return 1
if x<2:
return 2.0
if x<3:
return "3"
return [1,2,3,4]
print (test(0))
print (test(1))
print (test(2))
print (test(3))
The output:
1
2.0
3
[1, 2, 3, 4]
Problem: Write a Function to Calculate the Square Root of its
Parameter
Two thousand years ago the Babylonians had a way to calculate the square root of a number. They understood the definition of a square root: that if y*y = x then y is the square root of x. They figured out that if y was an overestimate to the true value of the square root of x, then x/y would be an underestimate. In that case, a better guess would be to average those two values: the next guess would be y1 = (y + x/y)/2. The guess after that would be y2 = (y1+x/y1)/2, and so on. At any point in the calculation the error (difference between the correct answer and the estimate) can be found by squaring the guess yi and subtracting x from it, knowing that yi*yi is supposed to equal x.
The function will therefore start by guessing what the square root might be. It cannot be 0 because then x/y would be undefined. x is a good guess. Then construct a loop based on the expression y2 = (y1+x/y1)/2, or more generally yi+1 = (yi+x/yi)/2 for iteration i. At first, run this loop a fixed number of times, perhaps 20. Here is the function that results:
def root (x): # Compute the square root of x
y = x # First guess: too big, probably
for i in range(1, 20): # Iterate20 times
y = (y + x/y)/2.0 # Average the prior guess and
# x/y
return y # Return the last guess
This correctly computes the square root of 2 to 15 decimal places. This is probably more than is necessary, meaning that the loop is executing more times than it needs to. In fact, changing the 20 iterations to only 6 still gives 15 correct places. This is exceptional accuracy: if the distance between the Earth and the Sun were known this accurately it would be within 0.006 inches of the correct value. The Babylonians seem to have been very clever.
What’s the square root of 10000? If the number of iterations is kept at 6, then the answer is a very poor one indeed: 323.1. Why? Some numbers (large ones) need more iterations than others. To guarantee that a good estimate of the square root is returned, an estimate of the error should be used. When the error is small enough, then the value will be good enough. The error will be x-yi*yi. The function should not loop a fixed number of times, but instead should repeat until the error is less than, say, 0.0000001. This function will be named roote, where the “e” is for “error.”
# Computer the square root of X to 7 decimal places
def roote (x):
y = x # y is supposed to be the square root
# of x, so
e = abs(x-y*y) # the error is x – y*y
while e > 0.0000001: # repeat while the error is bigger
# than 0.0000001
y = (y + x/y)/2.0 # New estimate for square root
e = abs(x-y*y) New error value
return y
This function will return the square root of any positive value of x to within 7 decimal places. It should check for negative values, though.
4.2.2 Parameters
A parameter can be either a name, meaning that it is a Python variable (object) of some kind, or an expression, meaning it has a value but no permanence in that it can’t be accessed later on—it has no name. Both are passed to a function as an object reference. The expression is evaluated before being given to the function, and its type does not matter in so far as Python will always know what it is; its value is assigned a name when it is passed. Consider, for example, the function square in the following context:
...
pi = 3.14159
r = 2.54
c = square (2*pi*r)
print ("Circumference is ", c)
The assignments to pi and r are performed, and when the call to square
occurs, the expression 2*pi*r is evaluated first. Its value is assigned to a temporary
variable, which is passed as the parameter to square. Inside the function this parameter is named x, and the function calculates x squared and returns it as a value. It is as if the following code executes:
pi = 3.14159
r = 2.54
# call square(2*pi*r)
parameter1 = 2*pi*r # set the parameter value
x = parameter1 # First parameter is named x inside
# SQUARE
returnvalue = x*x # Code within SQUARE, return x*x
c = returnvalue # assign result of function
# call to c
print ("Circumference is ", c)
This is not how a function is implemented, but it shows how the parameter is effectively passed; a copy is made of the parameters and those are passed. If the expression 2*pi*r was changed to a simple variable, then the internal location of that variable would be passed.
Passing more structured objects works the same way but can behave differently. If a list is passed to a function then the list itself cannot be modified, but the contents of the list can be. The list is assigned another name, but it is the same list. To be clear, consider a simple function that edits a list by adding a new
element to the end:
def addend (arg):
arg.append("End")
z = ["Start", "Add", "Multiply"]
print (1, z)
addend(z)
print (1, z)
The list associated with the variable z is changed by this function call. It now ends with the string “End.” Output from this is:
1 [ꞌStartꞌ, ꞌAddꞌ, ꞌMultiplyꞌ]
2 [ꞌStartꞌ, ꞌAddꞌ, ꞌMultiplyꞌ, ꞌEndꞌ]
Why is this? Because the name z refers to a thing that consists of many other parts. The name z is used to access them, and the function can’t modify the value of z itself. It can modify what z indicates; that is, the components. Think of it, if it makes it simpler, as a level of indirection. A book can be exchanged between two people. The receiver writes a note in it and gives it back. It’s the same book, but the contents are now different.
A small modification to addend() illustrates some confusing behavior. Instead of using append to add “End” to the list, use the concatenation operator “+”:
def addend (arg):
arg = arg + ["End"]
z = ["Start", "Add", "Multiply"]
print (1, z)
addend(z)
print (2, z)
Now the output is:
1 [ꞌStartꞌ, ꞌAddꞌ, ꞌMultiplyꞌ]
2 [ꞌStartꞌ, ꞌAddꞌ, ꞌMultiplyꞌ]
The component “End” is not a part of the list z anymore. It was made a component inside of the function, but it’s not present after the function returns. This is because the statement:
arg = arg + ["End"]
actually creates a new list with “End” as the final component, and then assigns that new list as a value to arg. This represents an attempt to change the value that was passed, which can’t happen: changing the value of arg will not change the value of the passed variable z. So, within the function arg is a new list with “End” as the final component. Outside, the list z has not changed.
The way that Python passes parameters is the subject of a lot of discussion on Internet blogs and lists. There are many names given for the method used, and while the technique is understood, it does differ from the way parameters are passed in other languages and is confusing to people who learned another language like Java or C before Python. The thing to remember is that the actual value of the thing (an object reference) being passed can’t be assigned a new value inside the function, but the things that it references or points to can be modified.
Multiple parameters are passed by position; the first parameter passed is given to the first one listed in the function declaration, the second one passed is given to the second one listed in the declaration, and so on. They are all passed in the same manner, though, as object references.
4.2.3 Default Parameters
It is possible to specify a value for a parameter in the instance that it is not given one by the caller. That may not seem to make sense, but the implication is that it will sometimes be passed explicitly and sometimes not. When debugging code it is common to embed print statements in specific places to show that the program has reached that point. Sometimes it is important to print out a variable or value there, other times it is just to show that the program got to that statement safely. Consider a function named gothere:
def gothere (count, value):
print ("Got Here: ",count, " value is ", value)
then throughout the program, calls to gothere would be sprinkled with a different value for count every time; the value of count indicates the statement that has been reached. This is a way of instrumenting the program, and can be very useful for finding errors. So the code being debugged may look like:
year = 2015 # The code below is not especially
# meaningful
a = year % 19 # and is an example only.
gothere(1, 0)
b = year // 100
c = year % 100
gothere (2, 0)
d = (19 * a + b - b // 4 - ((b - (b + 8) // 25 + 1)
// 3) + 15) % 30
e = (32 + 2 * (b % 4) + 2 * (c // 4) - d - (c % 4)) % 7
f = d + e - 7 * ((a + 11 * d + 22 * e) // 451) + 114
gothere (3, f)
month = f // 31
day = f % 31 + 1
gothere(4, day)
return date(year, month, day)
Output is:
Got Here: 1 value is 0
Got Here: 2 value is 0
Got Here: 3 value is 128
Got Here: 4 value is 5
2015 4 5
The program reaches each of the four checkpoints and prints a proper message. The first two calls to gothere did not need to print a value, only the count number. The second parameter could be given a default value, perhaps None, and then it would not have to be passed. The definition of the function would now be:
def gothere (count, value=None):
if value:
print ("Got Here: ",count, " value is ", value)
else:
print (Got Here: ", count)
and the output this time is:
Got Here: 1
Got Here: 2
Got Here: 3 value is 128
Got Here: 4 value is 5
2015 4 5
The assignment within the parameter list gives the name value a special property. It has a default value. If the parameter is not passed, then it takes that value; otherwise, it behaves normally. This also means that gothere can be called with one or two parameters, which can be very handy. It is important to note that the parameters that are given a default value must be defined after the ones that are not. That’s because otherwise it would not be clear what was being passed. Consider the (illegal) definition:
def wrong (a=1, b, c=12):
…
Now call wrong with two parameters:
wrong (2,5)
What parameters are being passed? Is it a and b? Is it a and c? It is impossible to tell. A legal definition would be:
def right (b, a=1, c=12)
This function can be called as:
right (19)
in which case b=19, a=1, and c=12. It can be called as:
right (19, 20)
in which case b=19, a=19, and c=12. It can be called as:
right (19, 19, 19)
in which case b=19, a=19, and c=19. But how can it be called passing b and c but not a? Like this:
right (19, c=19)
In this case a has been allowed to default. The only way to pass c without also passing a is to give its name explicitly so that the call is not ambiguous.
4.2.4 None
Mistakes happen when writing code. They are unavoidable, and much time is spent getting rid of them. One common kind of mistake is to forget to assign a return value when one is needed. This is especially likely when there are multiple points in the function where a return can occur. In many programming languages this will be caught as an error, but in Python it is not. Instead, a function that is not explicitly assigned a return value will return a special value called None.
None has its own type (NoneType), and is used to indicate something that has no defined value or the absence of a value. It can be explicitly assigned to variables, printed, returned from a function, and tested. Testing for this value can be done using:
if x == None:
or by:
if x is None:
4.2.5 Example: The Game of Sticks
This is a relatively simple combinatorial game that involves removing sticks or chips from a pile. There are two players, and the game begins with a pile of
21 sticks. The first player begins by removing 1, 2, or 3 sticks from the pile.
Then the next player removes some sticks, again 1, 2, or 3 of them. Players alternate in this way. The player who removes the last stick wins the game; in other words, if you can’t move, you lose.
Functions are useful in the implementation of this game because both players do similar things. The action connected with making a move, displaying the current position, and so on are the same for the human player and the computer opponent. The current status or state of the game is simply a number, the number of sticks remaining in the pile. When that number is zero, then the game is over, and the loser is whatever player is supposed to move next. The code for a pair of moves, one from the human and one from the computer, might be coded in Python as follows:
displayState(val) # Show the game board
userMove = getMove() # Ask user for their move
val = val – userMove # Make the move
print ("You took ", userMove, " sticks leaving ", val)
if gameOver(val):
print("You win!")
else:
move = makeComputerMove (val) # Calculate the
# computerꞌs move
print ("Computer took ", move, " sticks leaving ", val)
if gameOver(val):
print("Computer wins!")
The current state of the game is displayed first, and then the human player is asked for their move. The move is simply the number of sticks to remove. When the move has been made, if there are no sticks left then the human wins. Otherwise, the computer calculates and makes a move; again, if no sticks remain then the game is over, in this case the computer being the winner. This entire section of code needs to be repeated until the game is over, of course.
There are four functions that must be written for this version: displayState(), getMove(), gameOver(), and makeComputerMove().
The function displayState() prints the current situation in the game. Specifically, it prints one “O” character for each stick still in the pile, and does so in rows of 6. At the beginning of the game this function would print:
O O O O O O
O O O O O O
O O O O O O
O O O
which is 21 sticks. The code is:
def displayState(val):
k = val # K represents the number of sticks not
# printed
while k > 0: # So long as some are not printed …
if k >=6: # If there is a whole row, print it.
print ("O O O O O O ", end="")
k = k – 6 # Six fewer sticks are unprinted
else:
for j in range(0,k): # Print the remainder
print ("O ", end="")
k = 0 # None remain
print ("")
This should be obvious. Also note that the function is named for what it does. It does only one thing; it modifies no values outside of the function, and it serves a purpose that is needed multiple times. These are all good properties of a function.
The function getMove() will print a prompt to the user/player asking for the number of sticks they wish to remove and reads that value from the keyboard, returning it as the function value. Again, this function is named for what it does and performs a single, simple task. One possibility for the code is:
def getMove ():
n = int(input ("Your move: Take away how many? "))
while n<=0 or n>3:
print ("Sorry, you must take 1, 2, or 3 sticks.")
n = int(input ("Your move: Take away how many? "))
return n
The function gameOver() is trivial, but lends structure to the program. All it does is test to see whether the value of val, the game state variable, is zero. It leaves open the idea that there may be other end of game indicators that could be tested here.
def gameOver (state):
if state == 0:
return True
return False
Finally, the most complicated function, getComputerMove(), can be attempted. Naturally a good game presents a challenge to the player, and so the computer should win the game it if can. It should not play randomly if that is possible. In the case of this particular game, the winning strategy is easy to code. The player to make the final move wins, so if there are 1, 2, or 3 sticks left at the end, the computer would take them all and win. Forcing the human player to have 4 sticks makes this happen. The same is true if the computer can give the human player (i.e., leave the game in the state of having) 8, 12, or 16 sticks. This can be demonstrated by playing the game with actual sticks. So, if the human moves first (as it does in this implementation) the computer tries to leave the game in a state where there are 16, 12, 8, or 4 sticks left after its move. The code could be:
def getComputerMove (val):
n = val % 4
if n<=0:
return 1
else:
return n
There are a couple of details needed to finish this game properly that are left as an exercise.
4.2.6 Scope
A variable that is defined (first used) in the main program is called a global variable, and can be accessed by all functions if they ask for it. A variable that is used in a function can be accessed by that function, and is not available in the main program. It’s called a local variable. This scheme is called scoping: the locations in a program where a variable can be accessed is called its scope. It’s all pretty clear unless a global variable has the same name as a local one, in which case the question is: “what value is represented by this name?” If a variable named “x” is global and a function also declares a variable having the same name, this is called aliasing, and it can be a problem.
In Python, a variable is assumed to be local unless the programmer specifically says it is global. This is done in a statement; for example:
global a, b, c
tells Python that the variables named a, b, and c are global variables, and are defined outside of the function. This means that after the function has completed execution, those variables can still be accessed by the main program and by any other functions that declare them to be global.
Global variables are thought by some programmers to be a bad thing, but in fact they can be quite useful and can assist in the generality of the functions that are a part of the program. A global variable should represent something that is, in fact, global, something that should be known to the whole program. For instance, if the program is one that plays checkers or chess, then the board can be global. There is only one board, and it is essential to the whole program. The same applies to any program that has a central set of data that many of the functions need to modify.
An example of central data is game state in a video game. In the Sticks game program for example, the function getComputerMove() takes a parameter—the game state. There is only one game state, and although for some games it can involve many values, in this case there is only one value: the number of sticks remaining. The function can be rewritten to use the game state variable val as a global in the following way:
def getComputerMove ():
global val
n = val % 4
if n<=0:
return 1
else:
return n
Similarly, the function that determines whether the game is over could use val as a global variable. On the other hand it would be poor stylistic form to have getMove() use a global for the user’s move. The name does imply that the function will get a move, and so that value should be returned as an explicit function return value.
If a variable is named as global, then that name cannot be used in the function as a local variable as well. It would be impossible to access it, and it would be confusing. It is a common programming error to forget to declare a variable as global. When this happens the variable is a new one local to the function, and starts out with a value of 0. Thus no syntax error is detected, but the calculation will almost certainly be incorrect. It might be a good idea to identify global variables in their name. For example, place the string “_g” at the end of the names of all globals. The game state above would be named val_g, for example. This would be a reminder to declare them properly within functions.
Other kinds of data that could be kept globally would include lists of names, environment or configuration variables, complex data structures that represent a single underlying process, and other programming objects that are referred to as singletons in software engineering. In Python, because they have to be explicitly named in a declaration, there is a constant reminder of the variable’s scope.
4.2.7 Variable Parameter Lists
The print() function is interesting because it seems to be able to accept any number of parameters and deal with them. The statement:
print(i)
prints the value of the variable i, and
print (i,j,k)
prints the value of all three variables i, j, and k. Is this some sort of special thing reserved for print() because Python knows about it? Nope. Any function can do this. Consider a function:
fprint ( "format string", variable list)
where the format string can contain the characters “f” or “i” in any combination. Each instance of a letter should correspond to a variable passed to the function in the variable list, and it will be printed as a floating point if the corresponding character in the format string is “f” and as an integer if it is “i.” The call:
fprint("fi", 12, 13)
will print the values 12 and 13 as a float and an integer respectively. How can this be written as a Python function?
The function would start out with the following definition:
def fprint (fstring, *vlist)
The expression *vlist represents a set of positional parameters, any number of them. This is preceded by a specific parameter fstring, which will be the
format string. A simple test of this would be to just print the variables in the list to see if it works:
def fprint (fstring, *vlist)
for v in vlist:
print v
When called as fprint(“”, 12, 13, 14, 15) this prints:
12
13
14
15
It removes some of the magic to point out that what is going on is that the list of variables after the * character is turned into a tuple, which is passed as the parameter, so the *vlist actually counts as a single parameter with many components. No magic.
To finish the original function, what has to be done is to peel characters off of the front of the format string, match them against a variable, and print the result as the format character dictates. So it is the same loop as above, but also an index into the format string increases each time through and is used to indicate the format. It is also important that the number of format items equals the number of variables:
def fprint (s, *vlist):
i = 0
if len(s) != len(vlist): # Format string and
# variable list agree?
print ("There must be the same number of variables as format items.")
return
for v in vlist: # For each variable
if s[i] == "f": # Is the corresponding
# format ꞌfꞌ?
fv = float(v) # Yes. Make it a float
print (fv, " ", end="") # … and print it
elif s[i] == "i": # Is the corresponding
# format ꞌiꞌ?
iv = int(v) # Yes. Make it an
# integer
print(iv, " ", end="") # … and print it
else:
print ("?", end="") # Donꞌt know what this
# is. Print it
i = i + 1
All of the known positional parameters must come before the variable list; otherwise the end of the variable list can’t be determined. There is a second complication, that being the existence of named parameters. Those are indicated by a parameter such as **nlist. The two “*” characters indicate a list of named variables. This is properly a more advanced topic.
4.2.8 Variables as Functions
Because Python is effectively untyped and variables can represent any kind of thing at all, a variable can be made to refer to a function; not the function name itself, which always refers to a specific function, but a variable that can be made to refer to any function. Consider the following functions, each of which does one trivial thing:
def print0():
print ("Zero")
def print1():
print ("One")
def print2():
print ("Two")
def print3():
print("Three")
Now make a variable reference one of these functions by means of an
assignment statement:
printNum = print1 # Note that there is no parameter list
# given
The variable printNum now represents a function, and when invoked, the function it represents will be invoked. So:
printNum()
will result in the output:
One
Why did the statement printNum = print1 not result in the function print1 being called? Because the parameter list was absent. The statement:
printNum = print1()
results in a call to print1 at that moment, and the value of the variable printNum will be the return value of the function. This is the essential syntactic difference: print1 is a function value, and print1() is a call to the function. To emphasize this point, here is some code that would allow the English name of a number between 1 and 3 to be printed:
if a == 1:
printNum = print1 # Assign the function print1 to
# printNum
elif a == 2:
printNum = print2 # Assign the function print2 to
# printNum
else:
printNum = print3 # Assign the function print3 to
# printNum
. . .
printNum() # Call the function represented by
# printNum
There are more subtle uses in this case. Consider this use of a list:
a = 1
printList = [print0, print1, print2, print3]
printNum = printList[a]
printNum()
will result in the output:
One
The final iteration of this is to call the function directly from the list:
printList[1]()
This works because printList[1] is a function, and a function call is a function followed by (). Seems overly complicated, doesn’t it? It is rarely used.
For those with an interest or need for mathematics, consider a function that computes the derivative or integral of another function. Passing the function to be differentiated or integrated as a parameter may be the best way to proceed in these cases.
Example: Find the Maximum Value of a Function
Maximizing a function can have important consequences in real life. The function may represent how much money will be made by manufacturing various objects, how many patients can get through an emergency ward in an hour, or how much food will be grown with particular crops. If the function is well behaved then there are many mathematically sound ways to find a maximum or minimum value, but if a function is harder to deal with, then less analytical methods may have to be used. This problem proposes a search for the best pair of parameters to a problem that could be solved using a method called linear programming.
The problem goes like this:
A calculator company produces a scientific calculator and a graphing calculator. Long-term projections indicate an expected demand of at least 100 scientific and 80 graphing calculators each day. Because of limitations on production capacity, no more than 200 scientific and 170 graphing calculators can be made daily. To satisfy a shipping contract, a total of at least 200 calculators much be shipped each day.
If each scientific calculator sold results in a $2 loss, but each graphing calculator produces a $5 profit, how many of each type should be made daily to maximize net profits?
Let s be the number of scientific calculators manufactured and g be the number of graphing calculators. From the problem statement:
100 <= s <= 200
80 <= g <= 170
Also:
s + g > 200, or g > 200 - s
Finally, the profit, which is to be maximized, is:
P = –2s + 5g
First, code the profit as a function:
def profit (s, g):
return -2*s + 5*g
A search through the range of possibilities will run through all possible values of s and all possible values of g; that is, s from 100 to 200 and g from 80 to 170. The function will be evaluated at each point and the maximum will be remembered:
# Range for s is x0 .. x1
# Range for g is y0 .. y1
# s+g must be >= sum
def searchmax (f, x0, y0, x1, y1, sum):
pmax = -1.0e12
ps = -100
pg = -100
for s in range (x0, x1+1): # For all possible s
for g in range (y0, y1+1): # For all possible g
if s+g >= sum: # Condition is ok?
p = f (s, g) # Calculate the profit.
if p>=pmax: # Best so far?
pmax = p # Yes.
ps = s # Save it and
pg = g # the parameters
return ( (ps, pg) )
Finally, the call that does the optimization calls the search function passing the profit function as a parameter:
c = searchmax (profit, 100, 80, 200, 170, 200)
print (c)
The answer found is the tuple (100, 170), or s=100 and g = 170, which agrees with the correct answer as found by other methods. This is only one example of the value of being able to pass functions as parameters. Most of the code that does this is mathematical, but may accomplish practical tasks like optimizing performance, drawing graphs and charts, and simulating real-world events.
4.2.9 Functions as Return Values
Just as any value, including a function, can be stored in a variable, any value, including a function, can be returned by a function. If a function that prints an English name of a number is desired, it could be returned by a function:
def print0():
print ("Zero")
def print1():
print ("One")
def print2():
print ("Two")
def print3():
print("Three")
def getPrintFun (a): # Return a function to print a
# numeric value 0..3
if a == 0:
return print0 # Return the function print0 as
# the result
elif a == 1:
return print1 # Return the function print1 as
# the result
elif a == 2:
return print2 # Return the function print2 as
# the result
else:
return print3 # Return the function print3 as
# the result
Calling this function and assigning it to a variable means returning a function that can print a numerical value:
printNum = getPrintFun(2) # Assign a function to printNum
and then:
printNum() # Call the function represented by printNum
results in the output:
Two
The function printFun returns, as a value, the function to be called to print that particular number. Returning the name of the function returns something that can be called.
Why would any of these seemingly odd aspects of Python be useful? Allowing a general case, permitting the most liberal interpretation of the language, would permit unanticipated applications, of course. And the ability to use a function as a variable value and a return result are a natural consequence of Python having no specific type connected with a variable at compilation time. There are many specific reasons to use functions in this way, on the other hand. Imagine a function that plots a graph. Being able to pass this function another function to be plotted is surely the most general way to accomplish its task.
4.3 RECURSION
Recursion refers to a way of defining things and a programming technique, not a language feature. Something that is recursive is defined at least partly in terms of itself. This seems impossible at first, but consider the case of a grocery list (not a Python list) of items such as:
milk, bread, coffee, sugar, peanut butter, cheese, jam
Each element in the list can be called an item, and represents something to be purchased at a grocery store. The smallest list is one having only a single element:
milk
Thus, a list can be simply an item. What else can it be? It appears to be a bunch of items separated by commas. One way to describe this is to say it can be an item followed by a comma followed by a list. The complete definition is, presuming that the symbol -> means “can be defined as”:
list -> item # list can be defined as an item
list -> item, list # list can be defined as an item, a comma, and a list
In this way the list milk is defined as a list by the first rule. The list milk, bread is a list because it is an item (milk) followed by a comma followed by a list (bread). It is plain that a list is defined here in terms of itself, or at least in terms of a previous partial definition of itself.
When talking about functions, a function is recursive if it contains within it a call to itself. This is normally done only when the thing that it is attempting to accomplish has a definition that is recursive. Recursion as a programming technique is an attempt to make the solution simpler. If it does not, then it is inappropriate to use recursion. A problem some beginning programmers have with the ideas of a recursive function is that it appears that it does not terminate. Of course, it is essential that a function does return, and a program that never ends is almost always in error. The problem really is how to make certain that a chain of function calls terminates eventually.
The following function will never return once called:
def recur1 (i):
recur1(i+1)
print (i)
It will not result in any output, either. Why not? Because the first thing it does is call itself, and always does so. When it does, the next thing is does is call itself again, and then again, and so on. The following function, on the other hand, will terminate:
def recur2 (i):
if i>0:
recur2(i-1)
print (i)
When called it checks its parameter i. If that parameter is greater than zero, then it calls itself with a smaller value of i, meaning that eventually i will become smaller than 0 and the chain of calls will stop. What will be printed? The first call to recur2 that does not end up calling itself is when i==0, so the first thing printed will be 0. Then the function returns to the previous recursive call, which had to be where i == 1. The second thing printed will be 1. And so on until it returns to the original call to the function with the original value of i, at which point it prints i. This is a trivial example of a recursive function, but illustrates how to exit from the chain of calls: there must be a condition that defines the recursion. When that condition fails, the recursion ceases.
Each call to the function can be thought of as an instance of that function, and it will create all of the local variables that are declared within it. Each instance has its own copy of these, including its parameters, and each call returns to the caller as occurs with any other function call. So, when the recursive call to recur2() returns, the next thing to be done will be (in this case) to print the parameter value. A call to recur2() passing the parameter 4 will result in the following instances of that function being created:
By tracing through the statements that are executed in this way, it can be seen that the recursion does end, and the output or result can be verified.
One important use of recursion is in reducing a problem into smaller parts, each of which has a simpler solution than does the whole problem. An example of this is searching a list for an item. If names = [Adams, Alira, Attenbourough, …] is a Python list of names in alphabetical order, answer the question: “Does the name Parker appear in this list?” Of course there is a built-in function that will do this, but this example is a pedagogical moment, and anyway perhaps the built-in function is slower than the solution that will be devised here.
The function will return True or False when passed a list and a name. The obvious way to solve the problem is to iterate through the list, looking at all of the elements until the name being searched for is either found or it is not possible to find it anymore (i.e., the current name in the list is larger than the target name). Another, less obvious way to conduct the search is to divide the list in half, and only search the half that has the target name in it. Consider the following names in the list:
… Broadbent Butterworth Cait Cara Carling Devers Dillan Eberly Foxworthy …
The name in the middle of this list is Carling. If the name being searched for is lexicographically smaller than Carling, then it must appear in the first half; otherwise it must appear in the second half. That is, if it is there at all. A recursive example of an implementation of this is:
# Search the list for the given name, recursively.
def searchr (name, nameList):
n = len(nameList) # How many elements in this
# list?
m = n/2
if name < nameList[m]: # target name is in the first
# half
return searchr (name, nameList[0:m]) # Search the
# first half
elif name > nameList[m]: # target must be in the
# second half
return searchr (name, nameList[m:n] # Search the
# second half
else:
return True
If the name is in the list, this works fine. One way to think of this is that the function searchr() will take a string and a list as parameters and find the name in the list if it’s there. The way it works is not clear from outside the function (without being able to see the source) and should not matter. SO: if the target is to be found in the first half of the list, for example, then call searchr() with the first half of the list.
searchr (name, nameList[0:m])
The fact that the call is recursive is not really the concern of the programmer, but is the concern of the person who created the Python system. Now, how can the problem of a name not being in the list be solved?
When the name is not in the list, the program will continue until there is but one item in the list. If that item is not the target, then it is not to be found. So, if n=1 (only one item in the list) and nameList[0] is not equal to the target, then the target is not to be found in the list and the return value should be False. The final program will therefore be:
def searchr (name, nameList):
n = len(nameList) # How many elements in this list?
m = int(n/2)
if n==1 and nameList[0]!=name: # End of the recursive
# calls
return False # Itꞌs not in this
# list.
if name < nameList[m]: # target name is in the first
# half
return searchr (name, nameList[0:m]) # Search the
# first half
elif name > nameList[m]: # target must be in the
# second half
return searchr (name, nameList[m:n]) # Search the
# second half
else:
return True
Many algorithms have fundamentally recursive implementations, meaning that the effective solution in code involves a recursive function call. Many standard examples in beginning programming are not properly implemented recursively. Commonly encountered samples with a recursive solution include the factorial, which has a recursive definition but is not best implemented in that manner, and any other basically linear technique (linear search, counting, min/max finding) that does not do a reasonable subdivision. Testing the first component, for example, and then recursively looking at the remaining elements is a poor way to use recursion. It would be much better to use a loop. Here’s an example: find the maximum value in a given list. The non-recursive method
(reasonable) would be:
def max (myList):
max = myList [0]
for i in range(1, len(myList)):
if myList[i] > max:
max = myList[i]
return max
This is an effective way to find the largest value in a list, and is pretty easily understood by a programmer reading the code. Now here is a recursive solution:
def maxr (myList):
m1 = myList[0]
if len(myList)>1:
m2 = maxr (myList[1:])
else:
return m1
if m1 > m2:
return m1
else:
return m2
This function works by subdividing the list into two parts, as is often done with a recursive solution. The idea is to compare the first element in the list with the maximum of the remainder of the list to see which is bigger. For this particular problem this is not an obvious approach. It is less efficient and less obvious than the iterative version that preceded it. The use of recursion simplifies some problems, but it is not a universally applicable technique and should never be used to show off. Examples of very useful recursive functions will be examined in later chapters.
4.3.1 Avoiding Infinite Recursion
There is a limit to how many times a function can call itself without returning, because each call uses up some amount of memory, and memory is a finite resource. Usually when this happens a programming error has occurred and the function has slipped into an infinite recursion, in which it will continue to call itself without end. Recursion can be confusing to visualize and this sort of problem occurs frequently. How can it be avoided?
Programming the function correctly eliminates the problem, of course, but there are some basic rules that will avoid the problem at early stages. Assuming that global variables are not being referenced:
1. A function that begins with a call to itself is always infinitely recursive. The first thing the function does is call itself, and no matter what the parameters are it can never end.
2. Every recursive call within a function must have a condition upon which that call will be avoided. The function may return sometime before the call is made, or perhaps the call happens within an if statement, but there must be such a condition. If it exists it is expressible as a Boolean expression, and this should be placed in a comment near the recursive call. The call is suspect until this happens.
3. Avoid passing a function to itself. The call to a parameter hides the fact that recursion is taking place.
4. It is possible to have a global variable that is a count of the depth of recursion. The function will increment this count whenever a recursive call is made and decrease it just before returning. If the count ever gets larger than a reasonable estimate of the maximum depth, then the function could stop any more calls and back out, or an error message could be printed.
4.4 CREATING PYTHON MODULES
In some of the examples given so far there is a statement at the beginning that looks like “import name.” The implication is that there are some functions that are needed by the program that are provided elsewhere, possibly by the Python system itself or perhaps by some other software developer. The idea of writing functions that can be reused in a straightforward way is very important to the software development process. It means that no programmer is really alone; that code is available for doing things like generating random numbers or interfacing with the operating system or the Internet, and that it does not to be created each time. In addition, there is an assumption that a module works correctly. When a programmer builds a collection of code for their own use, it needs to be tested as thoroughly as possible, and from that time on it can be used in a package with confidence. If a program has errors in it, then look in the code for that program first and not in the modules. This makes debugging code faster.
What is a module? It is simply a function or collection of functions that reside in a file whose name ends in “.py.” Technically, all of the code developed so far qualifies as modules. Consider as an example the function from the previous section that finds the maximum value in a list. Save the functions max() and maxr() in a file named max.py. Now create a new Python program named usemax.py and place it in the same directory as max.py. If the two files are in the same directory, they can “see” each other in some sense.
Here is some code to place in the file usemax.py:
import max
d = [12,32,76,45,9,26,84,25,61, 66, 1,2]
print ("MAX is ", max.max(d), " MAXR is ", max.maxr(d))
if max.maxr(d) != max.max(d):
print ("*** NOT EQUAL ****")
This program is just a test of the two functions to make certain that they return the same value for the same list, the variable d. Note two things:
1. The statement import max occurs at the beginning of the program, meaning that the code inside this file is available to this program. Python will look inside of this file for function and variable names.
2. When the function max() or maxr() is called, the function name is preceded by the module name (max) and a period. This syntax informs the Python system that the name maxr() (for example) is found in the
module max and not elsewhere.
The first time that the module is loaded into the Python program the code in the module is executed. This allows any variable initializations to be performed. Henceforth that code is not executed again, and functions within the module can be called knowing that the initializations have been performed.
The module could reside in the same directory as the program that uses it, but does not have to. The Python system recognizes a set of directories and paths and modules can be placed in some of those locations as well, making it easier for other programs on the same computer to take advantage of them. On the computer used to create the examples in this book, the directory C:\Python34\Lib can be used to store modules, and they will be recognized by import statements.
Finally, if the syntax max.maxr(list) seems a bit cumbersome, then it is possible to import specific names from the module into the program. Consider the following rewrite of usemax.py:
from max import max, maxr
d = [12,32,76,45,9,26,84,25,61, 66, 1,2]
print ("MAX is ", max(d), " MAXR is ", maxr(d))
if maxr(d) != max(d):
print ("*** NOT EQUAL ****")
The statement from max import max, maxr instructs Python to recognize the names max and maxr as belonging to the module named max (i.e., as residing in the file named max.py). In that case the function can be called by simply referencing its name.
There would appear to be a name conflict with the package named max and the function named max, but in fact there is not. Indeed, it’s not uncommon to find this sort of naming relationship (example: random.random()). The module name max refers to a file name, max.py. The function name max refers to a function within that file.
4.5 PROGRAM DESIGN USING FUNCTIONS – EXAMPLE: THE GAME OF NIM
Nim is a game so old that its origins have been lost. It was likely invented in China, and is one of the oldest games known. It was also one of the first games to have a computer or electronic implementation and has been the frequent subject of assignments in computer programming classes. This program will implement the game and will play one side. It will serve as an example of how to design a computer program using functions and modularity—it is an example of a
top-down design.
The game starts with three rows of objects, such as sticks or coins, and there are a different number of objects in each row. In this version there are 9, 7, and 5 “sticks,” which are represented by “|” characters. A player may remove as many objects from one row as they choose, but they must remove at least one and must take them only from one row. Players take turns removing objects, and the player taking that final one is the winner.
Playing this game involves asking the user for two numbers: the row from which to remove sticks, and how many to remove. The human player will be prompted for the row, then the number. Then the computer will remove some sticks (take its turn) and print the new state.
A list named val contains the number of sticks in each row. Initially:
val = [5, 7, 9]
This is the game state, and is critical to the game as it defines what moves are possible. Also, when the state is [0,0,0] then the game is over.
When the user choses to remove N sticks from row M the action is:
val[M] = val[M] - N
Of course N and M must be tested to make certain that M is between 0 and 2, and M is as large as val[M]. M defines the row chosen to remove sticks from, and N is the number of sticks to remove. A move can therefore be defined as a list [row, sticks].
A program that uses functions should be built from the highest level of abstraction downwards. That is, the main program should be developed first, and should be expressed in terms of functions that do logical things, but that may not be designed or coded yet. So, the main program could look something like this:
val = [5, 7, 9] # the game state: 5, 7, and 9 sticks
done = False # Is the game over?
userMove = [-1, -1] # A move is a row and a number of
# sticks.
print ("The game of Nim.")
rules() # Print the rules for the game
while not done: # Run until the game is over
displayState(val) # Show the game board
prompt(userMove) # Ask user for their move
ok = legalMove (userMove, val) # Was the playerꞌs move
# OK?
while not ok:
print ("This move is not legal.")
displayState(val)
prompt(userMove) # Ask user for their move
ok = legalMove (userMove, val)
makeMove (userMove) # Make it
if gameOver(val):
print("You win!")
break;
print ("State after your move is ") # display it.
displayState(val)
This program is built using components (modules) that are not written yet, but that have a purpose that is defined by what the program needs. Those modules/functions are:
rules() - Print out the rules of the game
displayState(v) - Print the game state (how many sticks in each row)
prompt() - Ask the user for their move
legalMove(r, n) - is the move legal?
makeMove(r, n) - make this move
Using functions, the first thing that is needed is to display the game state. It prints the number of sticks in each of the three rows, and does so in a graphical way (i.e., rather than just displaying the numbers). Given the situation as described so far, the non-trivial such function is displayState(), which prints the current state of the game—how many sticks in each row. It will be passed a list representing the current state.
def displayState(val): # val is the list with
# the state
for j in range(0,3): # there are 3 rows;
# print each one
print (j+1, ": ", end="") # Print the row number
for i in range(0,val[j]): # val[j] is the current
# row
print ("| ",end="") # print a ꞌ|ꞌ for each
# stick
print("") # print an end of line
When called at the beginning of the game, here’s what the result of a call to this function would be:
1 : | | | | |
2 : | | | | | | |
3 : | | | | | | | | |
This function does a single task, uses a parameter to guide it and make it more general, and is named for what it does. These are signs of a good function. Note that the first row is labeled “1,” but is in fact element 0 of the list. It is common in user interfaces to adapt to the standard human numbering scheme that begins with 1 instead of 0. When the user enters a row number care must be taken to subtract 1 from it before using it as an index.
There is no required order for writing these functions, but the next one used in the program is prompt(). This will ask the user to input a row and then read a row number, then prompt the user to enter a number of sticks to remove and then read that value too. The two numbers will be placed into a list that was passed so that the values can be returned to the caller.
def prompt (move):
row = input ("Your move: which row? ") # Prompt for row &
# read it
sticks = input (" how many sticks?") # Prompt for
# sticks & read
# Convert row to integer and decrement to be from 0 to 2.
move[0] = int(row)-1 # Assign to the list[0]
move[1] = int(sticks) # Assign value to list[1]
This function again does a simple task, uses a parameter, and is named pretty appropriately.
Next is the question “Is this move legal”? A move is legal if the row is between 0 and 2 inclusive, and if the number of sticks in that row is greater than or equal to the number of sticks to be removed. The function returns True or False.
def legalMove(move, state):
row = move[0] # Which row was requested?
sticks = move[1] # How many sticks
if row<0 or row>2: # Legal number of rows?
return False # No
if sticks<=0 or sticks>val[row]: # Legal number of
# sticks?
return False # No
return True # Both were ok, so the move is OK.
Making a move involves decreasing the specified row by the specified number of sticks. This could have been done in legalMove() if it were thought to be OK to do multiple things in a function. Eventually that will be necessary, but for now a new function will be written, named makeMove(), that will actually implement a specified play in the game.
def makeMove(move, state):
row = move[0] # Subtract move[1] sticks from
sticks = move[1] # those that are in row move[0].
# Place the new number of sticks in the state list
state[row] = state[row]-sticks
There is a strategy that will permit a player to always win. It involves computing what amounts to a parity value and making a move to ensure that parity is maintained. Consider the initial state and the state after taking two sticks from row 1:
Row 1 = 5 = 0 1 0 1 row 1 = 3 = 0 0 1 1
Row 2 = 7 = 0 1 1 1 row 2 = 7 = 0 1 1 1
Row 3 = 9 = 1 0 0 1 row 3 = 9 = 1 0 0 1
Parity 1 0 1 1 1 1 0 1
The parity is determined by looking at each digit in the binary representation of the values. In each column (digit position) the parity bit for that column is 1 if the number of 1 bits in the column is odd and 0 if it is even. This can be calculated using the exclusive-OR operator, which is “^” in processing. The strategy in Nim is to make a move that makes the parity value 0. It turns out that this is always possible if parity is not 0; in the situation above, the computer might remove 5 sticks from row 3 giving the state:
row 1 = 3 = 0 0 1 1
row 2 = 7 = 0 1 1 1
row 3 = 4 = 0 1 0 0
Parity 0 0 0 0
This is what the sketch does after every move the player makes: it makes all possible moves, computing the parity after each one. When the one with zero parity is found it makes that move. The function eval() calculates the current parity value as val[0]^val[1]^val[2].
|
Note |
The computer always wins because the user always makes the first move. Alternating who moves first would make the gameplay fairer. |
4.5.1 The Development Process Exposed
In the introduction to the Nim program it was said that this was an example of top-down design. This means that the larger program, or the main program, is designed first. The question should be what are the steps involved in solving this problem? The answer to that question is written down in terms of functions that have not been written yet, but that have a known and required purpose within the solution. In the Nim game it is known that the user’s move will have to be read from the keyboard and that the current state of the game will have to be displayed, so those two functions can be presumed to be important to the solution when sketching the main program.
Once the high-level part of the program has been devised, it can be typed in and tested. The functions that are needed but are not yet written can be coded as stubs: functions that do not implement their task but that are present and prevent syntax errors. The first try at a solution of this sort does not, of course, solve the problem, but is simply a step towards the solution. In the case of Nim, the very first step could be something like:
Repeat
Display the game
Ask user for their move
Make userꞌs move
Generate computerꞌs move
Make computer's move
Until someone wins
Display the winner
None of these steps are written as proper Python code, and that’s OK for a first step. Translating this into Python would be a good idea:
Done = false
while not done: # Run until the game is over
displayState() # Show the game board
prompt() # Ask user for their move
makeMove () # Make it
if not gameOver(): # Computer move?
makeComputerMove()# Determine computer's move
done = gameOver() # Is the game over?
printWinner()
At this point in the design the data structures to be used in the solution have not been devised, nor have the algorithms needed. This is merely a sequence of steps that could lead to a program that works. The functions can now be written as stubs:
def displayState(): def prompt():
print("Display state") print("Enter move")
def makeMove(): def gameOver():
print ("Make move") if random.random()<0.2:
return False
return True
def makeComputerMove(): def printWinner():
print ("compute a move") print("The winner is:")
The output from this program might be:
Display state
Enter move
Make move
Display state
Enter move
Make move
compute a move
The winner is:
The exact output will be random, depending on what the return value of gameOver() is. This code can be thought of as one iteration of the solution, or as a prototype. The next step will be to refine the solution by implementing one of the stubs. Each time that happens a set of decisions will likely be made concerning the nature of the data structures used to implement the solution: the use of a list for the game state, for instance. Three integers could have been used instead, but once the decision is made one way or the other it should be stuck with unless it becomes infeasible.
Repeatedly implementing the stubs creates new prototypes, each one more functional than the one before. Some of the functions may require an application of this same process. Complex functions can be coded in terms of other stubs, and so on. The simpler functions, such as those that calculate based only on their parameter, should be completed first and should not involve permanent design choices.
A programming process of this kind can be thought of as iterative refinement. At all times after the first step, a complete program that compiles and runs will exist to be demonstrated and refined. This can be very useful, especially when dealing with graphical user interfaces and games. The interface might well be complete before any real functionality is present, and this permits a demonstration of the concept before the program is done.
4.6 Summary
Python allows a programmer to create a function that does something new. A function is really just some code that has a name, and can be executed simply by invoking that name. It usually represents some task that has to be done fairly frequently. A function should also have one main task, and that task should be represented in the function name: maximum, square, search, and so on. Many functions return a value, and finding that value is frequently the purpose of the function (e.g., sine, cosine).
The name of a function can be used to call that function, but it can also be assigned to a variable, passed as a parameter to another function, or returned as a value. A function can have variables that belong to it; they are called local variables and vanish after the function returns. They can also use variables defined outside of the function if they appear in a global statement.
A special value named None is used to represent no value, and is returned by a function that does not explicitly return some other value. A module is a function or collection of functions that reside in a file whose name ends in “.py.”
The use of functions can organize a computer program in a logical way. A program can be defined in terms of functions that are desired but not yet written, and then those functions can be defined as code or in terms of other functions. Functions are often named but are incomplete, and are called stubs—they permit the program to be compiled while still under development.
A function that calls itself is said to be recursive. Such functions can be very valuable in simplifying the code for some algorithms, especially ones in which something is actually defined in terms of itself, but care must be taken when programming to ensure that a recursive function always ultimately returns.
Exercises
1. Write a Python function that takes a tuple of numbers as a parameter and returns the location (index) of the maximum value found in that tuple.
2. A word processing system sometimes needs to shorten a word to make it fit on a line. Write a function that takes a string containing a single word and decides where to hyphenate it. A hyphen can occur before the endings: “ing,” “ed,” “ate,” “tion,” or “ment.” It could also occur after a prefix: “pre,” “post,” “para,” “pro,” “con,” or “com.” Otherwise, place a hyphen somewhere in the middle of the word. The function should return a tuple containing the first and second half of the word split at the hyphen.
3. Pascal’s triangle is an arrangement of numbers in rows and columns such that each number in a row is the sum of the two numbers above it. An example is:
1
1 1
1 2 1
1 3 3 1
Write a function triangle(n) that prints the first n rows of such a triangle. Use extra marks for proper indentation so it looks like a triangle.
4. Write a function that returns the value of a quadratic function at a particular x value. A quadratic is a polynomial of the form:
ax2 + bx + c
The function quad() is passed values for a, b, c, and x and returns the value of the polynomial.
5. A quadratic polynomial has a root at any value x for which the value of the polynomial is zero; that is, any x such that
ax2 + bx + c = 0
There can only be at most two such values (a tuple), and the expression for finding these values of x is:
Write a function (root(a,b,c))that returns the two roots of a quadratic equation having been passed a, b, and c. The result is a tuple, or if there is no solution (i.e., square root of a negative number, or a=0) then it returns None.
6. Write a function (inputfloat(s)) that takes a single parameter, a string to be used as a prompt, and returns a number read from the console. The function must prompt the user for the number using the given string, read the input, and return the result as a floating point number. If an error occurs return None.
7. The game of table tennis is sometimes called ping-pong. Write functions ping() and pong() that each take, as a parameter, a probability of hitting the ball. A probability is between 0.0 and 1.0. The function returns True if the ball is returns and False otherwise. There are two sides to the game, and each side serves (plays first) twice, then the other side serves twice. It will be assumed here that the server always succeeds. If ping is serving then pong() gets called first, then if pong succeeded then ping() gets called, and so on. The side that made the last successful hit wins a point. The game goes to 11 points, but must be won by a 2-point margin. Write a program that simulates ping-pong using two functions named ping() and pong().
8. In mutual recursion two functions call each other, usually repeatedly to some depth. So: A calls B, which calls A again, which calls B again, and so on. Recode the ping-pong exercise (Number 7 above) so that ping() calls pong() and pong() calls ping(). The functions return a string, that of the winner of the exchange.
9. Write a function prime(n) that returns True if the number n is prime, and False otherwise. How many prime numbers are there between 1 and 1000?
Notes and Other Resources
Tutorial on Python Functions: http://www.tutorialspoint.com/python/python_functions.htm
Also: http://anh.cs.luc.edu/python/hands-on/3.1/handsonHtml/functions.html
1. Thomas S. Ferguson. Game Theory, https://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
2. D. G. Luenberger. (1973). Introduction to Linear and Nonlinear Programming (Vol. 28), Reading, MA: Addison-Wesley.
3. Mitchell Wand. (1980). Induction, Recursion, and Programming, North Holland, NY, http://tocs.ulb.tu-darmstadt.de/82570701.pdf