home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1348 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  2.4 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: 11 Nov 92 10:41:19
  6. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  7.     Perceptive)
  8. Lines: 45
  9. Message-ID: <TMB.92Nov11104119@arolla.idiap.ch>
  10. References: <1992Nov10.164456.18062@email.tuwien.ac.at>
  11. Reply-To: tmb@idiap.ch
  12. NNTP-Posting-Host: arolla.idiap.ch
  13. In-reply-to: ulrich@mips.complang.tuwien.ac.at's message of Tue, 10 Nov 1992 16:44:56 GMT
  14.  
  15. In article <1992Nov10.164456.18062@email.tuwien.ac.at> ulrich@mips.complang.tuwien.ac.at (Ulrich Neumerkel E185/1 +43158801/4477) writes:
  16.  
  17.    In many textbooks and papers about functional languages it is suggested
  18.    that lazy evaluation allows to implement backtracking by representing
  19.    the sequence of solutions by an appropriate datastructure which is
  20.    generated in a lazy manner. Is seems however, that such an encoding,
  21.    although conceptually elegant, requires space proportional to the
  22.    number of choices already considered.
  23.  
  24.    [...]
  25.  
  26.    strangesucc n =    hd [x|x<-[0..];x>n];
  27.  
  28.    This program should run in constant space and linear time [1].
  29.    However, for the implementations I tried, it turns out that the program
  30.    seems to run in linear space! For a small n as 10000 the program aborts
  31.    due to memory problems. Also a rewriting of the program to encode list
  32.    comprehensions explicitly did not yield the desired result.
  33.  
  34.    Is there ANY implementation of a lazy functional language to execute
  35.    the program above in an efficient manner (i.e. in constant space)?
  36.  
  37. There should be no problem with that in principle. For example, the
  38. following program, using a lazy streams library in SML, only requires
  39. constant space (3397288 bytes). Of course, it garbage collects a
  40. lot...
  41.  
  42.   - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
  43.   
  44.   [Major collection... 21% used (3397260/15733684), 1920 msec]
  45.   
  46.   [Major collection... 21% used (3397288/15730836), 1910 msec]
  47.   
  48.   [Major collection... 21% used (3397288/15730948), 1920 msec]
  49.   
  50.   [Major collection... 21% used (3397288/15730888), 1920 msec]
  51.   
  52.   [Major collection... 21% used (3397288/15730888), 1910 msec]
  53.   val it = 1000001 : int
  54.   -
  55.  
  56. In general, I think that backtracking is better expressed using
  57. callcc; is there some equivalent to callcc in lazy languages?
  58.  
  59.                     Thomas.
  60.