From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 73CA1BBC4 for ; Mon, 2 Mar 2009 01:33:30 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhkCAJO3qknUnwcjjmdsb2JhbACCJ5IxAQEBAQkLCAkPBr5ehBoG X-IronPort-AV: E=Sophos;i="4.38,286,1233529200"; d="scan'208";a="35941414" Received: from relay.ptn-ipout01.plus.net ([212.159.7.35]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Mar 2009 01:33:30 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: As0FAEe4qknUnw4S/2dsb2JhbACCJ9FChBoG Received: from pih-relay05.plus.net ([212.159.14.18]) by relay.ptn-ipout01.plus.net with ESMTP; 02 Mar 2009 00:33:29 +0000 Received: from [87.112.14.152] (helo=leper.local) by pih-relay05.plus.net with esmtp (Exim) id 1Ldw64-000219-Rd for caml-list@yquem.inria.fr; Mon, 02 Mar 2009 00:33:29 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Odd performance result with HLVM Date: Mon, 2 Mar 2009 00:38:46 +0000 User-Agent: KMail/1.9.9 References: <200902280112.24115.jon@ffconsultancy.com> <20090228212117.GA21715@annexia.org> <200902282159.29086.jon@ffconsultancy.com> In-Reply-To: <200902282159.29086.jon@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200903020038.46904.jon@ffconsultancy.com> X-Plusnet-Relay: d00245d8f3b1978fbb7ae344a371792d X-Spam: no; 0.00; high-level:01 ocaml:01 bool:01 arrays:01 datatypes:01 pointers:01 ffi:01 compilation:01 struct:01 struct:01 expr:01 unions:01 curried:01 ocaml:01 recursive:01 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 - : = ((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