teaching machines

CS 330 Lecture 26 – HOFs Elsewhere and Closures

April 10, 2017 by . Filed under cs330, lectures, spring 2017.

Dear students,

Let’s start with a Program This!

Write the necessary Java 8 code to filter a List. Make the code as general as possible, allowing its clients to supply their own filtering criteria.

Here’s my solution.
To leave a hole in the filtering algorithm, we must leave a parameter for the predicate. We’ll use a functional interface so we can drop in a lambda: 
@FunctionalInterface
interface Predicate<T> {
  boolean isKeeper(T x);
}

class Library {
  public static <T> List<T> filter(List<T> list, Predicate<T> predicate) {
    ArrayList<T> keepers = new ArrayList<T>();
    for (int i = 0; i < list.size(); ++i) {
      if (predicate.isKeeper(list.get(i))) {
        keepers.add(list.get(i));
      }
    }
    return keepers;
  }
}

Let’s test this out with our planets, as we did in Haskell:

class Planet {
  private String name;
  private double ausFromTheSun;
  private double relativeMass;

  public Planet(String name,
                double ausFromTheSun,
                double relativeMass) {
    this.name = name;
    this.ausFromTheSun = ausFromTheSun;
    this.relativeMass = relativeMass;
  }

  public String getName() {
    return name;
  }

  public double getAUs() {
    return ausFromTheSun;
  }

  public double getMass() {
    return relativeMass;
  }

  public String toString() {
    return String.format("%15s %6.2f %6.2f%n", name, ausFromTheSun, relativeMass);
  }
}

Now we can make a list:

public class Main {
  public static void main(String[] args) {
    List<Planet> planets = Arrays.asList(
      new Planet("Saturn", 9.5, 95.0),
      new Planet("Earth", 1.0, 1.0),
      new Planet("Venus", 0.7, 0.815),
      new Planet("Jupiter", 5.2, 318.0),
      new Planet("Uranus", 19.6, 14.0),
      new Planet("Neptune", 30.0, 17.0),
      new Planet("Mars", 1.5, 0.107),
      new Planet("Mercury", 0.4, 0.055)
    );
  }
}

With these in place, we can execute the same queries as we did in Haskell:

System.out.println(Library.filter(planets, p -> p.getMass() > 1));
System.out.println(Library.filter(planets, p -> p.getAUs() < 2.2));
System.out.println(Library.filter(planets, p -> p.getName().contains("u")));

Let’s do another Program This!

Write the necessary Java 8 code to map a function over a List. Make the code as general as possible, allowing its clients to supply their own transformation function.

Here’s my solution.
interface Transformer<T, U> {
  U transform(T x);
}

class Library {
  // ...

  public static <T, U> List<U> map(List<T> olds,
                                   Transformer<T, U> transformer) {
    ArrayList<U> news = new ArrayList<U>();
    for (int i = 0; i < olds.size(); ++i) {
      news.add(transformer.transform(olds.get(i)));
    }
    return news;
  }
}

It’s not as pretty as Haskell, but remember, we only have to write the overall algorithm once! Let’s see it used with some lambdas:

System.out.println(Library.map(planets, p -> p.getName()));
String[] names = {"Alice", "Bob", "Carol", "Diphthong"};
System.out.println(Library.map(Arrays.asList(names), name -> name + ", Lord of Catan"));
Integer[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(Library.map(Arrays.asList(nums), num -> 2 * num));

In Haskell, we learned that there are situations where lambdas simply wrap around another function, which makes them kind of pointless. If it’s really some other function we want to call, we should just pass that function off instead unnecessarily wrapping it up in another function. Can we do that in Java 8? Yes, sometimes. We can use method references:

System.out.println(Library.map(planets, Planet::getName));

Okay, let’s visit one last abstraction, the for-each pattern:

for each item in list
  do something with that item (call a method, print, etc.)

This pattern only makes sense in a language with side effects. As you can see, it doesn’t return anything. It just does stuff. We might implement it in Java like this:

interface Visitor<T> {
  void visit(T x);
}

class Library {
  // ...

  public <T> void foreach(List<T> list,
                          Visitor<T> visitor) {
    for (T item : list) {
      visitor.visit(item);
    }
  }
}

The algorithm is simpler here, so we don’t gain as much as we did with filter and map, but still, the fewer braces the better!

Library.foreach(planets, p -> System.out.print(p));
Library.foreach(planets, System.out::print);

For completeness sake, we might write these three patterns in Ruby too. Ruby developers tend to use blocks, which are subtly different from lambdas. The block that is passed to a function comes in as an implicit parameter, and is invoked by a call to yield:

class Array
  def foreach
    i = 0
    while i < size
      yield self[i]
      i += 1
    end
  end

  def mymap
    news = []
    foreach do |element|
      news << (yield element)
    end
    news
  end

  def myfilter
    keepers = []
    foreach do |element|
      if yield element
        keepers << element
      end
    end
    keepers
  end
end

[1, 2, 3].foreach { |n| puts n }
p [1, 2, 3].mymap { |n| n * 2 }
p [1, 2, 3, 4].myfilter { |n| n % 2 == 0 }

Consider this bit of Ruby code, which uses blocks and the higher-order function each to spawn off five threads:

threads = []

i = 0
while i < 5
  threads << Thread.new do
    puts i
  end
  i += 1
end

threads.each do |thread|
  thread.join
end

What can we say about the output of this program? Sure, there are threads, but the output is still probably not going to be what you expect. Here’s what I got on one run:

2
2
5
5
5

What’s happening here? We are seeing the effect of a closure. In short, a closure is made when we define a lambda. Not only does the code get stored, but so does the relevant surrounding scope. The block we pass to Thread references i, so it keeps around a reference to i. All five of our closures hold that reference, and so does the surrounding scope. The surrounding scope keeps incrementing i, and this affects the threads.

This automatic capturing of the surrounding environment is often a wonderful thing. It can be used to achieve object-oriented modeling in a language that doesn’t have it. It means we don’t need to provide as many parameters, because the lambda can just gobble up whatever it needs implicitly. But sometimes it’s annoying and dangerous.

I’ve seen closure avoidance most often in Javascript, where we avoid capturing using an idiom called an immediately invoked function expression (IIFE):

(function(i) {
  console.log(i);
})(7);

Here we avoid introducing a new binding in the parent scope for identifier i. i only exists in the scope of the function, so we’ll have no unintended sharing.

In Ruby, we avoid the sharing by making sure i is not bound in the global scope. We can use block parameters to achieve this independence:

(1..5).each do |i|
  threads << Thread.new do
    puts i
  end
end

We will talk more about closures in the future, but they are relevant here because Java doesn’t have them. For example, we might want to print out a numbered list of planets:

int i = 1;
Library.foreach(planets, p -> {
  System.out.printf("%d. %s%n", i, p.getName());
  i += 1;
});

But this fails to compile. Java 8 doesn’t let inner classes or lambdas truly share bindings with outer scopes. Rather, the inner construct gets a copy of the outer scope’s binding. And to emphasize that the two bindings are separate, that a change in one will not result in a change in the other, the compiler says that you can’t change them at all. They must be final:

final int i = 1;
Library.foreach(planets, p -> {
  System.out.printf("%d. %s%n", i, p.getName());
  // i += 1; 
});

Sadly, final variables can’t be changed. So much for our numbered list! One workaround here is that we could create a mutable integer class. The reference to that object would be final, but the number it wraps around could.

Here’s your TODO list:

See you next time, when we discuss the function to end all functions: fold/reduce/inject!

Sincerely,