Re: [Caml-list] generic functions

[skaller <skaller@users.sourceforge.net>]

On Mon, 2005-01-10 at 02:48, Brian Hurt wrote:

> > let foo (x : int) = x*x;;
> > let foo (x : float) = x*.x;;

> The short answer is no.  For two reasons- first, Ocaml doesn't keep type 
> information (in most cases) of data at run time, the type information is 
> used during compilation and then tossed.  Which means that Ocaml doesn't 
> have a way at run time to tell which version of the function to call.  And 
> second, and more importantly, overloading (like you're doing above) would 
> make type inference extremely difficult if not impossible.

Felix is an ML like language which does provide overloading.
It does overload resolution at compile time. As Brian mentions
this makes full type inference hard, however this isn't nearly so
much of a problem as you might think

You have to annotate function argument types, however function
return types and variable types are still deduced. For this extra
effort you get three positive benefits:

(a) better documented code
(b) better diagnostic messages on type errors
(c) overloading

In addition, some of the newer Ocaml features like polymorphic
variants require type annotations or coercions to be used
at times anyhow, and such annotation is common for functions
in separately compiled files, which often have interface
specifications (which require type annotations).

The two principal advantages of inference would appear to be:

(a) for quick and dirty code and small functions where
the extra clutter would reduce clarity and increase coding time.

(b) for complex functions with nasty types

The brevity argument is context dependent. I have just written in
Felix a function which converts a complex parse tree into
a string. This function has to decode around 100 variants
from 40 or so types to produce the result.

In Felix all these functions are called 'str', and I can just
write code like

fun str : product_list_t -> string =
  | product_list_1 (?s,?sl) => str s + " * " + str sl
  | product_list_2 ?s => str s
;


fun str : term_t -> string =
  | term_1 (?t,?p) => str t + " / " + str p
  | term_2 (?t,?p) => str t + " % " + str p
  | term_3 ?pr => str pr
;

..

Without overloading I would have to invent a discrete name for
each function, which would certainly reflect the argument type,
so this is balances out in favour of overloading. In the actual
use of the function there is no doubt that overloading is
briefer than inference without it, since I can use
the 'str' name without knowing which function is applied.

In Ocaml, this program would be almost untenable.
I would try to avoid this problem by using polymorphic variants
instead of ordinary ones (and then write one big 'str' function
for all the variants).

Bottom line: I have used two similar languages, one with
type inference and one with overloading, and in general
I could pick between them like this:

Overloading (in the Felix and C++ style) only works on direct 
calls where the function is named. It doesn't work with 
closures, for example variables containing function values,
including parameters. So I would say inference is better
when you're doing lots of higher order work, and overloading
is better for more mundane industrial applications.

BTW: it would be interesting to provide a better integration
of both features. G'Caml is one idea. Polymorphic variants
are another. In Felix you can write:

	fun swap(x,y) => y,x;

without type annotations: type variables are assumed but
they're independent. This precludes code like

	fun apply(f,x)=> f x;

but it is clear some localised inference in this case would
allow this. 

It is also known that overloading CAN work with
inference with some contraints -- there is a paper somewhere
on Citeseer on this topic (sorry don't have the URL at the
moment, if someone finds it please let me know..)


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