🚀 go-pugleaf

olsson@ifi.uio.no (Jan Roland Olsson) writes:

>I have a program in Standard ML of New Jersey that
>synthesizes, i.e. writes, function definitions and
>translates them to closures in order to execute them.

>This works fine except for the fact that the resulting
>functions execute about twice as slowly as functions
>that are defined by ML source code and compiled.
>Since the functions created at run-time are needed
>over and over again, perhaps even millions of times
>including recursive calls, this is a significant
>performance problem for me.
>Here is a small trivial example that illustrates
>the problem.


>fun compose 0 F = ( fn X => X )
>  | compose N F = 
>      let val g = compose (N-1) F
>      in
>       fn X => F ( g X )
>      end;


>val f1 = compose 5 tl;

>val f2 = fn X => tl(tl(tl(tl(tl(X)))));


>The functions f1 and f2 are the same, but calls
>to f1 execute much slower than calls to f2.

>What I really would like to have is a built-in
>function 

>compile : ( 'a -> 'b ) -> ( 'a -> 'b )

>which has the same semantics as the identity 
>function, but changes the representation of the
>definition of its argument from lots of inter-
>linked closures to pure machine code.

You could try to rewrite compose into a somewhat more efficient form:

fun compose N F =
   let fun g 0 = (fn X => X)
         | g M = let val g1 = (g  N-1) in (fn X => F (g1 X)) end;
      in
       g N
      end;

This version does not carry F as a parameter to the recursive call.

f1 will still be slower than f2 when using this definition, but not by
the same extent. What is needed for this is that the application (g1
X) is unfolded so (fn X => F ((fn X' => F (g1' X')) X)) is reduced to
(fn X => F (F (g1' X))). This does not require compilation of the code,
but rather reduction to more than just WHNF. Of course, if this is to
be represented by a single closure, the code for it will not exist as
a single piece of the original code. But another representation in
between closures and straightline code would be feasible.

	Torben Mogensen (torbenm@diku.dk)