Implementing Closures

Loading...

From the course by University of Washington

Programming Languages, Part B

372 ratings

University of Washington

Programming Languages, Part B

372 ratings

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

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!

Datatype-Programming in Racket Without Structs13:21

Datatype-Programming in Racket With Structs9:34

Advantages of Structs8:13

Implementing Programming Languages10:07

What Your Interpreter Can and Cannot Assume13:47

Implementing Variables and Environments6:29

Implementing Closures6:32

Optional: Are Closures Efficient?9:03

Racket Functions As “Macros” For Interpreted Language9:15

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

>> [music]. So, at the end of the previous segment, I

said that was everything you needed to know about environments.

And I realize that's not entirely true. The most interesting part of your homework

assignment. The most interesting part of many

programming languages, is implementing closures.

And I want to show you how to do that. I hope you really enjoy this cause I think

it's the most interesting and mind bending part of what we do in this part of the

course. And that's that the language is going to

have first class closures. So you're going to be able to write map

and filter and call them with closures. We're going to implement lexical scope of

course, because that's the appropriate semantics.

And we need to learn how to do that. Fortunately what you have to implement, is

what we have been stressing. How closures work.

I just need to tell you a little bit about how to code them up.

And again the strategy here is I'm just going to do this in English and in power

point. It'll be your job to translate the ideas

into the racket code you're using to write your Interpreter.

So, the magic question is this. We know, thanks to lexical scope, that

when we evaluate a function body. We use the environment where the function

was defined extended to map the argument to the actual result.

So, how are we going to have that environment around?

Our interpreter only takes as an argument the current environment, it does not take

as an argument the environment where the function was defined.

So here is the trick, if you will. The lack of magic is when we define a

function, we will create a closure that includes the environment.

So later when we use that closure We have the environment stores away and we can use

it appropriately. So, when we have our language definition

we have all the structs that programmers use to write their programs.

And then we'll have 1 more, 1 that they should not use in their source programs.

You can use it for testing things out if you like.

And that's the struct closure. It has two parts.

Yes, it has the function that's going to include the argument, and the body for the

code, and all the code parts of the closure.

But then we also store the environment. So here's what happens.

A closure is a value. So like all values, if you have a closure,

your interpreter should just return it. But a function is not quite a value, we

often say that functions are values but really closures are values when you go to

interpret a function you have the current environment You have this function.

Make a closure out of both of them. So now, you return that.

And this closure carries with it, its own environment that we will use later when we

use the closure. So, that is how you interpret.

Functions. The only other thing I have to tell you is

how to interpret a function call. Right?

So now, we handled the function case of our interpreter.

Now what happens when you actually do a call?

So let's do that, and that's all there is to it.

Suppose you had something like call of expression 1 and expression 2.

So expression one should evaluate to some closure.

Expression two should evaluate to some argument.

We should call the closure with the argument.

Okay? So the first thing we need to do, like

many things where we have sub-expressions, is evaluate them.

So use the current environment to evaluate e1 to a closure.

It's an error if you don't get a closure back cause that would be trying to treat a

number as a function or something like that.

And use the current environment to evaluate e2 to a value.

Just normal recursion so far. Now, we have a closure and an argument.

What we need to do next is evaluate the closure's function's body.

Using not the current environment, but the closures environment.

The other thing that is stored in the closure.

We're going to start with that environment, then we'll extend it to map

the functions argument name To the value we have, the result of evaluating e 2.

And, the way we're going to deal with recursion on the homework assignment,

because our functions can be recursive, is we'll go ahead and further extend the

environment. For the purpose of recursion to map the

function's name to the entire closure. Not just to a function but to the entire

closure, because we still need that current environment.

So, that way. When we go to evaluate the closure's

function's body, any variables we look up, will either be the function argument.

And that will be map to the right thing, or we'll use the environment back when the

function was defined. And the only thing left is this little

work around for recursion. If inside dot functions body you want to

recursively call the function, you should use the same closure.

And so that's why we'll map the functions name for the purpose of recursion to the

entire closure. That's what you need to do, rather than

just thinking of it as, let's take what Dan said and try to code that up even

though I don't understand it, I encourage you to actually understand it.

To appreciate that this is the same semantics we learned a few weeks ago.

Back when we learned closures I told you that a closure was a pair.

Well, the struct for closure has two fields.

That's like a pair. There's the code part and there's the

environment part. And the reason why closures are not magic

is when we create a closure, we store the environment.

And then, when we use a closure, we use that environment for evaluating the

function's body. Notice that, given a closure.

That is the only environment we will ever use to evaluate that function's body with

that closure. But every time we evaluate a function

definition, a function that gets return, we create a new closure using whatever

environment was current back when we evaluated that function.

And that is the quote unquote magic of implementing high order functions.

Once you implement it in your programming language, you'll be able to use high order

functions, closures, variables that are not defined in function bodies and all the

wonderful other things we've been studying with closures in our functional

programming languages.

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.

Download on the App Store

Get it on Google Play