[Haskell-cafe] an evil type hangs GHC

[wren ng thornton]

On 11/12/10 4:53 PM, Ryan Ingram wrote:
>> From http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/bugs.html#bugs-ghc:
>
> GHC's inliner can be persuaded into non-termination using the standard
> way to encode recursion via a data type:

More specifically, since your bad2 does not look recursive, the inliner 
will get inline happy and apply the definition of bad1, but then it'll 
see a constant case match that it can reduce statically, and <loop>


{ okay, let's start with bad1 }

     bad1 b@(C f) = f b

{ mmm, tasty tasty sugar }

     bad1 = \b -> case b of C f -> f b

{ ha, dare you to optimize that further }

{ okay, now let's co compile bad2 }

     bad2 = bad1 (C bad1)

{ oh look, it's nonrecursive so let's start inlining }

     bad2 = (\b -> case b of C f -> f b) (C bad1)

{ oh look, an application we can evaluate statically }

     bad2 = let b = (C bad1) in case b of C f -> f b

{ meh, let's ignore sharing for now }

     bad2 = case (C bad1) of C f -> f (C bad1)

{ oh look, a case analysis we can evaluate statically }

     bad2 = let f = bad1 in f (C bad1)

{ oh look, f is only used once so we can substitute the let }
{ and if we didn't ignore sharing before, then we'd see that b is only 
used once now, so we could substitute that let too }

     bad2 = bad1 (C bad1)

{ oh look, it's nonrecursive so let's start inlining }

-- 
Live well,
~wren