17 ms·

Implementing Generic Types in C

89 points by sirwhinesalot 2y ago

lukaslalinsky 2y ago
For C with generic types, I think one should pick up Zig. It's exactly that, it's a low level language with manual memory management, but it allows you to do generic types like this without hacks.
- randomNumber7 2y ago
  You could use C++ and ignore the rest of it.
  - huhtenberg 2y ago
    Not sure why the parent is in gray. It's a perfectly valid and widely practiced approach.
    - codr7 2y ago
      How often it works out as intended is very much up for debate though.
      - jimbob45 2y ago
        For legacy codebases, switching the compiler is certainly out of the question. For everyone else, why do you think it would be an issue to use the C++ compiler?
        codr7 2y ago
        Because the complexity seeps in through the cracks, and with the language comes a mindset; same reasons Linus is wary about C++ in the kernel. Some say it works; I've never succeeded, even on solo projects.
      - krapp 2y ago
        I think this is the general style for the Godot framework. They use a limited subset of C++, avoiding STL and some modern features, and limited templates.
  - bfrog 2y ago
    I tried it once, ran out of memory debugging a template error as it blew up my terminal into a sea of jibberish.
- unclad5968 2y ago
  C3 and Odin are some other alternatives.
  - jdougan 2y ago
    Along with D
    - lukaslalinsky 2y ago
      D sits in a weird place and that's probably why it's not widely adopted. If I'm using C, it's probably because I'm doing something low level and garbage collector could be problematic there. If you are fine with complexity, C++ or Rust are better options. If you want a simple language, I'd suggest Zig. On the other hand, if I don't want to deal with memory management, and still want fairly fast compiled language, I'd just go with Go. It has a much better ecosystem, because low level GC language is really mostly targeted at server components and Go excels there with implicit async everywhere.
      - pebal 2y ago
        The creators of the D made a big mistake. Instead of focusing on improving the GC, they focused on making it possible to avoid GC in D. The Go has shown that this strategy was wrong.
- alcover 2y ago
  I often see such replies and wonder : the article isn't about choosing langs but is an exercise in C. That's the constraint.
  - bsder 2y ago
    If C is the constraint, then why are you doing generic types? If you're using C, use bloody C. Not C with weird extensions that nobody will understand. Not C attempting to gussy up into a language with a real type system. Not C with a garbage collector. etc. I don't get why so many people use C but don't want C. This isn't 1995 where you have to shoehorn everything into the C ecosystem because everything else sucked.
    - spacedcowboy 2y ago
      But ... all of those things are still C. Maybe with extra libraries / steps / whatever, but still C.
      - bsder 2y ago
        No ... this isn't C. Will it have IDE support for the abstraction? Will a syntax mistake explode with a non-sensical error (yes, in this instance, because you are splicing macros and a syntax mistake will splice weird)? etc. If you want C with Generic Types, use C++. Rather than splicing unknown garbage onto C, use a subset of your C++ features and you will get full IDE support, proper template errors (okay, maybe not an improvement), proper elision and inlining, etc.
        spacedcowboy 2y ago
        > No ... this isn't C. My test for whether something or not is "still C" is very simple... "Does it compile with a C compiler" These compile. They're C. End of debate. Whether something has IDE support is neither here nor there. When I was learning C, your IDE was "vi" and "csh"... It was still C. As for errors, completely normal C code can spew out errors up the wazoo if you miss an errant ;, " or } (to pluck examples out of the air) somewhere important, things like "function not defined" because you were using a function later on in the file and it can no longer be parsed. Error quality does not define the language either.
- sirwhinesalot 2y ago
  Zig is nice. Comptime is a really cool feature.
dleslie 2y ago
I've never heard of CC before; the ergonomics of it look positively _modern_. https://github.com/JacksonAllan/CC https://github.com/JacksonAllan/CC
juancn 2y ago
The Java example doesn't really compile due to generic arrays and mixing primitives and non-primitives, but the point still holds. Type erasure is still type checked though, it's just lost at runtime (i.e. the generics are not reified). This works for Java very well because the JIT will have another chance at further optimizations once the application runs.
- alcover 2y ago
  > Type erasure is still type checked though In the C example ? What do you mean ?
  - to11mtm 2y ago
    If I had to guess, they were moreso referring to the java examples... The article states "The biggest issue is the same one Java had before version 5, there’s no type safety"... But that's a weird way to put it... Java 5 was when generics were actually introduced... so comparing a C hack for generics to Java pre V5... is just... weird.
    - sirwhinesalot 2y ago
      Hi author here, I don't understand your comment. Why is it weird? It's the same issue, only difference is in java (pre-5) you'll get a runtime exception somewhere while in C you'll get memory corruption, but it's the same cause, an "any" type. Modern Java has generics so it'll check at compile time that you use the types correctly.
      - to11mtm 2y ago
        > only difference is in java (pre-5) you'll get a runtime exception somewhere while in C you'll get memory corruption, but it's the same cause, an "any" type. I would think that a runtime exception vs memory corruption is a big difference in relative type safety.... But overall I was just trying to explain to folks in thread how things were parsed....
deleted 2y ago
[deleted]
huhtenberg 2y ago
> I personally quite enjoy programming in “C with methods, templates, namespaces and overloading”, avoiding the more complicated elements of C++ (like move semantics2) Don't we all. Except for the committee, of course, and its entourage.
marcodiego 2y ago
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3509.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3509.pdf
- hgs3 2y ago
  Is this the version of "generics" the C committee is leaning towards? Last I checked there were at least three other proposals [1] [2] [3]. [1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3212.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3212.pdf [2] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2924.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2924.pdf [3] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2853.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2853.pdf
spacedcowboy 2y ago
Probably worth mentioning the C Template Library [1]... [1]: https://github.com/glouw/ctl/ https://github.com/glouw/ctl/
dsp_person 2y ago
I've found useful doing an implementation with void* and having thin macros to do casting with typeof() so the usage is type checked.
jll29 2y ago
> The former is nicer to program while the latter is nicer to use. When I have such a situation, I'm inclined to write myself my own pre-processor (as I did for Pascal once in a previous millenium, on an Atari ST 520+), so that you can write in a style that is nicer to program in, which gets pre-compiled into something that is nicer to use from your client code. Nothing comes without downsides: the price of this is that other developers need to understand your idiosyncratic pre-processor, so this method works best for "single author" code/personal projects. What you don't want in a team is each coder having their own way of doing things, so that you cannot share libraries and helper functions. BTW, the best book on the OP's topic of production coding in C and implementing type-safe ADTs is Chris Hanson's book "C: Interfaces and Implementations." It contains some eye-opening tricks even for experienced developers in (standard) C.
- RossBencina 2y ago
  I wonder are there any existing metaprogramming frameworks for C? (something like C#'s Roslyn) I've been playing around with ANTLR and Python but curious to know what I've missed.
  - usrnm 2y ago
    C++. Only half-joking, this is exactly how C++ started
    - dismas 2y ago
      Objective-C started that was as well, too!
- hgs3 2y ago
  It's worth mentioning that there are dedicated processors, like m4, and templating engines, like Jinja, if you need something battle-tested.
WalterBright 2y ago
When moving into generic types and metaprogramming in C, your only real choice is macros. I've been down that path. It just never seems to work out very well, and the results were always unsatisfying. At some point, it becomes worthwhile to graduate to a more powerful language that still retains all the low level capability, like DasBetterC.
tidwall 2y ago
Here's a b-tree library I wrote that uses a similar approach. https://github.com/tidwall/bgen https://github.com/tidwall/bgen
cyber1 2y ago
Unfortunately, the standardization committee plays around with macros and _Generic instead of investing their time in modern metaprogramming ideas
codr7 2y ago
This is how I do proper generic vectors in C, no template tricks needed and no pointer chasing involved: https://github.com/codr7/hacktical-c/tree/main/vector https://github.com/codr7/hacktical-c/tree/main/vector The problem was always pretending C is something it's not, that never works well in any language.
wolfspaw 2y ago
Lol, thats insane. And awesome, I love it!
attractivechaos 2y ago
For linked lists and binary trees, intrusive data structures are better. > Well, except the first one, template macros, where I can’t really find any pro, only cons. For toy examples, the first (expanding a huge macro) has mostly cons. But it is more flexible when you want to instantiate different parts of the header. The second approach can work but will be clumsy in this case because the whole header is considered as one unit.

89 points by sirwhinesalot 2y ago

For C with generic types, I think one should pick up Zig. It's exactly that, it's a low level language with manual memory management, but it allows you to do generic types like this without hacks.

randomNumber7 2y ago
You could use C++ and ignore the rest of it.
- huhtenberg 2y ago
  Not sure why the parent is in gray. It's a perfectly valid and widely practiced approach.
  - codr7 2y ago
    How often it works out as intended is very much up for debate though.
    - jimbob45 2y ago
      For legacy codebases, switching the compiler is certainly out of the question. For everyone else, why do you think it would be an issue to use the C++ compiler?
      - codr7 2y ago
        Because the complexity seeps in through the cracks, and with the language comes a mindset; same reasons Linus is wary about C++ in the kernel. Some say it works; I've never succeeded, even on solo projects.
    - krapp 2y ago
      I think this is the general style for the Godot framework. They use a limited subset of C++, avoiding STL and some modern features, and limited templates.
- bfrog 2y ago
  I tried it once, ran out of memory debugging a template error as it blew up my terminal into a sea of jibberish.
unclad5968 2y ago
C3 and Odin are some other alternatives.
- jdougan 2y ago
  Along with D
  - lukaslalinsky 2y ago
    D sits in a weird place and that's probably why it's not widely adopted. If I'm using C, it's probably because I'm doing something low level and garbage collector could be problematic there. If you are fine with complexity, C++ or Rust are better options. If you want a simple language, I'd suggest Zig. On the other hand, if I don't want to deal with memory management, and still want fairly fast compiled language, I'd just go with Go. It has a much better ecosystem, because low level GC language is really mostly targeted at server components and Go excels there with implicit async everywhere.
    - pebal 2y ago
      The creators of the D made a big mistake. Instead of focusing on improving the GC, they focused on making it possible to avoid GC in D. The Go has shown that this strategy was wrong.
alcover 2y ago
I often see such replies and wonder : the article isn't about choosing langs but is an exercise in C. That's the constraint.
- bsder 2y ago
  If C is the constraint, then why are you doing generic types? If you're using C, use bloody C. Not C with weird extensions that nobody will understand. Not C attempting to gussy up into a language with a real type system. Not C with a garbage collector. etc. I don't get why so many people use C but don't want C. This isn't 1995 where you have to shoehorn everything into the C ecosystem because everything else sucked.
  - spacedcowboy 2y ago
    But ... all of those things are still C. Maybe with extra libraries / steps / whatever, but still C.
    - bsder 2y ago
      No ... this isn't C. Will it have IDE support for the abstraction? Will a syntax mistake explode with a non-sensical error (yes, in this instance, because you are splicing macros and a syntax mistake will splice weird)? etc. If you want C with Generic Types, use C++. Rather than splicing unknown garbage onto C, use a subset of your C++ features and you will get full IDE support, proper template errors (okay, maybe not an improvement), proper elision and inlining, etc.
      - spacedcowboy 2y ago
        > No ... this isn't C. My test for whether something or not is "still C" is very simple... "Does it compile with a C compiler" These compile. They're C. End of debate. Whether something has IDE support is neither here nor there. When I was learning C, your IDE was "vi" and "csh"... It was still C. As for errors, completely normal C code can spew out errors up the wazoo if you miss an errant ;, " or } (to pluck examples out of the air) somewhere important, things like "function not defined" because you were using a function later on in the file and it can no longer be parsed. Error quality does not define the language either.
sirwhinesalot 2y ago
Zig is nice. Comptime is a really cool feature.

dleslie 2y ago

I've never heard of CC before; the ergonomics of it look positively _modern_. https://github.com/JacksonAllan/CC https://github.com/JacksonAllan/CC

juancn 2y ago

The Java example doesn't really compile due to generic arrays and mixing primitives and non-primitives, but the point still holds. Type erasure is still type checked though, it's just lost at runtime (i.e. the generics are not reified). This works for Java very well because the JIT will have another chance at further optimizations once the application runs.

alcover 2y ago
> Type erasure is still type checked though In the C example ? What do you mean ?
- to11mtm 2y ago
  If I had to guess, they were moreso referring to the java examples... The article states "The biggest issue is the same one Java had before version 5, there’s no type safety"... But that's a weird way to put it... Java 5 was when generics were actually introduced... so comparing a C hack for generics to Java pre V5... is just... weird.
  - sirwhinesalot 2y ago
    Hi author here, I don't understand your comment. Why is it weird? It's the same issue, only difference is in java (pre-5) you'll get a runtime exception somewhere while in C you'll get memory corruption, but it's the same cause, an "any" type. Modern Java has generics so it'll check at compile time that you use the types correctly.
    - to11mtm 2y ago
      > only difference is in java (pre-5) you'll get a runtime exception somewhere while in C you'll get memory corruption, but it's the same cause, an "any" type. I would think that a runtime exception vs memory corruption is a big difference in relative type safety.... But overall I was just trying to explain to folks in thread how things were parsed....

deleted 2y ago

[deleted]

huhtenberg 2y ago

> I personally quite enjoy programming in “C with methods, templates, namespaces and overloading”, avoiding the more complicated elements of C++ (like move semantics2) Don't we all. Except for the committee, of course, and its entourage.

marcodiego 2y ago

https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3509.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3509.pdf

hgs3 2y ago
Is this the version of "generics" the C committee is leaning towards? Last I checked there were at least three other proposals [1] [2] [3]. [1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3212.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3212.pdf [2] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2924.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2924.pdf [3] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2853.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2853.pdf

spacedcowboy 2y ago

Probably worth mentioning the C Template Library [1]... [1]: https://github.com/glouw/ctl/ https://github.com/glouw/ctl/

dsp_person 2y ago

I've found useful doing an implementation with void* and having thin macros to do casting with typeof() so the usage is type checked.

jll29 2y ago

> The former is nicer to program while the latter is nicer to use. When I have such a situation, I'm inclined to write myself my own pre-processor (as I did for Pascal once in a previous millenium, on an Atari ST 520+), so that you can write in a style that is nicer to program in, which gets pre-compiled into something that is nicer to use from your client code. Nothing comes without downsides: the price of this is that other developers need to understand your idiosyncratic pre-processor, so this method works best for "single author" code/personal projects. What you don't want in a team is each coder having their own way of doing things, so that you cannot share libraries and helper functions. BTW, the best book on the OP's topic of production coding in C and implementing type-safe ADTs is Chris Hanson's book "C: Interfaces and Implementations." It contains some eye-opening tricks even for experienced developers in (standard) C.

RossBencina 2y ago
I wonder are there any existing metaprogramming frameworks for C? (something like C#'s Roslyn) I've been playing around with ANTLR and Python but curious to know what I've missed.
- usrnm 2y ago
  C++. Only half-joking, this is exactly how C++ started
  - dismas 2y ago
    Objective-C started that was as well, too!
hgs3 2y ago
It's worth mentioning that there are dedicated processors, like m4, and templating engines, like Jinja, if you need something battle-tested.

WalterBright 2y ago

When moving into generic types and metaprogramming in C, your only real choice is macros. I've been down that path. It just never seems to work out very well, and the results were always unsatisfying. At some point, it becomes worthwhile to graduate to a more powerful language that still retains all the low level capability, like DasBetterC.

tidwall 2y ago

Here's a b-tree library I wrote that uses a similar approach. https://github.com/tidwall/bgen https://github.com/tidwall/bgen

cyber1 2y ago

Unfortunately, the standardization committee plays around with macros and _Generic instead of investing their time in modern metaprogramming ideas

codr7 2y ago

This is how I do proper generic vectors in C, no template tricks needed and no pointer chasing involved: https://github.com/codr7/hacktical-c/tree/main/vector https://github.com/codr7/hacktical-c/tree/main/vector The problem was always pretending C is something it's not, that never works well in any language.

wolfspaw 2y ago

Lol, thats insane. And awesome, I love it!

attractivechaos 2y ago

For linked lists and binary trees, intrusive data structures are better. > Well, except the first one, template macros, where I can’t really find any pro, only cons. For toy examples, the first (expanding a huge macro) has mostly cons. But it is more flexible when you want to instantiate different parts of the header. The second approach can work but will be clumsy in this case because the whole header is considered as one unit.