How are generics implemented in a modern compiler?

Question

What I mean here is how do we go from some template T add(T a, T b) ... into the generated code? I've thought of a few ways to achieve this, we store the generic function in an AST as Function_Node and then each time we use it we store in the original function node a copy of itself with all of the types T substituted with the types that are being used. For example add<int>(5, 6) will store a copy of the generic function for add and substitute all types T in the copy with int.

So it would look something like:

struct Function_Node {
    std::string name; // etc.
    Type return_type;
    std::vector<std::pair<Type, std::string>> arguments;
    std::vector<Function_Node> copies;
};

Then you could generate code for these and when you visit a Function_Node where the list of copies copies.size() > 0, you invoke visitFunction on all of the copies.

visitFunction(Function_Node& node) {
    if (node.copies.size() > 0) {
        for (auto& node : nodes.copies) {
            visitFunction(node);
        }
        // it's a generic function so we don't want
        // to emit code for this.
        return;
    }
}

Would this work out well? How do modern compilers approach this problem? I think perhaps another way to do this would be you could inject the copies into the AST so that it runs through all of the semantic phases. I also thought perhaps you could generate them in an immediate form like Rust's MIR or Swifts SIL for example.

My code is written in Java, the examples here are C++ because it's a bit less verbose for examples - but the principle is basically the same thing. Though there may be a few errors because it's just written out by hand in the question box.

Note that I mean modern compiler as in what is the best way to approach this problem. And when I say generics I don't mean like Java generics where they use type erasure.

Answer 1

How are generics implemented in a modern compiler?

I invite you to read the source code of a modern compiler if you wish to know how a modern compiler works. I'd start with the Roslyn project, which implements C# and Visual Basic compilers.

In particular I draw your attention to the code in the C# compiler which implements type symbols:

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Symbols

and you might also want to look at the code for convertibility rules. There is much there that pertains to the algebraic manipulation of generic types.

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Binder/Semantics/Conversions

I tried hard to make the latter easy to read.

I've thought of a few ways to achieve this, we store the generic function in an AST as Function_Node and then each time we use it we store in the original function node a copy of itself with all of the types T substituted with the types that are being used.

You are describing templates, not generics. C# and Visual Basic have actual generics in their type systems.

Briefly, they work like this.

• We begin by establishing rules for what formally constitutes a type at compile time. For example: int is a type, a type parameter T is a type, for any type X, the array type X[] is also a type, and so on.

• The rules for generics involve substitution. For example, class C with one type parameter is not a type. It's a pattern for making types. class C with one type parameter called T, under substitution with int for T is a type.

• Rules describing the relationships between types -- compatibility upon assignment, how to determine the type of an expression, and so on -- are designed and implemented in the compiler.

• A bytecode language that supports generic types in its metadata system is designed and implemented.

• At runtime the JIT compiler turns the bytecode into machine code; it is responsible for constructing the appropriate machine code given a generic specialization.

So for example, in C# when you say

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>(); 
c.X(123);

then the compiler verifies that in C<int>, the argument int is a valid substitution for T, and generates metadata and bytecode accordingly. At runtime, the jitter detects that a C<int> is being created for the first time and generates the appropriate machine code dynamically.

Answer 2

Most implementations of generics (or rather: parametric polymorphism) do use type erasure. This greatly simplifies the problem of compiling generic code, but only works for boxed types: since each argument is effectively an opaque pointer, we need a VTable or similar dispatch mechanism to perform operations on the arguments. In Java:

<T extends Addable> T add(T a, T b) { … }

can be compiled, type-checked, and called the same way as

Addable add(Addable a, Addable b) { … }

except that generics provide the type checker with far more information at the call site. This extra information can be handled with type variables, especially when generic types are inferred. During type checking, each generic type can be replaced with a variable, let's call it $T1:

$T1 add($T1 a, $T1 b)

The type variable is then updated with more facts as they become known, until it can be replaced with a concrete type. The type checking algorithm must be written in a way that accommodates these type variables even if they are not yet resolved to a complete type. In Java itself this can usually be done easily since the type of the arguments is often known before the type of the function call needs to be known. A notable exception is a lambda expression as function argument, which requires the use of such type variables.

Much later, an optimizer may generate specialized code for a certain set of arguments, this would then effectively be a kind of inlining.

A VTable for generic-typed arguments can be avoided if the generic function does not perform any operations on the type, but only passes them to another function. E.g. the Haskell function call :: (a -> b) -> a -> b; call f x = f x would not have to box the x argument. However, this does requires a calling convention that can pass through values without knowing their size, which essentially restricts it to pointers anyway.

---

C++ is very different from most languages in this respect. A templated class or function (I'll only discuss templated functions here) is not callable in itself. Instead, templates should be understood as a compile-time meta-function that returns an an actual function. Ignoring template argument inference for a moment, the general approach then boils down to these steps:

1. Apply the template to the provided template arguments. E.g calling template<class T> T add(T a, T b) { … } as add<int>(1, 2) would give us the actual function int __add__T_int(int a, int b) (or whatever name-mangling approach is used).

2. If code for that function has already been generated in the current compilation unit, continue. Otherwise, generate the code as if a function int __add__T_int(int a, int b) { … } had been written in the source code. This involves replacing all occurrences of the template argument with its values. This is probably a AST→AST transformation. Then, perform type checking on the generated AST.

3. Compile the call as if the source code had been __add__T_int(1, 2).

Note that C++ templates have a complex interaction with the overload resolution mechanism, which I do not want to describe here. Also note that this code-generation makes it impossible to have a templated method that is also virtual – a type-erasure based approach does not suffer from this substantial restriction.

---

What does this mean for your compiler and/or language? You have to think carefully about the kind of generics you want to offer. Type erasure in the absence of type inference is the simplest possible approach if you support boxed types. Template specialization is seems fairly simple, but usually involves name mangling and (for multiple compilation units) substantial duplication in the output, since templates are instantiated at the call site, not the definition site.

The approach you have shown is essentially a C++-like template approach. However, you store the specialized/instantiated templates as “versions” of the main template. This is misleading: they are not the same conceptually, and different instantiations of a function can have wildly different types. This will complicate things in the long run if you also allow function overloading. Instead, you would need a notion of an overload set that contains all possible functions and templates that share a name. Except for resolving overloading, you can consider different instantiated templates to be completely separate from each other.