Lambda the Ultimate

Re: multimethods, indeed most subsequent work in this area was done for Fortress IIRC. It's a very different beast than the paper I linked to, simultaneously more powerful and more limited due to its nominal types and multiple inheritance.

I'm not sure I quite grasp what you mean by reifying inferred type-directed code inference as a term, I'll have to think about it some more.

Any thoughts on "A Second Look at Overloading"? It seems to have some interesting properties. The limitations don't seem that terrible, but I haven't found much follow-up work.

In my experience multi-methods are too unstructured, and inhibit local reasoning because it is nearly impossible to know from the call site is something is a partial application or valid use of a function.

Partial application is only a problem if overloading on arity is permitted, or curried functions are used by default. It's definitely possible to detect whether an application is "valid" in the same sense that it's used in other languages. I'm not sure what you might mean by the above.

As programs get bigger this does not scale, and does not give the programmer any concise way to understand the whole program.

This conclusion seems dependent on assuming that overloading would be very pervasive. I'm not sure that's true. For precisely the reasons you specify, I'd wager most programs would stick with well-defined abstractions and smaller sets of overloads. However, multimethods give you the ability to loosely reorganize sets of functions into domain-specific abstractions without impacting existing code, particularly code you don't control, which is nice for refactoring purposes. That value shouldn't be underestimated.

For instance, none of the debates over reorganizing Haskell's prelude and the standard type class hierarchy would be needed. This benefit is also shared by the restricted type class-like overloads described in "A second look at overloading".

Only typing multimethods as first-class values is the true pain point, which is where you need intersection-like type signatures and usability suffers. And this still wouldn't solve the problem of duplication in cases like Haskell's sort/sortBy, which means you'd still probably need something like implicits.

Implicits then seem to yield the best value at this point.

[a quick note on the above, I did not mean partial application is a problem for the compiler, I meant it is a problem for the programmer in terms of reality and understandability of code. It makes local reasoning harder. Also in generic programming overloading is pervasive as we always try and write algorithms in their most generic form, as long as there is no performance loss. This means nearly every function takes typeclass constrained arguments instead of concrete types.]

As someone very interested in generic programming, Stepanov's "Elements of Programming" is really the book that defines this style.

Implicits offer no value over type classes because if something is not consistent over a type then the implicit mechanism is the wrong abstraction method. Type classes provide a way to generalise algebraic properties, for example there is only one way to add integers, and that is the way people expect '+' to behave, to overload it with anything else is a bad idea, and infact I want the type system to try and prevent this as much as possible.

The classic "wrong" example is "sort". People get confused by the fact you can only have one sort order with type-classes as reason why there is some sort of limitation, but this is misunderstanding the nature of type-classes. The goal of generic programming is to only ever define each algorithm once with maximum generality and no loss in performance. If you think about the "no loss in generality" you realise sort needs to be passed the order relation. As such the type-class constraint is something like types which have a binary relation, where that relation is a parameter. Given this the correct type for sort is quickly arrived at:

sort(f : I, n : I::DistanceType, r : R) requires I : Mutable + ForwardIterator, R : Relation, I::ValueType == R::Domain

I think the reason a lot of people have problems with type classes is that they try and start by defining interfaces without the necessary domain knowledge. Stepanov's method is to always start with the algorithms. Once you have a group of algorithms (say sorting algorithms) written without type classes, you look to abstract the common properties into interfaces. The abstractions used above are memory access pattern (the type of iterator) and the relation (order). Order is actually the simpler of the two because it is simply an operator and is consistently applied across all sort algorithms. Access pattern turns out to be far more interesting as it is a discrete dimension, and therefore requires categorising the useful access patterns (forward-one-pass, forward-multi-pass, bidirectional, indexed, and random access being the one's Stepanov uses).

Regardless of whether or not their application in these cases is "incorrect", type classes naturally lead to designs with duplication, like sort/sortBy, and these design mistakes don't have easy fixes in large codebases.

So even if you are correct, it seems perfectly reasonable to say that programming languages should permit manageable behaviour-preserving program transformations to correct any past design mistakes.

So even if I accept your position, named instances are precisely a reasonable solution to part of this problem. I'd argue the other is loosely coupling individual functions as in [1], rather than sets of functions as with type classes.

What does solve the sort/sortBy duplication? The only thing I can think of that solves it well is type classes done via implicit arguments: if you want to pass in an explicit order you can, but if you don't you get the standard one.

Yes, implicit arguments solve it by default, or type classes with the named instances extension are sufficient.

What is the standard order for integers?

I think languages should not encourage incorrect use. Implicit arguments are less optimal than type classes because they create an overlap with passing functions. In the example I gave the definition of sort is optimal (as far as I am aware) because it offers maximum generality with no performance loss, it can select an algorithm based on memory access pattern and ordering relation.

As the focus should be on algorithms, how would you classify sort algorithms differently? What dimensions and categories can sort algorithms be arranged into, and what are the best mechanisms.

Julia has type parameters, so iterating over two matrices of the same element type is efficient if you define your function like this:

function iter{T <: Real}(m1::Matrix{T}, m2::Matrix{T})
   ...
end

The compiler will then generate a specialised version for each type T. If you define it like this:

function iter(m1, m2)
   ...
end

Then it will be slow.

Type-classes also enable this kind of optimisation (often called specialisation). However as can be seen from C++ templates which also offer ad-hoc overloading, it can rapidly become an unstructured mess. Stepanov has been trying (amongst other people) to get C++ to adopt Concepts, which are effectively type-classes for C++ templates.

So in widely used mainstream languages, this kind of multi-method dispatch seems problematic, and type-classes are used to bring some order to the chaos. If you consider that multi-method dispatch is the normal method for C++ templates, it is telling that Stepanov's "Elements of Programming" uses only C++ Concepts throughout. The conclusion is that type-classes are the preferred abstraction, and multi methods are not suitable (as Stepanov created a new abstraction instead if using what was already there). C++ STL has concepts, except they are written in the documentation as the language had no way of expressing them at the time.