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)