Friday, December 28, 2007

Closures Sources

Closures sources

Advanced Features

Advanced features

A function type can be used as type parameter:

  public static void main(String[] args) {
    List<{ int, int => int }> operations = 
      new ArrayList<{ int, int => int }>();
    operations.add({ int x, int y => x + y });
    operations.add({ int x, int y => x | y });
    int[][] param = { { 1, 2 }, { 3, 4 }, { 5, 6 } };
    for (int[] p: param) {
      for ({ int, int => int } op : operations) {
        System.out.println(op.invoke(p[0], p[1]));
      }
    }
  }
  

A closure can return another closure:

  { String => { int => String } } concat = 
    { String s => 
      { int n => String r = ""; for ( ; n > 0; n--) r += s; r } };
  

Function concat takes a single string argument and returns a function that takes a single integer argument and returns string.

  { int => String } concatABC = concat.invoke("ABC");
  String result = concatABC.invoke(3);
  

Each function that takes multiple arguments can be transformed into a function that takes a single argument. This transformation is called currying. For example, function plus can be transformed into anotherPlus:

  { int, int => int } plus = { int x, int y => x + y };
  { int => { int => int } } anotherPlus = { int x => { int y => x + y } };
  int threePlusFour = anotherPlus.invoke(3).invoke(4);
  

The reverse transformation is called uncurrying. Currying and uncurrying are used in functional programming. For more examples of functional programming in Java, see Luc Duponcheel's blog.

Exceptions

Exceptions

Closures are allowed to throw exceptions. We use the throws keyword to declare which exceptions are thrown by a closure:

  { long => void throws InterruptedException } wait = 
    { long millis => Thread.sleep(millis); };
  try {
    wait.invoke(2000);
    System.out.println("hi");
  } catch (InterruptedException e) { e.printStackTrace(); }
  

A closure may throw more than one exception:

  try {
    FileOutputStream fos = new FileOutputStream("primes");
    try {
      { int, long => 
        void throws IOException, InterruptedException } writeAndWait = 
        { int value, long millis => 
          fos.write(value); Thread.sleep(millis); };
      writeAndWait.invoke(17, 2000);
      System.out.println("first");
      writeAndWait.invoke(19, 2000);
      System.out.println("second");
    } finally { fos.close(); }
  } catch (IOException | InterruptedException e) { e.printStackTrace(); }
  

When we assign a closure to a variable of function type, the closure must not throw more than is declared in the function type.

  // constructor FileWriter throws IOException which is a subclass of 
  // Exception
  { String => void throws Exception } truncate = 
    { String name => new FileWriter(name).close(); };
  { => double throws Exception } next = 
    { => Math.random() };  // Math.random() does not throw any exception
  

Exception Transparency

If we pass a closure that throws exceptions to some method, we might want these exceptions are propagated from the method. If we used ordinary type parameter for exception, we could have passed in only a block that throws one exception. But what if we want to accept a block that throws any number of exceptions and we want exceptions are transparently propagated to the caller? We have to use exception type parameters. The exception type parameter is declared using the throws keyword and stands for any number of exceptions.

  // method performTwice throws the same exceptions as the block passed in
  static <throws E> void performTwice({ => void throws E } block) throws E {
    block.invoke();
    block.invoke();
  }
  
  static void passBlockThrowingNoExceptions() {
    performTwice({ => System.out.println("no exception..."); });
  }
  
  static void passBlockThrowingOneException() {
    try {
      // the block passed to performTwice throws one exception 
      // (InterruptedException)
      // the compiler checks that we catch this exception
      performTwice({ => 
        System.out.println("waiting..."); Thread.sleep(2000); });
    } catch (InterruptedException e) { e.printStackTrace(); }
  }
  
  static void passBlockThrowingMoreExceptions() {
    try {
      // the block passed to performTwice throws two exceptions 
      // (InterruptedException and IOException)
      // the compiler checks that we catch these exceptions
      performTwice({ => Thread.sleep(2000); new FileWriter("x").close(); });
    } catch (InterruptedException | IOException e) { e.printStackTrace(); }
  }
  

If we do not want to propagate exceptions, we can invoke a closure in the try block:

  static <throws E> void logAndPerform(
    String desc, { => void throws E } block) {
    System.out.printf("start: %s...%n", desc);
    try {
      block.invoke();
    } catch (Exception e) { e.printStackTrace(); }
    System.out.printf("end: %s%n", desc);
  }
  
  public static void main(String[] args) {
    logAndPerform("doing nothing", { => System.out.println("hi"); });
    logAndPerform("sleeping", { => Thread.sleep(2000); });
    logAndPerform("sleeping and truncating", 
      { => Thread.sleep(2000); new FileWriter("x").close(); });
  }
  

Exercises

  1. Fill in the type of p.
      static void m() throws FileNotFoundException, InterruptedException {
        //...
      }
      
      public static void main(String[] args) {
                                                     p = { => m(); };
        try {
          p.invoke();
        } catch (FileNotFoundException | InterruptedException e) { 
          e.printStackTrace();
        }
      }
      
  2. Declare method forEach that performs an operation on each item of a collection. The operation is described by a closure and may throw an exception (one or more).

Solutions

  { => void throws FileNotFoundException, InterruptedException } p = 
    { => m(); };
  
  static <T, throws E> void forEach(
    Iterable<T> items, { T => void throws E } block) throws E {
    for (Iterator<T> it = items.iterator(); it.hasNext(); ) {
      block.invoke(it.next());
    }
  }
  public static void main(String[] args) {
    List<String> nums = Arrays.asList("first", "second", "third");
    forEach(nums, { String s => System.out.println(s); });
  }
  

Closure Conversion

Closure Conversion

A closure can be assigned to a variable of compatible interface type. A compatible interface type must have a single method with a compatible return type and compatible argument types. For example:

  interface IntPlus {
    int add(int x, int y);
  }
  IntPlus plus = { int x, int y => x + y };
  

In such case, a closure is converted to an instance of anonymous class that implements the given interface:

  IntPlus plus = new IntPlus() {
    public int add(int x, int y) { return x + y; }
  };
  

Then, we call the closure by the interface method:

  int sum = plus.add(5, 6);
  

This allows us to use a closure instead of anonymous subclass of interface with a single method. For example, the closure conversion can create an instance of Runnable:

  new Thread({ => System.out.println("hi"); }).start();
  

Sometimes we can use the closure conversion even if the interface has more than one method. It is in case when all but one method are implemented in Object. The closure is then converted to a single remaining method. For example, interface Comparator contains two methods: compare() and equals(). Method equals() is in Object and so the closure is converted to method compare().

  String[] girls = { "Jane", "Eva", "Sarah", "Alice" };
  Arrays.sort(girls,
    { String s1, String s2 =>
      int r = s1.length() - s2.length(); r == 0 ? s1.compareTo(s2) : r 
    });
  

Exercises

  1. Declare interface HashCalculator.
      HashCalculator hc = 
        { String s1, String s2 => s1.hashCode() ^ s2.hashCode() };
      System.out.println(hc.hash("elephant", "giraffe"));
      
  2. Use a closure to define Comparator which sort numbers descendingly.
      Integer[] wages = { 1200, 4500, 850, 1500, 990 };
      Arrays.sort(wages,                                      );
      
  3. Sort an array of strings and count the number of comparisons.

Solutions

  interface HashCalculator {
    int hash(String s1, String s2);
  }
  
  Integer[] wages = { 1200, 4500, 850, 1500, 990 };
  Arrays.sort(wages, { Integer i, Integer j => j.compareTo(i) });
  
  String[] countries = { 
    "France", "Czech Republic", "Poland", "Hungary", "Germany" 
  };
  int c = 0;
  Arrays.sort(countries, { String s1, String s2 => c++; s1.compareTo(s2) });
  System.out.println("number of comparisons: " + c);
  

Covariant Return and Contravariant Arguments

Covariant Return and Contravariant Arguments

As we know, to a variable of function type may be assigned a closure with compatible return type and compatible argument types. "Compatible return type" means that the type is either the same as in function type or is a subclass of this type (return types are covariant).

  { => Number } p1 = 
    { => Integer.valueOf(19) };  // Integer is a subclass of Number
  { => Number } p2 = 
    { => Double.valueOf(1.25) };  // Double is a subclass of Number
  

"Compatible argument type" means that the argument type is either the same as in function type or is a superclass of this type (argument types are contravariant).

  { String => void } p = 
    // Object is a superclass of String
    { Object o => System.out.println(o); };
  

We can combine covariant return with contravariant arguments:

  { String => Number } p = { Object o => Integer.valueOf(o.hashCode()) };
  System.out.println(p.invoke("haf"));
  

These rules define hierarchy on function types. So a function type might be a subtype or supertype of another function type. For example, { => Integer } is a subtype of { => Number } and { String => void } is a supertype of { Object => void }. As for class types, to a variable of function type may be assigned an object (closure) of its type or any subtype.

What is meant by covariant and contravariant?
Let S and T be two types (classes or function types) such that S is a subtype of T. If method m of T is overridden in S, then the corresponding types from the m's signature can either preserve the relationship between S and T (i.e. the type used in S is a subtype of the corresponding type in T), reverse this relationship (i.e. the type used in S is a supertype of that in T), or neither preserve nor reverse this relationship. If they preserve the relationship of S and T, we say they are covariant, and if they reverse the relationship of S and T, we say they are contravariant.

Local Variables

Access to Local Variables

So far, closures were a concise analogy to anonymous inner classes. But they offer more. In inner classes, you can access a variable from enclosing scope only if it is final. For closures, there is no such restriction:

  public static void main(String[] args) {
    int x = 4;
    { => void } printX = 
      { => System.out.println(x); };  // x is a free variable here
    x++;
    printX.invoke();  // will print 5
  }
  

In function printX, x is a free variable because it is not declared in the printX's block of code (it is neither a parameter nor a local variable in this block). We can access and change free variables:

  int x = 100;
  { => int } nextX = { => ++x };
  System.out.println(nextX.invoke());  // will print 101
  System.out.println(nextX.invoke());  // will print 102
  x = 200;
  System.out.println(nextX.invoke());  // will print 201
  

A block of code is packed with variables of the enclosing scope, i.e. the scope where the block is declared. This is where the name "closure" comes from. For example, the following block of code will always work with variable x in the main method:

  static void doTwice({ => void } block) {
    block.invoke();  // will print 10
    int x = 20;
    block.invoke();  // will print 11
    System.out.println(x);  // will print 20
  }
  
  public static void main(String[] args) {
    int x = 10;
    // the block is "packed" with variable x
    doTwice({ => System.out.println(x++); });  
  }
  

A closure can use variables of the enclosing scope even if this scope is not active at the time of closure invocation. For example, a closure can use local variables of a method after return from this method:

  static { => int } makeSum() {
    int n = 1, s = 0;
    // the following closure uses local variables n and s
    return { => s += n; n++; s };
  }
  
  public static void main(String[] args) {
    { => int } sum = makeSum();
    System.out.println(sum.invoke());  // will print sum 0 + 1
    System.out.println(sum.invoke());  // will print sum 0 + 1 + 2
    System.out.println(sum.invoke());  // will print sum 0 + 1 + 2 + 3
  }
  

If we declare n and s local in a closure, we will get different results:

  static { => int } makeSumWrong() {
    return { => int n = 1, s = 0; s += n; n++; s };
  }
  
  public static void main(String[] args) {
    { => int } sum = makeSumWrong();
    System.out.println(sum.invoke());  // will print sum 0 + 1
    System.out.println(sum.invoke());  // will print sum 0 + 1
    System.out.println(sum.invoke());  // will print sum 0 + 1
  }
  

Variables n and s are now local in a closure, so they are initialized upon each invocation of this closure.

Reference this in a closure has the same meaning as this in enclosing scope.

  public class TestThis {
    String s = "hello";
    void test() {
      String s = "hi";
      { => System.out.println(this.s); }.invoke();  // will print "hello"
    }
    public static void main(String[] args) {
      new TestThis().test();
    }
  }
  

Implementation Issue

Local variables that are accessed from a closure are allocated on the heap, so that they are available even when we exit the block they are declared in.


Exercises

  1. Determine the output.
      class ClosureWithThis {
        int x = 1;
        void tryThis() {
          new Invoker().tryThis({ int x => 
            System.out.println(x);
            System.out.println(this.x);
          });
        }
        public static void main(String[] args) {
          new ClosureWithThis().tryThis();
        }
      }
      
      class Invoker {
        int x = 2;
        void tryThis({ int => void } p) {
            p.invoke(3);
        }
      }
      
  2. Determine the output.
      static void m({ => int } c1, { => int } c2) {
        System.out.println(c1.invoke());
        System.out.println(c2.invoke());
      }
    
      public static void main(String[] args) {
        int i = 1;
        m({ => ++i }, { => --i });
      }
      

Solutions

  1. x refers to the argument and this.x refers to field x of the ClosureWithThis instance. Thus, the first println will print 3 and the second will print 1.
  2. Closures { => ++i } and { => --i } refer to the same variable i. Thus, the first println will print 2 and the second will print 1.

Function Types

Function Types

Function types are used when we want to refer to closures. We can declare a variable of function type and assign to it a reference to a closure. A function type is written as follows: { formal parameters => return type }. Formal parameters are optional. The return type can be any type or void. For example, { int, String => void } means a function with two arguments (int and String) and return type void. Any function with a compatible list of argument types and compatible return type can be assigned to a variable of function type.

  public class DeepThought {
  
    // { => int } means a function with no arguments and return type int
    static { => int } answer = { => 42 };
 
    public static void main(String[] args) {
      int i = answer.invoke();
      System.out.println(i);
    }
 
  }
  

A function with one int argument and return type String:

  { int => String } toBinary = { int x => Integer.toBinaryString(x) };
  String binary11 = toBinary.invoke(11);  // will return 1011
  

A function with no arguments and return type void:

  { => void } sayHello = { => System.out.println("Hello"); };
  sayHello.invoke();  // will print "Hello"
  

Function types can be used as types of arguments:

  static void doTwice({ => void } block) {
    block.invoke();
    block.invoke();
  }
  
  public static void main(String[] args) {
    doTwice({ => System.out.println("deja vu"); });
  }
  

They can also serve as a return type:

  static { => boolean } makeCond() {
    return { => Math.random() < 0.8 };
  }
  
  public static void main(String[] args) {
    { => boolean } cond = makeCond();
    while (cond.invoke()) {
      System.out.println("trying...");
    }
  }
  

Exercises

  1. Write a method that invokes an action on each value of array of ints. The action is passed in a function variable.
  2. Write a method that returns a closure which checks if a value is from a given interval. Bounds of the interval are arguments of the method.
  3. Write a method that selects values from a list in accordance with a predicate passed in a function variable.

Solutions

  static void perform(int[] values, { int => void } action) {
    for (int n: values) {
      action.invoke(n);
    }
  }
  
  public static void main(String[] args) {
    int[] v = { 2, 3, 5, 7, 11 };
    perform(v, { int x => System.out.println(x); });
  }
  
  static { int => boolean } makeInterval(int a, int b) {
    return { int x => a <= x && x <= b };
  }
  
  public static void main(String[] args) {
    { int => boolean } interval = makeInterval(10, 20);
    System.out.println(interval.invoke(15));
  }
  
  static <T> List<T> select(List<T> values, { T => boolean } cond) {
    List<T> selected = new ArrayList<T>();
    for (T t: values) {
      if (cond.invoke(t)) { selected.add(t); }
    }
    return selected;
  }
  
  public static void main(String[] args) {
    List<String> cities =
      Arrays.asList("London", "New York", "Prague", "San Francisco");
    List<String> shortCities = 
      select(cities, { String s => s.length() <= 6 });
    System.out.println(shortCities);
  }
  

Closures

Closures

A closure is a form of anonymous function. It is declared using the following syntax:
{ formal parameters => statements expression }. Formal parameters, statements, and expression are optional in this clause. For example, { int x => x + 1 } is a function that takes a single int argument and returns its value incremented by 1. A closure can be invoked by the invoke method. For example, { int x => x + 1 }.invoke(10) will call the closure with argument 10.

  public class SimpleClosure {
  
    public static void main(String[] args) {
      // function with no arguments; return value is always 42
      int answer = { => 42 }.invoke();
      System.out.println(answer);
    }
  
  }
  

A closure with one argument:

  double log = { double x => Math.log(x) }.invoke(10);
  

A closure with a statement:

  // this will print "31 is odd" and return 15
  int half = { 
    int x => 
    if (x % 2 != 0) System.out.printf("%d is odd%n", x); x / 2
  }.invoke(31);
  

A closure with two arguments:

  int sum = { int x, int y => x + y }.invoke(3, 4);  // will return 7
  

A closure does not have to return any value (the function may have return type void):

  { char c => System.out.println(c); }.invoke('@');  // will print @
  

A closure that returns a string:

  String reversed = { 
    String s => 
    new StringBuilder(s).reverse().toString()
  }.invoke("abcd");  // will return "dcba"
  

A closure that returns an instance of Runnable.

  { => new Runnable() {
      public void run() {
        System.out.println("hi from Prague");
      }
    }
  }.invoke().run();  // invoke() returns an instance of Runnable and we 
                     // call run() on it immediately
  

We can declare local variables in closures:

  { int n => 
    int m = n + 1; System.out.println(m * m); 
  }.invoke(3);  // will print 16
  

Implementation issue

This paragraph describes how the prototype compiler implements closures.

For each closure, the compiler will generate an interface with single method invoke(). E.g., for closure { => 42 }, the interface will look like:

  public interface I {
    int invoke();  // no arguments and return type int
  }
  

And for closure { int x, int y => x + y }, the interface will be like:

  public interface III {
    int invoke(int x, int y);  // two int arguments and return type int
  }
  

The interface will be in the javax.lang.function package. Then the compiler will generate an anonymous subclass of this interface, create an instance of this subclass, and call the invoke method. For example, the code

  public static void main(String[] args) {
    int answer = { => 42 }.invoke();
    System.out.println(answer);
  }
  

will be tranformed approximately as follows:

  public static void main(String[] args) {
    int answer = new javax.lang.function.I() {
      public int invoke() {
        return 42;
      }
    }.invoke();
    System.out.println(answer);
  }
  

So, at runtime a closure is represented as object. In JSR, this object is called the closure object.


Exercises

  1. Write a closure that returns the lesser of two double values.
  2. Write a closure that decides if a value is even.
  3. Write a closure that returns last n characters of a string.

Solutions

  double min1 = { double x, double y => x < y ? x : y }.invoke(7.5, 8.2);
  double min2 = { 
    double x, double y => 
    double m; if (x < y) m = x; else m = y; m 
  }.invoke(10.22, 9.76);
  
  boolean even = { int x => x % 2 == 0 }.invoke(15);
  
  { String, int => String } lastNChars = 
    { String s, int n => int len = s.length(); s.substring(len - n, len) };
  

Java Closures Tutorial

Java Closures Tutorial

JSR Proposal: Closures for Java, section 2:

'This JSR provides support for operating on an arbitrary "block of Java code", or body, which is either a statement list, an expression, or a combination of both. We call the mechanism a closure expression. Wrapping statements or an expression in a closure expression does not change their meaning, but merely defers their execution. Evaluating a closure expression produces a closure object. The closure object can later be invoked, which results in execution of the body, yielding the value of the expression (if one was present) to the invoker. A closure expression can have parameters, which act as variables whose scope is the body. In this case the invoker of the closure object must provide compatible arguments, which become the values for the parameters.'

This tutorial does not describe the whole proposal but only the features implemented in the prototype compiler. All examples in this tutorial were tested against the early prototype available at http://www.javac.info. Current version: closures.tar.gz