class: center, middle # Scala's Modular Roots Tim McGilchrist (@lambda_foo) .bottom[] ??? * No Scala expert * Interested in Scala OO and FP intersection * Anecdote about how this subject came up. --- # Scala the Simple Parts Martin Odersky did a series of talks at GOTO Chicago, flatMap Oslo and ScalaDays about "Scala the Simple Parts". Odersky drew from the ML families' module system in designing Scala. ??? --- # OCaml Module System The ML family of languages are static, strongly typed langauges with strict evaluation. The key parts of OCaml's module system are: * Structures * Signatures * Functors ??? Scala is similarly static, stron and strict. First it's worthwhile introducing the key concepts from ML modules. The ML family of languages are static, strongly typed langauges with strict evaluation. Familar features from FP Scala and Haskell OCaml Signatures are pure, no implementation. Which isn't true for Traits --- # OCaml Modules * Structures group together types and functions with implementations. * Signatures interface for a structure. * Functors are functions from `struct` to `struct`. ??? --- # Scala as OCaml * Trait ≅ Signature * Object ≅ Structure * Class ≅ Functor * Abstract Type ≅ Abstract Type * Refinement ≅ Sharing Constraint ??? The slide in particular that discusses this correspondence is above. I'm assuming the values on the left hand side are mostly familar to the audience here, while those on the right may be less so. Users of `scalaz` can probably make sense of a few of them however. Don't stress about that too much, I'll introduce the right hand side and if I do this correctly you'll have a reasonable idea what they are. --- # Signatures as Traits Equivalence between OCaml signatures and Scala's traits. ``` ocaml module type ORDERING = sig type t val compare : t -> t -> int end ``` ??? * --- # Signatures as Traits Similar Ordering concept in the Scala standard library ```scala trait Ordering[T] { def compare(x: T, y: T): Int } ``` ??? * Using type parameter, lets use type members * First point in Odersky's equivalence, sig as traits * Leaving aside that ML signatures are pure, while Scala traits can contain an implementation, the `Ordering` trait is a paramterised type. --- # Rewriting Trait Rewrite Scala to be closer to OCaml ```scala trait Ordering { type T def compare(x: T, y: T): Int } ``` OCaml ``` ocaml module type ORDERING = sig type t val compare : t -> t -> int end ``` ??? * making the positional type parameter an abstract type member * looking rather similar * discussion around type parameters versus abstract type members --- # OCaml Set Signature ```ocaml module type SET = sig type elt type t val empty : t val insert : elt -> t -> t val member : elt -> t -> bool end ``` --- # Scala Set trait ```scala trait SetSig { type Elem type Set def empty: Set def insert(e: Elem, s: Set): Set def member(e: Elem, s: Set): Boolean } ``` --- # Structures as Objects Equivalence between OCaml structures and Scala's objects. OCaml ```ocaml module IntOrdering = struct type t = int let compare(x,y) = x - y end ``` Scala ```scala object IntOrdering extends Ordering { type T = Int def compare(x: T, y: T): Int = x - y } ``` ??? Again baring slight syntax differences the 2 code examples look very similar. --- # Functors as Classes Equivalence between OCaml functors and Scala's classes. Functors are functions from `struct` to `struct`. OCaml has Generative and Applicative versions. ??? * --- # OCaml Functor ```ocaml module UnbalancedSet (Element : ORDERED) : (SET with type elt = Element.t) = struct type elt = Element.t type tree = E | T of tree * t * tree type t = tree let empty = E let rec member x = function | E -> false | T(a, y, b) when Element.compare x y < 0 -> member x a | T(a, y, b) when Element.compare x y > 0 -> member x b | _ -> true ... end ``` ??? * Taken from Purely Functional Data Structures by Okasaki * Parameterised over ORDERED and SET * Sharing constraint, between SET elt and ORDERED. --- # Scala Class ```scala abstract class UnbalancedSet extends SetSig { val Element: Ordering type Elem = Element.T sealed trait Set case object Leaf extends Set case class Branch(left: Set, elem: Elem, right: Set) extends Set val empty = Leaf ``` ??? * --- # Continued ```scala def member(x: Elem, s: Set): Boolean = s match { case Leaf => false case Branch(l, y, r) => if (Element.compare(x, y) < 0) member(x, l) else if (Element.compare(x, y) > 0) member(x, r) else true } ... } ``` --- # Using Functors ```ocaml module S = UnbalancedSet(IntOrdering) ``` ```scala object S extends UnbalancedSet { val Element: Ordering = IntOrdering } ``` --- ```scala scala> var set = S.insert(1, S.empty) set: S.Set = Branch(Leaf,1,Leaf) scala> set = S.insert(2, set) set: S.Set = Branch(Leaf,1,Branch(Leaf,2,Leaf)) scala> S.member(2, set) res5: Boolean = true scala> S.member(4, set) res6: Boolean = false ``` ```ocaml utop # let set = S.(insert 1 empty);; val set : S.t = <abstr> val set' : S.t = <abstr> - : bool = true - : bool = false ``` ??? * Scala functors are generative * OCaml's are applicative by default, generative if you ask nicely. --- # Where OCaml modules differ? * OCaml signatures are structural types * Scala traits are nomimal types * OCaml signatures can be composed structurally * Scala's mixin composition is nominal and creates an inequivalent type. * OCaml has generative and applicative Functors. * Scala Functors are generative, maybe? ??? * Structural types match the requirements of the signature. * Extra flexibility, no need to pre-declare. * Nominal types is more restrictive. * Requires any matching to be explicitly stated. * This generative property is sometimes called "Path Dependent Typing" * First Class Modules in OCaml, putting modules into variables. * Scala can do structural types --- # Conclusion * Expressing modular systems in Scala * Scala is clearly a powerful language * Scala has Path Dependent Types * Look outside your current chosen language. ??? * Modular Scala is clearly near and dear to Martin Odersky’s * Powerful enough that you can craft your own module system * Important to look outside your current language(s) for inspiration. --- # Resources * Scala: The Simple Parts https://www.youtube.com/watch?v=P8jrvyxHodU&feature=youtube_gdata_player * Shapeless: github.com/milessabin/shapeless * Encoding Standard ML modules in OO http://stackoverflow.com/questions/23006951/encoding-standard-ml-modules-in-oo --- class: center, middle # Thanks! Tim McGilchrist @lambda_foo Software Engineer @ Ambiata Thanks!