Re: [Caml-list] Generics?

[John Max Skaller <skaller@ozemail.com.au>]

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