[GHC] #11431: GHC instantiates levity-polymorphic type variables with foralls
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Consider the following use of `error`. {{{ ghci> :t error error :: forall (v :: GHC.Types.Levity) (a :: TYPE v). (?callStack::GHC.Stack.Types.CallStack) => [Char] -> a ghci> :t error "bad" :: (forall a. a -> a) -> a error "bad" :: (forall a. a -> a) -> a :: (?callStack::GHC.Stack.Types.CallStack) => (forall a1. a1 -> a1) -> a }}} GHC is instantiating the type variable `a` in the output with `(forall a. a -> a) -> a`, which requires impredicative polymorphism. So this example should actually be rejected by the type checker. Note that GHC also does this with open-kinded type variables, so the behavior with `error` and `undefined` has been around for a while. There are tests that depend on it, and a Note that describes the decision to accept these programs. Still, Simon PJ says perhaps we should really just reject these programs. So here's a ticket to discuss the matter. For more information, see the discussion starting at https://phabricator.haskell.org/D1739#51408. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I think the current behavior is fine, if somewhat unexpected. (We should document it if we haven't.) There is no such thing as a levity-polymorphic value. (If there were, how much space would it take up?) Thus, any levity-polymorphic expression must be bottom. So I don't see how a tiny bit of impredicativity just for bottoms can cause trouble. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
I don't see how a tiny bit of impredicativity just for bottoms can cause
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): trouble. Impredicativity never causes trouble for the dynamic semantics; after all Core is impredicative. In contrast levity-polymorphism does. Impredicativity does cause trouble for type inference -- see zillions of papers on the subject. In contrast levity-polymorphism does not. (Except in enforcing the restrictions that levity polyormophism must follow to avoid screwing up the dynamic semantics.) There is no reason (that I can see) that the restrictions for levity polymorophism should be sufficient to avoid all type- inference/impredicativity difficulties. Maybe so, but it would be a coincidence. There's an engineering issue too. Richard is about to eliminate `RetTv`. But `RetTv` is essential to the implementation that accepts the above program. Are we going to leave `RetTv` for this sole (ill-defined) purpose? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
There's an engineering issue too. Richard is about to eliminate `RetTv`. But `RetTv` is essential to the implementation that accepts the above program. Are we going to leave `RetTv` for this sole (ill-defined)
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Replying to [comment:2 simonpj]: purpose? Yes, I recognize that as an unfortunate consequence of this suggestion. But it wouldn't be `ReturnTv` -- it would go back to the old `PolyTv`, just a tyvar that's allowed to unify with a polytype. Agreed that, if this works, it's a coincidence. That does seem to suggest that it doesn't work. My hope that it would work is because levity polymorphism is vanishingly rare. In any case, I don't feel strongly. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: | TypeApplications Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => TypeApplications Comment: Tagging this with `TypeApplications`. Not strictly correct, but in the same general territory and I don't want to lose track of it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: | TypeApplications Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): It is very considerably easier not to instantiate levity-polymorphic variables with foralls. So that's what I'm doing right now. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: | TypeApplications, | LevityPolymorphism Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * keywords: TypeApplications => TypeApplications, LevityPolymorphism -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11431: GHC instantiates levity-polymorphic type variables with foralls -------------------------------------+------------------------------------- Reporter: gridaphobe | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: fixed | Keywords: | TypeApplications, | LevityPolymorphism Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by goldfire): * status: new => closed * resolution: => fixed Comment: This seems resolved. GHC now allows no impredicative polymorphism, even for levity-polymorphic values. Closing the ticket. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11431#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC