Higher order polymorphism + value types

Question

I've read somewhere that the higher order polymorphism cannot be used/implemented in the type systems with the value types (like .NET). Is it right and why?

Answer 1

The problem is with the value representation.

Traditional higher-order polymorphism languages have made the simplifying choice that all values are represented in an uniform way, usually a single word, with some clever tagging to indicate if it's an immediate integer or a pointer to a structure with a common representation (some tag, etc.) for all other values such as data structures or functions.

If you have this assumption, you can compile each polymorphic function once, and use it on all arguments of all types : they have the representation assumed by the compiled function.

Now say you throw types with other representations, eg. several continuous words on the stack. You cannot use your single compiled function anymore, because it will expect a single word, so the calling convention is not right. Something is broken.

This can be fixed in various ways, such as :

• pass along with the values some information about their representation (you could consider this information to be a sort of runtime "type" information, but in fact you don't need the full type information, just some information about representation); this is what the TILT compiler has explored for example

• try to compile several specialized versions of your polymorphic function for each possible representation, then decide (also based on a tag of sorts, or some statically-available information) which version to call. This could be reasonable with a whole-program optimisztion scheme such as MLton's. This is more or less a caller-choice (rather than callee-choice) version of the first idea.

• restrict polymorphisms using a kind system to distinguish "one-word types", "tuple types". Instead of the usual polymorphism "for all type", you would have a relativized version "for all types of such kind ...". This allows the programmer to reason statically about which function can accept which type of arguments ("ow, this function is polymorphic, so I must box my value type here") instead of hoping that the compiler will get the coercions right, but this also makes the type system heavier: you don't preserve the illusion of uniformity.

In short, combined (some form of) polymorphism with rich data representation choices is possible, but much harder than in the uniform representation case.