Operator overloading

Operator overloading

[oleg]

This message illustrates the translation of Haskell98 non-constructor
classes to OCaml, which gives us bounded polymorphism and a sort of
polymorphic recursion in OCaml.

It has to be remarked first that overloading is quite a complex issue:
please see `A Theory of Overloading' by Stuckey and Sulzmann (TOPLAS
2005) for many gory details.  The issue of the type of the plus
operation: 'a->'a->'a or 'a->'b->'c is not an abstract
subtlety. That's why functional dependencies where introduced in
Haskell (and quite often we need local functional dependencies to
resolve overloading). There are three main techniques of implementing
overloading: full inlining (aka C++), dictionary passing, and
the intensional type analysis. The latter is like `switch' and dictionary
passing is like a `vtable'. GHC and Hugs implement dictionary passing,
whereas JHC and Chameleon implement typeclasses via intensional type
analysis. I suspect F# might be doing something like that too, because
CLI might have run-time type tags. 

Non-constructor Haskell 98 classes (that is, overloading over parameter
of the kind *) can be implemented in OCaml in a straightforward way.

We start with a typical Haskell code

class Numb a where
    add :: a -> a -> a
    shw :: a -> String

instance Numb Int where
    add x y = x + y
    shw = show

instance Numb Float where
    add x y = x + y
    shw = show

instance Numb a => Numb [a] where
    add = zipWith add
    shw a = "[" ++ concatMap (\x -> (shw x) ++ " ") a ++ "]"

summ (h:t) = foldl add h t

test1 = shw (add [(1::Int),2,3] [4,5,6])
test2 = shw (summ (add [(1::Int),2,3] [4,5,6]))
test3 = shw (summ [(1.0::Float),2.0,3.0])
test4 = shw (summ [[(1.0::Float),2.0,3.0], [4,5,6], [7,8,9]])

We introduce a class Numb with two methods, for addition and for
showing. The latter is quite handy. The instances for Int and Float
are trivial. The instance of [a] says that if the type of list
elements is in class Numb, the list is in class Numb as well. Note the
definition for the "add" method in that case. It looks recursive: the
body of 'add' invokes 'add' itself, but on a different type.

We then define a function summ. Its inferred type is 
	summ :: (Numb a) => [a] -> a
The function is bounded polymorphic: it works on lists of any type
provided that type is in Numb. The tests test3 and test4 demonstrate
that summ can sum lists and lists of lists, etc.

Here's the OCaml translation:

(* class Numb a *)
type 'a numb = {add: 'a -> 'a -> 'a; shw: 'a -> string};;

(* instance Numb Int *)
let numb_i = {add = (+); shw = string_of_int};;
(* instance Numb Float *)
let numb_f = {add = (+.); shw = string_of_float};;

(* instance Numb a => Numb [a] *)
let numb_l numb_e = {add = List.map2 numb_e.add; 
		     shw = fun a -> 
		       "[" ^ List.fold_right 
			       (fun e z -> " " ^ numb_e.shw e ^ z) a "]"};;

(* we can define a bounded polymorphic function summ *)
let summ numb (h::t) = List.fold_left numb.add h t;;

let test1 = 
  let n = numb_l numb_i in
  n.shw (n.add [1;2;3] [4;5;6]);;

let test2 = 
  let n = numb_l numb_i in
  numb_i.shw (summ numb_i (n.add [1;2;3] [4;5;6]));;

let test3 = 
  numb_f.shw (summ numb_f [1.0;2.0;3.0]);;

let test4 = 
  let n = numb_l numb_f in
  n.shw (summ n [[1.0;2.0;3.0]; [4.0;5.0;6.0]; [7.0;8.0;9.0]]);;


The inferred type of summ in OCaml is
	val summ : 'a numb -> 'a list -> 'a = <fun>
It is instructive to compare it to the Haskell type. The only
difference is in the shape of the arrow: "Numb a =>" vs "'a numb ->".
Instead of the double arrow of Haskell we have the single arrow in
OCaml. The OCaml function summ is likewise bounded polymorphic: it
applies to arrays of any type provided that we have the _evidence_
(the dictionary) that the type is in the class numb. We must pass that
evidence as the first argument of summ. Granted, the burden of procuring
this evidence is on us; Haskell, in contrast, can, most of the time,
build that evidence by itself. As in Haskell, we can sum lists of
numbers and lists of lists of numbers, etc.


Haskell constructor classes (overloading over the parameters of 
higher kinds) do require OCaml functors. The example is a monad. With a
bit of syntactic sugar, the monadic notation and the corresponding
overloading are tolerable in OCaml.

Conversely, OCaml and SML modules (including sealing, generative and
applicative functors and recursive structures) can be emulated in
Haskell typeclasses. Chung-chieh Shan and I wrote a couple of messages
on that topic back in August and September 2004 on the Haskell mailing
list.


John Skaller wrote: ``(Haskell does this little cheat .. it makes
typeclasses very easy to explain to OO people).'' Are you sure about
that? There has been many long and recurring threads on Haskell-Cafe
about typeclasses and OO classes. I think the common advice is _not_
to think of Haskell typeclasses as of OO classes. Ralf Laemmel and I
once wanted to elaborate on the issue of OO in Haskell; we ended up
with a 79-page paper. I guess that shows that OO is never easy.

Re: [Caml-list] Operator overloading

[skaller]

On Thu, 2007-03-08 at 23:36 -0800, oleg@pobox.com wrote:

> John Skaller wrote: ``(Haskell does this little cheat .. it makes
> typeclasses very easy to explain to OO people).'' Are you sure about
> that? There has been many long and recurring threads on Haskell-Cafe
> about typeclasses and OO classes. I think the common advice is _not_
> to think of Haskell typeclasses as of OO classes. Ralf Laemmel and I
> once wanted to elaborate on the issue of OO in Haskell; we ended up
> with a 79-page paper. I guess that shows that OO is never easy.

Certainty requires at least a proof sketch, which I don't have.
However I do have a 'gut feeling' :)

It's hard to say, because in OO terms Haskell typeclasses
are so weak it's surprising they're any use at all.

If you consider your record implementation, observe
it is just a weak special case of a C++ class.
C++ classes can also provide state and inheritance.
The state looks vaguely like dependent typing to me .. :)

OK, so now we have a much more powerful model .. yet
it has known limitations, in particular the so-called
'covariance' problem prevents OO from modelling any
serious kind of system: for example a system
with binary operators doesn't admit an OO representation.

So all you need to do is elevate this model up one kinding
level to see typeclasses, even with the additional power
of 'everything C++ classes can do' are limited.

Of course it is argument by analogy and intuition, not
any kind of formal proof, that's for the experts :)

Felix currently has multi-parameter typeclasses which
use inlining because it's a whole program analyser,
so it can, however explicit objects would be required
either for separate compilation, or simply to experiment
with the 'extra power' of dynamic binding.

The 'obvious' implementation is of course a C++ class.

The difference to ordinary use is that the object doesn't
represent a type, but a typeclass, possibly with dependent
type parameters: eg a 'get' method for an array with
the length as a state variable.




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

Re: [Caml-list] Operator overloading

[Andreas Rossberg]

skaller wrote:
> 
> It's hard to say, because in OO terms Haskell typeclasses
> are so weak it's surprising they're any use at all.

Not sure how you come to that conclusion. Both concepts are somewhat 
incomparable, but there are a number of axes along which type classes 
are much more expressive than OO classes.

Ignoring implementation inheritance, I claim that in combination with 
existential types, even relatively basic type classes are strictly more 
powerful than OO classes (modulo some lack of syntactic sugar).

Have a look at Oleg's paper.

> C++ classes can also provide state and inheritance.
> The state looks vaguely like dependent typing to me .. :)

I grant you (implementation) inheritance, but I don't understand the 
rest of your comment. State is orthogonal to classes. Surely you can 
define a type class that contains a, say, IORef (for per-class state). 
Likewise, you can instantiate type classes to stateful types (as the 
equivalent to per-object (mutable) state).

> OK, so now we have a much more powerful model ..

I don't think so.

> yet
> it has known limitations, in particular the so-called
> 'covariance' problem prevents OO from modelling any
> serious kind of system: for example a system
> with binary operators doesn't admit an OO representation.

Which is one of the problems type classes do not have, because qualified 
types *are* more expressive than subtyping in that respect.

AFAICS, the rest of your argument hence does not follow.

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

Re: [Caml-list] Operator overloading

[skaller]

On Fri, 2007-03-09 at 14:52 +0100, Andreas Rossberg wrote:
> skaller wrote:
> > 
> > It's hard to say, because in OO terms Haskell typeclasses
> > are so weak it's surprising they're any use at all.
> 
> Not sure how you come to that conclusion. Both concepts are somewhat 
> incomparable, but there are a number of axes along which type classes 
> are much more expressive than OO classes.

I'm sorry to write so poorly. This isn't the comparison I'm
drawing. 

Consider *implementing* typeclasses with records,
as in Oleg's Ocaml examples.

Ok, now replace the records with classes. Classes
are more powerful because they provide

(a) state
(b) inheritance etc

They also don't make the weak assumption of an 
abstraction (possibly with default methods as in Haskell)
and a single instantiation: in C++ at least you can
have sequence of more derived classes.

So the type model associated with this implementation
can do more than the one just using plain records:
records aren't typeclasses, so the class based implementation
can't be compared with them:

	records   		classes
	typeclasses		???????

Clearly ???? is more expressive than typeclasses, whatever it
is .. I am guessing the state of the classes provides dependent
typing but I don't really know.

Anyhow my ARGUMENT was actually that using classes
subsumes plain old records .. and classes are
limited by the covariance problem, so records
must be limited too.



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

Re: [Caml-list] Operator overloading

[Andreas Rossberg]

skaller wrote:
> 
> I'm sorry to write so poorly. This isn't the comparison I'm
> drawing. 
> 
> Consider *implementing* typeclasses with records,
> as in Oleg's Ocaml examples.
> 
> Ok, now replace the records with classes. Classes
> are more powerful because they provide
> 
> (a) state
> (b) inheritance etc

Records and classes are not in the same category. Records and *objects* 
are. OTOH, objects *are* basically records, except that they usually 
come with more expressive typing, particularly allowing recursive types 
and subtyping. State is still orthogonal - records can have state, too.

Classes are a mechanism for *creating* objects (and in weaker languages 
than OCaml, for defining subtyping relations). Take away inheritance and 
you are basically left with fancy syntax for a function creating a 
record of mutually recursive closures over some local variables.

> They also don't make the weak assumption of an 
> abstraction (possibly with default methods as in Haskell)
> and a single instantiation: in C++ at least you can
> have sequence of more derived classes.

Please distinguish subtyping and inheritance. Type classes can express 
something akin to nominal interface subtyping, e.g.

   class C a        where m1 :: t1
   class C a => D a where m2 :: t2

But it's true that they do only provide a very weak form of inheritance 
(via default methods).

> So the type model associated with this implementation
> can do more than the one just using plain records:
> records aren't typeclasses, so the class based implementation
> can't be compared with them:
> 
> 	records   		classes
> 	typeclasses		???????

I cannot make much sense of this diagram, because of the category 
mismatch I mentioned above.

> Anyhow my ARGUMENT was actually that using classes
> subsumes plain old records .. and classes are
> limited by the covariance problem, so records
> must be limited too.

Something like the covariance problem does not occur with type classes 
(or modules, for that matter) because they decouple types from 
interfaces. A type class is merely an interface, witnessed by a record, 
the actual type is abstracted out. With OO, this is mingled together (an 
object type *is* its interface), which produces that nasty recursion 
where all the type problems originate.

So the difference is in the way these features factorise abstraction, 
rather than in the intrinsic expressiveness of the underlying 
primitives. Operationally, you can view dictionaries as detached 
"vtables". This detachment allows them to be used in more flexible ways, 
and avoid nuisances like the binary method issue.

Of course, it also makes inheritance a rather alien concept.

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

Re: [Caml-list] Operator overloading

[skaller]

On Fri, 2007-03-09 at 17:28 +0100, Andreas Rossberg wrote:
> skaller wrote:
> > 
> > I'm sorry to write so poorly. This isn't the comparison I'm
> > drawing. 
> > 
> > Consider *implementing* typeclasses with records,
> > as in Oleg's Ocaml examples.
> > 
> > Ok, now replace the records with classes. Classes
> > are more powerful because they provide
> > 
> > (a) state
> > (b) inheritance etc
> 
> Records and classes are not in the same category. Records and *objects* 
> are.

That depends on terminology. I was thinking in C++ terms:

	record = struct
	class = struct with methods

>  OTOH, objects *are* basically records, except that they usually 
> come with more expressive typing, particularly allowing recursive types 
> and subtyping. State is still orthogonal - records can have state, too.

Yes, records can have state, but usually any functions stored
in record fields are not bound to the state of the record.
Methods of an object are bound to the state of the object.

> Classes are a mechanism for *creating* objects (and in weaker languages 
> than OCaml, for defining subtyping relations). Take away inheritance and 
> you are basically left with fancy syntax for a function creating a 
> record of mutually recursive closures over some local variables.

Sure, but you're missing the point. In Haskell and in Oleg's Ocaml
implementation of typeclasses, a record object is like a C++ vtable.

A vtable contains static function pointers which can be
bound to the current object to create methods.

But I'm talking about replacing this with a class object,
so we're not talking about the methods binding against the
typeclass datatype .. we're talking about methods bound
against the typeclass itself.

> > They also don't make the weak assumption of an 
> > abstraction (possibly with default methods as in Haskell)
> > and a single instantiation: in C++ at least you can
> > have sequence of more derived classes.
> 
> Please distinguish subtyping and inheritance. 

I did. I said 'derived classes'.

> Type classes can express 
> something akin to nominal interface subtyping, e.g.
> 
>    class C a        where m1 :: t1
>    class C a => D a where m2 :: t2
> 
> But it's true that they do only provide a very weak form of inheritance 
> (via default methods).

Yes, its very weak. I don't know Haskell, but in Felix I have
typeclasses where I need to override the default method and I can't.

I don't know if Haskell suffers this restriction, but for someone
used to using C++ it shows the weakness of the 
typeclass/instance dichotomy  immediately. 
I actually need to do this:

typeclass container[bag,value] {
	virtual fold ..; // no default method
}

typeclass stl_container[bag,iterator,value] { 
   inherit container[bag,value]; // "implementation inheritance"
   fold .. // default method
}

because all STL containers have a single fold function,
implemented by using iterators. I need to instantiate
fold in the derived typeclass stl_container, but I'm
not allowed to.

So what I require is a tree:

	container --> stl_container --> vector --> vector<int>

and the distinction between typeclasses and instances is
a serious obstacle.

A C++ class has no such problems: you aren't limited to
defining an abstraction and one concrete instance class.

Roughly, my typeclasses allow adding new methods, but
you cannot override a method in a derived typeclass.

> Something like the covariance problem does not occur with type classes 
> (or modules, for that matter) because they decouple types from 
> interfaces. 

That's right.. it only occurs when you go up to the kind level.
Which occurs immediately if you want to try some dependent typing.
[I'm assuming a typeclass system with multiple type parameters
is required of course]

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