[Haskell-cafe] Type systems preventing laziness-related memory leaks?

[Eugene Kirpichov]

On Fri Feb 20 2015 at 1:23:25 AM Roman Cheplyaka <roma at ro-che.info> wrote:

> On 20/02/15 07:26, Eugene Kirpichov wrote:
> >
> >
> > On Tue Feb 17 2015 at 11:50:20 PM Roman Cheplyaka <roma at ro-che.info
> > <mailto:roma at ro-che.info>> wrote:
> >
> >     Note that foldr (+) 0 has nothing to do with laziness — it's eager.
> Its
> >     problem is that it's not tail-recursive.
> >
> > The problem is that when you say foldr (+) 0 [1, 2, 3, 4, 5] you build a
> > thunk "1 + (2 + (3 + (4 + (5 + 0))))", which has - let's call it "whnf
> > evaluation depth" of 4 (you need a stack of size 4 to evaluate it to
> whnf).
>
> This is not a thunk. These values would be pushed to the stack, but no
> thunks will be created.
>
> Just so that you have no doubts left, here's the STG code for foldr (+) 0:
>
> $wgo = \r srt:SRT:[] [w]
>   case w of _ {
>     [] -> 0;
>     : y ys ->
>       case y of _ {
>         I# x -> case $wgo ys of ww {
>           __DEFAULT -> +# [x ww];
>         };
>       };
>   };
>
> As you can see, there are no lets here, only cases.
>
Indeed - I guess the strictness analyzer did its job.
Nevertheless, the expression foldr (+) 0 [1..n] requires an evaluation
stack depth of n and I would like it to be uncompilable - I would like the
type of foldr (+) 0 to be "[Int] -> Int@\infty"


>
> Roman
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150220/f126a412/attachment.html>