[MUSIC] So it turns out that first class functions are a lot more powerful than we've seen so far. But before we can understand that, we need to take a step back and carefully reason about this idea called Lexical Scope. So we're going to start that here. So, this is a very important concept, but it's not actually anything new. It's something we just need to focus on and reconsider now that we have higher rare functions. We know that a function body can use more than just its arguments and any local variables it defines. It can use anything already in the environment, anything in scope. But the question is which scope, which environment and the answer in almost all programming languages these days is Lexical Scope that we use the environment where the function was defined not the one where the function is being called. Alright. There are lot's of good reasons for the symantecs, which we'll get to in the next segment. We'll even later in the course learn how to implement the symantecs, which you will do on one of your later homework assignments. But, at this point, we just want to make sure we understand what the rule is and the way Lexical Scope works. This is one of the most important concepts in the course, because we need it to use first class functions as properly and as powerfully as we can. So let's look at an example, and I'll do this with the code. Alright. this example doesn't actually have high order functions in it, but we can still see Lexical Scope being used. So, here after line one, I have an environment where clearly X maps to one. So, in the next line when I add F to my environment, I'm not going to repeat X, I'll just add F here. F maps to a function that adds one to its argument. And that is because whenever we call this function we're going to valuate this body, X plus Y, in an environment that we have when the function was defined. And when we defined this function, we had an environment where X maps to 1. So this function that f maps to always adds one to its argument, no matter where it is called. That is the rule. So, now lets see what happens, here on line three, I shadow X so in this environment X maps the two that has no effect on F, has no effect on the environment where F was defined. Clearly here, we now have an environment where x still maps to two, and y maps to three. So now we get to the all important call here. We look up F in the environment, we get the function that adds 1 to it's argument. We look up X we get 2, we look up Y we get 3. So we call the function defined on. Line 2 with 5, because we looked up X and Y here in the environment at the call site. But then when we make the call, we pass 5, we add 1 to the argument, and so in the end, Z maps to 6. That's the essential part. If you thought Z was going to map to 7, you're using a different rule, which is not how ML works, and not how most programming languages work. Okay. So that is the key idea and the key example for this segment. Now let's go back to the slides. Here I've said the same thing we just talked about. The point is that on Line 5 we evaluate X + Y in the current environment at Line 5 which gives us a 5 but then when we call the function, we evaluate that function body, the X + Y on line 2 in the old environment where X maps to 1, extended with Y, of course, mapping to 5 because that's how function arguments work. So this is why we need function closures, which we have not talked about before, in our language. Right? Because you might be thinking, that seems a little magic to me. How can a function be evaluated in an old environment that isn't around any more? Once we've shadowed X, how can that body of F use the old X? And the fact of the matter is it's not magical because the language implementation, the ML interpreter and compiler and whatever else that implements ML has to keep around those old environments so that we can implement Lexical Scope properly. So the way to think about the semantics of functions in general, is that we know functions are values. We can pass them around however we want. But a function value actually has two parts. So far we've only been talking about the code part which is sort of obvious. You can't have a function without a body to that function. But a function value, this closure has a second part. It has with it the environment that was current when the function was defined. So we really have a pair. It's not an ML pair. It's just something with two parts, and they, and those parts are the code and the environment. This thing is called a closure, and when you call a function, you're actually calling one of these pairs, one of these closures. And what you do is you evaluate the code using the environment. So you use both parts of the pair and that's how a function call actually works. So in our example we can now go back to it and see what actually happened, another way to reason about the semantics, which is at line two we created a closure, and that closure had a code part that said give me an argument why and I'll evaluate the code X + Y. And it had an environment part that said that I will evaluate that code in an environment where X maps to 1. So then when we did the call on Line 5 we passed to that closure the argument five, two plus three and then the result of the call used the code in the closure and the environment in the closure with the one addition that Y maps the 5 for the function argument. And that is once again why we got 6 back, alright. So that is Lexical Scope and that's how closures implement Lexical Scope and that's how you can think about the functions we're going to be passing around in ml. So to give you a bit of an outline of where we're going from here that is the rule of Lexical Scope. Now what I want to do in the next segment is continue with these sort of silly examples, but examples that use functions, taking functions, or functions, returning functions because that shows that its a pretty powerful feature, its may be a little harder to reason about, so I want some more advanced silly examples. Then we'll get to the why. Why would you implement, why would you want the semantics of your language to have this Lexical Scope. We'll contrast it with the other possibility which is called dynamic scope. And then we're going to talk a lot about programming idioms. How once you know that a language has Lexical Scope, there's a number of very powerful things you can do with first class functions that rely on the fact that we have Lexical Scope.
