milessabin/export-hook

Minimal infrastructure for type class providers to support the inclusion of derived, subclass and other orphan instances in their implicit scope.

export-hook: minimal dependency support for expanding type class implicit scope

This project provides minimal infrastructure to support the inclusion of derived, subclass and other orphan instances in the implicit scope of a type class without imposing heavyweight dependencies on the type class provider.

What are "orphan" type class instances?

An orphan type class instance is a type class instance which is defined outside its implicit scope. To understand this we first need to review a few details of how the scala compiler resolves implicit parameters ...

Implicit definitions are resolved to satisfy implicit parameters in two ways,

1. by searching for a matching definition in the current or an enclosing scope or via an import.
2. by searching for a matching definition in the implicit scope.

The implicit scope of a type T consists of all companion objects of the types that are associated with it. To a first approximation the types associated with T are all the types that are mentioned in T. So, for example, the implicit scope of Functor[List] includes the companion object of Functor and the companion object of List. The full set of rules is more complicated and can be found in section 7.2 of the Scala Language Reference.

When the compiler is resolving an implicit parameter it will first look for definitions using strategy (1) above: implicit definitions which are directly accessible in the current or an enclosing scope, or via an import will be consulted first and selected according to the normal overload resolution rules.

The compiler will only use strategy (2), searching the implicit scope, if no suitable implicit definitions are found using strategy (1). Or, to put it another way, directly accessible implicit definitions will always trump implicit definitions in the implicit scope. Eugene Yokota has an excellent writeup of the mechanics here.

As a general rule we prefer implicit definitions to be available without needing explicit imports so, by and large, it's preferable to define type class instances in the implicit scope, ie. within the companion object of the type class trait, or within the companion object of the type for which we're defining the instance.

For example, given the Functor type class and some type Foo, we would prefer to define the instance Functor[Foo] in either the companion object of Functor or the companion object of Foo. In this case, whenever Functor and Foo are visible, Functor[Foo] can be implicitly resolved without any further imports.

Conversely, an implicit definition which is defined outside its implicit scope will only be resolved as an implicit parameter if it is directly accessible, ie. if it is imported or defined in the current or an enclosing scope. This would be the case if the instance Functor[Foo] were provided by a third-party, neither in the companion object of Functor nor in the companion object of Foo. Type class instances defined in this way are orphans.

Why are orphans a problem for automatically derived and subclass type class instances?

Pulling the above together we can conclude,

• Orphan type class instances must be imported (because they're not in the implicit scope).
• Orphan type class instances will trump non-orphan type class instances (because directly accessible implicits are found during the first phase of implicit resolution before the implicit scope is consulted).

For many purposes these are exacly the semantics we want: orphan type class instances are often used locally to provide an alternative to the default instance of a type class which has been provided for a given type. In this scenario we want the directly accessible local definition to trump the definitions in the implicit scope.

However, these aren't the semantics we want for automatically derived or subclass type class instances. Here we want hand written instances, which will typically be defined in the implicit scope, to take precedence over derived instances. This directly conflicts with the need to import orphans.

To complicate matters still further, it's common for there to be a default type class instance for a very general type such as AnyRef or Any. This will typically be defined as a lowest priority instance in the companion object of the type class trait. We will want derived and subclass instances to have a higher priority than these very general instances.

In other words, we want derived and subclass instances to have a priority in-between hand-crafted specific instances (in the implicit scope) and very general fallback instances (also in the implicit scope). This is very difficult to achieve with orphan instances.

Dealing with derived, subclass and other orphans

shapeless has an evolving set of mechanisms which help to deal with this problem, but it would be even better if we didn't have to deal with it at all, and not produce orphan instances in the first place. One way of achieving this would be for projects which provide type classes to also publish derived and subclass instances directly. However, in the derived case this forces a dependency on shapeless onto those projects, which might be too heavyweight for them, and it limits shapeless's ability to evolve independently; and in the subclass case it couples subclasses and superclasses which can be problematic across module boundaries.

This project is a proof of concept of an alternative mechanism, an export hook, which allows derived, subclass and other orphan instances to be inserted into the implicit scope of a type class with the appropriate priority without requiring either a shapeless dependency or coupling between subclasses and superclasses, hence respecting module boundaries.

Instead the only dependency is this project, which has a very small runtime footprint and no further dependencies. Value classes and macro inlining have been used to eliminate all runtime overhead relative to directly importing external instances.

The project providing type classes, and the other parties, follow the conventions below (Encoder, Decoder, Codec, DerivedEncoder and DerivedDecoder are example user type classes) ...

The type class provider

The participating type class provider includes a hook for exporters of instances such as type class derivers or subclasses. That implies a dependency on this project, and a hook trait as part of the stack of prioritized companion object traits,

import export._

trait Encoder[T] {
  // Type class defns ...
}

object Encoder extends EncoderLowPriority {
  // Instances which should be higher priority than derived
  // or subclass instances should be defined here ...
}

// Derived, subclass and other instances of Encoder are automatically included here ...
@imports[Encoder]
trait EncoderLowPriority {
  // Instances which should be lower priority than imported
  // instances should be defined here ...
}

(Below we assume a similar set of definitions for the Decoder type class).

The provider of derived, subclass or other instances

A type class deriver provides instances for the requested types using shapeless or any other suitable mechanism and indicates that they are to be exported by adding the @exports annotation to its companion object,

import export._, shapeless._

// Automatically derive instances of Encoder[T] for all T with a shapeless
// Generic instance

trait DerivedEncoder[T] extends Encoder[T]

@exports
object DerivedEncoder {
  implicit def hnil: DerivedEncoder[HNil] = ...

  implicit def hcons[H, T <: HList]
    (implicit hd: Encoder[H], tl: Lazy[DerivedEncoder[T]]): DerivedEncoder[H :: T] = ...

  implicit def cnil: DerivedEncoder[CNil] = ...

  implicit def ccons[H, T <: Coproduct]
    (implicit hd: Encoder[H], tl: Lazy[DerivedEncoder[T]]): DerivedEncoder[H :+: T] = ...

  implicit def gen[T, R]
    (implicit gen: Generic.Aux[T, R], mtcr: DerivedEncoder[R]): DerivedEncoder[T] = ...
}

(Below we assume a similar set of definitions for the DerivedDecoder type class).

A type class subclass provides instances which are automatically instances of their superclasses by virtue of the subtype relationship,

import export._

trait Codec[T] extends Encoder[T] with Decoder[T]

@exports(Subclass)
object Codec {
  implicit val fooInst: Codec[Foo] = ...
}

Instances can be exported with different relative priorities. In the derivation example they are exported with the default priority, which is appropiate for instances constructed using type class derivation. In the subclass example we specify the Subclass priority explicitly as an argument to the @export annotation. The available instance priorities are, in order from highest to lowest priority,

• HighPriority

  A catch-all priority higher than any other defined here.

• Orphan

  User provided explicit orphan instances.

• Subclass

  Instances provided by subclasses, ie. a Semigroup[T] provided by a Monoid[T].

• Algebraic

  Instances provided by a combination of instances of other classes, combined according to their characteristic laws, ie. a Monoid[T] provided by a combination of a Semigroup[T] with a Zero[T].

• Instantiated

  Instances provided by instantiating a higher kinded instance at some first order type, ie. a Monoid[List[Int]] provided by instantiating MonoidK[List] at Int.

• Generic (default priority if not explicitly specified)

  Instances provided by type class derivation using shapeless or any other suitable mechanism.

• Default

  Instances which are acceptable in the last resort.

• LowPriority

  A catch-all priority lower than any other defined here.

The type class user

The type class user should import both the type class and the type class deriver or subclass exports,

import Encoder
import DerivedEncoder.exports._  // for derived instances
import Codec.exports._           // for subclass instances

If the type class user doesn't want derived or subclass instances they simply omit the corresponding import, in which case they will only see underived base instances.

Locally modifying the instance priority ordering

The priority ordering of the instance categories is a reasonable default which should do what the user expects in almost all circumstances. However, it's important to have an escape hatch for the rare cases where we need to do something different. export-hook provides a mechanism for defining a local priority ordering via an implicit definition of type ExportPriority. The local ordering will be in force only where that implicit definition is in scope,

import export._

object CustomPrioritization {
  implicit val priority =
    ExportPriority[
      ExportHighPriority,
      ExportOrphan,
      ExportSubclass,
      ExportAlgebraic,
      ExportGeneric,      // give generic instances a higher priority than instances
      ExportInstantiated, // constructed from higher kinded instances
      ExportDefault,
      ExportLowPriority
    ]
}

object ScopeWithDefaultPriority {
  // Here a Monoid[List[Int]] constructed from a MonoidK[List] will be
  // selected using the default prioritization ...

  implicitly[Monoid[List[Int]]]
}

object ScopeWithCustomPriority {
  import CustomPrioritization._ // instance of ExportPriority now in scope ...

  // Here a Monoid[List[Int]] provided by type class derivation will be
  // selected using the our custom prioritization ...

  implicitly[Monoid[List[Int]]]
}

Bundling and reexporting type class instances

It is sometimes convenient to make multiple orphan type class instances available via a single import. This is supported via the @reexport annotation. In the example below all the instances defined by DerivedEncoder and DerivedDecoder are made available in the current scope by a single import,

trait DerivedEncoder[T] extends Encoder[T]
@exports
object DerivedEncoder {
  // Encoder derivation here ...
}

trait DerivedDecoder[T] extends Decoder[T]
@exports
object DerivedDecorer {
  // Decoder derivation here ...
}

// Reexport instances of both type classes via a single object
@reexports[DerivedEncoder, DerivedDecoder]
object derivedcodecs

// Client code ...

import derivedcodecs._ // single import

// Instances of both DerivedEncoder and DerivedDecoder are now available via
// the implicit scope of Encoder and Decoder ...

Reexported instances will have the same priority that they were initially exported with.

Exporting and reexporting individual instances

Sometimes it's a little heavyweight to create a new subclass simply to be able to export a handful of ad hoc instances. In this case individual instance definitions can be exported by using a val/method level @export definition marking the definition for export and providing a priority,

@exports
object InstantiatedEmptyK {
  @export(Instantiated)
  implicit def instantiate[F[_], T](implicit ekf: EmptyK[F]): Empty[F[T]] = ekf.synthesize[T]
}

Here we synthesize an instance of the Alleycats Empty type class from an instance of the higher-kinded EmptyK type class. The resulting definition is exported with the Instantiated priority and made available by importing in the usual way,

import InstantiatedEmptyK.exports._

Empty[List[Int]] // synthesized from EmptyK[List]

These individual instances can also be bundled and reexported,

@reexports(InstantiatedEmptyK)
object emptykinst

which allows imports of the form,

import emptykinst._

Empty[List[Int]] // synthesized from EmptyK[List]

Exporting with type refinements

In order to avoid ambiguities with a blanket export, each individual definition will need an @export added.

trait RefinedExporter[T] extends Exporter[T]{
  type Out

  def wrap(t: T): Out
}

@exports
object RefinedExporter{
  type Aux[T, Out0] = RefinedExporter[T]{ type Out = Out0 }

  @export
  implicit def refined[T]: Aux[T, //rest of definition ...
}

Current status

This is a young project and we are keen to get input from anyone who finds it useful ... please create issues here or hop on the gitter channel. Discussion is also welcome on the shapeless and cats gitter channels ... please let us know what you think.

Using export-hook

Binary release artefacts are published to the Sonatype OSS Repository Hosting service and synced to Maven Central. Snapshots of the master branch are built using Travis CI and automatically published to the Sonatype OSS Snapshot repository. To include the Sonatype repositories in your SBT build you should add,

resolvers ++= Seq(
  Resolver.sonatypeRepo("releases"),
  Resolver.sonatypeRepo("snapshots")
)

Builds are available for Scala 2.12.x, 2.11.x and 2.10.x for Scala JDK and Scala.js. The main line of development for export-hook 1.1.0 is Scala 2.12.0 supported via the macro paradise compiler plugin.

scalaVersion in ThisBuild := "2.12.3"

libraryDependencies ++= Seq(
  "org.typelevel" %% "export-hook" % "1.2.0",
  "org.scala-lang" % "scala-reflect" % scalaVersion.value % "provided",
  compilerPlugin("org.scalamacros" % "paradise" % "2.1.0" cross CrossVersion.patch)
)

export-hook requires SBT 0.13.13 or later, and will cause a NullPointerException to be thrown at compile time for earlier versions (see issue #13).

The SBT version can be configured in /project/build.properties:

sbt.version=0.13.16

Binary compatibility

As of version 1.1.0 export-hook uses MiMa to verify binary compatibility within minor versions. export-hook is binary compatible within minor versions from 1.1.0 onwards.

Building export-hook

export-hook is built with SBT 0.13.13 or later, and its master branch is built with Scala 2.12.0 by default.

Participation

The export-hook project supports the Scala Code of Conduct and wants all of its channels (Gitter, github, etc.) to be welcoming environments for everyone.

Projects using export-hook

• circe
• kittens
• tabulate

Contributors

• Age Mooij age.mooij@gmail.com @agemooij
• Alistair Johnson alistair.johnson@johnsonusm.com @AlistairUSM
• Miles Sabin miles@milessabin.com @milessabin
• Nicolas Rinaudo nicolas@nrinaudo.com @NicolasRinaudo
• Your name here :-)