From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA00286; Thu, 5 Feb 2004 22:12:38 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA01965 for ; Thu, 5 Feb 2004 22:12:37 +0100 (MET) Received: from cs.rice.edu (cs.rice.edu [128.42.1.30]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id i15LCav21631 for ; Thu, 5 Feb 2004 22:12:36 +0100 (MET) Received: from localhost (localhost [127.0.0.1]) by cs.rice.edu (Postfix) with ESMTP id 5E5004ABDD; Thu, 5 Feb 2004 15:12:34 -0600 (CST) Received: from cs.rice.edu ([127.0.0.1]) by localhost (cs.rice.edu [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 16683-01-42; Thu, 5 Feb 2004 15:12:21 -0600 (CST) Received: from boromir.cs.rice.edu (boromir.cs.rice.edu [128.42.129.71]) (using TLSv1 with cipher EDH-RSA-DES-CBC3-SHA (168/168 bits)) (No client certificate requested) by cs.rice.edu (Postfix) with ESMTP id 8B1524ABF9; Thu, 5 Feb 2004 15:11:46 -0600 (CST) Date: Thu, 5 Feb 2004 15:11:45 -0600 (CST) From: Walid Taha To: Ben Kavanagh Cc: caml-list@inria.fr Subject: RE: [Caml-list] partial eval question In-Reply-To: <000b01c3eb0a$356074e0$b1c92952@Archimedes> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: by amavis-20030616-p5 at rice.edu X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 metaocaml:01 metaocaml:01 ml's:01 leone:99 cfm:99 cfm:99 unrolling:01 leone:99 inspector:01 anti-spam:99 2004:99 caml-list:01 staged:01 timings:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hi Ben, It would certainly be useful to extend MetaOCaml with a partial evaluation construct. The key component that is needed is a nice implementation of a binding-time analysis (BTA). If someone (maybe you? :) is willing to implement such an analysis, it can be added into MetaOCaml as a library function: BTA : b -> c> -> a -> c> Best regards, Walid. On Wed, 4 Feb 2004, Ben Kavanagh wrote: |Walid, | |Thanks much for your response. I was aware of MetaOCaml's ability to |stage this computation and I have downloaded/run many of your |benchmarks. My question was more if anyone had an implementation where |normal partial application (normal in ML's syntax) led to partial |evaluation. It turns out that there was an implementation of this, |namely Mark Leone/Peter Lee's Fabius compiler, which, unfortunately, has |never been made available publicly. | |http://portal.acm.org/citation.cfm?id=231407&dl=ACM&coll=portal&CFID=111 |11111&CFTOKEN=2222222 |http://portal.acm.org/citation.cfm?id=289144&dl=ACM&coll=portal | |Such a coarse grained approach to code generation in a program is not |necessarily ideal for all purposes, a point you touch on in a later mail |to the Caml list in your statement about loop unrolling. It does seem, |though, that a useful syntax shortcut that made this direct |partial-application -> partial-evaluation mapping available in the |manner of Lee/Leone could be useful in Caml, and maybe even more |appropriately, MetaOCaml. | |Does this make sense? | |Ben | | | | |------------------------------------------------------------------------ |-------------- |FIGHT BACK AGAINST SPAM! |Download Spam Inspector, the Award Winning Anti-Spam Filter |http://mail.giantcompany.com | | |-----Original Message----- |From: Walid Taha [mailto:taha@cs.rice.edu] |Sent: Wednesday, February 04, 2004 2:51 AM |To: Ben Kavanagh |Cc: caml-list@inria.fr |Subject: Re: [Caml-list] partial eval question | | |Hi Ben, | |Below is a MetaOCaml (www.metaocaml.org) program that does what you were |asking for. | |----- begin ben.ml | |Trx.init_times (* Initialize MetaOCaml timer library *) | |(* Here's Ben's original code *) | |let pow n x = | | let rec pow_iter (n1, x1, p1) = | | if (n1 = 0) then | p1 | else if (n1 mod 2 = 0) then | pow_iter(n1/2, x1*x1, p1) | else pow_iter(n1-1, x1, p1*x1) | | in pow_iter(n, x, 1);; | | | |let pow2 = pow 2 | |(* Here's a staged version of Ben's code *) | |let pow' n x = | | let rec pow_iter (n1, x1, p1) = | | if (n1 = 0) then | p1 | else if (n1 mod 2 = 0) then | pow_iter(n1/2, .<.~x1 * .~x1>., p1) | | else pow_iter(n1-1, x1, .<.~p1 * .~x1>.) | | in pow_iter(n, x, .<1>.);; | |let pow2 = pow' 2 | |(* Here's some code to get some timings *) | | |let unstagedRunning = | Trx.timenew "unstaged running"(fun () -> pow 5 3) | |let stage1Running = | Trx.timenew "stage 1 running" (fun () -> . .~(pow' 5 ..)>.) | |let compiling = Trx.timenew "compiling" (fun () -> .! stage1Running) | |let stage2Running = Trx.timenew "stage 2 running" (fun () -> (compiling |3)) | |let baseline = Trx.timenew "baseline" (fun () -> ()) | |(* Print all the timings *) | |let _ = Trx.print_times () | |(* Outpout of timer: |__ unstaged running ______ 2097152x avg= 7.929525E-04 msec |__ stage 1 running ________ 262144x avg= 7.248323E-03 msec |__ compiling ________________ 8192x avg= 2.320860E-01 msec |__ stage 2 running ______ 16777216x avg= 1.123075E-04 msec |__ baseline _____________ 33554432x avg= 3.921819E-05 msec |*) | |--- end ben.ml | |Walid. | |On Mon, 27 Oct 2003, Ben Kavanagh wrote: | || ||Say I have a function such as pow defined as || ||let pow n x = || let rec pow_iter (n1, x1, p1) = || if (n1 = 0) then p1 || else if (n1 mod 2 = 0) || then pow_iter(n1/2, x1*x1, p1) || else pow_iter(n1-1, x1, p1*x1) || in pow_iter(n, x, 1);; || ||and I say || ||let pow2 = pow 2 || ||Are there any ML implementations that would automatically perform ||partial evaluation to create pow2 instead of using closures, possibly ||unfolding the pow_iter call? Would Caml ever have this capability? || ||Ben || || ||------------------- ||To unsubscribe, mail caml-list-request@inria.fr Archives: |http://caml.inria.fr ||Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: |http://caml.inria.fr/FAQ/ ||Beginner's list: http://groups.yahoo.com/group/ocaml_beginners || | | -- ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners