[Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Vasili Galchin]

[-- Attachment #1: Type: text/plain, Size: 557 bytes --]

Hello,
 
    I am reluctantly learning C++ STL (Standard Template Library) and the notion of templates. Templates don't seem to be that great ... just parametric plymorphism done in a somewhat heavy handed way when compared to the same in OCaml, Haskell, etc. However, teh STL notion of containers and available operations allowed on containers does seem to be be very powerful and not available in OCaml. Is the last statement true?
 
Kind regards, Vasili

		
---------------------------------
Do you Yahoo!?
vote.yahoo.com - Register online to vote today!

[-- Attachment #2: Type: text/html, Size: 654 bytes --]

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Nicolas Cannasse]

[-- Attachment #1: Type: text/plain, Size: 712 bytes --]

  Hello,

      I am reluctantly learning C++ STL (Standard Template Library) and the notion of templates. Templates don't seem to be that great ... just parametric plymorphism done in a somewhat heavy handed way when compared to the same in OCaml, Haskell, etc. However, teh STL notion of containers and available operations allowed on containers does seem to be be very powerful and not available in OCaml. Is the last statement true?

  Kind regards, Vasili
You might have a look at ExtLib Enum module that is providing an uniform way of accessing  elements of a container and applying functionnal lazy operations (map, filter...) on them.
http://ocaml-lib.sourceforge.net/

Regards,
Nicolas Cannasse

[-- Attachment #2: Type: text/html, Size: 1544 bytes --]

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Vasili Galchin]

[-- Attachment #1: Type: text/plain, Size: 880 bytes --]

Thank you, Nicolas!
 
Vasili

Nicolas Cannasse <warplayer@free.fr> wrote:
Hello,
 
    I am reluctantly learning C++ STL (Standard Template Library) and the notion of templates. Templates don't seem to be that great ... just parametric plymorphism done in a somewhat heavy handed way when compared to the same in OCaml, Haskell, etc. However, teh STL notion of containers and available operations allowed on containers does seem to be be very powerful and not available in OCaml. Is the last statement true?
 
Kind regards, Vasili
You might have a look at ExtLib Enum module that is providing an uniform way of accessing  elements of a container and applying functionnal lazy operations (map, filter...) on them.
http://ocaml-lib.sourceforge.net/
 
Regards,
Nicolas Cannasse

		
---------------------------------
Do you Yahoo!?
Yahoo! Mail - 50x more storage than other providers!

[-- Attachment #2: Type: text/html, Size: 1756 bytes --]

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Vasili Galchin]

[-- Attachment #1: Type: text/plain, Size: 1172 bytes --]

Hello,
 
   I found this paper that might be useful to Nicolas and others! http://www.cs.kent.ac.uk/pubs/1997/224/index.html
 
Regards, Vasya

Vasili Galchin <vasiliocaml@yahoo.com> wrote:
Thank you, Nicolas!
 
Vasili

Nicolas Cannasse <warplayer@free.fr> wrote:
Hello,
 
    I am reluctantly learning C++ STL (Standard Template Library) and the notion of templates. Templates don't seem to be that great ... just parametric plymorphism done in a somewhat heavy handed way when compared to the same in OCaml, Haskell, etc. However, teh STL notion of containers and available operations allowed on containers does seem to be be very powerful and not available in OCaml. Is the last statement true?
 
Kind regards, Vasili
You might have a look at ExtLib Enum module that is providing an uniform way of accessing  elements of a container and applying functionnal lazy operations (map, filter...) on them.
http://ocaml-lib.sourceforge.net/
 
Regards,
Nicolas Cannasse


---------------------------------
Do you Yahoo!?
Yahoo! Mail - 50x more storage than other providers!
		
---------------------------------
Do you Yahoo!?
Yahoo! Mail - 50x more storage than other providers!

[-- Attachment #2: Type: text/html, Size: 2431 bytes --]

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop]

On Saturday 25 September 2004 23:52, Vasili Galchin wrote:
>     I am reluctantly learning C++ STL (Standard Template Library) and the
> notion of templates. Templates don't seem to be that great ... just
> parametric plymorphism done in a somewhat heavy handed way when compared to
> the same in OCaml, Haskell, etc.

A beneficial (although inelegant) advantage of templates is the ability to 
partially specialise programs by performing arbitrary compile-time 
computation. This is not available in OCaml. This will be addressed (in a 
much more powerful and elegant way) by MetaOCaml just as soon as Taha at al. 
stop reading this mailing list and start working harder. ;-)

> However, teh STL notion of containers and 
> available operations allowed on containers does seem to be be very powerful
> and not available in OCaml. Is the last statement true?

That last statement is only true in the absence of higher-order functions. 
Therefore, it does not apply to OCaml.

In functional languages, like OCaml, the operations on containers are much 
more productively factored into higher-order functions which are then 
container-type independent. In particular, the ubiquitous map and fold 
functions.

For example, to sum the floating-point elements of a container in C++, one 
might write:

#include <iostream>
#include <list>
#include <vector>

template<typename IT>
double sum(IT begin, IT end)
{
  double ans=0.;
  for (IT it=begin; it!=end; it++)
    ans +. *it;
  return ans;
}

int main(void)
{
  list<double> A;
  A.push_back(0.);
  A.push_back(1.);
  A.push_back(2.);
  A.push_back(3.);
  A.push_back(4.);
  vector<double> B;
  B.push_back(0.);
  B.push_back(1.);
  B.push_back(2.);
  B.push_back(3.);
  B.push_back(4.);
  cout << sum(A.begin(), A.end()) << endl
    << sum(B.begin(), B.end()) << endl;
}

The OCaml equivalent would be:

let sum fold_left c = fold_left ( +. ) 0. c
sum List.fold_left [0.; 1.; 2.; 3.; 4.]
sum Array.fold_left [|0.; 1.; 2.; 3.; 4.|]

If you have more time than sense then you'll prefer the C++ version (which is 
vastly more verbose and a bit quicker). If, on the other hand, you can see 
the forest for the trees then you'll want to be using OCaml because, given 
the same time, you can write OCaml programs which are both faster and smaller 
than equivalents written in virtually any other language. Not to mention that 
compilation of equivalent programs is typically between one and two orders of 
magnitude faster using ocamlopt rather than g++.

Believe it or not, the previous example favours C++ more than most others. 
Check out this example of function composition from SGI's STL manual:

  list<int>::iterator new_end = 
         remove_if(L.begin(), L.end(),
                   compose2(logical_and<bool>(),
                            bind2nd(greater<int>(), 100),
                            bind2nd(less<int>(), 1000)));
    L.erase(new_end, L.end());

In OCaml:

let l = List.filter (fun x -> not (100<x<1000)) l

These days, when I read fancy statements in the STL manual, like "function 
object adaptor", I just roll around laughing.

The STL does have some contructs which do not have direct equivalents in 
OCaml. Type traits, for example, allow templates to carry information on 
concrete types such that more highly type-specialised functions can be used 
to perform a given task, chosen at compile time. However, OCaml errs on the 
side of run-time polymorphism rather than compile-time.

Cheers,
Jon.

PS: I made several errors when writing that C++ code. Even if you just put 
"A()" instead of "A" when declaring a list, you get a page full of STL 
errors. God its nice to be writing OCaml... :-)

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Radu Grigore]

On Sun, 26 Sep 2004 02:34:50 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> For example, to sum the floating-point elements of a container in C++, one
> might write:

This example is slightly unfair to C++. In the OCaml code:

> let sum fold_left c = fold_left ( +. ) 0. c
> sum List.fold_left [0.; 1.; 2.; 3.; 4.]
> sum Array.fold_left [|0.; 1.; 2.; 3.; 4.|]

...you use _two_ library functions (namely List.fold_left and
Array.fold_left). Surely you should at least use one for C++ :)

--- begin code ---
#include <vector>
#include <list>
#include <numeric>
#define ALLARRAY(a) (a), (a) + sizeof(a)/sizeof((a)[0])
#define ALL(c) (c).begin() (c).end()

int array[] = {0, 1, 2, 3, 4}; 
double ddata[] = {0., 1., 2., 3., 4.}; vector<double> dv(ALLARRAY(ddata));
int idata[] = {0, 1, 2, 3, 4}; list<int> il(ALLARRAY(idata));

int as = accumulate(ALLARRAY(array));
double ds = accumulate(ALL(dv));
int is = accumulate(ALL(il));
--- end code ---

The resulting C++ code is still uglyer than its OCaml counterpart. And
longer. But you should notice that the same accumulate function is
used for three different containers, while in OCaml you use one
function for each container type. OTOH, something that is maybe less
obvious in the code above, I do use conainer specific functions in
C++: namely begin and end.

So, in short: In OCaml you don't have iterators so the fold method is
container specific. In C++ you have iterators that allow a
container-independent "fold-like" function to be implemented. The C++
program is more verbose.

> Believe it or not, the previous example favours C++ more than most others.
> Check out this example of function composition from SGI's STL manual:

Using C++'s <functional> header (or Boost.Lambda for that matter) is
sure to give you a headache after programming a bit in a functional
language like OCaml. But the same can be said about writting
imperative code in OCaml.

I have recently compared two implementations of the same small program
in C++ and OCaml, both written by me. The OCaml one was 45% the size
of the C++ one (byte count). After compression (with bzip2) it was
67%. And it was kind of imperative job so C++ should have been in
advantage there. And I know C++ much better than OCaml, so this should
have been another advantage..

regards,
 radu
PS: ok, maybe it's unfair to ocaml now that I used macros..

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[sejourne_kevin]

Radu Grigore wrote:
> On Sun, 26 Sep 2004 02:34:50 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> 
>>For example, to sum the floating-point elements of a container in C++, one
>>might write:
> 
> 
> This example is slightly unfair to C++. In the OCaml code:
> 
> 
>>let sum fold_left c = fold_left ( +. ) 0. c
>>sum List.fold_left [0.; 1.; 2.; 3.; 4.]
>>sum Array.fold_left [|0.; 1.; 2.; 3.; 4.|]
> 
> 
> ...you use _two_ library functions (namely List.fold_left and
> Array.fold_left). Surely you should at least use one for C++ :)
not two library, but _three_ if you count module Pervasives :)


> regards,
>  radu
> PS: ok, maybe it's unfair to ocaml now that I used macros..
No it's totaly fair. There is a 'cpp' preprocessor for ocaml.

#define P(x) (fst x) (snd x) (fst x)
#define S(x) (snd x)
let x = ("world","hello");;
Printf.printf "%s %s %s %s\n" S(x) P(x);;

ocamlc -pp /lib/cpp test.ml

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop]

On Sunday 26 September 2004 06:31, Radu Grigore wrote:
> The resulting C++ code is still uglyer than its OCaml counterpart. And
> longer. But you should notice that the same accumulate function is
> used for three different containers, while in OCaml you use one
> function for each container type.

My "sum" function was used for all container types. Indeed, that was the 
point... :-)

If you don't want to supply the container-specific fold at compile-time (e.g. 
with "sum List.fold_left ...") then you can use some form of RTTI, most 
obviously objects:

let sum c = c#fold_left ( +. ) 0. c

But, essentially, this is a problem of factoring code. We wish to factor the 
commonality of operations over different types of container. Iterators are 
only one way to do this and this approach is only suitable in the absence of 
HOFs (IMHO) and in the presence of imperative style. If you have HOFs, you 
just write my "sum" function and get on with something more interesting.

> OTOH, something that is maybe less 
> obvious in the code above, I do use conainer specific functions in
> C++: namely begin and end.

Also, note that the C++ version uses "accumulate" which is effectively 
equivalent to "folding with addition". In OCaml, you can fold using any 
function you want, or write a higher-order function which folds over a given 
function. This is possible but, IMHO, not practicable in C++.

> So, in short: In OCaml you don't have iterators so the fold method is
> container specific. In C++ you have iterators that allow a
> container-independent "fold-like" function to be implemented. The C++
> program is more verbose.

My example is also borderline. Virtually anything more complicated that this 
will widen the gap between C++ and OCaml. Consider computing the variance of 
a given container of integers using rational arithmetic, or computing the 
"n"th nearest neighbours in a graph, or writing a function minimisation 
algorithm, the maximum entropy method...

> Using C++'s <functional> header (or Boost.Lambda for that matter) is
> sure to give you a headache after programming a bit in a functional
> language like OCaml. But the same can be said about writting
> imperative code in OCaml.

I'd contest that. I use mutables for things like testing that some operation 
was done at least once by an otherwise functional function. I haven't had any 
headaches...

> I have recently compared two implementations of the same small program
> in C++ and OCaml, both written by me. The OCaml one was 45% the size
> of the C++ one (byte count). After compression (with bzip2) it was
> 67%. And it was kind of imperative job so C++ should have been in
> advantage there. And I know C++ much better than OCaml, so this should
> have been another advantage..

I'm finding that OCaml code is much more concise than that. My 
imperative-style vector graphics engine in about 1/4 the size than the C++ 
version and includes much more functionality. My other work simply cannot 
feasibly be written in C/C++ due to the incidental complexity of lexing, 
parsing and interpreting in such languages.

Also, for any >1 month programming tasks, my OCaml code is _always_ faster 
than my C++ equivalents were.

Cheers,
Jon.

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Sun, 2004-09-26 at 23:05, Jon Harrop wrote:
>  If you have HOFs, you 
> just write my "sum" function and get on with something more interesting.

Nope. That only works for a limited class algorithms.
Try a map function.. woops, you can't type it .. :)

This is somehow like the covariance problem: things
kind of work for one variable by cheating, but once
you have several it fails.

> Also, note that the C++ version uses "accumulate" which is effectively 
> equivalent to "folding with addition". In OCaml, you can fold using any 
> function you want, 

Accumulate can accept a function object argument.
C++ DOES have higher order functions. They're just
very clumby to use, but they're just as powerful
as monomorphic Ocaml ones. [My Felix compiler
does all that for you .. write ML, get C++ out]

Ocaml run time can also support polymorphic higher
order functions -- but the type system as of 
Ocaml 3.04 could not. 3.08 can support them with
the same problem as C++: messy housekeeping
is required -- you have to put them in a record
or class. [This is not so good because records 
and variants are generative/nominally typed like C++ classes 
.. Ocaml classes are actually algebraic .. LOL!]

> > Using C++'s <functional> header (or Boost.Lambda for that matter) is
> > sure to give you a headache after programming a bit in a functional
> > language like OCaml. But the same can be said about writting
> > imperative code in OCaml.
> 
> I'd contest that. 

So would I. Ocaml is a much better imperative and OO language
than C++.

> > I have recently compared two implementations of the same small program
> > in C++ and OCaml, both written by me. The OCaml one was 45% the size
> > of the C++ one (byte count). After compression (with bzip2) it was
> > 67%. And it was kind of imperative job so C++ should have been in
> > advantage there. And I know C++ much better than OCaml, so this should
> > have been another advantage..
> 

Sure but Ocaml offers other advantages such as type inference
lacking in C++ that make code more concise -- as well
as nice scoping constructs, lexical scoping, higher
order functions, variants, and garbage collection.
[Did I miss something .. ? :]

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[sejourne_kevin]

skaller wrote:
> Sure but Ocaml offers other advantages such as type inference
> lacking in C++ that make code more concise -- as well
> as nice scoping constructs, lexical scoping, higher
> order functions, variants, and garbage collection.
> [Did I miss something .. ? :]
Functors?

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Mon, 2004-09-27 at 01:08, sejourne_kevin wrote:
> skaller wrote:
> > Sure but Ocaml offers other advantages such as type inference
> > lacking in C++ that make code more concise -- as well
> > as nice scoping constructs, lexical scoping, higher
> > order functions, variants, and garbage collection.
> > [Did I miss something .. ? :]
> Functors?

Ocaml's modular functors are harder to use and more verbose
the C++ templates, so I didn't include them.
You have to instantiate them manually, and also
declare interfaces etc. Of course for more
complex constructions they're probably better
(because they're more modular).

OTOH Ocaml does have a second kind of type functor --
(polymorphic type constructors) which are *easier* 
to use than C++ templates.

Eg: List is a module functor, and list is a 
one of the simpler type functors.
(Also for hashtable, which provides a simple
type functor and a modular functor parameterised
on the key type (but the value type is still
a type variable .. :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop]

On Sunday 26 September 2004 15:36, skaller wrote:
> On Sun, 2004-09-26 at 23:05, Jon Harrop wrote:
> >  If you have HOFs, you
> > just write my "sum" function and get on with something more interesting.
>
> Nope. That only works for a limited class algorithms.
> Try a map function.. woops, you can't type it .. :)

Yes you can:

# let vec_add map2 = map2 ( +. );;
val vec_add : ((float -> float -> float) -> 'a) -> 'a = <fun>

So you can then do:

# let list_add = vec_add List.map2;;
val list_add : float list -> float list -> float list = <fun>

I think you're thinking of a function to convert between 'a and 'b container 
types. This can be achieved in general by folding an insertion function using 
the fold of the input container and the insertion of the output container. As 
I've said recently, doing this in the completely generic case buys you 
nothing but writing *_of or of_* functions does, for example a list_of 
function which accepts a fold and container of any type:

# let cons h t = h::t;;
val cons : 'a -> 'a list -> 'a list = <fun>
# let list_of fold_right c = fold_right cons c [];;
val list_of : (('a -> 'a list -> 'a list) -> 'b -> 'c list -> 'd) -> 'b -> 'd 
= <fun>

Then you have:

# let list_of_array a = list_of Array.fold_right a;;
val list_of_array : 'a array -> 'a list = <fun>

> This is somehow like the covariance problem: things
> kind of work for one variable by cheating, but once
> you have several it fails.

You mean there is a trade-off of functionality between more- and less-capable 
type systems?

> Accumulate can accept a function object argument.
> C++ DOES have higher order functions.

That statement is so HOF-definition dependent that it boils down to "C++ is 
Turing complete".

> Ocaml run time can also support polymorphic higher
> order functions -- but the type system as of
> Ocaml 3.04 could not. 3.08 can support them with
> the same problem as C++: messy housekeeping
> is required -- you have to put them in a record
> or class. [This is not so good because records
> and variants are generative/nominally typed like C++ classes
> .. Ocaml classes are actually algebraic .. LOL!]

I don't follow. List.fold_left is a polymorphic HOF that's been around for 
donkey's years, AFAIK.

> Sure but Ocaml offers other advantages such as type inference
> lacking in C++ that make code more concise -- as well
> as nice scoping constructs, lexical scoping, higher
> order functions, variants, and garbage collection.
> [Did I miss something .. ? :]

Good looking programmers.

Cheers,
Jon.

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Radu Grigore]

On Sun, 26 Sep 2004 19:51:52 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> > Nope. That only works for a limited class algorithms.
> > Try a map function.. woops, you can't type it .. :)

> Yes you can:
> # let vec_add map2 = map2 ( +. );;
> val vec_add : ((float -> float -> float) -> 'a) -> 'a = <fun>
> 
> So you can then do:
> 
> # let list_add = vec_add List.map2;;
> val list_add : float list -> float list -> float list = <fun>
> 
> I think you're thinking of a function to convert between 'a and 'b container
> types.

I think the idea is that you can't write a _generic_ map. All you did
above is a dipatcher that gives the job to a specialized map function:
List.map2. The accumulate function in C++ is not a simple dispatcher.
It can implement the logic of "fold" because there is an extra level
of abstraction: iterators.

But what John says is possible in FISh (namely, writing a generic,
shape preserving map) sounds quite cool.

regards,
 radu
"Get your data structures correct first and the rest of the program
will write itself." – David Jones.
http://rgrig.idilis.ro/

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop]

On Sunday 26 September 2004 21:43, skaller wrote:
> The requirement is for a polyadic map.
> Here is the type signature:
>
> map: ('a -> 'b) -> 'a 'F -> 'b 'F

I'm confused. There is no code common to both List.map and Array.map, so what 
is being factored out into this "polyadic map" apart from this (invalid!) 
type?

> Note: the output must have exactly the same shape
> as the input: map preserves shape, it only changes
> the values stored in the 'slots' of the data structure.
> So a weird tree or graph has to come out isomorphic
> to its input.

This makes sense for array and list but what about sorted containers (e.g. 
set)?

On Sunday 26 September 2004 21:14, Radu Grigore wrote:
> I think the idea is that you can't write a _generic_ map. All you did
> above is a dipatcher that gives the job to a specialized map function:
> List.map2.

What is the difference between a generic function and a function which 
dispatches to appropriate specialised functions?

> The accumulate function in C++ is not a simple dispatcher. 
> It can implement the logic of "fold" because there is an extra level
> of abstraction: iterators.

I'd say that templating over the iterator type in C++ is equivalent to writing 
a HOF which accepts a fold in OCaml. In think, therefore, that HOFs are 
exactly the "extra level of abstraction" you speak of.

Iterators often provide extra functionality, like the ability to go backwards. 
I think John calls the ability to control the iteration, rather than be 
controlled by it (e.g. by having fold call your given function on each 
element in order) "control inversion". However, I haven't found need of this 
because all the algorithms I use are written in terms of fold, map etc.

> But what John says is possible in FISh (namely, writing a generic,
> shape preserving map) sounds quite cool.

Perhaps, but I'm not sure what this costs - I assume there is a sound 
theoretical reason for avoiding such types. In practice, I'm all for 
aggressive factoring but I can't see what we're factoring here...

Cheers,
Jon.

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Mon, 2004-09-27 at 11:59, Jon Harrop wrote:

>  In practice, I'm all for 
> aggressive factoring but I can't see what we're factoring here...

Sure you can. Consider:

type 'a F = A | B of 'a | C of 'a * 'a * int 

Can you write a map function for this? Of course you
can! What about:

type 'a F = A of int | C of 'a * int | X of 'a F * 'a

Yes, of course you can!

Its obvious how to do it! 

There *exists* a universal algorithm in your head
for writing map functions. But this pattern cannot
be encoded in Ocaml as an HOF:

map: 'a 'F -> ('a -> 'b) -> 'b 'F

You can do this provided you have only types built
from variants, tuples, and recursion (no function types).

In fact you could probably write this function
in camlp4 from the definition of each type
for which you need a map. 

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jacques GARRIGUE]

From: skaller <skaller@users.sourceforge.net>
> On Mon, 2004-09-27 at 11:59, Jon Harrop wrote:
> 
> >  In practice, I'm all for 
> > aggressive factoring but I can't see what we're factoring here...
> 
> Sure you can. Consider:
> 
> type 'a F = A | B of 'a | C of 'a * 'a * int 
> 
> Can you write a map function for this? Of course you
> can! What about:
> 
> type 'a F = A of int | C of 'a * int | X of 'a F * 'a
> 
> Yes, of course you can!
> 
> Its obvious how to do it! 
> 
> There *exists* a universal algorithm in your head
> for writing map functions. But this pattern cannot
> be encoded in Ocaml as an HOF:
> 
> map: 'a 'F -> ('a -> 'b) -> 'b 'F
> 
> You can do this provided you have only types built
> from variants, tuples, and recursion (no function types).
> 
> In fact you could probably write this function
> in camlp4 from the definition of each type
> for which you need a map. 

Not exactly: what you demonstrated here is that you can automatically
build a map function for any type definition with one (or more) type
parameter. And the solution is more or less unique because you
required this map to be polymorphic in the parameter.

I often need to define map for types with no parameters. In that case
the problems is more complex, because there are many possible
definitions for map. You need to understand the semantics of the data
structure to choose.

And most types with parameters have small definitions, so defining map
by hand is not that bad...
(Yes, I know that there is a nice programming pattern involving big
types with parameters, but you cannot do this with normal sum types :-)

Jacques Garrigue

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Radu Grigore]

On Mon, 27 Sep 2004 02:59:43 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:

> What is the difference between a generic function and a function which
> dispatches to appropriate specialised functions?

For the client of the function there is no difference.

For the writter of the function there is a big difference, especially
if it has to write the specialized versions. The good news is that the
OCaml library gives you those specialized functions (fold) for common
data structures like List and Array. The bad news is that you are on
your own if you define new data structures that can be viewed as
sequences.

The meaning of "fold" is "apply this function repeatedly for each
element of the data-structure and accumulate the result". I'd like to
be able to write this in code _once_ for every data-structure that can
be seen as a sequence (i.e. a set of totaly ordered elements). You can
do this with iterators. As the article cited by Vasili shows there is
an analogue of iterators in functional languages. Another solution is
implemented in Extlib. So we are not really talking here about
differences between OCaml and C++; we are talking about library
design.

However, John said that talking about "sequences" means that we are
actually artificially limiting a more general concept: shape. But I
don't quite understand this idea fully.

regards,
 radu
http://rgrig.idilis.ro/

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Mon, 2004-09-27 at 20:50, Radu Grigore wrote:
> On Mon, 27 Sep 2004 02:59:43 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> 
> > What is the difference between a generic function and a function which
> > dispatches to appropriate specialised functions?
> 
> For the client of the function there is no difference.

.. unless you try to apply a function to an argument 
for which there is no specialisation..

> The good news is that the
> OCaml library gives you those specialized functions (fold) for common
> data structures like List and Array. The bad news is that you are on
> your own if you define new data structures that can be viewed as
> sequences.

Its much worse than that. Consider map. You have List.map and Array.map.
Now consider mapmap:

	let mapmap F g f x = F.map g (F.map f x)

This is just two maps in a row. Except you have to write:

	let List.mapmap g f x = List.map g (List.map f x)
	let Array.mapmap g f x = Array.map g (Array.map f x)

So you have to duplicate not just the basic algorithms,
but also every generic algorithm defined compositinally.
The lack of functorial polymorphism propagates.

This is the same as needing 'list_of_int' and 'list_of_float'
in C because there is no polymorphism, only one level up.

Haskell partially solves this problem with type classes.

> The meaning of "fold" is "apply this function repeatedly for each
> element of the data-structure and accumulate the result". I'd like to
> be able to write this in code _once_ for every data-structure that can
> be seen as a sequence (i.e. a set of totaly ordered elements). 

A generalised fold doesn't require either a sequence or any
ordering -- it just applies to all the elements of a container
in any order (so it works for a tree too).

The result isn't deterministic unless the accumulation
function 'add' is order independent ie:

	add (add acc x) y = add (add acc y) x

> However, John said that talking about "sequences" means that we are
> actually artificially limiting a more general concept: shape. But I
> don't quite understand this idea fully.

Me either but -- clearly you need that concept to
deal with multi-dimensional arrays and trees, neither of
which are sequences.

The basic idea is a data type can be broken up into
two parts -- the shape and the value. Shape is a functor,
value is a type. As Jacques said, using the type variable
in an ML type annotation:

	type 'a F = ...

to distinguish the value type 'a and shape F is artificial.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop]

On Monday 27 September 2004 11:50, Radu Grigore wrote:
> On Mon, 27 Sep 2004 02:59:43 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> > What is the difference between a generic function and a function which
> > dispatches to appropriate specialised functions?
>
> For the client of the function there is no difference.
>
> For the writter of the function there is a big difference, especially
> if it has to write the specialized versions.

The equivalent to the writer of fold is the writer of an iterator. You have to 
write specialized versions for each type of iterator just as you would have 
to write your own fold.

Check out vector<T>::iterator and set<T>::iterator. Consider writing a splay 
tree in C++ using iterators. You would have to rewrite most of what's in the 
STL for "set" by hand...

> The good news is that the 
> OCaml library gives you those specialized functions (fold) for common
> data structures like List and Array. The bad news is that you are on
> your own if you define new data structures that can be viewed as
> sequences.

Right, like Set, which has a completely different fold to array and list. 
Equivalently, the implementations for vector, list and set iterators in C++ 
will be completely different. I don't think iterators buy you anything.

> The meaning of "fold" is "apply this function repeatedly for each
> element of the data-structure and accumulate the result". I'd like to
> be able to write this in code _once_ for every data-structure that can
> be seen as a sequence (i.e. a set of totaly ordered elements).

Why not write fold once "for every data structure..." seeing as they have next 
to nothing in common?

> You can 
> do this with iterators. As the article cited by Vasili shows there is
> an analogue of iterators in functional languages.

Presumably the benefit of iterators in a functional language would be 
bidirectional traversal of a sequence container. But iterators fall apart on 
general trees, matrices and anything which isn't just a sequence of elements. 
In many such cases you want mapi...

> So we are not really talking here about
> differences between OCaml and C++; we are talking about library
> design.

I think we are, because I think iterators are only really useful in an 
imperative setting. Hence C++ programmers use them extensively but OCaml 
programmers do not. Folds are simply not feasible in C++. I'm sure Stepanov 
would have reinvented them if they had been... ;-)

On Monday 27 September 2004 13:14, skaller wrote:
> Except you have to write:
>  let List.mapmap g f x = List.map g (List.map f x)
>  let Array.mapmap g f x = Array.map g (Array.map f x)

No, you don't have to write that. You can write a generic function which 
accepts a map as an argument:

let map_2 map f g c = map f (map g c)

or better still, the deforested:

let map_2 map f g c = map (fun x -> f (g x)) c

You can't write map_n without some jiggery pokery though.

> ...
> A generalised fold doesn't require either a sequence or any
> ordering

Folds with a particular direction are much more useful, IMHO. Hence the folds 
in the core library are left or right for arrays and lists and up for sets 
and maps.

> -- it just applies to all the elements of a container 
> in any order (so it works for a tree too).

A lexicographically ordered traversal can be defined for any data structure in 
OCaml - that's how hash and compare work.

Cheers,
Jon.

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Radu Grigore]

On Mon, 27 Sep 2004 14:11:30 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> > For the writter of the function there is a big difference, especially
> > if it has to write the specialized versions.
> 
> The equivalent to the writer of fold is the writer of an iterator. You have to
> write specialized versions for each type of iterator just as you would have
> to write your own fold.

That's why I said iterators are another level of abstraction. The
difference is that after you write the iterators code for a new
sequence-like data structure all the "generic" functions, not only
fold but also map and others, will automagically work on them. The
simplest form of an "iterator" is implementing  a "next" function for
all sequences (although in this situation it is more of an
"enumeration").

You should really check out the article cited by Vasili. It seems that
we understend different things by "functional equivalent of an
iterator", since you talk about the advantage of being able of going
backwards a.s.o. which really is an irrelevant advantage.

regards,
 radu

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Jon Harrop]

On Monday 27 September 2004 14:31, Radu Grigore wrote:
> The
> difference is that after you write the iterators code for a new
> sequence-like data structure all the "generic" functions, not only
> fold but also map and others, will automagically work on them.

I think this is the core of what we disagree on. I believe you'll be 
implementing a new data structure (e.g. splay trees) because you want to use 
different algorithms under the hood so that you get different asymptotic 
complexities for different operations. Therefore, the "automagically" 
generated ones will be useless because they'll have terrible performance - 
they'll need replacing.

The different functions (e.g. insert, find for a splay tree) require 
completely different algorithms so iterators are useless. For example, "find" 
on a "set" in the STL does not use iterators. Equivalently, the HOF fold is 
useless, e.g. "find" in "Set" in OCaml does not use fold:

let rec fold f s accu = match s with
  Empty -> accu
| Node(l, v, r, _) -> fold f l (f v (fold f r accu))

The similar functions (e.g. accumulate for a splay tree) do have commonality 
which can be factored out. This commonality is factored out as functions 
templated over iterators in the STL. In OCaml, this can be factored out by 
writing these functions in terms of fold:

let sum fold c = fold ( +. ) 0. c
let list_sum = sum List.fold_left

The automagic effect will only be worthwhile if you are implementing a lot of 
data structures (which is very unlikely) in which case you can use a tuple of 
functions:

let common fold =
  (fun fold c -> fold ( +. ) 0. c),
  ...
let list_sum, list_... = common List.fold_left

> You should really check out the article cited by Vasili. It seems that
> we understend different things by "functional equivalent of an
> iterator",

I read it yesterday and, indeed, we did not mean the same thing by that term. 
I was referring to how I would go about rewriting a C++/iterators program in 
OCaml. I wouldn't begin by implementing iterators. I think you were referring 
to how iterators could be implemented in a functional language. Is that 
right?

Cheers,
Jon.

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Radu Grigore]

On Mon, 27 Sep 2004 17:54:35 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> On Monday 27 September 2004 14:31, Radu Grigore wrote:
> > The
> > difference is that after you write the iterators code for a new
> > sequence-like data structure all the "generic" functions, not only
> > fold but also map and others, will automagically work on them.
> 
> I think this is the core of what we disagree on. 

Indeed. I think this is the problem.
Efficiency is indeed a constraint that limits the usefuleness of
iterators and the "find" function is a good example of this. When
using STL you have to remember that for certain data structures (e.g.
set) you have to use member functions if you want better performance
that is available only on that data structure.

But I do not think that it is such a severe limitation. For iter, map,
and fold efficiency is not a problem. At least no counter-example
comes to mind. Even more, the same implementation of fold can be O(n)
for a list and O(n log n) for a tree. This is because the fold itself
is O(n), while particular iterators are either O(1) or O(log n).

regards,
 radu

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Radu Grigore]

On Mon, 27 Sep 2004 14:11:30 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> > For the writter of the function there is a big difference, especially
> > if it has to write the specialized versions.
> 
> The equivalent to the writer of fold is the writer of an iterator. You have to
> write specialized versions for each type of iterator just as you would have
> to write your own fold.

That's why I said iterators are another level of abstraction. The
difference is that after you write the iterators code for a new
sequence-like data structure all the "generic" functions, not only
fold but also map and others, will automagically work on them. The
simplest form of an "iterator" is implementing  a "next" function for
all sequences (although in this situation it is more of an
"enumeration").

regards,
 radu

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Brian Hurt]

On Mon, 27 Sep 2004, Jon Harrop wrote:

> I think we are, because I think iterators are only really useful in an 
> imperative setting. Hence C++ programmers use them extensively but OCaml 
> programmers do not. Folds are simply not feasible in C++. I'm sure Stepanov 
> would have reinvented them if they had been... ;-)

Two comments:

First, iterators are usefull in a functional setting, for two reasons.  
The first is they allow lazy application of transformations.  It's easy to 
define a map on an interator to do the transforms as the values get pulled 
out.  And second, they provide a generic way to plug data structures 
together.  All you need to write is a to_iterator and from_iterator for 
each data structure, and then all data structures can talk to each other.

Second, you can do fold, map, iter, etc. in C++- it's just a pain.  To 
emulate HOFs you define a new class with single virtual member function.  
The virtual member function then becomes your HOF.  Of course, 1 line of 
Ocaml code has just become a dozen lines of C++, but that doesn't mean it 
can't be done...

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Tue, 2004-09-28 at 00:04, Brian Hurt wrote:
> On Mon, 27 Sep 2004, Jon Harrop wrote:

> Second, you can do fold, map, iter, etc. in C++- it's just a pain.  To 
> emulate HOFs you define a new class with single virtual member function.  
> The virtual member function then becomes your HOF. 

For templates all you need is a class with an operator()() method.

Dynamic dispatch is only needed if you need
run time function variables (first class functions).

Heh .. it isn't a pain doing this in C++, its
quite easy -- just use Felix. 

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Brian Hurt]

On 28 Sep 2004, skaller wrote:

> On Tue, 2004-09-28 at 00:04, Brian Hurt wrote:
> > On Mon, 27 Sep 2004, Jon Harrop wrote:
> 
> > Second, you can do fold, map, iter, etc. in C++- it's just a pain.  To 
> > emulate HOFs you define a new class with single virtual member function.  
> > The virtual member function then becomes your HOF. 
> 
> For templates all you need is a class with an operator()() method.
> 
> Dynamic dispatch is only needed if you need
> run time function variables (first class functions).

All this means is that the calling code, instead of calling foo->doit(), 
now instead calls (*foo)().  Not that big of a difference in coding 
volume.

And you still need dynamic dispatch because you're passing the superclass
type in.  Unless you're talking about templating the map/fold functions so
that you get a different instantiation for each call?

> 
> Heh .. it isn't a pain doing this in C++, its
> quite easy -- just use Felix. 
> 

:-)  I rest my case.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Tue, 2004-09-28 at 01:30, Brian Hurt wrote:
> On 28 Sep 2004, skaller wrote:

> > For templates all you need is a class with an operator()() method.
> > 
> > Dynamic dispatch is only needed if you need
> > run time function variables (first class functions).
> 
> All this means is that the calling code, instead of calling foo->doit(), 
> now instead calls (*foo)().  Not that big of a difference in coding 
> volume.

The call is done by foo() which works for C functions, 
pointers to them, and function objects. This is required for 
STL to be generic.

> And you still need dynamic dispatch because you're passing the superclass
> type in.  

Type information is not required, the C++ compiler checks
the calls argument and return types after instantiation.

> Unless you're talking about templating the map/fold functions so
> that you get a different instantiation for each call?

Yes, because it costs nothing, which is much cheaper
than the virtual dispatch:

template<class F, class T> 
T apply(F f, T a) { return f(a); }

struct Sin { 
  float operator()(float a) const { return a; }
};

float (*pf)(float)= sin;

apply(sin,1.0);
apply(Sin(),1.0);
apply(pf,1.0);

No dynamic dispatch is required here. The templates
works with C functions, pointers to C functions,
and function objects.

The first two calls should both resolve to 
just sin(1.0) (the call through the C pointer
requires an extra memory access .. :)

If you use a base and dynamic dispatch you'd incur
an overhead. Note the call is applied to a function
constant argument (the sine function).

Felix only uses dynamic dispatch when the function
is stored in a variable (or when it is too stupid
to optimise the call away by substitution).

BTW: note in the template, F is NOT the type
of the function -- it is the *class*
of the function. The actual function has type

	T -> T

The class of the function is irrelevant.

The class can even be float (*)(float),
it is still irrelavant -- what matters
is the type of f(a). For the function
object, that's a completely distinct
method with its own type -- unrelated
to the type of F: F is used solely
to lookup operator()() -- oh yeah,
that's ad hoc polymorphism.. :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Brian Hurt]

On 28 Sep 2004, skaller wrote:

> Yes, because it costs nothing, which is much cheaper
> than the virtual dispatch:

This is wrong.  It does cost something- it costs code bloat, because now
instead of a single copy of the comprehension, you have a whole bunch of
copies, one for each time you call the comprehension.  This increases
cache pressure, and increases the cache miss rate by the whole program,
slowing the program down.

Note that a cache miss that goes to main memory is 100-350+ clock cycles 
on modern CPUs.  I can do a heck of a lot of work in that time.

Note that inlining has the same problem.

> No dynamic dispatch is required here. The templates
> works with C functions, pointers to C functions,
> and function objects.

This is the advantage of templates, but it comes at a cost.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Tue, 2004-09-28 at 03:01, Brian Hurt wrote:
> On 28 Sep 2004, skaller wrote:
> 
> > Yes, because it costs nothing, which is much cheaper
> > than the virtual dispatch:
> 
> This is wrong.  It does cost something- it costs code bloat, because now
> instead of a single copy of the comprehension, you have a whole bunch of
> copies, one for each time you call the comprehension. 

I can't demonstrate easily for g++,
but can do so easily for Felix, which uses the same
mechanism. First the input:

--------------------------
include "std";
fun apply[T] (f:T->T,a:T):T => f a;
val x = apply(sin of (double),1.0);
print x; endl;
-------------------------

and here is the code generated by 'flx --inline'

      //x := (Double::sin 1.0);
      ptf->_i1549_v1533_x = (sin((1.0)));
      // primcall Double::print x;
      {std::cout<<(ptf->_i1549_v1533_x);}
      // primcall Stdout::endl ();
      {std::cout << endl;}

What you claim may be true in general: extensionl
polymorphism costs in terms of code bloat,
and sometimes that leads to a performance cost.
It will be fun to measure that when the Felix optimiser
is working well enough to compare it with ocaml.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[brogoff]

On Mon, 27 Sep 2004, Brian Hurt wrote:
> Two comments:
>
> First, iterators are usefull in a functional setting, for two reasons.
> The first is they allow lazy application of transformations.  It's easy to
> define a map on an interator to do the transforms as the values get pulled
> out.  And second, they provide a generic way to plug data structures
> together.  All you need to write is a to_iterator and from_iterator for
> each data structure, and then all data structures can talk to each other.
>
> Second, you can do fold, map, iter, etc. in C++- it's just a pain.  To
> emulate HOFs you define a new class with single virtual member function.
> The virtual member function then becomes your HOF.  Of course, 1 line of
> Ocaml code has just become a dozen lines of C++, but that doesn't mean it
> can't be done...

I've thought for a while that a hybrid of C++, Ada, and Pascal, with the awful
C++ syntax fixed, pointers restricted, and especially downward funargs, would
be an amusing imperative language, and it would address tha second problem you
mention, without requiring GC. But functional languages are more amusing :-).

I don't think that iterator based libraries is the right thing in an
OCaml (or SML or Haskell) setting.

-- Brian

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Tue, 2004-09-28 at 02:41, brogoff wrote:

> I've thought for a while that a hybrid of C++, Ada, and Pascal, with the awful
> C++ syntax fixed, pointers restricted, and especially downward funargs, would
> be an amusing imperative language, and it would address tha second problem you
> mention, without requiring GC. But functional languages are more amusing :-).

Thats Felix (http://felix.sf.net)

> I don't think that iterator based libraries is the right thing in an
> OCaml (or SML or Haskell) setting.

That may be so, but functorial polymorphism is necessary
for better reusability.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[Florian Hars]

Jon Harrop wrote:
> On Monday 27 September 2004 13:14, skaller wrote:
>>Except you have to write:
>> let List.mapmap g f x = List.map g (List.map f x)
> 
> No, you don't have to write that. You can write a generic function which 
> accepts a map as an argument:
> 
> let map_2 map f g c = map f (map g c)

I made the same error at first, but this is a completely different function:

# let list_map2  g f x = List.map g (List.map f x);;
val list_map2 : ('a -> 'b) -> ('c -> 'a) -> 'c list -> 'b list = <fun>

# let map2 m g f x = m g (m f x);;
val map2 : ('a -> 'b -> 'b) -> 'a -> 'a -> 'b -> 'b = <fun>

# list_map2 (fun x -> 2.0 *. x) (float_of_int) [ 1; 2; 3];;
- : float list = [2.; 4.; 6.]
# map2 List.map (fun x -> 2.0 *. x) (float_of_int) [ 1; 2; 3];;
This expression has type int -> float but is here used with type
   float -> float

The deforested version works (and is the only version that does in fact work 
for any map), but last time I looked, deforestation was considered a task for 
the compiler.

Yours, Florian.

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

Re: [Caml-list] Factoring HOFs [was Re: C++ STL...]

[Jon Harrop]

On Wednesday 29 September 2004 16:32, Florian Hars wrote:
> I made the same error at first, but this is a completely different
> function:

Yipes! Ok, so I'm missing some typing subtlety. Why does this end up with a 
single polymorphic type:

# let map_2 m g f x = m g (m f x);;
val map_2 : ('a -> 'b -> 'b) -> 'a -> 'a -> 'b -> 'b = <fun>
# let mapmap2 g f x = map_2 List.map g f x;;
val mapmap2 : ('a -> 'a) -> ('a -> 'a) -> 'a list -> 'a list = <fun>

Rather than being equivalent to:

# let mapmap g f x = List.map g (List.map f x);;
val mapmap : ('a -> 'b) -> ('c -> 'a) -> 'c list -> 'b list = <fun>

It looks like the "m" argument to map_2 is assumed to have the same type when 
applied to "f x" as when applied to "g (f x)". Sounds like this might be 
related to polymorphic recursion...

Cheers,
Jon.

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

Re: [Caml-list] Factoring HOFs [was Re: C++ STL...]

[Radu Grigore]

On Wed, 29 Sep 2004 17:49:17 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> Why does this end up with a single polymorphic type:

Slightly related.
I've found in the manual an example were a method is annotated with a type like:

  'a. 'a -> int

meaning "forall 'a the type is 'a -> int". Is there something similar
for normal functions? I guess that such an annotation for the map
parameter would solve Jon's problem.

regards,
 radu

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

Re: [Caml-list] Factoring HOFs [was Re: C++ STL...]

[Keith Wansbrough]

> Yipes! Ok, so I'm missing some typing subtlety. Why does this end up with a 
> single polymorphic type:
> 
> # let map_2 m g f x = m g (m f x);;
> val map_2 : ('a -> 'b -> 'b) -> 'a -> 'a -> 'b -> 'b = <fun>

You want it to have type

(forall 'a 'b 'f. ('a -> 'b) -> ('a 'f -> 'b 'f))
   -> ('b -> 'c) 
   -> ('a -> 'b) 
   -> 'a 'f 
   -> 'b 'f

but OCaml doesn't allow nested quantifiers (i.e., higher-rank
polymorphism).

It actually wouldn't be very hard to support, if you're prepared to
accept the need for the occasional type annotation - see
http://research.microsoft.com/~simonpj/papers/putting/index.htm.

--KW 8-)

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

Re: [Caml-list] Factoring HOFs [was Re: C++ STL...]

[Keith Wansbrough]

> You want it to have type

Oops, I meant:

(forall 'a 'b. ('a -> 'b) -> ('a 'f -> 'b 'f))
   -> ('b -> 'c) 
   -> ('a -> 'b) 
   -> 'a 'f 
   -> 'b 'f

but the point stands.

--KW 8-)
-- 
Keith Wansbrough <kw217@cl.cam.ac.uk>
http://www.cl.cam.ac.uk/users/kw217/
University of Cambridge Computer Laboratory.

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

Re: [Caml-list] Factoring HOFs [was Re: C++ STL...]

[skaller]

On Thu, 2004-09-30 at 20:13, Keith Wansbrough wrote:

> but OCaml doesn't allow nested quantifiers (i.e., higher-rank
> polymorphism).
> 
> It actually wouldn't be very hard to support, if you're prepared to
> accept the need for the occasional type annotation

I doubt there is a problem with that. I use polymorphic 
variants and occasionally you need not just annotations,
but to actually write full coercions. This is a small
price to pay.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] Factoring HOFs

[Jacques Garrigue]

From: Keith Wansbrough <Keith.Wansbrough@cl.cam.ac.uk>

> > Yipes! Ok, so I'm missing some typing subtlety. Why does this end up with a 
> > single polymorphic type:
> > 
> > # let map_2 m g f x = m g (m f x);;
> > val map_2 : ('a -> 'b -> 'b) -> 'a -> 'a -> 'b -> 'b = <fun>
> 
> You want it to have type
> 
> (forall 'a 'b 'f. ('a -> 'b) -> ('a 'f -> 'b 'f))
>    -> ('b -> 'c) 
>    -> ('a -> 'b) 
>    -> 'a 'f 
>    -> 'b 'f
> 
> but OCaml doesn't allow nested quantifiers (i.e., higher-rank
> polymorphism).
> 
> It actually wouldn't be very hard to support, if you're prepared to
> accept the need for the occasional type annotation - see
> http://research.microsoft.com/~simonpj/papers/putting/index.htm.

OCaml has been supporting nested quantifiers for years.
However, they are a little more verbose because we chose to allow
unpredicate 2nd order types, which are harder to infer.

Look in the manual for polymorphic record fields and polymorphic
methods. The former are lighter syntactically, but require an
explicit record definition in advance, while the latter allow defining
polymorphic values on the fly.

But your example also uses constructor variables, which are not
available in ocaml. Note however that you can still encode it using
a functor:

module Map2(M : sig type 'a f val map : ('a -> 'b) -> 'a f -> 'b f end) =
  struct
    let map2 g f x = M.map g (M.map f x)
  end

Not much longer, he?
You can apply this functor locally with "let module".

let to_string l =
  let module M = Map2(struct type 'a f = 'a list let map = List.map end) in
  M.map2 string_of_int (fun x -> x + 1) l

Jacques

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

Re: [Caml-list] Factoring HOFs

[Keith Wansbrough]

> OCaml has been supporting nested quantifiers for years.
> However, they are a little more verbose because we chose to allow
> unpredicate 2nd order types, which are harder to infer.

Apologies; I didn't realise this.  Thanks for the pointer.

--KW 8-)

-- 
Keith Wansbrough <kw217@cl.cam.ac.uk>
http://www.cl.cam.ac.uk/users/kw217/
University of Cambridge Computer Laboratory.

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

Re: [Caml-list] Factoring HOFs

[brogoff]

On Fri, 1 Oct 2004, Jacques Garrigue wrote:
> From: Keith Wansbrough <Keith.Wansbrough@cl.cam.ac.uk>
> >
> > but OCaml doesn't allow nested quantifiers (i.e., higher-rank
> > polymorphism).
> >
> > It actually wouldn't be very hard to support, if you're prepared to
> > accept the need for the occasional type annotation - see
> > http://research.microsoft.com/~simonpj/papers/putting/index.htm.
>
> OCaml has been supporting nested quantifiers for years.
> However, they are a little more verbose because we chose to allow
> unpredicate 2nd order types, which are harder to infer.
>
> Look in the manual for polymorphic record fields and polymorphic
> methods. The former are lighter syntactically, but require an
> explicit record definition in advance, while the latter allow defining
> polymorphic values on the fly.

These are good additions to the language which allow you to do lots of things,
like encode Okasaki's algorithms more directly, but they don't seem like a
satisfactory solution. It would be better to just have the user give a type
annotation on functions I think. Also for recursive types, it seems like it
would better to allow them in the language with explicit annotations rather than
having a compiler switch or having to wrap in constructors.

> But your example also uses constructor variables, which are not
> available in ocaml. Note however that you can still encode it using
> a functor:

Nice.  Xavier Leroy used a similar encoding a while back to simulate
higher order type constructors. This trick seems FAQworthy.

It's funny, because I read some paper by Haskell guys talking about how
the ML module system is powerful but overcomplex (hope I'm not misstating the
intent of the paper!) yet it seems more intuitive than type classes to me.

-- Brian

> module Map2(M : sig type 'a f val map : ('a -> 'b) -> 'a f -> 'b f end) =
>   struct
>     let map2 g f x = M.map g (M.map f x)
>   end
>
> Not much longer, he?
> You can apply this functor locally with "let module".
>
> let to_string l =
>   let module M = Map2(struct type 'a f = 'a list let map = List.map end) in
>   M.map2 string_of_int (fun x -> x + 1) l
>
> Jacques
>
> -------------------
> 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
>

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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Mon, 2004-09-27 at 04:51, Jon Harrop wrote:

> I think you're thinking of a function to convert between 'a and 'b container 
> types. 

The requirement is for a polyadic map. 
Here is the type signature:

map: ('a -> 'b) -> 'a 'F -> 'b 'F

Here, 'F is a variable for 'list' or 'array'.
You cannot do that in Ocaml. 

Of course for given 'F, made of sums, products
and induction, you can write the
code for map_F, eg map_list, map_array, map_tree,
and you can do it 'mechanically'. But Ocaml can't.

Note: the output must have exactly the same shape
as the input: map preserves shape, it only changes
the values stored in the 'slots' of the data structure.
So a weird tree or graph has to come out isomorphic
to its input.

> You mean there is a trade-off of functionality between more- and less-capable 
> type systems?

No, I mean that trivial but useful cases of Object Orientation
exist but in general it doesn't work.

Similarly, trivial cases of polyadic programming
can be done with the trick of using iterators
or some other sequential representation such as Enums,
but it isn't a general solution -- it only 
works for sequences.

> > Accumulate can accept a function object argument.
> > C++ DOES have higher order functions.
> 
> That statement is so HOF-definition dependent that it boils down to "C++ is 
> Turing complete".

I agree :)

> > [Did I miss something .. ? :]
> 
> Good looking programmers.

LOL!

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features

[skaller]

On Sun, 2004-09-26 at 15:31, Radu Grigore wrote:
> On Sun, 26 Sep 2004 02:34:50 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> > For example, to sum the floating-point elements of a container in C++, one
> > might write:
> 
> This example is slightly unfair to C++. In the OCaml code:
> 
> > let sum fold_left c = fold_left ( +. ) 0. c
> > sum List.fold_left [0.; 1.; 2.; 3.; 4.]
> > sum Array.fold_left [|0.; 1.; 2.; 3.; 4.|]
> 
> ...you use _two_ library functions (namely List.fold_left and
> Array.fold_left). Surely you should at least use one for C++ :)

C++ STL + templates offer a messy and unreliable form
of polyadic programming not available in Ocaml.

C++ cheats quite a bit. 

So does Extlib. Basically, if you provide some
function such as 'get_next()' you can convert
some data structure to a fixed stream type, and then 
you can fold it with one algorithm. However, of course this 
isn't enough to provide map (since the original 
data structure is lost).

C++ has the same problem -- you can certainly
build a data structure of mapped values with
both systems, but that isn't a map:

	map: 'a F * ('a -> 'b) -> 'b F

is a map, where F is some type functor such as list,
bintree, array, etc. IE map should preserve the shape.

FISh can do that -- a single definition of 'map'
implements he above formula for all data types F.

I guess:

value variables .. type variables .. functor variables

Languages like Java are stuck in stage 1 and should
no longer be entitled to be considered 'high level
programming languages'. C++ and Ocaml are 
stuck in stage 2. For more reusability we must
proceed to stage 3.

In some way dynamic typing allows polyadic programming,
but I guess we'd like to get it without losing the
benefits of static typing.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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