Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Optional: Java Without Closures

Loading...

Programming Languages, Part A

University of Washington

4.9 (1,058 ratings) | 64K Students Enrolled

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.

Skills You'll Learn

Recursion, Higher-Order Function, Pattern Matching, Functional Programming

Reviews

4.9 (1,058 ratings)

5 stars
999 ratings
4 stars
52 ratings
3 stars
1 ratings
2 stars
1 ratings
1 star
5 ratings

AL

Mar 22, 2017

Great course!\n\nI think this course has just the right balance of theoretical background, formal definitions, and actual examples to make "just right".\n\nThanks Dan, and everybody else involved!

MK

Jun 17, 2017

Good fundaments for learning new programming languages. Well prepared and challenging homeworks. I learned a lot of functional programming concepts fom this course and I am sure I will use them.

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.

Introduction to First-Class Functions7:50

Functions as Arguments8:40

Polymorphic Types and Functions as Arguments7:57

Anonymous Functions9:17

Unnecessary Function Wrapping5:05

Map and Filter8:56

Generalizing Prior Topics9:01

Lexical Scope7:22

Lexical Scope and Higher-Order Functions7:37

Why Lexical Scope11:44

Closures and Recomputation6:30

Fold and More Closures11:28

Closure Idiom: Combining Functions9:18

Closure Idiom: Currying10:32

Partial Application9:41

Currying Wrapup6:40

Mutable References8:07

Closure Idiom: Callbacks8:25

Standard-Library Documentation7:00

Optional: Abstract Data Types With Closures11:16

Optional: Closure Idioms Without Closures4:48

Optional: Java Without Closures12:08

Optional: C Without Closures10:56

Taught By

Dan Grossman
Professor

Transcript

[MUSIC]

In this optional segment,

we'll see how to use objects in a language like Java to simulate closures.

It won't be pretty, but

we will be able to successfully port the ML code from the previous segment.

Just to be fair to Java, the next version of Java, Java 8, is supposed to have

closures that are much easier to use, and very ML-like, if you will.

Many languages that also support object-oriented programming these days

also have closures.

This is a great bit of progress for programming languages and software.

And you'll be able to write convenient things using map and filter and

length in a reasonably object-oriented style.

This was done for a number of reasons.

I won't claim to speak for the designers of Java, but

it's going to make using collections easier.

It's going to encourage a style that has less mutation.

Which will make it much easier to write parallel code in Java.

So for a number of reasons, after 15 to 20 years of living without it,

Java programmers will have closures.

But that's not really the point of this segment.

The point of this segment is how could you take a language with classes and

objects like the core of Java is, and write code like the ML code we saw in

the previous segment, if that's what we wanted to do.

Now, there are perfectly fine,

decent list libraries in Java that are not written in this style.

They're not about map and filter and closures and things like that.

They're in a more object-oriented style, they use more mutation, and that's okay.

But we're interesting in seeing what our ML code would look like using

Java's language constructs.

So the key technique to fake closures,

if you will, is to define interfaces with one method in them.

because a function is a lot like an object with one method.

You can just call a function.

So for example, here's a generic interface in Java using the generic type

parameters A and B for alpha and beta.

It just has one method.

So anything implementing Func of type one and

type two is something that is a method.

That takes a type one and returns a type two.

And we'll be able to create objects that implement that interface, and

then those objects will act like functions from the argument type to the result type.

We will have to put in those objects

fields that have whatever private data our closure would want.

Similarly, if we wanted a predicate, something that would turn true or

false given an argument.

Here's a generic interface that for some type A takes in an A and

returns true or false.

So the key is to implement these interfaces

with objects that have whatever fields we need.

So there you go.

So now with that background, and we'll get back to those in just a second,

let's just start building up our link list library.

And we'll start pretty much as you might expect for an object oriented library.

We'll create a generic type, List,

that's perameterized by the type of the elements of the list.

We'll have fields for head and tail.

And we'll have a constructor here that initializes it with the head for x and

the tail for xs.

Now, this constructor simply will not work for the empty list.

What should we do for that?

So here I'm going to make a choice that I'm going to regret in a couple minutes,

which is to have null represent the empty list.

It's a special constant in Java, this is fairly conventional that we'll use it for

the empty list.

So the empty list will not be an object.

It will not have a class, it'll be this special null constant.

And we'll see in a minute where that's going to get us into a bit of trouble.

Okay, so now what we're going to do is we're going to implement map,

filter, and length.

Those were the three functions in our library in ML for

this list type we've defined.

And I'm going to make them static methods.

And I'm doing this because of that decision for null.

Okay, so you see the code here, but it'll be easier to read and

highlight if I flip over here to emax.

All the Java code I've already shown you is up above.

And here is my method for map.

So this is the entire thing here, all right?

So static method, it is polymorphic.

It is generic in two types, alpha and

beta, because sure enough, the result type is a list of betas.

And one of the arguments is a list of alphas.

The other argument is one of these Funcs from alpha to beta.

Remember that interface that just has one method m.

And that method takes an A, or an alpha, and returns a B, or a beta.

So given these two arguments, and

that I want to return the appropriate list of betas.

At this point I can pretty much write the code like I do in ML.

If xs is null, the empty list, return null, the empty list.

Otherwise, return a new list of betas.

And I call the constructor, I build my new list out of f.m(xs.head).

So let's talk about that.

f is this function, that's an interface.

It has one method, m.

I pass it an appropriate alpha, I get back the appropriate beta.

And then let's just recursively call map with the same object for

the first argument and xs.tail, pretty much like the ML code does, all right?

So that's pretty nice.

Now you might argue, in Java we don't encourage so

much recursion because recursion is usually not as efficient in Java.

Particularly we do not have tail calls and things like that.

I would argue this is better than the alternative.

I encourage you to code up the version on you own that uses a while loop

instead of recursion.

Keep the pointer to the previous element.

It's a bit of a mess.

So I find this much easier to explain, reason about I prefer this version.

All right, so that's map.

Filter is fairly similar.

Filter takes a list of alphas and returns a list of alphas.

So it's only generic over one type alpha.

Its argument is not a Func from alpha to beta,

it's an implementation of the interface Pred of alpha.

But otherwise it's essentially filtering.

Again, the body of the function, once you survive the complicated first line without

any type inference, is not too bad.

If we have the empty list, return the empty list.

Otherwise, if taking this object, calling it's m method on the first

element of the list gives back true, then we want xs.head in our result.

So we return the new list of alpha with xs.head.

And then calling a recursive call to filter with the same Pred object and

xs.tail.

Otherwise, just filter(f,xs.tail).

And then finally, for length, that's the third function we needed.

I could again produce a recursive solution but

here actually the while loop version isn't so bad.

So I decided in porting my code to go ahead and just say static method,

return an alpha, length, take a list of alphas.

No closure needed, walk down the list setting xs = xs.tail, incrementing

variable ans, mutation, imperative update, and then just return ans, okay?

So that is my library.

Let's flip back to the slides here and

talk about why I made these static methods.

So a more object-oriented approach would be to make these instance methods.

That the class would have methods map, filter, and length that look like this.

They wouldn't take list arguments because the enclosing object, this,

would be the list.

So they would just take a function that took an element of type T,

the type of the list and returned a B.

And then we would make a list of Bs.

Similarly, filter will take a predicate over Ts and

length would take no arguments and just return an int.

The reason why this doesn't work very well is that it interacts poorly with our

decision to represent the empty list with null.

Now clients, users of our library, will not be able to take a list xs and

say xs.map or xs.filter if that list might be empty.

Because if you try to call a method on null, you get a null pointer exception.

I think every Java programmer ever has suffered through null pointer exceptions.

And we would force every client to check for null and

deal with the null cases themselves before calling map filter a length.

Whereas our static methods could handle the null case for them.

So it turns out, this is not picking on object-oriented programming.

The real problem here was our choice of using null.

In fact, a more object-oriented approach would be to not use null for

the empty list.

To instead have two subclasses of the list class,

one for empty lists and one for non-empty lists.

I have not written that code for you but what you do is you take the empty list

subclass, you implement map, filter, and length quite easily.

Map and filter just return another empty list.

Length returns zero.

And then everything works correctly.

And there is no problem with it, and I actually prefer that.

In my opinion, if you want to do object-oriented programming,

you need to rid yourself of the bad habit of leaning on null

when it gets you into trouble for a code like we're writing here.

All right, so now let's finish the story.

If you remember our ML code, we also had some clients of our library.

We wrote two functions, one that doubled all the elements and

a list mapping across it.

And the other that counts how many ends are in it.

Here is the code and it is admittedly a bit of a mess.

So let me explain what's going on.

When we want to call doubleAll, we want to define a doubleAll method,

I'm making it a static method here.

It wants to take a list of INTs or integers and return a list of integers.

All it's going to do when you call it is call list.map with xs.

And now what I need to do is pass in the appropriate object that is

acting like a closure.

So what I need to do is I need to make a new instance of that interface.

And I'm using here an anonymous inner class.

This, if you've never seen this syntax, it's mostly just syntactic sugar for

defining a class that implements an interface.

And then providing an implementation of the appropriate method.

But right here I'm saying, make a new object

that implements the Func interface for arguments integer and integer.

And let its method m take in an integer x and return x times 2.

So a lot of clumsy syntax, but it gets the job done, and

that will double all the elements in this list.

As for counting the ns, I can write the same code I wrote in ML.

I want to take the length of filtering to include only numbers that equal n.

I do the same thing where now I create an implementation of the Pred of integer

interface.

And the body of my one method m takes an x and just asks if x=n.

The one thing that's neat here, is in Java you can use this

n that is in scope here but only because it's declared final.

Java will not let you do this if n can be updated and

it's a longer story than I want to get into here.

But there are good reasons for it.

And so that's the end of our story.

So essentially what our clients do is if you want to map from a List<foo>

to a List<Bar> you define a class c that implements the interface Func<Bar, Foo>.

And use its fields to hold any private data.

Because we didn't need any of those fields,

we just used this anonymous inner class, which is mostly syntactic sugar.

And then we pass the resulting object to map, all right?

The count ns example is more interesting because we did need that

n in our environment.

We could have created a class with a field.

Instead, we did that trick that if you put final, you're okay.

All right, that's your advanced wizardry for

Java closures, faking closures in Java by using objects.

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.

Download on the App Store

Get it on Google Play

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

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