Explore
For Enterprise
Join for Free
Log In

Browse
Search
For Enterprise
Log In
Join for Free

Implementing Closures

Loading...

Programming Languages, Part B

University of Washington

4.9 (469 ratings) | 13K Students Enrolled

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

Skills You'll Learn

Racket (Programming Language), Programming Language Concepts, Type System, Functional Programming

Reviews

4.9 (469 ratings)

5 stars
440 ratings
4 stars
27 ratings
3 stars
2 ratings

KR

Mar 23, 2018

I'm a pretty experienced C/C++ programmer and this course has been a brilliant introduction into functional programming and the underlying philosophies underpinning programming languages in general.

JM

May 09, 2018

DO THIS COURSE. It brings together everything in part A. In particular, the final shorter week on the differences between Statically and dynamically typed languages is mind-bending and brilliant.

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

Taught By

Dan Grossman
Professor

Transcript

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

© 2019 Coursera Inc. All rights reserved.

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government
For Campus

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates