home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / function / 1460 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  2.4 KB
  1. Path: sparky!uunet!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Run-Time Code Generation ?
  5. Message-ID: <1992Dec15.152411.23326@odin.diku.dk>
  6. Date: 15 Dec 92 15:24:11 GMT
  7. References: <1992Dec14.152715.6442@ifi.uio.no>
  8. Sender: torbenm@thor.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 64
  11.  
  12. olsson@ifi.uio.no (Jan Roland Olsson) writes:
  13.  
  14. >I have a program in Standard ML of New Jersey that
  15. >synthesizes, i.e. writes, function definitions and
  16. >translates them to closures in order to execute them.
  17.  
  18. >This works fine except for the fact that the resulting
  19. >functions execute about twice as slowly as functions
  20. >that are defined by ML source code and compiled.
  21. >Since the functions created at run-time are needed
  22. >over and over again, perhaps even millions of times
  23. >including recursive calls, this is a significant
  24. >performance problem for me.
  25. >Here is a small trivial example that illustrates
  26. >the problem.
  27.  
  28.  
  29. >fun compose 0 F = ( fn X => X )
  30. >  | compose N F = 
  31. >      let val g = compose (N-1) F
  32. >      in
  33. >       fn X => F ( g X )
  34. >      end;
  35.  
  36.  
  37. >val f1 = compose 5 tl;
  38.  
  39. >val f2 = fn X => tl(tl(tl(tl(tl(X)))));
  40.  
  41.  
  42. >The functions f1 and f2 are the same, but calls
  43. >to f1 execute much slower than calls to f2.
  44.  
  45. >What I really would like to have is a built-in
  46. >function 
  47.  
  48. >compile : ( 'a -> 'b ) -> ( 'a -> 'b )
  49.  
  50. >which has the same semantics as the identity 
  51. >function, but changes the representation of the
  52. >definition of its argument from lots of inter-
  53. >linked closures to pure machine code.
  54.  
  55. You could try to rewrite compose into a somewhat more efficient form:
  56.  
  57. fun compose N F =
  58.    let fun g 0 = (fn X => X)
  59.          | g M = let val g1 = (g  N-1) in (fn X => F (g1 X)) end;
  60.       in
  61.        g N
  62.       end;
  63.  
  64. This version does not carry F as a parameter to the recursive call.
  65.  
  66. f1 will still be slower than f2 when using this definition, but not by
  67. the same extent. What is needed for this is that the application (g1
  68. X) is unfolded so (fn X => F ((fn X' => F (g1' X')) X)) is reduced to
  69. (fn X => F (F (g1' X))). This does not require compilation of the code,
  70. but rather reduction to more than just WHNF. Of course, if this is to
  71. be represented by a single closure, the code for it will not exist as
  72. a single piece of the original code. But another representation in
  73. between closures and straightline code would be feasible.
  74.  
  75.     Torben Mogensen (torbenm@diku.dk)
  76.