#4296: The dreaded SkolemOccurs problem
---------------------------------+------------------------------------------
Reporter: simonpj | Owner: simonpj
Type: bug | Status: new
Priority: normal | Milestone: 7.4.1
Component: Compiler | Version: 6.12.3
Keywords: | Testcase:
indexed-types/should_compile/Simple20
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
Comment(by daniel.is.fischer):
It's the second part in !SkolemOccursLoop, which is the problem.
{{{
Judging from the output for small context stacks, what happens is:
We have
type instance G (S x, y) = S (G (x,y))
and the context
(G (S a,a) ~ a)
Generally, a context of the form
G (S a_n, S^n a_n) ~ a_n
By the type instance, that becomes
S (G (a_n, S^n a_n)) ~ a_n
Now, let a_(n+1) = G (a_n, S^n a_n) and replace a_n by (S a_(n+1)) in
this:
S (G (S a_(n+1), S^n (S a_(n+1)))) ~ S a_(n+1)
The outermost type constructor S can be removed and we can associate:
G (S a_(n+1), S^(n+1) a_(n+1)) ~ a_(n+1)
The type expression a_n contains 2^n occurrences of a = a_0, hence the
size
of the context grows exponentially.
The above takes two stack slots, so size is ~ 2^(stack_depth/2).
}}}
That alone would fail hard with a large enough context stack.
What makes it fail sooner, however, is the pretty-printing. According to a
couple of `+RTS -hT` profiles, `Pretty.TextBeside` takes about 90% of the
heap at its peak.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4296#comment:6>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
