Type-erased generic functions for C: A modest non-proposal
Earlier this year, I read Martin Uecker's proposal N3212 to add parametric polymorphism to C. It's easy to scoff at the idea of adding generic programming to plain C, when C++ already has templates, and nearly every modern systems language has some form of generic programming support, but it got me thinking there is an opportunity to do something meaningfully and usefully different from those other languages. C++ templates rely on monomorphization, meaning that when you write a generic function or type, the compiler generates a distinct specialization for every set of types you use it with. Most other systems-ish languages follow C++'s lead, because monomorphization allows each specialization to be individually emitted and optimized specifically for the set of types it's instantiated on, and the resulting specializations don't need any runtime support to handle different types. However, monomorphization also implies a much more complicated compilation and linking model, where the source code (or some intermediate representation thereof) of generic definitions has to be consistently available to the compiler in order to generate new instantiations as needed.
Although C is not really the "portable assembly language" many want it to be, one function definition in C generally leads to one symbol in an object file, and having access to function bodies after they've been compiled once is unnecessary (although helpful for optimization), and it would be good to retain these properties. A less-trodden path for implementing parametric polymorphism in systems-ish languages, used by Swift and also proposed here in N3212, is to use runtime metadata to handle generic types dynamically. N3212 proposes a new _Type primitive type, which carries some metadata about a type's size and other properties, so that other values can be declared with the type represented by that _Type using the _Var specifier:
void sort(_Type T, size_t N, _Var(T) array[N],
int (*compare)(const _Var(T)*, const _Var(T)*))
{
qsort(array, N, sizeof(_Var(T)), compare);
}
One challenge specifying a language-integrated metadata system is that it needs to provide enough information to serve any possible use that the language supports, even if a particular interface only needs a subset of that metadata. A traditional qsort function only needs the size of the elements to do its work, but other generic functions might want to know a type's alignment, its name, how values of the type interact with the function calling convention, the specifier to use in printf, and so on. The vast body of existing C code uses all sorts of different idioms for ad-hoc polymorphic interfaces, so a language design that prescribes a single metadata mechanism is going to have a tough time finding a balance between providing enough metadata to support a wide range of use cases and not bloating code generation with too much metadata that most clients don't need.
So that's why I'd like to explore a third approach that has the potential to be simpler to understand and implement, more flexible, and I think more in the subjective "spirit of C" than C++ style monomorphization or the proposed N3212 design. I think the combination of type-erased generics, paired with a default argument mechanism to collect situationally-appropriate metadata at call sites, could provide a surprising amount of expressivity, allow for better type checking to be retrofitted to existing C interfaces.
Disclaimer
To be up front, my language designer duties are focused elsewhere, and I'm not going to formally propose this to the C working group any time soon. As such, I'm only going to describe the broad strokes of a design direction here without working out all the details. I'm strictly in "ideas guy" mode here. If you want to stop reading, that's fine. But if it inspires you to actually implement and/or propose something like this, then great!You might also ask, why spend so much time thinking about big new features for C? Isn't C illegal now anyway? Well, I also think it'd be generally good to see more systems languages that don't fall into the well-worn monomorphization rut. Maybe these thoughts will inspire an ambitious systems language designer to try something different.
Generic functions
In order for a single compiled version of a generic function to work with any input type, without needing any predefined runtime metadata about that type, then the function can't do anything that depends on the concrete layout of a specific type. C already has incomplete types, which are similar; you can forward-declare a struct or union, and the forward-declared type can be used as the pointee type of pointers, but not directly as the type of a variable or function parameter. As a starting point, we can say that generic type parameters also behave like incomplete types:// T can appear as the pointee of a pointer, be cv-qualified, … void good_generic«T»(const T *a, T *b); // …but can't appear as a parameter type by itself void bad_generic«T»(T a); // error; incomplete generic type TIt may not seem like you'd be able to do much in a generic function in this world, since you can't directly do anything with the value of an incomplete type. However, by passing function pointers with matching pointer argument types down along with a pointer, you can make useful generic functions:
// Traverse a list, given operations to visit each node in the list
// and to advance to the next node
void each_node«Node»(Node *head,
Node *(*next)(Node *),
void (*body)(Node *)) {
for (Node *node = head; node; node = next(node)) {
body(node);
}
}
struct int_node {
struct int_node *next;
int value;
};
struct int_node *next_int_node(struct int_node *node) {
return node->next;
}
void print_int_node(struct int_node *node) {
printf("%d\n", node->value);
}
int main() {
struct int_node list[] = {
{ .next = &list[1], .value = 1 },
{ .next = &list[2], .value = 2 },
{ .next = &list[3], .value = 3 },
{ .next = &list[4], .value = 5 },
{ .next = NULL, .value = 8 },
};
each_node«struct int_node»(&list[0], next_int_node, print_int_node);
}
This is akin to passing a vtable for a generic interface (or a "witness table" as Swift calls them), but entirely under the program's control to indicate what's in that vtable.
Default arguments for gathering type metadata
To do much else with a generic value or data structure, you need more metadata about the type. To operate on an array or other data structure of some unknown element type, you generally need to know at least the size and possibly alignment of the elements. Needing to explicitly pass large bundles of metadata at every call site will get tedious, and it'd also undermine the safety benefits of generics, since callers could easily pass the "wrong" metadata. If a generic function declaration could specify default arguments, that could provide a mechanism for automatically collecting relevant metadata from call sites:// Reduce the values in an array
void reduce«T»(T *out, const T *array, size_t count,
void (*sum)(T *out, const T *element),
size_t element_size = sizeof(T)) {
unsigned i;
const T *element;
for (i = 0, element = array;
i < count;
++i, element = (const T*)((const char *)T + element_size)) {
sum(out, element);
}
}
void sum_int(int *out, const int *value) {
out += value;
}
int main() {
int values[] = {0, 1, 1, 2, 3, 5, 8, 13};
int sum = 0;
// call site implicitly passes element_size = sizeof(int)
reduce«int»(&sum, values, sizeof(values)/sizeof(int), sum_int);
printf("%d\n", sum);
}
(Having to manually advance the element pointer in the reduce loop by casting to char* and back is kinda gross, so maybe there should be a way to associate a size expression with a generic type, just so pointer arithmetic works:)
// Declaring a generic parameter as T[size_expr] expresses that
// sizeof(T) == size_expr
void reduce«T[element_size]»(T *out, const T *array, size_t count,
void (*sum)(T *out, const T *element),
size_t element_size = sizeof(T)) {
unsigned i;
const T *element;
for (i = 0, element = array;
i < count;
// We can use normal pointer arithmetic on a T* if T has a
// size expression
++i, ++element) {
sum(out, element);
}
}
Retrofitting generics onto existing functions
With these two features, we already have enough to retrofit some existing common C functions to take advantage of generics. N3212 uses sorting as a motivating example, and demonstrates a new sort interface as an alternative to the traditional qsort standard library function. But let's see if we can upgrade the existing qsort in place without breaking compatibility with existing C. qsort's traditional prototype looks something like:void qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
where base is a pointer to the first element in an array, nel is the number of elements in the array, width is the size of an element, and compar is a three-way comparison function that returns whether the first pointed-to element is considered less than, equal, or greater than the second. We could change this to:
void qsort«T[width]»(T *base, size_t nel, size_t width = sizeof(T),
int (*compar)(const T *, const T *));
Since the generic type declaration itself has no runtime effect, it doesn't need to have any effect on the calling convention of qsort. And we're still passing pointers in all the same places we were passing pointers before. However, one concession to tradition is that the width parameter ought to default to sizeof(T), but it's not the final argument to qsort, so if we follow C++'s default argument rules, this wouldn't be allowed. But we could loosen that restriction, and allow any argument to be defaulted at a generic call site:
int compare_ints(const int *a, const int *b) {
return a - b;
}
int main() {
int array[] = {0, 1, 1, 13, 2, 21, 3, 34, 5, 8};
qsort«int»(array, sizeof(array)/sizeof(int), /*default*/,
compare_ints);
}
To allow existing C code to continue to call qsort after its retroactive genericization, we could say that calling a generic function without generic arguments devolves those arguments back to void. Default arguments that depend on the generic parameters aren't available at a nongeneric call site, and the caller has to be supply an argument manually. Backward compatibility aside, this would also be useful as a way to get back into generic code using runtime metadata that's been stored in a way that can't be statically reasoned about. (Of course, this is also an easy way to escape type safety, though C is full of those already… maybe there should be a more opt-in way to do so?)
Generic structs
User-defined types could also be parameterized, with the same constraint as function parameters that the type parameters act like incomplete types and can't influence the layout of the type. A generic struct can package up methods and information about a type into a single value. For instance, to support a generic hash table implementation, we might need to know the size and alignment of keys, as well as how to hash a key and compare it for equality with another key. This is another place where defaults are helpful to capture information about a type that the compiler can automatically fill in:struct hashable«Key» {
size_t size = sizeof(Key), alignment = alignof(Key);
uint64_t hash(const Key *value);
bool equal(const Key *a, const Key *b);
};
const struct hashable«int» int_hashable = {
.hash = int_hash,
.equal = int_equal,
};
Incomplete types can also usefully carry generic parameters, to provide some type safety at an interface boundary:
struct hash_table«Key, Value»;
struct hash_table«Key, Value» *hash_table_alloc«Key, Value»( size_t initial_buckets, const struct hashable«Key» *key_type, size_t value_size = sizeof(Value), size_t value_alignment = alignof(Value));
void hash_table_insert«Key, Value»( struct hash_table«Key, Value» *hash, const Key *key, const Value *value);
const Value *hash_table_find«Key, Value»( struct hash_table«Key, Value» *hash, const Key *key);
Generic unions and enums
Enums and unions are interesting because they represent alternatives. Borrowing an idea from GADTs in functional languages, we can say that an enum or union can not only be generic, but also restrict some or all of its members to be available only for specific generic parameters. Among other things, this could allow for more type-safe tagged unions:enum json_tag«T» {
null«struct null»,
boolean«bool»,
number«double»,
string«const char *»,
array«struct json_array»,
object«struct json_object»,
};
struct json«T» {
enum json_tag«T» tag;
union {
struct null null«struct null»;
bool boolean«bool»;
double number«double»;
const char *string«const char *»;
struct json_array array«struct json_array»;
struct json_object object«struct json_object»;
};
};
struct json«double» zero = { .tag = number, .number = 0.0 };
struct json«const char *» greeting = {
.tag = string,
.string = "hello world"
};
struct json«double» bad_number = {
// error, enum constant 'null' has type 'json_tag«struct null»', not
// 'json_tag«double»'
.tag = null,
// error, union field 'string' has type '(anonymous union)«const char *»'
.string = "0.0"
};
Parameterized globals?
The default argument mechanism works well for populating metadata parameters from builtin operations like sizeof and alignof, but C as it exists today doesn't provide a way to make open, user-defined associations between types and values. (_Generic does exist, but any one `_Generic expression can only cover a closed set of type alternatives.) The hash table example above demonstrates this:struct hash_table«Key, Value» *hash_table_alloc«Key, Value»( size_t initial_buckets, const struct hashable«Key» *key_type, size_t value_size = sizeof(Value), size_t value_alignment = alignof(Value));The Value's size and alignment can be prepopulated using sizeof and alignof, but there isn't a good way to default the key_type parameter to a canonical hashable struct for a given type (aside from maybe using _Generic for a closed set of types). C++-style template specialization is probably not a great idea, since it makes type checking dependent on template instantiation, but one possible design might be to allow a global variable name to be declared as being parametric:
// Declare a compound name _Generic const struct hashable«T» hashable_impl«T»;This wouldn't define any actual global variable itself, but would allow for definitions to be provided for specific types:
// Provide definitions for some common types:
const struct hashable«int» hashable_impl«int» = { ... };
const struct hashable«bool» hashable_impl«bool» = { ... };
const struct hashable«void *» hashable_impl«void *» = { ... };
Other than the common name, each individual global variable definition would behave like an independent variable definition. Trying to access a parametric name for which no definition is visible would be an error:
auto *hashable_char = &hashable_impl«char»; // error, no such definition
const struct hashable«char» hashable_impl«char» = { ... };
auto *hashable_char = &hashable_impl«char»; // OK
but this would give us the open association we need to provide a nice default for our hash table API:
struct hash_table«Key, Value» *hash_table_alloc«Key, Value»( size_t initial_buckets, const struct hashable«Key» *key_type = &hashable_impl«Key», size_t value_size = sizeof(Value), size_t value_alignment = alignof(Value));However, we're still type-erasing everything, so there's no dynamic lookup structure to recover this association at runtime. That would mean that you would not be able to refer to a parametric global generically, which might be weird:
const struct hashable«T» *get_hashable_impl«T»(void) {
// error, can't look up hashable_impl for a generic type T
return &hashable_impl«T»;
}