Context reduction stack overflow

[Esa Pulkkinen]

I'm using the ghc5 package (GHC 5.02.2) from Debian unstable.

I posted the following example (at the end of this mail) on
comp.lang.functional and had opinions that this is not valid Haskell 98
[due to "Eq (f (Rec f)) =>" constraint in the instance declaration], and
it was suggested I report this as a bug. I can understand why this would
be disallowed, although I'm not sure I understand how it follows from
the specification. [see 4.1.3 [contexts]; 4.3.1 [disallowing cyclic
superclass declarations in class dcls], and 4.3.2 [instance
declarations]].

However, regardless of whether I use -fallow-undecidable-instances
[similarly for -fglasgow-exts], I get the the following errors due to
mutually recursive instances:

Context reduction stack overflow; size = 21
Use -fcontext-stack20 to increase stack size to (e.g.) 20
    `Eq (Expr (Rec Expr))' arising from use of `==' at test.lhs:22
    `Eq (Rec Expr)' arising from use of `==' at test.lhs:22
    `Eq (Expr (Rec Expr))' arising from use of `==' at test.lhs:22
    `Eq (Rec Expr)' arising from use of `==' at test.lhs:22
    [SNIP COPIES]
    `Eq (Rec Expr)' arising from use of `==' at test.lhs:22
    `Eq (Expr (Rec Expr))' arising from use of `==' at test.lhs:22
    `Eq (Rec Expr)' arising from use of `==' at test.lhs:22
    `== at [Rec Expr]' arising from use of `==' at test.lhs:22

If the example was valid, then surely this error should not occur.  On
the other hand, if the example was not valid due to the constraint being
invalid, I think I should get an error already from the first instance
declaration, especially if neither -fallow-undecidable-instances nor
-fglasgow-exts was used.  Neither instance declaration produces an error
when used without the other using any combination of the compiler
options. It is somewhat awkward that this error occurs only when you use
instances that trigger the recursion, because you can never know from
your instance declarations whether you have this problem. This also
means that the instance declarations are not modular (since both are valid
independently, but their combination causes some expressions to become
invalid without a clear advance warning). And I cannot attribute this
problem to the use of the '==' symbol at line 22. [I'm aware of a
workaround though, i.e. higher-order equality type class.]

Hugs rejects this code when used with '+98' (complaining about illegal
Haskell 98 class constraint) and rejects it with '-98' (with a 'cutoff
limit/undecidable' error).

Here's the code:

>module Main where

import Prelude hiding (Rec) -- for Hugs

>data Rec f = In ! (f (Rec f))

>instance Eq (f (Rec f)) => Eq (Rec f) where -- HERE!
>         (In x) == (In y) = x == y

>data Expr a = App a a
>            | Var String

>instance Eq a => Eq (Expr a) where
>         (App x y) == (App x' y') = x == x' && y == y'
>         (Var x) == (Var y) = x == y
>         _ == _ = False

>e1 :: Rec Expr
>e1 = In (App (In (Var "x")) (In (Var "y")))

>main :: IO ()
>main = putStrLn (show (e1 == e1)) -- line 22

-- 
 Esa Pulkkinen