From oleg-at-okmij.org Thu Mar  8 22:36:58 2007
To: caml-list@inria.fr
Subject: Operator overloading
From: oleg-at-pobox.com
Message-ID: <20070309073658.8F020AD34@Adric.metnet.fnmoc.navy.mil>
Date: Thu,  8 Mar 2007 23:36:58 -0800 (PST)
Status: OR


This message illustrates the translation of Haskell98 non-constructor
classes to OCaml, which gives us bounded polymorphism and a sort of
polymorphic recursion in OCaml.

It has to be remarked first that overloading is quite a complex issue:
please see `A Theory of Overloading' by Stuckey and Sulzmann (TOPLAS
2005) for many gory details.  The issue of the type of the plus
operation: 'a->'a->'a or 'a->'b->'c is not an abstract
subtlety. That's why functional dependencies where introduced in
Haskell (and quite often we need local functional dependencies to
resolve overloading). There are three main techniques of implementing
overloading: full inlining (aka C++), dictionary passing, and
the intensional type analysis. The latter is like `switch' and dictionary
passing is like a `vtable'. GHC and Hugs implement dictionary passing,
whereas JHC and Chameleon implement typeclasses via intensional type
analysis. I suspect F# might be doing something like that too, because
CLI might have run-time type tags. 

Non-constructor Haskell 98 classes (that is, overloading over parameter
of the kind *) can be implemented in OCaml in a straightforward way.

We start with a typical Haskell code

class Numb a where
    add :: a -> a -> a
    shw :: a -> String

instance Numb Int where
    add x y = x + y
    shw = show

instance Numb Float where
    add x y = x + y
    shw = show

instance Numb a => Numb [a] where
    add = zipWith add
    shw a = "[" ++ concatMap (\x -> (shw x) ++ " ") a ++ "]"

summ (h:t) = foldl add h t

test1 = shw (add [(1::Int),2,3] [4,5,6])
test2 = shw (summ (add [(1::Int),2,3] [4,5,6]))
test3 = shw (summ [(1.0::Float),2.0,3.0])
test4 = shw (summ [[(1.0::Float),2.0,3.0], [4,5,6], [7,8,9]])

We introduce a class Numb with two methods, for addition and for
showing. The latter is quite handy. The instances for Int and Float
are trivial. The instance of [a] says that if the type of list
elements is in class Numb, the list is in class Numb as well. Note the
definition for the "add" method in that case. It looks recursive: the
body of 'add' invokes 'add' itself, but on a different type.

We then define a function summ. Its inferred type is 
	summ :: (Numb a) => [a] -> a
The function is bounded polymorphic: it works on lists of any type
provided that type is in Numb. The tests test3 and test4 demonstrate
that summ can sum lists and lists of lists, etc.

Here's the OCaml translation:

(* class Numb a *)
type 'a numb = {add: 'a -> 'a -> 'a; shw: 'a -> string};;

(* instance Numb Int *)
let numb_i = {add = (+); shw = string_of_int};;
(* instance Numb Float *)
let numb_f = {add = (+.); shw = string_of_float};;

(* instance Numb a => Numb [a] *)
let numb_l numb_e = {add = List.map2 numb_e.add; 
		     shw = fun a -> 
		       "[" ^ List.fold_right 
			       (fun e z -> " " ^ numb_e.shw e ^ z) a "]"};;

(* we can define a bounded polymorphic function summ *)
let summ numb (h::t) = List.fold_left numb.add h t;;

let test1 = 
  let n = numb_l numb_i in
  n.shw (n.add [1;2;3] [4;5;6]);;

let test2 = 
  let n = numb_l numb_i in
  numb_i.shw (summ numb_i (n.add [1;2;3] [4;5;6]));;

let test3 = 
  numb_f.shw (summ numb_f [1.0;2.0;3.0]);;

let test4 = 
  let n = numb_l numb_f in
  n.shw (summ n [[1.0;2.0;3.0]; [4.0;5.0;6.0]; [7.0;8.0;9.0]]);;


The inferred type of summ in OCaml is
	val summ : 'a numb -> 'a list -> 'a = <fun>
It is instructive to compare it to the Haskell type. The only
difference is in the shape of the arrow: "Numb a =>" vs "'a numb ->".
Instead of the double arrow of Haskell we have the single arrow in
OCaml. The OCaml function summ is likewise bounded polymorphic: it
applies to arrays of any type provided that we have the _evidence_
(the dictionary) that the type is in the class numb. We must pass that
evidence as the first argument of summ. Granted, the burden of procuring
this evidence is on us; Haskell, in contrast, can, most of the time,
build that evidence by itself. As in Haskell, we can sum lists of
numbers and lists of lists of numbers, etc.


Haskell constructor classes (overloading over the parameters of 
higher kinds) do require OCaml functors. The example is a monad. With a
bit of syntactic sugar, the monadic notation and the corresponding
overloading are tolerable in OCaml.

Conversely, OCaml and SML modules (including sealing, generative and
applicative functors and recursive structures) can be emulated in
Haskell typeclasses. Chung-chieh Shan and I wrote a couple of messages
on that topic back in August and September 2004 on the Haskell mailing
list.


John Skaller wrote: ``(Haskell does this little cheat .. it makes
typeclasses very easy to explain to OO people).'' Are you sure about
that? There has been many long and recurring threads on Haskell-Cafe
about typeclasses and OO classes. I think the common advice is _not_
to think of Haskell typeclasses as of OO classes. Ralf Laemmel and I
once wanted to elaborate on the issue of OO in Haskell; we ended up
with a 79-page paper. I guess that shows that OO is never easy.