Shapeless par la pratique !

Ludovic L'HOURS github.com/madbrain

Introduction

• Shapeless parait très théorique
• Mais très utile dans pleins de cas concrets
• Ajout de typepage forts et contextuels

Use case 1

• Étude autour du MachineLearning, DeepLearning
• Calcul à base de matrices (ou tenseurs)

Exemple d'utilisation

val x = new Matrix(4, 5)
val y = new Matrix(5, 3)
val z = new Matrix(4, 3)

println(x.mult(y)) // correct
println(x.mult(z)) // incorrect

Vérification des préconditions

• Cohérence des dimensions lors d'opérations (addition, produit, etc.)
• La cohérence des dimensions vérifiée au runtime

Implémentation de Matrice

class Matrix(val n: Int, val m: Int) {
    val elements = Array.ofDim[Double](n, m)

    def add(o: Matrix): Matrix {
        if (o.n != n || o.m != m) = {
            throw new RuntimeException("incompatible sizes")
        }
        // ...
    }
    def mult(o: Matrix): Matrix = {
        if (m != o.n) {
            throw new RuntimeException("incompatible sizes")
        }
        // ...
    }
}

Problème

• Mise au point complexe car au runtime
• Idée : Utilisation du typepage ?
• → Conversion de valeurs en types

Implémentation Nat de Shapeless

• Construction récursive : Arithmétique de Peano

trait Nat
class _0 extends Nat
case class Succ[N <: Nat]() extends Nat

val _1 = Succ[_0]
val _2 = Succ[Succ[_0]]

Ajout du typage

class Matrix[N <: Nat, M <: Nat] {
    val elements = Array.ofDim[Double](n, m)

    def add(o: Matrix[N, M]): Matrix[N, M] = {
        // ...
    }
    def mult[X <: Nat](o: Matrix[M, X]): Matrix[N, X] = {
        // ...
    }
}

Conversion Nat vers entier

• Comment obtenir la valeur entière d'un type Nat ?
• Utilisation de la typeclass ToInt
• La typeclass est injectée à l'aide d'une valeur implicite

Conversion Nat vers entier

class Matrix[N <: Nat, M : Nat](
        implicit toIntN: ToInt[N], toIntM: ToInt[M]) {
    val elements = Array.ofDim[Double](toIntN(), toIntM())

    def add(o: Matrix[N, M]): Matrix[N, M] {
        // ...
    }
    def mult[X <: Nat](o: Matrix[M, X]): Matrix[N, X] {
        // ...
    }
}

Calcul avec Nat

• Il est possible de réaliser des calculs avec les typeclasses Sum, Prod, Max, etc.

Calcul avec Nat

class Matrix[N <: Nat, M : Nat] {
    def concat[X <: Nat](o: Matrix[N, X])(
            implicit sum: Sum[M, X]): Matrix[N, sum.Out] {
        // ...
    }
}

Similitudes avec Prolog

• La fonction concat représente une règle Prolog
• Les variables de types (N, M, etc.) sont des variables Prolog
• L'injection d'implicites forment le corps de la règle
• Les définition de valeurs implicites sont les axiomes Prolog

Factorial en Prolog

factorial(0, 1).

factorial(N, F) :-
   N1 is N-1,
   factorial(N1, F1),
   F is N * F1.

Factorial en Prolog

factorial(0, 1).

factorial(N, F) :-
   sub(N, 1, N1),
   factorial(N1, F1),
   mult(N, F1, F).

Factorial en Prolog

factorial(0, 1).

factorial(succ(N), F) :-
   factorial(N, F1),
   mult(succ(N), F1, F).

Typeclass Factorial

trait Factorial[In <: Nat, Out <: Nat]
object Factorial {
    implicit val fact0 = new Factorial[Nat._0, Nat._1] {}
}

Typeclass Factorial

trait Factorial[In <: Nat, Out <: Nat]
object Factorial {
    implicit val fact0 = new Factorial[Nat._0, Nat._1] {}

    implicit def factN[N <: Nat, X <: Nat](
        implicit fact: Factorial[N, X],
                 mult: Prod[Succ[N], X]) =
                 new Factorial[Succ[N], mult.Out] {}
}

Typeclass Factorial

trait Factorial[In <: Nat, Out <: Nat]
object Factorial {
    implicit val fact0 = new Factorial[Nat._0, Nat._1] {}

    implicit def factN[N <: Nat, X <: Nat](
        implicit fact: Factorial[N, X],
                 mult: Prod[Succ[N], X]) =
                 new Factorial[Succ[N], mult.Out] {}

    def apply[N <: Nat, R <: Nat](x: N)(
        implicit fact: Factorial[N, R], toInt: ToInt[R]) = toInt()
}
def main(args: Array[String]) {
    println(Factorial(Nat._4))
}

Limitations

• Factorial(Nat._5) plante scalac !

Code réel

println(Factorial.apply(
    _4,
    Factorial.factN(
      Factorial.factN(
        Factorial.factN(
          Factorial.factN(Factorial.fact0(),
            Prod.prod2(Prod.prod1(), Sum.sum2(Sum.sum1()))),
          Prod.prod2(Prod.prod2(Prod.prod1(), Sum.sum2(Sum.sum1())), Sum.sum2(Sum.sum1()))),
        Prod.prod2(Prod.prod2(Prod.prod2(Prod.prod1(), Sum.sum2(Sum.sum2(Sum.sum1()))),
          Sum.sum2(Sum.sum2(Sum.sum1()))), Sum.sum2(Sum.sum2(Sum.sum1())))),
      Prod.prod2(Prod.prod2(Prod.prod2(Prod.prod2(Prod.prod1(),
        Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum1()))))))),
        Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum1()))))))),
        Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum1()))))))),
        Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum2(Sum.sum1())))))))),
    ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(
    ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(
    ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(
    ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toIntSucc(
    ToInt.toIntSucc(ToInt.toIntSucc(
    ToInt.toIntSucc(ToInt.toIntSucc(ToInt.toInt0()))))))))))))))))))))))))));

Use case 2

• Faciliter l'écriture de DSL
• Exemple : remplacer le router Play2 par un DSL
• http://codetunes.com/2012/scala-dsl-tutorial-writing-web-framework-router/

Exemple d'utilisation

val fooRoute  = GET on "foo" to Application.foo
val showRoute = PUT on "show" / * to Application.show
val barRoute  = POST on "bar" / * / * to Application.bar

def foo() = {
  println("foo")
}
def show(a: Int) = {
  println(s"show $a")
}
def bar(a: String, b: Boolean) = {
  println(s"bar $a $b")
}

Contraintes

• L'arité des fonction est corélée au nombre de wildcard
• Les arguments sont convertis par une typeclass

Implémentation initiale

• Une classe différente pour chaque arité de wildcard
• → beaucoup de code dupliqué

Utilisation de Shapeless

• Utilisation de Nat pour compter le nombre d'occurence de wildcard
• Comparaison de l'arité de la fonction avec ce nombre
• Création d'une fonction d'évaluation d'une Route
• Typeclasses utilisées: FnToProduct, Length, ZipApply et FromTraversable

Live Coding Time!

Aide au débuggage

• Instantiation manuelle des implicites manquantes
• Écrire ses propre typeclasses en s'inspirant de Shapeless
• Utilisation de l'annotation @implicitNotFound

Conclusion

• Amélioration de la robustesse par le typage
• Bon moyen d'apprentissage des typeclasses
• Limitations en puissance → Dotty ?
• Limitations en debuguage → Macros ?
• Pour aller plus loin: https://github.com/underscoreio/shapeless-guide/

Question Time?

https://madbrain.github.com/pres-shapeless/