Closures

From APIDesign

Revision as of 20:07, 28 November 2009

Closures are classical OOP approach to represent a block of code that can be invoked passing in few parameters. Closures are typical building block of Smalltalk systems. Origin of closures (called lamdas back then) can however be traced many years into the past to λ-calculus (where there is nothing else than invocable blocks of code).

Since their invention closures become almost mandatory syntactic element for any new language. Not having them become a faux pas. As the profound history of programming languages puts it: Java makes them popular by not having them.

Looks like things are about to change. Sun recently announced its will to implement closures for JDK7. To join the overwhelming ecstasy in the Java community I decided to write this page and provide few insights from less conventional angles.

The Da Vinci Closures

Everyone who read or saw The Da Vinci Code knows that public statements of those who rule the world need to be taken with a grain of salt. Public speech is there to influence the public behaviour. Not to describe the real estate of things. The real motivations need to remain hiden behind multiple meanings. The goal is to make trustable untrustable and untrustable real. Using irony and self denying references is good. Outsiders who discover part of the truth can never be sure whether it is the grail or just a fake layer around it with completely opposite meaning.

Only paranoid survive. Especially when dealing with Da Vinci and things related to him. One needs to be ready to reveal hidden and surprising meanings. One needs to seek for them.

That is why I was quite surprised that the attempt to extend Java bytecode with invokeDynamic has been named Da Vinci Machine project. What does that mean? Is the proclaimed goal to support multiple languages just a layered public statement and the real goal is somewhere else? What Sun wants public to think? Why?

Now when Sun adopted the idea of closures for JDK7, everything is clear. There was a hidden agenda behind the publicly stated goal.

Method Handle

When I was younger I used to believe that having invokeDynamic instruction in HotSpot VM can be beneficial. I even argued that the instruction should not be used just for dynamic languages like Ruby but rather by the core Java to implement lambdas. Now, after spending time to implement lambdas in my Bck2Brwsr VM and seeing things from the other side I have to admit I was wrong. invokeDynamic is wrong idea (especially for implementation of lambdas).

Benefits

Implementing different languages on top of HotSpot virtual machine is of different complexity. When John Rose pushed forward his invokeDynamic vision, he claimed that the most problematic thing is to properly and effectively dispatch methods calls. Not every language uses the Java rules. Some support type conversions, implicit arguments. Some can dynamically alter the existing dispatch target or strategies. More about that in an excellent summary Bytecodes meet Combinators. I really liked that paper and I continue to like it. It matches my functional heart: with MethodHandle (basically a pointer to method of some signature - for example plus would take two ints and return their sum as an int - and an object - a receiver to call the method on) a method invocation is finally first class citizen in the VM. One can do currying & co. - all the goodies functional languages had for ages.

But there is a hidden catch...

Getting Dynamic

The primary goal of John Rose was to support dynamic languages - e.g. languages where one knows (almost) no type information until the program actually runs. That means one can effectively type (in this JVM context: effectively generate bytecode) only when one knows the actual types. To address all these "deffered" needs the new invokeDynamic bytecode operand had been introduced. It does not hardcode the actual invocation, but once invoked, it calls back to let the "supervising" software (like your JRuby implementation) analyse the actual call parameters and generate sequence of MethodHandle transformation (possibly a bit of currying, mostly type conversions) to effectively match the actual types of method arguments.

Drawbacks

The major problem with invokeDynamic is, well, that it is dynamic! Java is statically typed language and all variable, field, method and parameter types are known to JavaC before its emits the bytecode. Yet (as JavaC from JDK8 is emulating lambdas with invokeDynamic) it forgets all the derived type information and generates invokeDynamic - which is supposed to do late binding - e.g. find out the right types at the invocation time.

One of the key ideas that I had in mind when advocating use of MethodHandles for implementation of lambdas was reduction in the size of constant pool - you know, the list of referenced symbols like Ljava/lang/String which generally needs to be repeated in every Java class. If lambdas were simulated by inner classes, the constant pools might get enormous (all the symbols might be duplicated in each lambda-innerclass). With invokeDynamic I was hoping for the pool to be reduced to one shared pool for a single source code (with as many lambdas as needed).

However the JDK8 lambdas are generating innerclasses behind the scene and on the fly! So the main benefit is in my opinion gone.

The Problem

The unnecessary loss of types is problematic for VMs that are supposed to run in restricted environment - e.g. Bck2Brwsr or (as far as I heard) Java ME 8. We are running in restricted environment, we can't consume these resources by trying to generate new classes. Just in time compilation may be too expensive, it is much easier to generate the right execution format ahead-of-time (both for Bck2Brwsr and for Java ME 8).

Another issue is related to reflection. Method Handles are (due to their dynamic nature) a specific form of reflection. While doing method lookup one identifies the desired method (or field, or setter) by name. One can reference public or private methods. It is not known in advance which methods will be requested - one needs to invoke the bootstrap method to find that out. As such it is really hard to do compile time optimizations (like shortening method names). Again problem for for small, limited environments.

Summary so far

As a result we have implementation of lambdas that is needlessly forgetting the type information gained during compilation, re-creates it during each startup, is generating bytecode on the fly. It is even surprising it performs acceptably (which probably took many nights of the HotSpot team members, but when there is a will, there is a way: John Rose was so motivated to show invokeDynamic is useful, so he did it).

No surprise InvokeDynamic is not supported by Android's Dalvik VM (and in fact it should never be, unless Android wants to attract Ruby and other dynamic language developers). Java language does not need it and if you care about Java language, forget about invokeDynamic!

Having a Hammer, Every Problem Looks like a Nail!

InvokeDynamic is not a Java (language) feature. It is a HotSpot feature to make HotSpot more attractive for other languages than Java. That is of course good intention. HotSpot is still one of the best performing VMs out there - making it more attractive to non-Java langauges makes sense.

However using InvokeDynamic to implement a core Java8 feature (e.g. lambdas) is a mistake. I know I had advocated that in the past too - but the consequences are horrible. Original Java was easy to get ported to small devices - InvokeDynamic is not - and as such the whole Java8 is not portable either!

When one has InvokeDynamic one may be tempted to see solutions to all problems with the help of InvokeDynamic. But sometimes too much may be an overkill.

Solution for the JVM

All Java8 actually needs is to be able to turn method into an instance of interface. However this specific goal can be achieved using simpler tools than InvokeDynamic - of course one can generate the necessary inner classes during compile time, but if we want to stick with the effective (from the point of view of constant pools) way of recording lambdas, the best way is to create new bytecode instruction specialized for the task.

Something like newFromAMethod that would specify the resulting interface to generate, the method to call and additional parameters to pass to it.

Some may say that adding new instruction into JVM needs to be done with care. But those who have seen John's new attempt in the area of Value classes have to realize that adding new instructions into JVM is no longer taboo. In such case adding newFromAMethod that closely mimics necessary Java8 semantics should be no brainer.

Porting that to limited VMs like Bck2Brwsr or Java ME would be way easier as all the typechecks are performed by Javac and the rest is just about wiring the method call. All the information is in the classfile. Way easier to extract it than to execute invokeDynamic's bootstrap method.

Extra Syntax on Top of Existing One

InvokeDynamic has been originally introduced as a helper for implementation of dynamic languages on top of JVM. That is indeed valuable goal from the point of view of HotSpot team. The question is: could the goal have been satisfied without unnecessarily (from the point of view of a Java language) complicating JVM specification?

I believe it could have been done. Have you heard about AsmJs? It is an extension of JavaScript designed by Mozilla. It solves completely different needs (it is an attempt to make JavaScript more typed language - e.g. something opposite to InvokeDynamic), yet the way it has been introduced worth analysis.

Rather than extending JavaScript with new keywords (which is similar to to adding new JVM bytecode instructions), the AsmJs decided to create additional syntax on top of the JavaScript language. For example if one wants to declare that variable x is an integer, one can do so by:

x = x | 0;

The above is valid JavaScript assignment and according to the language specification it guarantees that the result of the or operation is 32-bit integer. Using this to provide hint to the JavaScript VM that x is an integer is a clever way to embed additional semantics into existing language. As a result AsmJs program is parseable by any JavaScript implementation, just on Mozilla it runs way faster than on any other JavaScript implementation.

I believe the same style could have been used for InvokeDynamic. If HotSpot wanted to give Ruby & co. more effective way to handle method dispatch, there could be some extension of the base ByteCode that Ruby and HotSpot could use to talk to each other without modifying JVM specification at all.

Probably such extensive approach would be used, if the JVM team and HotSpot team would not be one! If there were more implementations of JVM spec treated seriously (which was true in case of AsmJs as Mozilla needs to negotiate changes to JavaScript specification with others: Safari, Chrome, etc.).

Diverging Future

Looks like the JDK guys got adrenalized by the "success" of using InvokeDynamic in recent introduction of lambdas in JDK8 and are willing to boost this kind of innovation in the next JDK release. Adding new instructions into the JVM is no longer taboo (as it has been for first fifteen years of Java existence): the Value classes proposal wants to add ten(!?) new bytecodes!

Meanwhile, it turned out that invokeDynamic may not be the best way to speed up dynamic language. The Truffle project's Ruby implementation running on top of enhanced HotSpot (and using no invokeDynamic) is ten times faster than with invokeDynamic. Turns out that in future we are likely to have fast dynamic languages on top of HotSpot not using invokeDynamic, yet the heavy burden of the invokeDynamic specification remains in the core JVM spec!

Java and JVM needs to get smaller (to compete with emerging and improving competitive technologies; think of V8 and NodeJS), not bigger. Complicating them just makes it harder to port Java to new, small areas of use.

Should not we rather think twice before repeating the invokeDynamic failure again? Should not we fix the invokeDynamic/lamda issue - for example by removing/deprecating invokeDynamic from future JVM spec and replacing it with a newFromAMethod bytecode?

Closures as innerclasses

The typical expectation for implementing closures (for example the 0.6a version) seems to envision a closure as an innerclass, with simplified syntax. This is indeed possible, yet ineffective. Overhead of defining new (inner) class in Java is high. Each class occupies a single .class file and these files are selfcontained. They contain not only their code, but also all their static linking information (e.g. the constant pool). This information gets copied with each inner class. Splitting one class into three does not keep the final size proportional to the original one. Imagine you want to rewrite following code:

class SayHello {
  public void sayHello(String to) {
    String hello = "hello";
 
    System.out.println(hello);
    System.out.println(to);
  }
}

so that each of the printlns runs under some lock (let's expect there there is some static method withLock(Runnable) and that we can use some form of closures):

class SayHelloSafely {
  public void sayHello(String to) {
    String hello = "hello";
 
    withLock({ System.out.println(hello); });
    withLock({ System.out.println(to); });
  }
}

Due to power of closures this code is as simple as the original one (just the call to withLock is added, but that was intended change to satisfy our goal). However if we stick with the originally planned implementation of closures as inner classes, then the above code in fact means:

class SayHelloSafely {
  public void sayHello(final String to) {
    final String hello = "hello";
    withLock(new Runnable() { 
      public void run() {
        System.out.println(hello);
      }
    });
    withLock(new Runnable() { 
      public void run() {
        System.out.println(to);
      }
    });
  }
}

Even this simple example shows how ineffective trivial implementation of closures can be. Instead of one class, we have three. Each of them having significant overlaps in their constant pools. Given the expected proliferation of closure based APIs (as they are easy to use, much easier than innerclasses), this can lead to enormous and unnecessary waste of memory. As one who watches over performance of NetBeans I cannot silently let this happen.

The Mapping

Thankfully there is a cure. It is possible to write well performing implementation of closures using invokeDynamic and its method handles. Imagine that the above code is rewritten to use method handles (and that the withLock method now takes MethodHandle):

class SayHelloEffectively {
  private static MethodHandle first;
  private static MethodHandle second;
 
  public void sayHello(final String to) {
    MethodHandle addThis = MethodHandles.insertArgument(first, 0, this);
    withLock(first);
    MethodHandle applyToAndThis = 
      MethodHandle.insertArgument(MethodHandles.insertArgument(second, 0, to), 0, this);
    withLock(second);
  }
 
  private void firstRunnable() {
    final String hello = "hello";
    System.out.println(hello);
  }
  private void secondRunnable(String to) {
    System.out.println(to);
  }
 
  static {
    first = MethodHandles.forMethod(SayHelloEffectively.class, "firstRunnable");
    second = MethodHandles.forMethod(SayHelloEffectively.class, "secondRunnable");
  }
}

Please accept my appology for the above use of method handling API. It is just a sketch of the implementation. I have not found the javadoc to verify or even compile my code against it. Anyway it is clear that this conversion of closures is very constant pool friendly. Regardless of the amount of closures in a class, just one, shared constant pool is used. This avoids useless duplication of its entries in the inner classes.

The method handle solution shall also be well performant. Method handle combinators are supposed to be effective. The only slow operation is the reflective binding, but that happens just once, when the class is loaded (or the method is first used).

Also notice that this approach really supports closures. If a piece of code references some variable from outer block, it is easy (because of method handle combinators) to pass such variable into the closure method via an argument. Sort of like partially applied functions in high level languages.

Also, in all the closures for Java specifications, the this is treated differently than in inner classes. It is supposed to mean the outer class, which would require certain compiler transformations if closures were implemented as hidden inner classes. If closures are implemented as method handles, the meaning of this naturally stays the same, as the methods are really methods of the proper class.

Declination

At the beginning I accused Sun for having a hidden agenda. I do not mean it. Given all the problems the Sun's JDK team had to keep even to simple plans after open sourcing JDK, I cannot imagine how could it execute something as complex as this. Pretending that invokeDynamic is for other languages on top of HotSpot virtual machine and doing all of this just because of closures is too complex to be real. Also, when I explained the usefulness of invokeDynamic for closures to Peter von Ahe few years ago (when he was working for Sun and responsible for the JavaC compiler), he was pleasantly surprised and slightly interested in the topic. So I do not think the compiler team knew about the emerging effects of these two parallel efforts.

Anyway this is not that interesting. What is important is that there is a effective way to implement closures for Java. It is also good that most of the work (on runtime performance) has already been done by the Da Vinci Machine project. And last, but not least - it is very good that the same infrastructure used by non-Java languages on top of JVM will now be shared by core Java. This will make it a primary focus for wider groups of engineers make the invokeDynamic and method handle combinators more and more effective in the future.

<comments/>