9 ms·
Datatype99: C99 with Sum Types, v0.1.0
- enriquto 6y agoWhat is this sorcery? #include <datatype99.h> datatype( BinaryTree, (Leaf, int), (Node, struct BinaryTree *, int, struct BinaryTree *) ); What kind of preprocessor black magic can you do so that this code compiles? I don't dare to open the file datatype99.h lest it casts a dark spell on me.
- willxinc 6y agohttps://github.com/Hirrolot/epilepsy https://github.com/Hirrolot/epilepsy According to the GitHub, which appears to be a metaprogramming library by the same author.
- flohofwoe 6y agoThe whole system seems to be built on top of variadic macros (which had been standardized in C99).
- Hirrolot 6y agoYes, as others have already noticed, it is implemented on top of https://github.com/Hirrolot/epilepsy https://github.com/Hirrolot/epilepsy, a metalanguage for preprocessor metaprogramming.
- jrimbault 6y ago> a metalanguage for preprocessor metaprogramming That sentence is everything I was taught to avoid. Props to you. I like the drug/alcohol metaphor for these things, as a child avoid them, as an adult do your thing as long as you remain sensible.
- globuous 6y agoFunny you use this example, the author's GH page says he's 16; in many countries he wouldn't be able to drink, event responsibly ^^
- masklinn 6y ago> in many countries he wouldn't be able to drink But in most countries they would be able to drink (especially in a private setting), just not purchase. In Europe for instance less than half a dozen countries have a minimum drinking age for private settings, and a dozen more have an MDA in public (but not private), though for some 16 is enough to drink fermented alcohols (alongside a meal with adults for the UK, regardless for Germany and Austria).
- enriquto 6y agoLOL, I cannot get enough of this shit! Can you point to some cool implementation tricks that you used to achieve that? I guess there's quite a bit of ## concatenation to create temporary names and stuff?
- Hirrolot 6y agoWell, mostly I use idioms from the Cloak Wiki (https://github.com/pfultz2/Cloak/wiki/C-Preprocessor-tricks,-tips,-and-idioms https://github.com/pfultz2/Cloak/wiki/C-Preprocessor-tricks,...). It takes some time to realise them :)
- orra 6y agoIn case anybody mistakenly thinks doing so is 'cheating', you're the author of both libraries! This is absurd, but in a good way.
- kzrdude 6y agoIt's syntax sugar for tagged unions, of course. It's not entirely out there that C could include such support natively in a future standard.
- rbonvall 6y agoI predict all languages will adopt some form of sum types and pattern matching in the next 10 years. They will go from esoteric to mainstream in the same way lambdas did.
- mtzet 6y agoI find it really interresting that such a simple concept as a tagged union, which appeared at least as far back as ALGOL 68, could be completely abandoned during the 90's and 00's where OOP reigned surpreme, and only seems to be gaining popularity again now that pattern matching is all the rage. It's just baffling to me that tagged unions could be shunned in favour of the visitor pattern. How could that ever look like progress? Being a millenial, I don't know what programming was like the 80's, but surely tagged unions must have been bread and butter for Pascal programmers?
- marcosdumay 6y agoTo be fair, tagged unions are too error prone to be useful without strong types. That never stopped people from using them, but when a statically enforced alternative came along, everybody jumped ship.
- flohofwoe 6y agoTagged unions have always been around as runtime constructs, they just had different names (e.g. "variant"). In C it's understandable why they aren't part of the language: they would be the only data type that requires a "builtin" opaque struct type to hold the tag and payload union (e.g. something like this, but hidden from the programmer): struct my_tagged_union { enum my_tag_enum tag; union { .... } payload; }; That would be a pretty big break with "tradition" for the C language ;) (e.g. it would be similar to a "builtin string type") And of course tagged unions as "generic user-defined types" are much less convenient/useful than being directly integrated into the language syntax and type system.
- cies 6y ago> Pattern matching is exhaustive too. Sweet. C seems to be getting there :)
- orra 6y agoIndeed, exhaustive pattern matching is sweet. What is the noddy explanation of how it is achieved, I wonder?
- Hirrolot 6y agodatatype99 generates a switch expression under the hood, and modern compilers check this switch expression for exhaustiveness.
- DaiPlusPlus 6y agoHow do compilers check for exhaustiveness when the domain is unbound? Or rather: how does one constrain an integer in C? C enums are glorified consts, it’s still legal to do `myenum_t x = 0xFFFF` where 0xFFFF is not a defined value. This is necessary to allow for flags/bitfield enums.
- fallat 6y agoCombine it with Checked C...Why do we need Rust? :)
- pjmlp 6y ago- proper strings and arrays, bounded checked by default. By the way, it doesn't need to be Rust, there are plenty of alternatives, some of them like NEWP and PL/I variants are about 10 years older than C.
- masklinn 6y ago- compiler prevents use of uninitialised or freed memory - langage actually uses safety features in api design (good luck updating libc to use this)
- skocznymroczny 6y agoworking and sane package manager and build tool
- syockit 6y agoToo often that I find the C extension projects introduced here on HN would omit examples for dynamically allocated objects. In the binary tree example, apparently I can't just memcpy an existing tree to a malloc'd tree because the nodes would point to the ones on the old tree. I was halfway writing a copy function that recursively traverses the source tree, void copy(BinaryTree *dest, const BinaryTree *src) { match(*src) { of(Leaf, x) { *dest = TREE(Leaf(x)); } } } then realised that this still points to a leaf on the stack. Need a way to replace all the pointers to be relative to the destination tree...
- lasagnaphil 6y agoIsn’t that a problem even in managed, garbaged-collected languages? For most (procedural) languages it’s a bit involved if you want to deep-copy heap-allocated objects. If you don’t want the overhead of re-creating the tree from scratch, you can use indices instead of pointers and store the nodes in a heap-allocated contiguous array, and then when you want to create a deep copy of the tree you can just memcpy the whole array in one go.
- dataflow 6y agoI'm guessing they're coming from C++ or similar where the copy constructors already take care of making a deep copy.
- lasagnaphil 6y agoStill, inside that copy constructor you're going to write the exact boilerplate code for recursively copying each node, so the complexity of code won't change that much. Also, you're going to call quite a lot of malloc/free, which could be a potential performance hit if you're creating/destroying large trees a lot, as well as fragmenting your memory if you're not careful. Personally I have a much easier time dealing with tree/graph data structures using indices, regardless of the language I'm using. Using indices as handles in general are just so much easier than using pointers in terms of memory management, and generally performs much better in terms of cache coherency. Indices are also easier to serialize/deserialize, and sometimes it just "makes sense" (for example, if you're developing a physics simulation, representing objects as indices are natural because you're going to use those index values inside various math equations.) The downside might be that if you're creating and destroying nodes in a tree continuously. then you have to be careful about reusing indices. There's a pattern in gamedev (generational indices) that solve the issue (basically, in addition to an index you also store a counter value with it, and you increment the counter everytime you allocate a new node in the same spot of the array. It's a bit more bookkeeping, but there's lots of code examples for it. It's kind of a well-known trick inside gamedev (and recently in the Rust community, in order to bypass borrow checker issues). A few pointers: - https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html - https://kyren.github.io/2018/09/14/rustconf-talk.html https://kyren.github.io/2018/09/14/rustconf-talk.html - https://news.ycombinator.com/item?id=17995634 https://news.ycombinator.com/item?id=17995634 (steveklabnik explaining how generational indices work with code).
- geon 6y agoHow does it compare to the tagged unions in Zig, which aims to be “C with the bugs fixed”?
- flohofwoe 6y agoZig has the advantage that it can add the syntax sugar right into the language instead of using macro "workarounds", but I'd guess in the end both have similar lowlevel memory layout (a struct with an enum tag, followed by a payload "raw union") and generated code (e.g. it would be interesting to look at the compiler outputs, they should be very similar).
- eqvinox 6y agoThis "advantage" is also its greatest disadvantage. I can stick these macro definitions in any existing project and start incrementally rolling them out. Migrating something — even partially — to Zig is a much bigger task.
- Hirrolot 6y agoHmm, I don't use Zig so can't say much about it.
- flohofwoe 6y agoThis is what it looks like in Zig: https://ziglang.org/documentation/master/#Tagged-union https://ziglang.org/documentation/master/#Tagged-union You create two types, a tag enum, and the tagged union itself, which has a typed "payload" for each tag. Plus the necessary "syntax sugar" for initialization and extracting the payload by tag.
- steerablesafe 6y agoIf `match` compiles down to a switch case on the type discriminator then it can easily beat current implentations of C++'s std::visit on std::variant. I assume pattern matching must be exhaustive. Can there be a default case?
- Hirrolot 6y agoYes, just write otherwise { ... } to handle a default case.
- sesuximo 6y agoWhat else can std visit generate? I’d imagine it does exactly that
- ynik 6y agostd::variant is implemented with variadic templates; but C++ doesn't have a "variadic switch" statement. So std::visit cannot directly use a switch statement. Instead it's usually implemented as a recursive function with the hope that the compiler will unroll the recursion and optimize it into a switch. This hope usually doesn't work out in practice.
- steerablesafe 6y agoAFAIK the usual implementation is statically generating an array of function pointers and dispatching based on the type discriminator. This works even less for inlining.
- sesuximo 6y agoOn my phone so cannot check, but I thought this was mostly a solved problem? Inlining/folding a jump table should be easy enough especially since the table can be const
- steerablesafe 6y ago
- marcodiego 6y agoCan it be used to implement something similar to typen_ame() or type_id()?
- Hirrolot 6y agoSomething similar, yes. Behind the scenes, datatype99 deduces a type of a matched expression using the typedefs generated earlier.
- marcodiego 6y agoYou mean, type_id and type_name would have to be handwritten functions, right? If it is possible to automatically generate these, could you provide an example?
- Hirrolot 6y agoWe can generate a type ID by defining an extern variable of a sum type inside the `datatype` macro. Its address then will be a type ID (though I am not sure that such two variables will always have different addresses, I need to check the standard). About type_name: you can deduce a type name if you know at least one tag of a sum type. For example, if a tag is `Foo`, then `FooSumT` is a typedef to an outer sum type (datatype99 generates this typedef).
- eqvinox 6y agoTwo non-const variables will always have different addresses if they are of the same type. Different types can [AFAIR] per the standard theoretically be in different address spaces, though this is rare in practice.
- a1369209993 6y ago> Different types can [AFAIR] per the standard theoretically be in different address spaces If you can force the types to contain a member of the same type (say, a int or enum foobar_discriminant), the pointers &const_var_foo.disc and &const_var_bar.disc would have to differ for obvious reasons.
- naasking 6y agoI created something similar [1] awhile back: SUM(foo) { foo_one, foo_two, }; /* declare each sum case */ CASE(foo, foo_one) { int i; char c; }; CASE(foo, foo_two) { double d; }; void do_bar(foo f) { MATCH(f) { AS(foo_one, y) printf("foo_one: %d, %c\n", y->i, y->c); AS(foo_two, y) printf("foo_two: %d\n", y->d); MATCHANY fprintf(stderr, "No such case!"); exit(1); } } [1] https://github.com/naasking/libsum https://github.com/naasking/libsum
- dleslie 6y agoOh, this is from the poica author! Neat! That Poica can't work on C99 made it a non-starter for me; but all I really wanted was the sum types.
- Hirrolot 6y agoYeah, actually the most missing thing in C is sum types, as for me. Poica was rather an experiment; datatype99 is rather a practical library. I'm planning to use it on my work.
- setpatchaddress 6y ago> Pure C99. No external tools are required; datatype99 is implemented using only preprocessor macros. And sure enough, the code is unreadable and unmaintainable as you'd expect. You can build Boost out of C99 macros. There's a really good reason why you shouldn't.
- Hirrolot 6y agoThe reason why I created this project is that I miss sum types in C all the time, literally everywhere I need a custom error type or just any other alternative data representation. And I do think the implementation of datatype99 is straightforward -- only long names, all the dirty hacks are encapsulated into the underlying framework.