Right now rust uses monomorphization to compile polymorphic function and this has several drawbacks:
- Bloated binary size
- Unable to compile polymorphic recursions
- Unable to compile higher-order polymorphic functions
- Slows compilation
An alternative would be to erase all type information and box all the polymorphic arguments, but this will impose performance penalties and can slow down tight loops significantly.
Haskell distinguishes boxed (e.g.
Bool) and unboxed types (e.g.
Bool#) at the kind level (levity): boxed types (lifted types really, but we ignore the difference here) have the kind
# where unboxed types have the kind
Type. Distingusing boxed and unboxed types allow us to specialize polymorphic functions when needed, but it also requires us to generate different machine codes because of different calling conventions, write separate functions for boxed and unboxed types and causes other problems in the type system. This motivates us to abstract over levity with so-called levity polymorphism described in this paper.
Compiling polymorphic functions using type erasure has been proposed before, would it be possible to incorprate levity and levity polymorphism into rust? What are your thoughts?