Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Modularity à la ML

Modularity à la ML

Ionuț G. Stan

April 07, 2017
Tweet

More Decks by Ionuț G. Stan

Other Decks in Programming

Transcript

  1. • Software Developer at • Worked with Scala for the

    past 5 years • FP, programming languages, compilers • Mostly-tech blog at igstan.ro About Me
  2. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map option f = case option of NONE => NONE | SOME a => SOME (f a) end
  3. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map option f = case option of NONE => NONE | SOME a => SOME (f a) end
  4. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map option f = case option of NONE => NONE | SOME a => SOME (f a) end
  5. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map option f = case option of NONE => NONE | SOME a => SOME (f a) end
  6. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map option f = case option of NONE => NONE | SOME a => SOME (f a) end
  7. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f f = case option of NONE => NONE | SOME a => SOME (f a) end
  8. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  9. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  10. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  11. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  12. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  13. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  14. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  15. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  16. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  17. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  18. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  19. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  20. $ sml - datatype 'a option = … NONE …

    | SOME of 'a; datatype 'a option = NONE | SOME of 'a - - fun map f option = … case option of … NONE => NONE … | SOME a => SOME (f a); val map = fn : ('a -> 'b) -> 'a option -> 'b option - - val a = SOME 1; val a = SOME 1 : int option - - map (fn a => a + 1) a; val it = SOME 2 : int option
  21. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  22. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  23. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  24. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  25. structure Option = struct datatype 'a option = NONE |

    SOME of 'a fun map f option = case option of NONE => NONE | SOME a => SOME (f a) end
  26. $ sml - use "option.sml"; - - val a =

    Option.SOME 1; val a = SOME 1 : int Option.option - - Option.map (fn a => a + 1) a; val it = SOME 2 : int Option.option
  27. $ sml - use "option.sml"; - - val a =

    Option.SOME 1; val a = SOME 1 : int Option.option - - Option.map (fn a => a + 1) a; val it = SOME 2 : int Option.option
  28. $ sml - use "option.sml"; - - val a =

    Option.SOME 1; val a = SOME 1 : int Option.option - - Option.map (fn a => a + 1) a; val it = SOME 2 : int Option.option
  29. $ sml - use "option.sml"; - - val a =

    Option.SOME 1; val a = SOME 1 : int Option.option - - Option.map (fn a => a + 1) a; val it = SOME 2 : int Option.option
  30. $ sml - use "option.sml"; - - val a =

    Option.SOME 1; val a = SOME 1 : int Option.option - - Option.map (fn a => a + 1) a; val it = SOME 2 : int Option.option
  31. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  32. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  33. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  34. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  35. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  36. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  37. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  38. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  39. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  40. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  41. structure IntListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case Int.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  42. structure StringListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case String.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  43. structure StringListSet = struct val empty = [] fun add

    set elem = case set of [] => [elem] | head :: tail => case String.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  44. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  45. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  46. In Standard ML, a functor is a module-level function that

    takes a module as argument and produces a module as a result.
  47. Note: There's no relationship between an SML functor and the

    Functor type-class as defined by the cats or scalaz libraries.
  48. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  49. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  50. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  51. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  52. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  53. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  54. A signature can be seen as the type of a

    module. It specifies the types and values that a module must define.
  55. functor ListSet(Elem : ORD) = struct val empty = []

    fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  56. functor ListSet(Elem : ORD) : SET = struct val empty

    = [] fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  57. functor ListSet(Elem : ORD) : SET = struct val empty

    = [] fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  58. signature SET = sig structure Key : ORD type t

    val empty : t val add : t -> key -> t end
  59. signature SET = sig type t type key val empty

    : t val add : t -> key -> t end
  60. signature SET = sig type t type key val empty

    : t val add : t -> key -> t end
  61. signature SET = sig type t type key val empty

    : t val add : t -> key -> t end
  62. signature SET = sig type t type key val empty

    : t val add : t -> key -> t end
  63. signature SET = sig type t type key val empty

    : t val add : t -> key -> t end
  64. signature SET = sig type t type key val empty

    : t val add : t -> key -> t end
  65. functor ListSet(Elem : ORD) : SET = struct type t

    = Elem.t list type key = Elem.t val empty = [] fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  66. functor ListSet(Elem : ORD) : SET = struct type t

    = Elem.t list type key = Elem.t val empty = [] fun add set elem = case set of [] => [elem] | head :: tail => case Elem.compare (head, elem) of LESS => head :: (add tail elem) | EQUAL => set | GREATER => elem :: set end
  67. structure IntOrd = struct type t = Int.int val compare

    = Int.compare end structure IntListSet = ListSet(IntOrd) structure StringListSet = ListSet(struct type t = String.string val compare = String.compare end)
  68. structure IntOrd = struct type t = Int.int val compare

    = Int.compare end structure IntListSet = ListSet(IntOrd) structure StringListSet = ListSet(struct type t = String.string val compare = String.compare end)
  69. structure IntOrd = struct type t = Int.int val compare

    = Int.compare end structure IntListSet = ListSet(IntOrd) structure StringListSet = ListSet(struct type t = String.string val compare = String.compare end)
  70. Limitations in SML Q If a functor is like a

    function, can we pass functors to functors, just like we can pass functions to functions?
  71. Limitations in SML Q If a functor is like a

    function, can we pass functors to functors, just like we can pass functions to functions? A No. Standard ML does not have higher-order functors. OCaml and some other ML dialects have it, though.
  72. Limitations in SML Q So we can't return functors from

    functors, either? A No, we cannot in Standard ML.
  73. Limitations in Scala Q If Scala classes are the equivalent

    of SML functors, are they higher-order or not?
  74. Limitations in Scala Q If Scala classes are the equivalent

    of SML functors, are they higher-order or not? A They're not. One cannot, save for reflection, pass classes as arguments to classes or produce classes from classes.
  75. Limitations in SML Q In Scala, we can store objects

    in variables, pass them to functions or return them from functions. Does SML allow this with structures and functors?
  76. Limitations in SML Q In Scala, we can store objects

    in variables, pass them to functions or return them from functions. Does SML allow this with structures and functors? A No. In Standard ML, modules are not first-class. Values and modules form two different, separate languages — the so- called core and module languages.
  77. object IntOrd extends Ord { type T = Int def

    compare(a: T, b: T): Int = a - b }
  78. trait Set { type T type K def empty: T

    def add(set: T, key: K): T }
  79. class ListSet(val ord: Ord) extends Set { type K =

    ord.T type T = List[ord.T] def empty: T = List.empty def add(set: T, key: K): T = ??? }
  80. object TwitterClient { object UserSet extends ListSet(UserOrd) def followers(username: String)

    = { val users: UserSet.T = UserSet.empty // add users and return them users } }
  81. object TwitterClient { object UserSet extends ListSet(UserOrd) def followers(username: String)

    = { val users: UserSet.T = UserSet.empty // add users and return them users } }
  82. object TwitterClient { object UserSet extends ListSet(UserOrd) def followers(username: String)

    = { val users: UserSet.T = UserSet.empty // add users and return them users } }
  83. object TwitterClient { object UserSet extends ListSet(UserOrd) def followers(username: String)

    = { val users = UserSet.empty // add users and return them users } }
  84. object TwitterClient { object UserSet extends ListSet(UserOrd) def followers(username: String)

    = { val users = UserSet.empty // add users and return them users } }
  85. object TwitterClient { def followers(username: String) = { object UserSet

    extends ListSet(UserOrd) val users = UserSet.empty // add users and return them users } }
  86. object TwitterClient { def followers(username: String) = { val userSet

    = new ListSet(UserOrd) val users = UserSet.empty // add users and return them users } }
  87. object TwitterClient { def followers(username: String) = { val userSet

    = new ListSet(UserOrd) val users: UserSet.T = UserSet.empty // add users and return them users } }
  88. object TwitterClient { def followers(username: String) = { val userSet

    = new ListSet(UserOrd) val users: userSet.T = UserSet.empty // add users and return them users } }
  89. object TwitterClient { def followers(username: String): List[userSet.ord.T] forSome { val

    userSet: ListSet } = { val userSet = new ListSet(UserOrd) val users: userSet.T = UserSet.empty // add users and return them users } }
  90. object TwitterClient { def followers(username: String): List[userSet.ord.T] forSome { val

    userSet: ListSet } = { val userSet = new ListSet(UserOrd) val users: userSet.T = UserSet.empty // add users and return them users } }
  91. object TwitterClient { import scala.language.existentials def followers(username: String): List[userSet.ord.T] forSome

    { val userSet: ListSet } = { val userSet = new ListSet(UserOrd) val users: userSet.T = UserSet.empty // add users and return them users } }
  92. object TwitterClient { import scala.language.existentials def followers(username: String): userSet.T forSome

    { val userSet: Set } = { val userSet = new ListSet(UserOrd) val users: userSet.T = UserSet.empty // add users and return them users } }
  93. object TwitterClient { import scala.language.existentials def followers(username: String): Set#T =

    { val userSet = new ListSet(UserOrd) val users: userSet.T = UserSet.empty // add users and return them users } }
  94. Limitations in SML Q Why aren't modules first-class values in

    Standard ML? A Having types as components of a signature seems to require the notion of dependent types if the language were to support first-class modules. Scala has path-dependent types.
  95. Other Differences • SML's modules are not (mutually) recursive, while

    Scala's objects and classes are. • Because objects, traits and classes are values, they're also types in Scala.
  96. Other Differences • SML's modules are not (mutually) recursive, while

    Scala's objects and classes are. • Because objects, traits and classes are values, they're also types in Scala. • Objects come with a concept of this (open recursion), SML modules do not.
  97. Other Differences • SML's modules are not (mutually) recursive, while

    Scala's objects and classes are. • Because objects, traits and classes are values, they're also types in Scala. • Objects come with a concept of this (open recursion), SML modules do not. • SML modules allow some sort of inheritance, but not overriding, as there's no this.
  98. Dependency Injection • Functor params look a lot like constructor

    injection. • The Reader monad is usually advocated by FP people for doing "functional" DI.
  99. Dependency Injection • Functor params look a lot like constructor

    injection. • The Reader monad is usually advocated by FP people for doing "functional" DI. • But Reader only injects values, not types.
  100. Dependency Injection • Functor params look a lot like constructor

    injection. • The Reader monad is usually advocated by FP people for doing "functional" DI. • But Reader only injects values, not types. • A functor-like approach, i.e., constructor injection, is still useful.
  101. Dependency Injection • Functor params look a lot like constructor

    injection. • The Reader monad is usually advocated by FP people for doing "functional" DI. • But Reader only injects values, not types. • A functor-like approach, i.e., constructor injection, is still useful. • Scala alternative: implicit params.
  102. Dependency Injection • We should distinguish between: • static dependencies:

    dependencies are known at compile-time. Employ constructor injection or type-classes (coherent implicit params).
  103. Dependency Injection • We should distinguish between: • static dependencies:

    dependencies are known at compile-time. Employ constructor injection or type-classes (coherent implicit params). • dynamic dependencies: dependencies are known at runtime. Employ constructor injection, implicit params, Reader monad.