Authors : erickt : September 2009
Why I find felix interesting
posted on September 28, 2009 - 12:53 PM PDT by Erick Tryzelaar
This is a repost from a reddit that's about why I find neat about felix. Maybe this will inspire someone to try it out some time :)
So felix has a couple nice things going for it. The main things I find interesting is the concurrency model, the dynamic syntax, the type system, c++ integration. That space is getting a bit busy, with Scala probably being the closest relative, but I think there's still plenty of room for exploration.
My personal favorite thing is our concurrency model. Similar to Erlang and Scala, we've got an actor-ish concurrency model with user space fibers that communicate through messages. We call them fthreads. It's a little lower level than those languages though, we only provide synchronous no-copy message passing. I'm planning on layering a mailbox layer on top of that to add asynchronous messaging though.
We've also got an async io library that's intended to work seamlessly with fthreads. The intention is that you should be able to write standard blocking batch-style code and let the compiler/runtime convert your code into event driven code. We've got a prototype web server that's built on top of this, but haven't gotten too far with it yet though.
Next up our dynamic syntax. Felix's grammar is essentially defined at runtime. We have a basic shim grammar that lets us load up a grammar specification at runtime to parse the rest of the language. This then gets compiled in memory to scheme, which then gets compiled to the ast for code generation. The neat thing with this is that it allows you to have scoped syntax extensions. This could allow for a lot of neat lisp-style macro metaprogramming, or even theoretically allow you to write, say, a python-compatible grammar and let felix handle the rest of the language.
We've got a pretty advanced type system. It's a static language with support for both ad-hoc polymorphism and haskell-style typeclasses. Since the grammar's dynamic, we don't really have hardcoded concepts of types like ints. They're specified in the standard library. So that means we can't really have the compiler know that 1+0 can be optimized down to 1. So we've got hooks in order to specify the reductions like this. Similarly, we tell the compiler axioms about types, like this type is symmetric, and that one is associative. This then can be outputted to the proof assistant generator Why in order to help prove things about your program, though I don't know too much about how that works.
Finally, the c++ integration. Our main backend is c++ source. This lets us directly support binding to c++ libraries without needing to write external shim bindings. For instance, we use this and typeclasses to directly expose a good portion of STL to felix. We'll see if I can figure out how to integrate this with my LLVM backend though. Maybe once Clang gets c++ working we could somehow use that to generate the right code for us.
Hello Felix!
posted on September 28, 2009 - 02:10 AM PDT
by Erick Tryzelaar
filed under:
Felix,
LLVM
Basic pointer types and c strings are now working!
type char = "%i8";
typedef charp = &char;
proc puts : charp = "puts";
puts c"Hello world!";
Generates:
@0 = internal global [13 x i8] c"Hello world!\00" ; <[13 x i8]*> [#uses=1]
declare void @puts(i8*)
define void @1() {
entry:
call void @puts(i8* getelementptr inbounds ([13 x i8]* @0, i32 0, i32 0))
ret void
}
And prints out:
Hello World!
Closures!
posted on September 27, 2009 - 05:40 PM PDT by Erick Tryzelaar
flxc now has automatic stack closures! Take that, C99! Check this out!
type tiny = "%i8";
type int = "%i32";
typedef bool = 2;
fun add : int*int -> int = "%add";
fun sub : int*int -> int = "%sub";
fun eq : int*int -> bool = "%eq";
fun lnot : bool -> bool = "%lnot";
proc exit : int = "exit";
noinline fun foo (x:int) = {
val y = 6;
return x + y;
}
noinline proc fake_exit (x:int) {
exit x;
return;
}
noinline fun bar (x:int) = {
var y = 10;
noinline proc baz () {
y = 20;
return;
}
baz ();
return x + y;
}
noinline fun x (a:int, b:int, c:tiny) = {
val x1 = a;
val x2 = b;
val x3 = c;
noinline fun y (d:int, e:int, f:tiny) = {
val y1 = x1;
val y2 = x2;
val y3 = f;
noinline fun z (g:int, h:int, i:tiny) = {
val z1 = x1;
val z2 = x2;
val z3 = i;
return z1;
}
return z (y1,y2,y3);
}
return y (x1,x2,x3);
}
fake_exit $ (foo 2) + (bar 3) + (x (1,2,3t));
And the llvm source:
%0 = type { i32, i32 }
%1 = type { i32, i32, i32, i32, i8 }
%2 = type { i32, i32, i8 }
declare void @exit(i32)
define i32 @foo(i32 %x) {
entry:
%foo.x = alloca i32 ; <i32*> [#uses=2]
store i32 %x, i32* %foo.x
%0 = load i32* %foo.x ; <i32> [#uses=1]
%1 = add i32 %0, 6 ; <i32> [#uses=1]
ret i32 %1
}
define void @fake_exit(i32 %x) {
entry:
%fake_exit.x = alloca i32 ; <i32*> [#uses=2]
store i32 %x, i32* %fake_exit.x
%0 = load i32* %fake_exit.x ; <i32> [#uses=1]
call void @exit(i32 %0)
ret void
}
define i32 @bar(i32 %x) {
entry:
%bar-closure = alloca %0 ; <%0*> [#uses=3]
%bar.y = getelementptr %0* %bar-closure, i32 0, i32 0 ; <i32*> [#uses=2]
%bar.x = getelementptr %0* %bar-closure, i32 0, i32 1 ; <i32*> [#uses=2]
store i32 %x, i32* %bar.x
store i32 10, i32* %bar.y
call void @bar.baz(%0* %bar-closure)
%0 = load i32* %bar.x ; <i32> [#uses=1]
%1 = load i32* %bar.y ; <i32> [#uses=1]
%2 = add i32 %0, %1 ; <i32> [#uses=1]
ret i32 %2
}
define void @bar.baz(%0* %bar-closure) {
entry:
%bar.y = getelementptr %0* %bar-closure, i32 0, i32 0 ; <i32*> [#uses=1]
%bar.x = getelementptr %0* %bar-closure, i32 0, i32 1 ; <i32*> [#uses=0]
store i32 20, i32* %bar.y
ret void
}
define i32 @x(i32 %a, i32 %b, i8 %c) {
entry:
%x-closure = alloca %1 ; <%1*> [#uses=6]
%x.x1 = getelementptr %1* %x-closure, i32 0, i32 0 ; <i32*> [#uses=2]
%x.x2 = getelementptr %1* %x-closure, i32 0, i32 1 ; <i32*> [#uses=2]
%x.a = getelementptr %1* %x-closure, i32 0, i32 2 ; <i32*> [#uses=2]
%x.b = getelementptr %1* %x-closure, i32 0, i32 3 ; <i32*> [#uses=2]
%x.c = getelementptr %1* %x-closure, i32 0, i32 4 ; <i8*> [#uses=2]
store i32 %a, i32* %x.a
store i32 %b, i32* %x.b
store i8 %c, i8* %x.c
%0 = load i32* %x.a ; <i32> [#uses=1]
store i32 %0, i32* %x.x1
%1 = load i32* %x.b ; <i32> [#uses=1]
store i32 %1, i32* %x.x2
%2 = load i32* %x.x1 ; <i32> [#uses=1]
%3 = load i32* %x.x2 ; <i32> [#uses=1]
%4 = load i8* %x.c ; <i8> [#uses=1]
%5 = call i32 @x.y(%1* %x-closure, i32 %2, i32 %3, i8 %4) ; <i32> [#uses=1]
ret i32 %5
}
define i32 @x.y(%1* %x-closure, i32 %d, i32 %e, i8 %f) {
entry:
%x.x1 = getelementptr %1* %x-closure, i32 0, i32 0 ; <i32*> [#uses=1]
%x.x2 = getelementptr %1* %x-closure, i32 0, i32 1 ; <i32*> [#uses=1]
%x.a = getelementptr %1* %x-closure, i32 0, i32 2 ; <i32*> [#uses=0]
%x.b = getelementptr %1* %x-closure, i32 0, i32 3 ; <i32*> [#uses=0]
%x.c = getelementptr %1* %x-closure, i32 0, i32 4 ; <i8*> [#uses=0]
%x.y-closure = alloca %2 ; <%2*> [#uses=4]
%x.y.d = getelementptr %2* %x.y-closure, i32 0, i32 0 ; <i32*> [#uses=1]
%x.y.e = getelementptr %2* %x.y-closure, i32 0, i32 1 ; <i32*> [#uses=1]
%x.y.f = getelementptr %2* %x.y-closure, i32 0, i32 2 ; <i8*> [#uses=2]
store i32 %d, i32* %x.y.d
store i32 %e, i32* %x.y.e
store i8 %f, i8* %x.y.f
%0 = load i32* %x.x1 ; <i32> [#uses=1]
%1 = load i32* %x.x2 ; <i32> [#uses=1]
%2 = load i8* %x.y.f ; <i8> [#uses=1]
%3 = call i32 @x.y.z(%1* %x-closure, %2* %x.y-closure, i32 %0, i32 %1, i8 %2) ; <i32> [#uses=1]
ret i32 %3
}
define i32 @x.y.z(%1* %x-closure, %2* %x.y-closure, i32 %g, i32 %h, i8 %i) {
entry:
%x.x1 = getelementptr %1* %x-closure, i32 0, i32 0 ; <i32*> [#uses=1]
%x.x2 = getelementptr %1* %x-closure, i32 0, i32 1 ; <i32*> [#uses=0]
%x.a = getelementptr %1* %x-closure, i32 0, i32 2 ; <i32*> [#uses=0]
%x.b = getelementptr %1* %x-closure, i32 0, i32 3 ; <i32*> [#uses=0]
%x.c = getelementptr %1* %x-closure, i32 0, i32 4 ; <i8*> [#uses=0]
%x.y.d = getelementptr %2* %x.y-closure, i32 0, i32 0 ; <i32*> [#uses=0]
%x.y.e = getelementptr %2* %x.y-closure, i32 0, i32 1 ; <i32*> [#uses=0]
%x.y.f = getelementptr %2* %x.y-closure, i32 0, i32 2 ; <i8*> [#uses=0]
%x.y.z-closure = alloca %2 ; <%2*> [#uses=3]
%x.y.z.g = getelementptr %2* %x.y.z-closure, i32 0, i32 0 ; <i32*> [#uses=1]
%x.y.z.h = getelementptr %2* %x.y.z-closure, i32 0, i32 1 ; <i32*> [#uses=1]
%x.y.z.i = getelementptr %2* %x.y.z-closure, i32 0, i32 2 ; <i8*> [#uses=1]
store i32 %g, i32* %x.y.z.g
store i32 %h, i32* %x.y.z.h
store i8 %i, i8* %x.y.z.i
%0 = load i32* %x.x1 ; <i32> [#uses=1]
ret i32 %0
}
define void @0() {
entry:
%0 = call i32 @foo(i32 2) ; <i32> [#uses=1]
%1 = call i32 @bar(i32 3) ; <i32> [#uses=1]
%2 = add i32 %0, %1 ; <i32> [#uses=1]
%3 = call i32 @x(i32 1, i32 2, i8 3) ; <i32> [#uses=1]
%4 = add i32 %2, %3 ; <i32> [#uses=1]
call void @fake_exit(i32 %4)
ret void
}
What to work on next? Polymorphism, or strings? I am a bit tired relying on exit to tell me if the code's working or not. What to do, what to do...
tail calls, baby!
posted on September 26, 2009 - 05:51 PM PDT by Erick Tryzelaar
Check this out! I just got the standard felix optimizations working.
type int = "%i32";
typedef bool = 2;
fun add : int*int -> int = "%add";
fun sub : int*int -> int = "%sub";
fun eq : int*int -> bool = "%eq";
fun lnot : bool -> bool = "%lnot";
proc exit : int = "exit";
fun foo (x:int) = {
if x == 0 do
return 10;
done;
return foo (x - 1);
}
exit $ foo 2;
Which compiles down to this code:
declare void @exit(i32)
define i32 @foo(i32 %x) {
entry:
%foo.x = alloca i32 ; <i32*> [#uses=4]
store i32 %x, i32* %foo.x
br label %start_21
start_21: ; preds = %_ifdoend_1, %entry
%0 = load i32* %foo.x ; <i32> [#uses=1]
%1 = icmp eq i32 %0, 0 ; <i1> [#uses=1]
%2 = icmp eq i1 %1, false ; <i1> [#uses=1]
br i1 %2, label %_ifdoend_1, label %else
_ifdoend_1: ; preds = %start_21
%3 = load i32* %foo.x ; <i32> [#uses=1]
%4 = sub i32 %3, 1 ; <i32> [#uses=1]
store i32 %4, i32* %foo.x
br label %start_21
else: ; preds = %start_21
ret i32 10
}
define void @0() {
entry:
%0 = call i32 @foo(i32 2) ; <i32> [#uses=1]
call void @exit(i32 %0)
ret void
}
flx now with stupid inner functions!
posted on September 25, 2009 - 11:20 PM PDT by Erick Tryzelaar
It's been quite some time since I last posted, but I've been pretty busy. I only wasted 2 days this time wandering down the depths of the felix type system and name binding... shudder. A couple nice things this time around. flxc now partially uses the language independent frontend for symbol lowering. None of the optimizations yet though. Also managed to get trivial non-closured inner functions working, as demonstrated here:
type int = "%i32";
typedef bool = 2;
fun add : int*int -> int = "%add";
fun eq : int*int -> bool = "%eq";
fun lnot : bool -> bool = "%lnot";
proc exit : int = "exit";
fun foo (x:int) = {
val y = x + 1;
fun bar (x:int) = {
if x == 1 do
return y;
else
return 3;
done;
}
return bar y;
}
exit $ foo 2;
This now generates this code:
declare void @exit(i32)
define i32 @foo(i32 %x) {
entry:
%foo.y = alloca i32 ; <i32*> [#uses=2]
%foo.x = alloca i32 ; <i32*> [#uses=2]
store i32 %x, i32* %foo.x
%0 = load i32* %foo.x ; <i32> [#uses=1]
%1 = add i32 %0, 1 ; <i32> [#uses=1]
store i32 %1, i32* %foo.y
%2 = load i32* %foo.y ; <i32> [#uses=1]
%3 = call i32 @foo.bar(i32 %2) ; <i32> [#uses=1]
ret i32 %3
}
define i32 @foo.bar(i32 %x) {
entry:
%foo.bar.x = alloca i32 ; <i32*> [#uses=2]
store i32 %x, i32* %foo.bar.x
%0 = load i32* %foo.bar.x ; <i32> [#uses=1]
%1 = icmp eq i32 %0, 1 ; <i1> [#uses=1]
%2 = icmp eq i1 %1, false ; <i1> [#uses=1]
br i1 %2, label %_ifdoend_1, label %else
_ifdoend_1: ; preds = %entry
ret i32 3
else: ; preds = %entry
ret i32 2
}
define void @0() {
entry:
%0 = call i32 @foo(i32 2) ; <i32> [#uses=1]
call void @exit(i32 %0)
ret void
}
And if you optimize it with flxc -O 1 ..., then you'll get:
declare void @exit(i32)
define i32 @foo(i32 %x) {
entry:
%0 = add i32 %x, 1 ; <i32> [#uses=1]
%1 = call i32 @foo.bar(i32 %0) ; <i32> [#uses=1]
ret i32 %1
}
define i32 @foo.bar(i32 %x) {
entry:
%0 = icmp eq i32 %x, 1 ; <i1> [#uses=1]
%retval = select i1 %0, i32 2, i32 3 ; <i32> [#uses=1]
ret i32 %retval
}
define void @0() {
entry:
%0 = call i32 @foo(i32 2) ; <i32> [#uses=1]
call void @exit(i32 %0)
ret void
}
Which looks surprisingly readable. You'll also notice that we're prepending the parent's name in the llvm symbol name, so it should hopefully help with debugging.
flxc is slightly more than useless with conditional branching
posted on September 16, 2009 - 12:33 AM PDT by Erick Tryzelaar
Just got basic conditional branching working. With this code:
>>> type int = "%i32";
>>> typedef bool = 2;
>>> fun add : int*int -> int = "%add";
>>> fun eq : int*int -> bool = "%eq";
>>> fun lnot : bool -> bool = "%lnot";
>>> proc exit : int = "exit";
>>> fun foo (x:int) = {
... if x == 1 do
... return 2;
... else
... return 3;
... done;
... }
>>> exit $ foo 1;
flxc will generate and execute this code:
declare void @exit(i32)
define i32 @foo(i32 %x) {
entry:
%x1 = alloca i32 ; <i32*> [#uses=2]
store i32 %x, i32* %x1
%0 = load i32* %x1 ; <i32> [#uses=1]
%1 = icmp eq i32 %0, 1 ; <i1> [#uses=1]
%2 = icmp eq i1 %1, false ; <i1> [#uses=1]
br i1 %2, label %_ifdoend_1, label %else
_ifdoend_1: ; preds = %entry
ret i32 3
else: ; preds = %entry
ret i32 2
}
define void @0() {
entry:
%0 = call i32 @foo(i32 1) ; <i32> [#uses=1]
call void @exit(i32 %0)
ret void
}
The program will exit with 2. It'll even return 3 if you call foo with 2. Unfortunately, branching only works inside functions.
flxc can now JIT the most useless program ever!
posted on September 15, 2009 - 02:27 AM PDT by Erick Tryzelaar
I finally got the llvm jit working with felix. Here's the proof. With this input:
type int = "%i32";
typedef array[t,n] = t ^ n;
fun add : int*int -> int = "%add";
fun subscript[t,n] : array[t,n] * int -> t = "%subscript";
proc exit : int = "exit";
var x = 5, 6;
var y = x.[1] + 1;
y = y + 3;
val z = x.[0], y;
exit (z.[0] + z.[1]);
Generates this llvm module and executes each numbered function at a time:
@x = weak_odr global [2 x i32] undef ; <[2 x i32]*> [#uses=2]
@y = weak_odr global i32 undef ; <i32*> [#uses=4]
@z = weak_odr global [2 x i32] undef ; <[2 x i32]*> [#uses=2]
declare void @exit(i32)
define void @0() {
entry:
store i32 5, i32* getelementptr inbounds ([2 x i32]* @x, i32 0, i32 0)
store i32 6, i32* getelementptr inbounds ([2 x i32]* @x, i32 0, i32 1)
ret void
}
define void @1() {
entry:
%0 = load i32* getelementptr inbounds ([2 x i32]* @x, i32 0, i32 1) ; <i32> [#uses=1]
%1 = add i32 %0, 1 ; <i32> [#uses=1]
store i32 %1, i32* @y
ret void
}
define void @2() {
entry:
%y = load i32* @y ; <i32> [#uses=1]
%0 = add i32 %y, 3 ; <i32> [#uses=1]
store i32 %0, i32* @y
ret void
}
define void @3() {
entry:
%0 = load i32* getelementptr inbounds ([2 x i32]* @x, i32 0, i32 0) ; <i32> [#uses=1]
store i32 %0, i32* getelementptr inbounds ([2 x i32]* @z, i32 0, i32 0)
%y = load i32* @y ; <i32> [#uses=1]
store i32 %y, i32* getelementptr inbounds ([2 x i32]* @z, i32 0, i32 1)
ret void
}
define void @4() {
entry:
%0 = load i32* getelementptr inbounds ([2 x i32]* @z, i32 0, i32 0) ; <i32> [#uses=1]
%1 = load i32* getelementptr inbounds ([2 x i32]* @z, i32 0, i32 1) ; <i32> [#uses=1]
%2 = add i32 %1, %0 ; <i32> [#uses=1]
call void @exit(i32 %2)
ret void
}
If everything works out, the program should exit with the returncode 15. You'll need a properly configured and built llvm from svn to get this to work though.