From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA00939; Thu, 4 Jul 2002 17:18:38 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA00445 for ; Thu, 4 Jul 2002 17:18:37 +0200 (MET DST) Received: from sunny.pacific.net.au (sunny.pacific.net.au [203.25.148.40]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g64FIZP16952 for ; Thu, 4 Jul 2002 17:18:35 +0200 (MET DST) Received: from wisma.pacific.net.au (wisma.pacific.net.au [210.23.129.72]) by sunny.pacific.net.au with ESMTP id g64FIRSs029437; Fri, 5 Jul 2002 01:18:27 +1000 (EST) Received: from ozemail.com.au (ppp188.dyn1.pacific.net.au [61.8.1.188]) by wisma.pacific.net.au with ESMTP id BAA11507; Fri, 5 Jul 2002 01:18:20 +1000 (EST) Message-ID: <3D246739.4030204@ozemail.com.au> Date: Fri, 05 Jul 2002 01:18:17 +1000 From: John Max Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: Chris Hecker CC: caml-list@inria.fr Subject: Re: [Caml-list] Re: generic programming References: <200207030246.WAA28665@dewberry.cc.columbia.edu> <4.3.2.7.2.20020703102610.0248b280@mail.d6.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Chris Hecker wrote: > > > Is it, in the sense that Stepanov and those guys mean it? John Max > Skaller and I were talking about this a long time ago, and I thought > he posted this to the list but it turns out it was in email to me, but > here goes anyway: > > "Sure. I have a 'problem' example: try to implement STL iterators > in Caml. I don't have the expertise in Caml: I think this requires > 'higher order functors'. Several people have attempted this, no one > has succeeded that I know of." > > Perhaps he's reading and can explain some of the problems. > > Caml polymorphism&functors and C++ templates seem to have different > properties, and I wonder what you can and can't write in each. > > > Is generic programming possible with O'Caml? > Sure it is possible ! C++ templates use TWO kinds of 'polymorphism' together: 1) parametric polymorphism 2) overloading (ad hoc polymorphism) for example: template int g(T t) { return f(t); } Notice that 'f' is chosen at instantiation time, based on the type T of t. You cannot do this in Ocaml, where you must write instead: let g t f = f t in ... that is, you have to pass the 'dependent function' f explicitly. This includes methods. The only functions in Ocaml that can act on a value which has the type of a parameter (but which do not need to be explicit arguments) are parametrically polymorphic ones, for example: let pair x = (x,x) in .. let f x = pair x (* don't need to pass 'pair', its polymorphic *) now, C++ iterators *depend* on ad hoc polymophism. For example the algorithm: template iterator2 copy(iterator1 src, iterator1 end, iterator2 dst) { while(src != end) *dst++ = *src++; return dst; } has 'ad hoc' operations on the types iterator1 and iterator2: namely comparison, dereference, and increment, and, there are also two implicit types iterator1::value_type iterator2::value_type which either must be the same, or there is a conversion between them .. which is yet another function not passed explicitly to the template. As you can see, C++ relies on the *syntactic form* of the template body, to express the genericity, and overloading at instantiation time. In general, this is not 'well principled' although it works well in practice (but also leads to disasters when it fails without a compilation error). technically, instantiation must be functorial, in the sense of both category theory an Ocaml functors (since these are the same idea ..), that is, instantiation should 'preserve structure'. But there is no assurance the C++ instantiation mechanism is functorial. To make 'copy' work in Ocaml, you can either pass ALL the arguments explicitly -- and there are a lot of them here .. or you can package them up in a module with a specifiic interface and use a functor. Ocaml functors (and polymorphic functions) guarratee functorial instantiation on the algebraic (free) types. If a module has constraints represented as comments, these are not necessarily preserved by instantiation .. so both systems have limitations. Only two data structures in Ocaml readily admit iterators: lists and arrays. Other data structures like hastables, sets, maps, etc, have control inverted iterators, which are much weaker (that is, you have to provide a callback which is given each value in turn -- this is very much less useful than the C++ construction dual to it in which the values are fetched in turn by an user algorithm...you have to 'control invert' the algorithm to use it with Ocaml XXX.iter functions, which is non-trivial and greatly obscures the code. [But I think it can always be done using a mechnical procedure, related to continuatiuon passing .. my Felix compiler does in precisely this, but only for a simgle message source at present] The real problem for STL style iterators is this: in C++, the very point of iterators is that container independent algorithms can be written. There is no easy way to do this in Ocaml, at least not without using classes. There is a technical way to express the limitation: in Ocaml, functions are value polymorphic. But higher order functions cannot be functorially polymorphic, that is, that cannot vary over different data functors (data structures like lists and arrays are known as data functors). Hence, we have List..map Array.map Hashtble.map etc, instead of just 'map' . Functorial polymorphism can be implemented for a wide class of functors in an extension of ML: there is work being done by Barry Jay at UTS on this. See http://www-staff.it.uts.edu.au/~cbj/Publications/functorial_ml.ps.gz Perhaps some of the type theorists reading the above text can give a better and more proper explanation. But basically: C++ allows polymorphism over data functors, but that polymorphism is NOT parametric like it should be. Ocaml insists of everything being 'correct', which excludes features which 'sort of work sometimes' :-) -- John Max Skaller, mailto:skaller@ozemail.com.au snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. voice:61-2-9660-0850 ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners