🚀 go-pugleaf

In article <1992Nov10.164456.18062@email.tuwien.ac.at> ulrich@mips.complang.tuwien.ac.at (Ulrich Neumerkel E185/1 +43158801/4477) writes:

   In many textbooks and papers about functional languages it is suggested
   that lazy evaluation allows to implement backtracking by representing
   the sequence of solutions by an appropriate datastructure which is
   generated in a lazy manner. Is seems however, that such an encoding,
   although conceptually elegant, requires space proportional to the
   number of choices already considered.

   [...]

   strangesucc n =	hd [x|x<-[0..];x>n];

   This program should run in constant space and linear time [1].
   However, for the implementations I tried, it turns out that the program
   seems to run in linear space! For a small n as 10000 the program aborts
   due to memory problems. Also a rewriting of the program to encode list
   comprehensions explicitly did not yield the desired result.

   Is there ANY implementation of a lazy functional language to execute
   the program above in an efficient manner (i.e. in constant space)?

There should be no problem with that in principle. For example, the
following program, using a lazy streams library in SML, only requires
constant space (3397288 bytes). Of course, it garbage collects a
lot...

  - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
  
  [Major collection... 21% used (3397260/15733684), 1920 msec]
  
  [Major collection... 21% used (3397288/15730836), 1910 msec]
  
  [Major collection... 21% used (3397288/15730948), 1920 msec]
  
  [Major collection... 21% used (3397288/15730888), 1920 msec]
  
  [Major collection... 21% used (3397288/15730888), 1910 msec]
  val it = 1000001 : int
  -

In general, I think that backtracking is better expressed using
callcc; is there some equivalent to callcc in lazy languages?

					Thomas.