Re: [Caml-list] Re: generic programming

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

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<class T> 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 <class iterator1, class iterator2>
    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