Generic types

Looking to write a language that combines primitive and object types with a prototypic approach ala Self, I am struggling to understand how to implement generic types. I read the GNAT Ada interface implementation document but did not see material directly related to this.

My concerns are:

  • Adjust the size of the object to the parameterized type(s)
  • Adjust the methods code to the parameterized type(s)
  • Compare instantiated generic types for compatibility (eg. two instances of the type with covariant method parameters)

In particular, how do languages that support generic types handle the second point?

Comment viewing options

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

Templates or Boxing or Tagged References

I don't know how Ada handles parametric polymorphism. C++ uses templates from which the compiler generates specialized code. So a List<int> generates one class and a List<double> generates a different class. It's almost exactly as if you had hand written a specialized List_int and a specialized List_double. Each such variation of List is statically compiled and linked in C++.

Sticking with the List example, many other languages with parametric polymorphism (e.g. Java) will use boxing to handle simple "primitives" like int and double, so as far as memory layout is concerned there would only be one List construct: List of references/pointers. The type system will then ensure that different types of List are treated appropriately. Depending on the language, the runtime may also treat them differently by tagging each instance of List with its parameter type. Boxing and unboxing are generally handled automatically by the compiler.

Edit: I remembered belatedly a third option. In some Haskell and Scheme implementations (and probably others) a few bits out of each reference/pointer are designated as a tag to indicate if the value is in fact a pointer or if it's a directly captured primitive like an int. This cuts down on boxing overhead at the price of a few bits per reference. Otherwise it behaves a lot like the previous option.

Edit: fixed angle bracket issues

What happens when you

What happens when you have

let adder a b = a + b

The compiler makes a specialized version for integer right? Does it go through all known types that support + and make a preventive compilation? Or does it happen in JIT fashion from an intermediate bytecode?

C# uses partial

C# uses partial specialization based on data type shape. BitC, GNAT Ada, MLTon all use monomorphization, ie. full specialization, like C++.


I didn't know that about C#. I dug around and found a paper on how its done in the CLR: Design and Implementation of Generics for the .NET Common Language Runtime.