Links

Slides
Check-in [SOL]

Concepts

1. What are the steps to evaluating def statements, assignments statements, and call expressions?
2. What is a recursive function. Why does a recursive function need a base case?

Problems

Question 1

def decrement(x):
    return x - 1

def half(x):
    return x // 2

def decrease_to_one(f, n):
    i = 0
    while n > 1:
        n = f(n)
        i += 1
    return i

How many call frames are opened if you call decrease_to_one(decrement, 5)? What about decrease_to_one(half, 8)?

TOGGLE SOLUTION

The initial call to decrease_to_one will open a frame. In the body of decrease_to_one, f is called until n reaches 1. So the question is, how many times does it take to reach 1 from n by calling f on it? For decrease_to_one(decrement, 5), it'll take 4 calls to f (f(5), f(4), f(3), f(2)), and for decrease_to_one(half, 8), it'll take 3 calls to f (f(8), f(4), f(2)). Each of these calls requires a new frame, so the answers are 5 and 4.

Question 2

Fill in the blanks below so that the output is as follows.

>>> def foo(x):
...     def bar(y):
...         return x("Higher order functions " + y)
...     return bar
>>> def baz(z):
...     print(z())
>>> baz(foo(____________________)(____________________))
Higher order functions are awesome

TOGGLE SOLUTION

baz(foo(lambda x: lambda: x)("are awesome"))

Explanation:
First, we see that the return value of foo(____________)(____________) is passed as an argument to baz and will be bound to the parameter z. Notice that z is being called with no arguments in the body of baz. That means that the entire expression foo(____________)(____________) must return a zero-argument function.

Now let's analyze the call expression itself. First, we evaluate the operator: foo(____________). This operator is itself a function call, and we know it must return a function. Well, that's already taken care of, because foo's return value is always the function bar regardless of the input. So what should we pass through to it? Notice that foo's parameter x is called on the string "Higher order functions " + y. That must mean that our argument is a function, more specifically, a one-argument lambda function. So then we have this:

foo(lambda x: ???)(____________)

Since I've named the lambda's parameter x, the entire string "Higher order functions " + y will be bound to x when we execute this lambda. Keep in mind now that lambda x: ??? will be bound to the parameter x.

Let's skip the lambda's body for now and move on what to put in the second set of parentheses. We've established that foo(lambda x: ???) will return bar, so essentially foo(lambda x: ???)(____________) becomes bar(_________). Figuring out what to pass through to bar is easy. We see that the parameter y will be added to the string "Higher order functions ". This is the only place in our code where we can concatenate strings, so y must be bound to "are awesome". So now all that's left is to write the body of the lambda:

foo(lambda x: ???)("are awesome")

Earlier I said that the entire expression above must return a zero-argument function that will be bound to z inside of baz. How can we make that happen? Well the return value of that whole expression is actually just the return value of bar (remember that foo(lambda x: ???)(____________) is basically bar(_________)). bar returns the value of x called on "Higher order functions " + y! Recall that x is bound to the lambda function we already wrote in. Thus, for bar to return a zero-arg function, our lambda must return a zero-arg function:

foo(lambda x: lambda: ???)("are awesome")

Let's regroup and go over what our "bindings" are so far. x is bound to lambda x: lambda: ???. z is bound to that inner lambda, lambda: ???. The parameter x to our first lambda will be bound to the string we want to print.

Now, to figure out what that inner lambda should return, we must turn back to baz. Our desired action is to print the string that is bound to x in the first lambda. baz takes care of the printing for us; it prints the return value of z(). That means that our inner zero-argument lambda must return the string we want to print, which is bound to the parameter x of the outer lambda function. This completes the solution:

foo(lambda x: lambda: x)("are awesome")

Important note #1: Throughout the explanation I said that certain variables are bound to lambda ... : .... I do not that the variables are literally bound to those lambda expressions; it was simply a clean way to refer to certain functions. Remember than lambda expressions are just unevaluated expressions just like 2+4. What I mean is that the variable is bound to the function object that that lambda expression creates.

Important note #2: I don't expect you to read through this lengthy explanation and totally understand everything that's going on. For that reason I highly recommend drawing out the environment diagram. You can find the solution to the environment diagram here.