RE: [Caml-list] partial eval question

[Walid Taha <taha@cs.rice.edu>]

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 : <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
|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 () -> .<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.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