Re: "Re: [Caml-list] A G'Caml question" + additional info

[Patrick M Doane <patrick@watson.org>]

On Sat, 30 Jun 2001, Brian Rogoff wrote:

> On Sat, 30 Jun 2001, Patrick M Doane wrote:
> > On Sat, 30 Jun 2001, John Max Skaller wrote:
> > > 	G'caml makes it easier to write readable algorithms,
> > > and to do 'cut and paste' genericity. But it can't do what
> > > you can do in C++. 
> > I agree.  Although I'm not advocating that it do everything you can do in
> > C++.
> 
> Less talk, more coding examples please.

Here's a simple example motivating my thoughts in this discussion:

generic get = case
  | string -> int -> char => String.get

let print_first x = get x 0

generic get = case
  | include get
  | $a array -> int -> $a => Array.get
;;
print_first [|0|]

As far as I can tell, there are no current plans for this kind of code
to work with G'caml.

> GCaml polymorphism is remarkably
> easy to use. A while ago, when there was some discussion of overloading
> on the list, Pierre Weis mentioned that he'd like a style of overloading
> that would allow us to overload array access, string access, and hashtbl
> access. How easy is that? Well, it writes itself from that sentence
> 
> generic get = case
>   | string -> int -> char  => String.get
>   | $a array -> int -> $a  => Array.get
>   | $a list -> int -> $a => List.nth
>   | ($a,$b) Hashtbl.t -> $a -> $b => Hashtbl.find 
>   | ($a -> $b) -> $a -> $b => fun f -> f;;

This part works great - we get clear and powerful overloading. I really
like it!

> This extensional polymorphism is beautiful, as well as practical. One of
> the nice things about the STL is the way that it allows you to write the
> algorithms independently of the containers, using the iterator interfaces. 
> You can write functions over generics like "get" to achieve the same
> effect in GCaml. 

The algorithms and containers can't be independent though because either:

  1) All containers (generic values) must be declared before any
algorithms (derived generics) which use them are declared. 

  2) Derived generics must include the generic values as parameters.

The first solution makes it difficult for users to extend a system.  If I
redefine a generic value like get, then existing code cannot make use of
it unless I 'cut and paste' to achieve genericity.

The second solution is similar to what we have in O'caml today, although
with G'Caml I can refer to things by a common name and get some cool
functions that were not expressible before. 

> > > > The proposed 'include' feature makes it much easier to
> > > > extend generic values, but doesn't help with derived generics. 
> 
> How doesn't it help?

The include feature, if I understand the proposition correctly, only
applies to generic values and would not effect any derived generics that
have been defined.  So I can't easily extend the definition of 'get' and
have existing code make use of those improvements.  Here are some possible
ideas: 

 1) Add a feature like 'include' which re-evaluates the definition of a
derived generic in the current context.  This simplifies the 'cut and
paste' approach by not specifying the code redundantly.

 2) Modify the semantics of derived generics such that the use of a
generic value depends on a link-time (or run-time) analysis.  It was
pointed out that this could be difficult to understand, but the OO system
already has a similar confusion.

 3) Delegate this issue to the use of objects or functors.

> > > 	Objects can help, but really that isn't the answer.
> > > The answer is more like: what can we do to make C++ like
> > > generics properly parametric?
> > > 
> > > 	It is possible to make STL like algorithms in Ocaml now.
> > > The problem is that you have to pass in a LOT of data, such as
> > > functions to deref and increment the iterator.
> > 
> > I think that one can implement much of the STL algorithms in the Caml
> > object system (avoiding the need to pass lots of data). 
> 
> While I think the STL is a fine design for a language like C++, I'm not
> sure that STL emulation is high on my list of criteria for an OCaml 
> overloading extension. 

Yes, the STL has little support for functional programming, and has other
aspects which are messy.  Attempting to implement something close to STL
in G'Caml is still a useful exercise though.  We can get a better sense
for the differences between the two langauges.

The point I wanted to make was that the object system can express many
concepts of the C++ template system. I can't think of anything that
wouldn't be expressible when G'caml is integrated with O'caml objects. 

> Once that include feature is in *and* it is integrated with the rest of
> the type system (modules and signatures, classes, polymorphic variants,
> etc.) we'll have an enormous amount of power. 

I think we both want a system which allows for data structures and
algorithms to be independent.  So far, I can't see how all the pieces will
fit together though.

Patrick


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr