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.
Everyone who hasn't used ADTs and pattern matching doesn't get what the big deal is all about. Everyone who is used to ADTs and pattern matching doesn't get what the big deal is all about, until they have to work in a language that doesn't have them. And everyone who just found out about them can't shut up about them being the best thing since sliced bread.
I have mainly used them in Rust. They are nice I suppose, but nothing mindblowing.
To me it feels very similar to an interface (trait) implemented by a bunch of classes (structs). I have multiple times wondered which of those two approaches would be better in a given situation, often wanting some aspects of both.
Being able to exhaustively pattern match is nice. But being able to define my classes in different places is also nice. And being able to define methods on the classes is nice. And defining a function that will only accept particular variant is nice.
From my perspective a discriminant vs a vtable pointer is a boring implementation detail the compiler should just figure out for me based on what would be more optimal in a given situation.
> I have multiple times wondered which of those two approaches would be better in a given situation, often wanting some aspects of both.
ADTs are closed to extension with new cases but open to extension with new functions, eg. anytime you want to add new cases, you have to update all functions that depend on the ADT, but you can add as many functions for that ADT as you like with no issues.
Traits are open to extension with new cases but closed to extension with new functions, eg. you can add as many impl as you like with no issues (new cases), but if you want to add a new function to the trait you have to update all impl to support it.
They are logical duals, and the problem of designing systems that are open to extension in both cases and functions is known as the expression problem:
I suppose this is a genuine dichotomy, but I feel like it’s missing a more critical difference: ADTs cleanly represent data, even when nothing can be, or needs to be, extended from outside.
For example, a result is a success value or an error. A stock order is a market order or a limit order, and nothing else, at least until someone updates the spec and recompiles the code. Situations like this happen all the time. I don’t want to extend a result to include gizmos in addition to success value or errors, nor do I generally want to extend the set of functions that operate on a certain sort of result. But I very, very frequently want to represent values with a specific, simple schema, and ADTs fit the bill. A bunch of structs/classes, interfaces/traits and getters/setters can do this, but the result would look like the worst stereotypes of enterprise Java code to accomplish what a language with nice ADTs can do with basically no boilerplate.
> For example, a result is a success value or an error. A stock order is a market order or a limit order, and nothing else, at least until someone updates the spec and recompiles the code.
But that's just it, specs are rarely complete because reality is fluid. For example, a result is a success or an error, until maybe you want an errors to prompt the user to correct something and then the computation can be resumed (see resumable exceptions).
Should you even have to recompile your code to handle new cases? Why can't you just add the new case, and define new handlers for the functions that depend on your ADT without recompiling that code? That's the expression problem.
> And defining a function that will only accept particular variant is nice
This is possible to achieve (or hack your way through, if you will) by parameterizing the type and using a nullary type (a type which is impossible to have) to exclude specific cases of a sum type. In Haskell this would look like this:
data Weather a b c = Sunny a | Rainy b | Snowy c
-- can't snow in the summer!
onlySummerWeather :: forall a b. Weather a b Void -> String
onlySummerWeather weather = case weather of
Sunny _ -> "Got sunny weather"
Rainy _ -> "Got rainy weather"
Snowy v -> absurd v
where `absurd :: forall a. Void -> a` "if you give me something you can't ever have, I will give you anything in return".
Enums are closed sets and trait objects are open sets. They are conceptually related concepts, but the language puts syntactic distance between the two, and I don't think it should.
There are lots of open design questions for every feature you propose, but all of them have been discussed and have higher or lower chance of making it into the language.
which would let you get around the problem of returning a type erased object for a Trait that isn't object safe:
trait Trait {
const C: i32 = 0;
}
impl Trait for i32 {}
impl Trait for &'static str {}
fn foo() -> Box<dyn Trait> {
if true {
Box::new("")
} else {
Box::new(42)
}
}
error[E0038]: the trait `Trait` cannot be made into an object
--> f500.rs:6:17
|
6 | fn foo() -> Box<dyn Trait> {
| ^^^^^^^^^ `Trait` cannot be made into an object
|
note: for a trait to be "object safe" it needs to allow building a vtable to allow the call to be resolvable dynamically; for more information visit <https://doc.rust-lang.org/reference/items/traits.html#object-safety>
--> f500.rs:2:11
|
1 | trait Trait {
| ----- this trait cannot be made into an object...
2 | const C: i32 = 0;
| ^ ...because it contains this associated `const`
= help: consider moving `C` to another trait
= help: the following types implement the trait, consider defining an enum where each variant holds one of these types, implementing `Trait` for this new enum and using it instead:
&'static str
i32
---
Relax object safety rules, like making all assoc consts implicitly `where Self: Sized`.
---
We could make enum variants types on their own right, allowing you to write
There's some work on this, under the umbrella of "patterns in types". For now the only supported part of it is specifying a value range for integers, but will likely grow to support arbitrary patterns.
---
Having a way to express `impl Trait for Enum {}` when every `Enum` variant already implement `Trait` without having to write the whole `impl`.
---
Anonymous enums:
fn foo() -> Foo | Bar | Baz
---
Being able to match on Box<dyn Any> or anonymous enums
match foo() {
x: Foo => ...,
x: Bar => ...,
_ => ...,
}
---
Stop needing to create a new struct type in order to box a single variant
enum Foo {
Bar(Box<struct { a: i32, b: i32 }>),
}
---
These are of the top of my head, there are many things that you can do to make trait objects and enums feel closer than they do today, to make changing the way your code works a "gradient" instead of a "jump". My go-to example for this is: if you have a type where every field is Debug, you can derive it. As soon as you add one field that isn't Debug, you have to implement the whole impl for your type. That's a "jump". If we had default values for structs you could still use the derive by specifying a default value in the definition. That makes the syntactic change "distance" be as far as the conceptual change "distance".
> To me it feels very similar to an interface (trait) implemented by a bunch of classes (structs)
Then you might not fully grok sum types yet.
> From my perspective a discriminant vs a vtable pointer is a boring implementation detail the compiler should just figure out for me based on what would be more optimal in a given situation.
Disagree. It's a design choice that should be decided by the programmers. There's a tradeoff—choosing which should be easier: adding a new variant or adding a new function/method. It's called the Expression Problem: https://wiki.c2.com/?ExpressionProblem
That's because Go is intentionally clunky and awkward in the name of "simplicity". IMO it's charming to some degree, but it's far from perfect and I think you'd need some pretty serious threats to get me to describe it as "elegant" in any way.
Rust somehow has more elegance than Go, if only in small parts. Nothing compares to Scheme in the elegance category IMO :)
My view of Go went from being annoyed to "they picked their tradeoffs carefully and consciously and then leaned into them hard to squeeze every ounce of upside out of them" and while it's still not really my preferred aesthetic I now have a lot of respect for the design as a design process.
Meanwhile, getting addicted to scheme many years ago is a lot of why I still mostly write perl, I need 'my' (i.e. expression/block level scoping and you actually have to declare your variables to scope them before use) and closures for the style of programming I like to do.
Rules out python, ruby, and pre-ES6 JS, though JS with 'let' and arrow functions is pretty survivable and will be even more so if the 'do' and 'match' proposals land.
(note: I know go has :=, and while I'm ambivalent about the syntax, the semantics are pretty much what I expect; the above was talking about scripting class languages though hence not mentioning it there)
Despite what I may have made it seem, I actually quite like Go as a language, I just wouldn't call it elegant or pretty (though certainly not as ugly as some other languages out there), but it's very pragmatic.
It's been a long time since I've written any Perl, but I can say I don't care for it as much as I do Lisps in general.
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.
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).
Sure, and Scala has had ADTs since its inception as well I think, and that's also JVM. It's not ADTs, but Clojure does have some level of pattern matching/destructuring as well.
It wasn't that I though that the JVM was incapable of doing something like an ADT, just that vanilla Java didn't support it. While it's easy to say that "companies should just use Kotlin", that's a bit of a big ordeal if you already have a 15 year old codebase that's written in Java.
I've heard of but never used the Functional Java library, though it'd be a tough sell to get my work to let me import a library that hasn't been updated in two years.
> that's a bit of a big ordeal if you already have a 15 year old codebase that's written in Java.
JetBrains has prioritised compatibility with Java and it shows. Of course, there are some gotchas (such as nullability or checked exceptions which don't exist in Kotlin), but you can really mix Kotlin and Java code relatively freely.
Java 21's pattern matching (you don't need functionaljava, and shouldn't really use that unless you're really into FP) is kind of nicer than Kotlin's, because you can automatically "destruct" records in your matches.
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.
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.
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.
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?
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.
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).
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).
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.
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.
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 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.
I think this is all true. Though with regard to your earlier example, it should be noted that Nim, too, has an extraordinarily powerful compile-time programming system: but it takes the form of typed macros and generics (as opposed to Zig's dislike for such abstractions).
The difference here is that there aren't C programmers who don't know about Rust, and since they're writing C, they have reasons they aren't using it. The same is not true of Zig. Some of the reasons not to be using Rust may be applicable (no specification comes to mind), others may not be.
I do agree that, on an even playing field, Nim should be considered when any of Rust, D, C++, or Go, are on the table. This is less true of C, and therefore, Zig. There's a difference between something being possible, and something being easy and pleasant.
There are also people using C, who really should be using some other language. Which is, in that case, probably not Zig. When you understand that C is the rational choice for some sorts of programming, you'll understand why Zig is a contender, in a way that the other languages we're discussing are not.
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!).
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.
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.
Yes TFA is pretty close, but note that it's not just "structs + unions + enums" getting you "most of the benefits", which is what I was responding to. There's a buttload of macros hiding allocation and switch statements.
The absolutely critical thing is to have checked every alternative when dealing with a sum type value. This is hard to do with macros, though not impossible (basically you'd need a macro to start a matching context and which introduces a variable in which to keep track of all the alternatives checked, then you need to arrange for the end of the matching context to check that all alternatives were checked).
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.
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.
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.
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.)
>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.
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]):
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.
This is where I like to cite Dijstra's "Go To Statement Considered Harmful".
What a lot of people miss about that paper is that he wasn't just talking about goto statements. He was also making a more general observation about how more powerful and general programming language features are not necessarily desirable, because they tend to adversely impact developer productivity.
The reason I, as a user, prefer structured control flow statements over goto is not that I believe they are powerful. It's precisely because they are less powerful. The resulting constraints on how the program can be structured make it easier for me to read and reason about existing code. That makes maintaining code easier. It also makes optimization and static analysis easier. And it makes writing tests easier, too.
I have similar feelings about ADTs. The reason I prefer them to other ways of doing composite data types is not that I think they're more powerful. It's that they create constraints that tend to reduce the semantic complexity of the domain models people create in programming languages that use them. And that makes my job easier.
The corollary to that, though, is that I'm not actually all that hype about adding ADTs to existing languages. For reasons that are similar to how the mere availability of structured, reentrant function calls is small consolation in a codebase that's already riddled with goto statements. The real win doesn't come from using ADTs, it comes from not having to worry about all those other confusing overpowered things that aren't ADTs.
That's exactly where I am. Pattern matched sum types "feel great" to code in to an expert because they are a concise and reasonably tight way to express the otherwise boring "enumerate over possibilities" code.
But they're hard to read for anyone who isn't an expert on not just the language but the type in question (c.f. Rust's Option() idioms all looks like line noise to newbies, etc...). And that's a bad trade.
In essence, this stuff is just Perl all over again. It's a language feature that prioritizes concision over comprehension. And I say that as someone who really likes coding in perl. But "people" don't like perl, and the community moved on, and the reasons are... the same reason that uptake in ADTs is lagging where the experts want it to be.
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!
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.
Of course the syntax sugar is a good thing if it makes it easier to write the code, but if the question is about "expressive power of the type system", it's not really relevant: Zig's type system can properly express a sum type. In addition: pattern matching is orthogonal to ADT, you can have pattern matching in both languages with and without algebraic types. Neither one implies the other.
I once explored the Epigram dependently typed programming language. It used to preclude many types of free form pattern matches, due to heavy dependence on structured editor (you speciy a type, it generates pattern matching, you cannot change the structure), so it was almost completely unuseable for many, many tasks.
So, while you are formally right, the need of shortcuts in pattern matching is undeniable to me.
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?
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.
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.
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)
sealed interface BinaryTree {
record Leaf(int value) implements BinaryTree {}
record Node(BinaryTree lhs,
BinaryTree rhs,
int value) implements BinaryTree {}
}
public class Hello {
static int sum(BinaryTree tree) {
return switch (tree) {
case BinaryTree.Leaf(var value) -> value;
case BinaryTree.Node(var lhs, var rhs, var value) -> sum(lhs) + value + sum(rhs);
};
}
public static void main(String... args) {
var tree = new BinaryTree.Node(
new BinaryTree.Leaf(1),
new BinaryTree.Node(
new BinaryTree.Leaf(2),
new BinaryTree.Leaf(3),
4),
5);
System.out.println(tree);
System.out.println("Sum: " + sum(tree));
}
}
If you added a new subtype to BinaryTree you would need to fix the switch.
EDIT: I didn't handle the `null` case above... so it would be a NullPointerException if someone passed null... apparently, Java decided to make handling `null` optional. More information: https://www.baeldung.com/java-lts-21-new-features
It absolutely does. Here is a (modified) snippet of my Java code from yesterday.
final boolean hasUncollectedSecret =
switch (each)
{
case Wall() -> false;
case Goal() -> false;
case Player p -> false;
case BasicCell(Underneath(_, var collectible), _)
->
switch (collectible)
{
case NONE, KEY -> false;
case SECRET -> true;
};
case Lock() -> false;
};
Java's sealed classes are still somewhat more limited than Rust's or Haskell's sum types, in that each instance of the superclass holds a fixed variant (i.e., subclass), so you can't change the variant without creating a new instance. Clearly, this limitation is necessary for references to stay intact, but I've personally ran into this issue when trying to represent a sum type in an ORM.
#[derive(Debug)]
pub enum Example {
Foo(i32),
Bar(&'static str),
}
let mut ex: Example = Example::Foo(42);
println!("{ex:?}"); // Foo(42)
let ex_ref: &mut Example = &mut ex;
*ex_ref = Example::Bar("hello");
println!("{ex:?}"); // Bar("hello")
Given a mutable reference to a value of enum type, you can replace it with another variant. Or you can swap it out with any other value of the same type, even if the variants are different. This is most commonly used for Option<T>, where you can insert or remove the contained value as long as you have a reference.
The limitation here is that for as long as the mutable reference is live, no other code can access the value. So when you do change the variant, you can't have any other references sitting around that point to the removed subfields.
This doesn't have anything to do with ADTs. It's because Rust has both in-place variables and references. You aren't changing the variant of an existing ADT, you're replacing the entire ADT value with a new one. That replacement is visible in multiple places because the language allows you to take references to variables (the `&mut ex` expression).
You can accomplish the same thing in C and C++ because they also have in-place value semantics and allow you to take the address of any variable. You can't do that in Java only because Java doesn't let you take references to variables.
I don't really think it's useful to do that though?? Can you give an example?
By the way, I would claim Java's sum types are less limited than Rust because in Rust, variants don't have their own type. The consequence is that you can't have functions that only accept some variant, as far as I know (I remember having this problem once), or add "methods" only to one variant... while in Java, because variants are just normal types, you can do both, and doing that is pretty damn useful.
> I don't really think it's useful to do that though?? Can you give an example?
For an exercise, I had to write a system with Admins and Customers, with the ability to upgrade a Customer into an Admin, or vice versa.
My thought was to put them as two subclasses under a User superclass, so that I could put them under a single Users table, and not have to link and unlink things over the conversion. Hibernate ORM supports storing subclasses by adding an implicit discriminator field.
However, its object model specifies that a single row always corresponds to a particular instance, so it has no support for changing the subclass of a row. Ultimately, I ended up with a hacky solution of creating a new record with the primary key copied over.
> By the way, I would claim Java's sum types are less limited than Rust because in Rust, variants don't have their own type. The consequence is that you can't have functions that only accept some variant, as far as I know (I remember having this problem once), or add "methods" only to one variant... while in Java, because variants are just normal types, you can do both, and doing that is pretty damn useful.
At least in Rust, you can simulate this pretty trivially by having each variant store a struct value with all the data and methods you want. See proc_macro::TokenTree [0] for an example of this. Of course, it's not ideal in how verbose it is (though not much worse than Java!), but it can be workable on the consumer's side if you add some extra From impls.
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.
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?
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.
> [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.
> 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.
Syntaxes like: `A | B(Int) | C(String)`. That means A, B, or C.
> 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
This value is either `A`, an Int (`B(Int)`) or a String (`C(String)`). Or: this knapsack either contains an A, B, or C. Difficult?
> (c.f. all the animal analogies),
Reminds me of the fact that software isn’t typically as static as animal taxonomies.
> and the syntax for expressing it is pretty clean in most languages.
I’m most used to Java where you spread `extends` over N files. (Sealed classes in Java is an exception.)
It’s fine. I don’t understand how it is particularly clean.
> Is it the "best" way to solve a problem? Maybe not. Neither are ADT sum types.
Is this an argument? ’Cause I don’t see it.
> But I think there's a major baby-in-the-bathwater problem
Inheritance is something that needs to have some concrete implementation affordance. Baby in the bathwater? I don’t see how you bolt this onto the struct model in a way that gets out of the way for people who don’t want to use it (the zero-cost-abstraction (in the if you don’t use it sense) is important to some low-level languages).[1]
Maybe the designers of hypothetical language X thinks that algebraic data types is enough. What baby are you missing then?
[1] For algebraic data types: structs are straightforward enough. While the “sum type” can be implemented by leaving enough space for the largest variant. That one-size-fits-all strategy isn’t perfect for all use-cases but it seems to have been good enough for Rust which has a lot, a lot of design discussions over minutiae.
> trying to be different.
With a technology from the ’70s. I also saw your “one oddball new idea is a revolution” snark. You’re clearly being very honest.
FWIW, I'm talking about the pattern matching syntax required to enforce coverage of all the sum types. Obviously the idea of the representation as a set of alternatives is easy enough to understand. The idea of "Now You Have To Show The Compiler You Know What To Do In All Circumstances" is very much not, c.f. how much basically everyone struggles with Option() in Rust.
Inheritance addresses similar issues by delegating the responsibility, something that is easy to understand. Does it have downsides? Sure. But I'm not sold that ADT has the advantage here at all.
> 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.
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.
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)
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).
> 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.
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.
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.
"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.
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).
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.
I think you're right to point out that it's too strong a claim to say that sum types are a basic building block of thought, although I believe they are very useful in coding regardless of that claim.
There is the still the ongoing debate about how much human perception and human reason are shaped by cultural forces vs. universal forces (where the latter asserts humans reason in the same/similar ways).
There's evidence that certain optical illusions don't work across cultures for example (I seem to remember those in Western countries have a tendency to mentally group things in rectangular boxes). The exact balance between cultural and universal forces isn't known and I doubt we could say anything about sum types in that regard.
Verdex's explanation is detailed but too long IMO. The short version is that ADTs/sum types formally correspond to the OR-logical connective, and records/product types formally correspond to AND-logical connective. I think you'd be hard-pressed to argue that people don't think in terms of "X AND Y OR Z". These are core primitives of any kind of reasoning.
I can easily argue that people don't think in terms of boolean logic. For one, the evidence seems as strong that people generally think backwards from the answer far more than they do forwards from the ingredients. This is often why new things are so long to be discovered. It isn't that people couldn't have gotten there, but they didn't know to go for it.
For two, addition is a wildly disparate thing everywhere we use it. We like to joke that computers made that hard, but literally half of intro chemistry is learning how to get thing to add together in a meaningful way, no? Balancing a chemical equation is a thing.
> For one, the evidence seems as strong that people generally think backwards from the answer far more than they do forwards from the ingredients.
Logic doesn't really have a direction, it works backwards or forwards. Even if you're solving a system "backwards", whatever that means, you still have to satisfy all of the necessary AND and OR constraints for a solution to be valid, so you're effectively still building ADTs or records just using a different evaluation order.
And this logic is how folks convince themselves that ball players are doing trigonometry when playing. It is just wrong.
You can /model/ it that way. But you are making a symbolic model to justify how a solution is reached.
Now, it can be frustrating to consider that this model could produce an agent that is better at the ball game than the players. But it is silly to think that means you have mirrored them.
> Logic doesn't really have a direction, it works backwards or forwards.
Implication is one of the primitives in logic, and gives us several of the classic logical fallacies: affirming the consequent, denying the antecedent, fallacy of the converse, and fallacy of the inverse.
All of which are examples of trying to work logic as though it doesn't have a direction.
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.
Doesn't look too bad particually the match tagged version last:
MyType= (Scalar4, Real4, NullTerminatedStringC);
MyUntaggedRecType=
RECORD
CASE MyType OF
Scalar4: (longC: ARRAY[1..150] OF longint);
Real4: (floatC: ARRAY[1..150] OF real);
END;
MyTaggedRecType=
RECORD
CASE tag: MyType OF
Scalar4: (longC: ARRAY[1..150] OF longint);
Real4: (floatC: ARRAY[1..150] OF real);
END;
...
{ set all to 0.0 without running through the MC68881 }
FOR j := 1 TO 150 DO
longC[j]:= 0;
...
CASE tag OF
Scalar4: percentReal = longC[1];
floatC: percentReal = floatC[1]*100;
ELSE
percentReal = 0.0/0.0;
edit: don't have a pascal compiler handy, but that's the idea
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.
Algol 68 may have been a failure because it was ahead of its time, which meant it was hard to write a compiler for it. For example, Algol 68 had closures (apparently Knuth snuck them in).
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.
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.
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.
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.
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.
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.
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.
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.
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.