Be LIke Water (Scala Italy 2016)

Updated (and bugfixed) version of the slides for the Shapeless Talk @ Scala Italy 2016

Transcript

1. BE LIKE WATER A Shapeless Primer
2. Edoardo Vacchi — UniCredit R&D ▸ @evacchi — twitter, github ▸ read more on rnduja.github.io
3. RUNNING EXAMPLE: DATAFLOW PROGRAMMING
4. RUNNING EXAMPLE: A.K.A. Reactive PROGRAMMING
5. A PIPELINE $ find ~ | xargs grep hello | wc -l case class Node[T, R](f: T => R) // then, for each input t: T val output = f(t)
6. What about graphs ?
7. WE KNOW HOW TO DO THIS WITH fixed ARITY /* * ### E.g: ARITY 2 * * f is a **binary** function */ case class Node[T1,T2,R](f:(T1,T2) => R) val in1 = readInput1() val in2 = readInput2() // f.tupled is the **unary** function that takes the **pair** (T1,T2) val ft: Tuple2[T1, T2] => R = f.tupled ft( (in1, in2) ) // apply f.tupled to the pair
8. ARBITRARY ARITY case class Node[T1, T2, ..., TK, R](f: (T1, T2, ..., TK) => R) // 1) how do you construct a K-tuple, for any K ? // 2) what would the type signature for Node be ? Function1[T,R] Function2[T1,T2,R] Tuple2[T1,T2] ... ... Function22[T1,T2,...,T22,R] Tuple22[T1,T2,...,T22]
9. - Code Generation: (macros ?) - Error prone. How to test ? - Reflection - Runtime errors Maybe Shapeless could help
10. SHAPELESS
12. Documentation
13. SHAPELESS WIKI «FACILITIES FOR ABSTRACTING OVER ARITY» 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
14. «FACILITIES FOR ABSTRACTING OVER ARITY» «Conversions between tuples and HList's, and between ordinary Scala functions of arbitrary arity and functions which take a single corresponding HList argument allow higher order functions to abstract over the arity of the functions and values they are passed»
15. WTF?
16. LISTS AND HETEROGENEOUS LISTS (HLISTS) val l = 1 :: "String" :: 2.0 :: Nil scala> val listFirst = l(0) listFirst: Any = 1 val hl = 1 :: "String" :: 2.0 :: HNil hl match { case x :: xs => ... // matches head and tail } scala> val first = hl(0) first: Int = 1 scala> val second = hl(1) second: String = "String" HLists also support map, folds, etc.
17. 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 => ... }
18. WITH arbitrary arity ! hl match { case 1 :: rest => ... // matches when head == 1 (any size) case x :: y :: rest => ... // matches size >= 2 case x :: y :: HNil => ... // matches when it is exactly a pair }
19. CONVERSIONS BETWEEN TUPLES, CASE CLASSES AND HLISTS val hl: String :: Int :: HNil = 1 :: "String" :: 2.0 :: HNil val t: (String, Int) = hl.tupled // to tuple val hl2: String :: Int :: HNil = t.productElements // to HList val p: Person = Person("John", 30) val hl3: String :: Int :: HNil = p.productElements // to HList
20. THE Generic[T] OBJECT // hl.tupled and t.productElements methods // are short-hands for: 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 ) // works for tuples as well val gp = Generic[(String,Int)] val johnTuple = ("John", 40) val hl: String :: Int :: HNil = gp.to(johnTuple) val tp: (String,Int) = gp.from(hl) assert( johnTuple == tp )
21. ▸ Tuples and case classes implement the Product trait ▸ You can convert between HLists, Tuples and case classes This is no surprise: they are all product types Similar to Cartesian product: A x B = { (a,b) | a ∊ A, b ∊ B }
22. /* * `Generic[P]` (here `Generic.Aux[P,L]`) * - converts between product types * - enables the `t.toProduct` syntax * What about `FnToProduct` ? */ 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) )((x: Int, y: Int) => x + y) res0: Int = 3
23. K-ARY FUNCTIONS AND HLISTS f.tupled for a K-ary function = a unary function of one K-tuple tuples are fixed-size! we cannot partially match; but with HLists... import syntax.std.function._ import ops.function._ val fhl: String::Int::HNil => String = f.toProduct f.toProduct is shorthand syntax for val fp = FnToProduct[(String, Int) => String] val fhl = fp.apply(f)
24. 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)
25. Wait, what about those .Aux thingamajigs ? Ok, let's rule this out very quick.
26. AN IMPLEMENTATION DETAIL: THE AUX ENCODING /* * When you create a Generic[P] instance * you want to let Scala infer the result HList type `L`. */ val gen = Generic[Person] // otherwise you would have to spell it out val gen = Generic[Person, String :: Int :: HNil] /* * when `Generic` is used to **enforce a constraint**, * then you might want to use `Generic.Aux[P,L]`. * * `Generic.Aux[P,L]` reads as "that `Generic[P]` instance that converts P into L" * FnToProduct.Aux[F, L => R] reads as "that FnToProduct[F] that converts F into L => R" */
27. wait, what ? are you saying that implicits can be used to enforce compile-time constraints ? how ?
28.       MAGIC
29. IMPLICITS ▸ Controversial feature ▸ Hard to grasp for beginners ▸ Can cause headaches even to experienced users. ▸ The term implicit may be arguable
30.       IMPLICITS
31. IMPLICIT VALUES & IMPLICIT DEFS // e.g. config objects implicit val implicitJohn = Person("John", 40) def somePersonString(implicit p: Person) = p.toString scala> somePersonString res0: String = "Person(John,40)" // *generate* values as they are needed implicit def personProvider = Person("Random Guy", (math.random * 100).toInt) def somePersonString(implicit p: Person) = p.toString scala> somePersonString res1: String = "Person(Random Guy,26)" scala> somePersonString res2: String = "Person(Random Guy,31)"
32. But implicits can be used as logic predicates
33. PROLOG
34. A QUICK PROLOG INTRODUCTION ▸ facts ▸ rules to derive new facts ▸ contained in the knowledge base (KB) ▸ Executing a Prolog program = solving the constraints in a query
35. Every man is mortal Sokrates is a man => Sokrates is mortal ∀ x: person(x) ! mortal(x) => person(sokrates) ! mortal(sokrates)
36. % fact person(sokrates). % rule mortal(X) :- person(X). ?- mortal(sokrates). true ?- mortal(X) X = sokrates
37. child, grandchild child(john, carl). child(carl, tom). grandchild(A, B) :- child(A, X), child(X, B). ∀ A, B, X: child(A,X) ∧ child(X,B) " grandchild(A,B)
38. % find the pair(s) X,Y % for which the 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
39. % false predicates: ?- grandchild(X, X). false ?- grandchild(tom, X). false ?- grandchild(X, john). false
40. INTRODUCING LOGIC SCALA ▸ A superset of Scala with 2 new keywords ▸ fact ▸ rule
41. DECLARING RELATIONS AND ATOMS trait Child[A,B] trait John trait Carl trait Tom
42. 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 ]{} you are introducing into the knowledge base concrete evidences, witnesses (obj instances) that these facts hold true
43. DECLARING RULES trait GrandChild[A,B] // in Logic Scala, even rules are named 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]
44. QUERYING LOGIC SCALA > query[ GrandChild[John, Tom] ] // (compiles; returns the fact instance) > query[ GrandChild[John, Carl] ] Compilation Failed
45. PLOT TWIST: LOGIC SCALA is ACTUALLY SCALA
47. 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
48. Scala | Prolog ---------------------------+----------------------------- implicit vals | facts implicit defs | rules type parameters in def | variables in a rule implicit parameter lists | bodies of a rule
49. applyProduct
50. 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)) scala> applyProduct(1, 2)((x: Int, y: Int) => x + y) res0: Int = 3
51. SECOND PLOT TWIST: Generic[P] AND FnToProduct[F] ARE TYPECLASSES
52. TYPECLASSES AS PREDICATES ▸ 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).
53. Q & A
54. 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”
55. BONUS TRACK
56. Wait, aren't you forgetting something ? What about those .Aux thingamajigs ?
57. AN IMPLEMENTATION DETAIL: THE AUX ENCODING /* * When you create a Generic[P] instance, * you generally **do not** want to specify * the result HList type `L`. */ val gen = Generic[Person] // otherwise you would have to write val gen = Generic[Person, String :: Int :: HNil] /* * when `Generic` is used as a **predicate** (as an **implicit**), * then you can use `Generic.Aux[P,L]`. * You can think of it as if it were defined as follows (pseudo-code) */ trait Generic[P] { type Out <: HList } type Generic.Aux[P,L] = Generic[P] { type Out = L }
58. 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.
59. PROLOG ENCODING generic(P, L) :- product(P), (X, Y) = P, hlist(L), [X, Y] = L. % in short: generic((X,Y), [X,Y]).
60. % 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).
61. 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)).