# Fun With Functions

You are not logged in.

Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

This reading is relatively new, and your feedback will help us improve it! If you notice mistakes (big or small), if you have questions, if anything is unclear, if there are things not covered here that you'd like to see covered, or if you have any other suggestions; please get in touch during office hours or open lab hours, or via e-mail at 6.101-help@mit.edu.

## 1) Introduction§

This week's readings focus on functions, and, in particular, on how functions fit into the environment model we started developing in last week's readings. We expect that functions are something you're all already familiar with, to some extent, from previous subjects; but we really think that functions are one of the most powerful tools we have for organizing and constructing complex programs, and so it's worth spending the time to review some things about functions and to dig into the details and really understand how functions work under the hood so that we can use them effectively in our own programs.

## 2) The Power of Abstraction§

One of our main goals in 6.101 is helping you develop new ways of managing the complexity of your programs. As we move to writing bigger and more complex programs (which may not fit all on one screen, and which may not fit nicely in your head all at once), we're going to need new tools and strategies to help us manage that complexity so that we can work with these kinds of programs effectively.

Although it may seem silly to say it, it's worth mentioning that reasoning about complicated systems can be... complicated. And a corollary is that reasoning about simpler systems is often simpler. As we move to thinking about (and designing!) bigger systems in terms of scope, scale, and complexity, it is important to have a way to think about breaking those complicated systems down into simpler pieces that are easier to understand.

To this end, one useful framework for thinking about complex systems involves thinking about:

• Primitives: What are the smallest and simplest building blocks of which the system is comprised?

• Means of Combination: How can we combine these building blocks together to build more complicated compound structures?

• Means of Abstraction: What mechanisms do we have for treating those complicated compound structures as building blocks themselves?

This third idea ("abstraction") is really critical, and it's the thing that allows us to keep things under control as we move to more complicated structures. The idea is that, once I have used the primitives and means of combination to build some new complicated structure, I can then give a name to that structure and treat it as though it were a primitive (including combining it with other pieces to make even more complex structures, which can then be given their own names and used to build even more complex structures, and so on...). The idea, then, is that we build up to big complicated systems layer by layer, each time designing, implementing, and testing new structures comprised of elements from the lower layers in such a way that each layer can be understood on its own. Then, when reasoning about the top-most (most complex) layer, we no longer need to think about it in terms of all of the underlying primitives, but merely in terms of the next layer down.

We can think about applying this framework to Python. In particular, considering operations that we can perform in Python:

Python gives us several primitive operations, including arithmetic (+, *, etc.), comparisons (==, !=, etc.), Boolean operators (and, or, etc.), built-in functions (abs, len, etc.), and more. We also have ways to combine those pieces together, using things like conditionals (if, elif, else), looping structures (for and while), and function compostion (f(g(x))).

But the real power comes when, after we've combined some pieces together to represent some new operations, we can abstract away the details of those new operations and treat them as though they had been built-in to Python from the start. And one of our main means of abstraction is the ability to define functions using the def or lambda keywords.

Functions provide a means of representing the abstract notion of an arbitrary computation. We can specify the nature of that computation (what values we view as inputs, and how we combine those pieces together to produce the effects and/or outputs that we want), and then we can abstract away the details and give it a name, such that we can invoke that computation at a later time, or combine it with other functions to build up to bigger and more complex programs.

Let's take a look at an example from lab 1 (and 2!) involving our choice of representation for images. In particular, let's focus on the decision to store the pixel values as a 1-dimensional array. While there are some good reasons for this choice of representation, as you're working through the labs, you may have noticed that working with this representation directly is not always the easiest thing to do. Generally, when we think about modifying images, we want to think about locations in 2 dimensions (i.e., we want to think about modifying the brightness value at a 2-d (row, col) location), and it takes a little bit of thought to figure out which index in the 1-d array of pixel values should be changed in order to make that kind of update.

But this is OK! One of the beautiful things about programming is that, if we are presented with a representation that we find difficult to work with, we can recognize that and create some functions that allow us to think about things using a more convenient representation. In this case, if set up some functions that take care of some of the conversion between 2-d and 1-d representations, then we can use those things to allow us to think about our images using the more natural 2-d representation! For example, we could write a function like the following:

def flat_index(image, row, col):
"""
Given an image and an (row, col) location, return the index associated with
that location in a 1-d list of pixel values stored in row-major order.

Parameters:
* row (int): the row number we want to look up, with 0 being the top-most
row
* col (int): the column number we want to look up, with 0 being the
left-most column

Returns an integer representing the index into a row-major-order 1-d list
of pixel values that corresponds to the location (row, col)

Raises an AssertionError if row or col are outside the bounds of the given
image
"""
pass  # writing this code is left as an exercise to the reader!


We've not written out the body of this function for you (you are welcome to fill it in and use it in your lab if you would like!), but the beautiful thing about this function is that it allows us to think about our images in terms of 2-d structures; once we've written this function and we're sure it's working as expected, we no longer need to worry about the details of converting between 2-d and 1-d locations when thinking about higher-level operations we want to perform on images. In that sense, this function is more than just a way to help us avoid repetitious code by calling this function instead of writing out the calculation for this conversion each time we need it; it enables us to think about later problems in a different, more natural way by building on top of this new abstraction we've built for ourselves.

But of course, this is not the only way we could have structured things to make our lives easier (another beautiful thing about programming is that there are always multiple ways to do things!). One example of a different approach we could have taken to the same problem (i.e., we want to be able to think about images as 2-dimensional structures, but the representation we're given is 1-dimensional) would be to define functions that convert back-and-forth between the given representation and some other, more natural representation. For example, some of you may have seen (in 6.100A or elsewhere) examples of representing 2-dimensional structures using lists of lists. If this representation feels more natural, we could have written functions like the following instead:

def image_to_2d_array(image):
"""
Convert an image in 6.101's lab format to a 2-d array (list-of-lists)

Parameters:
* image (dict): a dictionary with keys 'height', 'width', and 'pixels',
in the format described in the lab 1 writeup

Returns:
A 2-dimensional array (list of lists) containing pixel values, such
that image_to_2d_array(image)[row][col] represents the pixel value
at a specific row and column
"""
pass  # writing this code is left as an exercise to the reader!

def image_from_2d_array(array):
"""
Convert a 2-d array of pixel values to an image in 6.101's lab format.
This function is the inverse of image_to_2d_array, such that, for any image
im, image_from_2d_array(image_to_2d_array(im)) should produce a new image
identical to im.

Returns:
An image in the 6.101's lab format (a dictionary containing 'height',
'width', and 'pixels') equivalent to the input array.

Raises an AssertionError if the rows in the input array are not all the
same length.
"""
pass  # writing this code is left as an exercise to the reader!


With these functions in hand, our approach to the operations in the lab might have involved a few steps:

1. First, convert the image to a 2-d array using image_to_2d_array.
2. Then perform whatever operation we want using this new representation.
3. Finally, convert back to the lab's format using image_from_2d_array.

It's worth mentioning that these are not the only two ways we could have set up these abstractions, and there are pros and cons to each of these (as well as pros and cons to other ways we might think to set things up). But the point as of right now is not to focus on the details of the specific functions written above, but rather to demonstrate the usefulness of functions as a mechanism for building meaningful abstractions; and, as we saw in the example above, one way that these abstractions can help us out is when we're working with data in a format that isn't particularly easy to work with, we can write ourselves some helper functions to make thinking about those data more natural and easier for ourselves.

## 3) Functions and the Environment Model§

As we mentioned above, functions really are one of the most powerful tools we have at our disposal when designing programs. And even better, all of the interesting and complex behavior that we get from functions all follows from a small set of rules governing functions. As such, the remainder of these readings will focus on those rules and how they fit into our environment model. And the really cool thing is that, if we understand those rules, then we can also understand all of the beautiful high-level behaviors associated with functions; and the more we understand about how functions work, the more able we'll be to make effective use of functions in our own programs.

And, again, the reason to be thinking about this model at all is that it really helps us as programmers if we don't have to resort to guess-and-check strategies for every decision we make in our programs. It helps to have a structured and robust way of thinking about what happens behind the scenes in response to code that we write.

So throughout the semester, we'll keep expanding this model; and for today, we're going to focus on how functions fit into our model. There are 2 distinct processes we're going to need to think about when introducing functions into our model: we will need to think about what happens when we define a function; and, separately, we'll need to think about what happens when we eventually call that function.

### 3.1) Function definition with def§

The def keyword in Python does two things:

1. It creates a new function object in the heap. We're going to have a slightly simplified model as far as what we actually store inside of that object; but in our model, this object contains:

• The "formal parameters" of the function (i.e., the internal names by which we'll refer to the function's arguments).
• The code in the body of the function.
• A reference to the frame in which we were running when we encountered this def statement (we will refer to this as the "enclosing frame" of the function).
2. It associates that function object with a name in the frame in which we were running when we encountered the def statement.

Let's take a look at how this works by looking at the diagram that results from running a piece of code. Here is a small function definition:

def quad_eval(a, b, c, v):
"""
Given coefficients a, b, and c representing a quadratic polynomial
ax^2 + bx + c, as well as a value v, return the value of the polynomial at
the given point.
"""
term1 = a * v ** 2
term2 = b * v
return term1 + term2 + c


This function may not be the epitome of the good style we're trying to encourage, but it will serve as an example by which we can demonstrate how functions behave in terms of our environment model. When we run this code and Python encounters the def statement here, it will follow the steps we outlined above, creating a new function object and associating that object with a name. We'll draw the resulting diagram like so:

Crucially, we don't run the code in the body of the function at this point; rather, we simply store away these pieces of information in an object, which we can later call to actually run the code. Inside of the function object, we can see the pieces we mentioned up above:

• The top region of the box contains the parameters of the function (i.e., we're calling the arguments a, b, c, and v, respectively).

• The bottom region of the box contains the code representing the body of the function. Again, we're not running this code yet, just storing it away for later use.

• The little box in the top right corner shows a reference back to the frame that we were running in when we encountered the def statement (in this case, the global frame). Here, we've labeled this reference as "enclosing frame", but once we get more comfortable with these diagrams, we may omit that label. Note also that this arrow is pointing to the global frame itself, not to any of the individual names or references in the global frame.

Note that we also associated this object with the name quad_eval in the global frame. It's also worth noting that the resulting function object above is what we call a "first-class" object. That is to say, this object is treated similarly to how we've treated other objects. The variable binding that we made via def is the same exact kind of reference we saw in last week's readings. If we look up the name quad_eval, we do so by following the arrow and finding the function object on the heap. If we want to bind this object to a different variable, or to use it as an element in a list, or to pass it as an argument to a different function, we're able to do that (and we'll see some examples of how that might be useful a little bit later on in these readings)!

### 3.2) Calling a Function§

Function objects exist as abstract representations of particular computational processes, but they are really only useful when we call them (some people will call this "applying" or "invoking" the function; and syntactically, this is accomplished by putting round brackets after some expression that evaluates to a function object). Calling a function is how we actually perform the computation represented by that function; and, when we call a function, Python performs the following four steps:

1. It evaluates the function to be called, followed by its arguments (in order), in the frame from which the call is being made.

2. It then creates a new frame for the function call, which will be used to store variables local to the function call. This new frame has a "parent pointer" back to the function's enclosing frame.

3. It then binds the names of the formal parameters of the function to the arguments that were passed in, inside of the new frame we just created.

4. And, finally, it executes the body of the function in this new frame. Importantly, during this step, if Python tries to evaluate a name that isn't bound in that frame, it will look in that frame's "parent" frame (the enclosing frame of the function we're calling).

Let's see how this plays out using our example from above, when running the following code (which repeats the definition from above but also demonstrates a function call):

def quad_eval(a, b, c, v):
term1 = a * v ** 2
term2 = b * v
return term1 + term2 + c

n = quad_eval(7, 8, 9, 3)
print(n)


Use the buttons below to navigate through the process of drawing out the environment diagram for this program. We encourage you to follow along and draw the diagram for yourself alongside us as you're stepping through below!

Explanations go here.

Now that you've worked through the example above, answer the following question about it:

In step 4 above, when we set up the frame F1 for this function call, we set its parent pointer to be the global frame. For what reason was the parent pointer set this way?

### 3.3) Check Yourself§

Now that we've talked through the process by which functions are defined and called, we'll take a look at how they play out in a small example. This small program is, admittedly, a little bit contrived... but it should still illustrate how these rules give rise to the behaviors that we expect to see from functions.

Here is the piece of code we'll be considering (note that the names foo and bar don't have any real meaning, but they're conventionally used to refer to functions for which we don't have nicer names, often in silly examples like this):

x = 500

def foo(y):
return x+y

z = foo(307)

print('x:', x)
print('z:', z)
print('foo:', foo)

def bar(x):
x = 1000
return foo(308)

w = bar(349)

print('x:', x)
print('w:', w)

Check Yourself:

Without running the code above, try to predict what will be printed to the screen and fill in your guesses below. If you aren't able to predict these values correctly, that's OK (mistakes are a great way to learn!), but please make an earnest attempt to answer without relying on the description that follows, before moving on to our explanation.

What value will be printed for x on line 8?

What value will be printed for z on line 9?

What value will be printed for x on line 18?

What value will be printed for w on line 19?

Now that you have made a guess, let's draw an environment diagram as a way to help us reason about what happens when we run this code; and if we're careful with following the associated rules, we can use the diagram to accurately predict the output of the program above. But this is a complicated example, so grab a cup of tea or coffee and settle in. If you are confused by anything that follows, please feel free to ask for help!

STEP 1
Before we start running this program, we set up our initial environment structure. Here we have set up our "global frame" (GF), in which our program will be executed.

The next step to be executed is the assignment statement on line 1 (x = 500). What should the diagram look like after that statement has been executed?

STEP 2
Evaluting 500 gives us a new object that represents the integer 500. After creating this object, we associate the name x with it (in the global frame).

The next statement we encounter is a function definition. As mentioned above, Python will do two things here: firstly, it will make a new object to represent this function; then, it will associate that new function with a name (in this case foo).

STEP 3
Here we see the function object itself. Note the three things stored inside of the function: the names of the parameters (in this case, a single parameter called y), the body of the function (return x+y), and a reference to the enclosing frame (i.e., the frame we were running in when we executed this def statement).

Here we have labeled the reference to the enclosing environment with those words, but we will not always write that out.

STEP 4
Now we have also associated that function with the name fooin the global environment.

Note that we have not run any part of this function's body yet; we have just stored away the relevant information so that we can eventually call this function.

STEP 5
After finishing with the def statement, we are moving on to line 6, z = foo(307). This represents a function call, and so we need to follow the steps outlined under the "Calling a Function" header above.

We start by figuring out what function to call and what to pass to it. In this case, the function we're calling (the thing before the round brackets) is given by the expression foo. Evaluating that name in the global frame, we follow the associated arrow and find the function object on the right (marked with a small green check mark so that we can keep track of it).

Then we evaluate the arguments to the function. In this case, we have a single argument 307. Evaluating that expression produces a new object representing the integer 307.

Once we know what function we're calling and what arguments we're passing in to it, we are ready to proceed with the function call.

STEP 6
Our next step is creating a new frame to store the local variables associated with this function call. So we have made a new frame here. We also give it a name (just so that it is easier to refer to it), in this case F1.

Note that we have already drawn F1's parent pointer. How did we know that GF was the right parent? When we made F1, we looked at the function we were calling and used its enclosing frame as F1's parent.

Now that we've got our new frame set up, we proceed with our next step: binding the parameters of the function to the arguments that were passed in.

STEP 7
Here we see the end result of binding the parameters of our function to the arguments that were passed in. In this case, the function we're calling is a function of a single parameter (y), and the argument that was passed in is the object we see containing 307.

After this step, we have our local frame all set up, and we are now ready to actually run the body of the function.

STEP 8
After we've set up the frame associated wth this function call, we proceed by executing the body of the function inside of F1. In this case, the body of the function is return x+y.

Executing return x+y with respect to F1 involves evaluating x and y with respect to F1 and then adding those results together.

Evaluating y with respect to F1, we follow the arrow from y to the associated object, finding the integer 307 that was passed in as argument.

Evaluating x with respect to F1 is a little more complicated, since the name x is not bound in F1. But here we see the nature of the parent pointer. When evaluating a variable name in a given frame, if we don't find the name bound in that frame, we will follow the frame's parent pointer and look for the name there. If we find the name there, the associated object is the result. If we still don't find the name, we follow the next parent pointer; and we keep doing this until we either find the name we're looking for, or we run out of frames to look in. In this case, we don't find x in F1, so we follow its parent pointer and look for x in GF, where we find the associated value of 500.

Once we have those two pieces, we add them together, producing a new object representing the integer 807. This new object is the return value from our function call, which we will sometimes denote as above. Our function call is now done, and we need to look back and remember how we got here. In this case, we started this function call in the process of evaluating line 6, where our goal was to associate the result of the function call with the name z in the global frame.

STEP 9
Here we see the result of that assignment. At this point, we are done with the function call, and we can clean up all of the machinery that we used to figure out how the function call behaved and move back to executing code in the global frame. The result of that cleanup will be shown in the next step.
STEP 10
Here we see the result after line 6 has been executed. Next, we hit three print statements. Following the arrows in our diagram, we can now see that x is associated with 500 and z is associated with 807; so we can predict that those are the values that will be printed for x and z. But an important question remains: what will be printed for foo?

Even though it may seem strange at first, we can determine what will be printed for foo in the exact same way that we figured out what to print for x and z: by following the arrow in our diagram from the name foo. In this case, we find the function object on the right side of the diagram, which is what Python will print.

Python prints this in a somewhat strange way, but it's trying its best. It prints out a little representation that includes the function object's location in memory, something like <function foo at 0x7f30d9080040>, where the exact number on the right side will be different each time we run the program.

Importantly, what we are printing when we print(foo) is the function object itself, not the result of calling that function. Line 10 does not cause foo to be called; we simply look up the name foo and print the associated object.

Ultimately, we see something like the following as the output of lines 8-10:

x: 500
z: 807
foo: <function foo at 0x7f30d9080040>


Now, we are ready to move on to our next statement, the second def on line 12.

STEP 11
We follow the same rules when executing this def statement as we did before, and the first part of that process results in a new function object, shown in the diagram above. Note again that we have not run any of the code in the body of this new function yet; we are just storing it away to be called later.
STEP 12
The def statement also associates the name bar with this function, in the global frame. The end result is shown in the diagram above.

With that, we are done with evaluating the def statement that starts on line 12, and we are ready to move on to the next statement, the assignment on line 16.

STEP 13
Evaluating the assignment statement on line 16 involves first evaluating the expression on the right-hand side of the equals sign, which is a function call. We start that process by determining what function we're calling and what arguments we're passing in to it.

In this case, the function we're calling is given by bar, and a single argument 349 is given. So we evaluate the name bar, finding the function object indicated with the green checkmark above; this is the function we're going to call. And evaluating 349 produces a new object representing the integer 349, which is the object we are passing in to the function.

Once we know what function we're calling and what we're passing as inputs, we can proceed with the function call using the rules described earlier.

STEP 14
We start by making a new frame to store this function's local variables. Above, we've made this frame and labeled it as F2. Note that F2 has a parent pointer to our function's enclosing frame.

After we have created the frame, our next step will be to bind the parameters of the function to the objects passed in as arguments; the result of this process will be shown in the next step.

STEP 15
Here, we show the result of binding the name x to the value 349 inside of our new frame F2.

I think it is important to note here that this binding did not affect the value associated with the name x in the global frame. Even though x refers to 349 in F2, x still refers to the value 500 in the global frame. And since we will ultimately evaluate the body of this function inside of F2, referring to x in the function will not find the global binding of x.

This setup (where each function call gets its own frame to store its local variables) is generally really nice and quite powerful, in that it allows us to call the parameters of our functions (and other local variables inside of our functions) by any names we wish, without needing to worry about accidentally messing up the variable bindings in other frames.

Anyway, once we have made that binding, we are ready to execute the body of the function inside of F2. And so the next statement we encounter is x = 1000, which we evaluate with respect to F2. Can you predict what the result will look like? We will show it in the next step.

STEP 16
Since we were executing x = 1000 with respect to F2, we modify the arrow from x inside of F2. Note again that the global binding of x is unaffected. At this point, we're done with x = 1000, so we can move on to the next statement.
STEP 17
Remember that at this point, we are still executing the body of our function inside of F2. And the next statement we encounter is return foo(308). This is another function call! So what do we do?

Conveniently, even though we are now going to be two function calls deep, we evaluate this second function call in precisely the same way we evaluated the first one, by following the rules laid out earlier on this page. And so the first thing we need to do is to determine what function we're going to be calling and what arguments we're going to pass in. But there is a little bit of subtlety here that we need to be careful of.

Because this function call is being made from F2, figuring out what function to call involves looking up the name foo inside of F2. We don't find the name foo there, so we follow the parent pointer and look in the global frame, where we find that the name foo is bound to the function object that now has two small blue checkmarks next to it; so that's the function object we'll be calling.

Then we evaluate the argument and get a new integer 308, which has been drawn in above as well. And, now that we know what function we're calling and what arguments to pass in, we can proceed with actually calling the function. Our first step will be to make a new frame for this new function call.

STEP 18
Here we have drawn in our new frame (called F3), but we're actually not quite done with that part yet because we have not yet given this frame a parent pointer. **Please take a moment and try to predict**, given the rules we have outlined here, where should F3's parent pointer go?
STEP 19
The key rule for determining a new frame's parent pointer is: what is the enclosing frame of the function we're calling? In this case, we're calling the function drawn toward the top of the diagram (with the two blue checks next to it, which is referred to as foo in the global frame); and that function's enclosing environment is GF, so that's where our new frame's parent pointer goes.

Importantly, this is true even though we made this function call from F2! What matters for determining this structure is not where we're making the call from, but rather where the associated function was originally created. This may seem like a strange rule at first, but it leads to a lot of nice properties that we will discuss in more depth during class.

And now that we've set up our new frame, we can move on to our next step, binding the parameters of the function to the arguments that were passed in.

STEP 20
The function we're calling is a function of a single parameter called y, and so inside of F3, we bind the name y to the 308 that was passed in. Having done so, we are ready to execute the body of the function inside F3.
STEP 21
Evaluating the body of the function with respect to F3 involves evaluating both x and y with respect to F3 and then adding the results together to produce the return value of this function call.

Evaluating y with respect to F3 is relatively straightforward: y is bound in that frame, and so we follow its arrow to find the 308 that we passed in as an argument.

Evaluating x with respect to F3 is more involved. We look for x in F3, but we don't find it there, so what do we do next? We follow F3's parent pointer and look for x there. So, importantly, we find the value 500, to which x is bound in the global frame (and not the 1000 to which x is bound in F2).

Adding these values produces a new value 808, which will be our return value.

Now we need to think a little bit. How did we get to this function call, and where should we return back to? Remember that we started this function call in the process of figuring out what to return from our original call to bar. So we'll jump back to that point in the execution, with our new 808 value in hand.

STEP 22
Since the line we had been executing in F2 was return foo(308), we're simply going to take the result of that function call (the 808 we just figured out) and mark it as the return value from F2, which has been reflected above.

At this point, we are also done with that second function call. So on the next step, we'll clean up some of the machinery that we created purely for determining that result.

STEP 23
And we also need to remember: how did we come to be calling bar in the first place? That is, now that we have the output of the function call, where do we return to?

We first got here by executing w = bar(349) in the global frame. So that's where we'll go next, binding the name w to 808 inside of the global frame.

STEP 24
Phew, that was quite a journey! But now we're done with executing line 16 in our original program!

At this point, we can clean up F2, since we're done with that function call, leaving us with one final diagram.

STEP 25
Now the only thing left to do is to figure out what prints when lines 18 and 19 are run. Tracing the arrows from x and w from the global frame, we find 500 and 808 (respectively), and so those are the values that will be printed:

x: 500
w: 808


After the value 808 has been returned from F2, we no longer have a need to keep F2 around, and so it (as well as the integer 1000 that was only reachable from F2) will be garbage collected, leading to the final diagram.

STEP 26
This diagram represents the state of memory at the end of our little program. Notice that the value of 808 that we got from calling our function is still available to us, via the name w in the global frame.
x = 500

def foo(y):
return x+y

z = foo(307)

print('x:', x)
print('z:', z)
print('foo:', foo)

def bar(x):
x = 1000
return foo(308)

w = bar(349)

print('x:', x)
print('w:', w)


One last question for this section: imagine adding x = 2000 to line 5 of the program above and running it again. Which of the following printed values would be different from running the code without that change?

If you're unsure of why this answer is what it is, think about how things would change in terms of our environment diagrams. And, of course, if you're stuck, please don't hesitate to ask for help!

## 4) Functions Are "First-Class" Objects§

One powerful feature of Python is that it treats functions as first-class objects, which means that functions in Python can be manipulated in many ways that other data can (they can be passed as arguments to other functions, defined inside of other functions, returned from other functions, added to collections, and bound to variables, among other things). This is reflected in our environment diagrams by the fact that functions are represented by objects on the right side of our diagrams, just like other data (integers, lists, etc.) are!

Some of the sections below will talk more about the consequences of this feature. But, to start, let's look at a small example: code:

def double(x):
return 2 * x

myfunc = double


After executing the first def statement in the little code block above, our environment diagram looks something like this:

Below are four possible diagrams that could result after executing the second statement (myfunc = double). Which of these, if any, represents the result of executing that statement?

 A B

 C D

Which diagram shows the correct result?

What is the result of evaluating myfunc(21), starting from the diagram above? Enter a value below, or enter error if this expression causes a Python error.

Starting with the definition of double from above, if we wanted to create a structure like the one shown in environment diagram option C above, what code should we write? Type your code in the box below:

### 4.1) Example: Thinking About Types§

Consider the following small piece of code:

def square(x):
return x*x
foo = square
x = [square, foo]


Start by drawing an environment diagram for this code, and, once you have done so, click below to show our solution:

Here is the diagram we drew:

Does your drawing match this one? If not, pay careful attention to the differences. What assumptions about the code above (or the nature of the diagrams) led to those differences?

Make sure you understand this diagram before moving on! If not, please come and ask someone during instructor office hours or open lab hours, or via the 6.101-help@mit.edu mailing list.

Now, using your diagram from above, predict the type of each of the following expressions and enter your answer below. For each, also think about what would be printed to the screen if we were to print that object. After you have entered the correct type for each expression, viewing the associated answer will provide some more details and explanation.

Starting from the code/diagram above, what is the type of square(2)?

Starting from the code/diagram above, what is the type of foo(0.7)?

Starting from the code/diagram above, what is the type of foo?

Starting from the code/diagram above, what is the type of x?

Starting from the code/diagram above, what is the type of foo[1]?

Starting from the code/diagram above, what is the type of x[0]?

Starting from the code/diagram above, what is the type of square()?

Starting from the code/diagram above, what is the type of x[1](3.1)?

Starting from the code/diagram above, what is the type of (square + foo)(7)?

### 4.2) Example: Functions As Arguments§

We'll see a more practical example in a moment, but for now, let's take a look at a small example illustrating an interesting use of first-class functions. Consider the following code:

def apply_n_times(f, n, x):
out = x
for _ in range(n):
out = f(out)
return out


This code is, sadly, undocumented right now, but we can figure out some things about what it's doing from looking at how its arguments are used within the body of the function. Take a moment and see if you can figure out anything about the type(s) or value(s) of the arguments before reading on.

Looking at the code, we can see where n is being used: it's being used as the sole argument to the range function. Since range accepts integers as inputs, we can assume that n must be an int. And the looping structure there tells us that n specifies the number of times that we're repeating some action. What are we doing inside of the body of that loop?

The syntax there shows us that we are calling f with out passed in, binding the result of that call back to the name out. This tells us that f probably needs to be a function! Indeed, apply_n_times is a function itself, but it takes another function as one of its inputs! This is pretty trippy, but we can see it in action.

Consider the following function definition:

def double(y):
return y*2


What can we put in the blank in the code below to make the printed value equal to 48 (with no exceptions being raised)?

print(apply_n_times(_________, 4, 3))


### 4.3) Function definition with lambda§

For just a bit longer, let's keep looking at our small example function from the last section:

def square(x):
return x*x


As discussed above, this statement does two things: it creates a new function object, and it associates that function object with a name, such that we can refer to it later by that name.

Python also has another way of defining functions, which can be useful in some situations: the lambda keyword. This may seem a bizarre name, but it comes from a mathematical system for expressing computation, called the Lambda calculus. Another way to make a function that squares its input is:

lambda x: x*x


This makes a function that is almost exactly the same as square, except that it does not have a name. lambda is never necessary (you can always use def instead), but it is a nice convenience in some situations. The most common place where lambda is useful is when we need to provide a small function as argument to another function, but we don't have that function around yet (and we don't want to keep it around for other purposes). For example, in our apply_n_times example from above, if we had no use for double outside of passing it in as argument to apply_n_times, we could have produced an equivalent function call with the following:

print(apply_n_times(lambda x: x*2, 4, 3))


### 4.4) Example: Plotting Function§

We've seen a couple of examples above that made use of functions as first-class objects, but they were somewhat contrived, small examples that only existed to demonstrate the rules by which function objects operate. But right about now you might be asking yourself: is this actually good for anything? Is there any practical use? And the short answer is: yes! Not only is this a cool feature, but it turns out to be useful for organizational reasons. For now, let's just take a look at one example of how we can leverage this idea to improve the style of a piece of code.

To start, let's consider the following piece of code, which uses the matplotlib package to generate a plot of a sine wave:

import math
import matplotlib.pyplot as plt

def sine_response(lo, hi, step):
xs = []
ys = []
cur = lo
while cur <= hi:
xs.append(cur)
ys.append(math.sin(cur))
cur += step
plt.plot(xs, ys)


If we run call this function using sine_response(-5, 5, .1), matplotlib produces a plot for us showing a sine wave evaluated at several points between -5 and 5, spaced .1 apart:

But now imagine we want to plot other functions. What can we do? Well, the temptation will exist to copy/paste the function and make some slight changes:

import math
import matplotlib.pyplot as plt

def cosine_response(lo, hi, step):
xs = []
ys = []
cur = lo
while cur <= hi:
xs.append(cur)
ys.append(math.cos(cur))
cur += step
plt.plot(xs, ys)


Hooray, now we can plot cosines, too! Oh, but maybe there's another thing we want to plot, so let's do it again:

import math
import matplotlib.pyplot as plt

def square_response(lo, hi, step):
xs = []
ys = []
cur = lo
while cur <= hi:
xs.append(cur)
ys.append(cur**2)
cur += step
plt.plot(xs, ys)


And so on and so on...

This process is very tempting, but it results in a lot of repeated code! And then what happens when we want to change the behavior of this function, or we discover a bug? Now we have to remember to make the necessary changes in each of the similar functions we've defined above!

But we can do better here! An important thing to notice here is that each of the above functions is doing the same operation: it is looping over input values, performing some operation on each input and storing the results in a list; and then, finally, plotting the results.

The high-level idea here is that we would like to reorganize things so that the common behavior exists only in one place that we can repeatedly invoke but the specifics can be altered. One way to do this is shown below:

import math
import matplotlib.pyplot as plt

def response(f, lo, hi, step):
xs = []
ys = []
cur = lo
while cur <= hi:
xs.append(cur)
ys.append(f(cur))
cur += step
plt.plot(xs, ys)


Notice that here, we're specifying the function we want to plot as a Python function object! With this structure, the process of plotting a new function is easier, more concise, and far less error prone than our original version! For example, with that helper function in hand, the following code is all we need to plot several different functions:

def square(x):
return x**2

response(square, 0, 5, 0.001)
response(lambda x: x**3, 0, 5, 0.001)
response(math.sin, 0, 10, 0.01)


Which is a huge improvement over the repetitious code we started with!

So here we've seen an example of leveraging first-class functions as an organizational tool, and we'll see more examples of this idea in an upcoming lab and recitation.

## 5) Understanding Last Time's Mystery§

In last week's readings, we looked at the following piece of code as an example of code that is difficult to understand:

functions = []
for i in range(5):
def func(x):
return x + i
functions.append(func)

for f in functions:
print(f(12))


It is somewhat surprising that, despite the looping structure here, when we run this code, we see five 16's printed to the screen! Despite the surprising nature of this example, though, we now have all of the tools we need in order to make sense of this example and to understand why it behaves the way it does. We'll walk through an environment diagram to explain this behavior, and you're strongly encouraged to follow along (and to reach out for help if any of the steps are unclear!).

We'll start by drawing the diagram just for the first segment of the code (lines 1-5, where we are building up the functions list). Again, we encourage you to try to stay one step ahead of the drawings below (that is, try to draw out how things will change during each step, then click ahead and compare your work against our diagram).

Explanations go here.

## 6) Closures§

Now that we've explained the interesting phenomenon from last week's readings, we'd like to wrap up by trying to "fix" it (presumably, the person who wrote that code did not intend to see five 16's, but rather some number that is changing, i.e., the intent was probably to create five noticeably different functions: one that adds 0 to its input, one that adds 1 to its input, one that adds 2 to its input, and so on...). Before we can get there, though, we're going to introduce one more bit of terminology. This section is not about introducing a new rule for how function objects behave (we've already covered all of them, in fact!) but rather a powerful effect of those rules. Importantly, a function object "remembers" the frame in which it was defined (its enclosing frame), so that later, when the function is being called, it has access to the variables defined in that frame and can reference them from within its own body. We call this combination of a function and its enclosing frame a closure, and it turns out to be a really useful structure, particularly when we define functions inside the bodies of other functions. Let's explore this idea by example.

For this example, please watch the following video, which talks through a couple of examples demonstrating the idea of a closure:

Speed:

## 7) Fixing the Mysterious Code§

Using this idea of a closure, we can fix the mystery code from earlier! The code below resolves the issue (at least insofar as preventing the output from all of the functions from being identical!) by evaluating i each time through the loop and setting up a closure for each of the functions we add to the functions list, such that, when each is called, it has access to a variable storing the value that i had when that function was created.

def make_adder(n):
return lambda x: x + n

functions = []
for i in range(5):

for f in functions:
print(f(12))


When this program is run, what will its output be?

## 8) Summary§

We've covered a lot of ground in this set of readings, and we've talked about a few different things, but our main focus throughout was on functions. We started by seeing a couple of examples of how we can use functions as an organizational tool, by building up meaningful abstractions for ourselves.

Next, we went down into the weeds a little bit, going into detail about the rules that function objects follow, including discussing both what happens when we define a function and what happens when we call that function.

Finally, we did pull back a little bit and look at some of the interesting behaviors that follow from these rules, as well as how we can take advantage of these behaviors in our own programs.