home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1345 < prev    next >
Encoding:
Text File  |  1992-11-10  |  2.3 KB  |  50 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!email!mips.complang.tuwien.ac.at!ulrich
  3. From: ulrich@mips.complang.tuwien.ac.at (Ulrich Neumerkel E185/1 +43158801/4477)
  4. Subject: Is efficient backtracking feasible in functional languages?
  5. Message-ID: <1992Nov10.164456.18062@email.tuwien.ac.at>
  6. Keywords: lazy evaluation, comprehensions, backtracking
  7. Sender: news@email.tuwien.ac.at
  8. Nntp-Posting-Host: mips.complang.tuwien.ac.at
  9. Reply-To: ulrich@mips.complang.tuwien.ac.at
  10. Organization: Technische Universitaet Wien, Institut fuer Computersprachen
  11. Date: Tue, 10 Nov 1992 16:44:56 GMT
  12. Lines: 36
  13.  
  14.  
  15. In many textbooks and papers about functional languages it is suggested
  16. that lazy evaluation allows to implement backtracking by representing
  17. the sequence of solutions by an appropriate datastructure which is
  18. generated in a lazy manner. Is seems however, that such an encoding,
  19. although conceptually elegant, requires space proportional to the
  20. number of choices already considered.
  21.  
  22. Below is such a backtracking program `strangesucc' that computes the
  23. successor of a number by searching through all natural numbers and
  24. selecting the first solution found. This program here is a little
  25. overkill. It serves only as an example for the problems I
  26. encountered in more complex backtracking programs. Take a more
  27. complex condition and the program does make sense.
  28.  
  29. strangesucc n =    hd [x|x<-[0..];x>n];
  30.  
  31. This program should run in constant space and linear time [1].
  32. However, for the implementations I tried, it turns out that the program
  33. seems to run in linear space! For a small n as 10000 the program aborts
  34. due to memory problems. Also a rewriting of the program to encode list comprehensions explicitly did not yield the desired result.
  35.  
  36. Is there ANY implementation of a lazy functional language to execute
  37. the program above in an efficient manner (i.e. in constant space)?
  38.  
  39. Thank You, Ulrich
  40.  
  41. [1] more precicely in log n space and n log n time, if we consider
  42. numbers of arbitrary magnitude.
  43.  
  44. PS: Note that backtracking as implemented in Prolog does not have
  45. such problems.
  46. -- 
  47. Ulrich Neumerkel, ulrich@dec4.wu-wien.ac.at ulrich@mips.complang.tuwien.ac.at
  48. TU-Wien, Vienna University of Technology, +431 58801 4477 fax +431 5057838
  49. Institut fuer Computersprachen E185/1 Argentinierstr.8/4, A-1040 Wien Austria
  50.