Opened 10 months ago

Last modified 4 months ago

#9112 new feature request

support for deriving Vector/MVector instances

Reported by: jwlato Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.8.2
Keywords: Cc: ecrockett0@…, hackage.haskell.org@…, remi.turk@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

Since ghc-7.8, the following is no longer possible:

-- simplified example taken from the vector package
class MVectorClass (v :: * -> * -> *) a where
    basicLength :: v s a -> Int

data family MVector s a

data instance MVector s Int -- implementation not important

newtype Age = Age Int deriving (MVectorClass MVector) -- rejected

Following from discussion in #8177, to enable this ghc would need to support data families with representational matching, such that MVector s Int and MVector s Age are representationally equal.

This has broken some code that previously worked, however as there are some workarounds I'm not sure how important it is.

Change History (12)

comment:1 Changed 10 months ago by liyang

  • Cc hackage.haskell.org@… added

I'm not sure using vector-th-unbox counts as a complete workaround, as it amounts to giving the instance in full.

Without coerce, I think it's also susceptible to the expensive "map id" issue.

comment:2 Changed 10 months ago by simonpj

The trouble with your proposal is that (as of today) you can say

data instance MVector s Int = ...rep1...
data instance MVector s Age = ...rep2...

specifying that MVector over Int has an entirely different representation to MVector over Age. Indeed that is often the very reason that people define a newtype in the first place! For example, if you want sort to sort into reverse order, can write

import Data.Ord( Down(..) )

downSort :: Ord a => [a] -> [a]
downSort xs = coerce (sort (coerce xs :: [Down a]))

We coerce the [a] to [Down a], then sort (using Down's ordering), then coerce back.

It's going to be quite confusing data instance can sometimes match on a newtype, and sometimes not. And then there are nested cases to worry about:

newtype MVector s [Age] = ...
newtype MVector s [Int] = ...

Moreover, you still (presumably) want MVector s Age and MVector s Int to be distinct types!

None of this smells good to me.

But here's an idea. You want MVector s Age and MVector s Int But you want them to be represented the same way. That's what we use newtypes for. So how about this:

newtype instance MVector s Age = MVA (MVector s Int)

Would that help? For example, this compiles without complaint:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, GeneralizedNewtypeDeriving #-}
module T9112 where

class MVectorClass (v :: * -> * -> *) a where
    basicLength :: v s a -> Int

data family MVector s a

data instance MVector s Int = MV -- implementation not important

newtype Age = Age Int deriving (MVectorClass MVector)

newtype instance MVector s Age = MV1 (MVector s Int)

instance MVectorClass MVector Int where
  basicLength x = 0
Last edited 10 months ago by simonpj (previous) (diff)

comment:3 Changed 10 months ago by jwlato

Simon, it's possible that suggestion will work, with a few other modifications to the way roles are currently handled. It doesn't work with vector/ghc as currently released due to some other methods. For example, if I add basicUnsafeRead

class MVectorClass (v :: * -> * -> *) a where
    basicLength :: v s a -> Int
    basicUnsafeRead :: PrimMonad m => v (PrimState m) a -> Int -> m a

It's not possible to coerce basicUnsafeRead because of the coercion from m Int to m Age. There are a number of other methods that also can't be coerced, but I think they're all because ms type parameter is at a nominal role. If it were possible to express that ms parameter need only be representationally equal, I think this would work. (maybe related to the current issues with deriving and AMP?)

I'm not sure what's involved with making that coercion happen, but it seems decidely less tricky than representationally-equal data families (I have quite a bit more to say about that also, but I'll leave it for another venue). I'm changing the title of this ticket to more closely reflect the actual goal, e.g. deriving vector instances.

comment:4 Changed 10 months ago by jwlato

  • Summary changed from data families with representational matching to support for deriving Vector/MVector instances

comment:5 Changed 10 months ago by simonpj

Yes, the basisUnsafeRead thing is directly related to the AMP/GND question. See #9123.

comment:6 follow-up: Changed 9 months ago by bitemyapp

I am trying to build hackage-server on Mac OS X with GHC 7.8 and I was told this ticket is relevant to my problems.

I've included the build error in this comment.

    When deriving the instance for (VecMut.MVector
                                      VecBase.MVector DocId)

Distribution/Server/Features/Search/DocIdSet.hs:38:13:
    Could not coerce from ‘Data.Vector.Primitive.Mutable.MVector
                             s Word32’ to ‘VecBase.MVector s DocId’
      because ‘Data.Vector.Primitive.Mutable.MVector
                 s Word32’ and ‘VecBase.MVector s DocId’ are different types.
      arising from the coercion of the method ‘VecMut.basicOverlaps’
                   from type
                   ‘forall s.
                    VecBase.MVector s Word32 -> VecBase.MVector s Word32 -> Bool’
                   to type
                   ‘forall s.
                    VecBase.MVector s DocId -> VecBase.MVector s DocId -> Bool’
    Possible fix:
      use a standalone 'deriving instance' declaration,
        so you can specify the instance context yourself
    When deriving the instance for (VecMut.MVector
                                      VecBase.MVector DocId)

Distribution/Server/Features/Search/DocIdSet.hs:38:13:
    Could not coerce from ‘Data.Vector.Primitive.Mutable.MVector
                             s Word32’ to ‘VecBase.MVector s DocId’
      because ‘Data.Vector.Primitive.Mutable.MVector
                 s Word32’ and ‘VecBase.MVector s DocId’ are different types.
      arising from the coercion of the method ‘VecMut.basicUnsafeSlice’
                   from type
                   ‘forall s.
                    Int -> Int -> VecBase.MVector s Word32 -> VecBase.MVector s Word32’
                   to type
                   ‘forall s.
                    Int -> Int -> VecBase.MVector s DocId -> VecBase.MVector s DocId’
    Possible fix:
      use a standalone 'deriving instance' declaration,
        so you can specify the instance context yourself
    When deriving the instance for (VecMut.MVector
                                      VecBase.MVector DocId)

Distribution/Server/Features/Search/DocIdSet.hs:38:13:
    Could not coerce from ‘Data.Vector.Primitive.Mutable.MVector
                             s Word32’ to ‘VecBase.MVector s DocId’
      because ‘Data.Vector.Primitive.Mutable.MVector
                 s Word32’ and ‘VecBase.MVector s DocId’ are different types.
      arising from the coercion of the method ‘VecMut.basicLength’
                   from type ‘forall s. VecBase.MVector s Word32 -> Int’ to type
                   ‘forall s. VecBase.MVector s DocId -> Int’
    Possible fix:
      use a standalone 'deriving instance' declaration,
        so you can specify the instance context yourself
    When deriving the instance for (VecMut.MVector
                                      VecBase.MVector DocId)

comment:7 follow-up: Changed 9 months ago by simonpj

I can't reproduce this because I fall at an early fence:

bash$ cabal install hackage-server
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: hackage-server-0.4 (user goal)
trying: base-4.7.0.0/installed-018... (dependency of hackage-server-0.4)
next goal: process (dependency of hackage-server-0.4)
rejecting: process-1.2.0.0/installed-eaf... (conflict: process =>
unix==2.7.0.1/installed-23f..., hackage-server => unix<2.7)
trying: process-1.2.0.0
next goal: Cabal (dependency of hackage-server-0.4)
rejecting: Cabal-1.18.1.3/installed-9a9..., 1.20.0.0, 1.18.1.3, 1.18.1.2,
1.18.1.1, 1.18.1, 1.18.0 (conflict: hackage-server => Cabal>=1.16 && <1.17)
trying: Cabal-1.16.0.3
rejecting: Cabal-1.16.0.3:+base3 (conflict: process==1.2.0.0,
Cabal-1.16.0.3:base3 => process>=1 && <1.2)
rejecting: Cabal-1.16.0.3:-base3 (conflict: base==4.7.0.0/installed-018...,
Cabal-1.16.0.3:base3 => base<3)
Backjump limit reached (change with --max-backjumps).

bash$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.2

I have no idea what all this means. But it looks plausible that it's the same issue, and is rightly rejected on the grounds that it could be unsound. We have yet to figure out a way to solve this; see #9123.

I do not know whether this is a show-stopper any particular packages, and if so which. Nor do I know if there is a reasonable way to work around it. Perhaps others will know more than I do.

Simon

comment:8 in reply to: ↑ 7 Changed 9 months ago by tibbe

Replying to simonpj:

I have no idea what all this means. But it looks plausible that it's the same issue, and is rightly rejected on the grounds that it could be unsound. We have yet to figure out a way to solve this; see #9123.

I can't tell, from the cabal message, whether cabal gave up early or there's in fact no install plan possible. If it's the former then cabal-install-1.20.0.2 (released last weekend) has several solver improvements that might let it find a solution that lets you build.

comment:9 Changed 9 months ago by Remi

  • Cc remi.turk@… added

comment:10 in reply to: ↑ 6 Changed 8 months ago by rwbarton

Replying to bitemyapp:

I am trying to build hackage-server on Mac OS X with GHC 7.8 and I was told this ticket is relevant to my problems.

I've included the build error in this comment. [...]

These specific errors are easy to fix. VecBase.MVector (hereafter abbreviated MVector) is a standalone data family. There is an instance MVector s Word32, but no instance for the new type MVector s DocId. GHC 7.6.3 did not care at all about this when producing an instance VecMut.MVector MVector DocId with generalized newtype deriving, which is totally bogus because the derived instance has methods like basicLength of type MVector s DocId -> Int, even though there is no type MVector s DocId at all! A client can then define a mismatched instance data instance MVector s DocId = Foo Char, which will effectively be unsafely coerced to MVector s Word32, leading to undefined behavior (most likely a segfault).

GHC 7.8 actually pays attention to what is going on here. To satisfy it all you need to do is define an instance for the data family in a way such that MVector s DocId is actually coercible to MVector s Word32. For example, newtype instance MVector s DocId = DocVector (MVector s Word32) will do the job. (Then you will want an instance for VecBase.Vector, too.)

However, you will then immediately run into the other error involving the role of the parameter to m in the types of the other methods of VecMut.MVector, as discussed above.

comment:11 Changed 8 months ago by simonpj

My current belief is that #9123 is the nub of the issue. Once we've fixed that, I hope that this ticket will also be solved.

Please yell if you disagree.

Simon

comment:12 Changed 4 months ago by crockeea

  • Cc ecrockett0@… added
Note: See TracTickets for help on using tickets.