[LLVMdev] Parametric polymorphism

[DeLesley SpamBox]

> I think the problem is deeper than that, in that LLVM has no official
> concept of a subtype, so I don't see how the idea of polymorphism
> could be defined in it.

Parametric polymorphism is different from subtype polymorphism; you
can have one without the other.  Parametric polymorphism just means
that you can use type variables (like T) in the IR, which are later
instantiated
to actual types.

>> max <T extends Comparable>(T a, T b) {
>>  if (a > b) return a; else return b;
>> }
>>
>
> Also, "Comparable" implies some kind of function associated with the
> type in order to actually perform it...

True, but I'm not worried about that; method tables are easy to add once type
substitutions are allowed.  Dropping down to a mythical low-level language
that I call template C, we would have:

  struct ComparableDict<T> {
    bool (*equals)(T a, T b);
    bool (*leq)(T a, T b);
    bool (*geq)(T a, T b);
  }

  T max<T>(ComparableDict<T>* dict, T a, T b) {
    if ((*dict->geq)(a,b)) return a; else return b;
  }

This mechanism duplicates the dictionary-passing used in Haskell type classes.
The correct dictionary for any given type is inferred by the
high-level language, but
it is passed as an argument at the llvm level.

Notice that there is no subtyping.  The only things I need from llvm are:

(1) The ability to define a parameterized type, e.g. ComparableDict<T>.
(2) The ability to define a function that is parameterized by a type,
e.g. max<T>.
(3) The ability to substitute a type for a type variable, e.g. specialize max
     to max<int>.

In order to get good performance, you will need to instantiate max
with both a type
T, and the dictionary for T.  In other words, max must be partially
evaluated with
respect to a given type -and- a given dictionary.  While this is
obviously a complication,
partial evaluation with respect to constant arguments is something that llvm is
already quite capable of.  If there is not a pass that does it
already, I could easily write
one.  The problem is that I have no way of declaring a parameterized type or a
parameterized function within the llvm IR.

Note also that when I talk about ``types'', I am referring to
low-level llvm types --
scalars, records, pointers, etc.  I'm not referring to complex
functional types with pattern
matching as found in Haskell, or complex OOP classes as found in JVM
or .NET with
constructors, methods, and all that jazz.

  -DeLesley