[GHC] #323: Exponential behaviour with type synonyms

[GHC]

#323: Exponential behaviour with type synonyms
--------------------------------------+-------------------------------------
  Reporter:  simonpj                  |          Owner:  simonpj 
      Type:  bug                      |         Status:  assigned
  Priority:  low                      |      Milestone:          
 Component:  Compiler (Type checker)  |        Version:  6.4.1   
  Severity:  normal                   |     Resolution:  None    
  Keywords:                           |             Os:  Unknown 
Difficulty:  Unknown                  |   Architecture:  Unknown 
--------------------------------------+-------------------------------------
Changes (by simonmar):

  * architecture:  => Unknown
  * difficulty:  => Unknown
  * version:  None => 6.4.1
  * os:  => Unknown

Old description:

> {{{
> You're quite right.  GHC has a simple but non-
> performant representation of type synonyms in types, so
> as to be able to generate good error messages,  In
> particular, the type
>
>         S t
>
> where S is a type synonym defined by 'type S a = s', is
> represented as
>
>         SynNote (S t) (s [t/a])
>
> That is, (S t) is represented by *both* its un-expanded
> and expanded form.
>
> The SynNote is ignored by unification, but the un-
> expanded form is useful for error messages.
> Unfortunately, t is duplicated, as you can see, and that
> leads to the behaviour you describe.
>
> I don't see myself fixing this soon, at least partly
> because I can't see an obvious way to fix it that doesn't
> lose error message behaviour.
>
> I'm going to open a SourceForge bug for it.  If anyone
> has good ideas, let me know.
>
> Simon
>
> | -----Original Message-----
> | From: glasgow-haskell-bugs-bounces at haskell.org
> [mailto:glasgow-haskell-bugs-
> | bounces at haskell.org] On Behalf Of Iavor Diatchki
> | Sent: 17 February 2005 01:27
> | To: glasgow-haskell-bugs at haskell.org
> | Subject: 'type' declarations
> |
> | hello,
> | ghc seems to be having trouble with 'type' declarations.
> | while compiling (i guess kind checking is the correct
> word here)
> | the following program for a very long time, ghc (6.2)
> runs out of 300Mb of heap.
> |
> | module Test where
> |
> | type S          = Maybe
> | type S2 n       = S  (S  n)
> | type S4 n       = S2 (S2 n)
> | type S8 n       = S4 (S4 n)
> | type S16 n      = S8 (S8 n)
> | type S32 n      = S16 (S16 n)
> |
> | type N64 n      = S32 (S32 n)
> |
> | type N64'       =
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   S ( S ( S ( S ( S ( S ( S ( S (
> |   Int
> |   ))))))))
> |   ))))))))
> |   ))))))))
> |   ))))))))
> |   ))))))))
> |   ))))))))
> |   ))))))))
> |   ))))))))
> |
> | if i remove the N64 definition things work.  i guess
> something
> | exponential is happening
> | (substitution?).
> |
> | -iavor
>
> }}}

New description:

 {{{
 You're quite right.  GHC has a simple but non-
 performant representation of type synonyms in types, so
 as to be able to generate good error messages,  In
 particular, the type

         S t

 where S is a type synonym defined by 'type S a = s', is
 represented as

         SynNote (S t) (s [t/a])

 That is, (S t) is represented by *both* its un-expanded
 and expanded form.

 The SynNote is ignored by unification, but the un-
 expanded form is useful for error messages.
 Unfortunately, t is duplicated, as you can see, and that
 leads to the behaviour you describe.

 I don't see myself fixing this soon, at least partly
 because I can't see an obvious way to fix it that doesn't
 lose error message behaviour.

 I'm going to open a SourceForge bug for it.  If anyone
 has good ideas, let me know.

 Simon

 | -----Original Message-----
 | From: glasgow-haskell-bugs-bounces at haskell.org
 [mailto:glasgow-haskell-bugs-
 | bounces at haskell.org] On Behalf Of Iavor Diatchki
 | Sent: 17 February 2005 01:27
 | To: glasgow-haskell-bugs at haskell.org
 | Subject: 'type' declarations
 |
 | hello,
 | ghc seems to be having trouble with 'type' declarations.
 | while compiling (i guess kind checking is the correct
 word here)
 | the following program for a very long time, ghc (6.2)
 runs out of 300Mb of heap.
 |
 | module Test where
 |
 | type S          = Maybe
 | type S2 n       = S  (S  n)
 | type S4 n       = S2 (S2 n)
 | type S8 n       = S4 (S4 n)
 | type S16 n      = S8 (S8 n)
 | type S32 n      = S16 (S16 n)
 |
 | type N64 n      = S32 (S32 n)
 |
 | type N64'       =
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   S ( S ( S ( S ( S ( S ( S ( S (
 |   Int
 |   ))))))))
 |   ))))))))
 |   ))))))))
 |   ))))))))
 |   ))))))))
 |   ))))))))
 |   ))))))))
 |   ))))))))
 |
 | if i remove the N64 definition things work.  i guess
 something
 | exponential is happening
 | (substitution?).
 |
 | -iavor

 }}}

-- 
Ticket URL: <http://cvs.haskell.org/trac/ghc/ticket/323>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler