home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 952 < prev    next >
Encoding:
Internet Message Format  |  1992-07-24  |  4.7 KB
  1. Path: sparky!uunet!mcsun!uknet!icdoc!ds
  2. From: ds@doc.ic.ac.uk (David Sands)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: algorithmic efficiency and lazy languages
  5. Message-ID: <ds.711975612@achilles>
  6. Date: 24 Jul 92 11:00:12 GMT
  7. References: <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> <501@owl.ukc.ac.uk>
  8. Sender: usenet@doc.ic.ac.uk
  9. Distribution: comp
  10. Organization: Department of Computing, Imperial College, University of London, UK.
  11. Lines: 116
  12. Nntp-Posting-Host: achilles.doc.ic.ac.uk
  13.  
  14. dat@ukc.ac.uk (D.A.Turner) writes:
  15.  
  16. > There  is  no  special  difficulty  in
  17. >reasoning   about  the  *time*  complexity  of  programs  written  in  a
  18. >non-strict  functional  language.   One  can  derive  from  the  program
  19. >equations   for  functions  fi  say,  similar  equations  for  Tfi,  the
  20. >time-to-execute of function fi. There is quite  a  nice  discussion  of
  21. >this,   with   some   examples,  in  chapter  6  of  Bird  and  Wadler's
  22. >"Introduction to Functional Programming".
  23.  
  24. I think there is some "special difficulty" in reasoning about the time
  25. complexity of non-strict programs, and that B + W have chosen to
  26. de-emphasise these problems.  The "similar equations for Tfi" given by B+W are
  27. entirely context sensitive. For example, the statement (Ch 6 p138) that
  28.     T_reverse = O (n^2) 
  29. (the time to compute the naive reversal of a list is order n-squared)
  30. depends entirely on the assumption that the entire list is computed. 
  31.  
  32. For example, given a definition  of the form 
  33.  f3 x = f1 (f2 x) 
  34. with your/B&W's "similar equations" for Tf1 and Tf2, it is *not* the case that
  35.  Tf3 x = (Tf2 x) + (Tf1 (f2 x)) 
  36. because of 
  37. (i) lazy evaluation, which makes the cost of evaluating f2 dependent
  38. on its consumer f1, and
  39. (ii) higher order functions, which can make the time to evaluate f1
  40. dependent on more than just the (extensional) value of (f2 x), in the case
  41. that (f2 x) is a function (and similarly for f2 if x is of function type).
  42.  
  43. As a simple example (of (i)), take f2 = reverse and f1 = head. It should not be
  44. too hard to see that the time to evaluate f3 is linear in the length
  45. of its argument.
  46.  
  47. Nonetheless, I still agree with the second point:
  48.  
  49. >On the other  hand  reasoning  about  the  *space*  complexity  of  such
  50. >programs seems to be much more difficult.
  51.  
  52. Dave.
  53.  
  54. ----------------------------------------------------------
  55.  
  56. For anyone who might be interested, issues (i) and (ii) are considered
  57. in some detail in my thesis. Here are some other related references,
  58. some of which were mentioned recently in this group.
  59.  
  60. (My stuff is available by anonymous ftp from directory papers/Sands
  61. at theory.doc.ic.ac.uk)
  62.  
  63. @phdthesis{Bjerner:PhD,
  64.     author = "B. Bjerner",
  65.     title = "Time Complexity of Programs in Type Theory",
  66.     school = "Chalmers University of Technology",
  67.     year = 1989 }
  68.  
  69. @inproceedings{Bjerner:Holmstrom:Compositional,
  70.     author = {B. Bjerner and S. Holmstr\"om},
  71.     title = "A compositional approach to time analysis of first order lazy 
  72.                 functional programs",
  73.     booktitle = "Functional {P}rogramming {L}anguages and {C}omputer {A}rchitecture, conference proceedings",
  74.     publisher = {ACM press},
  75.     year =          {1989}
  76.         }
  77.  
  78. @inproceedings{Metayer:Analysis,
  79.         author = "{LeM\'etayer}, D.",
  80.         title = "Analysis of Functional Programs by Program Transformation",
  81.         booktitle = "Second France--Japan Artificial Intelligence and Computer
  82.                  Science Symposium",
  83.         month = "",
  84.         publisher = "North--Holland",
  85.         year = 1988}
  86.  
  87. @inproceedings{Sands:GFPW,
  88.         author =        "D. Sands",
  89.         title =         "Complexity Analysis for a Lazy Higher-Order Language",
  90.         booktitle =     
  91. {Proceedings of  Glasgow Workshop on Functional Programming },
  92.         publisher =     {Springer Verlag},
  93.         series =        {Workshop Series},
  94.         month =         {August},
  95.         year =          {1989},
  96.         }
  97.  
  98. @PhDThesis{Sands:PhD,
  99.   author =      "D. Sands",
  100.   title =       "Calculi for Time Analysis of Functional Programs",
  101.   school =      "Imperial College",
  102.   year =        "1990",
  103.   month =       "September",
  104.   OPTnote =     ""
  105. }
  106.  
  107. @InProceedings{Sands:FSTandTCS,
  108.   author =      "D. Sands",
  109.   title =       "Time Analysis, Cost Equivalence and Program Refinement",
  110.   booktitle =   "Proceedings of the Eleventh Conference on Foundations
  111.                  of Software Technology and Theoretical Computer Science",
  112.   year =        "1991",
  113.   pages =       "25--39",
  114.   publisher =   "Springer-Verlag",
  115.   number =      "560",
  116.   series =      "{L}{N}{C}{S}",
  117.    month =       "December"
  118. }
  119.  
  120. @inproceedings{Wadler:Strictness:Time,
  121.     author = "P. Wadler",
  122.     title = "Strictness Analysis Aids Time Analysis",
  123.     booktitle = "15th ACM Symposium on Principals of Programming Languages",
  124.     month = "January",
  125.     year = 1988}
  126.  
  127.  
  128.  
  129. --
  130.