Lambda the Ultimate

Overloaded based on type. I can see how to use variant types to overcome the problem of not having type, but as you indicated that isn't the question.

The question is why are they left out. The reason I ask, is that I am working on a type inference engine for Cat (a stack based language), and I can't, for the life of me, figure out a good reason to leave out function overloading based on type.

It appears to be hard to do so, but not intractable, unless there is something that I have overlooked.

Check out G'Caml. It's a fork of O'Caml with function overloading. Just judging from its type annotations, it's easy to see how complicated the type of a generic can become, especially when higher-order functions and functions which call generics come into play.

Thanks for pointing that out to me, I'll definitely take a careful look at it.

What a wonderfully complete and detailed reply! I really appreciate that you took the time to share that with me.

It would be interesting to see a list of what "basic" things language designers should use to validate their new fancy-pants features. To some degree it comes down to preference (presumably not everybody really cares deeply personally about having overloading), but having a short list of "miner bird" feature requirements would be neat. My personal beef is debugging; if humans can't realistically step through systems you've created, then you've created something unrealistic (again, personal desire/bias/domain/opinion). The funny thing is that even debugging threaded C++ or C# in expensive MS tools is a bad joke, as far as I can tell.

Overloading in C++ is essential for compile-time polymorphism. For example there is an implementation of sorting which works for any sequence type which satisfies the given interface.

While there are other means possible for archieving the dispatch (like higher order functions, Haskell classes, ML functors, OOP-style polymorphism, dynamic typing with generic functions), overloading makes C++ a better language, not worse. Compile-time polymorphism is an important and useful feature of C++.

C++ overloading is more or less premature optimisation, considering the fact that, given a general overloading mechanism, it's fairly trivial to optimise it down to compile-time dispatch in the correct cases.

C++ provides too many ways to achieve polymorphism. Parametric polymorphism can be achieved by template functions, but you cannot guarantee a function is truly parametric. Then, to get ad hoc polymorphism you have to choose between templates, subclassing, overloading or specialisation. Why can't we just have two interfaces: one to parametric polymorphism, one to ad hoc?

Overloading in C++ is essential for compile-time polymorphism. For example there is an implementation of sorting which works for any sequence type which satisfies the given interface.

That has relatively little todo with overloading, this is todo with templates and the word/term static/compile-time polymorphism in the context of C++ is used to specifically refer to templates. It's used to refer to the fact the one can do a form of compile-time duck-typing.

The only time overloading may come into play with implementations of the C++ standard library generic algorithms is when a more efficent implementation exists depending on some critieria which is known at compile-time. On template instantiation, if the criteria matches the more efficient/specific version is selected. The information exists in types & compile-time constants, the technique is called compile-time tag dispatching. One could consider this as a static/compile-time form of predicate dispatching.

C++'s overload resolution is static
multimethods is overloading where overload resolution is dynamic.

"Overriding" is just a special case of overloading where overload resolution is dynamic.

The only time overloading may come into play with implementations of the C++ standard library generic algorithms is when a more efficent implementation exists depending on some critieria which is known at compile-time

No. The implementation of an algorithm which uses iterators relies on the fact that expressions like ++it, *it, it1 == it2, it+N, it[N] etc. are defined and have a particular abstract meaning. It's often a single implementation usable with various iterator types.

Tag dispatching is a more specific usage: here different code is used for different choices of driving types, found with overloading or template specialization. Often each implementation is still overloaded for a family of types sharing particular properties. But overloading is used even if there is a single implementation which calls overloaded functions.

No. The implementation of an algorithm which uses iterators relies on the fact that expressions like ++it, *it, it1 == it2, it+N, it[N] etc. are defined and have a particular abstract meaning. It's often a single implementation usable with various iterator types.

... Yes i know, i'm not saying that and again as i said before this has nothing to do with C++ style overloading, overloading doesn't come into play with this part except when you're actually using overloaded functions within a template definition.

C++ ISO standard defines a set of *Concepts* for the C++ standard library which you where refering to as *interfaces* but there not really interfaces there more richer than that, There not dynamic entities. As of current Concepts are only conceptual entities until C++0x comes with Concepts as first-class entities this will give templates a form of bounded quantification. Similar to extending interfaces or type classes one can make refinements of other Concepts e.g.

Forward Iterator Concept is a refinement of the Input & Ouput Iterator Concepts
these Concepts do not exist in code (not until C++0x comes with Concepts as first-class entities).

Similar to type classes where a type can be an instance of a "class" one makes a type a model of a particular Concept by implementing the required operations e.g.

std::vector::iterator is model of the Random Access Iterator *Concept*.

However as of current making these relationships ("model of", "refinement of", etc, et) are not explicit because Concepts in current C++ are only conceptual.

Now when one wants a generic algorithm to do something different from the generic routine one can write code to introspect at compile-time information such as the concreate kind of iterator Concept an iterator "type instance" models this is done by using the iterator category tag type, which uses C++ subtyping to descern between refinements and overloading for compile-time matching and/or dispatching.

The only othertime where C++ style overloading may occur in the context of template functions is when you are actually using overloaded functions within the definition of template function but this has nothing to do with what C++ terminology of compile-time/static polymorphism is referring to and this term isn't used to refer to C++ style overloading either.

Consider this:

struct foo { void bar() {} };
struct scooby { void bar() {} };

template < typename T >
void foobar(const T& v) {
v.bar();
}

int main() {
foobar(foo());
foobar(scooby());
}

Are you telling me this has anything to do with overloading? well it isn't, maybe on the conceptual level but that is all. What is happening in foobar is what is refered to as compile-time/static polymorphism in C++ terminology.

Tag dispatching is a more specific usage: here different code is used for different choices of driving types, found with overloading or template specialization. Often each implementation is still overloaded for a family of types sharing particular properties.

Isn't that what i just told you previously or what i'm trying to tell you...

That has relatively little todo with overloading, this is todo with templates and the word/term static/compile-time polymorphism in the context of C++ is used to specifically refer to templates. It's used to refer to the fact the one can do a form of compile-time duck-typing.

Function overloading can be defined as providing more than one implementation for a function with the same fully qualified name, but varying on the number and/or type of arguments. Marcin is completely correct in his statement.

Function overloading can be defined as providing more than one implementation for a function with the same fully qualified name, but varying on the number and/or type of arguments. Marcin is completely correct in his statement.

Are you just ignoring everything i wrote or not bothering to read? clearly you've misunderstood what i'm trying to say.

Lets begin with what i'm arguing with, this is the part that he/she said that i'm arguing is an incorrect statement:

... For example there is an implementation of sorting which works for any sequence type which satisfies the given interface.

He/she is referring to the generic algorithm std::sort, here is one of it's prototypes (std::sort itself is overloaded):


namespace std {
// ....
template < typename RandomAccessIterator >
void sort(RandomAccessIterator first, RandomAccessIterator last);
// ...
};


std::sort can take any iterator type that is a model of the Random Access Iterator *Concept*. For the last time the fact that it can take almost any iterator *type* has nothing todo with C++ style overloading.

Whoah, take a deep breath. :-)

For the last time the fact that it can take almost any iterator *type* has nothing todo with C++ style overloading.

I partially agree with this statement, however I took Marcin's statement to mean that the sort implementation expects that certain functions, like operator<, are going to need to be overloaded for it to work properly.

The reason I don't completely agree with your statement is that in C++ when a function template is instantiated with different types, it effectively creates an overloaded function. Functions templates in C++ are in fact little more than macros.

I partially agree with this statement, however I took Marcin's statement to mean that the sort implementation expects that certain functions, like operator

Yes the first overload of std::sort expects the contained type to support the relational less than operator while the second overload has an extra argument that takes a binary predicate, but again this isn't necessarily todo with C++ style overloading look at my previous code example which proves that. The same would hold if user-defined operators are member functions in two different, completely unrelated classes/structs.

The term operator overloading is such a horrible term because one can say they have overloaded an operator and also have overloaded versions of that operator overload, baffles the mind. Personally i just call it "user-defined operators" to prevent confusion/ambiguity.

The reason I don't completely agree with your statement is that in C++ when a function template is instantiated with different types, it effectively creates an overloaded function. Functions templates in C++ are in fact little more than macros.

This is just on the conceptual level from a user's point-of-view and just an artifact of the implementation of templates from a compiler vendor's point-of-view, this isn't C++ style overloading itself.

Template functions themselfs are also considered in C++ overload resolution (you can check the C++ ISO standard) and template functions can be overloaded with other template functions too.

As i said before if you want to talk about C++ style overloading this isn't it, what you guys are talking about is just an artifact of an implemenation of parametric polymorphism in C++.

A recent post here to LtU pointed to a paper showing that type classes and Ocaml-style functors are equivelent (which, IMHO, proves your point about type classes wide applicability and power).

The important point here is that there is more than one way to skin this cat- overloaded operators is one, type classes a second, and functors a third. I'll admit to not being very familiar with type classes and haskell, but I am familiar with both C++ style operator overloading and Ocaml style functors, and I'll take functors over operator overloading any day. The advantage functors have is that the explicitly list which operators are needed for a given operation. In Ocaml, any point where you start wanting operator overloading, what you really want is a functor.

The important point here is that there is more than one way to skin this cat- overloaded operators is one, type classes a second, and functors a third. I'll admit to not being very familiar with type classes and haskell, but I am familiar with both C++ style operator overloading and Ocaml style functors, and I'll take functors over operator overloading any day. The advantage functors have is that the explicitly list which operators are needed for a given operation. In Ocaml, any point where you start wanting operator overloading, what you really want is a functor.

I think you're slightly confusing things, the discussion is on ad-hoc polymorphism (the overloading kind) and not user-defined operators (which may also be overloaded themselfs).

I seem to have missed that post, but I would say that it is a bit of a stretch to say that they are equivalent. Of course, there are encodings in either direction, but considering expressive power based on the Felleisen definition, type classes and modules are certainly incomparable, i.e. neither subsumes the other.

There is a large overlap, but how large exactly depends heavily on what extensions to the type class system you are considering, and what semantics you assume for modules. For example, applicative functors bring you closer to type classes but are themselves incomparable in expressive power to generative functors.

A recent paper looks at extending a quite general ML module calculus to express type classes. It requires significant additional machinery.

This may be of some interest.

It's such a shame that the authors of the Haskell prelude mucked it up by putting +,-, and * in the same type class as abs and signum - so that if you want to overload +,-,* for matrix or polynomial arithmetic, say, then you have to think up some kludge meaning for abs, signum in that context.

No. If two objects (type classes) aren't related, they shouldn't share the same interface, period. In a perfect world, this would be all fine and dandy, however, mathematicians are possibly the laziest people I have ever seen. They tend to overload the common symbols and names with conflicting operations, e.g. numerical multiplication vs. matrix multiplication. This generally doesn't matter too much when you're just dealing with equations, but once you start carrying this over to programming, you start to degrade the compiler's ability to check your program because you're providing conflicting information.

You make it sound like mathematicians are simply profligate with notation, using the same notation for all sorts of different things out of laziness. Well, that's not the way mathematicians see it. They have abstraction called a "ring", a generalisation of the integers, which is basically any class for which +,-,* are defined and obey certain rules - for example, matrices, polynomials. There's nothing unprincipled about this - it's the same sort of abstraction that programmers make all the time. The problem with the Haskell prelude is that it doesn't cut up mathematical space in the right way - the way that generations of mathematicians have found to be the most useful. For mathematicians, the arithmetic operations +,-,* are logically a different abstraction from the magnitude operation abs, and the order operation signum.
(Google for "Haskell numeric prelude" for more on this.)

Later: To clarify, the point I'm making is that operator overloading is a desirable feature because it can make code much more readable. But if type classes cut up the space in the wrong way, then they get in the way of valid uses of operator overloading (such as defining +,-,* for matrices).

You make it sound like mathematicians are simply profligate with notation, using the same notation for all sorts of different things out of laziness. Well, that's not the way mathematicians see it. They have abstraction called a "ring", a generalisation of the integers, which is basically any class for which +,-,* are defined and obey certain rules - for example, matrices, polynomials. There's nothing unprincipled about this - it's the same sort of abstraction that programmers make all the time.

Correct. I'd forgotten that matrix multiplication does share some properties with numeric multiplication.

The problem with the Haskell prelude is that it doesn't cut up mathematical space in the right way - the way that generations of mathematicians have found to be the most useful. For mathematicians, the arithmetic operations +,-,* are logically a different abstraction from the magnitude operation abs, and the order operation signum.
(Google for "Haskell numeric prelude" for more on this.)

I'm not too fluent in haskell, so I can't really comment on this. Specifically, you are correct in that different abstractions would be needed for the different uses.

The problem with the Haskell prelude is that it doesn't cut up mathematical space in the right way - the way that generations of mathematicians have found to be the most useful. For mathematicians, the arithmetic operations +,-,* are logically a different abstraction from the magnitude operation abs, and the order operation signum. (Google for "Haskell numeric prelude" for more on this.)

I'm interested in learning more about this. Specifically, how might one encode what "generations of mathematicians have found to be the most useful" into a programming language, and also what language features might best support that.

Can you (or anyone) recommend further reading? A good book on abstract algebra, perhaps? I'll google the supplied string, but I'm also interested in broader issues. Thanks.

For universal algebra, a good free introduction can be found here.

I also recommend Pierce's Basic Category Theory for Computer Scientists, but only after a bit of work in universal algebra, because Pierce says things like "Another class of familiar algebraic structures, monoids, also forms the basis of a category:" and that's on page four. Gulp—I had no idea what a "monoid" was when I read that. In fact, I still don't. :-)

Finally, a great way (IMHO) to learn this kind of material is interactively, with a good proof assistant supporting essentially the entirety of constructive mathematics at your fingertips. I like Coq a lot so far, both because of the software itself and because of Coq'Art, which is proving quite enjoyable to work through.

At risk of going off-topic, a monoid is a combination of a set (which I'll call S for now), a binary operation closed on S (* for now) and a distinguished element of S (which I'll call i), such that * is associative and i is an identity under *. For example, the naturals form a monoid with addition and 0, and with multiplication and 1. Strings also form a monoid, with concatenation as the operation and the empty string as identity.

You forgot the most important example and the one easiest to relate to categories: (endo)functions form a monoid with the multiplication composition and id as the identity. In fact, all monoids can be viewed this way (we can lift a monoid via m |-> \x.m*x). One computational example is a state machine.

I have and do highly recommend Barr and Well's Category Theory Lecture Notes for ESSLLI for an intro to category theory that uses these examples but provides definitions and is of a very computational bent. If you (Paul, or anyone else for that matter) have read it before, but it's been a while you may want to give it another read. That said, I have an issue with this and most other introductory material for category theory available online in that some notions that are extremely useful in actually doing category theory are left unmentioned, e.g. ends, indexed limits and Kan extensions. So I've wanted to write my own. I do have most of what I want on paper, but I need to get it into a computer sooner or later (and it better be sooner). Originally it was going to be just brutal and formalistic and not without basic category theory prerequisites, but as it got longer I decided to make it self-contained. In the mean time, the lecture notes here are closest (of what's online) to what I want.

[H]ow might one encode what "generations of mathematicians have found to be the most useful" into a programming language, and also what language features might best support that

Type classes can be used for what I had in mind. All I meant is that a type class groups several different functions (or operator overloads) together, and the numeric type classes in the Haskell Prelude don't group in the way that mathematicians would prefer.

In brief, the type classes I would define would look something like this:
Ring: (+), (-), (*) -- Similar to existing Num class
Field: (/) -- Similar to existing Fractional class
Normed space: abs -- abs is asking how big something is
Total order: signum -- signum is asking whether the element is before or after zero in the ordering

The point is simply that arithmetic properties, geometric properties, and order properties should be separate abstractions (ie separate type classes) - because in general you can have any one without the others.

For further reading - this is undergraduate maths, but the books I read as an undergraduate are probably out of print now - but for starters you could look at:
http://mathworld.wolfram.com/Ring.html
http://mathworld.wolfram.com/Field.html
http://en.wikipedia.org/wiki/Normed_vector_space
http://en.wikipedia.org/wiki/Metric_space
http://mathworld.wolfram.com/NormedSpace.html
http://mathworld.wolfram.com/MetricSpace.html

A book that is still in print is Fraleigh's A First Course in Abstract Algebra which gives a clear and concise presentation of the subject. It seems to be used in the first course in abstract algebra in many universities.

See DoCon and the Basic Algebra Proposal for alternative setups. I'm fairly certain there are some older discussions on the Basic Algebra proposal in the Haskell mailing list archives to give you an idea of some of the forces in the situation.

This confirms that I'm not the first mathematician to complain about this, and I won't be the last.
I happen to think that the Basic Algebra Proposal is a bit over the top. There's another project tackling this - Haskell numeric prelude - I don't know how good it is.
But it's all a bit futile unless someone among the Haskell great and good is going to take some notice.

First off, there is nothing keeping you from using these libraries now, but as I said, both of these have been discussed before (dig around the haskell mailing list). There may be some changes with Haskell', but probably nothing too dramatic. Probably just getting rid of the most egregrious things. If no existing library is satisfactory for you, you can also easily make your own. It is no trouble to qualify the Prelude (+), (-), etc. and to make your own. I do understand that this is less convenient than having it in the standard library and doesn't help when working with existing libraries.