home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 950 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  2.4 KB
  1. Path: sparky!uunet!usc!wupost!uwm.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!acha
  2. From: acha@CS.CMU.EDU (Anurag Acharya)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: algorithmic efficiency and lazy languages
  5. Message-ID: <ACHA.92Jul23145206@DRAVIDO.SOAR.CS.CMU.EDU>
  6. Date: 23 Jul 92 19:52:06 GMT
  7. Article-I.D.: DRAVIDO.ACHA.92Jul23145206
  8. References: <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> <501@owl.ukc.ac.uk>
  9. Distribution: comp
  10. Organization: School of Computer Science, Carnegie Mellon University
  11. Lines: 30
  12. Nntp-Posting-Host: dravido.soar.cs.cmu.edu
  13. In-Reply-To: dat@ukc.ac.uk's message of 23 Jul 92 15:36:00 GMT
  14. Originator: acha@DRAVIDO.SOAR.CS.CMU.EDU
  15.  
  16. In article <501@owl.ukc.ac.uk> dat@ukc.ac.uk (D.A.Turner) writes:
  17. > In article <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> dtarditi@CS.CMU.EDU (David Tarditi) writes:
  18. > >I have always been under the impression that lazy evaluation
  19. > >makes it difficult to determine the time and space efficiency
  20. > >of programs.>
  21. > >If this is true, then it is a strong practical argument against using 
  22. > >lazy evaluation, since asymptotic efficiency is quite important in
  23. > >practice.> An O(n^2) algorithm may be unusable in practice, while
  24. > >an O(n log n) algorithm may do quite nicely.
  25.  
  26. > I think it is only half true. There  is  no  special  difficulty  in
  27. > reasoning   about  the  *time*  complexity  of  programs  written  in  a
  28. > non-strict  functional  language.   One  can  derive  from  the  program
  29. > equations   for  functions  fi  say,  similar  equations  for  Tfi,  the
  30. > time-to-execute of function fi.  There is quite  a  nice  discussion  of
  31. > this,   with   some   examples,  in  chapter  6  of  Bird  and  Wadler's
  32. > "Introduction to Functional Programming".
  33. >   On the other  hand  reasoning  about  the  *space*  complexity  of  such
  34. > programs seems to be much more difficult.
  35.  
  36. If it is difficult to determine the space complexity of the programs, I wonder
  37. why is it easy to determine their time complexity ? Allocating and 
  38. initializing space takes time proportional to the space used (in the best
  39. case -- assuming the space is never reused). Explicit freeing 
  40. takes time proportional to the space freed (again in the best case -- not
  41. much compaction needed), garbage collection needs time proportional to the
  42. amount of live data (best case -- mark and sweep needs time proportional
  43. to the all space available to the program). 
  44.  
  45. anurag
  46.