Android = Java

The Java community is now swamped with discussions about Oracle's patent suit against Google's Android platform. I've been contributing my opinion in several places, but there is one critical topic that needs repeating the same comments everywhere... so, this blog spills the beans once and completely.

The 8th Millennium Problem: Android = Java?

The announcement that a researcher had proved P != NP, a few days ago, caused lots of enthusiasm in the programming community - at least for a couple days, until the first reviewers showed several flaws in the proof. I have studied the subject in my CS grad, but admittedly I don't know the advanced math to follow these proofs (P = NP? is one of the Clay Institute's Millennium Problems for a good reason.) So, let's talk about a much simpler equation: Is Android equivalent to Java? Notice I didn't say equal, I've said equivalent, just like in P = NP.

Equivalent class/bytecode formats

In many levels, the Android = Java equivalence is obvious. Android apps are written in the Java(TM) language, and compiled by the JDK's javac compiler (or equivalent, like ECJ). This produces standard Java bytecode (.class files). These files are then converted into Android's .dex, for all practical purposes just a different file format for Java classes. Yes it's a better format; an improvement over Sun's ~1994 design. But you can also take a GIF image and convert it into the superior PNG format, and both images will be perfectly equivalent even though the byte streams are completely different.

Equivalent file formats are largely implementation detail, usually for optimization. We could avoid all the trouble of fighting the MPEGLA video codec patents, for example, if we simply settled for a less efficient video stream without sophisticated, differential cross-frame compression techniques.

Android's different classfile design had several motivations; but avoidance of Sun's IP was certainly a major factor. Anyway, Google didn't move enough away of Java. Both formats are very equivalent. They differ in specific low-level data structures, but they are semantically identical, storing the exact same information. I'm sure a JavaSE or JavaME VM could easily add a .dex parser to its system classloader to load "Android classes".

The Android SDK relies on the fact that the .java -> .class -> .dex conversion is both trivial and lossless. The "lossless" part is important: While GIF = PNG, a lossy JPG file is less equivalent - it won't decode the same exact information. If the JVM and Dalvik were really independent, you could hardly write a relatively simple tool that converts compiled code from one form to the other, without any compromise: no loss of information, no bloat to compensate features that are first-class in one VM but not in the other, no extra runtime layer to implement one VM's core APIs in terms of the other's.

(I know how complex the dx translator is. I've looked the source code. The bytecode translator is big, a full decompiler/re-compiler, complete with SSA building. But this translation is still conceptually trivial; the mapping from Java to Dalvik bytecode is smooth, by design. Stack versus register architectures is optimization detail; important things like the VM-level typesystem are identical.)

Equivalent VMs

The Dalvik = JVM equivalence is also easy to show. It's not just the source or bytecode formats: it's their runtime counterpart too. Once an "Android class" is loaded by the Dalvik VM, it walks like a Java class and quacks like a Java class. If you know Java programming (down to advanced and low-level details), you know Android programming. It's just a matter of learning some new APIs and framework concepts. They are equivalent systems.

Remember Microsoft's .NET? When .NET was introduced, the Java community was quick to denounce .NET as a Java ripoff. I was in that crowd, but today I know better. Yeah it was largely a ripoff; the C# 1.0  language for one thing... the easiest way to distinguish programs of either language was style conventions - e.g. toString() versus ToString(). But in the critical VM specs, Microsoft did a good homework. The CLR, CLI, and core frameworks, are sufficiently different from Java so we cannot state a JVM = CLR equivalence. You can't run a simple file-format conversion tool on your compiled Java classes and get something that runs on the bare .NET runtime.

Want proof? Just look at the IKVM. This is a very interesting project that enables cross-compilation of Java into .NET, so your Java code will run unchanged on top of the CLR (or equivalent .NET runtime like Mono)... except that the IKVM is not a simple, dx-like file format converter. The conversion from Java classes, and the adaptation of its core APIs, to .NET, are very complex, for anything beyond HelloWorld. Internals of each platform like reflection, security, concurrency, exception handling, bytecode verification, I/O and other core APIs, are roughly similar in feature set but completely different in details and corner cases - forcing IKVM to jump through endless hoops so Java code will run on a .NET VM. This also needs a very large layer of extra runtime, basically the full JavaSE APIs adapted from OpenJDK sources. I've been loosely tracking IKVM's development for years - reading the great IKVM Blog - so I have a good idea of the massive effort that takes to adapt Java code and JavaSE apps to .NET. (The work is not yet complete; and the parts that are complete often have some performance tradeoff.)

(The old Visual J++ Visual J# was not a simple Java-to-.NET translator either. I won't discuss it, but it's sufficient to state that Visual J#'s compatibility with Java was much inferior than even very early IKVM releases.)

I've brought P = NP to the debate; somebody could bring Turing-equivalence and state that any Turing-complete platform / language / VM is equivalent to any other. This is true, but irrelevant. The Turing model is way too general; taking it by face value would destroy the entire software patent system (not a bad thing though!). We need to draw the line of JVM-equivalence in the sand, closer to pragmatic needs than Turing-equivalence. In my opinion, the trivial binary format translation, and extremely high source-level and runtime compatibility, puts Android definitely inside the line of Java equivalence.

Equivalent APIs and Runtime

Android uses a pretty big subset of the JavaSE APIs. These APIs (from Harmony) are clean-room implementations, but they have JavaSE as a model. Harmony would even be JavaSE certified, if not by the TCK licensing issue. This doesn't change the fact that the Harmony and JavaSE APIs are completely equivalent - on purpose, not by accident. As Charles Nutter, of JRuby fame, recently wrote:

Android supports a rough (but large) subset of the Java 1.5 class libraries. That subset is large enough that projects as complicated as JRuby can basically run unmodified on Android, with very few restrictions.

It seems that Dalvik is close enough to the JVM that it should be fully compliant with a big chunk of the JVM specification, including the complete and very detailed JMM (as Android supports Java-style threading and concurrency, down to the advanced java.util.concurrent package). So much for "Dalvik is a new VM" or "Dalvik doesn't run Java classes" (statements found in 90% of the blogs and forums debating the suit).

Final Thoughts

This blog is not about the merits of the Oracle vs Google suit. I will ignore (and I may delete) any off-topic comments (outside the issue of Android = Java equivalence). I'm just sick of the "Android is completely unrelated to Java" nonsense; Google and Android advocates must find much better arguments than this.

(I am saving my full judgment of the suit for the future, when all details and outcomes are known. Unless you have inside info (I don't), don't be naïve. Stay cool. We don't really know Oracle's - or Google's - full intentions and plans. We don't know the behind-the-scenes story, since 2007 when Google first announced Android (causing massive disruption of the JavaME ecosystem) and Sun was pissed off but had to put their tail between the legs. I don't buy altruistic motivations from any billion-dollar, shareholder-controlled company: not Google, not Oracle, not even old-beloved Sun. Anyway let's wait and see.)

I don't think Google was incompetent when they created a Java-based platform that didn't deviate further from Java (like .NET did). Dalvik, and the Android frameworks,  are probably as good as you can get while balancing the desire to keep huge compatibility with existing Java code and libraries, Java talent, and Java toolchain. Microsoft took the longer breath to create .NET without the benefit of instant migration from Java. Google didn't.

The Android = Java equivalence is obviously not all-inclusive in both sides (not a bijection). Each platform has some unique APIs, and of course, Android is a complete operating system including a Linux-based kernel, graphics and telephony stacks, etc. I'm obviously only talking about the common parts: the Java-based userland / application frameworks that rely on Java sources, Java classes (whatever the format), Java APIs (including thousands of common JavaSE APIs), and very remarkably a Java-like Virtual Machine. A precise statement of Android's relationship to other Java platforms might use the concept of Editions or Profiles. I remember a blogger saying something like "there's no 'J' in Android". Well, it's never too late: my suggestion is renaming it to Java GE (Java Google Edition). That would clear the confusion once and for all. ;-)

UPDATE: I wrote this blog after some research to refresh my knowledge of the discussed issues; but since posting I've read some tweets worth attaching here. Oracle's Terrence Barr points to a Good analysis: "Is Android Evil?", from Andreas Constantinou. (My summary: Android is quite closed from the POV of handset vendors and carriers; this doesn't make Android "evil" but it surely puts Android safely outside the rainbow-pooping-Unicorns domain of fully-open platforms... not that Java is in that domain either, like Oracle's suit shows.). From the other side of the fence, Google's Bob Lee states that Dalvik's design was driven by technical concerns, in his knowledge IP wasn't a factor; Bob links to the article Dalvik Optimization and Verification With dexopt. (My summary: Yes there is a lot of good, technical ideas behind the different Dalvik VM. That is not disputed.)