Best value for overloading?

There exist various approaches to overloading, including:

* type classes of various kinds
* traits
* implicits [2]
* multimethods
* other systems [1,3]

What seems to offer the best value for investment effort, expressiveness, and type safety?

For instance, multimethods are pretty flexible and uniformally allow a form of type-based and case-based overloading, but it seems quite difficult to capture accurate types with all the expressiveness we expect of ML functions, eg. first-class functions require intersection types and subtyping.

Type classes and traits seem more or less equivalent, but have problems with overlapping and named instances, a problem shared by [1] I believe. Implicits seem promising, and properly handle named and overlapping instances.

[1] A Second Look at Overloading
[2] The Implicit Calculus: A New Foundation for Generic Programming
[3] A Theory of Overloading

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Comments

Multi-methods have been little studied from the point of view of static types. Didier Rémy remarked to me some time ago that when the type-system community decided to work on object-oriented languages, they quickly narrowed their focus to single-dispatch language, and that maybe there are things left to be told about other visions of of OO, in particular multimethod languages. So it may not be a fair comparison.

I am not sure that there are essential difference between type-classes and implicits. For example, the way Coq does type-classes (using dependent types) has strong similarities to a system where all instance declarations are named, and therefore may feel closer to implicits than Haskell's presentation to some -- but it's a natural extension of Haskell type-classes nonetheless.

I think that in statically typed languages, type-directed code generation/inference/synthesis¹ is a good tool for concision and usability (which covers overloading, but also other domains). If you can guarantee consistency, that's a nice property to have, but if that contradicts modularity it's probably too high a price to pay. The more common case is when consistency cannot be guaranteed, and then I think naming all things is a good design.

¹: "type-directed code inference" means that the behavior that is inferred from the type can be described as a term in the programming language itself. This term is not made explicit in Haskell type-classes, but note that each instance declaration shape corresponds to a term former (conditional instances are function declarations -- like implicit function with implicit arguments). If you allowed to define instances in arbitrary other ways, you may lose that property that the elaboration result can be witnessed by a program term -- but terms in functional languages are quite powerful, and in particular could witness most "logic programming" approaches.

Re: multimethods, indeed

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.

Type-classes, traits, implicits

I have to be a bit careful because the word trait is used differently in different languages (C++ traits are something different), but from the context of the question I will assume Rust style traits.

Type-classes, traits and implicits are all the same thing. Being able to name instances does not affect their implicit selection, although it does allow for alternative explicit use (which unifies the concepts of a type-class and a record (or a limited form of module if type classes have associated types). All of these are effectively type constraints.

Multi-methods are different and require intersection types, and permit ad-hoc overloading.

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.

In generic programming we still need a classification of things to make the world follow some kind of structure, else we just have a mess.

The critical factor for soundness is that when I write a function I need to know if it is legal to call each function in the definition. Whilst this can clearly be done with intersection types, the results are not meaningful categories, but collections of individual definition types. As programs get bigger this does not scale, and does not give the programmer any concise way to understand the whole program.

In my experience

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.

Type-classes are optimal for generic programming

[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

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

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 give

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

Standard Order

What is the standard order for integers?

Classifying sort algorithms

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.

Multimethods and natural performance

Multimethods are central in Julia, and one interesting indirect effect of the design is that they are in fact good performance enablers. For example, the `+` operation is split into many declared multimethods with different parameter types, and each of these declarations can be optimized with knowledge of the dynamic types of its arguments.

In a sense, multimethods naturally lead to a style of programming where optimization does as well as what would require aggressive specialization in other dynamic languages. Compiling Julia to LLVM in a relatively straightforward way gives rather good performances (the benchmarks shown so far mostly used this implementation technique, with very little in the form of speculative optimization etc.), while that is not at all the case with Javascript, Python, Ruby etc.

On the other hand, while this may be true for multimethods with arguments of basic types (or containers annotated with type information, eg. Matrix instead of Matrix), this would not hold with very generic code (iterating on two Matrix of the same element type, generically over the element type). So I wonder whether relying on a relative-straightforward implementation does not also encourage users to write less abstract code, in effect to do the rest of the specialization by hand, inducing code duplication.

Julia has type parameters,

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.

Typeclasses order the chaos

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.

OASIS

One paper on overloading that hasn't seen much traction appears to be a thesis, Parametric Overloading in ML by Charles C. Krasic:

A prototype implementation of Oasis, including a compiler and top-level interpreter, was constructed from the Caml-Light system. An overview of the design of the prototype will be given. The prototype helps to investigate and demonstrate the effectiveness of Oasis extensions. A key aspect of parametric overloading in Oasis is that all let bound values are overloaded; there is no new language construct for introducing overloaded values. The feasibility of this approach is affirmed by the successful bootstrapping of the Caml-Light system with Oasis. The assumption that all let bound values are overloaded required less than a dozen of the thousands of lines of Caml-Light code to change.

Looks like a very lightweight approach to introducing very general, implicit overloading on all pure let generalizations in plain old ML.

This has a flavour of implicits linked in the original post, but it happens int the context of standard let generalizations rather than a separate language controlling a "separate implicit environment"