[LLVMdev] Parametric polymorphism

[DeLesley Hutchins]

>> How difficult would it be to add such a capability to llvm?  I was thinking
>> of marking type variables like T as opaque types for the initial codegen,
>> and then writing a custom pass that instantiates them to real types.
>> However, I don't know if that would confuse or break other parts of the
>> compiler infrastructure; parametric polymorphism is not necessarily a
>> trivial modification.
>
> What complications do you forsee?

The biggest change is that every type can suddenly contain type
variables.  That could possibly confuse anything that happens to be
looking at the types, which I assume is almost every compiler pass.
I'm not familiar with llvm internals, so I don't have a good sense
of the scale of the change.

>> Is anyone on this list familiar with System F, System F_sub, or System
>> F^\omega_sub?... Pick one, plug it into llvm, and you have a type
>> system that can compete with the JVM or .NET in terms of functionality,
>> without being OOP centric or sacrificing language neutrality.  (System F is
>> low-level -- OOP can be easily implemented on top of it).
>
> Sounds like a dream come true. Where's the catch? ;-)

As far as I'm concerned, there is no catch, aside from the work
required to make it happen.  The biggest technical problem is that
type specialization can be implemented in a couple of different ways,
and there are different time/space tradeoffs for each technique.
System F_omega tells you how to do type-checking with parameterized
types; it doesn't tell you how to generate efficient code.

If the actual specialization was encapsulated within a separate pass,
then different languages could use whatever technique was most
appropriate.  Unfortunately, different techniques are not binary
compatible, so that would make it hard to design a universal type
system.  :-(

 -DeLesley