A world without orphans

An orphan instance is where you have a situation like this:

module Foo where
  class Foo a where
    foo :: a

module Bar where
  newtype Bar = Bar Int

module Baz where
  instance Foo Bar where
    foo = Bar 0

I.e., a class is instantiated with a type in a module where neither the class nor the type was declared. GHC issues a warning in this case, because it has to put that instance in a global table that is scanned for every compilation unit. In non-orphan cases, it knows that the instance will be in scope, because at the point of usage, both the class an the type are in scope, so the instance came with one of them.

What happens if we change that warning into an error? No orphan instances allowed!

Wonderful things, that’s what. The most notable, in my opinion, being that the very common desire for superclassing is now perfectly acceptable (modulo the many implementation concerns). For example:

class Additive a where
    (^+^) :: a -> a -> a
instance (Num a) => Additive a where
    (^+^) = (+)

The problem used to be that, let’s say someone made a type Foo and instantiated it as Num and as Additive. Which Additive instance do we use, the one here or the one they defined? This problem vanishes if we don’t allow orphan instances, because Additive Foo and Num Foo would have to be instantiated in the same place, when Additive is in scope, and thus this superclass instance is in scope. So the collision would be caught modularly at compile time (that is, it’s not when you just happen to use these two modules together that the universe explodes, it’s precisely where the problem occurs). The module that defined Foo would be informed that he is not allowed to define an Additive instance, because one was already defined for him.

About these ads

13 thoughts on “A world without orphans

  1. But sometimes using a non-orphan instance will totally break modularity, and perhaps force you to change packages you are not the owner of.

  2. Here’s a concrete example:

    In hackage there’s package with a class for pretty printing (with the SPJ-RMJH combinators). It contains a class definition and instances for all relevant prelude types.

    In hackage there’s a package for JSON, it has a type representing JSON expressions. The type belongs to all relevant prelude classes.

    Now I want to use both packages, and I want to be able to pretty print JSON data. It feels totally wrong for me to go in and change either of the packages. Nor do I think they should be changed, because they are totally unrelated. I just happened to want to use both in a new way.

    There is no way that packages that introduce new general concepts (pretty printing, JSON) will be able to include all instances that make sense. Doing so would introduce spurious package dependencies.

  3. I’m not sure I understand the problem here.

    If it is legal to use these two systems together in the same third module, then that third module’s compilation unit seems to be a good place to determine that, and if there is going to be an error, then again, it seems like that’s an error in that third module.

  4. augustss: But adding your own instance is also completely non-modular, because someone else might have done it too. The obvious, though clunky, answer is to force you to use a newtype wrapper.

  5. Why is it non-modular?

    If someone else ads their own instance, as long as the instances are never visible in the same module, there should be no problem.

    I do think you’d need to extend the module syntax so that instance exporting/importing could be controlled.

  6. Crutcher: precisely – you need some extension to make orphan instances behave in a modular fashion.

  7. Sorry, using a newtype wrapper is too clunky for my taste. I’d rather take the chance that someone else has added an instance and fix that problem when it occurs.

  8. augustss: sure, and that’s probably what most people including me would do. But the fact is that having orphan instances does break modularity, so modularity concerns contribute to both sides of the argument :-)

    Perhaps with a more powerful newtype the clunkiness can be removed. If we could import a module translating all instances of a specified type into a newtype, including lifting the data constructors appropriately, then we have a potential alternative to named/export-limited instances that does make banning orphan instances feasible.

  9. Ganesh: But even with some magic lifting to a new type you would have trouble, because the new type would not be equal to the old. So places that use the old type would need some conversion to work with the new type. Unless that’s automagic too (and then I’d get nervous).

    I think Haskell’s unnamed instances has some fundamental problems, and I don’t know how to solve them. But I know outlawing orphans is not the solution.

  10. augustss: the automagic conversion between old and new would happen precisely at the import statements for functions that use the old type. I don’t think that’d require any type system magic. You could also do the same in reverse when exporting functions, I guess.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s