March 2017 - ghc-tickets

[GHC] #13361: Better type synonym merging/subtyping for Backpack
by GHC 02 Mar '17

02 Mar '17

#13361: Better type synonym merging/subtyping for Backpack -------------------------------------+------------------------------------- Reporter: ezyang | Owner: (none) Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 8.1 (Type checker) | Keywords: backpack | Operating System: Unknown/Multiple Architecture: | Type of failure: GHC rejects Unknown/Multiple | valid program Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Here are two signatures which don't merge today in Backpack: {{{ signature A where data T data U = Mk T signature A where data S data U = Mk S }}} On the one hand, this is not too surprising, because you never said that T and S were the same, so why should I decide that the declarations of U are compatible? OK, but suppose I were to add the missing type synonym: which direction should I put it? What you will find is that, under Backpack's current subtyping rules, *neither* orientation is a subtype of the other: {{{ signature A where data T type S = T data U = Mk T signature A where type T = S data S data U = Mk S }}} The first signature is a supertype of a module that says `data T = MkCommon`, but NOT of a module that says `data S = MkCommon`, since type synonym declarations and data declarations are not compatible. This doesn't smell very good. Indeed, ML's semantic signatures do not have this problem, because when I write these signatures, I actually get a semantic signature of the form `exists c. { type T = c, type S = c, ... }`; i.e., neither declaration is privileged. On the other hand, our behavior is inline with MixML, which does not have these as mutual subtypes. So it's not clear the complexity of changing our internal language justifies the marginal benefit that is to be gotten here. Not planning on fixing this unless someone shouts. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13361> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 0

[GHC] #9729: GHCi accepts invalid programs when recompiling
by GHC 01 Mar '17

01 Mar '17

#9729: GHCi accepts invalid programs when recompiling -------------------------------------+------------------------------------- Reporter: crockeea | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: GHCi | Version: 7.8.3 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: GHC Blocked By: | accepts invalid program Related Tickets: | Test Case: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Here's what's happening: Module A imports module B. Module B contains a function with constraints that are '''required''' to compile module B. If I load module A in GHCi, I can remove some (required) constraints on the function in module B and GHCi will successfully reload module B. My example uses the [https://hackage.haskell.org/package/syntactic syntactic] library. I attempted to recreate the situation I just described without syntactic, but I was unsuccessful. Module A.hs: {{{ #!haskell module A where import B import Data.Syntactic.Sugar.BindingT () main = print "hello" }}} Module B.hs: {{{ #!haskell {-# LANGUAGE GADTs, TypeOperators, FlexibleContexts #-} module B where import Data.Syntactic data Let x where Let :: Let (a :-> (a -> b) :-> Full b) share :: (Let :<: sup, sup ~ Domain b, sup ~ Domain a, Internal (a -> b) ~ (Internal a -> Internal b), -- remove me Syntactic a, Syntactic b, Syntactic (a -> b), SyntacticN (a -> (a -> b) -> b) (ASTF sup (Internal a) -> ASTF sup (Internal (a -> b)) -> ASTF sup (Internal b))) => a -> (a -> b) -> b share = sugarSym Let }}} Here's a terminal transcript: {{{ $ ghci A [1 of 2] Compiling B ( testsuite/B.hs, interpreted ) [2 of 2] Compiling A ( testsuite/A.hs, interpreted ) Ok, modules loaded: A, B. > (Now remove the constraint from B and save. This *should* break module B) > :r [1 of 2] Compiling B ( testsuite/B.hs, interpreted ) Ok, modules loaded: A, B. > :q $ ghci B [1 of 2] Compiling B ( testsuite/B.hs, interpreted ) testsuite/B.hs:21:9: Could not deduce (Internal (a -> b) ~ (Internal a -> Internal b)) }}} If I had to guess what's going on, it's that GHCi is remembering the instance that A imports from BindingT: {{{ instance (...) => Syntactic (a -> b) where type Internal (a -> b) = Internal a -> Internal b }}} This instance implies the constraint that module B needs, however it should never be visible to module B. GHCi seems to be ignoring that and using the instance to recompile module B. When compiling from scratch, module B is compiled first, so of course the instance (and therefore the constraint) are not visible. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9729> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 7

[GHC] #13358: Role ranges (allow decomposition on newtypes)
by GHC 01 Mar '17

01 Mar '17

#13358: Role ranges (allow decomposition on newtypes) -------------------------------------+------------------------------------- Reporter: ezyang | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.1 (Type checker) | Keywords: backpack | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Extracted from #13140. Today, there is a strange asymmetry between data types, for which the decomposition rule holds (if `T A ~R T B` then `A ~ρ B`, where ρ is the role of the type), and newtypes, for which the decomposition rule is unsound. I believe the root cause of this problem is the fact that we only maintain a single role per type parameter, while in fact what we need is a role *range* (i.e., and lower and upper role bound) to specify what inferences can be made about a type. Here's how it works. Every type parameter is ascribed a role range, specifying the possible roles by which the type parameter might possibly be used. For example, if I write `data T a = MkT a`, `a` is used exactly at representational role, but we could also say that a *might* be used nominally, giving the role range nominal-representational. The lower bound (nominal is lowest in subroling) specifies at what role the application rule is valid: if I say that the role is at least nominal, then I must provide `a ~N b` evidence to show that `T a ~R T b`. The upper bound (phantom is highest) specifies at what role the decomposition rule is valid. If I say that the role is at most phantom, I learn nothing from decomposition; but if I say the role is at most representational, when `T A ~R T B`, I learn `A ~R B`. Clearly, the role range nominal-phantom permits the most implementations, but gives the client the least information about equalities. How do we tell if a role range is compatible with a type? The lower bound (what we call a role today) is computed by propagating roles through, but allowing substitution of roles as per the subroling relationship `N <= R <= P`. To compute the upper bound, we do exactly the same rules, but with the opposite subroling relation: `P <= R <= N`. Some examples: {{{ type app role T representational type proj role T representational newtype T a = MkT a -- T a ~R T b implies a ~R b type app role T nominal type proj role T representational -- NB: type proj role T nominal is NOT ALLOWED newtype T a = MkT a -- T a ~R T b implies a ~R b, BUT -- a ~R b is insufficient to prove T a ~R T b (you need a ~N b) type app role T nominal type proj role T phantom -- (representational and nominal not allowed) newtype T a = MkT Int -- T a ~R T b implies a ~P b (i.e. we don't learn anything) -- a ~N b implies T a ~R T b }}} Richard wonders if we could use this to solve the "recursive newtype unwrapping" problem. Unfortunately, because our solver is guess-free, we must also maintain the most precise role for every type constructor. See https://ghc.haskell.org/trac/ghc/ticket/13140#comment:12 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13358> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 4

[GHC] #12703: Expand Backpack's signature matching relation beyond definitional equality
by GHC 01 Mar '17

01 Mar '17

#12703: Expand Backpack's signature matching relation beyond definitional equality -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.1 (Type checker) | Keywords: backpack | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Currently, signature matching is done by strict definitional equality. This can be pretty inconvenient in some cases (it is also the only place in the Haskell language that we actually expose definitional equality): **Polymorphism.** This is the obvious one. If I have an implementing function that is more polymorphic than my signature, I have to manually monomorphize it. {{{ unit p where signature H where import Prelude (Int) data String length :: String -> Int unit q where module H(String, length) where -- from Prelude unit r where dependency p[H=q:H] }}} Gives {{{ <no location info>: error: Identifier ‘Data.Foldable.length’ has conflicting definitions in the module and its hsig file Main module: Data.Foldable.length :: Data.Foldable.Foldable t => forall a. t a -> GHC.Types.Int Hsig file: Data.Foldable.length :: GHC.Base.String -> GHC.Types.Int The two types are different }}} Essentially, you have to monomorphize any functions you want to use. Annoying! **Quantifier ordering.** Here's a more subtle one: if I don't explicitly specify a type signature, GHC will pick whatever quantifier ordering it wants. Quantifier ordering affects definitional equality. It's actually pretty easy to trigger this, since GHC seems to always pick the reverse of what you'd get if you explicitly specified the type signature: {{{ unit p where signature H where k :: a -> b -> a unit q where module H where k x y = x unit r where dependency p[H=q:H] }}} Fails with: {{{ q.bkp:7:9: error: Identifier ‘q:H.k’ has conflicting definitions in the module and its hsig file Main module: q:H.k :: t2 -> t1 -> t2 Hsig file: q:H.k :: a -> b -> a The two types are different }}} **Constraint relaxation.** In #12679, you might want to define an abstract class which you can use to let implementors pass in type class instances that they might need. But you often end up in situations where the real implementations of your functions require less constraint than the signature specifies; for example, you might write `insert :: Key k => k -> a -> Map k a -> Map k a`, but if Map is an association list and just appends the new value onto the front of the list, no Eq constraint needed! There goes another impedance matching binding. **Type families.** Type family applications aren't reduced when deciding definitional equality. {{{ {-# LANGUAGE TypeFamilies #-} unit p where signature H where f :: Int unit q where module H where type family F type instance F = Int f :: F f = 2 unit r where dependency p[H=q:H] }}} Gives {{{ q.bkp:11:9: error: Identifier ‘q:H.f’ has conflicting definitions in the module and its hsig file Main module: q:H.f :: q:H.F Hsig file: q:H.f :: GHC.Types.Int The two types are different }}} **Discussion.** It's instructive to consider what the impacts of this sort of relaxation would have on hs-boot files. Some of the equalities that users expect in the source language have operational impact: for example, the ordering of constraints affects the calling convention of the function in question. So there would need to be an impedance matching binding to reorder/drop constraints to match the defining function. We already do an impedance matching of this sort with dictionary functions; this would be a logical extension. Thus, a signature would have to monomorphize, coerce, etc--whatever it needs to show the matching holds. I think this is quite plausible, although it would require rewriting this chunk of code. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/12703> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 3

[GHC] #10749: Boot file instances should imply superclasses
by GHC 01 Mar '17

01 Mar '17

#10749: Boot file instances should imply superclasses -------------------------------------+------------------------------------- Reporter: ezyang | Owner: ezyang Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.11 Keywords: backpack | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Revisions: | -------------------------------------+------------------------------------- Currently, if I write the following program: {{{ -- A.hs-boot module A where data T instance Ord T -- B.hs module B where import {-# SOURCE #-} A f :: T -> T -> Bool f x y = x == y }}} I get: {{{ B.hs:4:11: No instance for (Eq T) arising from a use of `==' Possible fix: add an instance declaration for (Eq T) In the expression: x == y In an equation for `f': f x y = x == y }}} This is a bit confusing, because Ord instances are supposed to imply Eq instances. GHC should either: 1. Reject A.hs-boot (claiming that it could not find evidence that T had an Eq instance), or 2. Accept B.hs, since the instance requirement for Ord should imply Eq. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10749> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 3

[GHC] #9131: Experiment with a dedicated solver for Coercible
by GHC 01 Mar '17

01 Mar '17

#9131: Experiment with a dedicated solver for Coercible ------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: task | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.8.2 Keywords: | Operating System: Unknown/Multiple Architecture: Unknown/Multiple | Type of failure: None/Unknown Difficulty: Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | ------------------------------------+------------------------------------- This is something that I might want to do some time; it should not distract us from working and improving the current design and implementation. But I think it should be explored. Currently `Coercible` appears as a type class, we have instances to explain it, and use the existing solver to solve them. The last part sometimes causes problems: * the order the instances are tried matters, there might be dead ends (#9117) * recursive newtypes are not handled as good as they could be. It would be worth exploring if a dedicated solver for `Coercible` constraints could solve these issues. It could replace the existing `getCoercibleInst`. Given a constraint `Coercible s t` it would solve it completely, do nothing or (and this is not planned out yet) return some sufficient and in some sense primitive constraint that should appear in inferred type signatures etc. Ideally we could still explain `Coercible` in terms of the instances written in the ICFP’14 paper, and simply state „GHC will find a solution using these instances, if there are any.“ instead of „The usual solver is employed, it might run into dead ends (or not, hard to tell).“ When tackling this task, I should do something that I keep postponing (because I don’t like to admit my lack of knowlege about that) but I think is really important: What are the theoretical properties of solving `Coercible` constraints? Is it even decidable? Semi decidable? Are there existing standard algorithms? How does this relate to SMT solving? And why don’t I know these things... -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9131> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 9

[GHC] #9117: Coercible constraint solver misses one
by GHC 01 Mar '17

01 Mar '17

#9117: Coercible constraint solver misses one ------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Keywords: | Operating System: Unknown/Multiple Architecture: Unknown/Multiple | Type of failure: None/Unknown Difficulty: Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | ------------------------------------+------------------------------------- When I say {{{ import Data.Type.Coercion import Data.Coerce eta :: Coercible f g => Coercion (f a) (g a) eta = Coercion }}} I get {{{ Could not coerce from ‘f a’ to ‘g a’ because ‘f a’ and ‘g a’ are different types. arising from a use of ‘Coercion’ from the context (Coercible f g) bound by the type signature for eta :: Coercible f g => Coercion (f a) (g a) at /Users/rae/temp/Roles.hs:6:8-44 In the expression: Coercion In an equation for ‘eta’: eta = Coercion }}} But, this coercion is easily expressible in Core. If `(co :: f ~R# g)` then `(co <a> :: f a ~R# g a)`, where `<a>` is the notation for a reflexivity coercion for the type `a`. The constraint solver should be able to do this. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9117> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 35

[GHC] #13323: Backpack doesn't work with DuplicateRecordFields
by GHC 01 Mar '17

01 Mar '17

#13323: Backpack doesn't work with DuplicateRecordFields -------------------------------------+------------------------------------- Reporter: ezyang | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 (Type checker) | Keywords: backpack | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- With {{{ {-# LANGUAGE DuplicateRecordFields #-} unit p where signature A where data A = A { foo :: Int } data B = B { foo :: Bool } }}} I get: {{{ [1 of 1] Processing p [1 of 1] Compiling A[sig] ( p/A.hsig, nothing ) <no location info>: error: The identifier $sel:foo:A does not exist in the local signature. (Try adding it to the export list of the hsig file.) }}} This is happening because the "exports" test is checking only the children of AvailTC, and not the field labels. Should be an easy fix. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13323> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 3

[GHC] #13335: Non-abstract types also have skolem nature
by GHC 01 Mar '17

01 Mar '17

#13335: Non-abstract types also have skolem nature -------------------------------------+------------------------------------- Reporter: ezyang | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.1 (Type checker) | Keywords: backpack | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- In #12680, we determined that abstract types from signatures need to be treated like skolem variables. But it turns out other types from signatures also need to be treated like skolem variables too: {{{ {-# LANGUAGE GADTs #-} unit p where signature M1 where data A = MkA signature M2 where data A = MkA module A where import qualified M1 import qualified M2 f :: M1.A ~ M2.A => a -> b f x = x }}} This is bad because these As could be the same thing in the end. I think the real, final fix, is to not test for "skolem abstractness" (as we do now), but just look and see if the Name for the TyCon is a name hole or not. Then we can eliminate skolem abstract completely. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13335> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 2

[GHC] #13140: Handle subtyping relation for roles in Backpack
by GHC 01 Mar '17

01 Mar '17

#13140: Handle subtyping relation for roles in Backpack -------------------------------------+------------------------------------- Reporter: ezyang | Owner: ezyang Type: feature | Status: new request | Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.1 (Type checker) | Keywords: backpack hs- | Operating System: Unknown/Multiple boot | Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- If I understand correctly, GHC's three currently supported roles follow the following subtyping relation: `phantom <: representational <: nominal`. So it would make sense to adjust Backpack and `hs-boot` files to handle this subtyping relation appropriately. Here's my proposal. * Today, roles in signature files default to representational. Let's change the default to nominal, as this is the most flexible implementation side. If a client of the signature needs to coerce with a type, the signature can be adjusted to have more stringent requirements. * If a parameter is declared as nominal in a signature, it can be implemented by a data type which is actually representational. * When merging abstract data declarations, we take the smallest role for every parameter. The roles are considered fix once we specify the structure of an ADT. I actually don't know if the proofs about roles actually say anything about this subtyping relation. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13140> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

1 15