Datatype99: C99 with Sum Types, v0.1.0

by hirrolot • 5 years ago

157 64 5 years ago

enriquto2• 5 years ago

What 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• 5 years ago

https://github.com/Hirrolot/epilepsy

According to the GitHub, which appears to be a metaprogramming library by the same author.

flohofwoe4• 5 years ago

The whole system seems to be built on top of variadic macros (which had been standardized in C99).

Hirrolot9• 5 years ago

Yes, as others have already noticed, it is implemented on top of https://github.com/Hirrolot/epilepsy, a metalanguage for preprocessor metaprogramming.

jrimbault• 5 years 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.

enriquto2• 5 years ago

LOL, 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?

orra2• 5 years ago

In case anybody mistakenly thinks doing so is 'cheating', you're the author of both libraries!

This is absurd, but in a good way.

kzrdude• 5 years ago

It'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• 5 years ago

I 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• 5 years ago

I 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?

mhh__• 5 years ago

Currently with D the two people in charge both favour library solutions, but so far I'm seriously leaning towards a language one - it seems to hard to do type erasure efficiently otherwise, for example.

cies• 5 years ago

Pattern matching is exhaustive too.

Sweet. C seems to be getting there :)

orra2• 5 years ago

Indeed, exhaustive pattern matching is sweet. What is the noddy explanation of how it is achieved, I wonder?

Hirrolot9• 5 years ago

datatype99 generates a switch expression under the hood, and modern compilers check this switch expression for exhaustiveness.

fallat• 5 years ago

Combine it with Checked C...Why do we need Rust? :)

pjmlp2• 5 years 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.

masklinn2• 5 years 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• 5 years ago

working and sane package manager and build tool

syockit2• 5 years ago

Too 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...

lasagnaphil2• 5 years ago

Isn’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• 5 years ago

I'm guessing they're coming from C++ or similar where the copy constructors already take care of making a deep copy.

boomlinde• 5 years ago

The allocation strategy used is only a tangential problem. The purpose of the example is to demonstrate the functionality of the library in brief, not to walk the reader through problems that C programmers face in general.

I would suggest recursively walking through the original tree, creating an equivalent tree in the process instead of copying the original elements.

syockit2• 5 years ago

Yeah, I suppose.

    /* get size required for malloc */
    size_t getsize(const BinaryTree *tree) {
      size_t acc = sizeof(*tree);
      match(*tree) {
          of(Leaf, x) {
              return acc;
          }
          of(Node, lhs, x, rhs) {
              return getsize(*lhs) + acc + getsize(*rhs);
          }
      }
    }

    BinaryTree* copy(BinaryTree *dest, const BinaryTree *src) {
      dest->tag = src->tag;
      match(*src) {
         of(Leaf, x) {
            *dest = Leaf(*x);
         }
         of(Node, lx, x, rx) {
            match(*dest) {
              of(Node, ly, y, ry) {
                *ly = dest + 1;
                *ry = copy(*ly, *lx);
                *y = *x;
                copy(*ry, *rx);
              }
              otherwise {}
            }
         }
      }
      return dest + 1;
    }

Kind of hackish, but I guess it works.

geon• 5 years ago

How does it compare to the tagged unions in Zig, which aims to be “C with the bugs fixed”?

flohofwoe4• 5 years ago

Zig 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).

eqvinox3• 5 years ago

This "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.

Hirrolot9• 5 years ago

Hmm, I don't use Zig so can't say much about it.

flohofwoe4• 5 years ago

This is what it looks like in Zig:

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.

steerablesafe3• 5 years ago

If `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?

Hirrolot9• 5 years ago

Yes, just write otherwise { ... } to handle a default case.

sesuximo4• 5 years ago

What else can std visit generate? I’d imagine it does exactly that

ynik• 5 years ago

std::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.

marcodiego2• 5 years ago

Can it be used to implement something similar to typen_ame() or type_id()?

Hirrolot9• 5 years ago

Something similar, yes. Behind the scenes, datatype99 deduces a type of a matched expression using the typedefs generated earlier.

marcodiego2• 5 years ago

You 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?

naasking• 5 years ago

I 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

dleslie• 5 years ago

Oh, 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.

Hirrolot9• 5 years ago

Yeah, 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• 5 years 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.

Hirrolot9• 5 years ago

The 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.

Datatype99: C99 with Sum Types, v0.1.0

Related Stories