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.
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.
// 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.
// 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);
}
}
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?)
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);
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"
};
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»;
}
View and comment on this post in the fediverse, or email me about it.