home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1358 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  3.0 KB
  1. Path: sparky!uunet!ukma!usenet.ins.cwru.edu!agate!doc.ic.ac.uk!uknet!glasgow!kh
  2. From: kh@dcs.glasgow.ac.uk (Kevin Hammond)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Keywords: lazy backtracking Gofer
  6. Message-ID: <BxM80r.1Hu@dcs.glasgow.ac.uk>
  7. Date: 12 Nov 92 18:14:49 GMT
  8. References: <TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu>
  9. Organization: Computing Sci, Glasgow Univ, Scotland
  10. Lines: 52
  11.  
  12. In article <1992Nov12.162725.25836@cs.yale.edu> jones-mark@CS.YALE.EDU (Mark P. Jones) writes:
  13. >Commenting on the implementation of a strange successor function, the fact
  14. >that it appears to run in space proportional to n, the fact that actually
  15. >it only uses constant space in an implementation of SML and the fact that
  16. >one implementation of Haskell seems to have problems with this, Thomas M.
  17. >Breuel says:
  18. >
  19. >|  Let's nip this rumor in the bud:
  20. >
  21. >Yes indeed.  Lazy languages do not have a problem with this either.
  22.  
  23. >[...]
  24.  
  25. >But the garbage collector algorithm has nothing to do with the
  26. >strangesucc algorithm that you're looking at.  I'd be very suprised if
  27. >the Haskell B. version doesn't actually run in constant space.
  28. > The backend of Gofer is based on the same G-machine technology that was  
  29. >introduced in the implementation of LML and then Haskell B.
  30.  
  31. The Haskell B. (and LML) implementations have (or had) some
  32. interesting space leaks (as Dave Wakeling's profiler pointed out).
  33. One of these was due to not "black-holing" closures when they were
  34. entered (so retaining space if arguments to the original closure
  35. became dead before the closure was fully evaluated).  It sounds as if
  36. this may be the problem reported with the Haskell B implementation.
  37. The most recent implementation has compiler flags to fix the problems
  38. which Dave Wakeling reported, but I think they're disabled by default
  39. (black-holing costs time, for instance, which you may not want to
  40. spend).
  41.  
  42. Most functional language implementations that I know in detail (strict
  43. or non-strict) have, or have had, significant space-leak problems.
  44. I'm sure the same is true of Lisp systems (though they may be
  45. sufficiently mature that they've solved most of the problems), and
  46. I've had space leaks in C (though that was generally my fault).  If
  47. you have dynamically allocated memory (stack or heap), then you need
  48. to control it carefully to avoid leaks.  If the memory is managed
  49. implicitly, then the compiler has to take care never to retain space
  50. unnecessarily.  At the moment we still seem to be discovering ways in
  51. which space can be lost, perhaps because they're not all written down,
  52. and they're not all obvious.
  53.  
  54. To reiterate the point, this is an *implementation* issue, NOT a
  55. language issue.  For what it's worth, the new Glasgow Haskell compiler
  56. has no problem with strangesucc 10000000.  It always "black-holes"
  57. entered closures, and should never retain dead values on the stack.
  58.  
  59. Kevin
  60. -- 
  61. Dept. of Computing Science, Glasgow University.    E-mail: kh@dcs.glasgow.ac.uk
  62.  
  63. This Signature Intentionally segmentation fault
  64.