🚀 go-pugleaf

Someone wrote:

anon> strangesucc n =	hd [x|x<-[0..];x>n];
anon> [this runs out of memory and uses space linear in n]

I replied that there is no reason why this should use space linear in n:

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

In article 18783@eua.ericsson.se, joe@erix.ericsson.se (Joe Armstrong) writes:
joe> 
joe> Wonderfull  !!
joe> 
joe> This is the kind of stuff that gives FP a bad name :-)

It only gives "FP a bad name" if you intepret this naively. The
performance of the SML implementation that I gave is actually quite
good: unlike the Haskell version that the other person referred to, it
uses only constant space. And, in my experience, memory management
overhead is significantly less than for similar code in CommonLisp or
C++.

Note also that the GC was deliberately configured to run frequently in
this example so that you can see how much memory is actually used at
various points during the computation.

joe> Is their a transformation system which can prove that
joe> strangesucc x == x + 1 ?

In article <lg3071INN8m1@exodus.Eng.Sun.COM> staffan@chivas.Eng.Sun.COM (Staffan Liljegren) writes:
staffan> So it's not only SML that has these problems. So what are
staffan> some better mechanisms for representing backtracking OR how
staffan> can You circumvent this problem ?

Let's nip this rumor in the bud: SML has no problem with this
construct. Streams are a lazy data structures, and you pay a certain
price for that. Yes, the compiler might be able to figure out in some
cases that it optimize away this loop, but I certainly don't expect it
to in more complex cases.

In general, in a lazy language, you are often at the mercy of the
compiler to prove things about your code in order to obtain decent
performance.  Fortunately, in SML, you have better control over
resources than in a lazy language, so if the Stream data structures
are too inefficient for your purposes (which is actually only rarely
the case), you can choose alternative constructs based on callcc or
tail recursion instead and be more certain about what resource
requirements your program will actually have.

					Thomas.