## Saturday, October 29, 2016

### Implementing type-classes as OCaml modules

Implementing type-classes as OCaml modules

## Modular type classes

We revisit the idea of type-classes first explored in this post. This time though, the implementation technique will be by via OCaml modules inspired by the paper "Modular Type Classes" [2] by Harper et. al.

Starting with the basics, consider the class of types whose values can be compared for equality. Call this type-class Eq. We represent the class as a module signature.

    module type EQ = sig
type t

val eq : t * t → bool
end

Specific instances of Eq are modules that implement this signature. Here are two examples.
    module Eq_bool : EQ with type t = bool = struct
type t = bool

let eq (a, b) = a = b
end

module Eq_int : EQ with type t = int = struct
type t = int

let eq (a, b) = a = b
end


Given instances of class Eq (X and Y say,) we realize that products of those instances are also in Eq. This idea can be expressed as a functor with the following type.

    module type EQ_PROD =
functor (X : EQ) (Y : EQ) → EQ with type t = X.t * Y.t

The implementation of this functor is simply stated as the following.
    module Eq_prod : EQ_PROD =
functor (X : EQ) (Y : EQ) → struct
type t = X.t * Y.t

let eq ((x1, y1), (x2, y2)) =  X.eq (x1, x2) && Y.eq(y1, y2)
end

With this functor we can build concrete instances for products. Here's one example.
    module Eq_bool_int :
EQ with type t = (bool * int) = Eq_prod (Eq_bool) (Eq_int)


The class Eq can be used as a building block for the construction of new type classes. For example, we might define a new type-class Ord that admits types that are equality comparable and whose values can be ordered with a "less-than" relation. We introduce a new module type to describe this class.

    module type ORD = sig
include EQ

val lt : t * t → bool
end

Here's an example instance of this class.
    module Ord_int : ORD with type t = int = struct
include Eq_int

let lt (x, y) = Pervasives.( < ) x y
end

As before, given two instances of this class, we observe that products of these instances also reside in the class. Accordingly, we have this functor type
    module type ORD_PROD =
functor (X : ORD) (Y : ORD) → ORD with type t = X.t * Y.t

with the following implementation.
    module Ord_prod : ORD_PROD =
functor (X : ORD) (Y : ORD) → struct
include Eq_prod (X) (Y)

let lt ((x1, y1), (x2, y2)) =
X.lt (x1, x2) || X.eq (x1, x2) && Y.lt (y1, y2)
end

This is the corresponding instance for pairs of intgers.
    module Ord_int_int = Ord_prod (Ord_int) (Ord_int)

Here's a simple usage example.
    let test_ord_int_int =
let x = (1, 2) and y = (1, 4) in
assert ( not (Ord_int_int.eq (x, y)) && Ord_int_int.lt (x, y))


## Using type-classes to implement parameteric polymorphism

This section begins with the Show type-class.

     module type SHOW = sig
type t

val show : t → string
end

In what follows, it is convenient to make an alias for module values of this type.
   type α show_impl = (module SHOW with type t = α)

Here are two instances of this class...
    module Show_int : SHOW with type t = int = struct
type t = int

let show = Pervasives.string_of_int
end

module Show_bool : SHOW with type t = bool = struct
type t = bool

let show = function | true → "True" | false → "False"
end

... and here these instances are "packed" as values.
    let show_int : int show_impl =
(module Show_int : SHOW with type t = int)

let show_bool : bool show_impl =
(module Show_bool : SHOW with type t = bool)

The existence of the Show class is all that is required to enable the writing of our first parametrically polymorphic function.
    let print : α show_impl → α → unit =
fun (type a) (show : a show_impl) (x : a) →
let module Show = (val show : SHOW with type t = a) in
print_endline@@ Show.show x

let test_print_1 : unit = print show_bool true
let test_print_2 : unit = print show_int 3

The function print can be used with values of any type α as long as the caller can produce evidence of α's membership in Show (in the form of a compatible instance).

The next example begins with the definition of a type-class Num (the class of additive numbers) together with some example instances.

    module type NUM = sig
type t

val from_int : int → t
val ( + ) : t → t → t
end

module Num_int : NUM with type t = int = struct
type t = int

let from_int x = x
let ( + ) = Pervasives.( + )
end

let num_int = (module Num_int : NUM with type t = int)

module Num_bool : NUM with type t = bool = struct
type t = bool

let from_int = function | 0 → false | _ → true
let ( + ) = function | true → fun _ → true | false → fun x → x
end

let num_bool = (module Num_bool : NUM with type t = bool)

The existence of Num admits writing a polymorphic function sum that will work for any α list of values if only α can be shown to be in Num.
    let sum : α num_impl → α list → α =
fun (type a) (num : a num_impl) (ls : a list) →
let module Num = (val num : NUM with type t = a) in
List.fold_right Num.( + ) ls (Num.from_int 0)

let test_sum = sum num_int [1; 2; 3; 4]

This next function requires evidence of membership in two classes.
    let print_incr : (α show_impl * α num_impl) → α → unit =
fun (type a) ((show : a show_impl), (num : a num_impl)) (x : a) →
let module Num = (val num : NUM with type t = a) in
let open Num
in print show (x + from_int 1)

(*An instantiation*)
let print_incr_int (x : int) : unit = print_incr (show_int, num_int) x


If α is in Show then we can easily extend Show to include the type α list. As we saw earlier, this kind of thing can be done with an approriate functor.

    module type LIST_SHOW =
functor (X : SHOW) → SHOW with type t = X.t list

module List_show : LIST_SHOW =
functor (X : SHOW) → struct
type t = X.t list

let show =
fun xs →
let rec go first = function
| [] → "]"
| h :: t →
(if (first) then "" else ", ") ^ X.show h ^ go false t
in "[" ^ go true xs
end

There is also another way : one can write a function to dynamically compute an α list show_impl from an α show_impl.
  let show_list : α show_impl → α list show_impl =
fun (type a) (show : a show_impl) →
let module Show = (val show : SHOW with type t = a) in
(module struct
type t = a list

let show : t → string =
fun xs →
let rec go first = function
| [] → "]"
| h :: t →
(if (first) then "" else ", ") ^ Show.show h ^ go false t
in "[" ^ go true xs
end : SHOW with type t = a list)

let testls : string = let module Show =
(val (show_list show_int) : SHOW with type t = int list) in
Show.show (1 :: 2 :: 3 :: [])


The type-class Mul is an aggregation of the type-classes Eq and Num together with a function to perform multiplication.

   module type MUL = sig
include EQ
include NUM with type t := t

val mul : t → t → t
end

type α mul_impl = (module MUL with type t = α)

module type MUL_F =
functor (E : EQ) (N : NUM with type t = E.t) → MUL with type t = E.t

A default instance of Mul can be provided given compatible instances of Eq and Num.
    module Mul_default : MUL_F =
functor (E : EQ) (N : NUM with type t = E.t)  → struct
include (E : EQ with type t = E.t)
include (N : NUM with type t := E.t)

let mul : t → t → t =
let rec loop x y = begin match () with
| () when eq (x, (from_int 0)) → from_int 0
| () when eq (x, (from_int 1)) → y
| () → y + loop (x + (from_int (-1))) y
end in loop

end

module Mul_bool : MUL with type t = bool =
Mul_default (Eq_bool) (Num_bool)

Specific instances can be constructed as needs demand.
   module Mul_int : MUL with type t = int = struct
include (Eq_int : EQ with type t = int)
include (Num_int : NUM with type t := int)

let mul = Pervasives.( * )
end

let dot : α mul_impl → α list → α list → α =
fun (type a) (mul : a mul_impl) →
fun xs ys →
let module M = (val mul : MUL with type t = a) in
sum (module M : NUM with type t = a)@@ List.map2 M.mul xs ys

let test_dot =
dot (module Mul_int : MUL with type t = int) [1; 2; 3] [4; 5; 6]

Note that in this definition of dot, coercision of the provided Mul instance to its base Num instance is performed.

This last section provides an example of polymorphic recursion utilizing the dynamic production of evidence by way of the show_list function presented earlier.

   let rec replicate : int → α → α list =
fun n x → if n <= 0 then [] else x :: replicate (n - 1) x

let rec print_nested : α. α show_impl → int → α → unit =
fun show_mod → function
| 0 → fun x → print show_mod x
| n → fun x → print_nested (show_list show_mod) (n - 1) (replicate n x)

let test_nested =
let n = read_int () in
print_nested (module Show_int : SHOW with type t = int) n 5


References:
[1] Implementing, and Understanding Type Classes -- Oleg Kiselyov
[2] Modular Type Classes -- Harper et. al.

## Wednesday, October 26, 2016

### Haskell type-classes in OCaml and C++

Haskell type-classes in OCaml and C++

This article examines the emulation of Haskell like type-classes in OCaml and C++. It follows [1] closely (recommended for further reading), extending on some of the example code given there to include C++.

First stop, a simplified version of the Show type-class with a couple of simple instances.

    class Show a where
show :: a -> string

instance Show Int where
show x = Prelude.show x -- internal

instance Show Bool where
str True = "True"
str False = "False"

The OCaml equivalent shown here uses the "dictionary passing" technique for implementation. The type-class declaration Show in Haskell translates to a data-type declaration for a polymorphic record α show in OCaml.
    type α show = {
show : α → string
}

let show_bool : bool show = {
show = function | true → "True" | false → "False"
}

let show_int : int show = {
show = string_of_int
}

In C++ we can use a template class to represent the type-class and specializations to represent the instances.
      template <class A> struct Show {};

template <>
struct Show<int> {
static std::string (*show)(int);
};
std::string(*Show<int>::show)(int) = &std::to_string;

template <>
struct Show<bool> {
static std::string show (bool);
};
std::string Show<bool>::show (bool b) { return b ? "true" : "false"; }


Next up print, a parametrically polymorphic function.

      print :: Show a => a -> IO ()
print x = putStrLn$show x  According to our dictionary passing scheme in OCaml, this renders as the following.  let print : α show → α → unit = fun {show} → fun x → print_endline@@ show x  The key point to note here is that in OCaml, evidence of the α value's membership in the Show class must be produced explicitly by the programmer. In C++, like Haskell, no evidence of the argument's membership is required, the compiler keeps track of that implicitly.  template <class A> void print (A const& a) { std::cout << Show<A>::show (a) << std::endl; }  This next simplified type-class shows a different pattern of overloading : the function fromInt is overloaded on the result type and the (+) function is binary.  class Num a where fromInt :: Int -> a (+) :: a -> a -> a sum :: Num a => [a] -> a sum ls = foldr (+) (fromInt 0) ls  Translation into OCaml is as in the following.  type α num = { from_int : int → α; add : α → α → α; } let sum : α num → α list → α = fun {from_int; add= ( + )} → fun ls → List.fold_right ( + ) ls (from_int 0)  Translation into C++, reasonably mechanical. One slight disappointment is that it doesn't seem possible to get the operator '+' syntax as observed in both the Haskell and OCaml versions.  template <class A> struct Num {}; namespace detail { template <class F, class A, class ItT> A fold_right (F f, A z, ItT begin, ItT end) { if (begin == end) return z; return f (fold_right (f, z, std::next (begin), end), *begin); } }//namespace<detail> template <class ItT> typename std::iterator_traits<ItT>::value_type sum (ItT begin, ItT end) { using A = typename std::iterator_traits<ItT>::value_type; auto add = Num<A>::add; auto from_int = Num<A>::from_int; return detail::fold_right (add, from_int (0), begin, end); }  In Haskell, Int is made a member of Num with this declaration.  instance Num Int where fromInt x = x (+) = (Prelude.+)  Returning to OCaml, we can define a couple of instances including the one above like this.  let int_num : int num = { from_int = (fun x → x); add = Pervasives.( + ); } let bool_num : bool num = { from_int = (function | 0 → false | _ → true); add = function | true → fun _ → true | false → fun x → x }  The code defining those above instances in C++ follows.  template <> struct Num<int> { static int from_int (int); static int add (int, int); }; int Num<int>::from_int (int i) { return i; } int Num<int>::add (int x, int y) { return x + y; } template <> struct Num<bool> { static bool from_int (int); static bool add (bool, bool); }; bool Num<bool>::from_int (int i) { return i != 0; } bool Num<bool>::add (bool x, bool y) { if (x) return true; return y; }  Here now is a function with two type-class constraints.  print_incr :: (Show a, Num a) => a -> IO () print_incr x = print$ x + fromInt 1

In OCaml this can be written like so.
    let print_incr : (α show * α num) → α → unit =
fun (show, {from_int; add= ( + )}) →
fun x → print show (x + (from_int 1))

In C++, this is said as you see below.
    template <class A>
void print_incr (A x) {
}

Naturally, the above function will only be defined for types A that are members of both the Show and Num classes and will yield compile errors for types that are not.

Moving on, we now look at another common pattern, an instance with a constraint : a Show instance for all list types [a] when the element instance is a member of Show.

    instance Show a => Show [a] where
show xs = "[" ++ go True xs
where
go _ [] = "]"
go first (h:t) =
(if first then "" else ", ") ++ show h ++ go False t


In OCaml, this takes the form of a function. The idea is, given evidence of a type α's membership in Show the function produces evidence that the type α list is also in Show.
    let show_list : α show → α list show =
fun {show} →
{show = fun xs →
let rec go first = function
| [] → "]"
| h :: t →
(if (first) then "" else ", ") ^ show h ^ go false t in
"[" ^ go true xs
}

It might be possible to do better than the following partial specialization over vector<> in C++ (that is, to write something generic, just once, that works for a wider set ofsequence types) using some advanced meta-programming "hackery", I don't really know. I suspect finding out might be a bit of a rabbit hole best avoided for now.
    template <class A>
struct Show<std::vector<A>> {
static std::string show (std::vector<A> const& ls);
};

template <class A>
std::string Show<std::vector<A>>::show (std::vector<A> const& ls) {
bool first=true;
typename std::vector<A>::const_iterator begin=ls.begin (), end=ls.end ();
std::string s="[";
while (begin != end) {
if (first) first = false;
else s += ", ";
//A compile time error will result here if if there is no
//evidence that A is in Show
s += Show<A>::show (*begin++);
}
s += "]";

return s;
}


In this next example, we need a type-class describing types that can be compared for equality, Eq. That property and the Num class can be combined to produce a type-class with a super-class and a default.

    class Eq where
(==) :: a -> a -> bool
(/=) :: a -> a -> bool

deriving instance Eq Bool
deriving instance Eq Int

class (Eq a, Num a) => Mul a where
(*) :: a -> a -> a
x * _ | x == fromInt 0 = fromInt 0
x * y | x == fromInt 1 = y
x * y | y + (x + (fromInt (-1))) * y

dot :: Mul a => [a] -> [a] -> a


## Prefix operators

The ! ("bang") prefix operator, has a predefined semantic as the operation of "de-referencing" a reference cell. A custom prefix operator can made by from a ! followed by one or more symbol characters.

So, to give some examples, one can define prefix operators like !!, !~ or even something as exotic as !::>. For example, one might write something like

let ( !+ ) x : int ref → unit = incr x

as a syntactic sugar equivalent to fun x → incr x

Additionally, prefix operators can begin with one of ~ and ? and, as in the case of !, must be followed by one or more symbol characters. So, in summary, a prefix operator begins with one of

! ~ ?

and is followed by one or more symbol characters.

For example let ( ~! ) x = incr x defines an alternative syntax equivalent to the !+ operator presented earlier.

Prefix operators have the highest possible precedence.

## Infix operators

It is in fact possible to define operators in 5 different categories. What distinguish these categories from each other are their associativity and precedence properties.

### Level 0

Level 0 operators are left associative with the same precedence as =. A level 0 operator starts with one of

= < > | & \$

and is followed by zero or more symbol chars. For example, >>= is an operator much beloved by monadic programmers and |> (pipe operator) is a builtin equivalent to let ( |> ) x f = f x.

### Level 1

Level 1 operators are right associative, have a precedence just above = and start with one of

@ ^

. That is, these operators are consistent with operations involving joining things. @@ (the "command" operator) of course has a predefined semantic as function application, that is, equivalent to the definition let ( @@ ) f x = f x.

### Level 2

Level 2 operators are left associative have a precedence level shared with + and - and indeed, are defined with a leading (one of)

+ -

and, as usual, followed by a sequence of symbol characters. These operators are consistent for usage with operations generalizing addition or difference like operations. Some potential operators of this kind are +~, ++ and so on.

### Level 3

Level 3 operators are also left associative and have a precedence level shared with * and /. Operators of this kind start with one of

* / %

followed by zero or more symbol characters and are evocative of operations akin to multiplication, division. For example, *~ might make a good companion for +~ of the previous section.

### Level 4

Level 4 operators are right associative and have a precedence above *. The level 4 operators begin with

**

and are followed by zero or more symbol characters. The operation associated with ** is exponentiation (binds tight and associates to the right). The syntax **~ would fit nicely into the +~, *~ set of the earlier sections.