Karl's Code

and other code related stuff

The Rise and (Hopefully) Fall of the Aux Pattern

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

12th April 2017
To present this document press 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

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
    }
}

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

* We need to delay type resolution * To give the compiler a chance to work it out

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 the type alias is like mathematical equality.
  • so if In0 = apple, and type 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)
  }
}

* two differnt classes but if you squint….

def foo[A,B](a:A):B
  • so I can make them conform to MyTypeclass

object MyTypeClass { //aux pattern type Aux[T0, In0, Out0] = MyTypeClass[T0] {type In = In0; type Out = Out0}

  // 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))

Greeting:- wassup, karl

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

import shapeless.{HList, ::, HNil}
import shapeless.ops.hlist.Last

//use the implicitly
implicitly[Last[String :: Int :: HNil]]
// res6: shapeless.ops.hlist.Last[shapeless.::[String,shapeless.::[Int,shapeless.HNil]]] =shapeless.ops.hlist$Last$$anon$34@20bd5df0

// use the summoner
Last[String :: Int :: HNil]
// res7: shapeless.ops.hlist.Last\
// [shapeless.::[String,shapeless.::[Int,shapeless.HNil]]]{type Out = Int} =shapeless.ops.hlist$Last$$anon$34@4ac2f6f

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….

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.

Thanks….

Comments