[MUSIC] In this optional segment, I'll discuss a little bit more how we could implement closures in a way that would be more efficient in practice than the way sketched in the previous segment. So first, let me emphasize that what we're doing is not particularly expensive. When we build a closure, we're just calling a constructor and initializing two fields. And when we're calling a function, we're just doing a couple things to pass the right environment to our interpreter function. So, the time is actually quite cheap. The problem with the way we're implementing closures is actually one of space. That what we're doing is restoring with the closure the entire environment at the point where the function was defined. So our different environments are actually sharing quite a bit because we're representing them as lists. But those lists themselves are not how you would want to do it in a more efficient implementation. Because it takes too long to look up variables if you have to walk down a list. So the sharing is a little more difficult to get right in a more realistic setting. But the more problematic issue is just keeping things around that we don't need. That storing everything in any environment for any closure we might possibly use in the future could end up keeping around a lot of data in our program that we don't need anymore. So an alternative that you can basically assume is used in practice in a language that supports closures is that when we create the closure, we need not store the entire environment. It suffices to just store a smaller environment. An environment that only contains those variables that the code in the function might possibly use. And those variables are known as the free variables. Not free as in don't cost anything. Free as in not bound, not defined themselves in the function body. So, the free variables by definition are just the variables that are used somewhere in the function body, not counting anything defined in the function, in the function parameters or any local variables. And the neat thing about free variables is it is sufficient to store in the closures environment bindings for all the free variables. Nothing else could ever possibly be used by the function when you call it because it doesn't include the variable in the body. So let me show some examples. It turns out that you can look at a function, and via simple recursive procedure over it, compute its free variables. So in this first example, I have a zero argument function. It adds x, y, and z. Those are all free variables. They are variables that occur in the function body without being defined in the function body. In the second example, since x is a parameter, the three variables, which I'm always writing here a comment on the right, are just y and z, but not x. In the third example, it's the same. The three variables are y and z. Now whenever you call this function, you are going to use y or z, never both. But the free variables are anything that might be used. We need to keep in the environment anything that ever could possibly be looked up when this function is evaluated. And so we need both y and z to be the free variables. Notice it's only things that are defined outside the function body. So in this fourth example, where y is now a local variable and x is a parameter, the free variables are only z. So it's the set containing just z. In this second to last example, there are no free variables. In fact, that's fairly common. All the examples I showed you before we got to closures, when we were just doing first class functions that were not closures, all had no free variables. This is what you have to do if you are in an impoverished language, where functions are not allowed to use variables outside of their definition. It's fairly common to have no free variables, although if you're referring to earlier bindings in the file, even if they are at top level, those tend to be things that are your free variables, and therefore need to be stored in the environment created with the closure that you create when evaluating the function. Finally, in this last example, is a little more sophisticated just to emphasize that you need to take shadowing into account. If I look at this function, x is definitely not a free variable because it's a parameter. Y is because of this first use of y here. The fact that there is a local variable y means that these later occurrences of y do not count for y being a free variable. But this earlier one does, so y is one of the free variables of this function. So is z, because I use z right here and z's definition would be somewhere outside of the function. So that should give you a sense of how you could compute the free variables. Let me emphasize that what interpreters do not do, is every time they create a closure, look at the function's body to find all the free variables. That would be fairly expensive. If you had a big function, you would have to run over the syntax of that function at run time to find the free variables. That doesn't make sense as something to do. Instead, there's a pre-pass. Something you can think of as part of a compiler step if you like, that before evaluation begins, before we start interpreting the program, we go ahead and look at every function in the program, compute that function's free variables once, and store this information somewhere convenient, such as with the function itself, or perhaps you could do it on the side in some sort of table that had an entry for every function in the program. So that when you then get to that function, you have stored somewhere, okay, the free variables are x and y. So I need to look up x and y in the current environment and use that to create a smaller environment to store with the closure. So doing this will take a little bit more time than the approach we're taking of just take the entire environment and put it in the closure. But it's worth it, because of the space savings that you get as a result. I should also add, by the way, as I mentioned before, that you can't look up variables efficiently by storing them in a list, like we are in our homework assignment. You really want them in something that supports faster look up time, such as a balance tree or a hash table. But that's a simple matter of swapping in a more efficient data structure for representing environments. All right, so that was all optional, this last slide is even extra optional, if there is such a thing. Which is, if you don't have an interpreter at all and you're actually compiling from a language with closures to a language without closures, then what do you do? You don't have an interpreter anymore that takes in the environment as a parameter. So what you have to do is take every function in your program and compile it such that in the target language, it takes in an extra argument. If it used to be an n argument function, now it's an n plus one argument function, and what you do is pass the environment as that extra argument. So what we do is we translate our entire program such that every function takes one more argument, and every function call passes one more argument. And if you do that consistently in your entire program, then the program itself is maintaining the environment. Passing it everywhere it needs to go into every function, at every call site. And this is a byproduct of how we've done the translation step so that the program itself is keeping track of environments. So when you do it that way, you have to also change how you translate variables. So any use of a variable, just some use of x or y inside of a function, now can't look up x or y, it has to look up x or y in that extra environment argument. And you need to compile the code in such a way that says, this used to be a use of a free variable. So I will now look up that variable in this extra argument that was added as part of the translation step. So those are the main changes. What's still the same is when you have a function value, you do still create a closure. You take the current environment, which is now just an argument that was passed to the current procedure that's executing, and the function body and you do still build a closure. So that part is still the same. In general, I hope this gives you a little more sense that the way we're implementing closures is sufficient. It's not too far off from how it's done in practice, but I wanted to give you a little insight into how things can be done more efficiently, so that you weren't left with the impression that any implementation of closures has to be inefficient.
