Monday, March 10, 2008

Duby: A Type-Inferred Ruby-Like JVM Language

It's been one of those nights, my friends! An outstanding night!

All day Sunday I had the stupids. It was probably related to a few beers on Saturday night, or the couple glasses of red wine before that. Whatever it was, I didn't trust myself to work on any JRuby bugs for fear of introducing problems if my brain clicked off mid-stream. So I started playing around with my old bytecode generating DSL from a few months back. Then things got interesting.

We've long wanted to have a "Ruby-like" language, probably a subset of Ruby syntax, that we could compile to solid, fast, idiomatic JVM bytecode. Not a compiler for Ruby, with all the bells and whistles that make Ruby both difficult to support and inefficient to use for implementing itself. A real subset language that produces clean, tight JVM bytecode on par with what you'd get from compiled Java. But better, because it still looks and feels mostly like Ruby.

So I wrote one! And I used my bytecode library too!

Let's say we want to implement our good friend fib.
class Foo
def fib(n)
if (n < 2)
n
else
fib(n - 2) + fib(n - 1)
end
end
end
This is normal ruby code. Given a Fixnum input, it calculates the appropriate fibbonaci number and returns it. It's slow in Ruby for a few reasons:
  1. In JRuby, it uses a boxed integer value. Matz's Ruby and Rubinius use tagged integers to improve performance, and we rely on the JVM to optimize as much as it can (which turns out to be a *lot*). But it's still way slower than using primitives directly.
  2. The comparison operations, integer math operations, and fib operations are all dynamic invocations. So there's at least a bit of method lookup cost, and then a bunch of abstraction cost. You can reduce it, but you can't eliminate it.
  3. There are many Ruby features that influence performance negatively even when you're not using them. It's very difficult, for example, to optimally store local variables when the local scope can be captured at any time. So either you rely on tricks, or you store local variables on the heap and deal with them being slow.
When working with a statically-typed language, you can eliminate all of this. In Java, for example, you have both object types and primitive types; primitive operations are extremely fast and eventually JIT down to machine-code equivalents; and the feature set is suitably narrow to allow current JVMs to do amazing levels of optimization.

But of course Java has its problems too. For one, it does very little guessing or "inferring" of types for you, which means you generally have to declare them all over the place. On local variables, on parameters, on return types. C# 3.0 aims to correct this by adding type inference all over, but then there's still other syntactic hassle using any C-like language: curly braces, semicolons, and other gratuitous syntax that make up a lot of visual noise.

Wouldn't be nice if we could take the code above, add some type inference logic, and turn it into a fast, static-typed language?
class Foo
def fib(n)
{n => java.lang.Integer::TYPE, :return => java.lang.Integer::TYPE}
if (n < 2)
n
else
fib(n - 2) + fib(n - 1)
end
end
end
And there it is! This is the same code as before, but now it's been decorated with a little type declaration block (in the form of a Ruby hash/map) immediately preceding the body of the method. The type decl describes that the 'n' argument is to be mapped to a primitive int, and the method itself will return a primitive int (and yes, I know those could be inferred too...it shall be soon). The rest of the method just works like you'd expect, except that it's all primitive operations, chosen based on the inferred types. For the bold, here's the javap disassembly output from the compiler:
Compiled from "superfib.rb"
public class Foo extends java.lang.Object{
public int fib(int);
Code:
0: iload_1
1: ldc #10; //int 2
3: if_icmpge 10
6: iload_1
7: goto 27
10: aload_0
11: iload_1
12: ldc #10; //int 2
14: isub
15: invokevirtual #12; //Method fib:(I)I
18: aload_0
19: iload_1
20: ldc #13; //int 1
22: isub
23: invokevirtual #12; //Method fib:(I)I
26: iadd
27: ireturn

public Foo();
Code:
0: aload_0
1: invokespecial #15; //Method java/lang/Object."<init>":()V
4: return

}
A few items to point out:
  • A default constructor is generated, as you'd expect in Java. This will be expected to also recognize "def initialize" constructors. I haven't decided if I'll allow overloading or not.
  • Notice the type signature for fib and all the type signatures for calls it makes are correctly inferred to the correct types.
  • Notice all the comparison and arithmetic operations are compiled to the correct bytecodes (iadd, isub, if_icmpge and so on).
And the performance is what you'd hope for:
$ jruby -rjava -e "t = Time.now; 5.times {Java::Foo.new.fib(35)}; p Time.now - t"
0.681
$ jruby -rnormalfib -e "t = Time.now; 5.times {Foo.new.fib(35)}; p Time.now - t"
27.851
Here's another example, with some string operations thrown in:
class Foo
def bar
{:return => java.lang.String}

'here'
end
end

class Foo
# reopening classes works in the same file only (for now)
def baz(a)
{a => java.lang.String}

b = "foo"
a = a + bar + b
puts a
end
end
It works, of course:
$ jruby -rjava -e "Java::Foo.new.baz('Type inference is fun')"
Type inference is funherefoo
And once again, the disassembled output:
Compiled from "stringthing.rb"
public class Foo extends java.lang.Object{
public java.lang.String bar();
Code:
0: ldc #13; //String here
2: areturn

public void baz(java.lang.String);
Code:
0: ldc #15; //String foo
2: astore_2
3: aload_1
4: checkcast #17; //class java/lang/String
7: aload_0
8: invokevirtual #19; //Method bar:()Ljava/lang/String;
11: invokevirtual #23; //Method java/lang/String.concat:(Ljava/lang/String;)Ljava/lang/String;
14: checkcast #17; //class java/lang/String
17: aload_2
18: invokevirtual #23; //Method java/lang/String.concat:(Ljava/lang/String;)Ljava/lang/String;
21: astore_1
22: getstatic #29; //Field java/lang/System.out:Ljava/io/PrintStream;
25: aload_1
26: invokevirtual #34; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
29: return

public Foo();
Code:
0: aload_0
1: invokespecial #36; //Method java/lang/Object."<init>":()V
4: return

}
Notice here that the + operation was detected as acting on two strings, so it was compiled to call String#concat rather than try to do a numeric operation. These sorts of mappings are simple to add, and since there's type information everywhere it's also easy to come up with cool ways to map Ruby syntax to Java types.

My working name for this is going to be Duby, pronounced "Doobie", after Duke plus Ruby. Duby! It has a nice ring to it. It may be subject to change, but that's what we'll go with for the moment.

Currently, Duby supports only the features you see here. It's a very limited subset of Ruby right now, and the subset doesn't support all Java primitive types, for example, so there's a lot of blanks to be filled. It also doesn't support static (class) methods, doesn't wire up "initialize" methods, doesn't support packages (for namespacing) or imports (to shrink type names) or superclasses or interfaces or enums or generics or what have you. But it's already functional for simple code, as you see here, so I think it's a great start for 10 hours of work. The rest will come, as needed and as time is available.

What are my plans for it? Well many of you may know Rubinius, an effort to reimplement Ruby in Ruby, modeled after the design of many Smalltalk VMs. Well, in order to make JRuby more approachable to Ruby developers, Duby seems like the best way to go. They'll be able to write mostly idiomatic Ruby code and know it will both perform at Java speeds and provide compile-type checking that all is wired up correctly. So we can avoid the overhead of "turtles all the way down" by just teaching one turtle how to speak JVM bytecode and building on that.

I also hope this will lead to lots of new ideas about how to implement languages for the JVM. It's certainly attractive to language users to be able to contribute to language implementations using the language in question, and if we can come up with compilers and sub-languages like Duby it could make the JVM more approachable to a wide range of developers.

Oh, and for those of you curious: the Duby compiler is written mostly in Ruby too.

26 comments:

  1. That seems a bit dubious :-D

    Seriously: that's really cool. Now what about parsing those type annotations in regular Ruby code, too, and optimizing JRuby's code generation for that?

    Maybe you could also allow type annotations like this in JavaDoc-style comments to methods, so you have documentation and performance enhancements at the same time!

    ReplyDelete
  2. @martin I've been looking into exactly that sort of thing, trying to decide on a minimally-invasive way to allow people to mark up code for performance. I'm interested to see what the reaction is to Duby to see if others are open to this kind of language-bending. I also want to get imports working (after some sleep) so that declarations can just be like {:a => int, :b => String}. There's a lot more to do, but I think this could be very powerful.

    ReplyDelete
  3. It was probably related to a few beers on Saturday night, or the couple glasses of red wine before that.

    As a uni lecturer of mine once said -

    Beer before wine, that's fine. Wine before beer, oh dear.

    ReplyDelete
  4. This is a great step in a very good direction.

    Is it possible to use Scala-style optional typing?

    name [':' type]

    I guess that type declarations may be needed for local variables, instance variables and class variables, as well as for method parameters and result types. At first sight the use of colons in declarations doesn't clash with their use elsewhere in Ruby syntax.

    Like Patrick, I'd prefer the typing to be in terms of Ruby's types, rather than Java's, so that the same optimisation could be used in other implementations.

    ReplyDelete
  5. charles, that rocks! keep the innovations coming :)

    would it be an advantage for going between ruby and duby if annotation were in a ruby comment and perhaps not confusable with ruby code. for instance (borrowing functional notation):

    class Foo
      def mult(x,y)  #(int,int)->int
        x*y
      end
    end

    ReplyDelete
  6. Where can I get Duby? I don't see a link.

    ReplyDelete
  7. This looks cool! It isn't really type inference what you're doing, but it definitely saves a lot of type-typing ;)

    ReplyDelete
  8. This is a pretty cool development, and I hope it doesn't get shelved away.

    It looks a bit more like how Cobra handles type inference, with all those precondition hints to help the compiler generate native code.

    ReplyDelete
  9. @laurence Me too...but I don't plan to shelve it away, and I'm already devising ways to use it for certain pieces of JRuby internals.

    @chris Ok, so would you say then that Scala is not a type-inferred language, since it requires you to specify argument types? And to answer your question, the main compiler logic is all in Ruby, though it uses our Java integration layer heavily to reflectively inspect Java types. The bytecode layer is a Ruby wrapper around ASM.

    ReplyDelete
  10. @superfast Hey, thanks for those links, they both look interesting. We're probably going to start looking into profile-based JIT after 1.1, since we have mixed-mode execution already. So these will be very useful to read. Thank you!

    ReplyDelete
  11. def fib(Integer n) => Integer
    ...
    end

    Break with MRI. Stop fighting it.

    ReplyDelete
  12. I'd very much prefer pulling the signature out of the method definition:

    sig fib(Integer) => Integer
    def fib(n)
    ...
    end

    or (valid ruby syntax)

    sig Integer, Integer
    def fib(n)
    ...
    end

    Anyway, excellent idea. jruby becomes increasingly interesting.

    (Any chance jruby will have macros one day?)

    ReplyDelete
  13. Hi Charles,

    Just for the record, here's what it would look like in Scala:

    class Fibo {
      def fib(n: Int): Int =
        if (n < 2) n else fib(n - 2) + fib(n - 1)
    }

    The bytecodes look similar to those generated by the Duby version:

    public int fib(int);
    Code:
    Stack=4, Locals=2, Args_size=2
    0: iload_1
    1: iconst_2
    2: if_icmpge 9
    5: iload_1
    6: goto 24
    9: aload_0
    10: iload_1
    11: iconst_2
    12: isub
    13: invokevirtual #16; //Method fib:(I)I
    16: aload_0
    17: iload_1
    18: iconst_1
    19: isub
    20: invokevirtual #16; //Method fib:(I)I
    23: iadd
    24: ireturn

    I guess you're after something that looks more like Ruby. By the way, this algo isn't tail recursive, so larger numbers passed in could cause other performance problems. A little searching on the web and I found this tail-recursive algorithm:

    class FiboTail {

      def fib(n: Int): Int = {

        def aux(n: Int, next: Int, result: Int): Int =
          if (n == 0)
            result
          else
            aux(n - 1, next + result, next)

        aux(n, 1, 0)
      }
    }

    The bytecodes for this one show just one call to the auxiliary function aux (which I defined as a local function inside fib):

    public int fib(int);
    Code:
    Stack=4, Locals=2, Args_size=2
    0: aload_0
    1: iload_1
    2: iconst_1
    3: iconst_0
    4: invokespecial #25; //Method aux$1:(III)I
    7: ireturn

    The tail recursion inside aux gets optimized away into a loop:

    private final int aux$1(int, int, int);
    Code:
    Stack=3, Locals=5, Args_size=4
    0: aload_0
    1: astore 4
    3: iload_1
    4: iconst_0
    5: if_icmpne 10
    8: iload_3
    9: ireturn
    10: iload_1
    11: iconst_1
    12: isub
    13: iload_2
    14: iload_3
    15: iadd
    16: iload_2
    17: istore_3
    18: istore_2
    19: istore_1
    20: goto 3

    This tail recursive one seems to give the same answers as the non-tail recursive one (for small numbers):

    scala> :load dubious.scala
    Loading dubious.scala...
    defined class Fibo
    defined class FiboTail

    scala> val fibo = new Fibo
    fibo: Fibo = Fibo@ee1c42

    scala> val fiboTail = new FiboTail
    fiboTail: FiboTail = FiboTail@616fde

    scala> for (i <- 1 to 10)
         |   println(fibo.fib(i) + " " + fiboTail.fib(i))
    1 1
    1 1
    2 2
    3 3
    5 5
    8 8
    13 13
    21 21
    34 34
    55 55

    Sorry to crash your party with Scala code. I'm sure you're looking for a more Ruby-like syntax, but when you started talking about wanting a language with concise expression, type inference, and optimized bytecodes for the JVM, it rang a bell for me.

    ReplyDelete
  14. Someone knows of any "backend" of Ruby or subset of ruby (a general computing library) that uses GPU?

    GPUs dont have the control unit needed for general Ruby usage but they have a whole bunch of useful instructions and of course a huge amount or ALU to become a very good backend for some Ruby operations.

    If I am interested in developing something like that, the only option would be write a C library and make a ruby wrap to it?

    ReplyDelete
  15. I second Tom's suggestion of pulling the signature out of the method body.

    ReplyDelete
  16. Tom, Mark,

    Putting it outside the method definition will be problematic for metaprogramming, e.g. Module#define_method. It'll probably be more difficult to parse, too.

    Also, I don't see the point of separating it. Python doesn't, and it seems to be working for them. Inlining the type looks much nicer.

    ReplyDelete
  17. @murphee Duby doesn't (currently) support arithmetic overflow into arbitrary-precision because the JVM doesn't support it. Duby is being designed to put a Ruby face on what works well on the JVM. The primary motivator is to give a static-typed lookalike for Ruby we can use to implement static signatures on compiled Ruby classes and to implement JRuby internals without all the Java fuss. Anything outside that...I'm open to contributions.

    ReplyDelete
  18. @tiago I assume you mean in Ruby, yes? We're considering it.

    ReplyDelete
  19. please do not involve rubyists with the java not-convention between data-objects and privitives ( Integer not egal int) etc.

    so its the best to use only the ruby syntax - so we can use the type hints for other ruby stuff and not only for the JVM

    so int should be a :integer etc.



    an other suggestion for syntax is:


    class Foo
    __def mult(x,y)
    ____params x => :integer, x > :integer
    ____returns :integer
    ____x*y
    __end
    end

    ReplyDelete
  20. Just another thought after reading everyone's comments regarding syntax. I'd love to see something like:

    def foo(a)
    types :a => Fixnum, :return => String
    ...
    end

    ReplyDelete
  21. singpolyma

    Something like that could be very easily implemented directly in ruby as a simple gem.

    And IDE's could use it for their type inference.

    ReplyDelete
  22. I like duby as an option for "strongly typed, more easily compilable" codes

    I assume this is like pyrex/cython?

    -=R

    ReplyDelete
  23. It would be pretty funny if you did it as comments, and then rdoc went "oh look, some people are putting type information in the comments, let's generate docs from it", and then IDE developers went "oh look, some people are putting type information in the comments, let's make autocomplete work much better".

    ReplyDelete
  24. Trejkaz: Actually I believe NetBeans already does that!

    ReplyDelete
  25. What is the syntax to put in the comment to make it work? Maybe IDEA supports it too and I just don't know because I'm only using call-seq and other "normal" Ruby ways of documenting methods.

    ReplyDelete
  26. You should start a mailing list or something so that users can contribute.
    Cheers!
    -=r

    ReplyDelete