[Caml-list] partial eval question

[Caml-list] partial eval question

[Ben Kavanagh]

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

Re: [Caml-list] partial eval question

[Damien]

On Mon, 27 Oct 2003 01:41:49 -0000 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?

Multi-Stage Programming is your friend...
<http://www.cs.rice.edu/~taha/MSP/>

There are two ML implementations :
Ocaml : MetaOCaml <http://www.cs.rice.edu/~taha/MetaOCaml/>
SML : MetaML <http://www.cse.ogi.edu/PacSoft/projects/metaml/>


let rec pow n = .< 
	.~(match n with
		| 1 -> .< fun x -> x >.
		| n -> .< fun x -> x * .~(pow (n-1)) x>.
	)
>.

(pow 3) get reduced into .<fun x -> x*x*x>.


Damien

-------------------
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

Re: [Caml-list] partial eval question

[William Chesters]

Damien writes:
 > Multi-Stage Programming is your friend...
 > <http://www.cs.rice.edu/~taha/MSP/>
 > 
 > There are two ML implementations :
 > Ocaml : MetaOCaml <http://www.cs.rice.edu/~taha/MetaOCaml/>
 > SML : MetaML <http://www.cse.ogi.edu/PacSoft/projects/metaml/>
 > 
 > 
 > let rec pow n = .< 
 > 	.~(match n with
 > 		| 1 -> .< fun x -> x >.
 > 		| n -> .< fun x -> x * .~(pow (n-1)) x>.
 > 	)
 > >.
 > 
 > (pow 3) get reduced into .<fun x -> x*x*x>.

And that's an improvement over

    double pow(double x, int n) {
      double it = 1;
      while (--n >= 0) it *= x;
      return it;
    }

    double pow3(double x, int n) {
      return pow(x, 3);
    }

in what way exactly?  (If it doesn't work for you, try
-funroll-all-loops.)

For these kinds of purposes, Multi-Stage Programming is a very
labour-intensive and error-prone way of doing what mainstream
compilers will do for you already.  Maybe it has useful applications
in e.g. generation of numerical codes, where inlining, unrolling,
"templatization" and partial evaluation are not enough because major
structural transformations are required.  But then, maybe
sophisticated jobs like that are always going to be easiest done with
special-purpose code generators?

-------------------
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

Re: [Caml-list] partial eval question

[Andrew Lenharth]

On Mon, Oct 27, 2003 at 03:39:21PM +0000, William Chesters wrote:
> And that's an improvement over
> 
>     double pow(double x, int n) {
>       double it = 1;
>       while (--n >= 0) it *= x;
>       return it;
>     }
> 
>     double pow3(double x, int n) {
>       return pow(x, 3);
>     }
> 
> in what way exactly?  (If it doesn't work for you, try
> -funroll-all-loops.)

And that's an improvement over

template <int N>
inline double pow (double x) {
  return x * pow<N-1>(x);
}
template<>
inline double pow<0> (double x) {
  return 1.0;
}

in what way exactly?  (If it doesn't work for you, try 
-O2) :)

The C example relies on a fairly smart compiler to 
do interprocedual analysis.  The C++ example 
only requires the inline keywork be honored, and you 
don't need explicit pow3 pow2, you have pow<3> pow<2> 
pow<any constant>.

Gives a bit more control over code generation.

Andrew

-------------------
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

Re: [Caml-list] partial eval question

[William Chesters]

Andrew Lenharth writes:
 > And that's an improvement over
 > 
 > template <int N>
 > inline double pow (double x) {
 >   return x * pow<N-1>(x);
 > }
 > template<>
 > inline double pow<0> (double x) {
 >   return 1.0;
 > }
 > 
 > in what way exactly?

What I wrote, the "obvious thing", is

   -- easy to write, and hard to get wrong

   -- gives much less confusing error messages if you get it slightly
wrong

   -- easy to read

   -- uses a smaller subset of the language, so is especially easier
for non-C++ experts

   -- more general, in that it doesn't blow up and use silly amounts
of space (and probably more time too, given cache churn) if N is not
tiny

   -- more general also in that the same code does both the
general-purpose (n known only at runtime) and the special-purpose
job

 > The C example relies on a fairly smart compiler to 
 > do interprocedual analysis.

Depends what you mean by fairly smart.  This is standard stuff: gcc is
really not the best optimising compiler around.

 > The C++ example only requires the inline keywork be honored, and
 > you don't need explicit pow3 pow2, you have pow<3> pow<2> pow<any
 > constant>.
 > 
 > Gives a bit more control over code generation.

It does.  I personally feel (actually have learned the hard way) that
using C++ templates for multi-stage programming is mostly much more
trouble than it is worth---especially when you realise what careful
exploitation of C-level specalisation by inlining can do.

If you really want more control over code generation (not forgetting
that just writing out what you want by hand is often the simplest
option in practice!) then I think C++ templates are a dead end---far
better to make the object language the same as the target language,
as in MetaOcaml and similar.

-------------------
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

RE: [Caml-list] partial eval question

[Jacques Carette]

> If you really want more control over code generation (not forgetting
> that just writing out what you want by hand is often the simplest
> option in practice!) then I think C++ templates are a dead end---far
> better to make the object language the same as the target language,
> as in MetaOcaml and similar.

If you know what you want, MetaOcaml is great.  If you are
prototyping/experimenting, then a typeless symbolic language (like Scheme or
Maple) give you much greater flexibility.  MetaOcaml's contortions to get
something like:

> pow := proc(x,n::nonnegint) if n=0 then 1 else times(x,pow(x,n-1)) end if
end proc;
pow := proc(x, n::nonnegint)
    if n = 0 then 1 else times(x, pow(x, n - 1)) end if
end proc

> unapply(pow(x,5), x);
       x -> times(x, times(x, times(x, times(x, times(x, 1)))))

is really quite burdensome.  Having the freedom of dealing with 'open' terms
as first-class citizens is really very powerful, if somewhat dangerous.

I have found Thiemann's PGG as the 'front end', coupled with
Scheme-to-YourFavoriteLanguage translation to be quite effective PE
strategy, at least when more basic 'symbolic computation' is not enough.

Jacques

-------------------
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

RE: [Caml-list] partial eval question

[Walid Taha]

Hi Jacques,

Please see my last email in responce to Ben's original email.  MSP in 
MetaOCaml doesn't require any "contortions".

Walid.

On Mon, 27 Oct 2003, Jacques Carette wrote:

|> If you really want more control over code generation (not forgetting
|> that just writing out what you want by hand is often the simplest
|> option in practice!) then I think C++ templates are a dead end---far
|> better to make the object language the same as the target language,
|> as in MetaOcaml and similar.
|
|If you know what you want, MetaOcaml is great.  If you are
|prototyping/experimenting, then a typeless symbolic language (like Scheme or
|Maple) give you much greater flexibility.  MetaOcaml's contortions to get
|something like:
|
|> pow := proc(x,n::nonnegint) if n=0 then 1 else times(x,pow(x,n-1)) end if
|end proc;
|pow := proc(x, n::nonnegint)
|    if n = 0 then 1 else times(x, pow(x, n - 1)) end if
|end proc
|
|> unapply(pow(x,5), x);
|       x -> times(x, times(x, times(x, times(x, times(x, 1)))))
|
|is really quite burdensome.  Having the freedom of dealing with 'open' terms
|as first-class citizens is really very powerful, if somewhat dangerous.
|
|I have found Thiemann's PGG as the 'front end', coupled with
|Scheme-to-YourFavoriteLanguage translation to be quite effective PE
|strategy, at least when more basic 'symbolic computation' is not enough.
|
|Jacques
|
|-------------------
|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

Re: [Caml-list] partial eval question

[Andrew Lenharth]

On Mon, Oct 27, 2003 at 07:12:59PM +0000, William Chesters wrote:
> What I wrote, the "obvious thing", is
>    -- easy to write, and hard to get wrong

Easy to write, maybe, if recursion is hard.  Harder for compilers to
 optimize.  Tests latter.

>    -- gives much less confusing error messages if you get it slightly
> wrong
>    -- easy to read

Which is less important in high performance situlations.

>    -- uses a smaller subset of the language, so is especially easier
> for non-C++ experts
>    -- more general, in that it doesn't blow up and use silly amounts
> of space (and probably more time too, given cache churn) if N is not
> tiny

When I dump the code, I see 2 * N bytes of code in the unrolled loop.
When I dump your code, I see no loop unrolling, hence no point in
even trying to specialize the case.

Anytime you are doing code generation, you must be careful to avoid
blow up.  Such is life.  As you alluded to in the cache churn comment
idea unrolling requires mesurement.  However, with the template code
we are explicitly using code generation, in the c code, we are simply
hoping the compiler will do something we want.

>    -- more general also in that the same code does both the
> general-purpose (n known only at runtime) and the special-purpose
> job

yes, and properly written the template code will support that.
 
>  > The C example relies on a fairly smart compiler to 
>  > do interprocedual analysis.
> 
> Depends what you mean by fairly smart.  This is standard stuff: gcc is
> really not the best optimising compiler around.

This is true.  Therefore I tried this on both gcc and icc (intel's compiler).
icc did worse on the c than gcc did (interesting).  Especially since icc
was trying to do interprocedual analysis.

The C++ versions were very similar at the assembly level in both compilers.
The body of the loop was just series of fmul is both compiler outputs.

quick measurement with gettimeofday:
compiler N=3   N=30
gcc      5181  89866 
icc,c   18437 106522
icc,c++  1336   1296
g++      1297   1297

for 1M iterations of assignment of pow into a volatile double

These are very dependent on compiler flags in the c case.  Having
icc be more aggressive with loop unrolling made matters worse, since
the code no longer fit in L1.  There was much less needing to tune
compiler options with the template approach, it consistently gave the
best code.

I would venture to say that for performance, there is still need for
a programmer visible code generation engine.

>  > The C++ example only requires the inline keywork be honored, and
>  > you don't need explicit pow3 pow2, you have pow<3> pow<2> pow<any
>  > constant>.
>  > 
>  > Gives a bit more control over code generation.
> 
> It does.  I personally feel (actually have learned the hard way) that
> using C++ templates for multi-stage programming is mostly much more
> trouble than it is worth---especially when you realise what careful
> exploitation of C-level specalisation by inlining can do.

Relying on the compiler is risky business.  Doing code generation and
hoping the compiler will optimize something a certain way are really
different things.

Further, for really interesting code generation, C-level specalisation
by inlining is utterly inadiquit.  Some tasks, such as data marshalling
engines, can benifit greatly from straight forward template style code
generation (both in shorter development time and smaller code base), 
whereas there is no equivilent framework to do that in C.

> If you really want more control over code generation (not forgetting
> that just writing out what you want by hand is often the simplest
> option in practice!) then I think C++ templates are a dead end---far
> better to make the object language the same as the target language,
> as in MetaOcaml and similar.

Indeed, a unified approach is easier to use, though for performance the
code generation needs to be tuned at runtime, a task C++ templates 
certainly cannot pretent to approach.

Andrew Lenharth

-------------------
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

Re: [Caml-list] partial eval question

[Walid Taha]

On Mon, 27 Oct 2003, Andrew Lenharth wrote:

|On Mon, Oct 27, 2003 at 03:39:21PM +0000, William Chesters wrote:
|> And that's an improvement over
|> 
|>     double pow(double x, int n) {
|>       double it = 1;
|>       while (--n >= 0) it *= x;
|>       return it;
|>     }
|> 
|>     double pow3(double x, int n) {
|>       return pow(x, 3);
|>     }
|> 
|> in what way exactly?  (If it doesn't work for you, try
|> -funroll-all-loops.)
|
|And that's an improvement over
|
|template <int N>
|inline double pow (double x) {
|  return x * pow<N-1>(x);
|}
|template<>
|inline double pow<0> (double x) {
|  return 1.0;
|}
|
|in what way exactly?  (If it doesn't work for you, try 
|-O2) :)

OK.  There is an article specifically about this point:

	http://www.cs.rice.edu/~taha/publications/preprints/2003-12-01.pdf

(Comments are welcome, actually, the paper is undergoing the final 
revision).

|The C example relies on a fairly smart compiler to 
|do interprocedual analysis.  The C++ example 
|only requires the inline keywork be honored, and you 
|don't need explicit pow3 pow2, you have pow<3> pow<2> 
|pow<any constant>.
|
|Gives a bit more control over code generation.

The draw back with C++ templates, in this case, is that you have to wait 
until the C++ code is generate before you know it type checks.  A key goal 
of MSP is to ensure that generated code is *always* well-typed.  That 
actually has been achieved in the context of a wide-range of type systems.

Walid.

|Andrew
|
|-------------------
|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

Re: [Caml-list] partial eval question

[Andrew Lenharth]

On Tue, Feb 03, 2004 at 08:59:57PM -0600, Walid Taha wrote:
> 
> On Mon, 27 Oct 2003, Andrew Lenharth wrote:
(CUT C and C++ version)
> |in what way exactly?  (If it doesn't work for you, try 
> |-O2) :)

Of course, after I posted this, I made a version that was much better.
Sigh.

> OK.  There is an article specifically about this point:
> 
> 	http://www.cs.rice.edu/~taha/publications/preprints/2003-12-01.pdf
> 
> (Comments are welcome, actually, the paper is undergoing the final 
> revision).

It is late, and I will more carefully read the paper tomorrow, but I
do have a couple of initial questions.

With C++ templates I can implement optimizations based on data type,
as you mention in 4.1, and provide a default implementation to ensure
a well-typed function.  Can I get the same from MetaOCaml?  Really I
guess I am almost asking for ad-hoc polymorphism, but with a fall back
polymorphic implementation.

Examples (in C++) may include generating code for vector units (SSE,
altivec, etc) for operations with known semantics (+, etc) if a type
in a vector is basic and falling back to calling the operator on
unknown types.  Similar thing for choosing a bitwise copy of a
container verses using the copy constructor of the members.

For such type optimizations I want

let t_eq x y = 
match (type x),(type y) with
  int,int -> int compare
| float,float -> float compare
| bool,bool -> (x && y)|| ((not x) && (not y))
| _,_ -> x = y

This is a silly example in that it only uses the mechanism to avoid
the runtime overhead for polymorphic functions, but it is late and I
hope you can understand what I am getting at.

Also, you say you can generate code at runtime, is the generated code
garbage collected?

> |The C example relies on a fairly smart compiler to 
> |do interprocedual analysis.  The C++ example 
> |only requires the inline keywork be honored, and you 
> |don't need explicit pow3 pow2, you have pow<3> pow<2> 
> |pow<any constant>.
> |
> |Gives a bit more control over code generation.
> 
> The draw back with C++ templates, in this case, is that you have to wait 
> until the C++ code is generate before you know it type checks.  A key goal 
> of MSP is to ensure that generated code is *always* well-typed.  That 
> actually has been achieved in the context of a wide-range of type systems.

I was a bit confused by this paragraph at first, but the paper
clarified it.  I think you meant to imply that any code that could be
generated by MSP will be well-typed.

This is starting to sound like other type checking arguments :) It is
correct for every way it is used v.s. it is correct for every way it
could be used.

Andrew

-- 
"The reasonable man adapts himself to the world; the unreasonable 
one persists in trying to adapt the world to 
himself. Therefore all progress depends on the unreasonable man."
-- George Bernard Shaw

No matter how cynical you become, it's never enough to keep up.
-- Lily Tomlin

Fools ignore complexity; pragmatists suffer it; experts avoid it; 
geniuses remove it.
-- A. Perlis

-------------------
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

Re: [Caml-list] partial eval question

[Walid Taha]

Hello Andrew,

On Wed, 4 Feb 2004, Andrew Lenharth wrote:

|> OK.  There is an article specifically about this point:
|> 
|> 	http://www.cs.rice.edu/~taha/publications/preprints/2003-12-01.pdf
|> 
|> (Comments are welcome, actually, the paper is undergoing the final 
|> revision).
|
|It is late, and I will more carefully read the paper tomorrow, but I
|do have a couple of initial questions.
|
|With C++ templates I can implement optimizations based on data type,
|as you mention in 4.1, and provide a default implementation to ensure
|a well-typed function.  Can I get the same from MetaOCaml?  Really I
|guess I am almost asking for ad-hoc polymorphism, but with a fall back
|polymorphic implementation.

No.  Not in the current MetaOCaml, which is basically just

	OCaml + Brackets + Escape + Run

As far as typing issues are concerned, there is an easy way to determine
if something can be typed done in MetaOCaml or not:  Erase your brackets,
escapes, and run.  If your program can't be typed in OCaml, it can't be
typed in MetaOCaml.

What you describe requires a change to the core type system, which
MetaOCaml tries to keep unchanged.

There are other research efforts that explore adding related changes to
the core type system.  If we have the resources, it would certainly be
worthwhile to incorporating such changes into MetaOCaml.

|Also, you say you can generate code at runtime, is the generated code
|garbage collected?

Not in the current (alpha) versions.  Do I see a volunteer?  :)

|> |The C example relies on a fairly smart compiler to 
|> |do interprocedual analysis.  The C++ example 
|> |only requires the inline keywork be honored, and you 
|> |don't need explicit pow3 pow2, you have pow<3> pow<2> 
|> |pow<any constant>.
|> |
|> |Gives a bit more control over code generation.
|> 
|> The draw back with C++ templates, in this case, is that you have to wait 
|> until the C++ code is generate before you know it type checks.  A key goal 
|> of MSP is to ensure that generated code is *always* well-typed.  That 
|> actually has been achieved in the context of a wide-range of type systems.
|
|I was a bit confused by this paragraph at first, but the paper
|clarified it.  I think you meant to imply that any code that could be
|generated by MSP will be well-typed.

Yes.

|This is starting to sound like other type checking arguments :) It is
|correct for every way it is used v.s. it is correct for every way it
|could be used.

I am not sure I understand what you are saying.  Can you clarify?

Walid.

-------------------
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

Re: [Caml-list] partial eval question

[Yann Regis-Gianas]

William Chesters wrote :
> And that's an improvement over
>
>     double pow(double x, int n) {
>       double it = 1;
>       while (--n >= 0) it *= x;
>       return it;
>     }
>
>     double pow3(double x, int n) {
>       return pow(x, 3);
>     }
>
> in what way exactly?  (If it doesn't work for you, try
> -funroll-all-loops.)
>
> For these kinds of purposes, Multi-Stage Programming is a very
> labour-intensive and error-prone way of doing what mainstream
> compilers will do for you already.  

	I agree with you that constant folding, inlining and unrolling are well known 
by common compilers. However, when you want to _control_  these 
optimisations, this is more difficult with standard optimizers since they are 
black-boxes. For example, the benefit of these optimizations is linked with 
the size of code, the processor type but also with the values of data (think 
of the sparse matrix example). All these parameters cannot be managed by a 
low level compiler optimizer. 

	In MetaOCaml, the general process of multi-stage evaluation enables the 
user-control of optimization simply :

let k = eval_processor_capabilities ()

let rec pow n = function 
                | 1 -> .< fun x -> x >.
                | n when n < k -> .< fun x  -> x * .~(pow (n-1)) x>.
		| n -> .< fun x -> x *. (.! (pow (n-1)) x >.
 

> Maybe it has useful applications
> in e.g. generation of numerical codes, where inlining, unrolling,
> "templatization" and partial evaluation are not enough because major
> structural transformations are required.  But then, maybe
> sophisticated jobs like that are always going to be easiest done with
> special-purpose code generators?

	By adding the multi-stage evaluation into a programming language, we obtain 
one general,  transparent and simple tool. Why should we develop or learn the 
usage of many special-purpose optimizers ? Yes, some work has to be done to 
enhance its user-friendliness but, in my opinion, this feature can be 
relevant in many daily programming situations (not only optimization). There 
are some papers about that, for example :

"Accomplishments and Research Challenges in Meta-programming". 
Tim Sheard.

--
Yann Regis-Gianas.

-------------------
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

Re: [Caml-list] partial eval question

[William Chesters]

Yann Regis-Gianas writes:
 > I agree with you that constant folding, inlining and unrolling are well known 
 > by common compilers. However, when you want to _control_  these 
 > optimisations, this is more difficult with standard optimizers since they are 
 > black-boxes.

That's a strength as well as a weakness.  In reasonably simple cases
it "just works" and is less effort, more readable, more maintainable.

 > By adding the multi-stage evaluation into a programming language, we obtain 
 > one general,  transparent and simple tool. Why should we develop or learn the 
 > usage of many special-purpose optimizers ?

Partial/abstract evaluation is a pretty general purpose optimiser.
Half seriously: Metaml improves on C++ templates by making the
metalanguage the same as and more tightly integrated with the object
language.  Partial evaluation can almost be seen as going a step
further and having the compiler infer the tightest meta/object
boundary.  Perhaps if there was a way of telling the partial evaluator
"specialise this code block by value of parameter i / type of
parameter j / whatever" (*) it would handle all the everyday tasks for
which metaml is designed, and require considerably less effort and
expertise.

(*) to get this effect with good current compilers you have to isolate
the block in a function, turn up the inlining sufficiently, and use
"if" branches to trigger specialisation

 > By adding the multi-stage evaluation into a programming language,
 > we obtain one general, transparent and simple tool.

It's not simple or transparent, and for many tasks it isn't necessary.
Perhaps it's a good general tool for the generation of code for
numerics etc.---it may help specialist library writers.

For everyday programming I think one has to remember that heavyweight
attempts to achieve generality are often not worth it.  Simple
things can be done by the compiler or just written out by hand.
Complex things look nasty when hand-optimised, but if you try to do
them "better and more generally" using metaprogramming, you are likely
to take much longer, and end up with something which is hard to
decipher and disappointingly doesn't generalise in quite the way you
want.

There is little point in trading the "complexity" of prolix,
irritating but basically straightforward hand-specialised code for the
genuinely challenging complexity of a meta-programming system.  (It
really does become extremely complicated when you start taking into
account the detailed requirements of real world problems.)

The most viable option is often to settle on a reasonably general and
extensible conceptual framework (at the level of conventions rather
than anything more formal) and implement just the bits of it that you
actually need for your particular problem, encapsulated in a
consistent way.

-------------------
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

Re: [Caml-list] partial eval question

[Walid Taha]

Sorry for picking up this thread after such a long time, but I only now 
got a chance to see this email.

On Tue, 28 Oct 2003, William Chesters wrote:

| > By adding the multi-stage evaluation into a programming language,
| > we obtain one general, transparent and simple tool.
|
|It's not simple or transparent, and for many tasks it isn't necessary.
|Perhaps it's a good general tool for the generation of code for
|numerics etc.---it may help specialist library writers.

I'm note sure why you think MSP is "neither simple nor transparent".  What 
can be simpler than having just three new constructs to do both generate 
and execute all programs, to be guaranteed statically that (many) 
generated programs will be well-typed even before you generate them, and 
to know that the three new constructs satisfy simple equational reasoning 
principles?

"For many tasks, it isn't necessary" is an argument that can also be made 
against module systems, objects, functions, and pretty much anything that 
can be viewed as a language feature.

The primary audience is indeed "specialist writers", who are interested in 
building program generators, and who build enough program generators to 
know what kind of support would actually help them in doing that.  Note 
that it is NOT for *users* of program generators:  it's for the 
people who *build* them.

Peace.

Walid.

-------------------
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

Re: [Caml-list] partial eval question

[Walid Taha]

On Mon, 27 Oct 2003, William Chesters wrote:

|Damien writes:
| > Multi-Stage Programming is your friend...
| > <http://www.cs.rice.edu/~taha/MSP/>
| > 
| > let rec pow n = .< 
| > 	.~(match n with
| > 		| 1 -> .< fun x -> x >.
| > 		| n -> .< fun x -> x * .~(pow (n-1)) x>.
| > 	)
| > >.
| > 
| > (pow 3) get reduced into .<fun x -> x*x*x>.
|
|And that's an improvement over
|
|    double pow(double x, int n) {
|      double it = 1;
|      while (--n >= 0) it *= x;
|      return it;
|    }
|
|    double pow3(double x, int n) {
|      return pow(x, 3);
|    }
|
|in what way exactly?  (If it doesn't work for you, try
|-funroll-all-loops.)

Two reasons:  1) MSP is finer grained (you usually DON'T want to unroll
all loops), and 2) you can do it at runtime (it's not limited to
compile-time specialization).  Those two simple reasons have a huge impact
when you are building bigger and more complex software systems.

|For these kinds of purposes, Multi-Stage Programming is a very
|labour-intensive and error-prone way of doing what mainstream
|compilers will do for you already.  

Why is MSP labour intensive?  More importantly, why do you think it is
error-prone?

|Maybe it has useful applications
|in e.g. generation of numerical codes, where inlining, unrolling,
|"templatization" and partial evaluation are not enough because major
|structural transformations are required.  But then, maybe
|sophisticated jobs like that are always going to be easiest done with
|special-purpose code generators?

What kinds do you have in mind?

MSP's primary target users are indeed builders of code generators, but you 
seem to suggest that that somehow needs to be limited to an elite group of 
"generator writers"...  That's exactly what MSP is supposed to help Joe 
Programmer avoid.

Walid.

-------------------
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

Re: [Caml-list] partial eval question

[Dmitry Lomov]

On Monday 27 October 2003 10:14, Damien wrote:
> On Mon, 27 Oct 2003 01:41:49 -0000 Ben Kavanagh wrote:
> > Say I have a function such as pow defined as
> >
> > let pow n x =
> > [skip]
> >
> > 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?
>
> Multi-Stage Programming is your friend...
> <http://www.cs.rice.edu/~taha/MSP/>
>
> There are two ML implementations :
> Ocaml : MetaOCaml <http://www.cs.rice.edu/~taha/MetaOCaml/>
> SML : MetaML <http://www.cse.ogi.edu/PacSoft/projects/metaml/>

May I also humbly draw your attention to Dynamic Caml:
http://oops.tercom.ru/dml

:)

Friendly,
Dmitry
-- 
Dmitry Lomov
IntelliJ Labs / JetBrains Inc.
http://www.intellij.com
"Develop with pleasure!"


-------------------
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

Re: [Caml-list] partial eval question

[Vincent Balat [prof Moggi team]]

I am working on a "type-directed" partial evaluator for OCaml.
I did an implementation a few years ago with Olivier Danvy
(see http://www.pps.jussieu.fr/~balat/publications/balat-danvy.pdf)

But it is still*experimental*:
 - only a small subset on ocaml
 - need a modified version of ocaml with a "call/cc" operator

ex:
# let rec power mul one x n = 
      if n=0 then one 
      else (mul x (power mul one x (n-1)));;  
      (* We close by mul and one because the function to be
         normalized must be mostly polymorphic *)
val power : ('a -> 'b -> 'b) -> 'b -> 'a -> int -> 'b = <fun>

# let power3 mul one x = power mul one x 3;;
val power3 : ('a -> 'b -> 'b) -> 'b -> 'a -> 'b = <fun>

# normalize "power3";;
- : unit = ()
(* Now the function power3 is normalized *)

(* You can print the normalized code by: *)
# normalize_nf "power3";;
- : NormalForms.computation =
(fun v7 v8 v9 ->
 let v10 = v7 v9 in
 let v11 = v10 v8 in
 let v12 = v7 v9 in
 let v13 = v12 v11 in
 let v14 = v7 v9 in
 let v15 = v14 v13 in
 v15)

It is not available on the web  any more (it was for ocaml 1.05) but I
can send it to you if you are interested.

I'm planning to update  it and to try to extend it  to a larger subset
of ocaml.  There are still a  lot of opened questions  to solve before
having it included in ocaml...

Otherwise,  as  pointed  by  Damien  Pous,  you can  have  a  look  at
MetaOCaml, which is  a multi-level language based on  ocaml, that is a
language  that   allows  you   to  manipulate  source   code  (program
generation).

Vincent Balat

---- Ben Kavanagh écrit :
 > 
 > 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

Re: [Caml-list] partial eval question

[Walid Taha]

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

RE: [Caml-list] partial eval question

[Ben Kavanagh]

Walid, 

Thanks 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 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

I concur that such an undiscriminating approach to partial evaluation in
a program is not ideal, a point you touch on in a later mail to the Caml
list.

It does seem, though, that a useful syntax shortcut that made this
direct partial-application -> partial-eval mapping available in the
manner of Lee/Leone could be useful in MetaOCaml. 

Do you agree?

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

RE: [Caml-list] partial eval question

[Ben Kavanagh]

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

RE: [Caml-list] partial eval question

[Walid Taha]

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