Higher-order type constructor polymorphism vs./and template style specialization

I'm wondering if there are language implementations that (elegantly?) combine what Scala (at least) refers to as "higher-order type constructor polymorphism" with the code specialization capabilities of C++ style templates?

I don't mean the notion of "specialization" sometimes used to generically describe how instantiating a template List[int] will (likely) generate new code.

I mean programmer driven template specialization.

That's pretty much the question, so now I'll make a fool of myself trying to come up with an example.

class Vector[T](size:int, init:T) extends Sequence[T]
with Indexed[T]
with Iterable[T, Vector[X]]
/* stuff */

So Iterable, say, has methods like map and friends that will now return Vector[U] for some function (T => U). And all the Iterator and Builder machinery comes out nicely typed. Yada yada yada.

Now, it would be *really* nice to somehow be able to implement bit vectors with custom code. Making up a silly keyword:

specialize class Vector[Bool](....
/* Do NOT want to use the normal machinery here. */

We don't really want a vector of 32 bit Bool values! We want some custom bitwise code over an array of bytes or unsigned ints or something. We'll also need specialized Iterators[Vector[Bool]] (hopefully inlined) and associated machinery.

But in the end we get a usable bit vector class (1) with much better space/speed for Vector[Bool] and (2) we can still write code like this.

def somefun(vi:Vector[Int]): Vector[Bool] = vi.map((_ % 2 == 0));

Just a dumb and obvious example. We could also inquire about method (or function) specializations on values yada yada yada.

Hence my question - are there language implementations that nicely combine their elegant type systems with the power of template style code specialization?

Sorry if this is too implementation oriented a question.


Comment viewing options

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

Don't know.

I don't think it's too implementation-oriented. In fact I think it's a very good question for LtU, but I don't know the answer. If I had to cast it in slightly more theoretical terms, it sounds like you're looking for ways to combine parametric and ad hoc polymorphism, or to add specialization without breaking parametricity.

The most relevant thing I can find in less than one minute is this POPL'08 paper by Vytiniotis and Weirich: Type-safe cast does no harm. I don't know how relevant it really is, and anyway I'm sure there is plenty of other stuff.


I should have added, of course, that Haskell is probably the best place to look for this capability, but it won't look much like the OO style you suggested. I don't know of anything that looks more like the OO style of C++ or Scala.

There are type systems...

...that do this cleanly, but I don't think any of them have hit the mainstream yet. Put in type-theoretic language, what you're asking for is the ability to do computation based on constructor-level data, both to come up with types based on this data, and to come up with terms inhabiting those types. This is an entirely sensible thing to ask for, both theoretically and pragmatically -- via Curry-Howard, this is basically asking for the type system to become a predicate logic, so it's both feasible and logically clean. It's just that the implementations aren't there yet.

If you want to get a sense of what this sort of programming might be like, you can download Sheard et al's Omega language. It's very much a research prototype, though.

Type-Indexed definitions

Mh, I don't think this requires something as advanced. AFAICS, template specialisation basically is an ad-hoc form of type-indexed definition. Various forms of those are available in Haskell implementations today.

I agree

Or at least, this is more the kind of thing I had in mind.