Re: Why is there a space leak here?
"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
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)
At 10:41 AM 6/8/2001 -0400, S. Alexander Jacobson wrote:
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?
I believe I know what he's talking about. The example I've read about this technique is random-number generators. Because typical generators will need a state (the seed), they can be awkward to use in functional languages. Instead, you can just generate an infinite list of the random numbers, and extract them from that list lazily. Specifically, what he's talking about is the fact that a function like "Natural -> a" corresponds to a list where all the possible results for each number are stored in the corresponding position in the list. If you generate that list lazily, and then access it, each element will only be computed once (the compiler/interpreter takes care of this in a very natural way). But if you do this, the program will (or can) grow as more elements get computed. Am I making sense? Salutaciones, JCAB --------------------------------------------------------------------- Juan Carlos "JCAB" Arevalo Baeza | http://www.roningames.com Senior Technology programmer | mailto:jcab@roningames.com Ronin Entertainment | ICQ: 10913692 (my opinions are only mine) JCAB's Rumblings: http://www.metro.net/jcab/Rumblings/html/index.html
participants (3)
-
cwitty＠newtonlabs.com -
Juan Carlos Arevalo Baeza -
S. Alexander Jacobson