>> [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 an constructor and int, initializing two fields. And when we're calling a function we're just doing a couple of 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 we're storing 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, alternative that you can basically assume that's 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. 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 variables that are used somewhere in the function body. Not counting anything defined in the function. 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 free variables. Which I'm always writing here over here in comment on the right are just y and z, but not x. Alright. In the third example it's the same. The free 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're 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're 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, this last example's 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, we could 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 is every time the create a closure. Look at the functions 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 variable. 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 functions 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. They 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. Okay. So doing this we'll take a little bit more time, than the approach we're taking of just, put the, 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 lookup 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. Alright 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 into, 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 1 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 by-product 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 the 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 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 closure is has to be inefficient.
