Skip to content

Interop Between Java and Scala

9
Feb
2009

Sometimes, the simplest things are the most difficult to explain.  Scala’s interoperability with Java is completely unparalleled, even including languages like Groovy which tout their tight integration with the JVM’s venerable standard-bearer.  However, despite this fact, there is almost no documentation (aside from chapter 29 in Programming in Scala) which shows how this Scala/Java integration works and where it can be used.  So while it may not be the most exciting or theoretically interesting topic, I have taken it upon myself to fill the gap.

Classes are Classes

The first piece of knowledge you need about Scala is that Scala classes are real JVM classes.  Consider the following snippets, the first in Java:

public class Person {
    public String getName() {
        return "Daniel Spiewak";
    }
}

…and the second in Scala:

class Person {
  def getName() = "Daniel Spiewak"
}

Despite the very different syntax, both of these snippets will produce almost identical bytecode when compiled.  Both will result in a single file, Person.class, which contains a default, no-args constructor and a public method, getName(), with return type java.lang.String.  Both classes may be used from Scala:

val p = new Person()
p.getName()       // => "Daniel Spiewak"

…and from Java:

Person p = new Person();
p.getName();      // => "Daniel Spiewak"

In the case of either language, we can easily swap implementations of the Person class without making any changes to the call-site.  In short, you can use Scala classes from Java (as well as Java classes from Scala) without ever even knowing that they were defined within another language.

This single property is the very cornerstone of Scala’s philosophy of bytecode translation.  Wherever possible — and that being more often than not — Scala elements are translated into bytecode which directly corresponds to the equivalent feature in Java.  Scala classes equate to Java classes, methods and fields within those classes become Java methods and fields.

This allows some pretty amazing cross-language techniques.  For example, I can extend a Java class within Scala, overriding some methods.  I can in turn extend this Scala class from within Java once again with everything working exactly as anticipated:

class MyAbstractButton extends JComponent {
  private var pushed = false
 
  def setPushed(p: Boolean) {
    pushed = p
  }
 
  def getPushed = pushed
 
  override def paintComponent(g: Graphics) {
    super.paintComponent(g)
 
    // draw a button
  }
}
public class ProKitButton extends MyAbstractButton {
    // do something uniquely Apple-esque
}

Traits are Interfaces

This is probably the one interoperability note which is the least well-known.  Scala’s traits are vastly more powerful than Java’s interfaces, often leading developers to the erroneous conclusion that they are incompatible.  Specifically, traits allow method definitions, while interfaces must be purely-abstract.  Yet, despite this significant distinction, Scala is still able to compile traits into interfaces at the bytecode level…with some minor enhancements.

The simplest case is when the trait only contains abstract members.  For example:

trait Model {
  def value: Any
}

If we look at the bytecode generated by compiling this trait, we will see that it is actually equivalent to the following Java definition:

public interface Model {
    public Object value();
}

Thus, we can declare traits in Scala and implement them as interfaces in Java classes:

public class StringModel implements Model {
    public Object value() {
        return "Hello, World!";
    }
}

This is precisely equivalent to a Scala class which mixes-in the Model trait:

class StringModel extends Model {
  def value = "Hello, World!"
}

Things start to get a little sticky when we have method definitions within our traits.  For example, we could add a printValue() method to our Model trait:

trait Model {
  def value: Any
 
  def printValue() {
    println(value)
  }
}

Obviously, we can’t directly translate this into just an interface; something else will be required.  Scala solves this problem by introducing an ancillary class which contains all of the method definitions for a given trait.  Thus, when we look at the translation for our modified Model trait, the result looks something like this:

public interface Model extends ScalaObject {
    public Object value();
 
    public void printValue();
}
 
public class Model$class {
    public static void printValue(Model self) {
        System.out.println(self.value());
    }
}

Thus, we can get the effect of Scala’s powerful mixin inheritance within Java by implementing the Model trait and delegating from the printValue() method to the Model$class implementation:

public class StringModel implements Model {
    public Object value() {
        return "Hello, World!";
    }
 
    public void printValue() {
        Model$class.printValue(this);
    }
 
    // method missing here (see below)
}

It’s not perfect, but it allows us to use some of Scala’s more advanced trait-based functionality from within Java.  Incidentally, the above code does compile without a problem.  I wasn’t actually aware of this fact, but “$” is a legal character in Java identifiers, allowing interaction with some of Scala’s more interesting features.

There is, however, one little wrinkle that I’m conveniently side-stepping: the $tag method.  This is a method defined within the ScalaObject trait designed to help optimize pattern matching.  Unfortunately, it also means yet another abstract method which must be defined when implementing Scala traits which contain method definitions.  The correct version of the StringModel class from above actually looks like the following:

public class StringModel implements Model {
    public Object value() {
        return "Hello, World!";
    }
 
    public void printValue() {
        Model$class.printValue(this);
    }
 
    public int $tag() {
        return 0;
    }
}

To be honest, I’m not sure what is the “correct” value to return from $tag.  In this case, 0 is just a stub, and I’m guessing a safe one since StringModel is the only subtype of Model.  Can anyone who knows more about the Scala compiler shed some light on this issue?

Generics are, well…Generics

Generics are (I think) probably the coolest and most well-done part of Scala’s Java interop.  Anyone who has more than a passing familiarity with Scala will know that its type system is significantly more powerful than Java’s.  Some of this power comes in the form of its type parameterization, which is vastly superior to Java’s generics.  For example, type variance can be handled at declaration-site, rather than only call-site (as in Java):

abstract class List[+A] {
  ...
}

The + notation prefixing the A type parameter on the List class means that List will vary covariantly with its parameter.  In English, this means that List[String] is a subtype of List[Any] (because String is a subtype of Any).  This is a very intuitive relationship, but one which Java is incapable of expressing.

Fortunately, Scala is able to exploit one of the JVM’s most maligned features to support things like variance and higher-kinds without sacrificing perfect Java interop.  Thanks to type erasure, Scala generics can be compiled to Java generics without any loss of functionality on the Scala side.  Thus, the Java translation of the List definition above would be as follows:

public abstract class List<A> {
    ...
}

The variance annotation is gone, but Java wouldn’t be able to make anything of it anyway.  The huge advantage to this translation scheme is it means that Java’s generics and Scala’s generics are one and the same at the bytecode level.  Thus, Java can use generic Scala classes without a second thought:

import scala.Tuple2;
 
...
Tuple2<String, String> me = new Tuple2<String, String>("Daniel", "Spiewak");

Obviously, this is a lot more verbose than the Scala equivalent, “("Daniel", "Spiewak")“, but at least it works.

Operators are Methods

One of the most obvious differences between Java and Scala is that Scala supports operator overloading.  In fact, Scala supports a variant of operator overloading which is far stronger than anything offered by C++, C# or even Ruby.  With very few exceptions, any symbol may be used to define a custom operator.  This provides tremendous flexibility in DSLs and even your average, every-day API (such as List and Map).

Obviously, this particular language feature is not going to translate into Java quite so nicely.  Java doesn’t support operator overloading of any variety, much less the über-powerful form defined by Scala.  Thus, Scala operators must be compiled into an entirely non-symbolic form at the bytecode level, otherwise Java interop would be irreparably broken, and the JVM itself would be unable to swallow the result.

A good starting place for deciding on this translation is the way in which operators are declared in Scala: as methods.  Every Scala operator (including unary operators like !) is defined as a method within a class:

abstract class List[+A] {
  def ::[B >: A](e: B) = ...
 
  def +[B >: A](e: B) = ...
}

Since Scala classes become Java classes and Scala methods become Java methods, the most obvious translation would be to take each operator method and produce a corresponding Java method with a heavily-translated name.  In fact, this is exactly what Scala does.  The above class will compile into the equivalent of this Java code:

public abstract class List<A> {
    public <B super A> List<B> $colon$colon(B e) { ... }
 
    public <B super A> List<B> $plus(B e) { ... }
}

Every allowable symbol in Scala’s method syntax has a corresponding translation of the form “$trans“.  A list of supported translations is one of those pieces of documentation that you would expect to find on the Scala website.  However, alas, it is absent.  The following is a table of all of the translations of which I am aware:

Scala Operator Compiles To
= $eq
> $greater
< $less
+ $plus
- $minus
* $times
/ div
! $bang
@ $at
# $hash
% $percent
^ $up
& $amp
~ $tilde
? $qmark
| $bar
\ $bslash
: $colon

Using this table, you should be able to derive the “real name” of any Scala operator, allowing its use from within Java.  Of course, the idea solution would be if Java actually supported operator overloading and could use Scala’s operators directly, but somehow I doubt that will happen any time soon.

Odds and Ends

One final tidbit which might be useful: @BeanProperty.  This is a special annotation which is essentially read by the Scala compiler to mean “generate a getter and setter for this field”:

import scala.reflect.BeanProperty
 
class Person {
  @BeanProperty
  var name = "Daniel Spiewak"
}

The need for this annotation comes from the fact that Scala’s ever-convenient var and val declarations actually generate code which looks like the following (assuming no @BeanProperty annotation):

// *without* @BeanProperty
public class Person {
    private String name = "Daniel Spiewak";
 
    public String name() {
        return name;
    }
 
    public void name_$eq(String name) {
        this.name = name;
    }
}

This works well from Scala, but as you can see, Java-land is not quite paradise.  While it is certainly feasible to use the _$eq syntax instead of the familiar set/get/is triumvirate, it is not an ideal situation.

Adding the @BeanProperty annotation (as we have done in the earlier Scala snippet) solves this problem by causing the Scala compiler to auto-generate more than one pair of methods for that particular field.  Rather than just value and value_$eq, it will also generate the familiar getValue and setValue combination that all Java developers will know and love.  Thus, the actual translation resulting from the Person class in Scala will be as follows:

public class Person {
    private String name = "Daniel Spiewak";
 
    public String name() {
        return name;
    }
 
    public String getName() {
        return name();
    }
 
    public void name_$eq(String name) {
        this.name = name;
    }
 
    public void setName(String name) {
        name_$eq(name);
    }
}

This merely provides a pair of delegates, but it does suffice to smooth out the mismatch between Java Bean-based frameworks and Scala’s elegant instance fields.

Conclusion

This has been a whirlwind, disjoint tour covering a fairly large slice of information on how to use Scala code from within Java.  For the most part, things are all roses and fairy tales.  Scala classes map precisely onto Java classes, generics work perfectly, and pure-abstract traits correspond directly to Java interfaces.  Other areas where Scala is decidedly more powerful than Java (like operators) do tend to be a bit sticky, but there is always a way to make things work.

If you’re considering mixing Scala and Java sources within your project, I hope that this article has smoothed over some of the doubts you may have had regarding its feasibility.  As David Pollack says, Scala is really “just another Java library”.  Just stick scala-library.jar on your classpath and all of your Scala classes should be readily available within your Java application.  And given how well Scala integrates with Java at the language level, what could be simpler?

Hacking Buildr: Interactive Shell Support

12
Jan
2009

Last week, we looked at the unfortunately-unexplored topic of Scala/Java joint compilation.  Specifically, we saw several different ways in which this functionality may be invoked covering a number of different tools.  Among these tools was Buildr, a fast Ruby-based drop-in replacement for Maven with a penchant for simple configuration.  In the article I mentioned that Buildr doesn’t actually have support for the Scala joint compiler out of the box.  In fact, this feature actually requires the use of a Buildr fork I’ve been using to experiment with different extensions.  Among these extensions is a feature I’ve been wanting from Buildr for a long time: the ability to launch a pre-configured interactive shell.

For those coming from a primarily-Java background, the concept of an interactive shell may seem a bit foreign.  Basically, an interactive shell — or REPL, as it is often called — is a line-by-line language interpreter which allows you to execute snippets of code with immediate result.  This has been a common tool in the hands of dynamic language enthusiasts since the days of LISP, but has only recently found its way into the world of mainstream static languages such as Scala.

interactive-shells.png

One of the most useful applications of these tools is the testing of code (particularly frameworks) before the implementations are fully completed.  For example, when working on my port of Clojure’s PersistentVector, I would often spin up a Scala shell to quickly test one aspect or another of the class.  As a minor productivity plug, JavaRebel is a truly invaluable tool for development of this variety.

The problem with this pattern of work is it requires the interactive shell in question to be pre-configured to include the project’s output directory on the CLASSPATH.  While this isn’t usually so bad, things can get very sticky when you’re working with a project which includes a large number of dependencies.  It isn’t too unreasonable to imagine shell invocations stretching into the tens of lines, just to spin up a “quick and dirty” test tool.

Further complicating affairs is the fact that many projects do away with the notion of fixed dependency paths and simply allow tools like Maven or Buildr to manage the CLASSPATH entirely out of sight.  In order to fire up a Scala shell for a project with any external dependencies, I must first manually read my buildfile, parsing out all of the artifacts in use.  Then I have to grope about in my ~/.m2/repository directory until I find the JARs in question.  Needless to say, the productivity benefits of this technique become extremely suspect after the first or second expedition.

For this reason, I strongly believe that the launch of an interactive shell should be the responsibility of the tool managing the dependencies, rather than that of the developer.  Note that Maven already has some support for shells in conjunction with certain languages (Scala among them), but it is as crude and verbose as the tool itself.  What I really want is to be able to invoke the following command and have the appropriate shell launched with a pre-configured CLASSPATH.  I shouldn’t have to worry about the language of my project, the location of my repository or even if the shell requires extra configuration on my platform.  The idea is that everything should all work auto-magically:

$ buildr shell

This is exactly what the interactive-shell branch of my Buildr fork is designed to accomplish.  Whenever the shell task is invoked, Buildr looked through the current project and attempts to guess the language involved.  This guesswork is required for a number of other features, so Buildr is actually pretty accurate in this area.  If the language in question is Groovy or Scala, then the desired shell is obvious.  Java does not have an integrated shell, which means that the default behavior on a Java project would be to raise an error.

However, the benefits of interactive shells are not limited to just the latest-and-greatest languages.  I often use a Scala shell with Java projects, and for certain things a JRuby shell as well (jirb).  Thus, my interactive shell extension also provides a mechanism to allow users to override the default shell on a per-project basis:

define 'my-project' do
  shell.using :clj
end

With this configuration, regardless of the language used by the compiler for “my-project”, Buildr will launch the Clojure REPL whenever the shell task is invoked.  The currently supported shells and their corresponding Buildr identifiers:

  • Clojure’s REPL — :clj
  • Groovy’s Shell — :groovysh
  • JRuby’s IRB — :jirb
  • Scala’s Shell — :scala

It is also possible to explicitly launch a specific shell.  This is useful for situations where you might want to use the Scala shell for testing some things and the JRuby IRB for quickly prototyping other ideas (I do this a lot).  The command to launch the JIRB shell in the context of my-project would be as follows:

$ buildr my-project:shell:jirb

As a special value-added feature, all of these shells (except for Groovy’s, which is weird) will be automatically configured to use JavaRebel for the project compilation target classes if it can be automatically detected.  This detection is performed by examining REBEL_HOME, JAVA_REBEL, JAVAREBEL and JAVAREBEL_HOME environment variables in order.  If any one of these points to a directory which contains javarebel.jar or points directly to javarebel.jar itself, the configuration is assumed and the respective shell invocation is appropriately modified.

javarebel-integration.png

Best of all, this support is implemented using a highly-extensible framework similar to Buildr’s own Compiler API.  It’s very easy for plugin implementors or even average developers to simply drop-in a new shell provider, perhaps for an internal language or even some unexpected application.  The core functionality of shell detection is integrated into Buildr itself, but this in no way hampers extensibility.  For example, I could easily create a third-party .rake plugin for Buildr which added support for a whole new language (e.g. Haskell).  In this plugin, I could also define a new shell provider which would be the default for projects using that language (e.g. GHCi).

Open Question

The good news is that this feature has been discussed extensively on the buildr-user mailing-list and the prevailing opinion seems to be that it should be folded into the main Buildr distribution.  Exactly what form this will take has yet to be decided.  The bad news is that there is still some dispute about a fundamental aspect of this feature’s operation.

The question revolves around what the exact behavior should be when the shell task is invoked.  Should Buildr detect the project (or sub-project) you are in and automatically configure the shell’s CLASSPATH accordingly?  This would give the interactive shell access to different classes depending on the current working directory.  Alternatively, should there be one all-powerful shell per-buildfile configured at the root level?  This would allow your shell to remain consistent throughout the project, regardless of your current directory.  However, it would also mean that some configuration would be required in order to enable the functionality.  (more details of this debate can be found on the mailing-list).

Additionally, what should the exact syntax be for invoking a specific shell?  Rake 0.8 allows tasks to take parameters enclosed within square brackets.  Thus, the syntax would be something more like the following:

$ buildr collection:shell[jirb]

In some sense, this is more logical since it reflects the fact that a single task, shell, is taking care of the work of invoking stuff.  On the other hand, it’s a little less consistent with the rest of Buildr’s tasks, particularly things like “test:TestClass” and so on.  This too is a matter which has yet to be settled.

All in all, this is a pretty experimental branch which is very open (and desirous) of outside input.  How would you use a feature like this?  Is there anything missing from what I have presented?  What design path should be we take with regards to project-local vs global shell configurations?

If you feel like adding your voice to the chorus, feel free to leave a comment or (better yet) post a reply on the mailing-list thread.  You’re also perfectly free to fork my remote branch at GitHub to better experiment with things yourself.  The root of the whole plate of spaghetti is the lib/buildr/shell.rb file.  Bon appetit!

Gun for Hire (off topic)

7
Jan
2009

Just in case you thought Christmas was over, I have a late gift for the world: I’m available for hire!  Ok, so maybe this wasn’t exactly the stocking-stuffer you were expecting, but it’s the thought that counts.

I’m announcing my availability for employment as a part-time developer.  Those of you who follow this blog are probably already familiar with my areas of expertise, so I don’t think there is a need to bore you with a rehash.  Resume available on request!

Anyway, my preference would be a project where I get to use multiple different languages, particularly Scala and Clojure, but I’m flexible.  If you think my skills would make a positive addition to your team, shoot me an email!

Joint Compilation of Scala and Java Sources

5
Jan
2009

One of the features that the Groovy people like to flaunt is the joint compilation of .groovy and .java files.  This is a fantastically powerful concept which (among other things) allows for circular dependencies between Java, Groovy and back again.  Thus, you can have a Groovy class which extends a Java class which in turn extends another Groovy class.

All this is old news, but what you may not know is the fact that Scala is capable of the same thing.  The Scala/Java joint compilation mode is new in Scala 2.7.2, but despite the fact that this release has been out for more than two months, there is still a remarkable lack of tutorials and documentation regarding its usage.  Hence, this post…

Concepts

For starters, you need to know a little bit about how joint compilation works, both in Groovy and in Scala.  Our motivating example will be the following stimulating snippet:

// foo.scala
class Foo
 
class Baz extends Bar

…and the Java class:

// Bar.java
public class Bar extends Foo {}

If we try to compile foo.scala before Bar.java, the Scala compiler will issue a type error complaining that class Bar does not exist.  Similarly, if we attempt the to compile Bar.java first, the Java compiler will whine about the lack of a Foo class.  Now, there is actually a way to resolve this particular case (by splitting foo.scala into two separate files), but it’s easy to imagine other examples where the circular dependency is impossible to linearize.  For the sake of example, let’s just assume that this circular dependency is a problem and cannot be handled piece-meal.

In order for this to work, either the Scala compiler will need to know about class Bar before its compilation, or vice versa.  This implies that one of the compilers will need to be able to analyze sources which target the other.  Since Scala is the language in question, it only makes sense that it be the accommodating one (rather than javac).

What scalac has to do is literally parse and analyze all of the Scala sources it is given in addition to any Java sources which may also be supplied.  It doesn’t need to be a full fledged Java compiler, but it does have to know enough about the Java language to be able to produce an annotated structural AST for any Java source file.  Once this AST is available, circular dependencies may be handled in exactly the same way as circular dependencies internal to Scala sources (because all Scala and all Java classes are available simultaneously to the compiler).

Once the analysis phase of scalac has blessed the Scala AST, all of the Java nodes may be discarded.  At this point, circular dependencies have been resolved and all type errors have been handled.  Thus, there is no need to carry around useless class information.  Once scalac is done, both the Foo and the Baz classes will have produced resultant Foo.class and Baz.class output files.

However, we’re still not quite done yet.  Compilation has successfully completed, but if we try to run the application, we will receive a NoClassDefFoundError due to the fact that the Bar class has not actually been compiled.  Remember, scalac only analyzed it for the sake of the type checker, no actual bytecode was produced.  Bar may even suffer from a compile error of some sort, as long as this error is within the method definitions, scalac isn’t going to catch it.

The final step is to invoke javac against the .java source files (the same ones we passed to scalac) adding scalac’s output directory to javac’s classpath.  Thus, javac will be able to find the Foo class that we just compiled so as to successfully (hopefully) compile the Bar class.  If all goes well, the final result will be three separate files: Foo.class, Bar.class and Baz.class.

Usage

Although the concepts are identical, Scala’s joint compilation works slightly differently from Groovy’s from a usage standpoint.  More specifically: scalac does not automatically invoke javac on the specified .java sources.  This means that you can perform “joint compilation” using scalac, but without invoking javac you will only receive the compiled Scala classes, the Java classes will be ignored (except by the type checker).  This design has some nice benefits, but it does mean that we usually need at least one extra command in our compilation process.

All of the following usage examples assume that you have defined the earlier example in the following hierarchy:

  • src
    • main
      • java
        • Bar.java
      • scala
        • foo.scala
  • target
    • classes

Command Line

# include both .scala AND .java files
scalac -d target/classes src/main/scala/*.scala src/main/java/*.java

javac -d target/classes \
      -classpath $SCALA_HOME/lib/scala-library.jar:target/classes \
       src/main/java/*.java

Ant

<target name="build">
    <scalac srcdir="src/main" destdir="target/classes">
        <include name="scala/**/*.scala"/>
        <include name="scala/**/*.java"/>
    </scalac>
 
    <javac srcdir="src/main/java" destdir="${scala.library}:target/classes" 
           classpath="target/classes"/>
</target>

Maven

One thing you gotta love about Maven: it’s fairly low on configuration for certain common tasks.  Given the above directory structure and the most recent version of the maven-scala-plugin, the following command should be sufficient for joint compilation:

mvn compile

Unfortunately, there have been some problems reported with the default configuration and complex inter-dependencies between Scala and Java (and back again).  I’m not a Maven…maven, so I can’t help too much, but as I understand things, this POM fragment seems to work well:

<plugin>
    <groupId>org.scala-tools</groupId>
    <artifactId>maven-scala-plugin</artifactId>
 
    <executions>
        <execution>
            <id>compile</id>
            <goals>
            <goal>compile</goal>
            </goals>
            <phase>compile</phase>
        </execution>
 
        <execution>
            <id>test-compile</id>
            <goals>
            <goal>testCompile</goal>
            </goals>
            <phase>test-compile</phase>
        </execution>
 
        <execution>
            <phase>process-resources</phase>
            <goals>
            <goal>compile</goal>
            </goals>
        </execution>
    </executions>
</plugin>
 
<plugin>
    <artifactId>maven-compiler-plugin</artifactId>
    <configuration>
        <source>1.5</source>
        <target>1.5</target>
    </configuration>
</plugin>

You can find more information on the mailing-list thread.

Buildr

Joint compilation for mixed Scala / Java projects has been a long-standing request of mine in Buildr’s JIRA.  However, because it’s not a high priority issue, the developers were never able to address it themselves.  Of course, that doesn’t stop the rest of us from pitching in!

I had a little free time yesterday afternoon, so I decided to blow it by hacking out a quick implementation of joint Scala compilation in Buildr, based on its pre-existing support for joint compilation in Groovy projects.  All of my work is available in my Buildr fork on GitHub.  This also includes some other unfinished goodies, so if you want only the joint compilation, clone just the scala-joint-compilation branch.

Once you have Buildr’s full sources, cd into the directory and enter the following command:

rake setup install

You may need to gem install a few packages.  Further, the exact steps required may be slightly different on different platforms.  You can find more details on Buildr’s project page.

With this highly-unstable version of Buildr installed on your unsuspecting system, you should now be able to make the following addition to your buildfile (assuming the directory structure given earlier):

require 'buildr/scala'
 
# rest of the file...

Just like Buildr’s joint compilation for Groovy, you must explicitly require the language, otherwise important things will break.  With this slight modification, you should be able to build your project as per normal:

buildr

This support is so bleeding-edge, I don’t even think that it’s safe to call it “pre-alpha”.  If you run into any problems, feel free to shoot me an email or comment on the issue.

Conclusion

Joint compilation of Java and Scala sources is a profound addition to the Scala feature list, making it significantly easier to use Scala alongside Java in pre-existing or future projects.  With this support, it is finally possible to use Scala as a truly drop-in replacement for Java without modifying the existing infrastructure beyond the CLASSPATH.  Hopefully this article has served to bring slightly more exposure to this feature, as well as provide some much-needed documentation on its use.

What is Hindley-Milner? (and why is it cool?)

29
Dec
2008

Anyone who has taken even a cursory glance at the vast menagerie of programming languages should have at least heard the phrase “Hindley-Milner”.  F#, one of the most promising languages ever to emerge from the forbidding depths of Microsoft Research, makes use of this mysterious algorithm, as do Haskell, OCaml and ML before it.  There is even some research being undertaken to find a way to apply the power of HM to optimize dynamic languages like Ruby, JavaScript and Clojure.

However, despite widespread application of the idea, I have yet to see a decent layman’s-explanation for what the heck everyone is talking about.  How does the magic actually work?  Can you always trust the algorithm to infer the right types?  Further, why is Hindley-Milner is better than (say) Java?  So, while those of you who actually know what HM is are busy recovering from your recent aneurysm, the rest of us are going to try to figure this out.

Ground Zero

Functionally speaking, Hindley-Milner (or “Damas-Milner”) is an algorithm for inferring value types based on use.  It literally formalizes the intuition that a type can be deduced by the functionality it supports.  Consider the following bit of psuedo-Scala (not a flying toy):

def foo(s: String) = s.length
 
// note: no explicit types
def bar(x, y) = foo(x) + y

Just looking at the definition of bar, we can easily see that its type must be (String, Int)=>Int.  As humans, this is an easy thing for us to intuit.  We simply look at the body of the function and see the two uses of the x and y parameters.  x is being passed to foo, which expects a String.  Therefore, x must be of type String for this code to compile.  Furthermore, foo will return a value of type Int.  The + method on class Int expects an Int parameter; thus, y must be of type Int.  Finally, we know that + returns a new value of type Int, so there we have the return type of bar.

This process is almost exactly what Hindley-Milner does: it looks through the body of a function and computes a constraint set based on how each value is used.  This is what we were doing when we observed that foo expects a parameter of type String.  Once it has the constraint set, the algorithm completes the type reconstruction by unifying the constraints.  If the expression is well-typed, the constraints will yield an unambiguous type at the end of the line.  If the expression is not well-typed, then one (or more) constraints will be contradictory or merely unsatisfiable given the available types.

Informal Algorithm

The easiest way to see how this process works is to walk it through ourselves.  The first phase is to derive the constraint set.  We start by assigning each value (x and y) a fresh type (meaning “non-existent”).  If we were to annotate bar with these type variables, it would look something like this:

def bar(x: X, y: Y) = foo(x) + y

The type names are not significant, the important restriction is that they do not collide with any “real” type.  Their purpose is to allow the algorithm to unambiguously reference the yet-unknown type of each value.  Without this, the constraint set cannot be constructed.

Next, we drill down into the body of the function, looking specifically for operations which impose some sort of type constraint.  This is a depth-first traversal of the AST, which means that we look at operations with higher-precedence first.  Technically, it doesn’t matter what order we look; I just find it easier to think about the process in this way.  The first operation we come across is the dispatch to the foo method.  We know that foo is of type String=>Int, and this allows us to add the following constraint to our set:

X  \mapsto  String

The next operation we see is +, involving the y value.  Scala treats all operators as method dispatch, so this expression actually means “foo(x).+(y).  We already know that foo(x) is an expression of type Int (from the type of foo), so we know that + is defined as a method on class Int with type Int=>Int (I’m actually being a bit hand-wavy here with regards to what we do and do not know, but that’s an unfortunate consequence of Scala’s object-oriented nature).  This allows us to add another constraint to our set, resulting in the following:

X  \mapsto  String

Y  \mapsto  Int

The final phase of the type reconstruction is to unify all of these constraints to come up with real types to substitute for the X and Y type variables.  Unification is literally the process of looking at each of the constraints and trying to find a single type which satisfies them all.  Imagine I gave you the following facts:

  • Daniel is tall
  • Chris is tall
  • Daniel is red
  • Chris is blue

Now, consider the following constraints:

Person1 is tall

Person1 is red

Hmm, who do you suppose Person1 might be?  This process of combining a constraint set with some given facts can be mathematically formalized in the guise of unification.  In the case of type reconstruction, just substitute “types” for “facts” and you’re golden.

In our case, the unification of our set of type constraints is fairly trivial.  We have exactly one constraint per value (x and y), and both of these constraints map to concrete types.  All we have to do is substitute “String” for “X” and “Int” for “Y” and we’re done.

To really see the power of unification, we need to look at a slightly more complex example.  Consider the following function:

def baz(a, b) = a(b) :: b

This snippet defines a function, baz, which takes a function and some other parameter, invoking this function passing the second parameter and then “cons-ing” the result onto the second parameter itself.  We can easily derive a constraint set for this function.  As before, we start by coming up with type variables for each value.  Note that in this case, we not only annotate the parameters but also the return type.  I sort of skipped over this part in the earlier example since it only sufficed to make things more verbose.  Technically, this type is always inferred in this way.

def baz(a: X, b: Y): Z = a(b) :: b

The first constraint we should derive is that a must be a function which takes a value of type Y and returns some fresh type Y’ (pronounced like “why prime“).  Further, we know that :: is a function on class List[A] which takes a new element A and produces a new List[A].  Thus, we know that Y and Z must both be List[Y'].  Formalized in a constraint set, the result is as follows:


X  \mapsto  (Y=>Y’ )

Y  \mapsto  List[Y' ]

Z  \mapsto  List[Y' ]

Now the unification is not so trivial.  Critically, the X variable depends upon Y, which means that our unification will require at least one step:


X  \mapsto  ( List[Y' ]=>Y’ )

Y  \mapsto  List[Y' ]

Z  \mapsto  List[Y' ]

This is the same constraint set as before, except that we have substituted the known mapping for Y into the mapping for X.  This substitution allows us to eliminate X, Y and Z from our inferred types, resulting in the following typing for the baz function:

def baz(a: List[Y']=>Y', b: List[Y']): List[Y'] = a(b) :: b

Of course, this still isn’t valid.  Even assuming that Y' were valid Scala syntax, the type checker would complain that no such type can be found.  This situation actually arises surprisingly often when working with Hindley-Milner type reconstruction.  Somehow, at the end of all the constraint inference and unification, we have a type variable “left over” for which there are no known constraints.

The solution is to treat this unconstrained variable as a type parameter.  After all, if the parameter has no constraints, then we can just as easily substitute any type, including a generic.  Thus, the final revision of the baz function adds an unconstrained type parameter “A” and substitutes it for all instances of Y’ in the inferred types:

def baz[A](a: List[A]=>A, b: List[A]): List[A] = a(b) :: b

Conclusion

…and that’s all there is to it!  Hindley-Milner is really no more complicated than all of that.  One can easily imagine how such an algorithm could be used to perform far more complicated reconstructions than the trivial examples that we have shown.

Hopefully this article has given you a little more insight into how Hindley-Milner type reconstruction works under the surface.  This variety of type inference can be of immense benefit, reducing the amount of syntax required for type safety down to the barest minimum.  Our “bar” example actually started with (coincidentally) Ruby syntax and showed that it still had all the information we needed to verify type-safety.  Just a bit of information you might want to keep around for the next time someone suggests that all statically typed languages are overly-verbose.