Operator overloading
 oleg@p...
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20070309 (07:38) 
From:  oleg@p... 
Subject:  Operator overloading 
This message illustrates the translation of Haskell98 nonconstructor 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 runtime type tags. Nonconstructor 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. Chungchieh 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 HaskellCafe 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 79page paper. I guess that shows that OO is never easy.