Stdlib

Stdlib

[Jonathan Bryant]

Quick (and rather random question) about the standard library.  I
noticed that, like the STL, many of the modules are very similar and
implement many of the same functions (iter, map, etc.).  Unlike the STL
or the Java Standard API, these modules are each completely
independent.  Why hasn't there been a push to do something like
functorize these modules?  For example: List, Array, Hashtbl, Set, and
Map are all collections.  Couldn't you factor out something to make it
easier to extend the library, sort of like the Java API?  Parametric
Polymorphism handles the generics of the elements of the set, so
couldn't the algorithms be factored out leaving three distinct parts
(Elements, Collections of Elements, Operations on Collections), sort of
like in the STL?

I know Java and C++ are bad words here, but you have to admit that at
least that part of Sun's library is rather well designed as is, for the
most part, the STL.  Give the devil his due, I guess... :)

--Jonathan Bryant
  jtbryant@valdosta.edu
  Student Intern
  Unix System Operations
  VSU Information Technology

"Das Leben ohne Music ist einfach ein Irrtum, eine Strapaze, ein" Exil."
("Life without music is simply an error, a pain, an exile.")
--Frederich Nietzsche

"The three cardinal values of a programmer are laziness, impatience, and
hubris."
--Perl Man Page

Re: [Caml-list] Stdlib

[skaller]

On Mon, 2005-10-31 at 09:41 -0500, Jonathan Bryant wrote:
> Quick (and rather random question) about the standard library.  I
> noticed that, like the STL, many of the modules are very similar and
> implement many of the same functions (iter, map, etc.).  Unlike the STL
> or the Java Standard API, these modules are each completely
> independent.  Why hasn't there been a push to do something like
> functorize these modules? 

Because the technology to do that is WAY in advance of the
current Ocaml.

What you are asking for is *polyadic* functions, aka
functorial polymorphism. For example, a fold function
that works on all data structures, that is, polymorphic
not just on the data type (such as int), 
but also the data functor (such as list).

Such a function would never work with abstracted modules,
it would require data types to be defined entirely algebraically.

All of this can be done (I worked on a system that did it),
however it is definitely non-trivial. It is well in advance
of anything Haskell can do also.

In fact, C++ DOES provide such functions: the STL is built
on this concept. .. however the mechanism is not 'type safe': 
it works only by hackery based on overloading
and dependent name lookup.

This problem is partly solved in Extlib, which provides an
equivalent concept to STL iterators. However the Extlib
solution, whilst not so general as STL, is fully safe
(since it is written in Ocaml .. :)


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Stdlib

[Jonathan Roewen]

> Because the technology to do that is WAY in advance of the
> current Ocaml.
>
> What you are asking for is *polyadic* functions, aka
> functorial polymorphism. For example, a fold function
> that works on all data structures, that is, polymorphic
> not just on the data type (such as int),
> but also the data functor (such as list).
>
> Such a function would never work with abstracted modules,
> it would require data types to be defined entirely algebraically.
>
> All of this can be done (I worked on a system that did it),
> however it is definitely non-trivial. It is well in advance
> of anything Haskell can do also.

Really? What about type classes? Haskell has fmap! That's an example
of what you mean, correct?

Jonathan

Re: [Caml-list] Stdlib

[skaller]

On Tue, 2005-11-01 at 13:11 +1300, Jonathan Roewen wrote:

> > All of this can be done (I worked on a system that did it),
> > however it is definitely non-trivial. It is well in advance
> > of anything Haskell can do also.
> 
> Really? 

Really. It is in some sense the Holy Grail of programming
language design. Ocaml doesn't even support higher order
polymorphism -- you cannot pass a polymorphic function to
a function -- when you try it gets monomorphised (yes,
it can be done by wrapping the function in a record or
using classes).

> What about type classes? Haskell has fmap! That's an example
> of what you mean, correct?

Yes, it is an example of what one would like to do,
however it is not the same. You have to provide certain
primitives, and then others are derived from them.

The problem is .. this is nominal typing. In fact, Ocaml
can do this same thing with functors, but the result
is merely a sum of all the named cases -- it isn't
abstract.

Haskell makes it easier to name the types (monadic notation)
but it isn't any more expressive than Ocaml's functors.
In fact, it is probably the other way around, its just that
instantiating all those dang functors by hand is a pain.
C++ is a breeze by comparison, since templates are instantiated
automatically.

The point is that the much vaunted 'intensional polymorphism'
in Ocaml only applies to type variables -- there are no
functor variables.

BTW: any real type theorist disgusted with my explanation is
welcome to explain it properly -- in particular why it
is THE central problem of programming theory.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Stdlib

[Brian Hurt]

On Mon, 31 Oct 2005, Jonathan Bryant wrote:

> Quick (and rather random question) about the standard library.  I
> noticed that, like the STL, many of the modules are very similar and
> implement many of the same functions (iter, map, etc.).  Unlike the STL
> or the Java Standard API, these modules are each completely
> independent.  Why hasn't there been a push to do something like
> functorize these modules?  For example: List, Array, Hashtbl, Set, and
> Map are all collections.  Couldn't you factor out something to make it
> easier to extend the library, sort of like the Java API?  Parametric
> Polymorphism handles the generics of the elements of the set, so
> couldn't the algorithms be factored out leaving three distinct parts
> (Elements, Collections of Elements, Operations on Collections), sort of
> like in the STL?

The question here is: why?  What good would factoring out the common base 
actually do?

In Java and C++, with their style of inheritance, if you don't explicitly 
factor out the common base, then you can't inherit from/manipulate the 
common base functionality.  But Ocaml does structural comparisons for 
matching, not inheritance trees.  So if you wanted to write a bit of code 
that could be used with lists, arrays, maps, etc., you could just write:

module type Collection = sig
     type 'a t
     val map : ('a -> 'b) -> 'a t -> 'b t
end;;

module MyCode(Col: Collection) = struct
     ...
end;;

OK, you have to hack a little bit because list.mli and array.mli don't 
explicitly define the 'a t type.  But they could.  And going:

module MyListCode =
     MyCode(struct type 'a t = 'a list let map = List.map end)
;;

isn't that big a deal.  But the important point is that this still works, 
even if the common functionality you want to depend upon isn't explicitly 
factored out.  A similiar stunt can be done with objects.

The other reason to do this is to factor out the common code.  But there 
isn't that much code to share among the various maps, iters, and folds. 
Well, a little bit of shared code between Map and Set (and see the Pagoda 
Core Foundation code for an example of how they could share code), but 
that's about it.

I suppose you could convert every ordered collection into either an 
iterator of some sort or a lazy list, and then map/fold/iter on that and 
while this sort of functionality is usefull in general (and I'd like to 
see it added to the standard library), there are generally usefull 
optimizations that can be applied.  For example, if I'm mapping a Map to 
another Map, I know the new tree will have the same shape as the old 
tree.  And so on.  This sort of optimization would be lost going through 
iterator or lazy list.

Brian

Stdlib

[Jonathan Bryant]

Wow, guys.  Thanks for the responses.  That really cleared up my
question :).  I (unfortunately) have to learn some of the STL for
another project and the thought occurred to me.

On another note, I would love to do this other project in OCaml, but it
is OpenGL intensive (read: based) and LablGL drives me nuts.  The named
argument thing drives me up the wall because it's more information that
I don't want to have to learn and internalize.  If the author of that
package reads this list, then I apologize.  You've done a fantastic job
of mapping the API, but I really do not like the OCaml syntax for both
Labeled and Optional arguments in general.  Does anyone know of an
OpenGL package that is /complete/ and /not/ labeled?  There is, of
course, the option of writing a module/set of modules that use the
existing C stubs an are not labled, but that would be a last-ditch
effort.

Thanks!

--Jonathan Bryant
  jtbryant@valdosta.edu
  Student Intern
  Unix System Operations
  VSU Information Technology

"Das Leben ohne Music ist einfach ein Irrtum, eine Strapaze, ein" Exil."
("Life without music is simply an error, a pain, an exile.")
--Frederich Nietzsche

"The three cardinal values of a programmer are laziness, impatience, and
hubris."
--Perl Man Page

Re: [Caml-list] Stdlib

[Jacques Garrigue]

From: Jonathan Bryant <jtbryant@valdosta.edu>

> On another note, I would love to do this other project in OCaml, but it
> is OpenGL intensive (read: based) and LablGL drives me nuts.  The named
> argument thing drives me up the wall because it's more information that
> I don't want to have to learn and internalize.  If the author of that
> package reads this list, then I apologize.  You've done a fantastic job
> of mapping the API, but I really do not like the OCaml syntax for both
> Labeled and Optional arguments in general.  Does anyone know of an
> OpenGL package that is /complete/ and /not/ labeled? 

Well, you're entitled to your own opinion.
A few years ago we had a few discussions on this list that were worse
than that.
Yet, a result of these discussions is that labeled arguments are much
less intrusive than before.
The explanation is in the tutorial part of the manual. Namely:

   As an exception to the above parameter matching rules, if an
   application is total, labels may be omitted. In practice, most
   applications are total, so that labels can be omitted in
   applications.

That is, you don't have to write labels in your code.
At least not for non-optional arguments.
Optional arguments still require a label.

The examples going with lablGL are heavily labelled, but you are not
forced to write it that way. As another example, GlDraw.vertex takes
labeled and optional arguments, but you can also use
GlDraw.vertex[234] which take tuples.

So I'd suggest you try to use it without labels.
And maybe later you will realize that, when reading your code later
on, your prefer to have labels. Or maybe your opinion won't change
anyway...

On the other hand, I don't know whether lablGL qualifies as complete,
as it only implements openGL 1.2, without extensions.

Jacques Garrigue

Re: [Caml-list] Stdlib

[Jon Harrop]

On Tuesday 01 November 2005 00:07, Jonathan Bryant wrote:
> On another note, I would love to do this other project in OCaml, but it
> is OpenGL intensive (read: based) and LablGL drives me nuts.  The named
> argument thing drives me up the wall because it's more information that
> I don't want to have to learn and internalize.  If the author of that
> package reads this list, then I apologize.  You've done a fantastic job
> of mapping the API, but I really do not like the OCaml syntax for both
> Labeled and Optional arguments in general.  Does anyone know of an
> OpenGL package that is /complete/ and /not/ labeled?  There is, of
> course, the option of writing a module/set of modules that use the
> existing C stubs an are not labled, but that would be a last-ditch
> effort.

You can omit the labels in most cases. I've done my fair share of OpenGL 
programming, both from C/C++ and from OCaml, and I was quite surprised to 
hear that Jacques has had complaints about his API. The C interface is flat 
and unlabelled because C doesn't support hierarchical interfaces, polymorphic 
variants and labelled/optional arguments. There is still room for improvement 
with lablGL but the API alone is a significant step in the right direction, 
IMHO.

After all, if you have an aversion to labelled arguments you can always omit 
the labels. :-)

I would value safety above completeness but writing a safe (and still 
efficient) interface to OpenGL is difficult.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists