[Caml-list] Understanding why Ocaml doesn't support operator overloading.

[Caml-list] Understanding why Ocaml doesn't support operator overloading.

[Jørgen Hermanrud Fjeld]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi.
Some time ago, when looking at Ocaml for the first time, I got baffled by the 
lack of operator overloading. I am still wondering why this is the case. 
Could someone please point me to more information about this?

I remember reading something about operator overloading and type inference 
beeing hard to combine. A little googleing brought me, amongst many things, 
what seems to be a paper about the subject:
"http://doi.acm.org/10.1145/581478.581495"
(No I haven't read the paper yet, but it seemed ontopic)


- -- 
Sincerely | Homepage:
Jørgen    | http://www.hex.no/jhf
          | Public GPG key:
          | http://www.hex.no/jhf/key.txt

Proper treatment will cure a cold in seven days, but left to itself,
a cold will hang on for a week.
		-- Darrell Huff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE95oR09jvTqPy5VsoRAk1jAJ9OAhTHIh1d59adbN4sNaIn8l2yygCfQG1u
3+Ki06a/O7DUp0wf3v8o5gU=
=9IUF
-----END PGP SIGNATURE-----

-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Jørgen Hermanrud Fjeld]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi again.
Now I found a previous thread about this
"http://caml.inria.fr/archives/200104/threads.html#00028"
I still don't understand why overloading isn't doable, (not only operator 
overloading)
And I wondered if any projects work on this?

On torsdag 28 november 2002, 22:02, Jørgen Hermanrud Fjeld wrote:
> Hi.
> Some time ago, when looking at Ocaml for the first time, I got baffled by
> the lack of operator overloading. I am still wondering why this is the
> case. Could someone please point me to more information about this?
>
> I remember reading something about operator overloading and type inference
> beeing hard to combine. A little googleing brought me, amongst many things,
> what seems to be a paper about the subject:
> "http://doi.acm.org/10.1145/581478.581495"
> (No I haven't read the paper yet, but it seemed ontopic)

- -- 
Sincerely | Homepage:
Jørgen    | http://www.hex.no/jhf
          | Public GPG key:
          | http://www.hex.no/jhf/key.txt

There are three schools of magic.  One:  State a tautology, then ring the
changes on its corollaries; that's philosophy.  Two:  Record many facts.
Try to find a pattern.  Then make a wrong guess at the next fact; that's
science.  Three:  Be aware that you live in a malevolent Universe controlled
by Murphy's Law, sometimes offset by Brewster's Factor; that's engineering.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE95ooy9jvTqPy5VsoRAsRCAJ9K3uuH2nK55WTFn4cRoK4NwfhpSQCeJEca
woLJurkjCSQqYi3k751obfo=
=EKLa
-----END PGP SIGNATURE-----

-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Xavier Leroy]

> Some time ago, when looking at Ocaml for the first time, I got
> baffled by the lack of operator overloading. I am still wondering
> why this is the case.  Could someone please point me to more
> information about this?
> I remember reading something about operator overloading and type inference 
> beeing hard to combine.

I don't know how technical you'd like the answer to be, so let me
start with a simple explanation that doesn't get into all technical
details.

The problem is indeed the combination of overloading and type
inference.  The catch-22 is this:
- overloading determines the meaning of an operator from the types of
  its arguments (e.g. to determine whether + is integer addition or
  floating-point addition);
- type inference relies (among other things) on the fact that each
  operator has a unique type to determine the types of its arguments
  (e.g. if one of the arguments is a function parameter).

If you don't see the circularity, consider

        let f x = x + x

If "+" is overloaded on integers and on floats, you get two possible
types for f: int -> int or float -> float.  None of these types is
better than the other; if the compiler commits to one of them, say
int->int, later applications of f (e.g. to a float) can be rejected.

In technical terms, we say that the principal types property fails.
This property says that the inferred type is always the "best" in the
sense that it subsumes all other possible types.  Its a crucial
property in order to do type inference, both from a theoretical and a
practical (usability) standpoint.

There are many ways to go about the problem with "f" above.
A simple one is to reject the definition as ambiguous, and require the
programmer to disambiguate, e.g. by putting a type declaration on "x".
Another equally simple is to resolve ambiguities using a default
strategy, e.g. favor "int" over "float".  Both ways aren't very nice,
since they break the principal types property.

Many type inference systems have been proposed for overloading that
preserve the principal types property.  The most famous example (but
not the only one) is Haskell's type classes.  If you look at the
literature, you'll see that they all involve significant typing
machinery; some even have significant impact on the design of the
whole language (as in the case of Haskell).  I'm not criticizing here,
just pointing out that combining type inference and overloading is not
a trivial extension of ML-style type inference.

Hope this (partially) answers your question.

- Xavier Leroy
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Christophe Raffalli]

Another solution is at

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

A question: will this be available in future official release of OCaml ?

Christophe


-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Nicolas Cannasse]

> > Some time ago, when looking at Ocaml for the first time, I got
> > baffled by the lack of operator overloading. I am still wondering
> > why this is the case.  Could someone please point me to more
> > information about this?
> > I remember reading something about operator overloading and type
inference
> > beeing hard to combine.
>
> I don't know how technical you'd like the answer to be, so let me
> start with a simple explanation that doesn't get into all technical
> details.
>
> The problem is indeed the combination of overloading and type
> inference.  The catch-22 is this:
> - overloading determines the meaning of an operator from the types of
>   its arguments (e.g. to determine whether + is integer addition or
>   floating-point addition);
> - type inference relies (among other things) on the fact that each
>   operator has a unique type to determine the types of its arguments
>   (e.g. if one of the arguments is a function parameter).
>
> If you don't see the circularity, consider
>
>         let f x = x + x
>
> If "+" is overloaded on integers and on floats, you get two possible
> types for f: int -> int or float -> float.  None of these types is
> better than the other; if the compiler commits to one of them, say
> int->int, later applications of f (e.g. to a float) can be rejected.

I have already seen this sample in my early caml days and there is still
something I don't get.
Of course the ML type system relies on type inference and need do choose the
"best available" type but what if we enrich the type system with an "OR"
operator ? Then if (+) is overloaded on floats, you'll get :

f :  int -> int OR float -> float
or something like a type constraint :   f : 'a -> 'a where 'a in [int;float]

This approach seems trivial to me, but I really can understand that this
require a lot of addins in the typing algorithms & theory. BTW, does one of
the upper approach has already been discussed ? any paper on it ? any
countersample that will make me feel stupid ? :)

Regards,
Nicolas Cannasse

-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Michal Moskal]

On Fri, Nov 29, 2002 at 04:52:03PM -0000, Nicolas Cannasse wrote:
> Of course the ML type system relies on type inference and need do choose the
> "best available" type but what if we enrich the type system with an "OR"
> operator ? Then if (+) is overloaded on floats, you'll get :
> 
> f :  int -> int OR float -> float
> or something like a type constraint :   f : 'a -> 'a where 'a in [int;float]
> 
> This approach seems trivial to me, but I really can understand that this
> require a lot of addins in the typing algorithms & theory. BTW, does one of
> the upper approach has already been discussed ? any paper on it ? any
> countersample that will make me feel stupid ? :)

The problem is what *assembly code* should be generated for function f?
Code to add 2 integers or code to add 2 floats? Hmm.. we'll have a
problem then. Or maybe both? And choose versions of f based on type it
is applied to? But then consider:

let f x1 x2 ... xn = ((x1 + x1), (x2 + x2), ..., (xn + xn))

you need to generate 2^n versions of f. We're getting to ugly things
like C++ templates here.

There is third answer: generate code that checks if it's passed int or
float. But this has very significant perfomance impact.

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Mike Lin]

> The problem is what *assembly code* should be generated for function f?
> Code to add 2 integers or code to add 2 floats? Hmm.. we'll have a
> problem then. Or maybe both? And choose versions of f based on type it
> is applied to? But then consider:
>
> let f x1 x2 ... xn = ((x1 + x1), (x2 + x2), ..., (xn + xn))
>
> you need to generate 2^n versions of f. We're getting to ugly things
> like C++ templates here.

If this is really a problem then what gets generated when you write any 
polymorphic function at all? The proposal is to allow constrained 
polymorphism; the polymorphism that is already in OCaml seems to 
supersede this with regard to the above objection.

I wonder if the unification algorithm can be generalized to intersect 
sets of allowable types instead of unifying "for all" type variables. 
It doesn't seem too ludicrous in principle but I could easily have 
missed some nasty corner case.

-Mike

-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Michal Moskal]

On Fri, Nov 29, 2002 at 07:00:21PM -0500, Mike Lin wrote:
> >The problem is what *assembly code* should be generated for function f?
> >Code to add 2 integers or code to add 2 floats? Hmm.. we'll have a
> >problem then. Or maybe both? And choose versions of f based on type it
> >is applied to? But then consider:
> >
> >let f x1 x2 ... xn = ((x1 + x1), (x2 + x2), ..., (xn + xn))
> >
> >you need to generate 2^n versions of f. We're getting to ugly things
> >like C++ templates here.
> 
> If this is really a problem then what gets generated when you write any 
> polymorphic function at all? 

No. Compiler trates polymorphic types as abstract then. It need not know
what is the exact type, all it cares about is size of data, which in
case of OCaml on 32 bit machines is always 4 bytes. 

For example in:

let f g x = g x x

f ( + ) 1
f ( +. ) 1.0

There is no problem for the compiler. It can genarate code for f like:

void *f(void *(*g)(void *, void *), void *x)
{
	return g(x, x);
}

However for:

let f x = x + x

it needs to generate something like:

void *f(void *x)
{
	if (is_integer(x))
		return x + x;
	else
		return box(unbox(x) +. unbox(x));
	// unbox(x) == *(double*)x
	// box(x) allocates double on the heap and returns pointer to it
}

and this runtime check has significant perfomance impact. I guess
Haskell does it.

> The proposal is to allow constrained 
> polymorphism; the polymorphism that is already in OCaml seems to 
> supersede this with regard to the above objection.
> 
> I wonder if the unification algorithm can be generalized to intersect 
> sets of allowable types instead of unifying "for all" type variables. 
> It doesn't seem too ludicrous in principle but I could easily have 
> missed some nasty corner case.

Again: Haskell does it, so typing isn't real issue here.

I guess overloading could be resolved efficiently using some kind of
runtime code generation, in spirit of M$ ILX, but this is faaaaaar from
trivial.

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Mike Lin]

>
> No. Compiler trates polymorphic types as abstract then. It need not 
> know
> what is the exact type, all it cares about is size of data, which in
> case of OCaml on 32 bit machines is always 4 bytes.
>
> For example in:
> .......

Fair enough. I'm curious though: Say I'm the programmer and I would 
like to solve the problem of combining different types of numbers with 
a fairly uniform syntax. I'm either going to define a union type for 
numbers and have all my functions pattern-match, or else I'm going to 
write several versions of my functions to handle different types of 
numbers and call different ones as appropriate. I would wish that if 
all my functions were built up from the primitives +, -, *, /, etc. the 
compiler could do this for me. The compiler may have to generate many 
different versions if I use them all, but otherwise I would have to 
write them myself!

I don't think this whole thing is a good idea in general, but I don't 
buy this practicality/efficiency argument against it.

>
> Again: Haskell does it, so typing isn't real issue here.

Haskell also does not have mutable data, and I think it has been well 
established in the literature that mutable data complicates subtyping 
and intersection typing. So, as others are pointing out, I definitely 
think typing is a real issue here.

-Mike

-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[William Lovas]

On Fri, Nov 29, 2002 at 07:00:21PM -0500, Mike Lin wrote:
> If this is really a problem then what gets generated when you write any 
> polymorphic function at all?

I think the whole idea behind polymorphic functions is that they don't
*care* about the type that 'a is instantiated as -- generic code that works
for all instantiations can be generated.  This is only really useful for
parametrized types, like 'a list, which is why it's called parametric
polymorphism.  As an exercise, try to write a useful function that operates
on just 'a's -- you'll find it a challenge :)  (in fact, i think there's a
theorem in one of Philip Wadler's papers that says the *only* function of
type 'a -> 'a in a purely functional language is the identity function).

> The proposal is to allow constrained 
> polymorphism; the polymorphism that is already in OCaml seems to 
> supersede this with regard to the above objection.

Overloading is also known as ad-hoc polymorphism, which as i understand it
basically means "rule-based" -- you can't generate generic code, but you
can generate all possibilites and pick the right one based on some set of
rules.

Just because "constrained polymorphism" seems less powerful than fully
parametric polymorphism doesn't mean it's just as tractable.  The analogy
that immediately came to mind for me comes from theory of computation -- a
subset of a regular language is not necessarily regular, even though it's
smaller.

> I wonder if the unification algorithm can be generalized to intersect 
> sets of allowable types instead of unifying "for all" type variables. 
> It doesn't seem too ludicrous in principle but I could easily have 
> missed some nasty corner case.

The type inference algorithm simply assigns type variables to expressions,
generates a set of constraints based on how those expressions are put
together, and then `unifies' those constraints to make sure that they don't
lead to any contradictory equalities, like `int = float'.  Trying to
generalize this would mean changing the `=' relation to something more
interesting, like maybe subset containment or something.  Clearly, this
would not be a trivial undertaking..

There has been research into "intersection types", but i don't know if they
have anything to do with your proposal... maybe someone else can shed some
light?

cheers,
William
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Pierre Weis]

> On Fri, Nov 29, 2002 at 07:00:21PM -0500, Mike Lin wrote:
> > If this is really a problem then what gets generated when you write any 
> > polymorphic function at all?
> 
> I think the whole idea behind polymorphic functions is that they don't
> *care* about the type that 'a is instantiated as -- generic code that works
> for all instantiations can be generated.  This is only really useful for
> parametrized types, like 'a list, which is why it's called parametric
> polymorphism.

Although, you are right in that parametric polymorphism shines when
used with parameterized types, this far from being the only use of it.

>  As an exercise, try to write a useful function that operates
> on just 'a's -- you'll find it a challenge :)  (in fact, i think there's a
> theorem in one of Philip Wadler's papers that says the *only* function of
> type 'a -> 'a in a purely functional language is the identity function).

This is a theorem that was stated about $\lambda$-calculus long time
ago, way before Phil Wadler's papers, back to Reynolds as I remember.

The challenge you proposed is not so difficult in Caml. You can easily
define functions that operates on justs'a's, or even just return plain
'a's!

        Objective Caml version 3.06+18 (2002-11-07)

# raise;;
- : exn -> 'a = <fun>
# ignore;;
- : 'a -> unit = <fun>

Furthermore, this is even easier if you consider using true side effects
that we have in Caml.

> > The proposal is to allow constrained 
> > polymorphism; the polymorphism that is already in OCaml seems to 
> > supersede this with regard to the above objection.
> 
> Overloading is also known as ad-hoc polymorphism, which as i understand it
> basically means "rule-based" -- you can't generate generic code, but you
> can generate all possibilites and pick the right one based on some set of
> rules.

This is untrue. You can generate fully generic code for ad-hoc
polymorphic functions without bothering to generate ``all
possibilities''. See Jun Furuse's thesis
(http://pauillac.inria.fr/~furuse/thesis/).

> Just because "constrained polymorphism" seems less powerful than fully
> parametric polymorphism doesn't mean it's just as tractable.  The analogy
> that immediately came to mind for me comes from theory of computation -- a
> subset of a regular language is not necessarily regular, even though it's
> smaller.

This is not right as well. Extensional polymorphism is MORE powerful
than fully parametric polymorphism, in that it can express all
parametric polymorphism types and functions, plus types and functions
that you have not even dreamed of!

Once more, have a look to http://pauillac.inria.fr/~furuse/thesis/ or
POPL'95 initial article
(ftp://ftp.inria.fr/INRIA/Projects/cristal/Pierre.Weis/generics.dvi.Z)

> > I wonder if the unification algorithm can be generalized to intersect 
> > sets of allowable types instead of unifying "for all" type variables. 
> > It doesn't seem too ludicrous in principle but I could easily have 
> > missed some nasty corner case.
> 
> The type inference algorithm simply assigns type variables to expressions,
> generates a set of constraints based on how those expressions are put
> together, and then `unifies' those constraints to make sure that they don't
> lead to any contradictory equalities, like `int = float'.  Trying to
> generalize this would mean changing the `=' relation to something more
> interesting, like maybe subset containment or something.  Clearly, this
> would not be a trivial undertaking..

This is correct. That's why the extensional polymorphism theory is
based on the usual plain unification, for both efficiency and
conservativity with respect to the Caml langauge considerations.

> There has been research into "intersection types", but i don't know if they
> have anything to do with your proposal... maybe someone else can shed some
> light?
> 
> cheers,
> William
> -------------------
> 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
> 

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[William Lovas]

On Sun, Dec 01, 2002 at 06:30:55PM +0100, Pierre Weis wrote:
> >  As an exercise, try to write a useful function that operates
> > on just 'a's -- you'll find it a challenge :)  (in fact, i think there's a
> > theorem in one of Philip Wadler's papers that says the *only* function of
> > type 'a -> 'a in a purely functional language is the identity function).
> 
> This is a theorem that was stated about $\lambda$-calculus long time
> ago, way before Phil Wadler's papers, back to Reynolds as I remember.

That's probably true -- i just happened to remember it from a Wadler paper.

> The challenge you proposed is not so difficult in Caml. You can easily
> define functions that operates on justs'a's, or even just return plain
> 'a's!
> 
>         Objective Caml version 3.06+18 (2002-11-07)
> 
> # raise;;
> - : exn -> 'a = <fun>
> # ignore;;
> - : 'a -> unit = <fun>

Mmm, this certainly is a useful use of polymorphism without parametrized,
types, but the challenge i was trying to propose was more to the spirit of
the original 'a -> 'a theorem: by "useful function that operates on just
'a's", what i meant was essentially "a non-trivial function of type
'a -> 'a", which is (i hope) a significantly more difficult challenge :)

Polymorphism as used in `raise' and `ignore' strikes me as more language
magic than anything else -- although useful in practice, i have a strong
intuition that from a certain theoretical perspective, namely that of
purely functional languages, they're not so interesting.  So, to clarify,
while they are practical uses of polymorphism, they're not what i had in
mind when i wrote the above paragraph.

Thanks for the corrections and pointers!

cheers,
William
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Remi VANICAT]

William Lovas <wlovas@stwing.upenn.edu> writes:

> Mmm, this certainly is a useful use of polymorphism without parametrized,
> types, but the challenge i was trying to propose was more to the spirit of
> the original 'a -> 'a theorem: by "useful function that operates on just
> 'a's", what i meant was essentially "a non-trivial function of type
> 'a -> 'a", which is (i hope) a significantly more difficult challenge :)
> 
> Polymorphism as used in `raise' and `ignore' strikes me as more language
> magic than anything else -- although useful in practice, i have a strong
> intuition that from a certain theoretical perspective, namely that of
> purely functional languages, they're not so interesting.  So, to clarify,
> while they are practical uses of polymorphism, they're not what i had in
> mind when i wrote the above paragraph.

Well, the ignore function is just an example of a constant function,
that may be of some interest in some case. The raise function is more
complex as it use exception that are a difficult matter in purely
functional languages. But I remember to have seen a try to add
exception to Haskell, so there might be intersting too.
-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Pierre Weis]

> > The problem is what *assembly code* should be generated for function f?
> > Code to add 2 integers or code to add 2 floats? Hmm.. we'll have a
> > problem then. Or maybe both? And choose versions of f based on type it
> > is applied to? But then consider:
> >
> > let f x1 x2 ... xn = ((x1 + x1), (x2 + x2), ..., (xn + xn))
> >
> > you need to generate 2^n versions of f. We're getting to ugly things
> > like C++ templates here.
> 
> If this is really a problem then what gets generated when you write any 
> polymorphic function at all? The proposal is to allow constrained 
> polymorphism; the polymorphism that is already in OCaml seems to 
> supersede this with regard to the above objection.
> 
> I wonder if the unification algorithm can be generalized to intersect 
> sets of allowable types instead of unifying "for all" type variables. 
> It doesn't seem too ludicrous in principle but I could easily have 
> missed some nasty corner case.
> 
> -Mike

Yes: I suspect a really nasty corner in this area. As far as I
remember, the kind of types you suggest is known as ``intersection
types'', and the type reconstruction problem for languages featuring
those types is just undecidable. The big problem with this kind of
stuff is to restrict the type schemes allowed in your type system such
that you do not fall into the undecidable general case, while still
maintaining a powerful enough type system to properly typecheck the
function double (fun x -> x + x).

Unfortunately, this far from trivial...

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Christophe Raffalli]

Pierre Weis wrote:

 >
 > Yes: I suspect a really nasty corner in this area. As far as I
 > remember, the kind of types you suggest is known as ``intersection
 > types'', and the type reconstruction problem for languages featuring
 > those types is just undecidable. The big problem with this kind of
 > stuff is to restrict the type schemes allowed in your type system such
 > that you do not fall into the undecidable general case, while still
 > maintaining a powerful enough type system to properly typecheck the
 > function double (fun x -> x + x).
 >

This is not the only solution: another solution is to keep the simple (in the
definition) type system with an incomplete algorithm that will always succeed
if enough type information. This works for instance for Mitchell's system F
with subtyping (see my normaliser:
<http://lama-d134.univ-savoie.fr/~raffalli/normaliser.html>)

The diffculty is that you need to have a very good way of printing typing error
message so that the user can easily guess where to add type information until
it works or a real error in the code is detected. Recent work (in a simple
setting) by Christian Haack, and Joe Wells
<http://www.cee.hw.ac.uk/ultra/compositional-analysis/type-error-slicing> let
me think that there may be a (non trivial) solution.

The big advantage, is that there are (undecidable) type systems that can
unifies typing of record, modules and object; functor and functions. Then, you
have a simpler type system definition which is easier to extend (with operator
overloading, for instance).

Remark: it does not change much the picture, because you have to find a
subsystem of the simple undecidable system. The difference, is that you can
define the subsystem by some limit to the typing complexity in the undecidable
system ... This is still far from trivial, but there is a lot of freedom (so
place for research :-).

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Pierre Weis]

> On Fri, Nov 29, 2002 at 04:52:03PM -0000, Nicolas Cannasse wrote:
> > Of course the ML type system relies on type inference and need do choose the
> > "best available" type but what if we enrich the type system with an "OR"
> > operator ? Then if (+) is overloaded on floats, you'll get :
> > 
> > f :  int -> int OR float -> float
> > or something like a type constraint :   f : 'a -> 'a where 'a in [int;float]
> > 
> > This approach seems trivial to me, but I really can understand that this
> > require a lot of addins in the typing algorithms & theory. BTW, does one of
> > the upper approach has already been discussed ? any paper on it ? any
> > countersample that will make me feel stupid ? :)
> 
> The problem is what *assembly code* should be generated for function f?
> Code to add 2 integers or code to add 2 floats? Hmm.. we'll have a
> problem then. Or maybe both? And choose versions of f based on type it
> is applied to? But then consider:
> 
> let f x1 x2 ... xn = ((x1 + x1), (x2 + x2), ..., (xn + xn))
> 
> you need to generate 2^n versions of f. We're getting to ugly things
> like C++ templates here.
> 
> There is third answer: generate code that checks if it's passed int or
> float. But this has very significant perfomance impact.
> 
> -- 
> : Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
> : PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h
> -------------------

There a fourth answer, more efficient than those approches, that we
call generic flows. See Jun's thesis for more detailed explanation...

Hope this helps,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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] Understanding why Ocaml doesn't support operator overloading.

[Pierre Weis]

[...]
> Of course the ML type system relies on type inference and need do choose the
> "best available" type but what if we enrich the type system with an "OR"
> operator ? Then if (+) is overloaded on floats, you'll get :
> 
> f :  int -> int OR float -> float
> or something like a type constraint :   f : 'a -> 'a where 'a in [int;float]
> 
> This approach seems trivial to me,

To me too: I just needed 5 years to set up and publish the theory and
Jun Furuse needed 6 years only to write a thesis with full proofs.

So you're right, it is indeed trivial.

> but I really can understand that this require a lot of addins in the
> typing algorithms & theory. BTW, does one of the upper approach has
> already been discussed ? any paper on it ? any countersample that
> will make me feel stupid ? :)

Yes, they are papers on it (to start with, read my POPL'95 paper with
François Rouaix and Catherine Dubois). You may also have a look to
Jun's thesis http://pauillac.inria.fr/~furuse/thesis/.

Have fun!

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


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