0:18
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.
1:44
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.
2:53
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.
3:43
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.
7:23
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.
9:26
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.
Dan GrossmanProfessor
