New polyglot programming on the JVM

Many people in the Java environment have heard of it: the legendary GraalVM. This “magical” new virtual machine for Java is supposed to ensure sheer performance by compiling Java bytecode into native code. It eliminates the start-up overhead in particular, since large parts of the initialization are already handled by the compiler. This and similar statements can be read in many places. But this is by far not the only feature Oracle has given GraalVM. It also has the potential to usher in a new era of polyglot programming on the JVM. We are talking about the Truffle API, a generic framework for implementing interpreters. (This article has been originally published in devmio Volume 2, based on a German version published in late 2019.)

When the JVM was newly released in 1994, it was still inseparable from the Java language. It can be clearly seen that the JVM bytecode had been created in such a way that Java’s “flavor” of object-oriented programming could be mapped in it. This is consistent from a historical point of view, because after all, the JVM should be able to execute compiled Java code efficiently.

Over the years, both the JVM and Java received new features, optimizations, and improvements. It was clear that Sun regarded backward compatibility as the greatest asset. Once compiled, Java programs should remain executable in future JVM versions practically indefinitely.

The crowning achievement of backwards compatibility came just under ten years later with the release of Java 5. In the Java compiler, the type system was turned upside down with the introduction of generics. However, very little changed in the bytecode: Generic types are unceremoniously removed by the compiler in order to not endanger compatibility with existing code. This is known as type erasure.

Differently typed and untyped languages

In parallel with these developments, clever minds have been working on alternative language designs that are more or less based on Java.

With Scala, which appeared at about the same time as Java 5, its inventor Martin Odersky retained the basic concept of object-orientation, broke old habits, and at the same time, made functional programming workable on the JVM. Thanks to type erasure, Odersky was able to remove cruft from the type system with little regard for generics in Java 5. Scala’s advanced type system no longer plays any role in the generated bytecode.

About a year earlier, the Groovy language had already appeared, which originally wanted to compete as a standardized scripting language on the JVM. However, nothing came of the associated JSR 241, and Groovy evolved into an independent programming language. In contrast to Java, Groovy does without types in many places, so that methods are called more frequently by reflection. Only at runtime, it becomes clear in which class the respective method is implemented. For a call without reflection, however, the concrete method would already have to be known when the bytecode is generated. So you have to accept the reflection overhead.

Is the JVM big enough for multiple languages?

Scala and Groovy are far from the only examples of alternative JVM languages. Some are typed, others are more dynamic. What they all have in common, however, is that the JVM is an attractive platform because of its performance and existing libraries. Ports of existing languages (Jython, JRuby) also became increasingly popular in the 2000s.

Java 7 followed in 2011, bringing the long-hoped-for bytecode extension invokedynamic. This allows efficient implementation of dynamic method calls, which dominate in untyped languages. This was preceded by work on the so-called Da Vinci Virtual Machine, with which Sun experimented on first-class support for other languages on the JVM.

In Java itself, non-static method calls are made using the invokevirtual or invokeinterface instructions. Here, the argument types are already specified, but the implementing class is selected at runtime. In the simplest example:

class A { int f() { /* ... */ } }
class B extends A { @Override int f() { /* ... */ }}

Depending on which class an object x belongs to, either A.f() or B.f() is executed when x.f() is called.

In untyped languages, methods must regularly also be selected according to their arguments, e.g. to distinguish between the addition of numbers or of strings. For this purpose invokedynamic is used, for which the Oracle documentation explains the following: “[It] enables the runtime system to customize the linkage between a call site and a method implementation.”

Implementation effort

For ambitious developers who want to add a JVM backend to their language, there is nothing to stop them, were there not the problem of compiler construction. Therefore, interpreters are often built instead of compilers for languages, because then you can simply use the runtime infrastructure of the host environment directly.

In contrast, it is very difficult to produce custom, correct JVM bytecode. The invokedynamic instruction is a prime example of this: Each call requires a bootstrap method that provides the correct method handle, also an innovation in Java 7. While these handles can be called much more efficiently than the usual reflection methods, they have a more complex API.

But only a “real” compiler can make effective program optimizations. An interpreter based on the JVM also has the problem that you have two layers of interpreters on top of each other (JVM bytecode through the JVM, language source code through the language interpreter). It’s no surprise that this is not particularly conducive to performance.

Futamura’s vision

So what would it be like if there were a system that could transform a language interpreter into a language compiler fully automatically? In other words, a compiler-compiler, so to speak? This futuristic concept was already described by Yoshihiko Futamura in 1971 and is appropriately named Futamura Projection.

Futamura projections, also known as partial evaluations, refer to a set of technologies that can be used to specialize a given program for certain inputs. Suppose a function expects two input values. The first input value determines the program flow, e.g., by a cascade of if-else statements. One possible optimization here would be to generate specialized functions for all known possibilities of this input value (e.g., in the case of an enum) that do not contain any further conditions. To a certain degree, existing JVMs can already do this, optimizing e.g. virtual method calls if it is clear which concrete method is jumped to.

Scala has a similar optimization built into the compiler. Namely, the language allows generics to be instantiated with primitive types as well, with the compiler automatically boxing and unboxing. If the type parameter of a method or class is annotated with @specialized, variants are generated at compile time that work directly with native types. This can save both memory (no object allocation) and runtime overhead (no conversions).

Nevertheless, such optimizations are selective at best. A full Futamura projection is general and produces a so-called residual program, that is, a program in which the entire control flow, known at compile-time, is erased. You can imagine this applied to interpreters, which I will show in the following. A possible interface for an interpreter can be defined approximately as follows:

interface Interpreter {
    Object runCode(String code, Object input);
}

This interpreter executes two different logics:

Interpreter logic (given by the implementation of runCode).
Program logic (given by the program code; to be precise, this is not the source code, but a syntax tree).

The first Futamura projection requires, on the basis of a given program text, optimizing the runCode method in such a way that there is no more interpreter logic, but only program logic. There are two more projections, but they are not relevant for this article.

Many decades after the first description of this concept, Oracle has succeeded with GraalVM in presenting a production-ready implementation of the first Futamura projection: You can write an interpreter – for example, for JavaScript – in Java and automatically get a JIT-optimizing compiler that beats the previously specialized interpreters Rhino and Nashorn.

Let’s stay with JS as an example of a language that is now universally used and for which there are good reasons to want to embed it in the JVM. With the help of the Truffle API, which is shipped with GraalVM, multiplication can be implemented in JavaScript, for example, as shown below (heavily abbreviated):

public abstract class JSMultiplyNode extends JSBinaryNode {

  public abstract Object execute(Object a, Object b);

  @Specialization(guards = "b > 0", rewriteOn = ArithmeticException.class)
  protected int doIntBLargerZero(int a, int b) {
    return Math.multiplyExact(a, b);
  }

  @Specialization(rewriteOn = ArithmeticException.class)
  protected int doInt(int a, int b) {
    // ...
  }

  @Specialization
  protected double doDouble(double a, double b) {
    return a * b;
  }

  // ...
}

Simple annotations like @Specialization are used to signal to Truffle which methods should be called for special object types. In general, anything can be multiplied by anything in JavaScript, but for the cases int, int and double, double efficient implementations are given here.

Thanks to the Truffle API, you can systematically implement an interpreter that is automatically used by GraalVM as a JIT compiler. Performance optimizations are automatically taken into account, as annotated above.

GraalVM vs. JVM

At this point, we should take a close look at how Truffle relates to the ecosystem. To do this, we need to clarify some terminology.

GraalVM is understood to be both the entire project led by Oracle and a (currently) Java 11-compatible implementation of the Java Virtual Machine. GraalVM joins a number of other implementations, e.g. Azul, and exists alongside HotSpot, Oracle’s most widely used JVM, which is shipped with the OpenJDK.

Code running on GraalVM continues to be interpreted as bytecode as usual. A so-called Ahead-of-Time (AOT) compiler is responsible for the conversion into native code. In contrast to the familiar Just-in-Time (JIT) compiler, bytecode is already translated into machine code before execution. The AOT compiler of GraalVM generates a native image that contains a minimal runtime infrastructure (SubstrateVM). AOT compilation is also used in Android Runtime (ART).

Alternative languages, such as JavaScript, are implemented using the Truffle framework, which can run on both GraalVM and SubstrateVM. In addition, some languages implemented with Truffle (but not all) can also be run on the HotSpot VM (or other JVMs), although performance is lower in this case.

Seamless embedding of such languages into Java programs is done through the Polyglot API, which abstracts over languages and allows the exchange of objects. As can be seen in the code snippet above, the usual Java types are used internally. Conversely, it is also very easy to call Java code from JS code. Nevertheless, GraalVM allows the guest code to run in isolation (separate heap and garbage collection) and to fine-tune the set of allowed operations.

A new era?

JavaScript is currently one of the best-supported languages in GraalVM. However, for those who are less interested in cool tech, but wonder what concrete advantages GraalVM brings in practice, the developers at Oracle have made provisions.

Firstly, the GraalVM distribution comes with a complete Node.js environment, which also includes the node command line tool. This means that most common npm packages can also be executed seamlessly in a Java environment. This gives GraalVM a huge advantage over both Rhino and Nashorn, which do not support many newer language constructs from the ES6 and later revisions.

Second, a polyglot application can be seamlessly translated into native code. Oracle has achieved a high degree of orthogonality in its features.

What could only be dreamed of in the past is already becoming reality today: Mixed JS/JVM projects can be built with little effort and executed efficiently. If you use Gradle as a build tool, there is a Node.js plug-in that can be used to install and build npm packages. The JS files packaged this way can be loaded directly into the JVM and executed.

However, there are other supported languages besides JavaScript:

If you are interested in statistical calculations, you can easily integrate R.
Thanks to Python 3 support, modern Python code can be executed, in contrast to Jython.
Ruby applications can be parallelized, since the restriction by the Global Interpreter Lock (GIL) is removed.

Even for people who don’t think much of Java, a look at GraalVM might be worthwhile: Of course, the Polyglot API can also be used from JavaScript, Ruby, or Python, which is why you can also mix these languages together. Fascinatingly, GraalVM implements the Chrome DevTools Protocol, which is normally used to debug JavaScript in the browser, but thanks to Polyglot API, this also applies to other languages. This can be used to set breakpoints in Chrome, e.g. in Ruby code that starts a JavaScript web server.

However, the Truffle API is also excellent for designing domain-specific languages. How this is done is demonstrated in an example repository.

Native code? In my JVM?

The languages mentioned above are usually always executed in a VM and an interpreter, respectively. So it is not so surprising that they can also be implemented on a JVM. However, GraalVM can also execute LLVM bitcode - a kind of assembly language. This allows you to implement performance- or memory-critical code in system-level languages like Rust and run it side-by-side with Java code.

It is worth taking a closer look at this interoperability. Until now, if you wanted to run native code in the JVM, you essentially had two options:

Java Native Interface (JNI), an official part of the Java specification.
Java Native Access (JNA), provided as a community library

Differences between the two approaches can be seen, for example, in the fact that JNA does not provide for manipulating Java objects or calling methods directly from C/C++. In contrast, native code does not need to be compiled with special header files for use in JNA. Additionally, there are numerous other differences, e.g. in performance.

What both approaches have in common is a platform-specific native library must be loaded for Java code that wants to call native code. As a rule, such a library must be binary-compatible with C. If it is not the standard C library, either the user is responsible for installing it, or the Java library must supply it. In the worst case, variants for Windows, Linux, macOS, BSD, and others must be considered. Furthermore, crashes in native code automatically crash the entire JVM.

GraalVM improves this situation significantly. Instead of integrating native code directly, the so-called bitcode of the LLVM project is used. Similar to GraalVM, LLVM is an infrastructure project that is driven by Apple and Google, among others. Under their umbrella, a modern C/C++ compiler (Clang) and a generic, optimizing backend that other compilers can use for code generation are being developed. The Rust project uses LLVM for this purpose. In a sense, LLVM bitcode can be thought of as a competitor to JVM bytecode. However, unlike JVM bytecode, LLVM bitcode is usually transformed into native code (AOT) before execution. GraalVM, on the other hand, can execute the bitcode and integrate it into the polyglot infrastructure.

In addition, the Enterprise Edition of GraalVM also offers a sandbox mode for C programs. In this mode, all memory accesses and system calls are wrapped, so that the same access restrictions can be configured as JavaScript. In particular, crashes do not take down the whole application with them, but are expressed in an exception. Want an example? Consider the following C code (adapted from a blog entry by the Graal team):

#include <stdio.h>

int main(int argc, char *argv[]) {
  printf("number of arguments: %n\n", argc);
  return 0;
}

The error is that the format modifier %n stores the number of bytes written so far in the argument, but argc is not a pointer. Common compilers warn about this problem, but compile the program anyway. With the Java code below, you can load and run the bitcode:

class Sandbox {
  public static void main(String[] args) throws IOException {
    Source source =
      Source.newBuilder("llvm", new File("bug.bc")).build();

    Context.Builder builder =
      Context.newBuilder()
        .allowIO(true)
        .option("llvm.sandboxed", "true");
    try (Context polyglot = builder.build()) {
      polyglot.eval(source).execute();
    }
    catch (Exception ex) {
      System.out.println("something went wrong: " + ex);
    }
  }
}

At runtime, you get this exception:

number of arguments: something went wrong: org.graalvm.polyglot.PolyglotException: Illegal pointer access: 0x0000000000000001

Normally, the pure C program would abort.

Running Rust

Thanks to the sandbox, even buggy C programs can be executed safely. However, those who cannot or do not want to use the Enterprise Edition must resort to a safe programming language instead. Rust is a good choice for this, since the compiler can also generate LLVM bitcode.

The challenge here is creating a robust integration between the object-oriented Java world and the more system-oriented Rust world. This integration is based on the fact that Java and Rust functions can call each other and exchange objects.

To understand this, the structure of the LLVM bitcode is important. This is similar to the structure of the JVM byte code: A set of functions (optionally with parameters and return value) is defined. The function bodies then consist of a series of instructions, e.g. arithmetic routines or calls to other functions. LLVM requires that the bitcode is type-correct (just like JVM).

Another common feature is that the bitcode can be incomplete. This means that some functions are only declared, i.e. they must be defined elsewhere for a call to be successful. In Java, this is the case when a method of another class is called. The JVM loads classes lazily, i.e. when a call is made, the classpath is searched for the appropriate class.

With LLVM or native code, this is a bit more complicated. Normally, you would have to rely on the operating system’s dynamic linking. In the context of Graal, this is not possible, since the JVM cannot reload arbitrary libraries (GraalVM offers a command line option to load a list of native libraries already at startup time, but this is platform-dependent). Instead, you must instruct the Rust compiler by suitable compiler flags to generate statically linked bitcode files. This only works if all used dependencies are implemented in Rust and are also available as LLVM bitcode. However, system-related code sometimes calls routines of the operating system. GraalVM can make such calls by passing them on 1:1. The Enterprise Edition can also intercept and redirect a list of calls in sandboxing mode.

If Java code now calls a function from Rust, this is searched for in the loaded bitcode by name, because overloading isn’t possible in Rust. The reverse is not as simple. First, the GraalVM installation provides a C header file in which certain functions are declared that can be used to load Java classes, instantiate them, and select and call their methods. These C functions are implemented in GraalVM and are not present in the bitcode. During the execution of Rust code, they are converted into corresponding Java reflection calls. Known types like integer are converted automatically.

Typical code that can be used to create and manipulate Java objects can be seen below.

unsafe {
  let buf = polyglot_new_instance(polyglot_java_type("java.lang.StringBuffer\0"));
  let value = polyglot_from_string_n(str, str.len(), "UTF-8\0".as_ptr());
  polyglot_invoke(buf, "append\0".as_ptr(), value);
  // ...
}

Despite all interoperability, one limitation remains: It is not possible to manage pointers to Java objects outside the local stack of a Rust function. In particular, it is not possible to wrap them in more complex data structures. This is because the GraalVM pointers do not behave like ordinary pointers; therefore arrays are also difficult to represent and pointer arithmetic is impossible.

Conclusion

It’s worth taking a close look at GraalVM, because it has many radically new capabilities. The development is progressing rapidly: While currently the official GraalVM is only compatible with Java 8, releases for newer Java versions are already being worked on at full speed. Notwithstanding this, polyglot programming is also largely possible with newer JVMs, if you can do without generating native code. It is quite possible that we will soon see more Java on the desktop again thanks to the combination of these features.