This Blog is about the Aux Pattern as seen all over the Shapeless library.
It is also a slide deck for a talk givn at Scalasyd April 2017.
To switch between modes press a number as follows :
- ‘1’ -> Doc mode:
- shows the document as intended.
- ‘2’ -> Deck mode, see the slides
- see the slides
- ‘4’ -> Lecture Mode
- enter zooms current navigated to section
- click zooms div or block clicked
Arrow keys navigate to next or previous section. or slide
The Rise (and hopefully fall) of
The Aux Pattern
2
. Press Esc
to get back to document view. Left and Right arrow keys to navigate.
See suited.js
This Blog is my talk for Scalasyd April 12th 2017. It is about the Aux Pattern as seen all over the Shapeless library.
Intro
- This talk is about Scala
-
Intro
- This talk is about Scala
- Not a Haskel talk dressed up in scala rags.
-
Intro
- This talk is about Scala
- Not a Haskel talk dressed up in scala rags.
- About the scala type system
- dependant types
- type inference
- implicits
Intro
- This talk is about Scala
- Not a Haskel talk dressed up in scala rags.
- About the scala type system
- dependant types
- type inference
- implicits
- About a cluncky work around
Aim
- De-mystify Shapeless code
We’ve all seen code like this:-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Alphabet soup if ever there was some. Hopefully at the end of this, we’ll all be able to read this.
But before I skip on, notice the Aux
all over that code. This is the source of the name of the Aux
pattern.
The Aux Pattern
The first thing to realise is that it is not a Pattern that can apply to a programming paradidm It is really a hack. An elegant hack, but never-the-less a hack. Definatly a hack.
The Aux Hack
The Aux Idiom
To be kinds to it, it has become quite pervasive as a way to work around a problem so I guess I can call it an idiom specific to Scala and its type system.
Being an idom it has become a common way to get stuff done in scala, but what is it solving? To answer that we need a little ramble around the scala type system.
Type inference
First let’s talk about type inference
Type inference
Type inference
- the compiler can work out the type of a thing
Type inference
- the compiler can work out the type of a thing
- without us supplying a clue
Type inference
- the compiler can work out the type of a thing
- without us supplying a clue
- based on info it already has.
A pretty useful feature to have, as I’m sure you’ll agree, as it helps cut down on “Type boiler-plate”, while letting the compiler asset correctness for us.
So let’s look an simple example
Type inference
object InferenceTest1 extends Application {
val x = 1 + 2 * 3 // the type of x is Int
val y = x.toString() // the type of y is String
def succ(x: Int) = x + 1 // method succ returns Int values
}
As we can see the compiler is able to infer some types from the context. The next example shows that even with generic types we can infer types at the call site. I.e. when the specific type is first used.
Type inference
case class MyPair[A, B](x: A, y: B);
object InferenceTest3 extends Application {
def id[T](x: T) = x // return type: T
val p = new MyPair(1, "scala") // type: MyPair[Int, String]
val q = id(1) // type: Int
}
with no hints the compiler knows that p
is a MyPair[Int, String]
and q
is an int
as an a2tion" sometimes mislabled “type annotation”, for example here is the some code with more type ascription than is necessary in scala
Type ascription
def id[T](x: T): T = x
val p: MyPair[Int, String] = new MyPair[Int, String](1, "scala")
val q: Int = id[Int](1)
val b = 2 : Byte
The only necessary ascription here was on on val b
which we want to be a Byte
rather than let the default inference of Int
.
Path Dependent Types
OK no lets switch to another Scala feature, path dependant types
.
Path-dependent types
Path-dependent types
- the type depends on the path
Path-dependent types
- the type depends on the path
- so we can have types that depend on the Object that defines them.
Path-dependent types
- the type depends on the path
- so we can have types that depend on the Object that defines them.
- we can reference these types in out functions and methods.
Why do I care?
let’s see an example
bad example
trait Food {
override def toString(): String
}
object grass extends Food {
override def toString: String = "grass"
}
object dogfood extends Food {
override def toString: String = "dogfood"
}
In good OOP style I’ve used inheritance
to create a type hierarchy.
I can then use these types to define some object instances.
bad example
abstract class BadAnimal {
def eat(fodder: Food): Unit = {
println(s" ${this.getClass} Eating my food: "+ fodder)
}
}
object badfeeder {
def feed(animal: BadAnimal, food: Food): Unit = {
animal.eat(food)
}
}
class Cow extends BadAnimal with Food {
override def toString = "Cow"
}
Now I can use the badfeeder
object to feed Daisy the cow.
bad example, so far so good
val Daisy = new Cow
//Acceptable
badfeeder.feed(Daisy, grass)
bad example, errrm?
val Daisy = new Cow
//naughty
badfeeder.feed(Daisy, dogfood)
bad example, WTF!
val Daisy = new Cow
//totally unacceptable. Canibalism
badfeeder.feed(Daisy, Daisy)
As you can see badfeeder
was allowed by the compiler to turn Daisy into a masochistic canible.
The problem is that the feeder was allowed to give Food
to an BadAnimal
, and Daisy was Food as well as an BadAnimal
.
What we need is that an Animal can only eat food suitable for that animal.
But at the time we declare the Animal supertype we don’t know what is suitable food. The solution is to create an abstract type in Animal that will be specialised by each animal kind when we extend Animal. So as before…
good example (same food)
trait Food {
override def toString(): String
}
object grass extends Food {
override def toString: String = "grass"
}
object dogfood extends Food {
override def toString: String = "dogfood"
}
good example, better Animals
abstract class GoodAnimal {
// path dependent type
type SuitableFood <: Food
def eat(food: SuitableFood): Unit = {
println(s" ${this.getClass} Eating my food: "+ food)
}
}
class Cow extends GoodAnimal with Food {
type SuitableFood = grass.type
}
Now we are saying that an Animal can only eat food that is suitable, we don’t know what that is when we create the
GoodAnimal
class so we make it abstract and give it an Abstract type.
Subclasses can declare what the type is. Notice that we can refer to the abstract type in the method eat.
Now let’s try to define the feed function. We might be tempted to try using the #
operator (type projectionn) to
access the type defined inside the GoodAnimal
…
good example, feeding time..
def feed(animal: GoodAnimal, food: GoodAnimal#SuitableFood): Unit = {
animal.eat(food)
}
good example, wont compile!
def feed(animal: GoodAnimal, food: GoodAnimal#SuitableFood): Unit = {
// OOPS cant do this it says
// expected animal.Suitablefood, actual:GoodAnimal#SuitableFood
//
animal.eat(food)
}
It won’t compile. Carefully reading the error message we see that we need animal.Suitablefood
, notice that this is specific to this animal
object instance!
good example, feeding time..
//
//
//
def feed1(animal: GoodAnimal, food: animal.SuitableFood): Unit = {
animal.eat(food)
}
good example, wont compile!
// OOPs cant resolve symbol animal
// can't re-refer to a param in same parameter list
// type system works left to right
def feed1(animal: GoodAnimal, food: animal.SuitableFood): Unit = {
animal.eat(food)
}
The problem here is that the Scala compiler’s type inferencer expects to be able to resolve all types statically in a parameter list,
but when declaring food
we don’t know yet what the type of actual type of animal is, we only know its abstract supertype.
The compiler has a rule to prevent this problem, as it says in the error, you can't re-refer to a param in same parameter list
This is getting tricky. How can I use this fancy good animal?
The solution is to give the Compiler and type inference system a chance to work it out statically using another scala feature
Multiple parameter lists
good example, multi parameter list
//
//
def feed2(animal: GoodAnimal)( food: animal.SuitableFood): Unit = {
animal.eat(food)
}
good example, multi parameter list
// solution is add a second parameter list now type is known at call site
// type resolution works left to right
def feed2(animal: GoodAnimal)( food: animal.SuitableFood): Unit = {
animal.eat(food)
}
As shown in the previous section, by using multiple parameter lists we can use the type animal.SuitableFood
in the second list because
the compiler will have been able to reason about the type of GoodAnimal
in the first list from its use at the call site.
Now the bad example are impossible.
good example, feeding time..
val Daisy = new Cow
// Acceptable
goodfeeder.feed2(Daisy)(grass)
// naughty
//
//
// totally unacceptable. Canabalism
//
//
good example, feeding time..
val Daisy = new Cow
//Acceptable
goodfeeder.feed2(Daisy)(grass)
// naughty
// wont compile says: expected Cow:SuitableFood, actual dogfood.type
//goodfeeder.feed2(Daisy)(dogfood)
//
//
//
good example, feeding time..
val Daisy = new Cow
//Acceptable
goodfeeder.feed2(Daisy)(grass)
//naughty
// wont compile says: expected Cow:SuitableFood, actual dogfood.type
//goodfeeder.feed2(Daisy)(dogfood)
//totally unacceptable. Canabalism
// wont compile says: expected Cow:SuitableFood, actual GoodAnimal.Daisy.type
// goodfeeder.feed2(Daisy)(Daisy)
The “multiple parameter list” feature is used all over scala and has more than one use. I found a good summary for uses of multiple parameter lists here on stack overflow.
Multiple parameter lists
- Allow us to delay type resolution
- while still allowing call site inference
So far so good.
How About with Type-Classes?
How About with Type-Classes?
- Now we are getting close to what the Aux pattern is about
You will often see this kind of code in scala libraries.
implicit parameter lists (context bound sugar)
def join[A: Monoid](a: A, b: A): A = {
a |+| b
}
the form [S : T]
in the type parameter list is actually syntactic sugar, called context bound
, for this:-
implicit parameter lists
def join[A](a: A, b: A)(implicit ev: Monoid[A]): A = {
a |+| b
}
There is implicit evidence available that a Monaid[A] exists, and so we can use the |+|
function from Monoid, nowing that an implicit converion to Monoid is available.
What if my Typeclass has path dependent types?
What if my Typeclass has path dependent types?
- can I have multiple implicit parameter lists to delay type resolution?
What if my Typeclass has path dependent types?
- can I have multiple implicit parameter lists to delay type resolution?
- no.
What if my Typeclass has path dependant types?
- can I have multiple implicit parameter lists to delay type resolution?
- no.
- s#1t
Scala says no
- to multiple implicit parameter lists
my Magic Typeclass
trait MyTypeClass[T] {
type In
type Out
def doMagic(foo: T, param1: In): Out
}
can’t have stuff like this API
def voodooT: MyTypeClass, In0(implicit ev: MyTypeClass.[T])(implicit out: ev.Out) : ev.Out = { ev.doMagic(foo, sayThis): ev.Out }
not only are there too many implicit param lists but we also have no way to tie the In0
type to ev.In
Aux to the rescue
- we can create a type alias to capture/keep track of the types
Aux to the rescue
object MyTypeClass {
//aux pattern
type Aux[T0, In0, Out0] = MyTypeClass[T0] {type In = In0; type Out = Out0}
// convenience Summoner so I don't need to use instead of `implicitly`
def apply[T](implicit evidence: MyTypeClass[T]): Aux[T, evidence.In, evidence.Out] = evidence
}
So we create a type alias to my type, that allows all the path dependent types to be seen on the outside.
We also create a handy typeclass summoner that an be used instead of implitly when we need it.
Aux to the rescue
- interestingly, when we bind In0 at a call site that also binds the inner type In.
=
in thetype
alias is like mathematical equality.- so if
In0
= apple, andtype In = In0
, then type In = apple
so we can do stuff like this ..
case class Greeter(name: String) {
def greeting(greeting: String): String = {
s"$greeting, $name"
}
}
case object ImAnAlien {
@tailrec
private def sayThis(thing: String, accumlator: String, numTimes: Int): String = numTimes match {
//base case
case 0 => accumlator
//recurse
case _ => sayThis(thing, accumlator + " " + thing, (numTimes - 1))
}
def say(num: Int): String = {
sayThis("I'm an Alien", "", num)
}
}
def foo[A,B](a:A):B
- so I can make them conform to MyTypeclass
// known type class members
implicit val greeterToTypeclass: Aux[Greeter, String, String] = new MyTypeClass[Greeter] {
type In = String
type Out = String
override def doMagic(foo: Greeter, param1: In): Out = foo.greeting(param1)
}
implicit val imAnAlienToTypeclass: Aux[ImAnAlien.type, Int, String] = new MyTypeClass[ImAnAlien.type] {
type In = Int
type Out = String
override def doMagic(foo: ImAnAlien.type, param1: In): Out = foo.say(param1)
}
}
fancy API …
object SomeApi {
def voodoo[T, In0, Out0](foo: T, sayThis: In0)(implicit ev: MyTypeClass.Aux[T, In0, Out0]): Out0 = {
val tc = MyTypeClass[T]
tc.doMagic(foo, sayThis)
ev.doMagic(foo, sayThis)
}
}
use it:-
//bring typeclass instance into scope import MyTypeClass. import SomeApi.
println(“Greeting:- ”) println(voodoo(Greeter(“karl”), “wassup”))
println(“\nAliens:- ”) println(voodoo(ImAnAlien, 3))
Aliens:-
I'm an Alien I'm an Alien I'm an Alien
But why that Summoner?
But why that Summoner?
- because implicitly will loose type information that we may want to use again
But why that Summoner?
- because implicitly will loose type information that we may want to use again
1 2 3 4 5 6 7 8 9 10 11 |
|
Notice that with implicitly
we loose information that Out
is Int
so this makes sense now, right?
object IsHCons {
def apply[L <: HList](implicit isHCons: IsHCons[L]): Aux[L, isHCons.H, isHCons.T] = isHCons
type Aux[L <: HList, H0, T0 <: HList] = IsHCons[L] { type H = H0; type T = T0 }
implicit def hlistIsHCons[H0, T0 <: HList]: Aux[H0 :: T0, H0, T0] =
new IsHCons[H0 :: T0] {
type H = H0
type T = T0
def head(l : H0 :: T0) : H = l.head
def tail(l : H0 :: T0) : T = l.tail
def cons(h : H0, t : T0) : H0 :: T0 = h :: t
}
}
We can now see that we have an Aux
type that promotes the HCons
’s abstrat types for head and tail of the HList, H
and T
into type parameters so they can be captured or bound.
We provide an implict function to produce an Aux tpe when needed that uses the IsHCons typeclass and fills in or binds the H and T to the type parameters in the Aux. and we also provide a summoner method to fetch the Aux from the implicit scope if it is available, ie if there is an IsHCons implicity available that matches the desired type parameters.
Finally….
- This will hopefully all go away
- see miles sabin sugests a fix in multiple param lists
- see pull req sip 520
It seems that they compiler restriction to prevent multiple implicit parameter lists is simply a syntactic sugar restriction. Miles Sabin, the initiator of the Shapeless library has proposed a change to remove the restriction, which looks like it will get accepted into a future version of Scala.
So while many use cases of the Aux pattern will be able to be expressed at the call site in terms of multiple implicit parameter lists, the Aux pattern is still a useful object lesson in how to use the type system to gain access to the Abstract types defined inside other types which could still be useful to keep the API of a library simple.