[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module of Part A. Part B assumes successful completion of Part A. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.
Optional: Are Closures Efficient?
Loading...
From the course by University of Washington
Programming Languages, Part B
346 ratings
From the lesson
Section 6 and Homework 5 (Second Module with Racket)
Welcome to the second week of Part B where we will focus on (a) building data structures in dynamically typed languages and (b) implementing programming languages with interpreters. Most of the programming assignment is focused on (b) -- implementing a small programming language that has function closures. As usual, start with the welcome message and enjoy!
Meet the Instructors
Dan GrossmanProfessor
Computer Science & Engineering
>> [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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
