Why is there a space leak here?

[S. Alexander Jacobson]

On 6 Jun 2001, Carl R. Witty wrote:

> "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'm not clear why you can't in general notice that you are using
more space after function application than before.  I it hard to see why a
program couldn't do the analysis I just did on foldl.

You could accumulate statistics on funtions that increase/decrease space
used at runtime and evaluate those that do reduce space used...

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

You are trading off the likelihood that an exploding expression contains a
bottom against the liklihood that the programmer would prefer the
exploding expression not to explode.  Much of this type of work can be
done as test-time warnings....

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

I don't think I understood this.  Can you clarify?


-Alex-

___________________________________________________________________
S. Alexander Jacobson                   Shop.Com
1-646-638-2300 voice                    The Easiest Way To Shop (sm)