What is a "multisorted algebra", and how do I use it to solve "real problems"?

Question

Apparently, Alexander Stepanov has stated the following in an interview:

“I find OOP [object-oriented programming] technically unsound. It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras - families of interfaces that span multiple types.” [Emphasis added.]

Ignoring his statement regarding OOP for a moment, what are "multisorted algebras", beyond his terse definition, and can you give a practical example of how they are used (in the language of your choice)?

Answer 1

I believe he was talking about generic programming (he coined the term), whether meant in the context of this talk about the STL, or 'at large', in the sense of:

1. programming against a sort of interface that describes something that could fit all (and hopefully several) types (hence multi-sorted), ...
2. ... provided they have some properties, often something about the nature of some operations on elements of that type (hence algebras).

To do (1), you need to have a way to specify a program that takes a type as a parameter, i.e. polymorphism, and to do (2), you need a way to say that you also want that type to carry specific operations (and, provided you can express them, properties). In effect, you're parametrizing your program by the structure of the data it manipulates. The paradigm is called in some places bounded polymorphism, datatype-generic programming, ... which reflects that languages have different notions of how to implement that idea — hence the italicized 'sort of' above.

• For C++, it seems that —to Stepanov at least— this corresponds to templates (though ideas on how to do this best are still evolving).
• For OO languages (Generic Java, C#), constraints on type parameters are typically expressed using subtype bounds ('bounded wildcards' ...).
• For Haskell or Scala, you have (respectively, and similarly) type classes or implicits.
• The ML family of languages prefers to do this using modules.
• note that a number of proof assistants (which can express 'honest-to-god' properties as types) have developed a flavor of type classes : Isabelle, Coq, Matita are such examples

Note that Stepanov just co-wrote an entire book giving an exhaustive development of a library that embodies exactly what (I think) he means. So if you want examples in C++, this is definitely where you should look. Note also that this is much more evolved than the now-common advice of coding against an interface, rather than an object.

By 'practical example', I don't know if you mean 'how' or 'why' does one uses it. To give a caricaturally quick answer to the 'why', genericity is nice because, a bit like run-of-the-mill polymorphism, it lets you reuse code. But, more importantly:

1. polymorphic code that has to work with every single type often can't do anything interesting, whereas having a constrained interface to play with allows you to write richer programs

2. by specifying how that interface fits some your data, you have a type-safe way to select just those elements that suit your needs. For example, you probably know that the reduction operator (the reduce of Python & Hadoop, fold of a bunch of functional languages) is parallelizable only if the order in which you apply your reduction function doesn't matter (+, x, min, and work, but set difference doesn't). If you have a notion of 'type equipped with an associative operation', you know that you will be able to call a parallel reduction on it.

3. any overhead incurred by genericity occurs at compile time. For example, templates are legendarily fast

If you have seen some generic Java, look at say, the Comparable generic interface. It defines just one operation, but the contract it makes, though basic, is very much of algebraic flavor. I quote:

For the mathematically inclined, the relation that defines the natural ordering on a given class C is:

  {(x, y) such that x.compareTo((Object)y) <= 0}. 

The quotient for this total order is:

  {(x, y) such that x.compareTo((Object)y) == 0}. 

It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, > and that the natural ordering is a total order on C.

Now, I can write a method that selects the minimum, once, and use it for any type that fits this interface:

 public static <T extends Comparable<T>> T min (T x, T y) {    if (x.compare(y) < 0) x; else y;  } 

Naturally, since the way programmative constructs implement that notion varies wildly, what you will get in terms of usability & expressivity will also vary. Perhaps you should not judge data-generic programming just by OO languages like C++ or Java ­— but I've written too much already to start with module ascription or the automatic instance generation of type classes.