home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1356 < prev    next >
Encoding:
Text File  |  1992-11-12  |  3.5 KB  |  78 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!gumby!yale!cs.yale.edu!news
  3. From: jones-mark@CS.YALE.EDU (Mark P. Jones)
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Message-ID: <1992Nov12.162725.25836@cs.yale.edu>
  6. Keywords: lazy backtracking Gofer
  7. Sender: news@cs.yale.edu (Usenet News)
  8. Nntp-Posting-Host: chickadee.systemsz.cs.yale.edu
  9. Organization: Yale University, Department of Computer Science, New Haven, CT
  10. References: <TMB.92Nov12122350@arolla.idiap.ch>
  11. Date: Thu, 12 Nov 1992 16:27:25 GMT
  12. Lines: 64
  13.  
  14. Commenting on the implementation of a strange successor function, the fact
  15. that it appears to run in space proportional to n, the fact that actually
  16. it only uses constant space in an implementation of SML and the fact that
  17. one implementation of Haskell seems to have problems with this, Thomas M.
  18. Breuel says:
  19.  
  20. |  Let's nip this rumor in the bud:
  21.  
  22. Yes indeed.  Lazy languages do not have a problem with this either.  Here
  23. is what I got when I tried it with the latest version of Gofer:
  24.  
  25. |  ? :set +g
  26. |  ? ss 100000 where ss n = head [x|x<-[0..], x>n]
  27. |  {{Gc:98065}}{{Gc:98065}}{{Gc:98064}}{{Gc:98064}}
  28. |  {{Gc:98064}}{{Gc:98064}}{{Gc:98064}}{{Gc:98064}}
  29. |  100001
  30. |  (600024 reductions, 800039 cells, 8 garbage collections)
  31. |  ?
  32.  
  33. The first line tells the garbage collector to print out the amount of space
  34. reclaimed after each collection; these are the figures in the {{Gc:...}}
  35. lines in the middle.  Certainly looks like constant space use to me.
  36.  
  37. |  It only gives "FP a bad name" if you intepret this naively. The
  38. |  performance of the SML implementation that I gave is actually quite
  39. |  good: unlike the Haskell version that the other person referred to, it
  40. |  uses only constant space.
  41.  
  42. The error reported for the Haskell implementation was "GC stack overflow".
  43. That sounds to me as though the garbage collector run out of stack space
  44. to me.  But the garbage collector algorithm has nothing to do with the
  45. strangesucc algorithm that you're looking at.  I'd be very suprised if
  46. the Haskell B. version doesn't actually run in constant space.  The
  47. backend of Gofer is based on the same G-machine technology that was  
  48. introduced in the implementation of LML and then Haskell B.
  49.  
  50. |  In general, in a lazy language, you are often at the mercy of the
  51. |  compiler to prove things about your code in order to obtain decent
  52. |  performance.
  53.  
  54. But in a lazy language, you don't need to do a lot of the standard
  55. optimisations like tail recursion elimination, moving constants outside
  56. loops etc.  Laziness gets you those things for free!  The only thing that
  57. Gofer ever `proves' about user programs is that they are type correct.
  58. It doesn't do any fancy optimisations or flow analysis at all.  Yet it
  59. still gets the constant space performance.  True, you might want to do
  60. these things for other purposes (strictness analysis is an example), but
  61. that is not the issue here.
  62.  
  63. |  Fortunately, in SML, you have better control over
  64. |  resources than in a lazy language,
  65.  
  66. Unfortunately, you will often have to write extra code to control
  67. those resources...
  68.  
  69. Yes, it is true that reasoning about the resources used by a program
  70. in a lazy language is more difficult than reasoning about a program in
  71. a strict language like SML.  But sometimes it's nice to be able to write
  72. code using a list without wondering whether I ought to write it with an
  73. explicit loop, or whether I should use a stream library instead, or ...
  74. I'm not criticising SML.  But Haskell (and lazy languages in general)
  75. have their nice points too.
  76.  
  77. Mark
  78.