Closure Idiom: Currying

Loading...

From the course by University of Washington

Programming Languages, Part A

869 ratings

University of Washington

Programming Languages, Part A

869 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] In this segment we're going to start our study of currying, our next

closure idiom. It's one of my favorite things to do in

functional programming. and this is a new way to deal with

conceptually multi-argument function. So you might remember that in ML, every

function takes exactly one argument. We worked around this previously by

passing n arguments as n different pieces of a single tuple.

So another way we could do it which is called currying, is to take one argument

and return a function that takes the next argument and it we'll still be able to

use the first argument, because it will be in its environment.

This is called Currying after the name of the person just as a funniest side, I

actually spent years of my life before I knew that, trying to figure out why it

was called currying, and of course, I was never successful.

So, let me show you an example in the code of how this is going to work.

So, we are going to stick with a very simple example in this section of just a

function that takes three arguments conceptually, x, y and z and sees that

they're sorted. So in terms of tupling, just take a

triple, pattern match against it like this, and return true or false based on

is z >= y and is y >= equal to x. And we would call that tupled function

with a triple like 7, 9, 11. So here is a new way to do it that at

first will seem very ugly, but then I will show you some syntactic sugar that

will perhaps make it even cleaner, even more pleasant than the tupled version.

So let's just make a sorted3 function that takes in an x and returns, these

parentheses are not optional or are optional, so I'm going to take them out,

a function y that when you call it, returns a function z, a function that

takes a z, and when you call it says z >= y and also y >= x.

Now that looks a little funny too, we could have instead said it fun sorted3

taking an x and then return a function y that when you call it, takes a function z

and so on. That's exactly the same thing so maybe

the val version will be a little easier here.

And now, what we can do is we could call sorted3 with a number, like 7 and that

would give us back a function, right? If we call this with x, we're going to get

back this. So what we could then do is call that

function with 9 and that would give us back this function,

and then we could call that with 11. And this will absolutely work and should

even give us the right answer, so let's see.

sure enough I have some lower stuff in the file, ignore that.

sorted3_tupled takes a tuple of ints and returns a bool.

t1 was true. Sorted3 takes an int,

returns a function that takes an int, and returns a function that takes an int, and

that all returns a bool, and then we did use it correctly, and so

t2 is true. So let's take a closer look at what's

going on, because that looks awfully complicated.

It's all the same semantics, we already know about closures.

So when we called (sorted3 7), we got back a closure.

Remember, a closure has two parts, a code and an environment.

The code is just the body of the function we called fn y, fn z, z >= y, and also,

that's the function we got back, we called with (sorted3 7).

It returned this function that takes y and the environment for that closure is

that x maps to 7. So when we call that closure with 9, we get back a closure

whose code is now fn z, z >= y and also y >= x, because that's what the result is

of calling the function with y to 9 and in the environment, x maps to 7 and y

maps to 9. So when we call that closure with 11, we

evaluate the and expression, and we get back true,

that's all there is to it. And, while the semantics may seem

complicated, it's just closures which we get used to.

And since currying is such a common pattern, such a common idiom,

we don't think through it on this level every time.

We just say oh, I'm using currying, so it's like a multi-argument function.

And, so now, let's make it even more pleasant to use by pointing out some

syntactic sugar that we happen to have in ML.

So, it turns out, the first thing we can clean up is this call.

Okay? So we don't need all these parentheses.

In general, if you just leave the parentheses out with spaces between

arguments, the parentheses go in to organize things

to the left. So if you just write sorted3 7 9 11, it's

calling sorted3 with 7, getting back a function and calling it with 9, and

getting back a function and calling it with 11.

So we don't need those parentheses. We can go back to our code here and instead,

just say val t3 = sorted3 7 9 11. And now if you compare this to calling a

tupled function, it's actually fewer characters, more space characters, but

less clutter on the screen, so that's actually kind of nice.

And this is a good time to point out that you have a curried function, like

sorted3, you can call it either of these two ways.

If you have a tupled function, you can only call it this way,

you can't mix and match, right? If you want to call a function

that takes a tuple, you have to pass a tuple.

And if you want to call a function that takes, that's curried, you have do via

via a sequence of calls. So you can't, for example, write

sorted3_tupled 7 9 11. That's going to try to call

sorted3_tupled with 7, you'll get a type error immediately,

because you're not passing a tuple where you need it. And similarly, you cannot

call sorted3 with a tuple, you will also get a type error. It doesn't expect a

tuple, we can see here in the greater than, y >= x, that x needs to be an int

and not a triple int, so we better comment all that out.

Okay? So, so far, so good. That's the first step of syntactic sugar,

is that callers can just think oh, it's curried and takes three arguments.

I'll just separate them by spaces. It's also easier to define curried

functions than I've suggested, that you don't have to write all these

anonymous functions that return other anonymous functions.

That you can, or syntax for function binding has built in support for

currying. So, I have the definitions here written

on the slide, but it is sometimes easier just to show an example.

Here is another definition of sorted3, which I'll call sorted3_nicer.

If you just separate multiple patterns in general, here just variables, before the

equals, this means curried Alright? So y >= x, and so, compared to our

previous version here, these are exactly the same,

this is syntactic sugar for this, although, because we used fn, we could

also use recursion, we don't need recursion here.

So given this that's a much nicer way to write the function, and we can continue

to use it using our syntactic sugar, and that is a really nice way to think of

multi-argument functions. Just the caller, separated them by

spaces, the callee and the caller, separated them by spaces, but what is

going on semantically is closures, functions returning other functions,

the rest is just syntactic sugar. I would point out that because this is

just syntax, you could call sorted3_nicer with all these parentheses, because this

means exactly the same thing as the line and a buff, 'kay? So that is what most of

what I wanted to show you. Remember here, over in the over in SML,

in ripple, that these tupled functions will print their arguments looking like

this, sorted3_nicer, we'd have exactly the same

type. Remember, the parentheses go to the right

here, so this says, I'm a function that takes

an int and returns an int -> int -> bool. meaning that you passed that function in

int and you get back a function, you pass that function in int and you'll get back

a bool. So as you can, here in the alpha to the

ripple, I had one more thing I wanted to show you,

which was a fold in a curried form. So we've seen fold before, it was a

couple of segments ago. Here is a version that takes three

curried arguments using our syntactic sugar. So this first line right here that

I'm highlighting, means exactly the same thing as on a function fold that takes f

and returns a function that takes the accumulator.

If you call that, it returns a functions that takes x's and this is its body. And

you'll notice that here in the recursive call, since I have a curried function, I

need to pass those arguments separated by spaces and I've done that.

Here is the first argument, here is the second argument, and you need

these parentheses so that you know where the second argument ends and this third

argument begins. So that's a perfectly fine curried

function. Here is a use of it.

Here is a function that sums all the elements in a list by just calling fold,

which here is curried. Here's the first argument, space, second

argument, space, third argument, exact same semantics as sorted3,

just more useful. So, coming back here, in terms of

sorted3, our final version here is really very elegant.

It's actually fewer non-space characters than the tupled approach, the approach

that used tuples, and we just know that it's syntactic

sugar for this bottom version, which is easier to understand what's going on.

But once you get it, once you go oh, that's what curring is doing,

then you just think of it as a three argument function, like we've thought of

tuples as multi-argument functions. And then for fold, we just write it this

way to begin with. It's just as elegant.

We think of fold as a three argument function and we call it with three

arguments.

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