3

I'm developing a language like Vala and OOC that compiles back to C.

This means that, eventually, every feature needs to be adoptable to C code in some way or another. Generics is one of the features I'd like to implement in my language.

As you probably know, C is a strictly typed language. Except for the opaque void pointer, there is no way to pass an argument of a unknown type. This is because the compiler needs to know the exact size of the argument passed or returned.

The following solutions come to my mind:

  1. Boxing: Create a union that can store every possible type
  2. Pass a pointer to the parameter, rather than the parameter itself.

Both of these have their downsides:

    • The size of the generic type T will be equal to the largest possible type
    • The sizes are predetermined, a struct with a different size cannot be passed by value
    • Slower, because every argument has to be boxed/unboxed
    • The parameter is not copied onto the new stack scope
    • Memory management issues because of the above
    • Not the desired behaviour because of the above

I'm interested in knowing how I could adopt this high-level principle in a lower level language, and also how other high-level languages have conquered this problem.

EDIT

As @delnan has pointed out, another possibility is Monomorphization, creating a new function for every data type. This has a few of the same downsides:

  • The type T needs to be defined beforehand (not very generic)
  • The binary size gets larger (which, granted, isn't very relevant nowadays)
  • 1
    As an inspiration, have a look at Ada implementations. Ada can produce low-level code and has quite capable generics. Second, note that compiling to C from another language might complicate static type checking (you will probably have to know how C deals with types in your language). – coredump Nov 2 '14 at 15:48
9

Monomorphization. For every generic (polymorphic) type/function, generate a non-generic (monomorphic) version for every set of type parameters. Given these declarations:

struct G<T> {
  a: T,
  b: T
}

fn get_a<T>(g: G<T>) -> T {
  return g.a;
}

and this code:

x = G<int>(1, 2);
y = G<float>(1.0, 2.0);
get_a(x);
get_a(y);

Generate code equivalent to:

struct G_int {
  a: int,
  b: int
}

struct G_float {
  a: float,
  b: float
}

fn get_a_int(g: G_int) -> int {
  return g.a;
}

fn get_a_float(g: G_float) -> float {
  return g.a;
}

x = G_int(1, 2);
y = G_float(1.0, 2.0);
get_a_int(x);
get_a_float(y);

This also works across library barriers! It requires the code (at least in AST/IR form) of generics to be included with library binaries, but aside from that the compiler can simply generate the code in the same way, just taking the "template" from a different source. Duplicate definitions (when two libraries instantiate the same generic with the same type parameters) can be merged by the linker and at worst increase compile time.

  • Oh yes, I forgot about this one. This is how C++ does it. That one has a few of the same downsides though: Every type has to be predefined. In a library e.g. you can't know what types the user of your library is going to use. – NSAddict Nov 2 '14 at 14:16
  • @NSAddict Not at all, see my edit. – user7043 Nov 2 '14 at 14:23
  • Wait until you get the dreaded "Monomorphism Restriction" from the compiler because of type ambiguity... – recursion.ninja Nov 2 '14 at 15:06
  • @recursion.ninja The monomorphism restriction is a Haskell thing (in particular, a typeclass thing), only applies to top-level bindings without any parameters, and is not technically necessary (it can be turned off with the only consequence being possibly-slower code). Did you perhaps mean something else? – user7043 Nov 2 '14 at 15:12
  • @delnan It was meant as a joke; a reference to how Haskell implements generics through type-classes. – recursion.ninja Nov 2 '14 at 15:20
5

currently there are 2 ways;

  1. the type erasure method of java; essentially everything becomes a void* (or a custom type like a struct base{void** functptrs;} and gets casted to and fro as needed, this requires the type to follow a certain interface to let the template figure out if casts are valid at runtime.

  2. instantiation creates a new definition of the template like delnan explained; this is what is used in C++. It does cause some code bloat as you need to let the client recompile the template each time it is used.

  • 1
    C# does both ( type erasure for classes, instantiation for value types) so it's not a binary choice. – Pete Kirkham Nov 2 '14 at 14:38
  • @PeteKirkham C# doesn't use type erasure. Type information is persisted in run time. – Konrad Morawski Nov 2 '14 at 18:01
  • @KonradMorawski the specialisation is preserved in the reflected type information, but for generating code the behaviour is to erase the type - The first time a generic type is constructed with any reference type, the runtime creates a specialized generic type with object references substituted for the parameters in the MSIL. Then, every time that a constructed type is instantiated with a reference type as its parameter, regardless of what type it is, the runtime reuses the previously created specialized version ... msdn.microsoft.com/en-us/library/f4a6ta2h.aspx – Pete Kirkham Nov 3 '14 at 16:26
  • 1
    @PeteKirkham maybe it's my English, but to me it doesn't mean that type information is erased at all. Specialized generic type is created, and then it is reused. How could Stack<int> be ever reused if the <int> bit wasn't preserved? I'm tempted to post this as a question. – Konrad Morawski Nov 3 '14 at 20:51

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.