[Haskell-cafe] Puzzling "Reduction stack overflow" error message

CASANOVA Juan Juan.Casanova at ed.ac.uk
Sun Jan 24 03:15:24 UTC 2021

Hello Haskell Cafe,

I almost feel guilty for posting this since I almost never read messages from this list. But I guess others do and do so because they want to so it's an asymmetry that is fine, and which probably won't be like that forever (I'll get to reading them again at a different stage of my life I'm feeling better). I also have very bad experience with asking "complex" Haskell questions in Stack Overflow, with people either not replying or replying stuff that indicates they did not understand the question.

Digression aside, I have encountered this error before and it is a nasty one, but this time I am just wildly puzzled by what it's trying to tell me.

This is part of a very large program (and I think the huge stack of types and instances is what is hiding the problem here), but I'll try to condense it into a small bit.

The following function I have is the one that throws the error:

resolve_to_constraints_metacnf :: SOMetaSignature -> SOMetaCNF -> Computation (Maybe SOMetaUnifSystem)
resolve_to_constraints_metacnf sig cnf = result
f1 = (ADDirect <$>) :: SOMetaliteral -> SOMetaUnifLiteral;
f2 = (f1 <$>) :: [SOMetaliteral] -> [SOMetaUnifLiteral];
f3 = (f2 <$>) :: [[SOMetaliteral]] -> [[SOMetaUnifLiteral]];
ucnf = f3 cnf :: [[SOMetaUnifLiteral]];
resolved = res_computeresolve SOResGreedyFactorH ucnf :: StateT uv Computation (Maybe SOMetaUnifSystem);
runstated = runStateT resolved (UnifVar 0);
result = fst <$> runstated

The error starts as follows:

Reduction stack overflow; size = 201
      When simplifying the following type: Eq OFunction

The rest is the standard for this type of errors.

OFunction does not appear explicitly on my function signature, but if we look at the definitions of SOMetaSignature, SOMetaCNF, SOMetaLiteral, SOMetaUnifLiteral and SOMetaUnifSystem, we see they are type aliases for parameterised types, all of which include OFunction as one of their parameters. Here's an example:

type SOMetaUnifLiteral = Literal (AtomDependant CAtomPF CTermF LambdaCNF SOPredicate OPredicate OFunction OVariable SOAMVariable SOMVariable UnifVariable)

(Yes, I know how tedious it is to have so many type parameters, tell me about it).

And perhaps also relevantly, this is the signature of res_computeresolve (which type checks):

res_computeresolve :: (ResLiteral l r mt, Heuristics h [Literal l] () (ResStep l) m) => h -> [[Literal l]] -> mt m (Maybe r)

(note, might be relevant, that ResLiteral requires mt to be a MonadTrans and MFunctor, which StateT, the type it gets instantiated to in the calling function, is. m gets instantiated to Computation which is a Monad I implemented myself (and works fine).)

Now, the natural thing to think is to track the Constraints to find which one is asking for an Eq OFunction and how that works. It definitely is a constraint that I use all over the place.

But, here is the puzzling thing. Eq OFunction is clearly implemented. OFunction is a really simple type. Here is the basic definition:

data OFunction = OFun Int Int deriving (Eq, Ord)

So, why is it having such a hard time proving Eq OFunction, if it is a really simple type with a derived instance of Eq (which has worked thus far without any issues)?

My suspicion is that the message is bugged, and the stack overflow is not on that specific instance, but rather on some type variable on a larger instance that it can never entirely instantiate no matter how many constraints it resolves. This is why I added those inline type signatures to the triple fmap, to try to help GHC know what the types should look like. But I am still getting the error, and I really don't know what else to do now.

Sorry for the long message, but since I don't know where the error is coming from, I wanted to give some context, and my entire program is tens of thousands of lines of codes by now...

I hope people are able to skim and find the relevant bit that tells them what's likely the stupid mistake I am making.

Thanks in advance,
The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20210124/ae791df9/attachment.html>

More information about the Haskell-Cafe mailing list