Week 5: While loops, Functions

CS21 Week 5: While loops, Functions

Monday

More Strings: substrings, in operator

A substring of a string is a portion of the string that appears contiguously. For example, blue is a substring of blueberries. Python has some commands for accessing substrings.

The most relevant for us right now is the in operator. in takes a substring called the pattern and another string commonly called the target, and returns True if and only if the pattern appears as a substring in the target.

Sometimes, the pattern can be a single letter, but in general, the pattern can be any string.

>>> 'a' in "apples"
True
>>> 'b' in "apples"
False
>>> "vark" in "Aardvark"
True
>>> "bbrries" in "blueberries"
False

While Loops

Another syntactic tool for designing programs in Python is the while loop. You’ve previously seen for loops, Boolean types, and if statements. The while loop is a mix of these three concepts. A typical for loop executes for a definite number of times. For example, programmers decide in advance to loop over things like finite lists, range() results, or the length of a string.

What if we are expecting a user to enter input in a specific format (e.g., a positive integer, a valid date, or a string with no punctuation)? We could trust the user not to make a mistake, but this approach is not very robust. Instead, if we detect that a user made a mistake in typing input, we could prompt the user again. But how many times should we ask? Once? Twice? 100 times? With a for loop, you’d have to set the number in advance.

A while loop can solve these types of computational problems by repeatedly looping until a Boolean condition is met. The general syntax of a while loop is:

while <CONDITION>:
    <BODY>

The <CONDITION> is a Boolean expression. When the condition evaluates to True, the body of the loop will execute and then re-evaluate the condition. When the condition finally evaluates to False, Python skips the body of the loop and executes the next line after the body.

Note that a for loop can often be written as an equivalent while loop.

Let’s look at some examples in while_loops.py.

Try: Echo

Practice writing while loops, and using conditionals in a program called echo.py. The program should repeatedly prompt the user for an input string. If the user types anything other than quit, you should print their message back with a counter of how many times you’ve "echoed" a message:

$ python3 echo.py
Enter a string: hello
Echo #1: hello
Enter a string: test string
Echo #2: test string
Enter a string: quit
Echo #3: quit
good bye

Use a while loop to continue asking the user for strings indefinitely until they type quit. If you get this, next see if you can remove echo’ing the quit string (remove the Echo #3: quit output when the user enters quit).

String Formatting

The print statement is nice for outputting, but it is difficult to format the output in a way we prefer. For example, every time we put out a dollar amount, we can’t guarantee two digits after the decimal point for the cents and we also have to always leave a space between the dollar sign and the amount. String formatting allows us to define string templates:

string value

int value

float value

String formatting also enables optional width and precision values:

Feature	Syntax	Example	Semantics
width	%<number>type	%10s	Format a number to a string with ten spaces minimum.
precision (float only )	%.<number>f	%.2f	Require exactly two digits after a decimal point.

Feature

Syntax

Example

Semantics

width

%<number>type

%10s

Format a number to a string with ten spaces minimum.

precision (float only )

%.<number>f

%.2f

Require exactly two digits after a decimal point.

Let’s look at some of the examples in print_format.py that show printing out the float variable pi from the math library using different formatting. This also shows some other examples.

Note that you can combine multiple values in a single string format:

item = "dozen eggs"
qty = 4
price = 2.49
print("%d %s cost $%.2f" % (qty, item, qty*price) )

Try

open the program currency.py to see what it is doing, and try running it a few times. Then modify the program to use a string formatting in the print statement to produce nicer looking output.

Try: Echo redux

Revisit your echo.py program, and try replacing the print statment with one that uses print formatting instead.

Wednesday

Functions

Today we’ll introduce another big, key computer science topic: functions. A function is a named sequence of statements that perform a particular operation. Some functions are built in (int,str,float,input,print), but you can also define your own functions. Defining your own functions has many benefits:

Modularity and Readability: break program up into functional parts, make programs easier to read/understand/debug.
Abstraction: hide low-level details of a function until you need to understand them; you can use a function without having to know how it is implemented (e.g., the print function).
Code Reuse: put repeated code into functions: "write code once, use function multiple times".
Minimize programmer error: write and test functions in isolation.

In fact, you’ve been defining and using your own functions for a couple of weeks now, with the main() function. This week, we’ll see many more examples of functions. You’ll see that functions can take input and return input, and even do other "side effects" in between.

Function Syntax

Here is the syntax for how to define a function:

def <NAME>(<PARAMETERS>):
    <BODY>

The <NAME> is the name of the function you define. The <BODY> is a series of statements that you want to execute each time you use your function. <PARAMETERS> is a list of zero or more inputs to the function. These parameters can be used inside the function just like any other variable.

Let’s look at some examples in function_examples.py. We have defined four functions so far: printIntro, printStarRow(n), starBox(n), and main(). We will describe a few of these and then have you practice some.

Once a function is defined, you can call the function, by giving the name of the function and specific values for each parameter.

vim shortcuts

Once we start working with larger program files, it is helpful to use some vim shortcuts to move to certain parts of the file. Here are a few (in ESC mode):

CNTRL-F move one page forward in the file
CNTRL-U move one page backward in the file
SHIFT-G moves to the end of the file
:<num> go to line number num (ex. :203 go to line number 203)
/<pattern> search for <pattern> in the file (ex. /print search for print in the file)
- n find next occurance of the pattern moving forward in the file
- N find next occurrance of the pattern moving backward in the file

Exercise: practice function definition and calls

Practice defining and calling functions by modifying your program in function_examples.py to implement starBox(n). Call starBox in main with different values of n. Try getting a value from the user with input in main and passing the value to starBox.

What happens when a function gets called?

Python does a lot of behind-the-scenes work when a function gets called. Here is an outline of what happens:

Steps that occur when a function is called:

Suspend current function.
Evaluate arguments, copy them to parameters of the called function in order.
Execute called function using set values of parameters.
Return back to the calling function.

When calling a function, arguments are sometimes but not always plain values. Other times, they are complex expressions. These expressions get evaluated in Step 2 of the process above.

starBox(2**3)

The `return` statement.

Often when you define a function, you want the function to return some value back to whatever program called the function. You can do this with the return command. For example, the built-in function input reads in a string of text from the user and returns it as a string. When a return statement is reached, the function stops and immediately returns the value indicated by the return statement.

For example, if you defined a function def add(a,b) to add the values a and b integers, you’ll probably want to define and return a variable result=a+b. Then, once you’ve added the numbers, the return result statement sends this value back to the calling function.

def add(a,b):
    """
    Computes the sum of values a and b
    Returns result

    sample usage:
        ans = add(3, 4)
        print(ans)        # Should print: 7
    """

    result = a + b
    return result

Stack Diagrams

A stack diagram is a way to visualize what happens with variables in memory as Python executes your program. Consider the following program:


def main():
  a = 6
  b = 11
  avg = average(a,b)

  print("The average of " + str(a) + " and " + str(b) \
        + " equals " + str(avg))

def average(num1, num2):
  """
  computes the average of two numeric values
    param num1: one value
    param num2: the other value
    returns: the average of the two values
  """

  toReturn = (num1 + num2)/2

  return toReturn

main()

Now, on the whiteboard we’ll see how this computation happens in memory. The computer’s memory is where the program stores the state of a running program including the values of all variables and the stack of all functions currently waiting to finish. Here is the general procedure for how a function execute when called:

Pause the execution of the current function.
Create a stack frame for the called function.
- space for parameters are allocated in the function’s stack frame
- space for local variables are allocated in the function’s stack frame
Each argument’s value is passed to the corresponding parameter: the value of each argument (the reference in the box) is copied to the corresponding parameter in order. For example, the third parameter refers to the same value of as the third argument.
Execute called function step-by-step until the return or until it reaches the end of the function body.
Send back the return value to calling function.
Remove or pop the called function’s frame off stack.
Continue executing calling function that is now back on top of stack. (the called function now evaluates to its return value in the caller)

Some things to keep in mind as you draw your own stack diagrams:

Function call stack is on left, values belong on the right
Space for variables and parameters are inside stack frames, the values to which they refer are outside the stack
The call stack always grows "up" when we call a function
The call stack shrinks when a function returns.
There is a separate box (frame) on the call stack for each function.
Parameters point to the same value as the arguments in the calling function.
The assignment operator changes the arrow.
A function can only access/reference variable names in its own stack frame. These variables are said to be in the function’s scope

Try: Stack Example 2

def main():

  x = 5
  y = 9

  ans = addNumbers(x,y)
  print("In main:")
  print(ans)
  print(total)       # Q2b: Gives an error. Q: Why?

def addNumbers(num1,num2):
    """
    adds two numbers together
      param num1: one value
      param num2: the other value
      returns: sum of num1 and num2
    """

    total = num1 + num2
    print("In addNumbers:")
    print(num1)
    print(num2)
    print(total)

    # Q1: Show the stack diagram as it exists at this point
    return total

main()

Draw the stack up to the point right before return total is executed
Answer the following questions:
- (a) What is the scope, respectively, of x, y, ans, num1, num2, and total?
- (b) Why does the last line of main() give a runtime error?

Friday

Stack Review

Let’s review stack drawing with Stack Example 2

def main():

  x = 5
  y = 9

  ans = addNumbers(x,y)
  print("In main:")
  print(ans)
  print(total)       # Q2b: Gives an error. Q: Why?

def addNumbers(num1,num2):
    """
    adds two numbers together
      param num1: one value
      param num2: the other value
      returns: sum of num1 and num2
    """

    total = num1 + num2
    print("In addNumbers:")
    print(num1)
    print(num2)
    print(total)

    # Q1: Show the stack diagram as it exists at this point
    return total

main()

Draw the stack up to the point right before return total is executed
Answer the following questions:
- (a) What is the scope, respectively, of x, y, ans, num1, num2, and total?
- (b) Why does the last line of main() give a runtime error?

Another Stack

Here is another one you can try on your own.

Trace through the execution of the program below, and draw the stack to the point DRAW TO HERE.

def main():

  a = 10
  b = 35
  result = absval(a,b)
  print("abs(%d-%d) = %d" % (a,b,result))

def absval(x,y):
    """
    absval: computes absolute value of difference of two values
      param x: one value
      param y: the other value
      returns: the absolute value of the difference of the two
    """

    if (x > y):
        aval = x-y
    else:
        aval = y-x

    # DRAW TO HERE: draw the stack to this point!
    #               (as it would look right before return)

    return aval

main()

Random Library

Python has a library for generating pseudo random numbers. This is useful if you want to write a program that does something different each time it runs. For example, game programs often use these to randomize game playing functionality like flipping a coin or rolling a die.

To use the random library, add the following to the top of your program:

from random import *     # grab a bunch of useful functions

The randrange function is one we will try out in randomOps.py:

randrange(start, stop)  # get the next random number in the range [start, stop)

randrange(stop)         # get the next random number in the range [0, stop)

Together: let’s modify randomOps.py, so that it keeps flipping coins until it flips 3 heads.

"keeps flipping": what type of construct do we need?
"until 3": how can we detect when 3 heads have been flipped?

Function Practice

Today we are going to practice writing more functions.

Exercise: square the biggest

Together, we are going to start the design of the a function, named square_the_biggest, that computes the square of the larger of two values. You’ll finish the implementation in the totally.py file and test it out.

Let’s start by consider these two questions first:

Does this function take any input (do we need to pass it any values)? If so, how many? And what type of values?
Does this function return a value? If so, what does it return and what type of value does it return?

With this we can write the start of the function definition, and some example calls to it from main.

Now finish the fuction definition (its implementation) and test it out.

Exercise: totally

In totally.py, define another function named total(n), which takes a positive integer as input and returns the sum of the first n positive integers.

Then, call your function from main on several different inputs to test it.

If you finish this early, try adding to main a call to read in a value from the user and test that it is a positive int value before calling your total function. If it is not, you can print out an error message. If it is, call your function.

Exercise: Syracuse Sequence: challenging!

This exercise combines while loops, functions, and the accumulator pattern!

In the syracuse.py file, add a function named syracuseSeq that takes as input a positive integer value, and returns the number of terms in the syracuse sequence starting at that value until the sequence reaches 1. Your function should also print out each term in the syracuse sequence. Add some calls to your function in main and print out the value that returned.

Starting with a value x, the next value in the syracuse sequence is determined by the following function (note that if x is even one function is applied to get the next value in the sequence, and if x is odd another is applied to get the next value in the sequence):

\( \mbox{next value is} \begin{cases} x \div 2 & \mbox{ if x is even} \\ (3 \times x) + 1 & \mbox{ if x is odd} \end{cases}\)

The entire syracuse sequence is generated by starting with a positive integer and repeatedly applying the function above until reaching 1. For example:

The syracuse sequence of 4 is:  4, 2, 1
The syracuse sequence of 3 is:  3, 10, 5, 16, 8, 4, 2, 1

It is an open question in mathematics whether this sequence always goes to 1 for every possible starting value.

Your main program should:

ask the user to enter a starting point value x (you may assume they enter a positive int value
call your syracuseSeq function that computes the syracuse sequence for x, printing out each term in the sequence until the sequences reaches 1 and returning the total number of terms in the sequence returning the total number of terms in the sequence (e.g., syracuseSeq(4) returns 3 and syracuseSeq(3) returns 8).
print out the value returned by the call.

Hints:

All terms in the sequence are integers (no floats)
The number of terms in the sequence until it reaches 1 varies for different values. Hence, you need a while loop not a for loop.
Break solving this into 2 parts:
1. first, implement the function to print out all the terms the syracuse sequence for a passed value and test it
2. then add in the functionality to compute the total number of terms in the sequence and return that value and test it
What pattern can you use to keep track of the total number of terms in the sequence?

Extra problems: stars, stars, stars!

These are some additional function writing problems that you can try out on your own. They combine functions, loops, and strings!

We don’t expect that you can necessarily solve all of these, but they are a good challenge to try in the context of getting some more practice writing functions.

In stars.py write a function named pyramid that takes a positive int value n and prints out the following pattern of stars:

when n is 3:
*
**
***

when n is 5:
*
**
***
****
*****

And then make some calls from main to your function.

Hints:

You could solve this using string accumulator or a string operator. Try one, then try the other way.
Remember you know how to print out a box of stars. In what ways is this similar? In what ways is it different?
Think about what is printed each line, how many stars, and how that related to the loop iteration.

If you solve this one, add another function called pyramid2 that prints out this challenging pattern of stars for different n values:

when n is 3:
***
**
*

when n is 5:
*****
****
***
**
*

Hints:

This one is easier to solve using string operators vs. string accumulator.

And if you want a super challenge, here is another very challenging pattern to think about:

when n is 3:
  *
 **
***

when n is 5:
    *
   **
  ***
 ****
*****

Hints:

think about some number of spaces being printed each line in addition to some number of stars. What is the pattern depending on the loop iteration?

CS21 Week 5: While loops, Functions

Monday

More Strings: substrings, in operator

While Loops

Try: Echo

String Formatting

Try

Try: Echo redux

Wednesday

Functions

Function Syntax

Exercise: practice function definition and calls

What happens when a function gets called?

The return statement.

Stack Diagrams

Try: Stack Example 2

Friday

Stack Review

Another Stack

Random Library

Function Practice

Exercise: square the biggest

Exercise: totally

Exercise: Syracuse Sequence: challenging!

Extra problems: stars, stars, stars!

The `return` statement.