RE: [Caml-list] Generics?

RE: [Caml-list] Generics?

[Dave Berry]

In the broader community, "generics" also refers to parameterised
classes or modules.  Examples include ML's functors, C++ class
templates, and parameterised classes in Eiffel, OCaml, and others.
There are some papers comparing the power and expressiveness of
inheritance vs genericity (I think Bertrand Meyer wrote one of these).

Chris's concern's are largely addressed by functors, given suitable
optimisations in the implementation.  Overloading can also help.

-----Original Message-----
From: Brian Rogoff [mailto:bpr@best.com]
Sent: Tuesday, April 03, 2001 19:14
To: Chris Hecker
Cc: caml-list@inria.fr
Subject: [Caml-list] Generics?


On Mon, 2 Apr 2001, Chris Hecker wrote:
> I find OCaml pretty wordy as it is (no overloading being a big problem
> here, since the types all float into the names, as someone said), and
> making it moreso seems to me to be a mistake.  I also feel (like
> Patrick) that there are more important things (overloading, module
> recursion, generics) that need fixing than labeling right now.

I'm confused by your use of the term "generics", which I've seen in
another of your posts as well. Care to explain to the uninitiated? 

FYI, "generic polymorphism" is being used as a term to describe the kind
of overloading formerly called "extensional polymorphism", and that was 
probably influenced by CLOS/Dylan style generic functions with multiple 
dispatch. So generics are already overloaded enough, maybe you need to 
disambiguate :-). 

I don't find Ocaml wordy at all, but then I've used (and liked) Ada so 
it's probably just whatever you're used to...
 
-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives:
http://caml.inria.fr
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] Generics?

[John Max Skaller]

Chris Hecker wrote:

> I first started thinking about this when I was trying to wrap my head 
> around the difference between Caml style polymorphism and C++ templates.  

	Ocaml generic functions require all arguments
to be passed in explicitly. C++ templates don't: some of the arguments
are passed implicitly. These arguments have to be looked up at
instantiation
time, in places depending on the types of the template type arguments.
For example:

	template<class T> T add(T t1, T t2) { return t1 + t2; }

Here, operator+ must be looked up when T is bound. It may be
a method of T, or it could be a function defined in the namespace
in which T is defined, or any base of T. Or it could be
defined in the context in which the template is defined.
Lookup is followed by overload resolution.

Consider even the case:

	template<class T> T add(T t1, T t2) { return t1.add(t2); }

and you see there is a constraint that T must be a class with
a method 'add' defined. The constraint is _implicit_.

Ocaml generic functions provide 'unconstrained genericity':
they work for ALL types. More precisely, if a call 'types'
correctly, then the function will work. This is NOT true
in C++, where it is not enough to know that a call types
correctly, since the instantiation can still fail
due to a failure looking up the implicit arguments
(or during subsequent overload resolution).

In general the use of implicit arguments is a bad, it breaks
the fundamental principle 'Explicit Interfaces' of Bertrand Meyer.

Note however that even Ocaml is 'weaker' than desired, since
interfaces cannot fully express constraints: type systems aren't
expressive enough. For example, a module may be:

	module type integer = sig
		type int
		val incr : int -> int
		val succ : int -> int -> bool
	end

and you can see the interface is inadequate, because the axiom

	succ x (incr x)

is not represented. This is relevant to generics too, since
a functor may require this constraint of its argument,
but it cannot be stated.

While one can live with constraints stated in comments
(by manually checking the constraints), Ocaml also has the
opposite problem. Some higher order generics cannot be defined,
and some of these CAN be defined using C++ templates.

Consider the generic 'map' which takes a container

	container<T>

and applies a function

	f:T -> V

to each element, producing a container

	container<V>

In Ocaml, there is one 'map' written per data structure. 
But 'map' is actually quite generic for a large class of containers.
In C++ you can write a template for map, but it relies on
overloading things like the begin() and end() methods used to
obtain the iterators.

In 'Functorial ML' (including FISh 2), there is a single 'map'
function that works for all data structures. So advances are
being made, to define 'even more generic'
functions than ocaml can support, and separately, work is being
done to allow constraints to be expressed (all obeying
the 'Explicit Interfaces' requirement).

[Note that Ocaml does have some ability to handle constraints]

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] Generics?

[Chris Hecker]

>I'm confused by your use of the term "generics", which I've seen in
>another of your posts as well. Care to explain to the uninitiated? 

I would definitely be one of the uninitiated as well.  :)

I should point out, as I said in my original post ages ago asking about the status of these features, that the generics thing is a little cloudy in my mind (as opposed to overloading and module recursion).  I'll mumble a bit and then maybe somebody with more of a clue can help out.

I first started thinking about this when I was trying to wrap my head around the difference between Caml style polymorphism and C++ templates.  Basically, if I write a sort routine in Caml, I need to pass in the comparator as a closure (not really, because </>/compare/etc. are polymorphic themselves, but hopefully you get the general idea).  Now, ignoring overloaded operators, in the C++ sort function you'd just type if(compare(a,b)) { ... } and the compare(type,type) function would have to be declared somewhere for the type you're sorting, but you don't have to pass compare to the sort.

There are pros and cons of both ways, as far as I can tell.  The Caml way lets you totally decouple the sort function from the code that calls it, whereas in current C++ implementations you basically need to have the sort function in a header file because it resolves compare() by name at the time of compilation.  On the other hand, in Caml I have to pass closures around all over the place, and for a simple case like compare(), I get a function call per comparison while the C++ case is easy to inline and generate optimal code as if the specific typed versions were hand written.

So anyway, I guess I want the best of both types (excuse the pun) of polymorphism/genericity.  I'm not exactly sure what "the best of both" looks like, however, so I'm not exactly sure what I want.  When I was thinking about this before, I ran across some good posts on the subject in the archive.

http://caml.inria.fr/archives/199803/msg00011.html
http://caml.inria.fr/archives/200004/msg00122.html

I guess a partial specification of "the best of both" would be that if all the information was available statically, then I'd like the optimal code to be generated, like C++.  If I stick a generic function into a datastructure or pass it as a closure, then I'm fine with the runtime checks that the second message above implies.

To take a slightly higher level view, I'd like to be able to do some of the generic programming stuff that Stepanov had in mind when he designed the STL.  I don't see how to do that without overloading and some kind of generic facility (or maybe overloading is enough, not sure).  Passing closures isn't really the same thing.

Vague enough for you?  :)

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

[Caml-list] Generics?

[Brian Rogoff]

On Mon, 2 Apr 2001, Chris Hecker wrote:
> I find OCaml pretty wordy as it is (no overloading being a big problem
> here, since the types all float into the names, as someone said), and
> making it moreso seems to me to be a mistake.  I also feel (like
> Patrick) that there are more important things (overloading, module
> recursion, generics) that need fixing than labeling right now.

I'm confused by your use of the term "generics", which I've seen in
another of your posts as well. Care to explain to the uninitiated? 

FYI, "generic polymorphism" is being used as a term to describe the kind
of overloading formerly called "extensional polymorphism", and that was 
probably influenced by CLOS/Dylan style generic functions with multiple 
dispatch. So generics are already overloaded enough, maybe you need to 
disambiguate :-). 

I don't find Ocaml wordy at all, but then I've used (and liked) Ada so 
it's probably just whatever you're used to...
 
-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr