CS61A Lab 2: Control Flow and Higher-Order Functions

Week 1, Summer 2012

Exercise 1: Assignment

Predict what Python will print in response to each of these expressions. Then try it and make sure your answer was correct, or if not, that you understand why!

a = 1
b = a + 1
a + b + a * b 
______________
a == b
______________
z, y = 1, 2
print(z)
______________
def square(x):
    print(x * x)        # Hit enter twice
a = square(b)
______________
print(a)
______________
def square(y):
    return y * y # Hit enter twice
a = square(b)
print(a)
_______________

Exercise 2: Control Flow

Use the values of a and b from the previous exercise. Predict what Python will print in response to each of these expressions. Then try it and make sure your answer was correct, or if not, that you understand why!

boolean operators
a > b and a == 0
_______________

a > b or a == 0
_______________

not a == 0
_______________

if statements
if a==b:
    a
else:
    b
_______________

if a == 4:
    6
elif b >= 4:
    6 + 7 + a
else: 
    25
________________

# ';' lets you type multiple commands on one line
if b != a: a; b  
_________________

while loops
n = 2
def exp_decay(n):
    if n % 2 != 0:
        return
    while n > 0:
        print(n)
        n = n // 2 #See exercise 3 for an explanation of what '//' stands for
exp_decay(1024)
__________________
exp_decay(5)
__________________


Exercise 3: factor()

Before we write our next function, let's look at the idea of integer division versus normal division.

Normal Division 	 		Integer Division
# a / b → returns a float!		# a // b → rounds down to the nearest integer
>>> 1/4					>>> 1//4 
0.25					0
>>> 4/2 				>>> 4//2 
2.0					2
>>> 5/3 				>>> 5//3 
1.666666666667				1

Thus, if we have a function "%" that gives us the remainder of dividing two numbers, we can see that the following rule applies:

b * (a // b) + (a % b) = a

Now, define a procedure factors(n) which takes in a number, n, and prints out all of the numbers that divide n evenly. For example, a call with n=20 should result as follows (order doesn’t matter):

>>> factors(20)
20
10
5
4
2
1 

Helpful Tip: You can use the % to find if something divides evenly into a number. % gives you a remainder, as follows:

>>> 10 % 5
0
>>> 10 % 4
2
>>> 10 % 7
3
>>> 10 % 2
0

Exercise 4: Type-checking

Many procedures require a certain type of argument. For example, many arithmetic procedures only work if given numeric arguments. If given a non-number, an error results. For instance, pow('hello', 2) will result in the following error:

TypeError: unsupported operand type(s) for ** or pow(): 'str' and 'int'

Suppose we want to write safe versions of procedures, that can check if the argument is okay, and either call the underlying procedure or return False for a bad argument instead of giving an error. (We'll restrict our attention to procedures that take a single argument.)

>>> sqrt('hello')
Traceback (most recent call last):
 File "", line 1, in 
TypeError: a float is required
>>> type_check(sqrt, isnumber, 'hello')
False
>>> type_check(sqrt, isnumber, 4)
2.0

1.) Write type_check. Its arguments are a function, a type-checking predicate that returns True if and only if the datum is a legal argument to the function, and the datum.
For testing, you'll want the isnumber procedure: use the one here (you don't have to understand how it works):

def isnumber(thing):
   try:
       int(thing)
   except:
       return False
   return True

2.) We really don’t want to have to use type_check explicitly every time. Instead, we’d like to be able to use a safe_sqrt procedure:

>>> safe_sqrt(’hello’)
False
>>> safe_sqrt(4)
2.0
Don’t write safe_sqrt! Instead, write a procedure make_safe that you can use this way:

>>> safe_sqrt = make_safe(sqrt, isnumber)

It should take two arguments, a function (you can assume it takes exactly one argument) and a type-checking predicate, and return a new function that returns False if its argument doesn’t satisfy the predicate.

Project 1 Peek

This section is a sort of sneak peak of project 1. In project 1, you'll be dealing with randomness (in the form of dice rolls). Often when dealing with non-deterministic procedures, we want to be able to quantify how a non-deterministic procedure typically behaves. One common quantification is called the mean, aka the average.

For the following exercises, we'll be using a simulated die for our source of randomness. Copy the file dice.py into your current directory (say, lab2/), by typing in your terminal:

   star[200] ~ # cp ~cs61a/lib/proj/proj01/dice.py .
Don't forget the space and period at the end! This should copy the file from our account to yours.

Look through dice.py - there are two functions, make_fair_die and make_test_die.

make_fair_die

This procedure takes in an integer sides, and returns a procedure that, when invoked, simulates a die roll by returning a number from 1 to sides. For instance, to create a 6-sided die, we would do:

>>> from dice import *
>>> my_die = make_fair_die(6)
>>> my_die()
4
>>> my_die()
2

Note: It turns out that providing an integer argument to make_fair_die is optional - if you look at the code for make_fair_die in dice.py, the function signature looks like:

    def make_fair_die(sides=6):
        …

The sides=6 means that the sides argument is optional - if the caller doesn't provide an argument, then make_fair_die will set sides to the default value specified (in this case, 6).

>>> my_die = make_fair_die()    # Also creates a 6-sided die
>>> my_die()
5

make_test_die

This procedure lets you explicitly state exactly how the die will behave. For instance, if I want to create a die that will always return 2, 5, 3 over and over again, I would do:

>>> die = make_test_die(2, 5, 3)
>>> die()
2
>>> die()
5
>>> die()
3
>>> die()
2

Note: The above interaction may seem a little morbid - remember, die is the singular version of dice. An unfortunate coincidence.

5.) Implement the average_value function (similar to Q8 from Project 1). This function takes two arguments: a non-pure target function fn and an integer num_samples that indicates how many times the target function should be called. The return value of the target function should be a number. Call fn a total of num_samples times, and return the average result. Assume that fn takes no arguments. Make sure that the doctest passes before you move on.

from ucb import main, trace, interact

def average_value(fn, num_samples):
   """Compute the average value returned by fn over num_samples trials.
   
   >>> d = make_test_die(1, 3, 5, 7)
   >>> average_value(d, 100)
   4.0
   """
   "*** YOUR CODE HERE ***"
   

6.) Now write the averaged function. averaged should take two arguments: a no-argument function fn, and an integer num_samples.
averaged should return a new no-argument function that, when called, returns the average value of calling fn num_samples number of times.

def averaged(fn, num_samples=100):
   """Return a function that returns the average_value of fn when called.

   >>> die = make_test_die(3, 1, 5, 7)
   >>> avg_die = averaged(die)
   >>> avg_die()
   4.0
   """
   "*** YOUR CODE HERE ***"

Exercise 7: Additional ucb.py features

At the end of last lab, we introduced the ucb.py file which the staff have provided and contains several helpful features in writing code. We started with main which helps with testing.

In order to use any features of the ucb.py file, you need to import it into your Python files by including an import statement at the top of each file:

	from ucb import main, trace, interact

Section I: A Recap of main

An entry point of a program is the place where execution starts happening. It's usually very convenient to be able to demarcate an entry point in a Python file for testing purposes. Say we have the following file cube.py:

def cube(x):
    return x * x * x

print("Should be 1:", cube(1))
print("Should be 8:", cube(2))
print("Should be 27:", cube(3))

star [123] ~ # python cube.py
Should be 1: 1
Should be 8: 8
Should be 27: 27

One problem with this file is that the tests aren't cleanly arranged. Plus, if I'm using Python in Emacs, then the test output will print out every time I re-load the cube.py file, which we might not want.

Note: The above interaction shows how to run Python scripts from the command line. When you do python cube.py, Python will effectively evaluate each line of the file, which is why the print outputs show when we run cube.py.

Instead, it'd be much better if we had a test function that performed these tests:

def cube(x):
    return x * x * x

def run_tests():
    print("Should be 1:", cube(1))
    print("Should be 8:", cube(2))
    print("Should be 27:", cube(3))

However, now, if I run the file, nothing happens:

star [123] ~ # python cube.py
star [124] ~ #

This is because, to Python, all we've done is define two functions: cube, and run_tests. We want Python to actually do something when we do 'python cube.py', however. So, we can specify an entry point with the @main annotation:

from ucb import main, trace, interact

def cube(x):
    return x * x * x

def run_tests():
    print("Should be 1:", cube(1))
    print("Should be 8:", cube(2))
    print("Should be 27:", cube(3))

@main
def main():
    print("Starting.")
    run_tests()
    print("Ending.")

star [123] ~ # python cube.py
Starting.
Should be 1: 1
Should be 8: 8
Should be 27: 27
Ending.

Section II: The trace feature

Let's face it - people make mistakes, especially when writing code. When trying to track down a mistake, it's usually useful to be able to see what a particular function does every time it's called. This is called trace-ing a function.

Say we have the following (incorrect) code to compute the Euclidean distance between two points:

def square(x):
   return 2 * x

def distance(x1,x2,y1,y2):
   return sqrt(square(x1-x2) + square(y1-y2))

We call the distance function with the points (3,0) and (0,0), expecting to get 3.0 back, but instead we get:

>>> distance(3,0,0,0)
2.449489742783178

Hm, that's not right! We take another look at the distance function, and everything seems to be structured correctly. So, the problem could be with one of the helper functions called by distance - we'll first examine square. We can trace square to see how square behaves when called by adding an '@trace' above the square definition: (Remember to import the ucb features)

from ucb import main, trace, interact
from math import sqrt

@trace
def square(x):
    return 2 * x

def distance(x1,x2,y1,y2):
    return sqrt(square(x1-x2) + square(y1-y2))

Then, when we call distance, we get:

>>> distance(3,0,0,0)
square(3):
square(3) -> 6
square(0):
square(0) -> 0
2.449489742783178

The trace output tells us when a trace'd function is called (i.e. 'square(3):' means that the square function was called with argument 3), and it also tells us what a trace'd function returns (i.e. 'square(3) -> 6' means that square(3) returned 6).


Section III: The interact feature

interact is a utility function in ucb.py that, when called, stops execution of the program, and opens an interactive prompt at that point in the program. This is very useful for debugging, because at this prompt, you can examine variable values during program execution.
For instance, copy the following into a new file dist_interact.py

from ucb import main, trace, interact
def distance(x1,y1,x2,y2):
    a = (x2-x1)**2
    b = (y2-y1)**2
    c = a+b
    print("== Before interact ==")
    interact()
    print("== After interact ==")
    return sqrt(c)

@main
def run():
    print("Starting.")
    print(distance(1, 1, 3, 1))
    print("Done!")

Run the program (either in Emacs, or in the terminal by doing 'python dist_interact.py'). You'll notice that the '>>>' Python prompt will appear. We are currently in the middle of evaluating the body of the distance function - in fact, we've stopped exactly where the interact() function is called. Print out the values of the local variables (such as x1, y2, a, b, c) to see their values. To resume execution, do C-d (if you're on a Windows machine, you instead need to do C-z Return).

interact() is useful for debugging, because you get to halt execution and examine variables to see what went awry.


Documentation Strings (aka docstrings)

From the PEP 257:

"A docstring is a string literal that occurs as the first statement in a module, function, class, or method definition."

A docstring can (and should!) be used to document functions that you write. Good docstrings will do things like: Ideally, a docstring should be of such quality that a programmer will, after having read the docstring, know exactly what the function does, and how to use it. For instance, here's an example of using docstrings:
def square(n):
   """Given a number n, returns the result of squaring n.

   Arguments:
       n -- a number
   Returns:
       The square of n.

   """
   return n * n

Doctests

A really cool feature is the ability to create 'automated' test cases within the docstrings. Inside a docstring, you can signify expected behavior by typing out expected interpreter behavior, like:

def square(n):
   """Given a number n, returns the result of squaring n.

   Arguments:
       n -- a number
   Returns:
       The square of n.

   >>> square(5)
   25
   >>> square(-1)
   1
   """
   return n * n
To 'run' the test cases, go to the terminal and run python with the '-m doctest -v' options:
star [123] ~/lab2 # python -m doctest -v square.py
Trying:
    square(5)
Expecting:
    25
ok
Trying:
    square(-1)
Expecting:
    1
ok
1 items had no tests:
    doctest_test
1 items passed all tests:
  2 tests in doctest_test.square
2 tests in 2 items.
2 passed and 0 failed.
Test passed.
The '-m doctest' option tells Python to run all doctests in square.py, and the '-v' option tells Python to tell us everything that's going on with each doctest (i.e. 'verbose' mode). If you only care about doctests that fail, don't provide the '-v' option. If a doctest fails, then Python will let you know which doctest failed.

As you can imagine, writing doctests is a quick and convenient way to both provide easy-to-verify test cases, and also provides example usage inside the docstring.

8.) Add doc-tests to your make_safe procedure.

Fin.