home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / function / 1453 < prev    next >
Encoding:
Text File  |  1992-12-14  |  2.9 KB  |  102 lines
  1. Nntp-Posting-Host: hauken.ifi.uio.no
  2. Newsgroups: comp.lang.functional
  3. Path: sparky!uunet!mcsun!sunic!aun.uninett.no!nuug!ifi.uio.no!olsson
  4. From: olsson@ifi.uio.no (Jan Roland Olsson)
  5. Subject: Run-Time Code Generation ?
  6. Message-ID: <1992Dec14.152715.6442@ifi.uio.no>
  7. Organization: Dept. of Informatics, University of Oslo, Norway
  8. Date: Mon, 14 Dec 1992 15:27:15 GMT
  9. Lines: 90
  10. Originator: olsson@hauken.ifi.uio.no
  11.  
  12.  
  13. Functions that return other functions are common in
  14. functional programs. The function returned is created
  15. at run-time and is in strict languages most often 
  16. represented using closures. 
  17.  
  18. In my view, a closure consists of 
  19.  
  20. 1. A pointer to the machine code for a function.
  21. 2. One or more pointers to "arguments" of the function.
  22.    These arguments may be other closures.
  23.  
  24. It sometimes happens that the function returned is
  25. represented by 10 or more closures pointing to each
  26. other. If the function is not recursive, these closures
  27. normally form a tree that is isomorphic to the
  28. expression tree for the right hand side of the
  29. function definition.
  30.  
  31. A recursive function may be represented by closures 
  32. that form a directed cyclic graph, where the cycle
  33. can be introduced with a pointer i.e. a value of
  34. ref type in ML.
  35.  
  36. I have a program in Standard ML of New Jersey that
  37. synthesizes, i.e. writes, function definitions and
  38. translates them to closures in order to execute them.
  39.  
  40. This works fine except for the fact that the resulting
  41. functions execute about twice as slowly as functions
  42. that are defined by ML source code and compiled.
  43. Since the functions created at run-time are needed
  44. over and over again, perhaps even millions of times
  45. including recursive calls, this is a significant
  46. performance problem for me.
  47. Here is a small trivial example that illustrates
  48. the problem.
  49.  
  50.  
  51. fun compose 0 F = ( fn X => X )
  52.   | compose N F = 
  53.       let val g = compose (N-1) F
  54.       in
  55.        fn X => F ( g X )
  56.       end;
  57.  
  58.  
  59. val f1 = compose 5 tl;
  60.  
  61. val f2 = fn X => tl(tl(tl(tl(tl(X)))));
  62.  
  63.  
  64. The functions f1 and f2 are the same, but calls
  65. to f1 execute much slower than calls to f2.
  66.  
  67. What I really would like to have is a built-in
  68. function 
  69.  
  70. compile : ( 'a -> 'b ) -> ( 'a -> 'b )
  71.  
  72. which has the same semantics as the identity 
  73. function, but changes the representation of the
  74. definition of its argument from lots of inter-
  75. linked closures to pure machine code.
  76. Since Standard ML of New Jersey stores machine
  77. code on the heap as garbage collectable byte
  78. sequences and since the compiler is part of a
  79. running ML program this seems possible.
  80.  
  81. Am I the only ML programmer on this planet that
  82. finds such a function useful ?
  83.  
  84. Or maybe there are some drawbacks or solutions that
  85. I have overlooked ?
  86.  
  87. Or maybe I should use Common Lisp instead, which after
  88. all has compile built in ? Needing to switch to
  89. Lisp just for a performance problem like this would
  90. really be a pity, since ML in my view is a much
  91. better language and since Standard ML of New Jersey 
  92. is an excellent implementation.
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.