"Archetype by prototype": a suggestion for making compile-time polymorphism more usable

A recent post on interface matching in ParaSail (a new parallel programming language under development) inspired me to think about compile-time polymorphism in languages like C++.  The author of the article observed that "C++ templates define essentially no 'contract' so there is no easy way to find out what sort of type will be acceptable without trying the instantiation." 

This stirred me to think about what C++ programmers can (and do) do to get around this.  A standard technique is to use "concept checks."  These test the required syntax by, well, trying the instantiation ;-) in a way that makes it easy to catch syntax errors.  They can be tedious, because doing them right requires two things:

1. Concept checking code, that verifies the interface statically and as simply as possible (so that compiler error messages are easier to read)

2. An "archetype class": like a Java interface, except with (skeletal) implementations of the required interface

In the above, i'm using the terminology of the Boost Concept Check Library.  #1 alone adds to the code maintenance burden, since as the "contract" evolves, you have to synchronize the checks with how you are actually using the object.  #2 alone doesn't ensure synchronization of your idea of the contract, with the classes you think are implementing it.  Nevertheless, there are still four separate bodies of code to synchronize: the archetype class, the concept checking code, the application class(es), and the application code that invokes these class(es).  The most straightforward (but not easiest) way to avoid this burden would be to

1. Write an archetype class, and make the compiler check the concept, using application code



I call this approach "declared archetypes."  It calls for a syntax for declaring that a particular concrete data type implements an archetype's interface.  This approach has implications for avoiding error-prone tedium.  A common case for templates is generic code for different kinds of numbers.  I've written a lot of code templated on "Scalar", which could be anything representing a real or complex number, and Ordinal, which represents an array index type.  It would be tedious to declare an archetype supporting all the different kinds of things one might like to do with a Scalar, for example.  It would at least have to include all of arithmetic, and all kinds of transcendental functions (such as trigonometric functions and logarithms).  That would be an awful lot of effort, especially since most people are only going to instantiate Scalar with "float" or "double".  (A few unlucky folks will make Scalar a complex number and discover all the places where the supposedly generic code was using less-than on Scalar!)

To avoid this tedium, the "concepts" proposal considered for addition to the C++ standard (but rejected) offered a shorthand for "aggregate archetypes."  You could say that Scalar is "FloatingPointLike" or that Ordinal is "SignedIntegralLike", and that would hopefully bring in the syntax that you want.  You could also "inherit" from archetypes to create your own.

The trouble with this approach is that somebody has to write a huge library of arbitrarily named predefined archetypes.  Huge, because pretty much anything you might want to do with a "plain old data" type has to have its own concept.  Arbitrarily named, because somebody has to decide what "ArithmeticLike" means.  (Does it mean integers or real numbers?)  This path seems to call for abstract algebra, where you have semigroups and rings and fields of a certain characteristic, and all kinds of things that nonmathematicians don't want to understand.  (I'm convinced the main reason why people don't use Haskell more is because it's so hard to explain what a monad is, and why you want to know.) 

This is overkill because in most cases, programmers can accomplish their work without so much formality.  The ParaSail blog post alludes to the reason why:  "... when ad hoc matching is used, there is a presumption that the module formal (or target type) is very stable and new operations are not expected to be added to it."  The typical use case of C++ templates (for example) is for things that "look like double" or "look like int."  That suggests a second approach:

2. "Archetype by prototype" or "looks like type T"

If T is something simple like "double" or "int", then you save a lot of syntax and / or library writing.  If T is complicated, this forces you to write an archetype class, which is probably a good thing if T is complicated!  For the numerical linear algebra algorithms i write and maintain, this would help remind me whether an algorithm (that claims to be generic on a Scalar type) can handle complex numbers.  (Complex arithmetic changes linear algebra in subtle ways that don't only have to do with syntax.) 

This approach does not require special syntax for defining archetypes.  However, it might still be nice to have such a syntax, and also to have a small library of archetype classes.  I could see this being useful for iterators, for example.

"Archetype by prototype" would impose requirements "lazily," much like users of C++ template metaprogramming expect.  The "actual archetype" would consist only of those operations with the concrete datatype that are actually written in code.  For example, if you never ask for the cosine of a Scalar, you don't need to have an implementation of cosine that takes a Scalar argument.  It would be nice to have some development environment support for "extracting" the "actual archetype."  C++ compilers do some of this already in their error messages, if you have the patience to read them (after about a page of compiler backtrace, you get something like "no implementation of cos(Scalar) exists for Scalar = YourType").

In summary, i propose "archetype by prototype" as an alternative to "concepts" for making compile-time polymorphism more usable.