21 ms·

Algebraic Data Types for C99

376 points by bondant 2y ago

naasking 2y ago
Definitely looks nicer and probably works better than my older attempt [1], but uses 8x more code and depends on the awesome but kinda scary Metalang9 macro toolkit. I think libsum is a good intro if you want to see how algebraic data types work underneath. [1] https://github.com/naasking/libsum https://github.com/naasking/libsum
- Hirrolot 2y ago
  I have a star on your repository, so it seems I was looking into it while designing Datatype99 :)
  - cryptonector 2y ago
    GH stars kinda function as a bookmark system, except I never go looking at what all I've starred, so it's more of an optimistic bookmark system. I only sometimes use it as a "I would recommend this repo" -- how can one do that anyways, given that the repo could morph into something one would no longer recommend?
different_base 2y ago
One of the crimes of modern imperative programming languages is not having ADTs (except maybe Rust) built-in. It is such a basic mental model of how humans think and solve problems. But instead we got inheritance and enums which are practically very primitive.
- skywal_l 2y ago
  Zig is a modern imperative programming language with ADTs: https://ziglang.org/documentation/master/#Tagged-union https://ziglang.org/documentation/master/#Tagged-union
  - madeofpalk 2y ago
    Also Typescript https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#union-types https://www.typescriptlang.org/docs/handbook/2/everyday-type...
    - fanf2 2y ago
      Union types are not the same as sum types.
      - dtech 2y ago
        TS narrows union types cases based on conditionals like "if" (called discriminated unions in the docs in the past), and supports exhaustiveness checks. How do they differ in functionality from sum types?
        mpawelski 2y ago
        Supports exhaustiveness checks only if you explicitly opt-in it (by coding to pattern where you use helper function that accepts `never` type). "Dicriminated Unions Type"/"Sum Types" feels very hacky there, at least syntax-wise, because it is constraint by being "JS + types" language. It's remarkable what Typescript can do, but having native Discriminated Unions in JS (hence in TS too) would be much more ergonomic and powerful.
        nyssos 2y ago
        Sum types are disjoint unions. This `T` has three cases L = { tag: "a", payload: string } | { tag: "b", payload: number } R = { tag: "b", payload: number } | { tag: "c", payload: boolean } T = L | R whereas a proper sum type `L + R` would have four.
        brabel 2y ago
        Isn't that a completely useless distinction? For all purposes and intents, the "b" type in L and R should be treated the same, no? What do you gain by not doing that??
- tombert 2y ago
  Yeah, when I first learned Haskell a million years ago, and Erlang slightly less than a million years ago, the pattern matching was so plainly obviously the "correct" way to do things; it just felt like it was exactly how I thought about problems, and all the constructs with if/switch/enums had been an attempt to force my brain thinking into something that executes. It honestly does annoy me that a lot of mainstream languages still haven't really adopted ADTs; when Java 8 added a lot of (well-needed) new syntax, it felt like that was an ideal opportunity to add ADTs and pattern matching (though I'm sure that was easier said than done).
  - kaashif 2y ago
    > when Java 8 added a lot of (well-needed) new syntax, it felt like that was an ideal opportunity to add ADTs and pattern matching Well at least Java does now (as of Java 21) have pattern matching (including nested record destructuring) and sealed classes, which let you have decent sum types. The one issue is that everything is nullable, but that's a wider Java issue.
    - tombert 2y ago
      Yeah, but the annoying part of Java is that people stick with old versions for a long time. Java 21 looks pretty great but most companies are still using Java 17, or even Java 11 still.
      - cess11 2y ago
        Some have even older Java versions in 'prod'. 6 is still alive in some places out there, because management refuses to pay for either upgrade, replacement or dismantling. I have a mid-sized application I built on 17 that's used to deliver a particular project, really looking forward to finish the project so I get to move to 21 and refactor it with these new features and make it more general.
        tombert 2y ago
        Oof, I didn't know that anyone still used Java 6 anywhere. I have to think that it's a potential security nightmare at this point isn't it?
- jjice 2y ago
  I've never written Swift, but it seems like they have it too https://docs.swift.org/swift-book/documentation/the-swift-programming-language/enumerations/#Associated-Values https://docs.swift.org/swift-book/documentation/the-swift-pr... I also would love a future where ADTs are more common in imperative languages
  - odyssey7 2y ago
    Swift “enumerations” are very nice.
- zozbot234 2y ago
  Pascal has had variant records since the 1970s.
  - adrian_b 2y ago
    But Pascal's variant records (1970-11) had very ugly design errors in comparison with the unions of Algol 68 (1968-12), which made them either useless or annoying for most applicatons. Niklaus Wirth is well known as a critic of Algol 68 (before the design of Algol 68 was finalized), but in the case of his variant records he has completely failed to create something competitive.
    - pjmlp 2y ago
      Given where Algol 68 ended up, I would say Wirth was quite right.
      - adrian_b 2y ago
        Algol 68 was a failure mainly due to its inappropriate documentation, not due to the quality of the language. It included many innovations that appeared again in other programming languages only decades later. Niklaus Wirth was a good teacher and writer and the success of his languages is due mostly to his books and due to his languages being used for teaching in many universities, not due to their technical qualities.
        peoplefromibiza 2y ago
        > not due to their technical qualities AFAIK Pascal is C and Algol 68 is C++ people used Pascal because the compiler was blazing fast, it was easier to implement and learn and the features it lacked against Algol did not really matter most of the time (at the time) More features doesn't automatically means "better" Also Pascal had quite strong technical qualities, not very common among other contemporary languages edit: can I ask the reason for the downvote? I would really like to hear an opinion on what Pascal did wrong, having used it extensively in the late 80s until the end of the 90s and why my comment was awarded with a negative score.
- adrian_b 2y ago
  Moreover, they have already been proposed by John McCarthy in October 1964, 60 years ago, for inclusion in the successor of ALGOL 60, which makes even more weird the lack of widespread support. (And in fact Algol 68 had a better implementation than most later languages, but Algol 68 was missing completely any documentation suitable for newbies, like tutorials and programming examples, while not being promoted by any hardware vendor, like IBM or DEC, so it was doomed.)
  - floxy 2y ago
    >The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors. https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hi...
- debo_ 2y ago
  ADT feels like an unfortunately acronym-collision with "Abstract data types."
  - pjmlp 2y ago
    Yep, people that eventually buy a Modula-2 ADT book, when hunting old stuff, are in for a surprise. :)
    - debo_ 2y ago
      It's a term that is commonly used in computer science education to refer to any data type independent of its concrete implementation (so, basically, its interface.) I don't think it's just restricted to Modula-2?
      - pjmlp 2y ago
        Indeed, however CLU and Modula-2 were the ones used mostly for practical teaching purposes, until ML became widespread enough for ADT to gain yet another meaning.
    - mst 2y ago
      I just realised something terrible. This code is ADTs for C. At some point somebody's going to call it CADT and jwz will explode.
  - jghn 2y ago
    More often than not, when I say ADT to someone outside of the FP world, they assume I mean abstract data type.
    - bee_rider 2y ago
      Or the company that sells the security stickers, for houses.
  - keybored 2y ago
    ADT feels like an unfortunately acronym-collision with "algebraic data types." They were both introduced in the same decade.
- Verdex 2y ago
  NAND is a universal circuit primitive because it can be used to create all of the other circuit primitives. But if you think about it, this is more of an argument of manufacturing than it is in comprehensibility. Only needing to manufacture NAND is easy, but if you could only create your circuit this way, then you would have an unmaintainable mess. You can do the same thing with boolean logic and just have not-and, but thankfully we have and, or, not, xor. Similarly, you don't need greater-than-or-equal because you can just write 'x > y || x == y'. Comprehension is linked to how closely you can express the idea of what you're doing in the object language that you have to look at. It might be convenient to compile everything down to SK combinators so that your optimizer and evaluator can be simpler, but people should never look at that level (at least not until you suspect a compiler defect). So we get to object oriented programming. Where our data expression has an AND property (a class has an INT field AND a STRING field), an existential property (interfaces: there exists some object with these methods), and inheritance (a truly bizarre feature where we duck tape subtyping to a method and field grouping mechanism with a bunch of hooks). With interfaces and inheritance you can simulate both a universal property (generic) and an OR property. But because it's not a direct expression, we leave this giant gap for what people intended to happen to diverge from what actually happens. Especially after time passes, defects are found, and requirements change. [For example, when using interfaces to simulate an OR property, there really isn't any mechanism to let everyone know that this construct is closed. So if something erroneously gets added, you won't know to check the entire code base. And if requirement change and you need to add a new case, then you have to check the entire code base. Completeness checking of ADTs give you this for free in your pattern matches.] Too many non-trivial architectural messes that I've encountered in my career have been due to either someone trying to solve all of their problems with interfaces or the same with inheritance* when a simple OR data structure would have made everything simple, clear, and correct. [*] - Inheritance being more problematic when someone tries to create a non-trivially sized category hierarchy, which ruins the day when requirements change and suddenly the tree needs to be reorganized but doing so would invalidate entire swaths of the code base already accepting types with a different assumed (and undocumented) hierarchal tree structure. Thankfully most people have gotten the memo and switched to interfaces.
- taeric 2y ago
  I'm curious on supporting evidence for it being a basic mental model of how humans think? That sounds like a fairly strong claim.
  - Verdex 2y ago
    I'm a huge proponent of ADTs being a more comprehensible way to write code than some of the alternatives. But I do have to agree with you that there isn't really evidence that this is a basic mental model. However What we do see is a bunch of mathematical disciplines that end up creating properties like: AND, OR, Universal, Existential, Implication, (and a few others). They end up in places like: set theory, type theory, category theory, various logics, lattice theory, etc. Now, maybe they're only copying one another and this is more of a memetic phenomena. Or maybe they've hit upon something that's important for human comprehensibility. That would be the 'evidence' of the positive effect of ADTs (scare quotes because it might just be math memes and not fundamental). But we can also think about what I feel is legit evidence for the negative effect of lacking ADTs. Consider what happens if instead of having the standard boolean logic operators and, or, not, xor, we only have the universal not-and operator. Now a straightforward statement like: A && B || C becomes (((A !& B) !& (A !& B)) !& ((A !& B) !& (A !& B))) !& (B !& B) [I think...]. It's more complicated to tell what's actually supposed to be going on AND the '&&' simulation can get intertwined with the '||' simulation. The result being that requirements changes or defect fixes end up modifying the object level expression in a way where there is no longer any mapping back to standard boolean logic. Comprehensibility approaches zero. And we've seen this happen with interfaces and inheritance being used to implement what would otherwise be a relatively simple OR property (with the added benefit that pattern matching ADTs often comes with totality checking; not something you can do with interfaces which can always have another instance even up to and including objects loaded at runtime).
    - taeric 2y ago
      Appearing in symbolic reasoning tools we have invented doesn't really support them being how brains work, though? This is akin to saying that gears are how nature works because gears are everywhere in how we build things. I could maybe buy that with "friction" being a fundamental thing, but feels like a stretch for the other. Now, I should add that I did not mean my question to be a criticism of them! I'm genuinely curious on evidence that they are a basic building block. Feels save to say they are a good building block, and those aren't the same thing. As an easy example for them not being basic building blocks, I can't remember ever seeing anything like them in any assembly instructions for things. Put together a batting net for the kids. Lots of instructions, but nothing algebraic, in this sense. Looking at recipes for food. Nothing algebraic, really? Maybe I can squint and see some, but it would be hard. Exercise plans? Music lessons? Playbooks for a sport? Again, though, I /do not/ intend this as a criticism of them. Genuinely curious on any investigation into them.
- mgaunard 2y ago
  C has always had them, it's called union. In practice you need to couple it with an enum, and your visitation mechanism is a switch statement. But C doesn't impose that on you and lets you do it as you see fit.
  - duped 2y ago
    You're confusing semantics for implementation. The point of union and discriminated union types (not what C calls union) is to enable compiler checked pattern matching, which tagged enums in C plus a switch statement do not get you.
  - estebank 2y ago
    Tagged unions + pattern matching is what gp wants. You can always encode whatever model you want using any programming language, but language features/ergonomics matter.
  - coldtea 2y ago
    >C has always had them, it's called union It also has all the features of Haskell, since you can implement a Haskell compiler in C.
  - naasking 2y ago
    That you can sort of simulate the skeleton of algebraic data types does not mean that C has algebraic data types. The whole point of the algebra part is that the syntax has a compositional semantics which is completely absent in C, unless you go to great lengths as with this macro header.
  - bmoxb 2y ago
    That is not a proper alternative to real pattern matching.
  - anon-3988 2y ago
    lol this is like saying C doesn't need structs, you can just declare the variables with a common prefix separately! See ma, product types!
- CraigJPerry 2y ago
  >> not having ADTs (except maybe Rust) built-in Most of the common languages today have product types. Java[1], Rust, Haskell, etc. have sum types. I think it gets a bit more escoteric beyond that though - i don't doubt that there's probably some haskell extension for quotient types[2] or some other category theory high-jinx. Most languages have ADTs built in. [1] https://blogs.oracle.com/javamagazine/post/inside-the-language-sealed-types https://blogs.oracle.com/javamagazine/post/inside-the-langua... [2] https://en.wikipedia.org/wiki/Quotient_type https://en.wikipedia.org/wiki/Quotient_type
  - speed_spread 2y ago
    Java sum types work but still need a bit of syntax sugar on the declaration side, IMHO.
    - def_not_troll 2y ago
      [flagged]
  - nextaccountic 2y ago
    Does Java sealed classes enable something like an exhaustive pattern matching? (A form of pattern matching that will fail at compile time if you add a new class that extends the sealed class)
    - thewakalix 2y ago
      > The intent is to introduce a more-advanced construction called pattern matching in a later release.
      - brabel 2y ago
        You read that in a blog post from 2019. Java has had comprehensive pattern matching since Java 21, like one year ago (current Java version is 22). I posted an answer to the same parent comment with the C example written in Java... You can read more about it here: https://www.baeldung.com/java-lts-21-new-features https://www.baeldung.com/java-lts-21-new-features
- ajross 2y ago
  > [Algebraic Data Types are] such a basic mental model of how humans think and solve problems I think that's actually wrong for "Sum types". Product types, sure. The idea of storing a bunch of fields in a single thing matches the way we've been organizing information since we started writing things down. But I genuinely don't think I've seen an attempt at a sum/union/enumerant/whatever syntax in a programming language that wasn't horrifyingly confusing. Where by extension: class-based inheritance is actually pretty simple to understand. The classic "IS-A" relationship isn't as simple as "fields in a struct", but it's not hard to understand (c.f. all the animal analogies), and the syntax for expressing it is pretty clean in most languages. Is it the "best" way to solve a problem? Maybe not. Neither are ADT sum types. But I think there's a major baby-in-the-bathwater problem with trying to be different. I really don't think, for the case of typical coders writing typical code, that ADTs are bringing as much to the table as the experts think.
  - throwawaymaths 2y ago
    > class-based inheritance is actually pretty simple to understand Simple to understand, a nightmare to debug, as you'll be chasing where your data and data contracts across a ton of files.
    - ajross 2y ago
      That's a bit much. Type inheritance has been a core abstraction in software development since before most working developers were born. We as a society know how to do this. The idea that one oddball new idea is a revolution that turns a "nightmare" into sunshine is way too hyperbolized. Sum typing might be better! But frankly the jury is still out, and the impact is clearly going to be smaller than what you're imagining.
      - throwawaymaths 2y ago
        The new lowest level pls (zig, rust) have ditched class based inheritance. Higher level PLs are going more functional, to include JS, where entire frameworks are encouraging functional (not to mention how everyone complains about the opacity of trying to use inheritance in place of declarative i.e. Amazon CDK)
- Alifatisk 2y ago
  Isn’t ADT abbreviation for Abstract Data Type? Or does it depend in context nowadays?
  - rowanG077 2y ago
    Context. It means algebraic data type here.
  - Jaxan 2y ago
    You answered your own question: it depends and the context and is confusing imo. Both are very common in compsci
    - Alifatisk 2y ago
      No I didn’t, I provided two options and asked which case it was. I could’ve assumed OP had used the wrong abbreviation.
  - drycabinet 2y ago
    Wait until you switch to unions in rust and ask yourself whether it is a union or a struct.
    - Alifatisk 2y ago
      Oh dear
- Tainnor 2y ago
  > except maybe Rust Swift, Kotlin and Scala all have had ADTs for a while, even Java has it now.
- thesz 2y ago
  "Haskell is the best imperative language," (C) various software engineers. Also, algebraic data types can be seen as hierarchy consisting of abstract base class and several final children classes. So it is an inheritance model, just restricted one.
- epolanski 2y ago
  May not be built in but many mainstream languages such as typescript have libraries or the tools to easily implement them.
- deleted 2y ago
  [deleted]
linkdd 2y ago
This is the work of a wizard. I've known C for almost 20 years, and never would I have thought the macro system was powerful enough to allow such black magic. This is awesome!
- lupire 2y ago
  ADTs are mostly string replacement on generic structs and unions, plus tagging on the union. It's not a complicated use of macros.
- clnhlzmn 2y ago
  You might also be interested in metalang99 by the same author.
- CuriousCosmic 2y ago
  Yeah xmacros (the style of macro use) are pretty fancy. "Classically" they are used for creating and accessing type safe generics or for reducing boilerplate for hardware register and interrupt definitions. They are kind of cursed but at their core they are actually incredibly simple and a reliable tool for reducing cognitive complexity and boilerplate in C based projects.
- cl91 2y ago
  > I've known C for almost 20 years The author is only 19 years old. I feel really dumb now.
tombert 2y ago
Interesting. Algebraic Data Types are almost always one of the things I miss when I use imperative languages. I have to do Java at work, and while I've kind of come around on Java and I don't think it's quite as bad as I have accused it of being, there's been several dozen instances of "man I wish Java had F#'s discriminated unions". Obviously I'm aware that you can spoof it with a variety of techniques, and often enums are enough for what you need, but most of those techniques lack the flexibility and terseness of proper ADTs; if nothing else those techniques don't have the sexy pattern matching that you get with a functional language. This C extension looks pretty sweet since it appears to have the pattern matching I want; I'll see if I can use it for my Arduino projects.
- AlecBG 2y ago
  Sealed interfaces in java 21 allow pattern matching
  - tombert 2y ago
    Yeah I know, we just don't use Java 21 at work yet. I'm super excited for that update, and it actually looks like we will be transitioning to that by the end of the year, but I haven't had a chance to play with it just yet. I do find it a little annoying that it's taken so long for Java to get a feature that, in my opinion, was so clearly useful; it feels like they were about a decade later on this than they should have been, but I'll take whatever victories I can get.
    - brabel 2y ago
      If you can enable preview features, you can use pattern matching since Java 17 (though the final syntax in Java 21 was slightly changed - still you may want to use preview features, it's mostly fine in Java as they tend to change very little, and when you do upgrade, the compiler will tell you where you need to update your code).
- lupire 2y ago
  Kotlin is JVM compatible and has ADTs. Java has https://github.com/functionaljava/functionaljava https://github.com/functionaljava/functionaljava which is unsupported but stable.
jackling 2y ago
Could you not get most of the benefits of ADTs using structs + unions + enums? I've used the pattern where I had a union of several types and an enum to differentiate which one to pick. Something like std::variant seems to work a bit like a sum type. The only issue is you can't do a clean switch statement that matches on the specific value of a field, but nested switch statements aren't that messy.
- acuozzo 2y ago
  Yes, and you can also get many of the benefits of OOP with convention and discipline, but doing so requires you to frequently get down in the weeds since, e.g., vtables must be dealt with manually. The trouble with this approach is that there's a lot of mental overhead in dotting all of your i's and crossing all of your t's. It's draining, so you start to, e.g., shoehorn additional functionality into existing classes instead of making new ones. You eventually wind up perceiving the abstraction as costly which lessons your use of it at the expense of producing a more elegant solution to the problem(s) you're solving. tl,dr? The ability to just state "Darmok and Jalad at Tanagra" is transformative when the alternative is telling an entire story every time you want to reference a complex idea.
- mattgreenrocks 2y ago
  I generally don't mind C++ for most code when it's absolutely necessary, but I'm not a huge fan of std::variant. Using std::visit to exhaustively match all cases feels hacky. It really would benefit from being a first-class language feature. It's more impactful to a lot of day-to-day code than other things they've worked on, such as coroutines.
  - TheBicPen 2y ago
    The 4th example at https://en.cppreference.com/w/cpp/utility/variant/visit https://en.cppreference.com/w/cpp/utility/variant/visit that uses a class template makes the feature a bit nicer, but still not as ergonomic as something like Rust.
- naasking 2y ago
  > Could you not get most of the benefits of ADTs using structs + unions + enums? The modelling aspects can be simulated, yes, but that's barely half of the benefits of ADTs. Pattern matching is a big ergonomic benefit.
samatman 2y ago
Let's say you have a C program to write, and you really want exhaustive pattern matching on the tags of unions (which is what Datatype99 provides: "Put simply, Datatype99 is just a syntax sugar over tagged unions"). Let's say further that you already know Rust exists, and aren't going to use it for reasons that anyone writing a C program already knows. At least consider Zig. Here's a little something I wrote in Zig two days ago: /// Adjust a label-bearing OpCode by `l`. No-op if no label. pub fn adjust(self: *OpCode, l: i16) void { switch (self.*) { inline else => |*op| { const PayType = @TypeOf(op.*); if (PayType != void and @hasField(PayType, "l")) { op.*.l += l; } }, } } This uses comptime (inline else) to generate all branches of a switch statement over a tagged union, and add an offset to members of that union which have an "l" field. You can vary the nature of the branches on any comptime-available type info, which is a lot, and all the conditions are compile-time, each branch of the switch has only the logic needed to handle that variant. "But my program is already in C, I just need it for one file" right. Try Zig. You might like it.
- pajko 2y ago
  Seems like Nim can be useful too, plus it compiles to C. https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62ea21f6 https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62e...
  - brabel 2y ago
    In Nim, ADTs are painful still (as your example clearly shows), but they are working on adding proper ADTs to the language (I can't find where I read that, but I am sure I did!).
    - j-james 2y ago
      https://github.com/nim-lang/RFCs/issues/548 https://github.com/nim-lang/RFCs/issues/548
  - samatman 2y ago
    I've been a Nim respecter for many years, it's slept on in general as a language. The difference here is that Nim compiles to C and you can turn the garbage collector off: Zig compiles C and there's no garbage collector. That means the entire standard library is available when generating object code. It's also trivial to opt-in to the C ABI on a fine-grained basis, by defining a function or struct with the extern keyword. I believe this is still fairly current about the difficulties of building Nim dylibs for C programs: https://peterme.net/dynamic-libraries-in-nim.html https://peterme.net/dynamic-libraries-in-nim.html I expect Nim will stabilize about where D has: it will have a dialect of the language which, with relatively painless accommodations, is able to produce object code which speaks C ABI. Zig is different. The language is relentlessly focused on providing a better alternative to C while occupying the same niche, and a lot of design time has been spent on making it practical to take an existing C program and start writing the new parts of it in Zig. It's a good language, Nim, and getting better. I'd recommend it for someone who is considering Go, for example.
otikik 2y ago
What a madlad. Kudos for implementing this.
KerrAvon 2y ago
Anyone considering using this should be strongly looking at using Swift or Rust instead. You can build almost any given language idea using the C macro preprocessor, but that doesn't mean it's a good idea to ship production code using it. The worst codebases to inherit as a maintenance programmer are the ones where people got clever with the C preprocessor. Impossible to debug and impossible to maintain.
- 392 2y ago
  I find that most abuses of the preprocessor are by folks unwilling/unable to simplify their design into a form that's (a) native to the C language/runtime or (b) not repetitive to type. This library on the other hand addresses a nasty papercut whose presence usually stops folks with modern language experience from choosing C when it might otherwise be valid. Plus you can't beat C's long-term stability. Though I agree that 90+% who _think_ they still need C should probably move on to making Rust work for them, instead.
- endgame 2y ago
  C99 is a stable target for writing bootstrappable software: there are multiple mature compiler implementations, at least one of which is bootstrappable down to hex0, and the bootstrap chain is not too long.
mingodad 2y ago
There is also https://melt.cs.umn.edu/ https://melt.cs.umn.edu/ that has an extension that add templates and algebraic data types to C : https://github.com/melt-umn/ableC-template-algebraic-data-types https://github.com/melt-umn/ableC-template-algebraic-data-ty...
deleted 2y ago
[deleted]
WhereIsTheTruth 2y ago
Tagged Union is a must have in a programming language
modeless 2y ago
> PLEASE, do not use top-level break/continue inside statements provided to of and ifLet; use goto labels instead. Seems like a pretty big footgun. But otherwise, very cool.
- linkdd 2y ago
  goto is a footgun only if you use it to move from function to function, which btw was what "goto considered harmful" was about. That practice has disappeared, and now goto, within a function, is pretty harmless and quite identical to break/continue in fact.
  - modeless 2y ago
    Goto isn't the footgun. The footgun is if you use break/continue by accident then some unspecified bad thing will happen, silently I'm guessing.
- zzo38computer 2y ago
  Using goto instead isn't a problem, but knowing not to use break/continue inside of such blocks is something that you will have to be aware of. I had written a immediate mode UI out of macros, and this reminded me of that although in my case it is not a problem, although some blocks are ones that you can use "break". For example, you can use "break" to exit out of a win_form block ("goto" also works), while a win_command block does not capture "break" so using break (or goto) inside of a win_command block will break out of whatever block the win_command is in (probably a win_form block; for example, this would commonly be used in the case of a "Cancel" button).
- 392 2y ago
  What's neat about Rust is that in its macro land, writing the code that checked for this condition would be not only possible, but doable, imaginable, and aided by easily installable OSS libraries. So it's not just about being slightly better in some ways, but smoothing over so many paper cuts that it can be hard to see how they have added up overtime across ecosystems, like CPython and co having so many of its own vocab types, or HPC libs. For example, the problem with this macro that causes this wouldn't even be problems in a well written Rust macro. They're artifacts of smart people trying to work around C's limitations. But then the macro wouldn't have been written anyway because this is a port of a native Rust feature (which means it gets taken advantage of in community software).
klysm 2y ago
If I ever implement a product from scratch again, discriminated unions with compiler enforced exhaustive pattern matching is a hard requirement. It’s too powerful to not have.
- nmfisher 2y ago
  Union types are my biggest wish for Dart, but unfortunately it doesn't look like they'll be added any time soon. They've recently added support for compiler-enforced pattern matching over sealed classes, which I suppose does get you halfway there though.
- actionfromafar 2y ago
  What languages could fit that description today? I don't really understand what it even means but maybe I could understand better if I could look at examples in languages which have them.
  - phi-go 2y ago
    For example Rust: https://doc.rust-lang.org/std/keyword.enum.html https://doc.rust-lang.org/std/keyword.enum.html
    - jghn 2y ago
      Also Scala
  - seivan 2y ago
    Swift, Typescript depending on your opinion with structural typing, and Rust. Think Scala, Elm and Haskell have it as well. Having that and elixirs pattern matching would be insane.
- seivan 2y ago
  [dead]
drycabinet 2y ago
Wikipedia has something interesting on this (how unions can be implemented using "class hierarchy in object-oriented programming"): https://en.wikipedia.org/wiki/Tagged_union#Class_hierarchies_as_tagged_unions https://en.wikipedia.org/wiki/Tagged_union#Class_hierarchies... There is a lengthy blog post about the same stuff, except that the author doesn't seem to have come across the said wiki section yet: https://nandakumar.org/blog/2023/12/paradigms-in-disguise.html https://nandakumar.org/blog/2023/12/paradigms-in-disguise.ht... Kudos to the dev of datatype99 for showing the problem with such ad-hoc methods in the readme right away.
- alpine32 2y ago
  [dead]
rurban 2y ago
I certainly won't use that. It's not type safe, and doesn't even allow names for its pattern matching sugar. Why he calls this simple struct matching sugar via tagged unions "Algebraic Data Types" is beyond my understanding. He cannot even do nested structs nor unions. datatype( BinaryTree, (Leaf, int), (Node, BinaryTree *, int, BinaryTree *) ); No names for the struct fields, so you need to rely on the position. And then used: int sum(const BinaryTree *tree) { match(*tree) { of(Leaf, x) return *x; of(Node, lhs, x, rhs) return sum(*lhs) + *x + sum(*rhs); } // Invalid input (no such variant). return -1; } Where lhs, x, rhs magically match the types defined above. What a nonsense design!

376 points by bondant 2y ago

Definitely looks nicer and probably works better than my older attempt [1], but uses 8x more code and depends on the awesome but kinda scary Metalang9 macro toolkit. I think libsum is a good intro if you want to see how algebraic data types work underneath. [1] https://github.com/naasking/libsum https://github.com/naasking/libsum

Hirrolot 2y ago
I have a star on your repository, so it seems I was looking into it while designing Datatype99 :)
- cryptonector 2y ago
  GH stars kinda function as a bookmark system, except I never go looking at what all I've starred, so it's more of an optimistic bookmark system. I only sometimes use it as a "I would recommend this repo" -- how can one do that anyways, given that the repo could morph into something one would no longer recommend?

different_base 2y ago

One of the crimes of modern imperative programming languages is not having ADTs (except maybe Rust) built-in. It is such a basic mental model of how humans think and solve problems. But instead we got inheritance and enums which are practically very primitive.

skywal_l 2y ago
Zig is a modern imperative programming language with ADTs: https://ziglang.org/documentation/master/#Tagged-union https://ziglang.org/documentation/master/#Tagged-union
- madeofpalk 2y ago
  Also Typescript https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#union-types https://www.typescriptlang.org/docs/handbook/2/everyday-type...
  - fanf2 2y ago
    Union types are not the same as sum types.
    - dtech 2y ago
      TS narrows union types cases based on conditionals like "if" (called discriminated unions in the docs in the past), and supports exhaustiveness checks. How do they differ in functionality from sum types?
      - mpawelski 2y ago
        Supports exhaustiveness checks only if you explicitly opt-in it (by coding to pattern where you use helper function that accepts `never` type). "Dicriminated Unions Type"/"Sum Types" feels very hacky there, at least syntax-wise, because it is constraint by being "JS + types" language. It's remarkable what Typescript can do, but having native Discriminated Unions in JS (hence in TS too) would be much more ergonomic and powerful.
      - nyssos 2y ago
        Sum types are disjoint unions. This `T` has three cases L = { tag: "a", payload: string } | { tag: "b", payload: number } R = { tag: "b", payload: number } | { tag: "c", payload: boolean } T = L | R whereas a proper sum type `L + R` would have four.
        brabel 2y ago
        Isn't that a completely useless distinction? For all purposes and intents, the "b" type in L and R should be treated the same, no? What do you gain by not doing that??
tombert 2y ago
Yeah, when I first learned Haskell a million years ago, and Erlang slightly less than a million years ago, the pattern matching was so plainly obviously the "correct" way to do things; it just felt like it was exactly how I thought about problems, and all the constructs with if/switch/enums had been an attempt to force my brain thinking into something that executes. It honestly does annoy me that a lot of mainstream languages still haven't really adopted ADTs; when Java 8 added a lot of (well-needed) new syntax, it felt like that was an ideal opportunity to add ADTs and pattern matching (though I'm sure that was easier said than done).
- kaashif 2y ago
  > when Java 8 added a lot of (well-needed) new syntax, it felt like that was an ideal opportunity to add ADTs and pattern matching Well at least Java does now (as of Java 21) have pattern matching (including nested record destructuring) and sealed classes, which let you have decent sum types. The one issue is that everything is nullable, but that's a wider Java issue.
  - tombert 2y ago
    Yeah, but the annoying part of Java is that people stick with old versions for a long time. Java 21 looks pretty great but most companies are still using Java 17, or even Java 11 still.
    - cess11 2y ago
      Some have even older Java versions in 'prod'. 6 is still alive in some places out there, because management refuses to pay for either upgrade, replacement or dismantling. I have a mid-sized application I built on 17 that's used to deliver a particular project, really looking forward to finish the project so I get to move to 21 and refactor it with these new features and make it more general.
      - tombert 2y ago
        Oof, I didn't know that anyone still used Java 6 anywhere. I have to think that it's a potential security nightmare at this point isn't it?
jjice 2y ago
I've never written Swift, but it seems like they have it too https://docs.swift.org/swift-book/documentation/the-swift-programming-language/enumerations/#Associated-Values https://docs.swift.org/swift-book/documentation/the-swift-pr... I also would love a future where ADTs are more common in imperative languages
- odyssey7 2y ago
  Swift “enumerations” are very nice.
zozbot234 2y ago
Pascal has had variant records since the 1970s.
- adrian_b 2y ago
  But Pascal's variant records (1970-11) had very ugly design errors in comparison with the unions of Algol 68 (1968-12), which made them either useless or annoying for most applicatons. Niklaus Wirth is well known as a critic of Algol 68 (before the design of Algol 68 was finalized), but in the case of his variant records he has completely failed to create something competitive.
  - pjmlp 2y ago
    Given where Algol 68 ended up, I would say Wirth was quite right.
    - adrian_b 2y ago
      Algol 68 was a failure mainly due to its inappropriate documentation, not due to the quality of the language. It included many innovations that appeared again in other programming languages only decades later. Niklaus Wirth was a good teacher and writer and the success of his languages is due mostly to his books and due to his languages being used for teaching in many universities, not due to their technical qualities.
      - peoplefromibiza 2y ago
        > not due to their technical qualities AFAIK Pascal is C and Algol 68 is C++ people used Pascal because the compiler was blazing fast, it was easier to implement and learn and the features it lacked against Algol did not really matter most of the time (at the time) More features doesn't automatically means "better" Also Pascal had quite strong technical qualities, not very common among other contemporary languages edit: can I ask the reason for the downvote? I would really like to hear an opinion on what Pascal did wrong, having used it extensively in the late 80s until the end of the 90s and why my comment was awarded with a negative score.
adrian_b 2y ago
Moreover, they have already been proposed by John McCarthy in October 1964, 60 years ago, for inclusion in the successor of ALGOL 60, which makes even more weird the lack of widespread support. (And in fact Algol 68 had a better implementation than most later languages, but Algol 68 was missing completely any documentation suitable for newbies, like tutorials and programming examples, while not being promoted by any hardware vendor, like IBM or DEC, so it was doomed.)
- floxy 2y ago
  >The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors. https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hi...
debo_ 2y ago
ADT feels like an unfortunately acronym-collision with "Abstract data types."
- pjmlp 2y ago
  Yep, people that eventually buy a Modula-2 ADT book, when hunting old stuff, are in for a surprise. :)
  - debo_ 2y ago
    It's a term that is commonly used in computer science education to refer to any data type independent of its concrete implementation (so, basically, its interface.) I don't think it's just restricted to Modula-2?
    - pjmlp 2y ago
      Indeed, however CLU and Modula-2 were the ones used mostly for practical teaching purposes, until ML became widespread enough for ADT to gain yet another meaning.
  - mst 2y ago
    I just realised something terrible. This code is ADTs for C. At some point somebody's going to call it CADT and jwz will explode.
- jghn 2y ago
  More often than not, when I say ADT to someone outside of the FP world, they assume I mean abstract data type.
  - bee_rider 2y ago
    Or the company that sells the security stickers, for houses.
- keybored 2y ago
  ADT feels like an unfortunately acronym-collision with "algebraic data types." They were both introduced in the same decade.
Verdex 2y ago
NAND is a universal circuit primitive because it can be used to create all of the other circuit primitives. But if you think about it, this is more of an argument of manufacturing than it is in comprehensibility. Only needing to manufacture NAND is easy, but if you could only create your circuit this way, then you would have an unmaintainable mess. You can do the same thing with boolean logic and just have not-and, but thankfully we have and, or, not, xor. Similarly, you don't need greater-than-or-equal because you can just write 'x > y || x == y'. Comprehension is linked to how closely you can express the idea of what you're doing in the object language that you have to look at. It might be convenient to compile everything down to SK combinators so that your optimizer and evaluator can be simpler, but people should never look at that level (at least not until you suspect a compiler defect). So we get to object oriented programming. Where our data expression has an AND property (a class has an INT field AND a STRING field), an existential property (interfaces: there exists some object with these methods), and inheritance (a truly bizarre feature where we duck tape subtyping to a method and field grouping mechanism with a bunch of hooks). With interfaces and inheritance you can simulate both a universal property (generic) and an OR property. But because it's not a direct expression, we leave this giant gap for what people intended to happen to diverge from what actually happens. Especially after time passes, defects are found, and requirements change. [For example, when using interfaces to simulate an OR property, there really isn't any mechanism to let everyone know that this construct is closed. So if something erroneously gets added, you won't know to check the entire code base. And if requirement change and you need to add a new case, then you have to check the entire code base. Completeness checking of ADTs give you this for free in your pattern matches.] Too many non-trivial architectural messes that I've encountered in my career have been due to either someone trying to solve all of their problems with interfaces or the same with inheritance* when a simple OR data structure would have made everything simple, clear, and correct. [*] - Inheritance being more problematic when someone tries to create a non-trivially sized category hierarchy, which ruins the day when requirements change and suddenly the tree needs to be reorganized but doing so would invalidate entire swaths of the code base already accepting types with a different assumed (and undocumented) hierarchal tree structure. Thankfully most people have gotten the memo and switched to interfaces.
taeric 2y ago
I'm curious on supporting evidence for it being a basic mental model of how humans think? That sounds like a fairly strong claim.
- Verdex 2y ago
  I'm a huge proponent of ADTs being a more comprehensible way to write code than some of the alternatives. But I do have to agree with you that there isn't really evidence that this is a basic mental model. However What we do see is a bunch of mathematical disciplines that end up creating properties like: AND, OR, Universal, Existential, Implication, (and a few others). They end up in places like: set theory, type theory, category theory, various logics, lattice theory, etc. Now, maybe they're only copying one another and this is more of a memetic phenomena. Or maybe they've hit upon something that's important for human comprehensibility. That would be the 'evidence' of the positive effect of ADTs (scare quotes because it might just be math memes and not fundamental). But we can also think about what I feel is legit evidence for the negative effect of lacking ADTs. Consider what happens if instead of having the standard boolean logic operators and, or, not, xor, we only have the universal not-and operator. Now a straightforward statement like: A && B || C becomes (((A !& B) !& (A !& B)) !& ((A !& B) !& (A !& B))) !& (B !& B) [I think...]. It's more complicated to tell what's actually supposed to be going on AND the '&&' simulation can get intertwined with the '||' simulation. The result being that requirements changes or defect fixes end up modifying the object level expression in a way where there is no longer any mapping back to standard boolean logic. Comprehensibility approaches zero. And we've seen this happen with interfaces and inheritance being used to implement what would otherwise be a relatively simple OR property (with the added benefit that pattern matching ADTs often comes with totality checking; not something you can do with interfaces which can always have another instance even up to and including objects loaded at runtime).
  - taeric 2y ago
    Appearing in symbolic reasoning tools we have invented doesn't really support them being how brains work, though? This is akin to saying that gears are how nature works because gears are everywhere in how we build things. I could maybe buy that with "friction" being a fundamental thing, but feels like a stretch for the other. Now, I should add that I did not mean my question to be a criticism of them! I'm genuinely curious on evidence that they are a basic building block. Feels save to say they are a good building block, and those aren't the same thing. As an easy example for them not being basic building blocks, I can't remember ever seeing anything like them in any assembly instructions for things. Put together a batting net for the kids. Lots of instructions, but nothing algebraic, in this sense. Looking at recipes for food. Nothing algebraic, really? Maybe I can squint and see some, but it would be hard. Exercise plans? Music lessons? Playbooks for a sport? Again, though, I /do not/ intend this as a criticism of them. Genuinely curious on any investigation into them.
mgaunard 2y ago
C has always had them, it's called union. In practice you need to couple it with an enum, and your visitation mechanism is a switch statement. But C doesn't impose that on you and lets you do it as you see fit.
- duped 2y ago
  You're confusing semantics for implementation. The point of union and discriminated union types (not what C calls union) is to enable compiler checked pattern matching, which tagged enums in C plus a switch statement do not get you.
- estebank 2y ago
  Tagged unions + pattern matching is what gp wants. You can always encode whatever model you want using any programming language, but language features/ergonomics matter.
- coldtea 2y ago
  >C has always had them, it's called union It also has all the features of Haskell, since you can implement a Haskell compiler in C.
- naasking 2y ago
  That you can sort of simulate the skeleton of algebraic data types does not mean that C has algebraic data types. The whole point of the algebra part is that the syntax has a compositional semantics which is completely absent in C, unless you go to great lengths as with this macro header.
- bmoxb 2y ago
  That is not a proper alternative to real pattern matching.
- anon-3988 2y ago
  lol this is like saying C doesn't need structs, you can just declare the variables with a common prefix separately! See ma, product types!
CraigJPerry 2y ago
>> not having ADTs (except maybe Rust) built-in Most of the common languages today have product types. Java[1], Rust, Haskell, etc. have sum types. I think it gets a bit more escoteric beyond that though - i don't doubt that there's probably some haskell extension for quotient types[2] or some other category theory high-jinx. Most languages have ADTs built in. [1] https://blogs.oracle.com/javamagazine/post/inside-the-language-sealed-types https://blogs.oracle.com/javamagazine/post/inside-the-langua... [2] https://en.wikipedia.org/wiki/Quotient_type https://en.wikipedia.org/wiki/Quotient_type
- speed_spread 2y ago
  Java sum types work but still need a bit of syntax sugar on the declaration side, IMHO.
  - def_not_troll 2y ago
    [flagged]
- nextaccountic 2y ago
  Does Java sealed classes enable something like an exhaustive pattern matching? (A form of pattern matching that will fail at compile time if you add a new class that extends the sealed class)
  - thewakalix 2y ago
    > The intent is to introduce a more-advanced construction called pattern matching in a later release.
    - brabel 2y ago
      You read that in a blog post from 2019. Java has had comprehensive pattern matching since Java 21, like one year ago (current Java version is 22). I posted an answer to the same parent comment with the C example written in Java... You can read more about it here: https://www.baeldung.com/java-lts-21-new-features https://www.baeldung.com/java-lts-21-new-features
ajross 2y ago
> [Algebraic Data Types are] such a basic mental model of how humans think and solve problems I think that's actually wrong for "Sum types". Product types, sure. The idea of storing a bunch of fields in a single thing matches the way we've been organizing information since we started writing things down. But I genuinely don't think I've seen an attempt at a sum/union/enumerant/whatever syntax in a programming language that wasn't horrifyingly confusing. Where by extension: class-based inheritance is actually pretty simple to understand. The classic "IS-A" relationship isn't as simple as "fields in a struct", but it's not hard to understand (c.f. all the animal analogies), and the syntax for expressing it is pretty clean in most languages. Is it the "best" way to solve a problem? Maybe not. Neither are ADT sum types. But I think there's a major baby-in-the-bathwater problem with trying to be different. I really don't think, for the case of typical coders writing typical code, that ADTs are bringing as much to the table as the experts think.
- throwawaymaths 2y ago
  > class-based inheritance is actually pretty simple to understand Simple to understand, a nightmare to debug, as you'll be chasing where your data and data contracts across a ton of files.
  - ajross 2y ago
    That's a bit much. Type inheritance has been a core abstraction in software development since before most working developers were born. We as a society know how to do this. The idea that one oddball new idea is a revolution that turns a "nightmare" into sunshine is way too hyperbolized. Sum typing might be better! But frankly the jury is still out, and the impact is clearly going to be smaller than what you're imagining.
    - throwawaymaths 2y ago
      The new lowest level pls (zig, rust) have ditched class based inheritance. Higher level PLs are going more functional, to include JS, where entire frameworks are encouraging functional (not to mention how everyone complains about the opacity of trying to use inheritance in place of declarative i.e. Amazon CDK)
Alifatisk 2y ago
Isn’t ADT abbreviation for Abstract Data Type? Or does it depend in context nowadays?
- rowanG077 2y ago
  Context. It means algebraic data type here.
- Jaxan 2y ago
  You answered your own question: it depends and the context and is confusing imo. Both are very common in compsci
  - Alifatisk 2y ago
    No I didn’t, I provided two options and asked which case it was. I could’ve assumed OP had used the wrong abbreviation.
- drycabinet 2y ago
  Wait until you switch to unions in rust and ask yourself whether it is a union or a struct.
  - Alifatisk 2y ago
    Oh dear
Tainnor 2y ago
> except maybe Rust Swift, Kotlin and Scala all have had ADTs for a while, even Java has it now.
thesz 2y ago
"Haskell is the best imperative language," (C) various software engineers. Also, algebraic data types can be seen as hierarchy consisting of abstract base class and several final children classes. So it is an inheritance model, just restricted one.
epolanski 2y ago
May not be built in but many mainstream languages such as typescript have libraries or the tools to easily implement them.
deleted 2y ago
[deleted]

linkdd 2y ago

This is the work of a wizard. I've known C for almost 20 years, and never would I have thought the macro system was powerful enough to allow such black magic. This is awesome!

lupire 2y ago
ADTs are mostly string replacement on generic structs and unions, plus tagging on the union. It's not a complicated use of macros.
clnhlzmn 2y ago
You might also be interested in metalang99 by the same author.
CuriousCosmic 2y ago
Yeah xmacros (the style of macro use) are pretty fancy. "Classically" they are used for creating and accessing type safe generics or for reducing boilerplate for hardware register and interrupt definitions. They are kind of cursed but at their core they are actually incredibly simple and a reliable tool for reducing cognitive complexity and boilerplate in C based projects.
cl91 2y ago
> I've known C for almost 20 years The author is only 19 years old. I feel really dumb now.

tombert 2y ago

Interesting. Algebraic Data Types are almost always one of the things I miss when I use imperative languages. I have to do Java at work, and while I've kind of come around on Java and I don't think it's quite as bad as I have accused it of being, there's been several dozen instances of "man I wish Java had F#'s discriminated unions". Obviously I'm aware that you can spoof it with a variety of techniques, and often enums are enough for what you need, but most of those techniques lack the flexibility and terseness of proper ADTs; if nothing else those techniques don't have the sexy pattern matching that you get with a functional language. This C extension looks pretty sweet since it appears to have the pattern matching I want; I'll see if I can use it for my Arduino projects.

AlecBG 2y ago
Sealed interfaces in java 21 allow pattern matching
- tombert 2y ago
  Yeah I know, we just don't use Java 21 at work yet. I'm super excited for that update, and it actually looks like we will be transitioning to that by the end of the year, but I haven't had a chance to play with it just yet. I do find it a little annoying that it's taken so long for Java to get a feature that, in my opinion, was so clearly useful; it feels like they were about a decade later on this than they should have been, but I'll take whatever victories I can get.
  - brabel 2y ago
    If you can enable preview features, you can use pattern matching since Java 17 (though the final syntax in Java 21 was slightly changed - still you may want to use preview features, it's mostly fine in Java as they tend to change very little, and when you do upgrade, the compiler will tell you where you need to update your code).
lupire 2y ago
Kotlin is JVM compatible and has ADTs. Java has https://github.com/functionaljava/functionaljava https://github.com/functionaljava/functionaljava which is unsupported but stable.

jackling 2y ago

Could you not get most of the benefits of ADTs using structs + unions + enums? I've used the pattern where I had a union of several types and an enum to differentiate which one to pick. Something like std::variant seems to work a bit like a sum type. The only issue is you can't do a clean switch statement that matches on the specific value of a field, but nested switch statements aren't that messy.

acuozzo 2y ago
Yes, and you can also get many of the benefits of OOP with convention and discipline, but doing so requires you to frequently get down in the weeds since, e.g., vtables must be dealt with manually. The trouble with this approach is that there's a lot of mental overhead in dotting all of your i's and crossing all of your t's. It's draining, so you start to, e.g., shoehorn additional functionality into existing classes instead of making new ones. You eventually wind up perceiving the abstraction as costly which lessons your use of it at the expense of producing a more elegant solution to the problem(s) you're solving. tl,dr? The ability to just state "Darmok and Jalad at Tanagra" is transformative when the alternative is telling an entire story every time you want to reference a complex idea.
mattgreenrocks 2y ago
I generally don't mind C++ for most code when it's absolutely necessary, but I'm not a huge fan of std::variant. Using std::visit to exhaustively match all cases feels hacky. It really would benefit from being a first-class language feature. It's more impactful to a lot of day-to-day code than other things they've worked on, such as coroutines.
- TheBicPen 2y ago
  The 4th example at https://en.cppreference.com/w/cpp/utility/variant/visit https://en.cppreference.com/w/cpp/utility/variant/visit that uses a class template makes the feature a bit nicer, but still not as ergonomic as something like Rust.
naasking 2y ago
> Could you not get most of the benefits of ADTs using structs + unions + enums? The modelling aspects can be simulated, yes, but that's barely half of the benefits of ADTs. Pattern matching is a big ergonomic benefit.

samatman 2y ago

Let's say you have a C program to write, and you really want exhaustive pattern matching on the tags of unions (which is what Datatype99 provides: "Put simply, Datatype99 is just a syntax sugar over tagged unions"). Let's say further that you already know Rust exists, and aren't going to use it for reasons that anyone writing a C program already knows. At least consider Zig. Here's a little something I wrote in Zig two days ago: /// Adjust a label-bearing OpCode by `l`. No-op if no label. pub fn adjust(self: *OpCode, l: i16) void { switch (self.*) { inline else => |*op| { const PayType = @TypeOf(op.*); if (PayType != void and @hasField(PayType, "l")) { op.*.l += l; } }, } } This uses comptime (inline else) to generate all branches of a switch statement over a tagged union, and add an offset to members of that union which have an "l" field. You can vary the nature of the branches on any comptime-available type info, which is a lot, and all the conditions are compile-time, each branch of the switch has only the logic needed to handle that variant. "But my program is already in C, I just need it for one file" right. Try Zig. You might like it.

pajko 2y ago
Seems like Nim can be useful too, plus it compiles to C. https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62ea21f6 https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62e...
- brabel 2y ago
  In Nim, ADTs are painful still (as your example clearly shows), but they are working on adding proper ADTs to the language (I can't find where I read that, but I am sure I did!).
  - j-james 2y ago
    https://github.com/nim-lang/RFCs/issues/548 https://github.com/nim-lang/RFCs/issues/548
- samatman 2y ago
  I've been a Nim respecter for many years, it's slept on in general as a language. The difference here is that Nim compiles to C and you can turn the garbage collector off: Zig compiles C and there's no garbage collector. That means the entire standard library is available when generating object code. It's also trivial to opt-in to the C ABI on a fine-grained basis, by defining a function or struct with the extern keyword. I believe this is still fairly current about the difficulties of building Nim dylibs for C programs: https://peterme.net/dynamic-libraries-in-nim.html https://peterme.net/dynamic-libraries-in-nim.html I expect Nim will stabilize about where D has: it will have a dialect of the language which, with relatively painless accommodations, is able to produce object code which speaks C ABI. Zig is different. The language is relentlessly focused on providing a better alternative to C while occupying the same niche, and a lot of design time has been spent on making it practical to take an existing C program and start writing the new parts of it in Zig. It's a good language, Nim, and getting better. I'd recommend it for someone who is considering Go, for example.

otikik 2y ago

What a madlad. Kudos for implementing this.

KerrAvon 2y ago

Anyone considering using this should be strongly looking at using Swift or Rust instead. You can build almost any given language idea using the C macro preprocessor, but that doesn't mean it's a good idea to ship production code using it. The worst codebases to inherit as a maintenance programmer are the ones where people got clever with the C preprocessor. Impossible to debug and impossible to maintain.

392 2y ago
I find that most abuses of the preprocessor are by folks unwilling/unable to simplify their design into a form that's (a) native to the C language/runtime or (b) not repetitive to type. This library on the other hand addresses a nasty papercut whose presence usually stops folks with modern language experience from choosing C when it might otherwise be valid. Plus you can't beat C's long-term stability. Though I agree that 90+% who _think_ they still need C should probably move on to making Rust work for them, instead.
endgame 2y ago
C99 is a stable target for writing bootstrappable software: there are multiple mature compiler implementations, at least one of which is bootstrappable down to hex0, and the bootstrap chain is not too long.

mingodad 2y ago

There is also https://melt.cs.umn.edu/ https://melt.cs.umn.edu/ that has an extension that add templates and algebraic data types to C : https://github.com/melt-umn/ableC-template-algebraic-data-types https://github.com/melt-umn/ableC-template-algebraic-data-ty...

deleted 2y ago

[deleted]

WhereIsTheTruth 2y ago

Tagged Union is a must have in a programming language

modeless 2y ago

> PLEASE, do not use top-level break/continue inside statements provided to of and ifLet; use goto labels instead. Seems like a pretty big footgun. But otherwise, very cool.

linkdd 2y ago
goto is a footgun only if you use it to move from function to function, which btw was what "goto considered harmful" was about. That practice has disappeared, and now goto, within a function, is pretty harmless and quite identical to break/continue in fact.
- modeless 2y ago
  Goto isn't the footgun. The footgun is if you use break/continue by accident then some unspecified bad thing will happen, silently I'm guessing.
zzo38computer 2y ago
Using goto instead isn't a problem, but knowing not to use break/continue inside of such blocks is something that you will have to be aware of. I had written a immediate mode UI out of macros, and this reminded me of that although in my case it is not a problem, although some blocks are ones that you can use "break". For example, you can use "break" to exit out of a win_form block ("goto" also works), while a win_command block does not capture "break" so using break (or goto) inside of a win_command block will break out of whatever block the win_command is in (probably a win_form block; for example, this would commonly be used in the case of a "Cancel" button).
392 2y ago
What's neat about Rust is that in its macro land, writing the code that checked for this condition would be not only possible, but doable, imaginable, and aided by easily installable OSS libraries. So it's not just about being slightly better in some ways, but smoothing over so many paper cuts that it can be hard to see how they have added up overtime across ecosystems, like CPython and co having so many of its own vocab types, or HPC libs. For example, the problem with this macro that causes this wouldn't even be problems in a well written Rust macro. They're artifacts of smart people trying to work around C's limitations. But then the macro wouldn't have been written anyway because this is a port of a native Rust feature (which means it gets taken advantage of in community software).

klysm 2y ago

If I ever implement a product from scratch again, discriminated unions with compiler enforced exhaustive pattern matching is a hard requirement. It’s too powerful to not have.

nmfisher 2y ago
Union types are my biggest wish for Dart, but unfortunately it doesn't look like they'll be added any time soon. They've recently added support for compiler-enforced pattern matching over sealed classes, which I suppose does get you halfway there though.
actionfromafar 2y ago
What languages could fit that description today? I don't really understand what it even means but maybe I could understand better if I could look at examples in languages which have them.
- phi-go 2y ago
  For example Rust: https://doc.rust-lang.org/std/keyword.enum.html https://doc.rust-lang.org/std/keyword.enum.html
  - jghn 2y ago
    Also Scala
- seivan 2y ago
  Swift, Typescript depending on your opinion with structural typing, and Rust. Think Scala, Elm and Haskell have it as well. Having that and elixirs pattern matching would be insane.
seivan 2y ago
[dead]

drycabinet 2y ago

Wikipedia has something interesting on this (how unions can be implemented using "class hierarchy in object-oriented programming"): https://en.wikipedia.org/wiki/Tagged_union#Class_hierarchies_as_tagged_unions https://en.wikipedia.org/wiki/Tagged_union#Class_hierarchies... There is a lengthy blog post about the same stuff, except that the author doesn't seem to have come across the said wiki section yet: https://nandakumar.org/blog/2023/12/paradigms-in-disguise.html https://nandakumar.org/blog/2023/12/paradigms-in-disguise.ht... Kudos to the dev of datatype99 for showing the problem with such ad-hoc methods in the readme right away.

alpine32 2y ago
[dead]

rurban 2y ago

I certainly won't use that. It's not type safe, and doesn't even allow names for its pattern matching sugar. Why he calls this simple struct matching sugar via tagged unions "Algebraic Data Types" is beyond my understanding. He cannot even do nested structs nor unions. datatype( BinaryTree, (Leaf, int), (Node, BinaryTree *, int, BinaryTree *) ); No names for the struct fields, so you need to rely on the position. And then used: int sum(const BinaryTree *tree) { match(*tree) { of(Leaf, x) return *x; of(Node, lhs, x, rhs) return sum(*lhs) + *x + sum(*rhs); } // Invalid input (no such variant). return -1; } Where lhs, x, rhs magically match the types defined above. What a nonsense design!