selector thunks not working? space leak in standard example

[tullsen@…]

I thought that GHC evaluates "THUNK_SELECTORS" and thus eliminates the space leak in this infamous example [Hughes83][Wadler87][Sparud93]:

module Main where

surprise xs = b1 ++ [0,0] ++ b2
              where
              (b1,b2) = break (==0) xs

strictFromTo :: Int -> Int -> [Int]
strictFromTo i m = takeWhile (<= m) $ strictFrom i

strictFrom :: Int -> [Int]
strictFrom x = let x' = x + 1 in seq x' $ x' : strictFrom x'
        
main = print (length $ surprise $ strictFromTo (-1000000) 1)
       -- space leak, w/ or w/o optimization
main2 = print (length $ strictFromTo (-1000000) 1)
       -- runs in constant space, w/ or w/o optimization

However, this program does not run in constant space, even with -O2. I get the same results on

GHC6.6 Mac OS X Intel GHC6.2.1 Linux Intel GHC6.4.1 Linux Intel

[igloo]

I thought we already had a bug report about this, but I can't find it now.

As I recall, GHC does implement an optimisation designed to fix this leak, but it only looks down the thunk/selector chain to a bounded depth before bailing out, and thunks/selectors are created too fast. We have an idea of how it could be fixed, but haven't implemented it yet.

[simonmar]

Patch attached. I'm not going to push this until after 6.8.1, as it needs plenty of testing. For 6.8.1 I'm going to simply bump the depth limit for selector thunks, which also makes the example run in constant space, though more slowly.

[simonmar]

Now pushed, don't merge to the branch.

Mon Sep 17 16:18:34 BST 2007  Simon Marlow <simonmar@microsoft.com>
  * FIX #1038: failure of selector-thunk machinery to do its job

and a couple of subsequent fixes.