[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.
Dan GrossmanProfessor
