home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1355 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  2.4 KB
  1. Path: sparky!uunet!noc.near.net!hri.com!spool.mu.edu!agate!doc.ic.ac.uk!uknet!rook.ukc.ac.uk!larch.ukc.ac.uk!rej
  2. From: rej@ukc.ac.uk (R.E.Jones)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Keywords: lazy evaluation, comprehensions, backtracking
  6. Message-ID: <42@larch.ukc.ac.uk>
  7. Date: 12 Nov 92 14:47:22 GMT
  8. References: <1992Nov10.164456.18062@email.tuwien.ac.at>
  9. Reply-To: rej@ukc.ac.uk (R.E.Jones)
  10. Organization: Computing Lab, University of Kent at Canterbury, UK.
  11. Lines: 40
  12. Nntp-Posting-Host: larch.ukc.ac.uk
  13.  
  14. In article <1992Nov10.164456.18062@email.tuwien.ac.at> ulrich@mips.complang.tuwien.ac.at writes:
  15. >
  16. >strangesucc n =    hd [x|x<-[0..];x>n];
  17. >
  18. >This program should run in constant space and linear time [1].
  19. >However, for the implementations I tried, it turns out that the program
  20. >seems to run in linear space! For a small n as 10000 the program aborts
  21. >due to memory problems. Also a rewriting of the program to encode list comprehensions explicitly did not yield the desired result.
  22. >
  23. >Is there ANY implementation of a lazy functional language to execute
  24. >the program above in an efficient manner (i.e. in constant space)?
  25. >-- 
  26. >Ulrich Neumerkel, ulrich@dec4.wu-wien.ac.at ulrich@mips.complang.tuwien.ac.at
  27. >TU-Wien, Vienna University of Technology, +431 58801 4477 fax +431 5057838
  28. >Institut fuer Computersprachen E185/1 Argentinierstr.8/4, A-1040 Wien Austria
  29.  
  30.  
  31. I've tried this on an implementation based on the G-machine. My machine
  32. uses the blackholing technique to avoid space leaks that I describe in [1].
  33. I translate list comprehensions to their equivalent using foldr, map and
  34. concat; for example see [2].
  35. I have no problem with this function: it runs in constant space (262 words
  36. of heap space if you want to compare figures with those give in [1]).
  37.  
  38. [1] Richard E. Jones. `Tail recursion without space leaks', Journal of 
  39.     Functional Programming 2(1), 73--79, January 1992.
  40.     
  41. [2] Richard Bird & Phil Wadler. `Introduction to Functional Programming', 
  42.     Prentice Hall, 1988. Page 63.
  43.  
  44.  
  45. Richard Jones
  46.  
  47. ===============================================================================
  48.  
  49. Computing Laboratory                email: rej@ukc.ac.uk
  50. University of Kent at Canterbury        Telephone: 0227 764000 ext.7550
  51. Canterbury, CT2 7NF, U.K.            FAX: 0227 762811
  52.  
  53. ===============================================================================
  54.