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=0.0 required=5.0 tests=AWL 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 213EEBC0C for ; Thu, 18 Jan 2007 10:49:03 +0100 (CET) Received: from ipmail01.adl2.internode.on.net (ipmail01.adl2.internode.on.net [203.16.214.140]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0I9n0Hj024925 for ; Thu, 18 Jan 2007 10:49:01 +0100 Received: from ppp27-234.lns1.syd6.internode.on.net (HELO rosella) ([59.167.27.234]) by ipmail01.adl2.internode.on.net with ESMTP; 18 Jan 2007 20:18:58 +1030 X-IronPort-AV: i="4.13,204,1167571800"; d="scan'208"; a="75564193:sNHT27325753" Subject: Re: [Caml-list] Polymorphic Variants From: skaller To: Jacques Garrigue Cc: caml-list@yquem.inria.fr In-Reply-To: <20070118.152023.36917506.garrigue@math.nagoya-u.ac.jp> References: <20070118.102808.108741650.garrigue@math.nagoya-u.ac.jp> <1169093137.5327.33.camel@rosella.wigram> <20070118.152023.36917506.garrigue@math.nagoya-u.ac.jp> Content-Type: text/plain Date: Thu, 18 Jan 2007 20:48:53 +1100 Message-Id: <1169113733.5327.125.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 45AF428C.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; variants:01 overloading:01 overloading:01 polymorphism:01 polymorphism:01 model:01 hackery:01 stl:01 lookup':01 haskell:01 typeclass:01 functors:01 constructors:01 stl:01 ocaml:01 On Thu, 2007-01-18 at 15:20 +0900, Jacques Garrigue wrote: > From: skaller > > On the other hand some code would just be impossible > > without overloading. For example C has > > > > char, short, int, long, long long > > unsigned versions > > float, double, long double > > > > which is 13 distinct 'number' types, and I would hate > > to have to write: > > > > 1 int_add 2 > > 1L long_add 2L > > Actually this is not only overloading that is used here, but also > automatic conversions. In C/C++ yes, both overloading and automatic conversions. In Felix there are no automatic conversions. However Felix still allows you to write 1 + 1L if you open the module 'MixedInt'. That module provides a constrained polymorphic function: fun add[t1:fast_ints, t2:fast_ints]: t1 * t2 -> arithmax(t1,t2) ="$1+$2" ; where 'fast_ints' is a typeset, which is a finite set of concrete types, and t: typeset in this context means t where t isin typeset (which is also legal Felix). This is, in effect, the complete set of all the 100 overloads on the 10 C integer type pairs, represented as polymorphism with a constraint checked at the point of call. Note the implementation here is "$1+$2" which leverages C++ overloading. Typesets and constrained polymorphism are just a convenient sugar for writing huge numbers of overloads out. It is interesting that to model the C/C++ type system here I had to do some quite advanced type system hackery, but the result is mixed mode arithmetic without any automatic conversions. It is also possible to defer choice of types to the instantiation phase, which can now be done in a well principled manner using Felix typeclasses. In particular you can now, finally, after 6 years work, do a 'fold' on an STL container using typeclasses without needing any 'dependent name lookup'. this is not first class polyadic programming, since (unlike Haskell?) only types can be typeclass parameters, not functors (type constructors, eg STL vector, list, set etc can't be arguments). However the result is easier to use than Ocaml I think: typeclasses are weaker than Ocaml functors but they're much easier to use, since they work with 'ordinary' code. In Ocaml to write 'generic' code you have to put your code inside a functor definition. Perhaps that is easy if you have, for example, one container type, but typical programs will use several container types, which would require several levels of nested functors in Ocaml. I think this would mean that the Ocaml code would be fragile in the sense that you'd have to do a lot of housekeeping if the implementation changed to use a slighly different set of containers -- you'd have to rewrite all the nested functor wrappers. I wonder if there is a better way? I really don't like typeclasses that much: they only allow a single instantiation. For example 1 < 2 is an instance of a total ordering typeclass for integers, but integers can also be sorted in the other direction. You can't have both orderings, instead you need a dummy type type revint = RevInt of int which supports the reverse ordering. Whereas with Ocaml/ML functors the comparison function is a specific argument. I think this is correct. Hmm .. am I right in thinking Ocaml's local modules also allow local functor instantiations? This must help quite a bit? Having to explicitly instantiate is quite a pain though, compared to C++ templates, typeclasses in either Haskell or Felix, or plain old Ocaml polymorphic functions: people keep asking for a polymorphic version of the Ocaml Set .. and I'm sure I use Hashtbl polymorphic version to avoid having to instantiate Map all over the place *** *** This is not so trivial due to lack of inter module recursion across ml file boundaries I wonder if Ocaml couldn't support automatic functor instantiation by providing an "canonical" instance. For example: module IntSet = Set.Make (Int) module FloatSet = Set.Make (Float) let s1 = IntSet.add s1 1 (* uses manual instantiation *) let s2 = Set.Make(Int).add s 1 (* uses canonical instantiation *) The canonical instantiation is 'generated' by the compiler. It would have to be shared across ml files. This would be similar to having nominally typed records BUT also having a canonical structurally typed instance, namely tuples. > When writing numeric computations in ocaml, I > find it just as painful to have to add float_of_int, as to add the dot > after all operators. (In number of characters, float_of_int might be > the biggest...) Nah, Felix uses BigInt internally for integers in case constants fit in C integer types but not Ocaml ones .. BigInt.int_of_bigint is bigger .. :) > For overloading alone, the module system could help. > If we had the operators defined with different types in each of the > numeric type modules, then one could just choose the numeric type used > with "open Mynumtype". Yes. Interestingly in Felix you can open both modules and typeclasses, AND you can partially specialise type parameters if they're polymorphic, AND these things can be overloaded .. all at once! This can be a bit confusing .. especially since the typeclass feature is new and undoubtedly contains bugs. > This is one of the reasons I pushed for having > a local "let open" construct... which can be simulated by "let > module", at a slight cost. Right. You want to localise the impact. Using 'open' is only "poor man's genericity" but a localised version would be better than nothing. Interestingly Felix supports that, and it is precisely how typeclasses passed to functions are implemented: fun f[t with Eq[t]] (a:t, b:t, c:t) => a < b and b < c ; // same as "f: Eq t => t :: t * t -> t" in Haskell? is actually implemented by open Eq[t]; return a < b and b < c; So in Ocaml if you could also "pass" in the module to be opened it would be really cool! This should not require properly first class modules: Felix does it without them so Ocaml could too :) -- John Skaller Felix, successor to C++: http://felix.sf.net