[OCaml] modular implicits
1. 背景
在看《Exploring ReasonML and functional programming》的时候，
Basic values and types 一章提到了，modular implicits的概念，
ReasonML does not currently support ad hoc polymorphism where the same operation is implemented differently depending on the types of the parameters. Haskell, another functional programming language supports ad hoc polymorphism via type classes. ReasonML may eventually support it via the similar modular implicits.
于是就想了解一下，这到底是什么意思。
1. module
OCaml中的module可以作为functor的参数来传递，
通过使用 Language extensions: first-class module，也可以作为first-class value来使用。
module一般由两部分组成，struct 和 signature。
类似于一个变量的，value 和 type。
1.1 module struct
module PrioQueue =
struct
type priority = int
type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
let empty = Empty
let rec insert queue prio elt =
match queue with
Empty -> Node(prio, elt, Empty, Empty)
| Node(p, e, left, right) ->
if prio <= p
then Node(prio, elt, insert right p e, left)
else Node(p, e, insert right prio elt, left)
exception Queue_is_empty
let rec remove_top = function
Empty -> raise Queue_is_empty
| Node(prio, elt, left, Empty) -> left
| Node(prio, elt, Empty, right) -> right
| Node(prio, elt, (Node(lprio, lelt, _, _) as left),
(Node(rprio, relt, _, _) as right)) ->
if lprio <= rprio
then Node(lprio, lelt, remove_top left, right)
else Node(rprio, relt, left, remove_top right)
let extract = function
Empty -> raise Queue_is_empty
| Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
end;;
格式如下：
module module_name = struct ... end;;
模块外部可以使用dot notaion来访问struct内部的名字，
例如，PrioQueue.insert PrioQueue.empty 1 "hello";;。
1.2 module signature
signature是模块对外表现的接口，指定了模块内哪些名字是对外可见的。
module type PRIOQUEUE =
sig
type priority = int (* still concrete *)
type 'a queue (* now abstract *)
val empty : 'a queue
val insert : 'a queue -> int -> 'a -> 'a queue
val extract : 'a queue -> int * 'a * 'a queue
exception Queue_is_empty
end;;
格式如下：
module type signature_name = sig ... end;;
使用signature PRIOQUEUE对struct PrioQueue进行限制，
将得到PrioQueue的另一个视图（view），其中，remove_top是不可访问的。
module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);;
AbstractPrioQueue.remove_top ;;
(* Error: Unbound value AbstractPrioQueue.remove_top *)
以上写法，还可以有下面两种简写，
module PrioQueue = (struct ... end : PRIOQUEUE);;
module PrioQueue : PRIOQUEUE = struct ... end;;
1.3 functor
Functors are “functions” from modules to modules.
通过定义functor，我们可以创建带参数的module，
它接受其他一个module作为参数，然后返回一个被具体化的module。例如，
type comparison = Less | Equal | Greater;;
(* 定义一个module的signature *)
module type ORDERED_TYPE =
sig
type t
val compare: t -> t -> comparison
end;;
(* 定义一个functor，它要求参数module实现了 ORDERED_TYPE*)
module Set =
functor (Elt: ORDERED_TYPE) ->
struct
type element = Elt.t
type set = element list
let empty = []
let rec add x s =
match s with
[] -> [x]
| hd::tl ->
match Elt.compare x hd with
Equal -> s (* x is already in s *)
| Less -> x :: s (* x is smaller than all elements of s *)
| Greater -> hd :: add x tl
let rec member x s =
match s with
[] -> false
| hd::tl ->
match Elt.compare x hd with
Equal -> true (* x belongs to s *)
| Less -> false (* x is smaller than all elements of s *)
| Greater -> member x tl
end;;
(* 一个实现了ORDERED_TYPE的module *)
module OrderedString =
struct
type t = string
let compare x y = if x = y then Equal else if x < y then Less else Greater
end;;
(* 调用functor返回一个具体的module *)
module StringSet = Set(OrderedString);;
1.4 first-class modules
Language extensions 指的是，在OCaml中实现的，但是没有在OCaml参考手册中提到的特性。
与first-class module相关的特性，以及OCaml版本号如下，
Introduced in OCaml 3.12;
pattern syntax and package type inference introduced in 4.00;
structural comparison of package types introduced in 4.02.;
fewer parens required starting from 4.05)
module通常被认为是一个静态组件，
这个语言扩展，可以将module打包（pack）成一个first-class value，
然后在适当的时候再动态解包（dynamically unpacked into a module）。
表达式( module module-expr : package-type )，
会将由module-expr表示的模块，转换成一个value，这个value的类型为module package-type。
与之想对应的，表达式( val expr : package-type )，
会将类型为module package-type的expr进行求值，得到它所包装的那个module。
first-class module的一个典型应用，
是在运行时选择实现某一signature的不同module。
每一个module都可以打包成first-class value，
于是就可以保存到数据结构中了，例如hash table中。
(* signature *)
module type DEVICE = sig … end
let devices : (string, (module DEVICE)) Hashtbl.t = Hashtbl.create 17
(* 实现该signature的某一具体实现 *)
module SVG = struct … end
let _ = Hashtbl.add devices "SVG" (module SVG : DEVICE)
(* 实现该signature的另一具体实现 *)
module PDF = struct … end
let _ = Hashtbl.add devices "PDF" (module PDF: DEVICE)
(* 根据用户输入的名字，动态选择module *)
module Device =
(val (try Hashtbl.find devices (parse_cmdline())
with Not_found -> eprintf "Unknown device %s\n"; exit 2)
: DEVICE)
let draw_using_device device_name picture =
(* 使用pattern matching，解包出动态选择的module *)
let module Device =
(val (Hashtbl.find devices device_name) : DEVICE)
in
Device.draw picture
2. ad-hoc polymorphism
First-Class Modules and Modular Implicits in OCaml这篇文章里提到，
First-class modules + implicits = typeclasses in ML.
为了理解这句话，我们要先理解 ad-hoc polymorphism 以及 type class，
以下是维基百科对ad-hoc polymorphism的解释，
In programming languages, ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied. It is also known as function overloading or operator overloading.
即，一个具有ad-hoc polymorphism的函数，
可以针对参数的不同类型，有不同的表现形式。
2.1 type class
haskell中常用的show函数就是ad-hoc polymorphism的，
show 3
> "3"
show 5.334
> "5.334"
show True
> "True"
虽然都返回了String类型，但是show的入参类型是不同的，
而且，用户自定义的类型，也能实现自己的show函数。
这是由于haskell中采用了type class，用来实现ad-hoc polymorphism，
其中，show函数是Show这个type class声明的一种约束（constraint），
class Show a where
show :: a -> String
instance Show Int where
show = showSignedInt
对于用户自定义的类型，只需要像上面指定它为Show type class的实例，
并且给出show的实现即可。
Type classes are implemented using a type-directed implicit parameter-passing mechanism. Each constraint on a type is treated as a parameter containing a dictionary of the methods of the type class. The corresponding argument is implicitly inserted by the compiler using the appropriate type class instance.
2.2 implicits
和Haskell不同的是，OCaml中的 modular implicits 借鉴了Scala中 implicits 的思想，
Parameters can be marked implicit which then allows them to be omitted
from function calls.
例如，在Scala中show函数可以这样写，
// 定义一个show函数
def show [ T ]( x : T )( implicit s : Showable [T ]): String
trait Showable [T] { def show (x: T ): String }
object IntShowable extends Showable [ Int ] {
def show (x: Int ) = x. toString
}
// 第二个参数传入一个具体的类型
show (7)( IntShowable)
在Scala中，如果将IntShowable标记为implicit，
就可以省略show调用时的最后一个类型参数。
implicit object IntShowable extends Showable [ Int ] {
def show (x: Int ) = x. toString
}
show (7)
Scala会查找作用域中，所有被标记为implicit的类型，
除非遇到歧义（ambiguity）。
2.3 modular implicits
OCaml中的modular implicits思路如下，
通过给一个function传入标记为implicit的module参数，
这些module必须要符合某个给定的signature的约束。
通过函数的参数类型，可以推断出作用域中所有implicit的module类型，
从而找到适当的function的实现。
module type Show = sig
type t
val show : t -> string
end
let show {S : Show } x = S. show x
implicit module Show_int = struct
type t = int
let show x = string_of_int x
end
implicit module Show_float = struct
type t = float
let show x = string_of_float x
end
implicit module Show_list {S : Show } = struct
type t = S. t list
let show x = string_of_list S . show x
end
let () =
print_endline (" Show an int : " ^ show 5);
print_endline (" Show a float : " ^ show 1.5);
print_endline (" Show a list of ints : " ^ show [1; 2; 3]);
例如，show 5这个函数调用，会导致OCaml去查找，Show with type t = int，
结果就可以找到，Show_Int module，
然后它就会被作为implicit参数传递给show函数。
参考
Exploring ReasonML and functional programming
The OCaml system release 4.07
Overloadingwith modular implicits
Modular implicits
First-Class Modules and Modular Implicits in OCaml
Haskell 2010 Language Report
Ad hoc polymorphism
OCaml language extensions
