[Haskell-beginners] Disappointing thought on Haskell -- a simple space leak on "insert" is hard bug to catch

[KC]

Hi:

Heinrich Apfelmus wrote:

"But in the expression,

   let x = "A String which uses a lot of memory"
       y = 12
   in snd (x,y+2)

we may not discard `x` just yet, because it still occurs in the expression
`snd (x,y+2)`. Of course, performing reduction step will turn this into
`y+2` and now the memory used by binding for `x` can be freed."


Wouldn't the compiler know how "snd" works and therefore know that the
first argument isn't needed?

Isn't the above the advantage of pure code - same inputs ~ same outputs?



On Tue, Aug 19, 2014 at 7:42 AM, Heinrich Apfelmus <
apfelmus at quantentunnel.de> wrote:

> Dimitri DeFigueiredo wrote:
>
>> Hi Heinrich,
>>
>> Thanks so much! :-)
>>
>> Wow! I was totally wrong on that one then. I got it that lazy evaluation
>> is the culprit here. Now, I am still a little uneasy about insert producing
>> a new version of the tree when it is not needed. Can't that come back to
>> bite me later depending on how I use it?
>>
>> In your explanation, you say that "the old path is usually not referenced
>> anywhere, and can be garbage collected immediately."
>> I am a little uneasy about the "usually". Could you expand on that? What
>> if it is? Could that happen? Or does that just imply a bigger constant?
>>
>
> First, note that a new version of the tree has to be created whenever the
> element you insert was not in the tree. Most likely, your "higher-up"
> algorithm that makes use of the tree structure doesn't treat these two
> cases too differently, so you probably have to think about the case where
> the tree is copied anyway.
>
> Second, you may want to look up on how lazy evaluation, respectively
> *graph reduction* work. This will answer your questions. For instance, the
> new code that you wrote implicitly builds a new version of the tree as well
> (building a tower of expressions of the form `>>= \r -> return $ MkTree a x
> r`) but discards it level by level when it turns out that the end result is
> `Nothing`. Without an understanding of the evaluation model, you will
> always feel uneasy.
>
> The basic tenet of garbage collection is that the binding for any name
> which does not occur in the current expression can be discard. For
> instance, in the expression
>
>    let x = "A String which uses a lot of memory"
>        y = 12
>    in y + 2
>
> we can safely discard the name `x` and its value, as the name `x` does not
> occur in the expression `y + 2`.
>
> But in the expression,
>
>    let x = "A String which uses a lot of memory"
>        y = 12
>    in snd (x,y+2)
>
> we may not discard `x` just yet, because it still occurs in the expression
> `snd (x,y+2)`. Of course, performing reduction step will turn this into
> `y+2` and now the memory used by binding for `x` can be freed.
>
> Note that the runtime may choose to wait some time before freeing the
> associated memory. In fact, at periodic intervals, the runtime will stop
> the current evaluation and instead perform a process called "garbage
> collection", where it looks for all variable names and frees the memory of
> those that are no longer needed.
>
> A "space leak" generally refers to the situation where a name is no longer
> needed but still occurs in the expression to be evaluated. This is very
> much like the `x` in the second example: it's "not really needed", because
> we humans know that `snd` doesn't use it, but it's still written there, so
> the runtime can't throw it away.
>
>
>
> Best regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 

--

Sent from an expensive device which will be obsolete in a few months! :D
Casey
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140819/8824c9fc/attachment.html>