home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1352 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  3.1 KB

  1. Path: sparky!uunet!snorkelwacker.mit.edu!ai-lab!life.ai.mit.edu!tmb
  2. From: tmb@arolla.idiap.ch (Thomas M. Breuel)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Date: 12 Nov 92 12:23:50
  6. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  7.     Perceptive)
  8. Lines: 62
  9. Message-ID: <TMB.92Nov12122350@arolla.idiap.ch>
  10. References: <1992Nov11.171742.18783@eua.ericsson.se> <lg3071INN8m1@exodus.Eng.Sun.COM>
  11. Reply-To: tmb@idiap.ch
  12. NNTP-Posting-Host: arolla.idiap.ch
  13. In-reply-to: staffan@chivas.Eng.Sun.COM's message of 11 Nov 92 21:53:37 GMT
  14.  
  15. Someone wrote:
  16.  
  17. anon> strangesucc n =    hd [x|x<-[0..];x>n];
  18. anon> [this runs out of memory and uses space linear in n]
  19.  
  20. I replied that there is no reason why this should use space linear in n:
  21.  
  22. tmb> - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
  23. tmb> 
  24. tmb> [Major collection... 21% used (3397260/15733684), 1920 msec]
  25. tmb> 
  26. tmb> [Major collection... 21% used (3397288/15730836), 1910 msec]
  27. tmb> 
  28. tmb> [Major collection... 21% used (3397288/15730948), 1920 msec]
  29. tmb> 
  30. tmb> [Major collection... 21% used (3397288/15730888), 1920 msec]
  31. tmb> 
  32. tmb> [Major collection... 21% used (3397288/15730888), 1910 msec]
  33. tmb> val it = 1000001 : int
  34. tmb> -
  35.  
  36. In article 18783@eua.ericsson.se, joe@erix.ericsson.se (Joe Armstrong) writes:
  37. joe> 
  38. joe> Wonderfull  !!
  39. joe> 
  40. joe> This is the kind of stuff that gives FP a bad name :-)
  41.  
  42. It only gives "FP a bad name" if you intepret this naively. The
  43. performance of the SML implementation that I gave is actually quite
  44. good: unlike the Haskell version that the other person referred to, it
  45. uses only constant space. And, in my experience, memory management
  46. overhead is significantly less than for similar code in CommonLisp or
  47. C++.
  48.  
  49. Note also that the GC was deliberately configured to run frequently in
  50. this example so that you can see how much memory is actually used at
  51. various points during the computation.
  52.  
  53. joe> Is their a transformation system which can prove that
  54. joe> strangesucc x == x + 1 ?
  55.  
  56. In article <lg3071INN8m1@exodus.Eng.Sun.COM> staffan@chivas.Eng.Sun.COM (Staffan Liljegren) writes:
  57. staffan> So it's not only SML that has these problems. So what are
  58. staffan> some better mechanisms for representing backtracking OR how
  59. staffan> can You circumvent this problem ?
  60.  
  61. Let's nip this rumor in the bud: SML has no problem with this
  62. construct. Streams are a lazy data structures, and you pay a certain
  63. price for that. Yes, the compiler might be able to figure out in some
  64. cases that it optimize away this loop, but I certainly don't expect it
  65. to in more complex cases.
  66.  
  67. In general, in a lazy language, you are often at the mercy of the
  68. compiler to prove things about your code in order to obtain decent
  69. performance.  Fortunately, in SML, you have better control over
  70. resources than in a lazy language, so if the Stream data structures
  71. are too inefficient for your purposes (which is actually only rarely
  72. the case), you can choose alternative constructs based on callcc or
  73. tail recursion instead and be more certain about what resource
  74. requirements your program will actually have.
  75.  
  76.                     Thomas.
  77.