Sunday, 8 February 2009

Tail calls on the JVM: work in progress

The terms proper tail recursion and tail call elimination are used to describe the ability for a computation to flow through an arbitrary number of functions via tail calls in a bounded amount of stack space. Consequently, correct implementation of tail call elimination has been regarded as an essential feature for functional programming languages for over two decades. Without it, many functional idioms are prone to causing stack overflows.

Microsoft's .NET platform is built upon a Common Language Run-time (CLR) that was designed to support a wide variety of programming languages including functional languages and, consequently, the CLR has had tail call elimination for the best part of a decade. There are already several commercial products that depend upon the correct handling of tail calls in the CLR.

Although the JVM has many advantages and is the VM of choice for millions of developers, the lack of support for tail call elimination on the JVM has seriously impeded the development and uptake of functional languages like Scala and Clojure and that has, in turn, greatly reduced the diversity of tools and solutions available on the JVM.

Sun have been making noises about implementing tail call elimination in the HotSpot virtual machine for years but there had been no visible signs of progress until Arnold Schwaighofer's announcement on the OpenJDK mailing list a few weeks ago stating that he had successfully implemented tail call elimination on the JVM.

This is very exciting news and represents the single most important step the JVM has ever made toward being a genuine common language run-time. If support for tail call elimination makes it into the JVM then both existing and new functional languages (such as OCamlJava) will no doubt see vastly more interest as they will be infinitely more suitable for writing production quality code.