The type class wilderness + Separating instances and implementations into separate packages
What is the right interface for a queue? What is the right interface for a random number generator? I don't know, but in both cases you will find many packages on hackage offering different takes on the matter. In fact, there is a wilderness of alternative interfaces. We've had various discussions on this list about the number of alternative packages. I'm fine with lots of packages, but I think it would be great if not every package introduced a new interface as well as a new implementation. If we could agree as a community on common interfaces to use for some basics, that would probably go a long way towards taming the type class wilderness. People have mentioned this problem before with respect to "Collections" generally. One basic part of reaching such a goal is separating interface from implementation. I ran into the following problems just in the last 24 hours. In both cases I wanted to use a type class, but didn't want to depend on the whole package it lived in: - I wanted to use the Benchmarkable class in Criterion in my package. (Criterion deserving to be a "standard" package.) But I can't get that typeclass without depending on the whole Criterion package, which has several dependencies. And in fact on the machine I was on at the time some of those dependencies were broken, so I decided not to use Benchmarkable. - I wanted to use, or at least support, an existing class for Queues. I found the following: http://hackage.haskell.org/packages/archive/queuelike/1.0.9/doc/html/Data-MQ... I have no idea who uses this package. But because this package (like most packages) includes the implementation along with the interface it introduces additional dependency liabilities. In this case it failed to build on GHC 7.2 so I quickly gave up on supporting that TypeClass. How can we enumerate packages that at least purport to provide standard interfaces that you should both use and pick up to implement? On a Wiki page? -Ryan P.S. I'm working on mutable concurrent Deques right now and am trying to follow my own prescription above by creating an abstract interface in a separate package. See below if you would like to offer feedback on that interface. -------------------------------------- My ultimate goal is an "abstract-deque" parameterizable interface that abstracts over bounded/unbounded, concurrent/non-concurrent, single, 1.5, and double-ended queues, which would include both, say, Michael & Scott linked queues and the Chase-Lev work-stealing deques. An aggregated queue package could use type families to dispatch to the best available queue implementation for a given configuration. I've got a couple drafts of how this might work. They're in different branches here: https://github.com/rrnewton/haskell-lockfree-queue/blob/master/AbstractDeque... https://github.com/rrnewton/haskell-lockfree-queue/blob/one-type-class/Abstr... One of them uses an associated data type family, the other an unassociated one. The type family has a bunch (six) phantom type parameters, and the unassociated one allows hiding those parameters at the expense of introducing more type classes. MegaQueue.hs will be used to aggregate together different queue implementations. The end result is that someone can create a new queue by setting all the switches on the type, as follows: test = do q :: Deque NT T SingleEnd SingleEnd Bound Safe Int <- newQ pushL q 33 x <- tryPopR q print x return q With those settings, requiring only single-ended rather than double-ended queues, the above code can use the LinkedQueue (Michael and Scott) implementation included in that repo. That little test, by the way, segfaults for me on Mac OS under GHC 7.2.1 even WITHOUT using casMutVar# (It's using Data.CAS.Fake presently.) I'll file a bug report after I sanity check it some more. Disregarding that... the big problem in this case is the* inability to create overlapping type family instances. * In this case what we dearly WANT to do is specialize some subset of the 64-mode configuration space and then have a "fallback". You can take a look at my struggling in MegaDeque. Both of my approaches require specifying explicitly the modes that you don't cover. Worse, we may want to specialize on element type as well. For example, for simple scalar types (or even Storable types) it may be desirable to use something foreign, like TBB queues. But in that case, there's no way to enumerate the types NOT specialized. As far as I know there is no way for type families to accomplish this (specialize, say "Int", and have a fallback for everything else). In general, is there a recognized work-around for this? For example, is this a place where using functional dependencies instead might do the trick? Also, there are some software-engineering issues here with respect to* where to put the instances*. It would be nice to put the instances for DequeClass inside the individual implementations (like LinkedQueue.hs). But that leads to problems because it's really the job of MegaQueue.hs to figure out how to spread implementations over the configuration-space. And once you put the instances in LinkedQueue.hs there is of course *no way to qualify or hide them upon import....* Feedback welcome. Cheers, -Ryan
These are all very good questions! Here's my stab at it:
On Wed, Nov 2, 2011 at 11:28 AM, Ryan Newton
What is the right interface for a queue? What is the right interface for a random number generator?
For any given class I'd try to get a few experts/interested parties together and discuss.
I don't know, but in both cases you will find many packages on hackage offering different takes on the matter. In fact, there is a wilderness of alternative interfaces. We've had various discussions on this list about the number of alternative packages.
The lack of cohesion in our library offerings is a problem and so is the lack of interfaces. We end up programming against concrete types way too often.
I'm fine with lots of packages, but I think it would be great if not every package introduced a new interface as well as a new implementation. If we could agree as a community on common interfaces to use for some basics, that would probably go a long way towards taming the type class wilderness. People have mentioned this problem before with respect to "Collections" generally.
Aside: The problem with collections is that we don't have the programming language means to do this well yet (although soon!). The issue is that we want to declare a type class where the context of the methods depends on the instance e.g. class MapLike m where type Ctx :: Context -- Can't do this today! insert Ctx => k -> v -> m -> m Java et all cheats in their container hierarchy by doing unsafe casts (i.e. they never solved this problem)!
One basic part of reaching such a goal is separating interface from implementation. I ran into the following problems just in the last 24 hours. In both cases I wanted to use a type class, but didn't want to depend on the whole package it lived in:
- I wanted to use the Benchmarkable class in Criterion in my package. (Criterion deserving to be a "standard" package.) But I can't get that typeclass without depending on the whole Criterion package, which has several dependencies. And in fact on the machine I was on at the time some of those dependencies were broken, so I decided not to use Benchmarkable. - I wanted to use, or at least support, an existing class for Queues. I found the following:
http://hackage.haskell.org/packages/archive/queuelike/1.0.9/doc/html/Data-MQ...
I think the best option at the moment is to break out type classes in their own packages. That's what I did with hashable. How can we enumerate packages that at least purport to provide standard
interfaces that you should both use and pick up to implement? On a Wiki page?
I would hope that we could get all the important interfaces into the Haskell Platform eventually (and have all packages there use them). -- Johan
I think the best option at the moment is to break out type classes in their> own packages. That's what I did with hashable. Indeed! I greatly believe in this mantra now. Really, my point was only this banal one -- packages with only interfaces in them have no dependencies and are much less likely than implementation packages to break when the GHC version changes.
Aside: The problem with collections is that we don't have the programming language means to do this well yet (although soon!). The issue is that we want to declare a type class where the context of the methods depends on the instance e.g. class MapLike m where type Ctx :: Context -- Can't do this today! insert Ctx => k -> v -> m -> m Java et all cheats in their container hierarchy by doing unsafe casts (i.e. they never solved this problem)!
Ah, interesting. Is there a proposal to do this? While we need to avoid an infinite regress of generalization and abstraction (type programming => kind programming?, etc) -- it does seem like class contexts on types and type class instances themselves would be nice to have *some* control over. (In the above message, for example I was having trouble due to not being able to hide instances on import.)
I would hope that we could get all the important interfaces into the Haskell Platform eventually (and have all packages there use them).
+1! Cheers, -Ryan
On 3 November 2011 14:56, Ryan Newton
Aside: The problem with collections is that we don't have the programming language means to do this well yet (although soon!). The issue is that we want to declare a type class where the context of the methods depends on the instance e.g. class MapLike m where type Ctx :: Context -- Can't do this today! insert Ctx => k -> v -> m -> m Java et all cheats in their container hierarchy by doing unsafe casts (i.e. they never solved this problem)!
Ah, interesting. Is there a proposal to do this?
Even better: it's already implemented by Max Bolingbroke and will be in ghc-7.4! See: http://hackage.haskell.org/trac/ghc/wiki/Status/Oct11 So be patient and wait for your Christmas present ;-) Bas
participants (3)
-
Bas van Dijk -
Johan Tibell -
Ryan Newton