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


# 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


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):
" 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
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 h(x):
return f(x) + g(x)
return h
def square(x):
return x*x
def two(x):
return 2

# >>> composed(square, two)(7)
# >>> composed(two, square)(2)

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
"""

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



# 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


HTML("<iframe width='800' height='500'frameborder='0' src='http://goo.gl/0UQpc8'></iframe>")