Re: [Caml-list] Odd performance result with HLVM

[Jon Harrop <jon@ffconsultancy.com>]

On Saturday 28 February 2009 21:59:29 Jon Harrop wrote:
> On Saturday 28 February 2009 21:21:18 Richard Jones wrote:
> > On Sat, Feb 28, 2009 at 03:18:40PM -0500, Kuba Ober wrote:
> > > You didn't let us in on how it really works. You said "high-level
> > > virtual machine
> > > built upon LLVM and written in OCaml". LLVM means too many things to be
> > > able to decipher what you mean, and your statement is too general.
> >
> > I'm still waiting for the open source project ...
>
> I'm working on it. I now have:
>
> . unit, bool, int, float.
> . tuples.
> . arrays.
> . algebraic datatypes.
> . function pointers.
> . tail calls.
> . generic printing.
> . catching stack overflows.
> . C FFI.
> . JIT compilation to high performance native code.
>
> I need to implement closures...

Now that I come to try it, I don't think I do need to implement closures. 
Check out the following sample:

let curry : t list =
  let ty_closure(ty1, ty2) =
    `Struct[`Function([`Reference; ty1], ty2); `Reference] in
  let apply(f, x) =
    Apply(GetValue(f, 0), [GetValue(f, 1); x]) in
  let ty_ret = `Struct[`Int; `Float] in
  [`Function("f_uncurried", ["x", `Int; "y", `Float], ty_ret,
	     Struct[Var "x"; Var "y"]);

   `Type("env_int", ["Int", `Int]);

   `Function("f_apply_2", ["env", `Reference; "y", `Float], ty_ret,
	     Apply(Var "f_uncurried", [Cast(Var "env", "Int"); Var "y"]));

   `Function("f_apply_1", ["x", `Int], ty_closure(`Float, ty_ret),
	     Struct[Var "f_apply_2"; Construct("Int", Var "x")]);

   `Expr(Let("g", Apply(Var "f_apply_1", [Int 3]),
	     Struct[apply(Var "g", Float 2.3);
		    apply(Var "g", Float 3.4)]), `Struct[ty_ret; ty_ret])]

Unions are represented by the type "`Reference" and constructed 
with "Construct". Their type can be tested with "IsType" and their argument 
can be extracted with "Cast".

The above code is an intermediate representation of the curried OCaml 
function:

  let f (x: int) (y: float) = (x, y)

and the example application of a closure created by partially applying the 
first argument "x":

  let g = f 3 in (g 2.3, g 3.4)

The raw representation is an uncurried function "f_uncurried". That should 
make recursive closures a lot faster than they are in OCaml.

The type constructor "Int" is used to represent a closure environment that 
conveys an int. Such types can be generated on-the-fly whenever the compiler 
sees code that would generate a closure that required an environment of this 
type.

The "f_apply_2" function extracts "x" from the environment and applies "x" 
and "y" to "f".

The "f_apply_1" function partially applies "x" to "f", creating a closure 
represented by a struct containing a pointer to "f_apply_2" and the boxed 
environment containing "x".

The final expression partially applies "f" to "x=3" and then applies the 
resulting closure twice.

Running this program in HLVM produces:

Writing bitcode
Evaluating
- : <type> = ((3, 2.3), (3, 3.4))
Took 0.027330s

Note that the structs are pretty printed as tuples using generic printers. You 
can call the internal Print function on any value of any type and it will be 
pretty printed.

A front-end for a functional language can, therefore, already handle 
first-class functions with the current HLVM by representing all functional 
values as a struct containing a function pointer and a boxed environment. 
Moreover, HLVM could include an optimization pass to remove redundant closure 
constructions and deconstructions. The nice aspect of this is that it reduces 
complexity and makes it much easier to write a GC: only algebraic datatypes 
are non-trivial.

So I'll probably just reimplement my GC and then publish HLVM as open source 
software on the OCaml Forge.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e