A First Taste of InvokeDynamic

Greetings, readers!

Over the past couple weeks I've had a few departures from typical JRuby development. I consider it a working vacation. I'm hoping to report on all of it soon, but for now we'll focus on one of the most exciting items: JSR-292, otherwise known as "InvokeDynamic".

I've reported on invokedynamic previously (InvokeDynamic: Actually Useful?), and of course the technical bits of John Rose's blog should be required reading for anyone interested in this stuff. What I'm going to try to do today is give you an inside picture of the pieces of InvokeDynamic and how they fit together. It will be technical, but everyone should be able to follow it. Ready?

The Problem

Any description of a solution must first describe the problem.

As you probably know, Java is a statically-typed language. That means the types of all variables, method arguments, method return values, and so on must be known before runtime. In Java's case, this also means all variable types must be declared explicitly, everywhere. A variable cannot be untyped, and a method cannot accept untyped parameters nor return an untyped value. Types are pervasive.

The problem, put simply, is this: Because Java is the primary language on the JVM, almost all language implementations on the JVM are written in Java. When implementing a statically-typed language, especially one with structure and rules similar to Java, this is not much of a problem. But when implementing a dynamic language that stubbornly refuses to yield type information until runtime, all this static-typing is a real pain in the neck. Of course this is pretty much the same situation when implementing a dynamic language on top of C or C++ or C#, since they're all generally statically-typed languages too. Or is it? An example is in order.

public class <span style="font-weight:bold;">Hello</span> {
  public static <span style="font-weight:bold;">void</span> main(<span style="font-weight:bold;">String[]</span> args) {
    <span style="font-weight:bold;">java.util.List</span> list = new <span style="font-weight:bold;">java.util.ArrayList</span>();
    for (<span style="font-weight:bold;">int</span> i = 0; i < 5; i++) {
      <span style="font-weight:bold;">String</span> newString = args[0] + i;
    <span style="font-weight:bold;">System</span>.out.println(list);

Here we see a short, reasonably simple snippit of Java code. An ArrayList is constructed, populated with five strings based on the incoming first command-line argument and a numeric iteration count, and then displayed as a string on the console. The type declarations (shown in bold) represent a lot of the visual noise, the "ceremony" that dynamic language fans decry. From a usability perspective, they're both a positive and negative influence; they noise up the code and require more typing, but they also make it trivial to determine the type of a variable (in most cases) or build tools that safely restructure your code (so-called "refactoring"). From a technical perspective, they give the "javac" compiler all the information it needs to produce very clean, optimized bytecode, and they give the JVM itself type information it uses to execute and optimize that bytecode at runtime. Ahh, but what about the bytecode?

If we peel the Java layer away, the situation changes a bit. At the JVM bytecode level, types are still visible, but they're not nearly as prevalent. Here's the same code in bytecode, with the type names again in boldface:

public static <span style="font-weight:bold;">void</span> main(<span style="font-weight:bold;">java.lang.String[]</span>);
   0: new #2; //class <span style="font-weight:bold;">java/util/ArrayList</span>
   3: dup
   4: invokespecial #3; //Method <span style="font-weight:bold;">java/util/ArrayList</span>."<init>":()<span style="font-weight:bold;">V</span>
   7: astore_1
   8: iconst_0
   9: istore_2
   10: iload_2
   11: iconst_5
   12: if_icmpge 50
   15: new #4; //class <span style="font-weight:bold;">java/lang/StringBuilder</span>
   18: dup
   19: invokespecial #5; //Method <span style="font-weight:bold;">java/lang/StringBuilder</span>."<init>":()<span style="font-weight:bold;">V</span>
   22: aload_0
   23: iconst_0
   24: aaload
   25: invokevirtual #6; //Method <span style="font-weight:bold;">java/lang/StringBuilder</span>.append:(L<span style="font-weight:bold;">java/lang/String</span>;)<span style="font-weight:bold;">Ljava/lang/StringBuilder</span>;
   28: iload_2
   29: invokevirtual #7; //Method <span style="font-weight:bold;">java/lang/StringBuilder</span>.append:(<span style="font-weight:bold;">I</span>)L<span style="font-weight:bold;">java/lang/StringBuilder</span>;
   32: invokevirtual #8; //Method <span style="font-weight:bold;">java/lang/StringBuilder</span>.toString:()L<span style="font-weight:bold;">java/lang/String</span>;
   35: astore_3
   36: aload_1
   37: aload_3
   38: invokeinterface #9,  2; //InterfaceMethod <span style="font-weight:bold;">java/util/List</span>.add:(L<span style="font-weight:bold;">java/lang/Object</span>;)<span style="font-weight:bold;">Z</span>
   43: pop
   44: iinc 2, 1
   47: goto 10
   50: getstatic #10; //Field <span style="font-weight:bold;">java/lang/System</span>.out:L<span style="font-weight:bold;">java/io/PrintStream</span>;
   53: aload_1
   54: invokevirtual #11; //Method <span style="font-weight:bold;">java/io/PrintStream</span>.println:(L<span style="font-weight:bold;">java/lang/Object</span>;)<span style="font-weight:bold;">V</span>
   57: return

Since not everyone reads

JVM bytecode

like their native language, a description of these operations is in order.

Java provides what's called an "operand stack" for bytecode it executes. The stack is analogous to registers in a "real" CPU, acting as temporary storage for values against which operations (like math, method calls, and so on) are to be performed. So most JVM bytecode spends its time either manipulating that stack by pushing, popping, duping, and swapping values, or executing operations that produce or consume values. It's a pretty simple mechanism. So then, with a general understanding of the operand stack, lets look at the bytecode itself:

  • The "load" and "store" instructions are all local variable accesses. "load" retrieves a local variable and pushes it on the stack. "store" pops a value off the stack and stores it in a local variable. The prefix indicates whether the value is an object or "reference" type (denoted by "a") or one of the primitive types (denoted by "i" for integer, "f" for float, and so on). The standard load and store operations take an argument (embedded along with the operation into the bytecode) to indicate which indexed local variable to work with, but there are specialized bytecodes (denoted by a suffixed underscore and digit) for a "compressed" representation of heavily-used low-index variables.
  • The "invoke" bytecodes are what you might expect: method invocations. Method invocations consume zero or more arguments from the stack and in some cases a receiver object as well. "virtual" refers to a normal call to a non-interface method on an object receiver. "interface" refers to an interface invocation on an object receiver. "static" refers to a static invocation, or one that does not require an object to call against. The "strange quark" of the bunch is "invokespecial", which is used for calling constructors and superclass implementations of methods. You'll notice a couple invokespecials above paired with "new" operations; "new" instantiates the object and "invokespecial" initializes it.
  • The "const" instructions are what you might guess: they push a constant on the stack. Again, the prefix and suffix denote type and "compressed" opcodes for specific values, respectively.
  • "aaload" and all "*aload" operations are retrievals out of an array. As with local variables, the first letter indicates the type of the array. Here, the "aaload" is our retrieval of args[0].
  • "iinc" is an integer increment operation. The arguments are the index of the local variable and how much to increment it by (usually 1).
  • "if_icmpge" performs a conditional jump after testing whether the second-topmost int on the stack (indicated by the "i" in "icmpge") is greater than or equal to the topmost int on the stack (the >= relationship represented by the "ge" in "icmpge"). This is our "for" loop test i < 5 reversed to act as a loop exit condition rather than a loop continue condition. The looping itself is provided by the "goto" operation further down (yes, the JVM has goto...it's just Java that doesn't have goto).
  • Finally, we see the "return" instruction, which represents the void return from main. If it were a return of a specific value or object type, it would be preceded by the appropriate type character.

Now the astute reader may already have noticed that other than being specified as reference or primitive types, the opcodes themselves have no type information. Even beyond that, there are no actual variable declarations at the bytecode level whatsoever. The only types we see come in the form of opcode prefixes (as in aload, iinc, etc) and the method signatures against which we execute invoke* operations. The stack itself is also untyped; we push a reference type (aload) one minute and push a primitive type (iload) the next (though values on the stack do not "lose" their types). And when I tell you that the type signatures shown above for each method invocation or object construction are simply strings stuffed into the class's pool of constants...well...now you may start to realize that Java's sometimes touted, oft-maligned static-typing...is just a façade.

The Greatest Trick

Let's dispense with the formality once and for all. The biggest lie that's been spread about the JVM (ok, maybe the biggest after "it's slow") is that it's never going to be a good host for dynamic languages. "But look at Java," people cry, "it's so staticky and rigid; it's far too difficult to implement a dynamic language on top of that!" And in a very naive way, they're partially correct. Writing a language implementation in Java and following Java's rules can certainly make life difficult for a dynamic language implementer. We end up stripping types (making everything Object, since we don't know types until runtime), boxing types (stuffing primitives in carrier objects, to simplify passing them through our Object-only code), and boxing array arguments (since many dynamic languages also have flexible "arities" or numbers of arguments, and others allow optional, "rest", and other special argument types). With each sacrifice we make, we lose many of the benefits static typing provides us, not to mention confounding the JVM's efforts to optimize.

But it's not nearly as bad as it seems. Because much of the rigid, static nature of Java is in the language itself (and not the JVM) we can in many cases ignore the rules. We don't have to declare local variable types. We can juggle items on the stack at will. We can cheat in clever ways, allowing much of normal code execution to proceed with very little type information. In many cases we can get that code to run nearly as well as statically-typed code of twice the size, because the JVM is so dynamic already at its core. JVM bytecode is our assembly, and it's a powerful tool in the right hands.

Unfortunately, on current JVMs, there's one place we absolutely, positively must follow the rules: method invocation.

Know Thyself

Question: In the bytecode above, all invocations came with a formal "signature" representing the type to call against and the types of the method's arguments and return value. If we do not know those types until runtime, and they may be variant even then...how do we support invocation in a dynamic language?

Answer: Very carefully.

Because we are bound to following Java's method invocation rules, the once sunny and clear forecast turns rather cloudy. Every invocation has to be called against a known type. Its arguments must be known types. Its return value must be a known type. Making matters worse, we can't even provide signatures with similar types; the signatures must exactly match the method we intend to invoke. So we understand limitation #1: invocations are statically typed.

There's another way this affects dynamic languages, especially those that may not present normal Java types or that run in an interpreted mode for some part of execution: Invocations must be against real methods on real types. There's simply no way to tell the JVM that instead of calling method W on type X with param Y and return value Z, I want you to enter this interpreter loop; don't mind the types, we'll figure it out for you. Oh no, you have to be part of the Java club and present a normal Java type to get invocation privileges. That's limitation #2: invocations must be against Java methods on Java types.

1 2 3 4 Page 1
Page 1 of 4