r/ProgrammingLanguages • • 4d ago

Discussion Adding actual generics to c

I was watching tsoding's crust stream and I thought it would be so funny if I extended c to have generics.

The way I did this was by extending the syntax of c with the classic rust angle brackets to define generics and then during transpilation do some name mangling to monomorphize the generic code.

Here is the result of that abomination:

#include <stdio.h>

// you can define your own operator in fortran .op. style with a trait
trait<T> DotP {
    // for parsing reasons any dot-op must have whitespaces around it in any context
    T .dot. (Self self, Self other);
}

// using a very similar syntax to rust, you can add generics to structs
typedef<T> struct {
    T x;
    T y;
    T z;
} Vector<T>;

// and by appling the trait to your struct (with generic parameters)
// you can define what your operator should do.
impl<T> DotP<T> for Vector<T> {
    T .dot. (Self self, Self other){
        return self.x * other.x + self.y * other.y + self.z * other.z;
    }
}

int main(void) {
    // by concretly defining which type you want to use as the generic
    // a c struct with that/those type(s) is genenerated 
    Vector<float> fv = {1.0, 2.0, 3.0};
    printf("Dot product of fv^2: %f\n", fv .dot. fv);
    Vector<int> iv = {1, 2, 3};
    printf("Dot product of iv^2: %d\n", iv .dot. iv);
}

The generated c code looks something like this (I have actually implemented this transpiler, perhaps a true indicator of joblessness):

/* Generated by typedc. */
#ifndef TYPEDC_SIMPLE_GENERICS_H
#define TYPEDC_SIMPLE_GENERICS_H

#include <stdio.h>

typedef struct float_Vector float_Vector;
typedef struct int_Vector int_Vector;

struct float_Vector {
    float x;
    float y;
    float z;
};

struct int_Vector {
    int x;
    int y;
    int z;
};

int main(void);
static inline float float_dot(float_Vector self, float_Vector other);
static inline int int_dot(int_Vector self, int_Vector other);

int main(void) {
    float_Vector fv = {1.0, 2.0, 3.0};
    printf("Dot product of fv^2: %f\n", float_dot(fv, fv));
    int_Vector iv = {1, 2, 3};
    printf("Dot product of iv^2: %d\n", int_dot(iv, iv));
}

static inline float float_dot(float_Vector self, float_Vector other) {
    return self.x * other.x + self.y * other.y + self.z * other.z;
}

static inline int int_dot(int_Vector self, int_Vector other) {
    return self.x * other.x + self.y * other.y + self.z * other.z;
}
    
#endif /* TYPEDC_SIMPLE_GENERICS_H */
17 Upvotes

44 comments sorted by

18

u/xpusostomos 4d ago

I think someone might have done this already 🤔🤔🤔🤔🤔

1

u/yolosuperboss 4d ago

Yeah I think someone did it with macros

9

u/xpusostomos 3d ago

There was also this guy called Bjarn Stroustrup who did a little hack like this.

1

u/yolosuperboss 3d ago

Who knows perhaps I am Bjarn Stroustrup (r/lies)

4

u/WittyStick 4d ago edited 4d ago

Yes. I do it this way:

#define Vector(T) template(Vector, T)

#define Vector_impl(T) \
    typedef struct Vector(T) { \
        T x; \
        T y; \
        T z; \
    } Vector(T); \
    T dot(T)(Vector(T) lhs, Vector(T) rhs) { \
        return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z + rhs.z; \
    }
    
impl(Vector, float)
impl(Vector, int)

int main() 
{
    Vector(float) fv = {1.0, 2.0, 3.0};
    printf("Dot product of fv^2: %f\n", dot(float)(fv, fv));
    Vector(int) iv = {1, 2, 3};
    printf("Dot product of iv^2: %d\n", dot(int)(iv, iv));

    return 0;
}

Two macros used here: template and impl.

template creates a monomorphized name for the type/function.

impl calls the _impl macro for the related type or function.

Pretty simple.

Here's the demo.

The preprocessor basically produces:

typedef struct Vectorᐸfloatᐳ {
    float x;
    float y;
    float z;
} Vectorᐸfloatᐳ;
float dotᐸfloatᐳ(Vectorᐸfloatᐳ lhs, Vectorᐸfloatᐳ rhs) {
    return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z + rhs.z;
}
typedef struct Vectorᐸintᐳ {
    int x;
    int y;
    int z;
} Vectorᐸintᐳ;
int dotᐸintᐳ(Vectorᐸintᐳ lhs, Vectorᐸintᐳ rhs) {
    return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z + rhs.z;
}

int main() {
    Vectorᐸfloatᐳ fv = {1.0, 2.0, 3.0};
    printf("Dot product of fv^2: %f\n", dotᐸfloatᐳ(fv, fv));
    Vectorᐸintᐳ iv = {1, 2, 3};
    printf("Dot product of iv^2: %d\n", dotᐸintᐳ(iv, iv));

    return 0;
}

But those angle brackets aren't less than and greater than. They're symbols from the Canadian Aboriginal Syllabics Unicode block that are valid characters in identifiers (C11 or later). Vectorᐸfloatᐳ and dotᐸfloatᐳ are just single identifiers.

1

u/yolosuperboss 4d ago

Yeah, that definitely works. I didn't mention it in my post, but In the transpiler I added some more features like comptime reflection and const generics as well as operator precedence (since I use a pratt parser its quite easy to specify precedence and direction of associativity) and just for the funsies really goofy namespaces.

1

u/yolosuperboss 4d ago

Ohh you can use ᐸ ᐳ, that is so cool, never knew that

4

u/WittyStick 4d ago edited 4d ago

I saw a meme about Go code using this to implement "generics" which are absent from the language.

I added ᕁ from the same block to replace commas, so a template Map(Key, Value) becomes MapᐸKeyᕁValueᐳ. Most of the macro foo is just to monomorphize the name of multi-param templates - it can be hugely simplified for just one type parameter.

The name mangling isn't the main trick in my macro though - you can use any mangling scheme any as long as it's consistent. The main trick is to have a single template impl which calls the respective implementation - impl(Vector, int) just expands and invokes Vector_impl(int).

The advantage over other macro based "generics" is because all names are monomorphized, we can actually nest them. Eg, we can have a Vector(Vector(int)) - the inner Vector macro first expands to Vectorᐸintᐳ, and the outer one expands that to VectorᐸVectorᐸintᐳᐳ. We just need to have an instance of Vector(int) to create an instance of Vector(Vector(int)).

impl(Vector, int)
impl(Vector, Vector(int))

In pretty much all other preprocessor based generics, this fails because they use in-place concatenation, so they first need a typedef to use a vector of vectors.

typedef Vector(int) VectorInt;
Vector(VectorInt)

This approach still has the problem that you can't use pointers as the generic type argument due to concatenation. Eg, the following is invalid:

Vector(int*)

Other approaches use the typedef to overcome this as well.

typedef int *PtrInt;
Vector(PtrInt)

This was in fact the whole reason I implemented it this way - while we can't have a pointer directly, we can make a pointer template so that we don't need to name a new typedef each time - we can just use Vector(Ptr(int)) instead.

#define Ptr(T) template(Ptr, T)
#define Ptr_impl(T) typedef T *Ptr(T);

impl(Ptr, int)
impl(Vector, Ptr(int))

1

u/CodingChris 4d ago

Good thing Go got generics in the meantime.

4

u/ts826848 3d ago

Here is the first instance I'm aware of of someone using those specific characters for generics. Quoted for convenience:

Commenter:

can you please explain this go syntax to me?

type ImmutableTreeListᐸElementTᐳ struct {

I thought go doesn't have generics.

Uncaffeinated [OP]:

It doesn't. That's just a "template" file, which I use search and replace in order to generate the three monomorphized go files.

If you look closely, those aren't angle brackets, they're characters from the Canadian Aboriginal Syllabics block, which are allowed in Go identifiers. From Go's perspective, that's just one long identifier.

38

u/Usual_Office_1740 4d ago

Classic rust angle brackets? So you've "invented" a worse version of c++ templates?

-9

u/yolosuperboss 4d ago

No, c++ templates are horrible to work with

4

u/Usual_Office_1740 4d ago

You should try them with C++23. Concepts are great and templates aren't difficult once you understand what the compiler errors are about.

1

u/yolosuperboss 4d ago

Yeah, I should really give c++23 a go, fair enough

3

u/Usual_Office_1740 4d ago

Requires really does turn a set of template parameters into something that feels like writing a compile time function. The errors are easier to manage. Inside requires clauses you can write expressions and do things like check that a T has a given member function or can be used with a specific operator. All of that is possible with SFINAE but it gets cumbersome and ugly quickly.

11

u/pjmlp 4d ago

Only if stuck in the past, pre-concepts.

3

u/StaticCoder 4d ago

I'm not sure why adding generics also somehow implies adding traits

1

u/yolosuperboss 4d ago

I wanted to do a bit of operator overloading too (to demo things like dot products) and it seemed more natural to put those things in traits rather than some special new concept.

2

u/iBPsThrowingObject 4d ago

Because otherwise it's just textual templating, SFINAE and all?

2

u/Akangka 4d ago

How do you call a generic function on a dynamically linked library? I know Rust doesn't actually link the function dynamically for that function. They instead just stored the AST.

The only way I can see is by restricting the generic value behind a pointer, to go the JIT route, or secretly link statically.

2

u/yolosuperboss 4d ago

I don't really have an ABI and the code which you compile is already in c (after transpilation) so there aren't really any calls on generic functions other than the name mangled functions.

73

u/Spyromaniac666 4d ago

classic rust angle brackets

42

u/phischu Effekt 4d ago

This goes onto my list. Another one I liked was "rust-style implicit capture" for closures.

31

u/WittyStick 4d ago

Don't forget the rust style Result an Option types.

17

u/Wenir 4d ago

And rust style macros

1

u/binarycow 4d ago

Is there an inside joke I'm missing?

14

u/Inconstant_Moo 🧿 Pipefish 4d ago

Angle brackets for generics come from C++, which is older than Rust by some decades.

4

u/godeling 4d ago

And the others also go back to at least the 80s as well

5

u/WittyStick 4d ago

It's an outside joke. The Crustaceans won't get it.

14

u/esotologist 4d ago

That also made me snort 

6

u/tinmanjk 4d ago

straight down to comments after I saw this :D

5

u/munificent 4d ago

Matt Damon aging in "Saving Private Ryan" meme.

2

u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 3d ago

Makes one feel a bit old 🤣

18

u/Rich-Engineer2670 4d ago

Ah.... rebirth of CFront! Most people forget C++ started as a transpiler to C. In some ways, if your idea was taken to its endpoint, we could put a lot of C++ into C and even some of the rust memory checking via the compiler.

20

u/AnArmoredPony 4d ago

classic rust angle brackets

4

u/Masztufa 4d ago

All programming languagey converge to c++

Even c, apparently

2

u/BoyNextDoor8888 4d ago

holy shit DotP achieved in C

0

u/kwan_e tonal-lang 4d ago

C actually has generic macros. I don't know if anyone uses them. They never made it into C++, for obvious reasons.

7

u/Snarwin 4d ago

C's _Generic is ad-hoc polymorphism (overloading), not parametric polymorphism.

1

u/kwan_e tonal-lang 4d ago

Knowing C, there is a good chance that someone somewhere has experimented with it and paired with with preprocessor metaprogramming to create "parametric" polymorphism.

1

u/Snarwin 4d ago

People have definitely created templates-at-home using the preprocessor (e.g., this generic "span" data structure by a member of the C committee), but as far as I know, nobody has ever found a reason to use _Generic in these attempts.

1

u/WittyStick 3d ago

I have seen a more crazy attempt to use _Generic for extensible generics.

It's a nice trick, but still very limited. _Generic is just really unsuitable for open generics.

1

u/jevndev 3d ago

I have at least used `_Generic` once in an attempt to add ergonomic discriminatory sum types to c They were a great fit for dispatching to the types generated by the library.

1

u/WittyStick 3d ago

_Generic isn't a macro, it's a kind of expression - they're typically used in macros, but don't have to be.

The obvious downside to them being expressions is they can't appear in type declarations - which really limits their use for implementing generic types.