GHC Handbook

Chapter 5

Classes, instances and deriving

Where a class declaration becomes a record of functions, an instance becomes a value of that record, and `deriving` writes code you never see: the machinery that makes overloading disappear before Core.

Where this lives in the tree

Type classes are the feature that most distinguishes Haskell, and the one whose implementation is least visible from the outside. By the time your program reaches Core there are no classes at all: only records, ordinary functions, and ordinary arguments.

This chapter is how that erasure happens.

Dictionaries

A class becomes a data type; its methods become fields. Show a is, after elaboration, a record holding showsPrec, show and showList. An instance becomes a value of that record. A constraint Show a => becomes a function argument carrying it.

You saw the result in the parser chapter without comment:

describe :: forall a. Show a => a -> String
describe
  = \ (@a) ($dShow :: Show a) (x :: a) ->
      ++ (unpackCString# "value: "#) (show $dShow x)

$dShow is the dictionary. show $dShow x is a field selection followed by an application. Nothing about that is class-specific any more, which is precisely the point, because it means the whole optimiser downstream needs to know nothing about classes.

Single-method classes get a further simplification: rather than a one-field record, the dictionary is the method, via a newtype. It is why a single-method class often costs nothing at runtime.

Solving a dictionary constraint

When the solver meets a Wanted Show Int, it consults the instance environment for a match. Success produces evidence (the dictionary) and fills the hole.

Superclasses complicate this pleasantly. If you have Ord a, you also have Eq a, because Ord declares Eq as a superclass, and the Ord dictionary physically contains the Eq one. Extracting it is a field selection:

Note [Solving superclass constraints] GHC/Tc/TyCl/Instance.hs:1700 
How do we ensure that every superclass witness in an instance declaration
is generated by one of (sc1) (sc2) or (sc3) in Note [Recursive superclasses]?
Answer:

  * The "given" constraints of an instance decl have CtOrigin of
    (GivenOrigin (InstSkol head_size)), where head_size is the
    PatersonSize of the head of the instance declaration.  E.g. in
        instance D a => C [a]
    the `[G] D a` constraint has a CtOrigin whose head_size is the
    PatersonSize of (C [a]).

  * When we make a superclass selection from a Given (transitively)
    we give it a CtOrigin of (GivenSCOrigin skol_info sc_depth blocked).

    The 'blocked :: Bool' flag says if the superclass can be used to
    solve a superclass Wanted. The new superclass is blocked unless:

       it is the superclass of an unblocked dictionary (wrinkle (W1)),
       that is Paterson-smaller than the instance head.

    This is implemented in GHC.Tc.Solver.Dict.mk_strict_superclasses
    (in the mk_given_loc helper function).

  * Superclass "Wanted" constraints have CtOrigin of (ScOrigin NakedSc)
    The 'NakedSc' says that this is a naked superclass Wanted; we must
    be careful when solving it.
Show the rest of this Note (64 more lines) 
  * (sc1) When we rewrite such a wanted constraint, it retains its
    origin.  But if we apply an instance declaration, we can set the
    origin to (ScOrigin NotNakedSc), thus lifting any restrictions by
    making prohibitedSuperClassSolve return False. This happens
    in GHC.Tc.Solver.Dict.checkInstanceOK.

  * (sc2) ScOrigin wanted constraints can't be solved from a
    superclass selection, except at a smaller type.  This test is
    implemented by GHC.Tc.Solver.InertSet.prohibitedSuperClassSolve

Note [Silent superclass arguments] (historical interest only)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
NB1: this note describes our *old* solution to the
     recursive-superclass problem. I'm keeping the Note
     for now, just as institutional memory.
     However, the code for silent superclass arguments
     was removed in late Dec 2014

NB2: the silent-superclass solution introduced new problems
     of its own, in the form of instance overlap.  Tests
     SilentParametersOverlapping, T5051, and T7862 are examples

NB3: the silent-superclass solution also generated tons of
     extra dictionaries.  For example, in monad-transformer
     code, when constructing a Monad dictionary you had to pass
     an Applicative dictionary; and to construct that you need
     a Functor dictionary. Yet these extra dictionaries were
     often never used.  Test T3064 compiled *far* faster after
     silent superclasses were eliminated.

Our solution to this problem "silent superclass arguments".  We pass
to each dfun some ``silent superclass arguments’’, which are the
immediate superclasses of the dictionary we are trying to
construct. In our example:
       dfun :: forall a. C [a] -> D [a] -> D [a]
       dfun = \(dc::C [a]) (dd::D [a]) -> DOrd dc ...
Notice the extra (dc :: C [a]) argument compared to the previous version.

This gives us:

     
     DFun Superclass Invariant
     ~~~~~~~~~~~~~~~~~~~~~~~~
     In the body of a DFun, every superclass argument to the
     returned dictionary is
       either   * one of the arguments of the DFun,
       or       * constant, bound at top level
     

This net effect is that it is safe to treat a dfun application as
wrapping a dictionary constructor around its arguments (in particular,
a dfun never picks superclasses from the arguments under the
dictionary constructor). No superclass is hidden inside a dfun
application.

The extra arguments required to satisfy the DFun Superclass Invariant
always come first, and are called the "silent" arguments.  You can
find out how many silent arguments there are using Id.dfunNSilent;
and then you can just drop that number of arguments to see the ones
that were in the original instance declaration.

DFun types are built (only) by MkId.mkDictFunId, so that is where we
decide what silent arguments are to be added.

The uncomfortable case is when a local Given and a global instance both match. The chapter on the solver quoted Instance and Given overlap for this reason: picking the instance would be wrong, because the caller may be passing a different dictionary for the same type.

Deriving

deriving is code generation. GHC writes out an instance declaration and typechecks it as though you had written it, which is why derived instances can fail with ordinary type errors.

There is more than one way to derive, and choosing between them is explicit:

Note [Deriving strategies] GHC/Tc/Deriv.hs:2250 
GHC has a notion of deriving strategies, which allow the user to explicitly
request which approach to use when deriving an instance (enabled with the
-XDerivingStrategies language extension). For more information, refer to the
original issue (#10598) or the associated wiki page:
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/deriving-strategies

A deriving strategy can be specified in a deriving clause:

    newtype Foo = MkFoo Bar
      deriving newtype C

Or in a standalone deriving declaration:

    deriving anyclass instance C Foo

-XDerivingStrategies also allows the use of multiple deriving clauses per data
declaration so that a user can derive some instance with one deriving strategy
and other instances with another deriving strategy. For example:

    newtype Baz = Baz Quux
      deriving          (Eq, Ord)
      deriving stock    (Read, Show)
      deriving newtype  (Num, Floating)
      deriving anyclass C

Currently, the deriving strategies are:

* stock: Have GHC implement a "standard" instance for a data type, if possible
  (e.g., Eq, Ord, Generic, Data, Functor, etc.)
Show the rest of this Note (26 more lines) 
* anyclass: Use -XDeriveAnyClass

* newtype: Use -XGeneralizedNewtypeDeriving

* via: Use -XDerivingVia

The latter two strategies (newtype and via) are referred to as the
"coerce-based" strategies, since they generate code that relies on the `coerce`
function. See, for instance, GHC.Tc.Deriv.Infer.inferConstraintsCoerceBased.

The former two strategies (stock and anyclass), in contrast, are
referred to as the "originative" strategies, since they create "original"
instances instead of "reusing" old instances (by way of `coerce`).
See, for instance, GHC.Tc.Deriv.Utils.checkOriginativeSideConditions.

If an explicit deriving strategy is not given, GHC has an algorithm it uses to
determine which strategy it will actually use. The algorithm is quite long,
so it lives in the Haskell wiki at
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/deriving-strategies
("The deriving strategy resolution algorithm" section).

Internally, GHC uses the DerivStrategy datatype to denote a user-requested
deriving strategy, and it uses the DerivSpecMechanism datatype to denote what
GHC will use to derive the instance after taking the above steps. In other
words, GHC will always settle on a DerivSpecMechnism, even if the user did not
ask for a particular DerivStrategy (using the algorithm linked to above).

The four strategies do genuinely different things. stock generates real code per class, known to the compiler. newtype coerces an existing instance through a newtype (zero cost, since the representations are identical). anyclass takes the class’s default methods. via coerces through a type you nominate.

For inferred contexts there is a further problem: what constraints should the generated instance require? deriving Show for data T a = MkT a needs Show a, but working that out in general means running the solver over the generated code:

Note [Inferring the instance context] GHC/Tc/Deriv/Infer.hs:471 
There are two sorts of 'deriving', as represented by the two constructors
for DerivContext:

  * InferContext mb_wildcard: This can either be:
    - The deriving clause for a data type.
        (e.g, data T a = T1 a deriving( Eq ))
      In this case, mb_wildcard = Nothing.
    - A standalone declaration with an extra-constraints wildcard
        (e.g., deriving instance _ => Eq (Foo a))
      In this case, mb_wildcard = Just loc, where loc is the location
      of the extra-constraints wildcard.

    Here we must infer an instance context,
    and generate instance declaration
      instance Eq a => Eq (T a) where ...

  * SupplyContext theta: standalone deriving
      deriving instance Eq a => Eq (T a)
    Here we only need to fill in the bindings;
    the instance context (theta) is user-supplied

For the InferContext case, we must figure out the
instance context (inferConstraintsStock). Suppose we are inferring
the instance context for
    C t1 .. tn (T s1 .. sm)
There are two cases
Show the rest of this Note (34 more lines) 
  * (T s1 .. sm) :: *         (the normal case)
    Then we behave like Eq and guess (C t1 .. tn t)
    for each data constructor arg of type t.  More
    details below.

  * (T s1 .. sm) :: * -> *    (the functor-like case)
    Then we behave like Functor.

In both cases we produce a bunch of un-simplified constraints
and them simplify them in simplifyInstanceContexts; see
Note [Simplifying the instance context].

In the functor-like case, we may need to unify some kind variables with * in
order for the generated instance to be well-kinded. An example from #10524:

  newtype Compose (f :: k2 -> *) (g :: k1 -> k2) (a :: k1)
    = Compose (f (g a)) deriving Functor

Earlier in the deriving pipeline, GHC unifies the kind of Compose f g
(k1 -> *) with the kind of Functor's argument (* -> *), so k1 := *. But this
alone isn't enough, since k2 wasn't unified with *:

  instance (Functor (f :: k2 -> *), Functor (g :: * -> k2)) =>
    Functor (Compose f g) where ...

The two Functor constraints are ill-kinded. To ensure this doesn't happen, we:

  1. Collect all of a datatype's subtypes which require functor-like
     constraints.
  2. For each subtype, create a substitution by unifying the subtype's kind
     with (* -> *).
  3. Compose all the substitutions into one, then apply that substitution to
     all of the in-scope type variables and the instance types.

Stock deriving also needs helper bindings (comparison tags, enumeration indices) that must not collide with anything the user wrote:

Note [Auxiliary binders] GHC/Tc/Deriv/Generate.hs:2758 
We often want to make top-level auxiliary bindings in derived instances.
For example, derived Ix instances sometimes generate code like this:

  data T = ...
  deriving instance Ix T

  ==>

  instance Ix T where
    range (a, b) = map tag2con_T [dataToTag# a .. dataToTag# b]

  $tag2con_T :: Int -> T
  $tag2con_T = ...code....

Note that multiple instances of the same type might need to use the same sort
of auxiliary binding. For example, $tag2con is used not only in derived Ix
instances, but also in derived Enum instances:

  deriving instance Enum T

  ==>
Show the rest of this Note (192 more lines) 
  instance Enum T where
    toEnum i = tag2con_T i

  $tag2con_T :: Int -> T
  $tag2con_T = ...code....

How do we ensure that the two usages of $tag2con_T do not conflict with each
other? We do so by generating a separate $tag2con_T definition for each
instance, giving each definition an Exact RdrName with a separate Unique to
avoid name clashes:

  instance Ix T where
    range (a, b) = map tag2con_T{Uniq2} [dataToTag# a .. dataToTag# b]

  instance Enum T where
    toEnum a = $tag2con_T{Uniq2} a

   $tag2con_T{Uniq1} and $tag2con_T{Uniq2} are Exact RdrNames with
   underlying System Names

   $tag2con_T{Uniq1} :: Int -> T
   $tag2con_T{Uniq1} = ...code....

   $tag2con_T{Uniq2} :: Int -> T
   $tag2con_T{Uniq2} = ...code....

Note that:

* This is /precisely/ the same mechanism that we use for
  Template Haskell–generated code.
  See Note [Binders in Template Haskell] in GHC.ThToHs.
  There we explain why we use a 'System' flavour of the Name we generate.

* See "Wrinkle: Reducing code duplication" for how we can avoid generating
  lots of duplicated code in common situations.

* See "Wrinkle: Why we sometimes do generated duplicate code" for why this
  de-duplication mechanism isn't perfect, so we fall back to CSE
  (which is very effective within a single module).

* Note that the "_T" part of "$tag2con_T" is just for debug-printing
  purposes. We could call them all "$tag2con", or even just "aux".
  The Unique is enough to keep them separate.

  This is important: we might be generating an Eq instance for two
  completely-distinct imported type constructors T.

At first glance, it might appear that this plan is infeasible, as it would
require generating multiple top-level declarations with the same OccName. But
what if auxiliary bindings /weren't/ top-level? Conceptually, we could imagine
that auxiliary bindings are /local/ to the instance declarations in which they
are used. Using some hypothetical Haskell syntax, it might look like this:

  let {
    $tag2con_T{Uniq1} :: Int -> T
    $tag2con_T{Uniq1} = ...code....

    $tag2con_T{Uniq2} :: Int -> T
    $tag2con_T{Uniq2} = ...code....
  } in {
    instance Ix T where
      range (a, b) = map tag2con_T{Uniq2} [dataToTag# a .. dataToTag# b]

    instance Enum T where
      toEnum a = $tag2con_T{Uniq2} a
  }

Making auxiliary bindings local is key to making this work, since GHC will
not reject local bindings with duplicate names provided that:

* Each binding has a distinct unique, and
* Each binding has an Exact RdrName with a System Name.

Even though the hypothetical Haskell syntax above does not exist, we can
accomplish the same end result through some sleight of hand in renameDeriv:
we rename auxiliary bindings with rnLocalValBindsLHS. (If we had used
rnTopBindsLHS instead, then GHC would spuriously reject auxiliary bindings
with the same OccName as duplicates.) Luckily, no special treatment is needed
to typecheck them; we can typecheck them as normal top-level bindings
(using tcTopBinds) without danger.


Wrinkle: Reducing code duplication


While the approach of generating copies of each sort of auxiliary binder per
derived instance is simpler, it can lead to code bloat if done naïvely.
Consider this example:

  data T = ...
  deriving instance Eq T
  deriving instance Ord T

  ==>

  instance Ix T where
    range (a, b) = map tag2con_T{Uniq2} [dataToTag# a .. dataToTag# b]

  instance Enum T where
    toEnum a = $tag2con_T{Uniq2} a

  $tag2con_T{Uniq1} :: Int -> T
  $tag2con_T{Uniq1} = ...code....

  $tag2con_T{Uniq2} :: Int -> T
  $tag2con_T{Uniq2} = ...code....

$tag2con_T{Uniq1} and $tag2con_T{Uniq2} are blatant duplicates of each other,
which is not ideal. Surely GHC can do better than that at the very least! And
indeed it does. Within the genAuxBinds function, GHC performs a small CSE-like
pass to define duplicate auxiliary binders in terms of the original one. On
the example above, that would look like this:

  $tag2con_T{Uniq1} :: Int -> T
  $tag2con_T{Uniq1} = ...code....

  $tag2con_T{Uniq2} :: Int -> T
  $tag2con_T{Uniq2} = $tag2con_T{Uniq1}

(Note that this pass does not cover all possible forms of code duplication.
See "Wrinkle: Why we sometimes do generate duplicate code" for situations
where genAuxBinds does not deduplicate code.)

To start, genAuxBinds is given a list of AuxBindSpecs, which describe the sort
of auxiliary bindings that must be generates along with their RdrNames. As
genAuxBinds processes this list, it marks the first occurrence of each sort of
auxiliary binding as the "original". For example, if genAuxBinds sees a
DerivCon2Tag for the first time (with the RdrName $tag2con_T{Uniq1}), then it
will generate the full code for a $tag2con binding:

  $tag2con_T{Uniq1} :: Int -> T
  $tag2con_T{Uniq1} = ...code....

Later, if genAuxBinds sees any additional DerivCon2Tag values, it will treat
them as duplicates. For example, if genAuxBinds later sees a DerivCon2Tag with
the RdrName $tag2con_T{Uniq2}, it will generate this code, which is much more
compact:

  $tag2con_T{Uniq2} :: Int -> T
  $tag2con_T{Uniq2} = $tag2con_T{Uniq1}

An alternative approach would be /not/ performing any kind of deduplication in
genAuxBinds at all and simply relying on GHC's simplifier to perform this kind
of CSE. But this is a more expensive analysis in general, while genAuxBinds can
accomplish the same result with a simple check.


Wrinkle: Why we sometimes do generate duplicate code


It is worth noting that deduplicating auxiliary binders is difficult in the
general case. Here are two particular examples where GHC cannot easily remove
duplicate copies of an auxiliary binding:

1. When derived instances are contained in different modules, as in the
   following example:

     module A where
       data T = ...
     module B where
       import A
       deriving instance Ix T
     module C where
       import B
       deriving instance Enum T

   The derived Eq and Enum instances for T make use of $tag2con_T, and since
   they are defined in separate modules, each module must produce its own copy
   of $tag2con_T.

2. When derived instances are separated by TH splices (#18321), as in the
   following example:

     module M where

     data T = ...
     deriving instance Ix T
     $(pure [])
     deriving instance Enum T

   Due to the way that GHC typechecks TyClGroups, genAuxBinds will run twice
   in this program: once for all the declarations before the TH splice, and
   once again for all the declarations after the TH splice. As a result,
   $tag2con_T will be generated twice, since genAuxBinds will be unable to
   recognize the presence of duplicates.

These situations are much rarer, so we do not spend any effort to deduplicate
auxiliary bindings there. Instead, we focus on the common case of multiple
derived instances within the same module, not separated by any TH splices.
(This is the case described in "Wrinkle: Reducing code duplication".) In
situation (1), we can at least fall back on GHC's simplifier to pick up
genAuxBinds' slack.

Seeing it happen

What you wrote.

-- | Type classes are the clearest demonstration that Core is a *different*
-- language from Haskell, not a lightly-desugared version of it.
--
-- Watch `describe` acquire an extra argument between the typechecked output and
-- the desugared Core: the class constraint `Show a =>` becomes an ordinary
-- value parameter holding a dictionary of methods.
module Classes where

class Container f where
  empty :: f a
  insert :: a -> f a -> f a

newtype Stack a = Stack [a]

instance Container Stack where
  empty = Stack []
  insert x (Stack xs) = Stack (x : xs)

describe :: Show a => a -> String
describe x = "value: " ++ show x

twice :: Container f => a -> f a -> f a
twice x c = insert x (insert x c)
The Container class and its Stack instance. In Core, the class is a record and the instance is a value, $fContainerStack, passed explicitly wherever it is needed.

Look for $dContainer in twice. The constraint Container f => in the source has become a value parameter, and the two insert calls select from it.

Then compare Core (optimised): for a known concrete type the simplifier can often see which dictionary arrives, inline the selection, and leave a direct call. That is the specialiser’s doing, and the reason class-heavy Haskell is not automatically slow.

Reading the source yourself

  1. GHC/Core/Class.hs: small, and shows exactly what a class is once elaborated. Start here; everything else is easier afterwards.
  2. GHC/Tc/Instance/Class.hs for matching a Wanted against instances.
  3. GHC/Tc/TyCl/Instance.hs for what an instance declaration turns into, superclass evidence included.
  4. GHC/Tc/Deriv/* last. Deriv.hs chooses the strategy, Deriv/Generate.hs writes the code, Deriv/Infer.hs works out the context.

-ddump-deriv shows exactly what deriving generated, which is the quickest way to understand a confusing error in code you did not write.