Sunday, March 30, 2008

Duby's C Backend POC

Late last week I wired up a quick proof-of-concept C back-end for Duby, to show that it is possible. Duby's design represents all types as symbols, which allows the type representation to vary across platforms. So in fib(), the fixnum type is represented as ":fixnum" throughout, and it can be mapped to whatever the backend decides fixnums should be. This means that, in general, code you write in Duby will type infer (for some definition of infer) and produce an AST suitable for compilation to any backend or type system. And with the appropriate plugins, like the "math" typer from my previous Duby post, you can do cool things like represent integer math as either primitive math operations or method calls against object types. But the source code remains the same.

I also wanted to blunt some criticism I received during the first Duby prototype. It represented types as symbols, but symbols nearly identical to their eventual Java types. In order for Duby to be generally useful (in, for example, Rubinius) platform-agnostic symbolic typing is a must.

So here's the code for my little C backend in its current state. It's pretty crude at the moment, but you can get the general idea. There's obviously work to do: it doesn't correctly insert "return" keywords, doesn't insert end-of-line semicolons everywhere appropriate (and often inserts them in totally inappropriate place), and in general doesn't produce entirely valid C code, but those are mostly minor details; the important takeaway here is that the typing and general Duby AST representation can easily be compiled this way.

Ok then! Given a simple script:

def fib(n)
{n => :fixnum}
if n < 2
n
else
fib(n - 1) + fib(n - 2)
end
end

def go
fib(35)
end
We can run the C "compiler" thus:
jruby -rduby/plugin/math lib/ruby/site_ruby/1.8/duby/c_compiler.rb fib.rb
And we get a fib.rb.c file as a result:
int fib(int n) {;
if (n < 2) {n} else {fib(n - 1) + fib(n - 2)};
}

;
int go() {fib(35)}

;
As I said, it's not the prettiest thing in the world, but I think it demonstrates that Duby should easily be able to target pretty much any backend platform you like. Fun stuff!

3 comments:

JoshG said...

G'day mate,

Just breezing through your Duby writings while waiting at the airport.

Feels like some of your type inference / hinting is very Haskell-like.

Any thoughts about tail recursion and lazy eval while you're at it? :-D

Charles Oliver Nutter said...

@joshg It seems to me such things are in the domain of the compiler and its plugins; whether a given piece of code is evaluated lazily or tail optimized should usually have no bearing on the syntax or the type inference logic. So if you want to write a compiler backend for Duby that lazily evaluates or optimizes tail calls, it ought to be possible without modifying the rest of the pipeline.

john said...

I expected the link you gave was C code. What do you mean by C backend then?