teaching machines

CS 330: Lecture 32 – Closures

Dear students,

Let’s start with a Program This! Consider the foreach algorithm:

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

The core idea is that we have a list of items, and we want to produce some side effect for each of them. The foreach algorithm doesn’t return anything. It just does stuff. (The Haskell implementation of this algorithm is mapM_, which we didn’t discuss.)

Implement this in Java. First, write a functional interface (SAM), and then write a higher-order function that implements the algorithm.

Here’s my solution.
interface Visitor<T> {
  void visit(T x);
}

class Library {
  // ...

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

We can use foreach to quickly print out a list of planets, for example:

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

In Haskell, we saw that it’s very easy to write a lambda that does no real work—it simply wraps around another function. If it’s really that other function we want to call, we should just pass that function off instead of unnecessarily wrapping it up in another function. Can we do that in Java 8? Yes, sometimes. We can use method references:

List<String> names = Library.map(planets, Planet::getName);
System.out.println(names);
Library.foreach(planets, System.out::print);

There are a lot of related but separable ideas in this stage of our journey. Let’s take a moment to revisit these:

  • Higher-order functions are algorithms that can’t entirely be abstracted away. Their writer leaves a few holes that need to be plugged by custom routines from the caller. Filter doesn’t know its predicate, map doesn’t know its transform, fold doesn’t know how to mix its element into the accumulation.
  • A language with first-class functions allows functions to be passed around, saved to variables, and returned. They are first-class in the sense that they are treated with the same dignity as our other data types.
  • Lambdas are function literals, the definition of a function without the pomp of binding it to a name. A language can support HOFs and first-class functions without having lambdas. (If you count function pointers, C is one such language.) But lambdas make HOFs far more pleasant to use. Lambdas allow us to fill those algorithms holes in a very ad hoc way. (Haskell also had a few other ways of producing new functions: partial evaluation and composition.)

There are some issues surrounding lambdas that I think we need to address because I think you’re going to run into them in your development life. That’s how we’ll spend the rest of our time today. First, checkout this HTML and Javascript code, which renders some buttons and then grabs some handles to them:

<input id="buttonA" type="button" value="Click A!">
<input id="buttonB" type="button" value="Click B!">
<input id="buttonC" type="button" value="Click C!">

<script>
var buttons = [
  document.getElementById('buttonA'),
  document.getElementById('buttonB'),
  document.getElementById('buttonC')
];
</script>

Let’s loop through these. What do you expect for output here?

for (var i = 0; i < buttons.length; ++i) {
  console.log(i);
}

0, 1, 2, right? Right. How about this?

for (var i = 0; i < buttons.length; ++i) {
  console.log(buttons[i]);
}

It shows the buttons, as we’d expect. Now let’s register a click handler:

for (var i = 0; i < buttons.length; ++i) {
  buttons[i].onclick = function() {
    alert(i);
  }
}

Pretend we want to do something that depends on the button’s serial number. We’ll use alert as a placeholder for that more meaningful computation. This code does not behave as we’d expect. All three buttons produce a 3. There wasn’t even a button 3.

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 function references i, which is the exact same i that was declared in our outer loop. All three of our lambdas hold a reference to i, and so does the surrounding scope. The surrounding scope keeps incrementing i, and this affects the lambdas.

This automatic capturing of the surrounding environment is often a wonderful thing. In fact, I’d go so far as to say that lambdas need closure semantics to be useful. Suppose for a moment that lambdas could not access variables from the surrounding scope. Consider writing a compound slider/spinner widget in HTML:

<input id="slider" type="range">
<input id="ticker" type="number">

When you change one of the widgets, you want the other widget to change to stay in sync, so you write this code:

var slider = document.getElementById('slider');

slider.oninput = function() {
  // ?
}

How do you update the ticker? In the absence of closures, the only information we have is what’s given to our lambda through parameters. Only the information known and deemed worthy by the writer of the event system will ever get sent to our callbacks. In this case, we do get some information sent to our callback:

slider.oninput = function(event) {
  console.log(event);
}

But it’s not enough to update the ticker. Instead, we do have closure semantics and we can access variables from the surrounding scope:

var slider = document.getElementById('slider');
var ticker = document.getElementById('ticker');

slider.oninput = function(event) {
  ticker.value = slider.value; 
}

And vice versa:

ticker.oninput = function(event) {
  slider.value = ticker.value; 
}

So, we do want to capture the surrounding scope, but how do we deal with the situation we saw with our buttons where the closed-over i was too shared? Well, we need to narrow the scope. Let’s try declaring num inside the loop:

for (var i = 0; i < buttons.length; ++i) {
  var num = i;
  buttons[i].onclick = function() {
    alert(num);
  }
}

Now we see 2 on every click. Argh. This solution actually does work in some languages, but not Javascript. In this blessed language, variable declarations are hoisted to the top of their scopes. A loop doesn’t introduce a new scope in Javascript, so the top of the scope is the same as the beginning of our script. Effectively, our code becomes this:

var num;

// ...

for (var i = 0; i < buttons.length; ++i) {
  num = i;
  buttons[i].onclick = function() {
    alert(num);
  }
}

That’s still too much sharing for our buttons. We need some other trick to introduce a narrower scope. What in Javascript does provide a new scope? Functions. We can falsely wrap up the generation of the lambda inside another function call:

for (var i = 0; i < buttons.length; ++i) {
  function register(iUnshared) {
    buttons[iUnshared].onclick = function() {
      alert(iUnshared);
    }
  }
  register(i);
}

This situation happens frequently enough in Javascript that there’s a slightly simpler idiom called an immediately invoked function expression (IIFE). It looks kind of gross at first, but it eliminates the need to bind the function to a name:

for (var i = 0; i < buttons.length; ++i) {
  (function(iUnshared) {
    buttons[iUnshared].onclick = function() {
      alert(iUnshared);
    }
  })(i);
}

iUnshared only exists in the scope of the function, so we will have no unintended sharing across buttons.

We could also have fixed this particular example by not using a for loop in the first place. A forEach HOF would also introduce a new scope for the index variable:

buttons.forEach((button, i) => alert(i));

But we’re bound to run into oversharing situations sooner or later, and it’s important that we can read and write IIFEs.

Here’s your TODO list:

  • Start the Wasd homework assignment. Don’t wait! It combines templates, HOFs, lambdas, multithreading, and 3D rendering algorithms from the 1990s.

See you next time!

Sincerely,

P.S. It’s time for a haiku!

Code is us, dancing
I leave holes and you fill them
Hold me closure, dear

P.P.S. Here’s the code we wrote together:

Whatdo.java

public interface Whatdo<A> {
  void doer(A item);
}

ForeachTest.java

import java.util.Arrays;
import java.util.Random;
import java.util.List;

public class ForeachTest {
  public static <A> void foreach(List<A> list, Whatdo<A> action) {
    for (A item : list) {
      action.doer(item);
    }
  }

  public static void except(String s) {
    Random g = new Random();
    System.out.println(s + " " + g.nextInt(100));
  }

  public static void main(String[] args) {
    String[] names = {"Jordan", "Jones", "Null", "Andy", "Dang", "Dayne"};
    /* foreach(Arrays.asList(names), item -> System.out.println(item)); */
    /* foreach(Arrays.asList(names), System.out::println); */
    foreach(Arrays.asList(names), ForeachTest::except);
  }
}

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *