Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] partial eval question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Ben Kavanagh <kavabean@l...>
Subject: RE: [Caml-list] partial eval question
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