Be Like Water — A Shapeless Primer

A follow up to http://rnduja.github.io/2016/01/19/a_shapeless_primer/

Video recording (in Italian) @ https://www.youtube.com/watch?v=8KQ9Iuj3bns

Transcript

1. BE LIKE WATER A Shapeless Primer
2. @evacchi — twitter, github read more on rnduja.github.io
4. INTRODUCTION
5. GENERIC PROGRAMMING example (Spire) def sum[A : Numeric](l: A, r: A) = l + r !""""""" "context bound" ... desugars to... def sum[A](l: A, r: A)(implicit nm: Numeric[A]) = l + r
6. RUNNING EXAMPLE Define a node in a pipeline: case class Node[T, R](f: T => R) With arbitrary arity: case class Node[T1, T2, ..., TK, R](f: (T1, T2, ..., TK) => R)
7. without special-casing Function1[T,R] Function2[T1,T2,R] Tuple2[T1,T2] ... ... Function22[T1,T2,...,T22,R] Tuple22[T1,T2,...,T22]
8. SHAPELESS WIKI import syntax.std.function._ import ops.function._ def applyProduct[P <: Product, F, L <: HList, R](p: P)(f: F) (implicit gen: Generic.Aux[P, L], fp: FnToProduct.Aux[F, L => R]) = f.toProduct(gen.to(p)) scala> applyProduct(1, 2)((_: Int)+(_: Int)) res0: Int = 3 scala> applyProduct(1, 2, 3)((_: Int)*(_: Int)*(_: Int)) res1: Int = 6
9. WTF?
10. HLISTS AS TUPLES val t = (1, "String", 2.0) val hl = 1 :: "String" :: 2.0 :: HNil val (a, b, c) = t val x :: y :: z :: HNil = hl t match { case (1, s, _) => ... } hl match { case 1 :: s :: _ :: HNil => ... }
11. WITH ARBITRARY ARITY hl match { case 1 :: rest => ... // matches if first element 1, regardless the size of the list // and binds the tail to `rest` case x :: y :: HNil => ... // matches when it is a pair // etc. }
12. FROM TUPLES TO HLISTS AND BACK AGAIN val hl = 1 :: "String" :: 2.0 :: HNil val t : (Int, String, Double) = hl.tupled aTuple.productElements match { case a :: b :: HNil => ... } case class Person(name: String, age: Int) Person("John", 40).productElements match { case name :: age :: HNil => ... }
13. THE Generic[T] OBJECT val gp = Generic[Person] val john = Person("John", 40) val hl: String :: Int :: HNil = gp.to(john) val p: Person = gp.from(hl) assert( john == p )
14. Both case classes and tuples extend Product, so: val gp = Generic[Tuple2[String,Int]] val johnTuple = ("John", 40) val hl: String :: Int :: HNil = gp.to(johnTuple) val tp: Tuple2[String,Int] = gp.from(hl) assert( johnTuple == tp ) In fact, the t.productElements method is really short-hand syntax for the code snippet above.
15. K-ARY FUNCTIONS AND HLISTS ▸ f.tupled turns a K-ary function into a unary function of one K-tuple argument. For instance: val f = (s: String, i: Int) => s"$s $i" val ft: Tuple2[String, Int] => String = f.tupled tuples are fixed-size! But with HLists... import syntax.std.function._ import ops.function._ val fhl: String::Int::HNil => String = f.toProduct
16. THE FnToProduct[F] OBJECT f.toProduct is shorthand syntax to val fp = FnToProduct[(String, Int) => String] val fhl = fp.apply(f)
17. BACK TO THE EXAMPLE def applyProduct[P <: Product, F, L <: HList, R](p: P)(f: F) (implicit gen: Generic.Aux[P, L], fp: FnToProduct.Aux[F, L => R]) = f.toProduct(gen.to(p)) // we can understand this! val gen = Generic[Person] val fhl: String :: Int :: HNil => String = f.toProduct val hl: String :: Int :: HNil = gen.to(p) fhl(hl)
18. IMPLICITS
19. ▸ Implicits are a controversial feature of the Scala programming language. ▸ hard to grasp for beginners ▸ can be cause of headaches even to experienced users. ▸ The term implicit may be arguable
20. IMPLICIT VALUES implicit val implicitJohn = Person("John", 40) def somePersonString(implicit p: Person) = p.toString somePersonString // returns "Person(John, 40)" e.g. configuration objects
21. IMPLICIT DEFS ▸ generate implicit values as needed. implicit def personProvider = Person("Random Guy", (math.random * 100).toInt) def somePersonString(implicit p: Person) = p.toString > somePersonString // Person("Random Guy", and a random integer between 0 and 100)
22. IMPLICIT PARAMETERS AS PREDICATES Enforce extra compile-time constraints ▸ Generic.Aux[P,L] encodes a predicate on P,L
23. PROLOG
24. A QUICK PROLOG INTRODUCTION ▸ facts ▸ rules to derive new facts ▸ kept in the knowledge base (KB), ▸ Executing a Prolog program = solving the constraints in a query
25. EXAMPLE person(john). person(carl). person(tom).
26. ?- person(john). true ?- person(X). X = john ; X = carl ; X = tom
27. child, grandchild child(john, carl). child(carl, tom). grandchild(A, B) :- child(A, X), child(X, B).
28. PROLOG V. LOGIC grandchild(A, B) :- child(A, X), child(X, B). ∀ A, B, X: child(A,X) ∧ child(X,B) " grandchild(A,B)
29. QUERYING % find the pair(s) X,Y for which the grandchild relation holds ?- grandchild(X, Y). X = john Y = tom % find the john's grandchildren ?- grandchild(john, Y). Y = tom % find tom's grandparents ?- grandchild(X, tom). X = john
30. QUERYING (2) % false predicates: ?- grandchild(X, X) no ?- grandchild(tom, X) no ?- grandchild(X, john) no
31. mortal(X) :- person(X). person(sokrates). ?- mortal(sokrates). true
32. INTRODUCING LOGIC SCALA ▸ A superset of Scala with 2 new keywords ▸ fact ▸ rule
33. DECLARING RELATIONS AND ATOMS trait Child[A,B] trait John trait Carl trait Tom
34. DECLARING FACTS // in Logic Scala, facts are named fact johncarl = new Child[John,Carl]{} // an instance of type Child fact carltom = new Child[Carl,Tom ]{}
35. DECLARING RULES trait GrandChild[A,B] rule grandChild[A,B,X]( facts xy: Child[A,X], yz: Child[X,B] ) = new GrandChild[A,B] {} rule[A,B,X](Child[A,X], Child[X,B]): GrandChild[A,B]
36. QUERYING LOGIC SCALA > query[ GrandChild[John, Tom] ] // (compiles; returns the fact instance) > query[ GrandChild[John, Carl] ] Compilation Failed
37. PLOT TWIST: LOGIC SCALA is ACTUALLY SCALA
39. trait John trait Carl trait Tom trait Child[T,U] implicit val john_carl = new Child[John,Carl]{} implicit val carl_tom = new Child[Carl,Tom ]{} trait GrandChild[T,U] implicit def grandChild[X,Y,Z]( implicit xy: Child[X,Y], yz: Child[Y,Z] ) = new GrandChild[X,Z] {} > implicitly[ GrandChild[John, Tom] ] // (compiles; returns the fact instance) > implicitly[ GrandChild[John, Carl] ] Compilation Failed
40. Scala | Prolog ---------------------------+----------------------------- implicit vals | facts implicit defs | rules type parameters in def | variables in a rule implicit parameter lists | bodies of a rule
41. applyProduct
42. can_apply_product(P, F, L, R) :- generic(P,L), fn_to_product(F, fn(L, R)). def applyProduct[P <: Product, F, L <: HList, R](p: P)(f: F) (implicit gen: Generic.Aux[P, L], fp: FnToProduct.Aux[F, L => R] ) = f.toProduct(gen.to(p))
43. SECOND PLOT TWIST: Generic[P] AND FnToProduct[F] ARE TYPECLASSES
44. ▸ value of an implicit parameter = evidence that a predicate holds ▸ when one such an object instance provides methods, then it is called a typeclass. ▸ Generic[P] provides the methods to(P) and from(HList).
45. THE AUX ENCODING Generic.Aux and FnToProduct.Aux are actually type aliases. For instance, Generic.Aux is defined in the companion object of Generic object Generic { type Aux[P,L] = Generic[P] { type Out = L } ... } trait Generic[P] { type Out }
46. Generic.Aux[P,L] is sometimes called a type extractor because it extracts the type member value Generic.Out by raising it into the signature of type Generic.Aux.
47. BONUS TRACK
48. generic(P, L) :- product(P), (X, Y) = P, hlist(L), [X, Y] = L. % in short: generic((X,Y), [X,Y]).
49. % let us represent function signatures with fn fn((arg_type1, arg_type2, ..., arg_typeN), ret_type) fn_to_product(F, fn(L, R)) :- fn(Args,R) = F, generic(Args, L). % in short: fn_to_product(fn(Args,R), L, R) :- generic(Args, L).
50. generic((X,Y), [X,Y]). fn_to_product(fn(Args,R), L, R) :- generic(Args, L). can_apply_product(P, F, L, R) :- generic(P,L), fn_to_product(F, fn(L, R)).
51. REFERENCES ▸ Andrea Ferretti's dependent types encoded in Scala's type system ▸ Mark Harrah's series on type-level programming ▸ Stefan Zeiger's slides on Type-level Computations ▸ Sam Halliday's Shapeless For Mortals ▸ Miles Sabin's introductory talks ▸ Why is the Aux technique required for type-level computations? on StackOverflow ▸ Shapeless Wiki ▸ Shapeless Examples ▸ Eugene Yokota's “Herding Cats”