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

[Joachim Breitner]

Hi,

last = foldl (\_ x -> x) (errorEmptyList "last")
(see http://git.haskell.org/ghc.git/blob/f44bbc83bab62f9a2d25e69d87c2b4af25318d52:/libraries/base/GHC/List.hs#l88)

not sure how contrived that is, but at least it’s real code in GHC-7.10.

Greetings,
Joachim


Am Freitag, den 20.02.2015, 11:13 +0200 schrieb Roman Cheplyaka:
> I'd be curious to see a (non-contrived) example.
> 
> On 20/02/15 09:05, David Feuer wrote:
> > Probably not. There's real code that depends on the current foldl semantics.
> > 
> > On Wed, Feb 18, 2015 at 10:40 AM, Joe Hillenbrand <joehillen at gmail.com> wrote:
> >> Is foldl = foldl' ever going to happen?
> >>
> >> On Tue, Feb 17, 2015 at 11:50 PM, Roman Cheplyaka <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.
> >>>
> >>> foldl (+) 0 would be an example of a laziness issue.
> >>>
> >>> If you want to specify which functions should or shouldn't be used in a
> >>> lazy context, take a look at polarity (see Harper's Practical
> >>> Foundations for Programming Languages). So you could say, for instance,
> >>> that it doesn't make sense to use + in a lazy context; that'd eliminate
> >>> half the cases of laziness-induced memory leaks in practice.
> >>>
> >>> If instead you want to impose some upper bound on the memory consumption
> >>> without caring about specific cases, then see this ICFP'12 paper:
> >>> http://www.dcc.fc.up.pt/~pbv/AALazyExtended.pdf
> >>>
> >>> On 18/02/15 07:04, Eugene Kirpichov wrote:
> >>>> Hello haskell-cafe,
> >>>>
> >>>> Let me repost here a question I posted to cstheory stackexchange - in
> >>>> hopes that there are more type theory experts here.
> >>>>
> >>>>
> >>>> http://cstheory.stackexchange.com/questions/29518/type-systems-preventing-laziness-related-memory-leaks
> >>>>
> >>>> Perhaps the main source of performance problems in Haskell is when a
> >>>> program inadvertently builds up a thunk of unbounded depth - this causes
> >>>> both a memory leak and a potential stack overflow when evaluating. The
> >>>> classic example is defining sum = foldr (+) 0 in Haskell.
> >>>>
> >>>> Are there any type systems which statically enforce lack of such thunks
> >>>> in a program using a lazy language?
> >>>>
> >>>> Seems like this should be on the same order of difficulty as proving
> >>>> other static program properties using type system extensions, e.g. some
> >>>> flavors of thread safety or memory safety.
> >>>
> >>> _______________________________________________
> >>> Haskell-Cafe mailing list
> >>> Haskell-Cafe at haskell.org
> >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> >>
> >>
> >>
> >> _______________________________________________
> >> Haskell-Cafe mailing list
> >> Haskell-Cafe at haskell.org
> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> >>
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

-- 
Joachim “nomeata” Breitner
  mail at joachim-breitner.de • http://www.joachim-breitner.de/
  Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150220/6e632720/attachment.sig>