[Camllist] partial eval question
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20040205 (21:12) 
From:  Walid Taha <taha@c...> 
Subject:  RE: [Camllist] partial eval question 
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 bindingtime analysis (BTA). If someone (maybe you? :) is willing to implement such an analysis, it can be added into MetaOCaml as a library function: BTA : <a > b > c> > a > <b > 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 partialapplication > partialevaluation 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 AntiSpam 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: camllist@inria.fr Subject: Re: [Camllist] 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(n11, 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(n11, 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 () > .<fun x> .~(pow' 5 .<x>.)>.)  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.929525E04 msec __ stage 1 running ________ 262144x avg= 7.248323E03 msec __ compiling ________________ 8192x avg= 2.320860E01 msec __ stage 2 running ______ 16777216x avg= 1.123075E04 msec __ baseline _____________ 33554432x avg= 3.921819E05 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(n11, 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners      To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners