home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 979 < prev    next >
Encoding:
Text File  |  1992-07-29  |  3.1 KB  |  57 lines

  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!mcsun!sunic!diku!bombadil
  3. From: bombadil@diku.dk (Kristian Nielsen)
  4. Subject: Re: Maturing implementations of functional languages (and religion)
  5. Message-ID: <1992Jul19.151418.16386@odin.diku.dk>
  6. Sender: bombadil@ask.diku.dk
  7. Date: Sun, 19 Jul 1992 15:14:18 GMT
  8. References: <TMB.92Jul14175723@arolla.idiap.ch>> <NICKH.92Jul14151920@VOILA.VENARI.CS.CMU.EDU> <farrell.711165248@coral.cs.jcu.edu.au> <rk+mqkm@lynx.unm.edu> <farrell.711246506@coral.cs.jcu.edu.au>
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 45
  11.  
  12. farrell@coral.cs.jcu.edu.au (John Farrell) writes:
  13.  
  14. >  Certainly, functional languages have some properties which look like they
  15. >will slow the language down no matter what. On the other hand, we can write
  16. >functional and FORTRAN programs which produce exactly the same results on
  17. >exactly the same machine, so why shouldn't they both run in the same time.
  18. >While a functional program is slower than an equivalent procedural program, we
  19. >have to acknowledge that we haven't got the compiler technology right yet.
  20.  
  21. I think there is another aspect that is often overlooked when lazy
  22. functional programs are deemed slower than en equivalent program in a
  23. more traditional language such as C or Pascal. I often find myself
  24. writing 'better' programs in say Haskell to solve a particular problem
  25. than I would have done otherwise. A very common example of this is the
  26. tendency to have artificial constrains on the size of data structures
  27. used in programs, like the dreaded maximum identifier length in
  28. compilers or 256 character limit on input lines. In functional
  29. languages (eager and lazy alike) the natural use of dynamic data
  30. structures avoids this. Another example more related to laziness would
  31. be a binary tree implementation. In a straitforward implementation in
  32. an eager language the time complexity of m insertions followed by n
  33. lookups would be O((m+n)log(m)). In a lazy implementation the
  34. complexity might be somewhat better, since the insertions are not
  35. taking place until/unless actually needed by the lookup operations.
  36.  
  37. The point is that a lazy program that is seemingly equivalent to
  38. another (efficient) program may in fact not be quite equivalent. While
  39. using dynamic data structures is probably at least as efficient in C
  40. as in functional languages, I would think that the true equivalent of
  41. the Haskell binary tree would be quite difficult to write as efficient
  42. in C. The code would certainly be an order of magnitude more complex.
  43. Anyway, such subtle differences will make it very difficult for a
  44. compiler to reach the efficiency of todays compilers for traditional
  45. languages, since it would have to outguess the programmer as to
  46. his/her intention. In the binary tree example, a transformation to
  47. strict evaluation would probably seem 'wrong', even though it might be
  48. faster in most cases.
  49.  
  50. My personal feelings about this is that the lazy formulation is
  51. usually the 'right', or most elegant, way to formulate the solution
  52. (as likely as not steaming from my matematical background), causing me
  53. to delight in the added power of expression provided by these
  54. languages.
  55.  
  56.     - Kristian.
  57.