How to transpile generic functions into language that do not support generics?

Question

Currently, I am developing a transpiler for my own language, however, I find difficulties to transpile generic functions. For example, how would you translate the following Java-like code in to C?

interface Comparable<T> {
    boolean compare(T that);
}

class Person implements Comprable<Person> {
    public string name;
    public boolean compare(Person that) {
        return this.name.compareTo(that.name);
    }
}

// The generic function
<T extends Comparable<T>> boolean isSorted(T[] xs) {
    for(int i = 1; i < xs.length(); i++) 
        if(xs[i-1].compare(xs[i]) > 0) 
            return false
    return true
}

My current solution is to use Javascript prototypes. So, the code above would be translated into the following Javascript (workable in Google Chrome):

class Person { }

Person.prototype.compare = function (that) {
    return this.name.localeCompare(that.name);
}

function isSorted(xs) {
    for (var i = 1; i < xs.length; i++) 
        if(xs[i-1].compare(xs[i]) > 0) 
            return false;

    return true;
}

However, Javascript prototype suffers performance issue (I tested it myself), so I am looking for other ways to translate generics without using prototypes. That is why I'm looking for example on how to translate that into pure C.

Note: You might also translate it to any language you like, as long as you did not use generics.

Answer 1

When compiling to a target language without generics, there are two main strategies.

1. Monomorphization: if you have a generic function, and it's instantiated with types $T_1\ldots T_n$ throughout your program, you make $n$ copies of the function, with the concrete type replacing the generic variable. This tends to result in fast but large code, since there's lots of duplication.

2. Boxing: you can "box" the generic variables behind some sort of reference type, and cast to and from this type when entering and exiting your generic function. The guarantees of the source language ensure that these casts are always safe. For example, in C you probably want to use void*.

If you're looking for resources, generics are known as "parametric polymorphism" in the Programming Languages literature, so that might help your search.

If you're compiling from a Java-like OO language, you'll also need to attach a VTable to your objects: a table of pointers to their methods, you get Java's dynamic dispatch (i.e. the method of an object depends only on its runtime type, not it's compile-time type).

Having "bounded polymorphism" with option 2 (i.e. the T extends Comparable<T>makes this a little more tricky, since you need to come up with some sort of boxed representation that lets you find your Comparable methods. You could do a dynamic lookup to find such methods, but this is slow. I'd search around for how to compile bounded polymorphism, you'll probably find a better answer.