Lexical Scope

Loading...

From the course by University of Washington

Programming Languages, Part A

834 ratings

University of Washington

Programming Languages, Part A

834 ratings

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. 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. The three parts are not quite equal in length: Part A is almost as substantial as Part B and Part C combined. 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 3 and Homework 3 -- and Course Motivation

This section is all about higher-order functions -- the feature that gives functional programming much of its expressiveness and elegance -- and its name! As usual, the first reading below introduces you to the section, but it will make more sense once you dive in to the lectures. Also be sure not to miss the material on course motivation that we have put in a "lesson" between the other videos for this week and the homework assignment. The material is "optional" in the sense that it is not needed for the homeworks or next week's exam, but it is still very highly encouraged to better understand why the course (including Parts B and C) covers what it does and, hopefully, will change the way you look at software forever.

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

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

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