13 ms·

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 thin

• 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??
            • hexane360 2y ago
              This often comes up when writing a function which returns a wrapper over a generic type (like Option<T>). If your Option type is T | null, then there's no way to distinguish between a null returned by the function or a null that is part of T. As a concrete example, consider a map with a method get(key: K) -> Option<V>. How do you tell the difference between a missing key and a key which contains `null` as a value?
              • brabel 2y ago
                This is trivial to model by making your type `T | null | Missing`.
                • efnx 2y ago
                  Maybe trivial to “work around” but there is a difference, ay? With this type you would have to check/match an extra case! The type you use there also takes more memory than Option<T> or Maybe<T>. So it has some other downsides.
                • epolanski 2y ago
                  Or just using Option since you would have Some<null> or None in that case.
                • 2y ago
    • chem83 2y ago
      F# too. And Elm. But I get your point.
  • chongli 2y ago
    While this is a step up from C, it is still a long way from the full power and generality of algebraic data types. The key word here is algebraic. In a language with ADTs, such as Haskell, you can pattern match on an arbitrarily complex types, not just the outermost tag. A contrived example (from [1]): contrived :: ([a], Char, (Int, Float), String, Bool) -> Bool contrived ([], 'b', (1, 2.0), "hi", True) = False To achieve a result like this using Zig's switch syntax would seem to involve a huge amount of boilerplate code and nested switch statements. [1] https://www.haskell.org/tutorial/patterns.html https://www.haskell.org/tutorial/patterns.html
    • Hirrolot 2y ago
      This is more of syntax sugar than power and generality, since nested pattern matching can be mechanically translated into "top-level" matching (e.g., see [1] and [2]). [1] L. Augustsson. Compiling Pattern Matching. In Functional Programming Languages and Computer Architecture, pages 368– 381, 1985. [2] P. Wadler. Efficient Compilation of Pattern Matching. In S.L. Peyton Jones, editor, The Implementation of Functional Programming Languages, pages 78–103. Prentice Hall, 1987.
      • chongli 2y ago
        This argument is the most common fallacy I see in programming language discussions. I might as well give it a name right here: "Turing equivalence fallacy" or perhaps "syntax sugar fallacy." All Turing Complete programming languages are Turing equivalent to one another. Programs written in one language can be mechanically transformed into those written in another. This is irrelevant to the discussion of programming languages. The whole point of creating different programming languages is to explore different ways to express the same program!
        • Hirrolot 2y ago
          In programming language design, we tend to distinguish between global and local analysis. While type checking and elaboration is an example of global analysis, desugaring is inherently local to some piece of code. Therefore, "power" or "expressiveness" usually mean that something cannot be syntactically "expanded"; e.g., while type classes elaborate into explicit dictionaries, they still require information from the type checker, and therefore considered a "real" feature of a programming language. On the other hand, nested pattern matching can be formulated as local syntax transformation, and therefore it doesn't bring anything fundamentally new to the type system or dynamic semantics. There's also a great talk on the matter [1], if somebody is interested in formalities. [1] https://www.youtube.com/watch?v=43XaZEn2aLc https://www.youtube.com/watch?v=43XaZEn2aLc
• 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]