🚀 go-pugleaf

In article <1992Nov12.162725.25836@cs.yale.edu> jones-mark@CS.YALE.EDU (Mark P. Jones) writes:
>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.

>[...]

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

The Haskell B. (and LML) implementations have (or had) some
interesting space leaks (as Dave Wakeling's profiler pointed out).
One of these was due to not "black-holing" closures when they were
entered (so retaining space if arguments to the original closure
became dead before the closure was fully evaluated).  It sounds as if
this may be the problem reported with the Haskell B implementation.
The most recent implementation has compiler flags to fix the problems
which Dave Wakeling reported, but I think they're disabled by default
(black-holing costs time, for instance, which you may not want to
spend).

Most functional language implementations that I know in detail (strict
or non-strict) have, or have had, significant space-leak problems.
I'm sure the same is true of Lisp systems (though they may be
sufficiently mature that they've solved most of the problems), and
I've had space leaks in C (though that was generally my fault).  If
you have dynamically allocated memory (stack or heap), then you need
to control it carefully to avoid leaks.  If the memory is managed
implicitly, then the compiler has to take care never to retain space
unnecessarily.  At the moment we still seem to be discovering ways in
which space can be lost, perhaps because they're not all written down,
and they're not all obvious.

To reiterate the point, this is an *implementation* issue, NOT a
language issue.  For what it's worth, the new Glasgow Haskell compiler
has no problem with strangesucc 10000000.  It always "black-holes"
entered closures, and should never retain dead values on the stack.

Kevin
-- 
Dept. of Computing Science, Glasgow University.    E-mail: kh@dcs.glasgow.ac.uk

This Signature Intentionally segmentation fault