home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 949 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  1.3 KB
  1. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!swrinde!mips!pacbell.com!decwrl!parc!boehm
  2. From: boehm@parc.xerox.com (Hans Boehm)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: algorithmic efficiency and lazy languages
  5. Message-ID: <boehm.711912209@siria>
  6. Date: 23 Jul 92 17:23:29 GMT
  7. References: <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> <501@owl.ukc.ac.uk>
  8. Sender: news@parc.xerox.com
  9. Distribution: comp
  10. Organization: Xerox PARC
  11. Lines: 23
  12.  
  13. dat@ukc.ac.uk (D.A.Turner) writes:
  14.  
  15. > There  is  no  special  difficulty  in
  16. >reasoning   about  the  *time*  complexity  of  programs  written  in  a
  17. >non-strict  functional  language.   One  can  derive  from  the  program
  18. >equations   for  functions  fi  say,  similar  equations  for  Tfi,  the
  19. >time-to-execute of function fi.
  20.  
  21. It seems to me that this is insufficient.  It basically tells us that it's
  22. possible to write accurate profilers.  The real question is:  Are the Tfi
  23. sufficiently simple for real programs that I can understand what's going
  24. on, and use them to drive my algorithm design? 
  25.  
  26. >There is quite  a  nice  discussion  of
  27. >this,   with   some   examples,  in  chapter  6  of  Bird  and  Wadler's
  28. >"Introduction to Functional Programming".
  29. >
  30. >On the other  hand  reasoning  about  the  *space*  complexity  of  such
  31. >programs seems to be much more difficult.
  32.  
  33. >David Turner
  34.  
  35. Hans-J. Boehm
  36.