5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You may be surprised to find out that the JVM doesn't support generics! Actually most generic information is removed by the Java compiler. $\endgroup$ – immibis Nov 20 '18 at 4:37
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Monomorphization seems like a good choice, but would it work for recursive generic function also? $\endgroup$ – Wong Jia Hau Jul 13 '18 at 11:57
  • $\begingroup$ Yes, I don't see why it wouldn't. $\endgroup$ – jmite Jul 13 '18 at 12:02
  • $\begingroup$ Noted. By the way would you mind to explain the drawbacks of using monomorphization instead of dynamic boxing, despite the code duplication issue? $\endgroup$ – Wong Jia Hau Jul 13 '18 at 12:07
  • 1
    $\begingroup$ @WongJiaHau I think that's the main drawback. It's a popular enough technique that it's what C++ and Rust use for their generics. $\endgroup$ – jmite Jul 13 '18 at 15:09
  • $\begingroup$ Then, what is the advantage of using boxing compare to monomorphization? (Let's not talk about Java's erasure, perhaps about C# generics) $\endgroup$ – Wong Jia Hau Jul 13 '18 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.