In [9]:
# Setup
from IPython.display import HTML

Discussion 2 - CS61A

Control and Higher Order Functions

Sumukh Sridhara - Section 19

sumukh@berkeley.edu

Announcements

Quiz Due: Today @ 11:59!

Lab Due

Project Due: Wednesday. Turn it in early!

Practical Programming Skill - Today @ 6:30 in 306

Warmup!

Assume the following has been typed into the interpreter. What comes out?

In [12]:
from operator import add, mul
def either(f, g):
    def or1(y, x):
        if y and x:
            return f(1, x and y)
        return g(2, y or x)
    return or1
# >>> which = either(add, mul)
# >>> which(1,5)
In [15]:
#Draw an env diag for this:
def f(x):
    def g(y):
        return x + y
    return g
sieben = f(4)(3)
In [14]:
which = either(add, mul)
which(1,5)
Out[14]:
2

Control

In [1]:
def is_prime(n):
    # Fill out this function. Returns True if n is a prime
    # Hint use % operator
    # Answer is below
    "Your code here"
    
In [1]:
def is_prime(n):
    k=2
    while k < n:
        if n % k == 0: 
            return False
        k += 1 
    return True

is_prime(5)
Out[1]:
True
In [24]:
def choose(n, k):
    # The answer is below. 
    " Compute n choose k "
In [1]:
def choose(n,k):
    total = 1 
    i=0
    while i < k:
        total = total * (n - i) // (i + 1)
        i += 1 
    return total
choose(5,2)
Out[1]:
10
In [25]:
def skipped(f):
    def g():
        return f
    return g
def composed(f, g):
    def h(x):
        return f(g(x))
    return h
def added(f, g):
    def h(x):
        return f(x) + g(x)
    return h
def square(x):
    return x*x
def two(x):
    return 2

# >>> composed(square, two)(7)
# >>> skipped(added(square, two))()(3)
# >>> composed(two, square)(2)
# Answer is below
In [17]:
composed(square, two)(7)
Out[17]:
4
In [18]:
skipped(added(square, two))()(3)
Out[18]:
11
In [19]:
composed(two, square)(2)
Out[19]:
2

Higher Order Functions

In []:
def every(func, n):
    """Prints out all integers from 1 to n with func applied on them.
    >>> def square(x):
    ...     return x * x
    >>> every(square, 3)
    1
    4
    9
    """
    # Answer below
In [5]:
def every(func, n):
    i=1
    while i <= n:
        print(func(i)) 
        i += 1

def nyan(x):
    return x + 101

every(nyan, 5)
102
103
104
105
106

Enviroment Diagrams

Environment Diagram Rules

Creating a Function

  1. Draw the func <name>(<arg1>, <arg2>, ...)
  2. The parent of the function is wherever the function was defined (the frame we're currently in, since we're creating the function).
  3. If we used def, make a binding of the name to the value in the current frame.

Calling User Defined Functions

  1. Evaluate the operator and operands.
  2. Create a new frame; the parent is whatever the operator's parent is. Now this is the current frame.
  3. Bind the formal parameters to the argument values (the evaluated operands).
  4. Evaluate the body of the operator in the context of this new frame.
  5. After evaluating the body, go back to the frame that called the function.

Assignment

  1. Evaluate the expression to the right of the assignment operator (=).
  2. If nonlocal, find the frame that has the variable you're looking for, starting in the parent frame and ending just before the global frame (via Lookup rules). Otherwise, use the current frame. Note: If there are multiple frames that have the same variable, pick the frame closest to the current frame.
  3. Bind the variable name to the value of the expression in the identified frame. Be sure you override the variable name if it had a previous binding.

Lookup

  1. Start at the current frame. Is the variable in this frame? If yes, that's the answer.
  2. If it isn't, go to the parent frame and repeat 1.
  3. If you run out of frames (reach the Global frame and it's not there), complain.

Tips

  1. You can only bind names to values. No expressions (like 3+4) allowed on environment diagrams!
  2. Frames and Functions both have parents.
In [29]:
n=7
def f(x):
    n=8
    return x + 1
def g(x):
    n=9
    return x + 3

def f(f, x):
    return f(f(x+2)) 

m = f(g, n)
# Draw an enviroment diagram. Example below
In [28]:
HTML("<iframe width='800' height='500'frameborder='0' src='http://goo.gl/ZC65yQ'></iframe>")
Out[28]:
In [30]:
from operator import add
def curry2(h):
    def f(x):
        def g(y):
            return h(x,y)
        return g
    return f

make_adder  = curry2(add)
add_three = make_adder(3)
five = add_three(2)

# Draw an enviroment diagram
In [22]:
HTML("<iframe width='800' height='500'frameborder='0' src='http://goo.gl/0UQpc8'></iframe>")
Out[22]: