home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 924 next >
Encoding:
Text File  |  1992-07-20  |  1.3 KB  |  38 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!cis.ohio-state.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!crabapple.srv.cs.cmu.edu!dtarditi
  3. From: dtarditi@CS.CMU.EDU (David Tarditi)
  4. Subject: algorithmic efficiency and lazy languages
  5. Message-ID: <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU>
  6. Date: Tue, 21 Jul 92 07:35:49 GMT
  7. Organization: School of Computer Science, Carnegie Mellon University
  8. Nntp-Posting-Host: desert.fox.cs.cmu.edu
  9. Distribution: comp
  10. Originator: dtarditi@DESERT.FOX.CS.CMU.EDU
  11. Lines: 25
  12.  
  13. I have always been under the impression that lazy evaluation
  14. makes it difficult to determine the time and space efficiency
  15. of programs.  
  16.  
  17. If this is true, then it is a strong practical argument against using 
  18. lazy evaluation, since asymptotic efficiency is quite important in
  19. practice.   An O(n^2) algorithm may be unusable in practice, while
  20. an O(n log n) algorithm may do quite nicely.
  21.  
  22. As a side note, it is sufficient to base the argument simply on
  23. affecting asymptotic space complexity, since that affects the 
  24. asymptotic time complexity of garbage collection.
  25.  
  26. It seems hard to argue that referential transparency is more
  27. important to language design than the ability to predict the
  28. algorithmic behavior of one's programs, given the fact that
  29. a vast section of computer science is devoted to the study
  30. of algorithms.
  31.  
  32.   -- David Tarditi
  33.  
  34.  
  35.  
  36.  
  37.  
  38.