Re: [Caml-list] Polymorphic Variants

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

On Thu, 2007-01-18 at 15:20 +0900, Jacques Garrigue wrote:
> From: skaller <skaller@users.sourceforge.net>

> > On the other hand some code would just be impossible
> > without overloading. For example C has
> > 
> > 	char, short, int, long, long long
> > 	unsigned versions
> > 	float, double, long double
> > 
> > which is 13 distinct 'number' types, and I would hate
> > to have to write:
> > 
> > 	1 int_add 2
> > 	1L long_add 2L
> 
> Actually this is not only overloading that is used here, but also
> automatic conversions.

In C/C++ yes, both overloading and automatic conversions.
In Felix there are no automatic conversions.

However Felix still allows you to write

	1 + 1L

if you open the module 'MixedInt'. That module provides
a constrained polymorphic function:

  fun add[t1:fast_ints, t2:fast_ints]: 
    t1 * t2 -> arithmax(t1,t2)
    ="$1+$2"
  ;

where 'fast_ints' is a typeset, which is a finite set
of concrete types, and 

	t: typeset

in this context means

	t where t isin typeset

(which is also legal Felix).

This is, in effect, the complete set of all the 100 overloads 
on the 10 C integer type pairs, represented as polymorphism 
with a constraint checked at the point of call. 

Note the implementation here is "$1+$2" which leverages
C++ overloading.

Typesets and constrained polymorphism are just a convenient
sugar for writing huge numbers of overloads out.

It is interesting that to model the C/C++ type system
here I had to do some quite advanced type system hackery,
but the result is mixed mode arithmetic without any
automatic conversions.

It is also possible to defer choice of types to the instantiation
phase, which can now be done in a well principled manner using
Felix typeclasses. In particular you can now, finally, after
6 years work, do a 'fold' on an STL container using typeclasses
without needing any 'dependent name lookup'.

this is not first class polyadic programming, since (unlike Haskell?)
only types can be typeclass parameters, not functors 
(type constructors, eg STL vector, list, set etc can't be arguments).

However the result is easier to use than Ocaml I think: 
typeclasses are weaker than Ocaml functors but they're much
easier to use, since they work with 'ordinary' code. 

In Ocaml to write 'generic' code you have to put your code 
inside a functor definition. Perhaps that is easy if you have,
for example, one container type, but typical programs will
use several container types, which would require several
levels of nested functors in Ocaml.

I think this would mean that the Ocaml code would be fragile
in the sense that you'd have to do a lot of housekeeping
if the implementation changed to use a slighly different
set of containers -- you'd have to rewrite all the
nested functor wrappers.

I wonder if there is a better way? I really don't like
typeclasses that much: they only allow a single instantiation.
For example

	1 < 2

is an instance of a total ordering typeclass for integers,
but integers can also be sorted in the other direction.
You can't have both orderings, instead you need a dummy
type

	type revint  = RevInt of int 

which supports the reverse ordering. Whereas with Ocaml/ML
functors the comparison function is a specific argument.
I think this is correct.

Hmm .. am I right in thinking Ocaml's local modules also allow
local functor instantiations? This must help quite a bit?

Having to explicitly instantiate is quite a pain though,
compared to C++ templates, typeclasses in either Haskell
or Felix, or plain old Ocaml polymorphic functions:
people keep asking for a polymorphic version of the 
Ocaml Set .. and I'm sure I use Hashtbl polymorphic version
to avoid having to instantiate Map all over the place ***

*** This is not so trivial due to lack of inter module
recursion across ml file boundaries

I wonder if Ocaml couldn't support automatic functor instantiation
by providing an "canonical" instance. For example:

module IntSet = Set.Make (Int)
module FloatSet = Set.Make (Float)

let s1 = IntSet.add s1 1            (* uses manual instantiation *)
let s2 = Set.Make(Int).add s 1      (* uses canonical instantiation *)

The canonical instantiation is 'generated' by the compiler.
It would have to be shared across ml files.

This would be similar to having nominally typed records BUT
also having a canonical structurally typed instance,
namely tuples.


>  When writing numeric computations in ocaml, I
> find it just as painful to have to add float_of_int, as to add the dot
> after all operators. (In number of characters, float_of_int might be
> the biggest...)

Nah, Felix uses BigInt internally for integers in case constants
fit in C integer types but not Ocaml ones .. BigInt.int_of_bigint
is bigger .. :)

> For overloading alone, the module system could help.
> If we had the operators defined with different types in each of the
> numeric type modules, then one could just choose the numeric type used
> with "open Mynumtype".

Yes. Interestingly in Felix you can open both modules
and typeclasses, AND you can partially specialise type
parameters if they're polymorphic, AND these things
can be overloaded .. all at once!

This can be a bit confusing .. especially since the typeclass
feature is new and undoubtedly contains bugs.

>  This is one of the reasons I pushed for having
> a local "let open" construct... which can be simulated by "let
> module", at a slight cost.

Right. You want to localise the impact. Using 'open'
is only "poor man's genericity" but a localised version
would be better than nothing.

Interestingly Felix supports that, and it is precisely
how typeclasses passed to functions are implemented:

	fun f[t with Eq[t]] (a:t, b:t, c:t) =>
		a < b and b < c
	;

	// same as "f: Eq t => t :: t * t -> t" in Haskell?

is actually implemented by

		open Eq[t];
		return a < b and b < c;

So in Ocaml if you could also "pass" in the module to be
opened it would be really cool! This should not require
properly first class modules: Felix does it without
them so Ocaml could too :)

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