From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.4 required=5.0 tests=AWL,NO_REAL_NAME,SPF_FAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 42976BC69 for ; Fri, 9 Mar 2007 08:38:01 +0100 (CET) Received: from selenite.metnet.navy.mil (selenite.metnet.navy.mil [192.16.167.32]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l297bwYp013196 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Fri, 9 Mar 2007 08:38:00 +0100 Received: (qmail 22876 invoked by uid 107); 9 Mar 2007 07:37:55 -0000 Received: from unknown (HELO Adric.metnet.fnmoc.navy.mil) (10.100.105.102) by selenite.metnet.navy.mil with SMTP; 9 Mar 2007 07:37:55 -0000 Received: by Adric.metnet.fnmoc.navy.mil (Postfix, from userid 760) id 8F020AD34; Thu, 8 Mar 2007 23:36:58 -0800 (PST) To: caml-list@inria.fr Subject: Operator overloading Reply-To: oleg@pobox.com Errors-To: oleg@okmij.org From: oleg@pobox.com Message-Id: <20070309073658.8F020AD34@Adric.metnet.fnmoc.navy.mil> Date: Thu, 8 Mar 2007 23:36:58 -0800 (PST) X-Miltered: at concorde with ID 45F10ED6.005 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; overloading:01 oleg:01 haskell:01 ocaml:01 bounded:01 polymorphism:01 recursion:01 ocaml:01 overloading:01 toplas:01 'a-:01 'a-:01 'b-:01 dependencies:01 haskell:01 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 = 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.