🚀 go-pugleaf

Commenting on the implementation of a strange successor function, the fact
that it appears to run in space proportional to n, the fact that actually
it only uses constant space in an implementation of SML and the fact that
one implementation of Haskell seems to have problems with this, Thomas M.
Breuel says:

|  Let's nip this rumor in the bud:

Yes indeed.  Lazy languages do not have a problem with this either.  Here
is what I got when I tried it with the latest version of Gofer:

|  ? :set +g
|  ? ss 100000 where ss n = head [x|x<-[0..], x>n]
|  {{Gc:98065}}{{Gc:98065}}{{Gc:98064}}{{Gc:98064}}
|  {{Gc:98064}}{{Gc:98064}}{{Gc:98064}}{{Gc:98064}}
|  100001
|  (600024 reductions, 800039 cells, 8 garbage collections)
|  ?

The first line tells the garbage collector to print out the amount of space
reclaimed after each collection; these are the figures in the {{Gc:...}}
lines in the middle.  Certainly looks like constant space use to me.

|  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.

The error reported for the Haskell implementation was "GC stack overflow".
That sounds to me as though the garbage collector run out of stack space
to me.  But the garbage collector algorithm has nothing to do with the
strangesucc algorithm that you're looking at.  I'd be very suprised if
the Haskell B. version doesn't actually run in constant space.  The
backend of Gofer is based on the same G-machine technology that was  
introduced in the implementation of LML and then Haskell B.

|  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.

But in a lazy language, you don't need to do a lot of the standard
optimisations like tail recursion elimination, moving constants outside
loops etc.  Laziness gets you those things for free!  The only thing that
Gofer ever `proves' about user programs is that they are type correct.
It doesn't do any fancy optimisations or flow analysis at all.  Yet it
still gets the constant space performance.  True, you might want to do
these things for other purposes (strictness analysis is an example), but
that is not the issue here.

|  Fortunately, in SML, you have better control over
|  resources than in a lazy language,

Unfortunately, you will often have to write extra code to control
those resources...

Yes, it is true that reasoning about the resources used by a program
in a lazy language is more difficult than reasoning about a program in
a strict language like SML.  But sometimes it's nice to be able to write
code using a list without wondering whether I ought to write it with an
explicit loop, or whether I should use a stream library instead, or ...
I'm not criticising SML.  But Haskell (and lazy languages in general)
have their nice points too.

Mark