Why is there a space leak here?
S. Alexander Jacobson
alex@shop.com
Fri, 8 Jun 2001 10:41:48 -0400 (Eastern Daylight Time)
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)