Why is there a space leak here?

[Carl R. Witty]

"S. Alexander Jacobson" <alex@shop.com> writes:

> For example w/ foldl:
> 
> foldl + 0 [1..10000]
> foldl (+) ((+) 0 1) [2..10000]
> foldl (+) ((+) ((+) 0 1) 2) [3..10000]
> 
> Can't the implementation notice that each iteration leads to a
> larger closure and, if it is running out of space go ahead an just
> evaluate (+) 0 1?

It's complicated.  You can't (in general) know whether application of
a function will increase or decrease the space used.  If you were
running out of space, would you just search the whole unevaluated
program graph for reductions which somehow seemed "likely" to reduce
the space used?  Would you add such reduction nodes to some global
list at the time they were created?

> I realize that there is a risk of evaluating _|_ unnecessarily, but if you
> are otherwise going to run out of memory, you might as well give it a
> shot.
> 
> In practice, how often do you expect to see growing expressions that cover
> a _|_ that are not actually an error in any case?

It's certainly possible.

One portable way to implement a memoizing function in Haskell (if the
domain of the function is countable) is to lazily build a data
structure that contains the results of the function on every possible
argument.  Then you evaluate the portions of the data structure that
you need; the result on each argument is only evaluated once.  This
probably would count as a "growing expression", and it's certainly
possible that the function on some arguments would be bottom.

> Hunting down memory leaks is already so obscure, that you might as well
> take a shot at solving the problem automatically...
> 
> Alternatively, is there some magical way of warning about leaky
> expressions at compile time?  You don't have to ban them, but it would be
> nice if the programmer were aware of which parts of the code are likely to
> grow...

In general, this problem is uncomputable.  It might be possible to
come up with some useful approximation, but I bet that's a very
difficult research problem.

Carl Witty