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

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

[John R Harrison]

Markus Mottl writes:

| This is a shortcoming of the standard library that there are no
| polymorphic implementations of "Set" and similar. It's very easy to
| extract a polymorphic (module-) version from the existing code. 

I strongly agree with this point. From recent messages it seems that I'm
just one of a whole army of O'Caml users who've essentially
cut-and-pasted code out of the standard set library with a fixed
polymorphic comparison function inserted. For a polymorphic language to
make dealing with polymorphic sets so awkward seems ridiculous.

Perhaps the justification for the decision to include orderings in the
standard interface is that the default equality and orderings may not
behave as desired on arbitrary types, e.g. non-canonical abstract data
types like other sets. However, a better solution might be to make
equality on abstract types settable (see an earlier thread I started on
this topic). Will G'Caml be any help in this respect? That is, will it
allow one to "overload" equality on particular types?

John.
-------------------
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

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

[Patrick M Doane]

On Wed, 11 Jul 2001, Brian Rogoff wrote:

> On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> > Sven [mailto:luther@dpt-info.u-strasbg.fr] wrote:
> > > On Tue, Jul 10, 2001 at 02:21:02PM -0400, Krishnaswami, Neel wrote:
> > > > 
> > > > Can you describe how I'd write something like the show function in 
> > > > Haskell, or the print-object generic function in Dylan? I've looked
> > > > at the G'Caml documentation, and it doesn't look like it's possible
> > > > to extend a generic function with new branches.
> > > 
> > > i think they are speacking about an extension to g'caml that 
> > > would use the include keyword and permit such extension.
> > > Please read the previous mails about this thread.
> > 
> > Ah, I misunderstood, then. I thought the claim was that include 
> > wouldn't be included, but that it wasn't necessary. 
> 
> No. The discussion is about whether the proposed include feature is
> sufficient. My original concerns had to do with modeling recursive
> generics in such a way that they can be extended (hence my question about
> a form of open recursion) and I think Patrick was proposing something 
> like dynamic binding (Patrick?). 

Not quite dynamic binding... I'd still like everything to be resolved
statically.  The thoughts I initially had were:

  1) Link time analysis once all types are known.  This isn't suitable
for all applications and is also much harder to implement, but still an
option.

  2) Specialized syntax to re-analyze the body of a derived generic to
avoid "cut and paste" polymorphism (I like that term Max!).  Eventually, I
realized this is present through the functor system.

To really make me happy, I'd like to be able to use functors and generics
without having any performance penalty for cases when it matters.  I know
this can lead to code bloat in general, but the C++ community is certainly
moving along just fine with it (and continuing to make improvements).
Maybe some options to the compiler to control this behavior would be
useful.

> I've managed to convince myself that once generics play with modules and
> functors, include will give me enough rope (to hang myself with :) for
> now. Still, it is different from type classes and CLOS/Dylan generics, so 
> read the papers, the mails by Jun Furuse on include, and start kicking
> those tires! 

It's definitely sufficient.  I think we'll still see a large number of
messages from people being confused by the lack of dynamic binding, but
that's okay -- the functor approach should be easier to understand/debug.

So here's another thought about G'caml.  Suppose we have two record types
like this:

type t1 = {
  t1_field: int
};

type t2 = {
  t2_field: int
};

The field names have to be unique to be able to access them, but we can
"share" the field name through a generic:

generic get_field = case
  | t1 -> int => fun x -> x.t1_field
  | t2 -> int => fun x -> x.t2_field

Any hope for a compiler to auto-generate these declarations and provide a
syntax similar to dot notation?

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

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

[Markus Mottl]

On Wed, 11 Jul 2001, Bruce Hoult wrote:
> But the language itself seems to be starting to rival C++ for sheer
> complexity. When you want to do something you seem to have a choice
> of using this feature, or *this* one, or *this* newly developed one.

Having choices is not necessarily bad, being forced to using many
alternatives is. I think that OCaml has succeeded quite well so far in
keeping different features apart as one can see in the standard library,
which can be used with the core language + modules alone. I hope this
will stay so!

Whether one or the other feature will be thrown out at some point of
time depends on how it performs in real work. That's not necessarily
easily tried in small scale experiments.

> Dylan is conceptually a much simpler language, with less intimidating 
> syntax, and you can easily express what you want to do using a very 
> small number of basic constructs.

Maybe, I don't know. But it does not declare itself as a research
language.  Everybody who uses OCaml should be aware of its status. If
you use experimental features, this is likely to burn you some time
in the future. If you stay with the core + module language, you should
probably be fairly safe for the foreseeable future.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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

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

[Bruce Hoult]

At 9:22 AM -0700 7/11/01, Brian Rogoff wrote:
>G'Caml also has dynamics, so I imagine we'll be seeing other disaffected
>Dylanites dallying with it too ;-).

I'm not sure about that.

Caml's primary interest for me is that it is mature and extremely 
well implemented.

But the language itself seems to be starting to rival C++ for sheer 
complexity. When you want to do something you seem to have a choice 
of using this feature, or *this* one, or *this* newly developed one.

Dylan is conceptually a much simpler language, with less intimidating 
syntax, and you can easily express what you want to do using a very 
small number of basic constructs.  It depends on the compiler to find 
the way in which a particular use of a particular construct is not 
making use of the full generality and thus can be optimized, so it 
does require quite complex compilers to get speed.  Dylan's biggest 
problem has been the fickleness of corporate development efforts, 
compared to the constancy of INRIA over a very long period.

For which they are to be congratulated, of course!

-- Bruce
-------------------
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

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

[Brian Rogoff]

On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> Sven [mailto:luther@dpt-info.u-strasbg.fr] wrote:
> > On Tue, Jul 10, 2001 at 02:21:02PM -0400, Krishnaswami, Neel wrote:
> > > 
> > > Can you describe how I'd write something like the show function in 
> > > Haskell, or the print-object generic function in Dylan? I've looked
> > > at the G'Caml documentation, and it doesn't look like it's possible
> > > to extend a generic function with new branches.
> > 
> > i think they are speacking about an extension to g'caml that 
> > would use the include keyword and permit such extension.
> > Please read the previous mails about this thread.
> 
> Ah, I misunderstood, then. I thought the claim was that include 
> wouldn't be included, but that it wasn't necessary. 

No. The discussion is about whether the proposed include feature is
sufficient. My original concerns had to do with modeling recursive
generics in such a way that they can be extended (hence my question about
a form of open recursion) and I think Patrick was proposing something 
like dynamic binding (Patrick?). 

I've managed to convince myself that once generics play with modules and
functors, include will give me enough rope (to hang myself with :) for
now. Still, it is different from type classes and CLOS/Dylan generics, so 
read the papers, the mails by Jun Furuse on include, and start kicking
those tires! 

G'Caml also has dynamics, so I imagine we'll be seeing other disaffected 
Dylanites dallying with it too ;-).

-- Brian


-------------------
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

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

[Krishnaswami, Neel]

Sven [mailto:luther@dpt-info.u-strasbg.fr] wrote:
> On Tue, Jul 10, 2001 at 02:21:02PM -0400, Krishnaswami, Neel wrote:
> > 
> > Can you describe how I'd write something like the show function in 
> > Haskell, or the print-object generic function in Dylan? I've looked
> > at the G'Caml documentation, and it doesn't look like it's possible
> > to extend a generic function with new branches.
> 
> i think they are speacking about an extension to g'caml that 
> would use the include keyword and permit such extension.
> Please read the previous mails about this thread.

Ah, I misunderstood, then. I thought the claim was that include 
wouldn't be included, but that it wasn't necessary. 


--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
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

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

[Sven]

On Tue, Jul 10, 2001 at 02:21:02PM -0400, Krishnaswami, Neel wrote:
> Patrick M Doane [mailto:patrick@watson.org] wrote:
> > 
> > On Mon, 2 Jul 2001, Brian Rogoff wrote:
> > 
> > > I'm convinced that the include scheme, when properly integrated with
> > > modules, will be sufficient. We need more experience with 
> > > the current scheme. 
> > 
> > I'm convinced now too, it took me a day or two to think things over to
> > come to the same conclusion. 
> 
> Can you describe how I'd write something like the show function in 
> Haskell, or the print-object generic function in Dylan? I've looked
> at the G'Caml documentation, and it doesn't look like it's possible
> to extend a generic function with new branches.

yet ...

i think they are speacking about an extension to g'caml that would udse the
include keyword and permit such extension.

Please read the previous mails about this thread.

Friendly,

Sven Luther
-------------------
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

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

[Krishnaswami, Neel]

Patrick M Doane [mailto:patrick@watson.org] wrote:
> 
> On Mon, 2 Jul 2001, Brian Rogoff wrote:
> 
> > I'm convinced that the include scheme, when properly integrated with
> > modules, will be sufficient. We need more experience with 
> > the current scheme. 
> 
> I'm convinced now too, it took me a day or two to think things over to
> come to the same conclusion. 

Can you describe how I'd write something like the show function in 
Haskell, or the print-object generic function in Dylan? I've looked
at the G'Caml documentation, and it doesn't look like it's possible
to extend a generic function with new branches.

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
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

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

[Patrick M Doane]

On Mon, 2 Jul 2001, Brian Rogoff wrote:

> I'm convinced that the include scheme, when properly integrated with
> modules, will be sufficient. We need more experience with the current
> scheme. 

I'm convinced now too, it took me a day or two to think things over to
come to the same conclusion.

Caml already has support for generic programming by using functors but
they can get cumbersome when concepts are highly separated.  For example,
I usually see every algorithm written as a functor.  This is very
powerful, but requires many more lines of code for all the functor
instantiation. In some sense, we also lose a nice aspect of core ML -- the
ability to avoid specifying types. 

Initially I thought that G'caml (when integrated with the rest of the
language) wouldn't be able to improve on this model for writing libraries. 
When all the code is under central control, the code can obviously be
reordered such that all generic values come before all derived generics. 

I now see that a library which wants to provide generic algorithms will be
much easier to write with G'caml.  Rather than providing a functor for
every algorithm which must be instantiated in for a large variety of
types, the library would provide one functor per module which needs to be
instantiated once with the generic values defined by the application. This
all makes sense, and is easy to trace/follow manually.

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

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

[Brian Rogoff]

On Sun, 1 Jul 2001, Patrick M Doane wrote:
> On Sat, 30 Jun 2001, Brian Rogoff wrote:
> > 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|]

Right, but I expect that if you want something like this you'll be
satisfied with adding the new print_first (re)definition after the new
get, or if you're just changing the program, at worst recompiling after
the change. If you have modules (GCaml doesn't yet), this should be fine.

The case that I see as annoying involves composing recursive generics, but
since in current versions of ML (Mosml 2 excepted) recursive definitions
don't span module boundaries this probably isn't too important. 

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

I don't find that troubling. You could still incrementally define "get". 

> > 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. 

I'm thinking about independence of source code. I don't believe I'd need 
to change the algorithm source which used get if I did a decent job of
modularization. 

>   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.

That's right. It's like regular function definitions, which don't have
open recursion. Mostly this is a good thing though, right? 

> > 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.

I'm convinced that the include scheme, when properly integrated with
modules, will be sufficient. We need more experience with the current
scheme. 

> > 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.

I agree. 

> 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. 

C++ templates can express compile time computation; I don't think you can
do that in GCaml. I don't know if the STL makes use of that ability, or 
how well C++ compilers support it, etc. 

-- Brian


-------------------
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

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

[Patrick M Doane]

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

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

[Brian Rogoff]

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. 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;;

OK, I'd like a bit of syntax sugar to make this .(), but that generic does
the trick, and then some (it works with a single argument function too). 

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 proposed 'include' feature makes it much easier to
> > > extend generic values, but doesn't help with derived generics. 

How doesn't it help? 

> > 	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. 

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. 

-- Brian


-------------------
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

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

[Patrick M Doane]

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++. 
> 
> 	This is a good thing, since you can do some pretty
> unprincipled things in C++.

I agree.  Although I'm not advocating that it do everything you can do in
C++.

> 	Sure, and in C++ the iterators just don't work.

Could you elaborate on this?

> > The proposed 'include' feature makes it much easier to
> > extend generic values, but doesn't help with derived generics. 
> 
> 	One step at a time. If you _really_ want to do high level
> polymorphism, you'll have to use a more modern research language
> like FISh 2. 

What's in the works for the next version of FISh? The current version is
very interesting, but not too useful for me until more support for data
structures is added.

> 	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). It's not very
convenient because of the need to convert primitive values into objects
though. I'm still a novice with the object type system so we can probably
improve this a bit, but here is a basic implementation of STL iterators in
Caml object style:

class ['a] list_iterator list_init = object
  (* is there a better way to define eq here? *)
  val list = list_init
  method get_list = list
  method eq (x : 'a list_iterator) = x#get_list = list
  method get : 'a = List.hd list
  method incr = new list_iterator (List.tl list)
end

class ['a] list_obj l = object
  method iter_begin : 'a list_iterator = new list_iterator l
  method iter_end : 'a list_iterator   = new list_iterator []
end

class ['a] array_iterator arr_init idx_init = object
  val arr = arr_init
  val idx = idx_init
  method get_arr = arr
  method get_idx = idx
  method eq (x : 'a array_iterator) = x#get_arr == arr && x#get_idx = idx
  method get : 'a = Array.get arr idx
  method incr = new array_iterator arr (idx + 1)
end

class ['a] array_obj a = object
  method iter_begin : 'a array_iterator = new array_iterator a 0
  method iter_end : 'a array_iterator   = new array_iterator a
(Array.length a)
end

let rec for_each f first last =
  if first#eq last then ()
  else (
    f first#get;
    for_each f (first#incr) last
  )

let l = new list_obj [1;2;3]
let a = new array_obj [|1;2;3|]
;;
for_each print_int l#iter_begin l#iter_end;
for_each print_int a#iter_begin a#iter_end

-------------------
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

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

[Patrick M Doane]

On Fri, 29 Jun 2001, John Max Skaller wrote:

> Patrick M Doane wrote:
> 
> > >   We do not want to introduce the full open recursion to generic
> > > values. You could add new type cases easily using the open recursion
> > > and it should be helpful in some cases. But it can also introduce
> > > heavy semantic confusion to our programs, since in the open recursion
> > > the semantics of generic values could not be fixed until all modules
> > > are linked together.
> > 
> > I agree that this could make programs more difficult to follow, but I
> > think it is to be expected with generic programming these days.
> 
> 	Yes, its expected: which is very good reason NOT to do it.
> Its expected that all the problems associated with it have to exist,
> because people haven't seen anything better.

I would like to apply the generic programming techniques so that I can
have reusable algorithms.  The extensions provided by GCaml don't achieve
that goal although they are much more powerful than basic operator
overloading. 

If I want to define a generic function similar to the STL for_each
function, this works fine until I need to extend the system with new
iterator types.  The proposed 'include' feature makes it much easier to
extend generic values, but doesn't help with derived generics. I would
assume that most folks are interested in the reusability of those derived
generics.  Does it make sense to provide a similar construct to 'include'
for derived generics which would re-analyze the body of the code based on
a new context of generic values?  Or am I trying to abuse what these
features are intended for? Maybe this kind of approach is better suited to
the object system or using functors.

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

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

[Brian Rogoff]

On Wed, 27 Jun 2001, Patrick M Doane wrote:
> On Mon, 25 Jun 2001, Jun Furuse wrote:
> >   We do not want to introduce the full open recursion to generic
> > values. You could add new type cases easily using the open recursion
> > and it should be helpful in some cases. But it can also introduce
> > heavy semantic confusion to our programs, since in the open recursion
> > the semantics of generic values could not be fixed until all modules 
> > are linked together. 
> 
> I agree that this could make programs more difficult to follow, but I
> think it is to be expected with generic programming these days.
> Also, isn't this kind of semantic confusion already present with using the
> object oriented system?
> 
> In the following example, writing definitions like MyProgram.print may get
> very tedious in practice.
> 
> module Int = struct
>   generic print = case int -> unit => print_int
> end
> 
> module String = struct
>   generic print = case string -> unit => print_string
> end
> 
> module List = struct
>   generic print =
>    case $a list -> unit => function [] -> () | x :: xs -> print x; print xs
> end
> 
> module MyProgram = struct
>   generic print = case
>   | include Int.print
>   | include String.print
>   | include List.print
>     (*  all other print functions to follow *)
> end

Actually, that doesn't look too bad to me. Once generics play well with
modules and functors (and classes and polymorphic variants :), support the 
include syntax Jun described, and are in the release (along with a safer
marshaling) I'll be very pleased

The real issue which open recursion would solve is if you had, say, a
recursive generic for printing lists recursively, one for doing arrays
recursively, and one for doing tuples (up to some fixed arity). Here's 
how you'd write it now 

generic print_basic = case 
    | int -> unit => print_int
    | float -> unit => print_float
    | char -> unit => print_char
    | string -> unit => print_string
    | bool -> unit => 
	(function true -> print_string "true" 
         |        _ -> print_string "false")

generic rec print_seq = case 
    (* print_tuple *)
    | $a * $b -> unit => fun (u,v) -> print_seq u; print_seq v
    | $a * $b * $c -> unit => 
        fun (u,v,w) -> print_seq u; print_seq v; print_seq w
    | $a * $b * $c * $d  -> unit => 
        fun (u,v,w,x) -> 
	  (print_seq u; print_seq v; print_seq w;print_seq x)
    | $a * $b * $c * $d * $e -> unit => 
        fun (u,v,w,x,y) -> 
	   (print_seq u; print_seq v; print_seq w;print_seq x;print_seq y)
    (* print_array *)
    | $a array -> unit => fun a -> Array.iter print_seq a
    (* print_list *)
    | $a list  -> unit => fun l -> List.iter print_seq l
    | $a -> unit => print_basic;;

note that this can print a lot of stuff because of recursion:

# print_seq (1,2);;
12- : unit = ()
# print_seq (1,(2,(3,(4,(5,(6,(7,(8,9))))))));;
123456789- : unit = ()
# print_seq (1,[|(2,3);(4,5);(6,7)|],"8",9.0);;
123456789- : unit = ()

but you can't break it into parts print_tuple, print_list, print_array 
and construct print_seq by composing them. Oh well, they still give a
much needed overloading and have lots of power to spare. 

> Given what is done with Haskell type classes and C++ templates, it seems
> more confusing to me to not support open recursion.  Any thoughts?  

They're really powerful. Once the design and implementation are more
stable, we'll see how important the lack of open recursion is. I think
it's more important to have human understandable error messages and
inferred types. I'm already looking forward to the merger with OCaml
proper. 

-- Brian


-------------------
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

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

[Patrick M Doane]

On Mon, 25 Jun 2001, Jun Furuse wrote:

> Thus, the generic values are "open" to the others who include them,
> but it is not the open recursion you mentioned; print and print' are
> different values and independent each other. 
> 
>   We do not want to introduce the full open recursion to generic
> values. You could add new type cases easily using the open recursion
> and it should be helpful in some cases. But it can also introduce
> heavy semantic confusion to our programs, since in the open recursion
> the semantics of generic values could not be fixed until all modules 
> are linked together. 

I agree that this could make programs more difficult to follow, but I
think it is to be expected with generic programming these days.
Also, isn't this kind of semantic confusion already present with using the
object oriented system?

In the following example, writing definitions like MyProgram.print may get
very tedious in practice.

module Int = struct
  generic print = case int -> unit => print_int
end

module String = struct
  generic print = case string -> unit => print_string
end

module List = struct
  generic print =
   case $a list -> unit => function [] -> () | x :: xs -> print x; print xs
end

module MyProgram = struct
  generic print = case
  | include Int.print
  | include String.print
  | include List.print
    (*  all other print functions to follow *)
end

Given what is done with Haskell type classes and C++ templates, it seems
more confusing to me to not support open recursion.  Any thoughts?  

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

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

[Jun Furuse]

Hello,

Thanks your comment about the exntesion. It is natural idea to extend
generic values and it must be definitively required. This extension
of generic values cannot be handled by the normal redefinition which
is available in G'Caml. They essentially requires its own syntax and
typing, which are still not be implemented...

Let me explain details using your example:

> # generic rec print = case 
>   | int -> unit => print_int
>   | string -> unit => print_string
>   | $a list -> unit => 
>       function [] -> ()
>       |   x :: xs -> print x; print xs
>   ;;            
>
> # generic rec print = case float -> unit => print_float | $a -> unit =>
> print;;
> 
> # print 1.0;;
> 1- : unit = ()
> # print 1 (* infinite loop! *)
> 
> Well, that should be expected, since we try and print an int, which isn't
> a float, so we try (from $a -> unit => print) to print, ad
> infinitum. 

Yes, as you pointed out, your second definition of print will not
work, because its definition is completely independent from the first;
it uses the same name print, but it points to the new print. 
We can have the same thing even in the normal let rec expressions:

   let f () = print_string "hello";;
   let rec f () = f ()

The second f does not call the first f, but itself (and loops forever).

> # let print' = print ;;
>
> # generic rec print = case 
>   | float -> unit => print_float 
>   | $a -> unit => print'
>   ;;
>
> # print [1.0;2.0;3.0];; 
> This generic full instance is used with type float list -> unit
>  which is not its valid instance of ...

This does not work neither. Since what print recursively calls
is the original print, not the newly defined print. Therefore
we cannot use the interesting mixed case of float list -> unit...

> Is there some trick to build up recursive generics by parts? One thing 
> to do is to break the recursive generic into a non-recursive generic
> and a recursive function which applies the generic to the elements, 
> but that feels like cheating. Maybe open recursion for generics would 
> be desirable, so that I can add a new case and have the recursive call in 
> an existing case call the new one? Yes, it's a half baked idea, but maybe 
> a better cook can finish baking...

As we have seen, redefinitions cannot achieve what you (and I) want. 
We will need some special construction for the extension. We will have
the new "include" phrase to import the type case definitions of the
other generic values. For example:

	generic print' = case
	| include print
	| float -> unit => print_float
	;;

This newly defined print' will be semantically equivalent to the 
following generic definition:
 
	generic print' = case
	| int -> unit => print_int
	| string -> unit => print_float
	| $a list -> unit =>
	     function [] -> ()
		    | x :: xs -> print' x; print' xs  
	| float -> unit => print_float
	;;

Note that the recursive occurrences of print in the original
definition are now replaced by print', in order to point 
the newly defined generic value. In this sense, the include phrase is
not the pure inclusion of the source. Thus, the new print' can print
float lists:

      # print' [1.2; 3.4; 5.6];;
      1.23.45.6- : unit = ()

Thus, the generic values are "open" to the others who include them,
but it is not the open recursion you mentioned; print and print' are
different values and independent each other. 

  We do not want to introduce the full open recursion to generic
values. You could add new type cases easily using the open recursion
and it should be helpful in some cases. But it can also introduce
heavy semantic confusion to our programs, since in the open recursion
the semantics of generic values could not be fixed until all modules 
are linked together. 

-----------------------------------------------------------------------

Several people have courageously tried some module programming using
G'Caml and reported troubles. I am sorry but you cannot write .mli
files with extensional polymorphic values. At the time of the
implementation, we had not had clear idea to store generic constraints
in signatures... Please only use the toplevel.

I explained briefly the limitations of the current implementation at

  http://pauillac.inria.fr/~furuse/generics/

However, none of them are theoretical. 
They can be fixed when I will get some more time for coding!

Regards,

-----------------------------------------------------------------------
Jun P. Furuse 					 Jun.Furuse@inria.fr
-------------------
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