conservative optimizations

[Alexei Kitaev]

Dear GHC team,

I have observed a space leak in a simple program compiled with -O
option. The problem is to compute the "Fibonacci rabbit sequence":
[1,0,1,1,0,1,0,1,1,0,1,1,0,...] see e.g., this Haskell Cafe discussion:
http://www.haskell.org/pipermail/haskell-cafe/2007-November/034236.html
I like this problem because I studied the spectrum of the Schrodinger
operator defined by this sequence a while ago. Anyway, here are two
slightly different programs that compute the rabbit sequence:

-- Version 1: O(n) time, O(n) space

rs :: [Int]
rs = 1: tail [x | r <- rs, x <- f r]
  where
    f 0 = [1]
    f 1 = [1,0]

main :: IO ()
main = print $ take 100 rs

-- Version 2: O(n) time, O(log n) space

rs :: () -> [Int]
rs () = 1: tail [x | r <- rs(), x <- f r]
  where
    f 0 = [1]
    f 1 = [1,0]

-- test of memory usage
main :: IO ()
main = print $ rs() !! (10^8)

When the second program is compiled with -O flag (using GHC-6.10.4 or
the latest version, 6.13.20091125), it eats up a lot of memory. After
some web searching and experimentation, I found that the space leak can
be fixed by compiling with -fno-full-laziness and inserting
{-# NOINLINE rs #-}
However, I still have a few of questions:

1) Why would inlining introduce a space leak? This looks like a compiler
bug to me.

2) Is there a set of "safe" or, if this is a better word, "conservative"
optimizations that never increase the running time or space usage more
than by a constant factor? This leads to another question: relative to
what? I understand that prescribing the exact evaluation order and other
details would be impractical, but is it possible to define *some*
aspects of the program behavior that would allow the programmer to
guarantee the correct asymptotic efficiency?

Thank you,
Alexei Kitaev