Lexical Scope and Higher-Order Functions

Loading...

From the course by University of Washington

Programming Languages, Part A

796 ratings

University of Washington

Programming Languages, Part A

796 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] Okay, I want to continue our discussion of lexical scope.

Now, I am going to pass into the discussion, functions that take and

return there functions. So, the rule is not going to change.

The rule is the way always evaluate the function body in the environment where

the function was defined. At the point we created that function, we

made a closure with the environment, we had at that moment.

And that's the environment we used when we later called the function.

So, nothing is going to change here except what the environment is, is going

to be much more interesting because we're going to have nested let expressions,

we're going to take functions, we're going to return functions.

So, in this segment, I'm going to do two examples that are a little bit

complicated and are silly, and they're not going to motivate the semantics.

And then in later segments, we'll get to why you want the semantics and how it

lets you do powerful things, okay?

So, let's go to the code. here's our first example.

Let's just walk through it line by line. So, we start with an environment where x

is one, this is going to turn out to be irrelevant, because we're going to end up

shadowing x anywhere before we could possibly use it.

Then on this next line, we're defining a function y and this, oh, sorry function

f. And this function f returns this

anonymous function right here. So, let's just look at this function.

And the great thing about lexical scope is we can figure out what this function

does completely separate from the rest of the file and how it's potentially called.

So, the function f takes an argument y, creates a local variable x that holds y +

1. So, that's going to shadow in here, this

outer x, that would have been in the environment but, of course, it's shadowed

in the body of this let expression. We then return this function,

alright? So whenever you call f with some y, this

is going to take z and return in terms of f's argument, 2y + 1,

right? Because x is y + 1 and we're adding x and

y and z together. That is what it will always do because

the environment where this function was defined had whatever y maps to based on

the call to f and then x-mapping 2y + 1. So let's see that in action with a use of

f and a use of the function that's returned.

Down here, I'm going to have val x = 3. This will again be irrelevant.

I'm just putting it here to show that it's irrelevant.

[SOUND] And the reason why it's irrelevant is right here I call f with

four, okay?

So, this is going to return a function [SOUND] that adds 9 to its argument.

[SOUND] The reason why it's 9 is because 2Y + 1, where y is four, is nine.

We call f with four, so we go up to the body of f right here,

y is four, we create an environment where y is four and x is five and we return a

function that when called will use that environment, extended with whatever z

maps to. So sure enough, right here where I call

g, the function returned up here, when I call g with six, I will get 15

because that is 9 + 6. The fact that this y is five here, also

irrelevant. The same way that we're not going to use

the fact that X is three, when we evaluate this x plus y plus z, we're not

going to use this y = 5. When we evaluate this x plus y plus z, we

use the environment where the function was created,

y is four, x is five. If we had another call to f down here

with a different argument, that would create a different closure with a

different environment, one where x was, oh, sorry, y was eight, and x was nine,

so that would return a function that always added 17 to its argument, okay?

So, that's our first example, let us now go to our second example.

In the second example, we're going to pass in a function to a function rather

then returning a function from a function,

alright? So, here is our function f that takes a

function g. And all it does is call g with two.

the rest of this is more irrelevant clutter.

And, in fact, let's look at function F.

And again, the advantage of lexical scope is we can understand a function just by

looking at its definition and what is in its environment.

We never have to look at how it's called. So, if I look at this function, I say,

oh, it takes a function g and it calls it with two.

And, in fact, the rest of this is, I mean, I'm just defining a variable that's

never used so I would very naturally just come in here and delete all these.

I'm, and, it just, I'm commenting it out here so you can still see it, but that

should be exactly the same function, a function that takes its argument and

calls it with two, is the same as a function that defines a local variable x

to be three and then calls g with two. So, the great thing about lexical scope

is you can do this kind of code maintenance and know that its never going

to change how the function behaves. Let's see that by following through with

an actual call. So here, I have val x = 4.

And now, I create a little function here, h. So, this function is always going to

add four to its arguement. Why?

because it's the same thing at top level. When I create this binding h, I create a

closure that has it, the current environment where the function was

defined. And then at this point, we have an

evironment where x is four, so h is bound to a function that will always add four

to its arguement. So now, we got to the exciting last line

where we're going to call f with h. So, I'm going to look up f and I'm going

to get this function that always calls its argument with two.

And I'm going to pass in h, which is a function that always adds four to its

argument. So, I will get six,

I will not get seven. Seven is what you would get if you passed

in this code, which has body xy. + y.

And then here said, oh, now, I want to look up x in this environment.

But that's wrong. We always look up x in the body where the

function we're calling was defined. And here, we pass for g the function h,

that's this function. We looked up h in the environment, we got

this function that adds four to its argument and so we get six,

alright? So, those are our two complicated

examples. If you don't believe me, feel free to go

back through them more slowly. Try them in the read–eval–print loop.

See what the different variables are bound to at different points.

The remaining slides here have the exact same examples and a little bit more text

to walk you through it. So, this was the first example we did

when we ended up with 16, and this is the second example where we ended up with six

bound to z. So now, that we hopefully understand

lexical scope and believe me that we didn't change the rule in this segment,

it's the same rule we had before, we can move on to discussing why you want

the semantics for your programming language.

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