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.
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.
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.
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.
That's kind of greek to me, but shouldn't promising the compiler that my set is closed unlock more features instead of taking features away?
I'm not sure I understand your point, but I'll elaborate on ways that we could "homogenize" the two features:
---
We could add implicit enums to impl Trait, so that you could return different types from a function:
fn foo() -> enum impl Display {
if rand() > 0.5 {
"str"
} else {
42
}
}
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
fn foo() -> Result<i32, i32>::Ok { Ok(42) }
let Ok(val) = foo();
---
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".
A trait is a collection of variants that may or may not have unknown members. An enum is a collection of variants that may not have unknown implementations. So enums are in some sense a subset of traits. Hence every property of traits is also a property of enums. Does that make sense?
Those suggestion of your look interesting, but I haven't thought them through enough to have an opinion.
They are conceptually related concepts, but the language puts syntactic distance between the two, and I don't think it should.
Haskell's type classes are a bit like Rust's traits. Type classes are open by default, but optionally can be closed off.
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.
I want more syntax sugar for my ADTs that mirror what traits have. I don't need that kind of double extensibility.
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
I would be so tempted to name the variable 'ity' instead of 'v'.
By floating the forall., we get another representation type for Void (forall a. a) and `absurd' is one half of that isomorphism :)
absurd :: Void -> (forall a. a)
drusba :: (forall a. a) -> Void
drusba void = void @VoidYou might be interested in taking a look at OCaml's extensible sum types which may straddle the line in the way you're describing.
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
I’m in the latter camp (from Ocaml) and now using Go. Go feels clunky and awkward.
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.
Many people don't care for it, and I made peace with that many moons ago; personally, I'm quite fond of what I'd call 'applications perl', which at least when I write it tends to be a mixture of OO and function composition type code with as much of the state as possible pushed to the outer edge (plus async for I/O if applicable), etc.
It barely feels like the same language as sysadmin scripts are written in, it just happens to share a compiler and a VM.
... and it doesn't exactly even share syntax since perl supports libraries defining their own keywords, e.g. while I won't be surprised if somebody makes it a feature of the VM eventually, our async/await is currently provided by https://metacpan.org/pod/Future::AsyncAwait and as you can see at https://metacpan.org/pod/Future::AsyncAwait#WITH-OTHER-MODUL... there's quite a few other useful ones out there.
Of course, many people complain vociferously about the idea that you have to use *libraries* to get syntax, but as somebody who still loves scheme I regard the ability to build the language up towards the problem to that extent to be a feature.
My first ever cpan release was making continuations pass back out to perl as a subroutine reference from Guile so I could write linear top level logic in scheme and use continuation capturing to sit that atop an event driven I/O stack - axisofeval.blogspot.com's lispx (https://github.com/lispx/lispx/) provides an fexpr based lisp that does similar for JS.
(trying to think of a good example of perl code of mine that shows an example of this is annoying me because I don't have any public code right now that's new enough for me to not have already decided I don't like it anymore ;)
Scheme (and by Scheme, I mean Racket, I guess) is nice, but it's not particularly elegant compared to eg Haskell.
Kotlin is JVM compatible and has ADTs.
Java has https://github.com/functionaljava/functionaljava
which is unsupported but stable.
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.
For Java, see https://www.baeldung.com/java-lts-21-new-features
Kotlin's: https://www.baeldung.com/kotlin/when
Make up your own mind.
kind of nicer than Kotlin's, because you can automatically "destruct" records in your matches.
I find positional destructuring of records a bad idea.
Sealed interfaces in java 21 allow pattern matching
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).
Algebraic Data Types are almost always one of the things I miss when I use imperative languages.
Algebraic data types and pattern matching actually work really well in imperative languages, too. See eg Rust.
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;
}
},
}
}
"But my program is already in C, I just need it for one file" right. Try Zig. You might like it.
Seems like Nim can be useful too, plus it compiles to C.
https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62e...
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
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.
Let's say further that you already know Zig exists, and aren't going to use it for reasons that anyone writing a C/Rust/D/C++ program already knows.
At least give Nim a try.
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.
Maybe I’ll understand one day.
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).
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!).
At least consider Zig.
Considered the example given. Now my eyes hurt. I think I started appreciating Lisp more.
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.
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.
TFA gets pattern matching.
The critical thing is that the compiler (or macro system) needs to check that you've checked all the alternatives.
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.
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.
The 4th example at 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.
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).
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.
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.
For example Rust: https://doc.rust-lang.org/std/keyword.enum.html
Also Scala
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.
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.
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.
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.
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.
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).
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!
ADTs are mostly string replacement on generic structs and unions, plus tagging on the union. It's not a complicated use of macros.
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.
You might also be interested in metalang99 by the same author.
I've known C for almost 20 years
The author is only 19 years old. I feel really dumb now.
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.
I have a star on your repository, so it seems I was looking into it while designing Datatype99 :)
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?
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.
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 *)
);
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;
}
What a madlad. Kudos for implementing this.
There is also 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-ty...
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...
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.ht...
Kudos to the dev of datatype99 for showing the problem with such ad-hoc methods in the readme right away.
Tagged Union is a must have in a programming language
Zig is a modern imperative programming language with ADTs: https://ziglang.org/documentation/master/#Tagged-union
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]):
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
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 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.
[1] https://www.youtube.com/watch?v=43XaZEn2aLc
You're approaching this from a PL design standpoint where the distinction is important, but from a user perspective it doesn't matter if it's just "syntax sugar" or if it's a super complicated to implement all that matters is whether the feature is available or not.
Typing features affect the way we design APIs. Libraries written in languages with type classes and without them can have completely different designs. If nested pattern matching is not available, this will not affect the APIs, only the function bodies -- because desugaring is local by definition.
That doesn't matter in practice. If two programming languages have the same underlying feature but one has syntactic sugar to make it very easy to use and the other does not (so is quite cumbersome to use) then you'll find that the library ecosystem for the former language will see the feature in widespread use whereas the ecosystem of the latter will tend to shun the feature.
This is one of the social factors of programming language design and it's one of the main reasons successful programming languages work so hard to establish a coherent philosophy and a set of best practices or idioms within the language. For similar reasons, I believe this is why "anything goes" languages such as LISP have struggled to gain widespread adoption: with no philosophy every programmer becomes an island unto themselves.
There are already two misconceptions.
First: "Lisp has no programming philosophies" and styles.
Not every program starts by zero. Since Lisp exists since the end 1950s, it has seen quite a lot in programming styles over the years and it may contain traces of several. Generally it may support more than one programming paradigm. For example during the Common Lisp standardization there was a wish to have a standardized object system. So instead of the multiple possible approaches (actors, message passing, prototype-based, ...), Common Lisp has just one: CLOS, the Common Lisp Object System. So, much of the object-oriented code written in CL is implemented in one particular object system: CLOS. Object Lisp, Flavors, LOOPs, Common Objects, and a bunch of other once had thus been replaced by one standard.
CLOS also defines a bunch of user-level macros: DEFCLASS, DEFMETHOD, DEFGENERIC, ... Everyone using CL & CLOS will use those macros.
Second: "every programmer becomes an island unto themselves". If we look at the way CLOS was designed: there was a core group of six people from three companies. Around that there was a mailing-list based communication with a large group of interested people. Early on a prototype was implemented as a portable implementation of CLOS. This was widely distributed among interested parties: implementors, companies, research groups, ... Then reports about the language extension and its layers were published, books were published, application & library code was published.
One of famous books coming out of this effort: "The Art of the Meta-Object Protocol". It contained also a toy implementation of CLOS in Common Lisp. Book and the implementation of CLOS (both the larger prototype and the toy implementation) showed in excellent quality how to write object-oriented Lisp code.
https://mitpress.mit.edu/9780262610742/the-art-of-the-metaob...
So, there are communities, which share code and coding styles. Not every programmer is alone and starts from zero.
First: "Lisp has no programming philosophies" and styles
You misquoted me. I said no philosophy, singular. In the programming language context, a philosophy is a convention or a standard. Just as many standards implies that there is no standard, many philosophies implies no philosophy.
Everything else you said is evidence for my premise. Hire 3 different programmers, one from each of the communities, and you might as well have 3 different programming languages. That’s not a standard. That’s not a philosophy. That’s anything goes!
That makes no sense.
Maybe not. They build on the same foundation, a language with a large standard, which is largely unchanged since three decades. A language which can be incrementally extended, without invalidating the rest. A language where extensions can be embedded, without invalidating the rest of the language or its tools. Many projects use SBCL (now itself 25 years old and only incrementally grown) and a bunch of core libraries for it.
Most languages support widely different software development practices. Take JavaScript: it includes imperative, object-oriented and functional elements (similar to Lisp). It has huge amounts of competing frameworks (many more than any Lisp), where many of them have been superseded and many of them are built on a multitude of other libraries. The developer can pick and choose. Each projects will be different from other projects, depending on which libraries and programming frameworks it uses - and which of those the developer re-invents.
Any half-way powerful language (C++ -> templates, Ruby -> meta objects, Java -> objects & byte code & reflection & class loader, Smalltalk -> meta objects, Rust -> macros, C++ -> language interpreters, Java -> external configuration languages, C -> macro processor, ...) has ways to adapt the language to a certain style & domain.
Any large Java framework defines new standards, new configuration mechanisms, new ways to use new Java features (lambdas, streams, ...). See the large list of features added to the Java language over time: https://en.wikipedia.org/wiki/Java_version_history For many of them there were competing proposals. Each Java code base will use some subset/superset of these features, depending on what is needed and what the personal preferences are. And then the Java architect in the project will not be satisfied and will invent yet another configuration system, this time not using XML or JSON for the syntax, but develop a new embedded scripting language for the JVM and integrate that with his software. I have seen Java architects which eventually didn't understand their own configuration system any more.
If you think a language like Common Lisp is special here, then in reality it is not. It's just slightly different in that it has extensibility as one of its philosophies and provides defined interfaces for that. There is one macro mechanism, which is powerful enough, that for decades it has not been replaced. Every syntactic extension mechanism will use this macro system, which is documented, stable and widely used.
There is rather no evidence for your premise.
Most of the Common Lisp code that is accessible via public repositories conforms to conventions and is understandable.
Lisp programmers are highly motivated toward encouraging collaboration, since there aren't that many people in Lisp where you can afford to be turning people away toward projects that are easier to get into.
Also, you can easily hire 3 developers and get 3 different languages in, oh, Java or JavaScript. One person is doing Kotlin, another one Scala, ...
Three C++ programmers in the same room could also not understand each other. The greybeard speaking only C++98 with a bit of 2003 doesn't grok the words coming out of the C++20 girl's mouth and so it goes.
Why do you think that Lisp is an "anything goes" language? What's your baseline? I think that C is no less an "anything goes" language, but with a much less pleasant UI.
Some people actually think that Lispers tend to be too philosophical
Lisp is anything goes because of macros. Hire ten different Lisp programmers and you’ll get ten different domain specific languages and no one will understand what everyone else has done. If there is a unifying philosophy of Lisp, it’s probably “don’t use macros” and yet so many ignore it!
For all its faults, C is quite easy to read and understand, even by beginner C programmers. Yes, C also has macros but their clumsiness helps to discourage their use.
I'm a Common Lisp programmer. I don't really know how to respond to that except to say, what you describe is not the case at all. Reading others' Common Lisp code is a joy compared to reading others' code in any other language.
Yes, features that are easy to use will be more often used, while inconvenient features will be less used. I don't quite see any controversy with my comment.
The point is that in both cases the underlying feature is present, so APIs will be compatible. However, the lack of syntactic sugar in the one case will make any API that uses the feature cumbersome to use in that language, so in practice it will be avoided.
Abstractly this is true, but software development is a human practice, so it matters not what's technically possible but what people actually do.
That's why the most important difference between C++ and Rust isn't some technicality even though the technical differences are huge, it's cultural. Rust has a Safety Culture and everything else is subservient to that difference.
Sugar matters, Rust's familiar looking loops are just sugar, it only "really" has a single way to do loops, the loop construct, an infinite loop you can break out of. But despite that, people deliberately write the other loops - and the linter strongly recommends that they write them, because the programs aren't just for machines to compile, they're for other humans to read, and a while let loop is an intuitive thing to read for example, so is the traditional for-each style iterator loop.
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.
Surely any Turing complete PL can express a sum type? I can't imagine a language that can support products but not sums.
Turing completeness has nothing to do with static type checking. Dynamically typed PLs can't express any type (except Any) yet are still Turing complete.
Better known as the Turing Tar Pit.
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.
Pattern matching on the "top level branch" of the ADT, whatever you call it, is pretty darned useful.
Pattern matching on the next level down is a power tool to be used with care.
Having used some pattern matching languages for quite some time, I find anything much deeper than that is a code smell at best and pathological at worst. Pattern matching creates coupling proportional to the depth/complexity/precision of the pattern match. The top-level coupling is often unavoidable; if you're pattern matching at all, you certainly care which "branch" you are on and there is likely no refactoring that away. But the danger rises rapidly the deeper in you go. It's just so easy to pattern match on a third-level part of the complex object when you really ought to be wrapping that behind a function somewhere, possibly itself emitting a sum type value.
... but if all you really need is that "top level" match, a lot of pattern matching syntax and features are not really necessary (if not positively dangerous).
Which is exactly how Perl apologia arguments went.
You've got to distinguish syntax from semantics, though. I agree, it's easy to turn a big semantic win into a net readability loss if you choose to represent it with an overly terse syntax that promotes code golf.
Compilers are really smart. It's easy enough in the modern world to demand that a "type" field be checked against all enumerants, preserving the "semantic win". A plain old C switch statement with gcc -Wall will do this today, in fact.
syntax sugar IS power. also if the mechanical transformation is nontrivial, then so is the power of the sugar
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.
Also Typescript https://www.typescriptlang.org/docs/handbook/2/everyday-type...
Union types are not the same as sum types.
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?
Sum types are disjoint unions. This `T` has three cases
whereas a proper sum type `L + R` would have four.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??
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?
This is trivial to model by making your type `T | null | Missing`.
Only if you're designing both functions ahead of time. In other words, it's not composable.
Or just using Option since you would have Some<null> or None in that case.
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.
`T | null` is equivalent to T. You can assign null to `T`>
It's like saying `string | "foo"` it is simply `string` due to subtyping.
No, it isn't "completely useless".
If you have a function that will normally return a string, but can sometimes fail due to reasons, you may wish to yield an error message in the latter case. So you're going to be returning a string, or a string.
It's not what the content of the data is; it's how you're supposed to interpret it. You have two cases, success and failure, and control will flow differently depending on that, not based strictly on the type of data at hand. We just model those cases in a type.
Why would you return `string | string` here? Wouldn't you explicitly mark the error, and return `string | error`? (substitute error with whatever type you want there - null, Error, or your own thing)
No disrespect, but that still sounds entirely useless to me. I would never model something as `String | String` as that makes zero sense. You should use a `Result` or `Either` type for that like everyone does.
As you've demonstrated, you can always construct sum types in typescript with the use of explicit discriminants:
The real issue is typescript doesn't have pattern-matching, which make operating on these sum types inelegantSupports 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.
F# too. And Elm. But I get your point.
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-langua... [2] https://en.wikipedia.org/wiki/Quotient_type
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.
> so you can't change the variant without creating a new instance.
Isn't that true of ADTs in all languages? I can't think of a single language with ADTs that lets you change the tag/variant of an existing value.
In Rust [0]:
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.
[0] https://play.rust-lang.org/?version=stable&mode=debug&editio...
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.
'Values' in Rust have no identity, except for their address. They're just a bunch of bytes in a row. What could it mean for a value to exist, except for it to be present at a set place in memory? If I have an instance of a Java class, and I change all the fields, I'd hardly say the instance has been replaced with a new instance.
If you insist, I'd say "Java's sealed classes are more limited in that when you have a bunch of references to the same thing, you can change the values in the fields of that thing (and have it be reflected in other references), but you can't change which variant it is." Call that thing a 'value' or a 'variable', it doesn't change the visible outcome compared to enums in Rust, or discriminated unions in C/C++.
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.
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.
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.
[0] https://doc.rust-lang.org/proc_macro/enum.TokenTree.html
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)
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
Yes, since Java 21.
Example:
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
Okay that's better than I expected!
It absolutely does. Here is a (modified) snippet of my Java code from yesterday.
Your examples, on the TIOBE index, are #4, #18, and #28. https://www.tiobe.com/tiobe-index/
Product types are one kind of algebraic data type, only 5 languages from that TIOBE page don’t have them so most common langs have ADTs
When you have natural numbers and a multiplication operation (product) would you say that those form an algebra? (ADT means algebraic data type)
You’ve got both a carrier (the set of natural numbers) and a morphism (product operation) so yeah you have an algebra.
Java doesn't have pattern-matching yet. Haskell is not an imperative language.
Java sum types work but still need a bit of syntax sugar on the declaration side, IMHO.
Please don't forget Dart!
https://medium.com/dartlang/dart-3-1-a-retrospective-on-func...
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'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.
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.
You're attempting a sleight of hand here by saying "they're" not "doing trig". Clearly they are not doing anything like that consciously, but equally clearly some part of their brain is triangulating objects and predicting trajectories based on gradients, meaning that part is "doing trig and calculus" subconsciously. What else does it mean to "do something" if not "process X is isomorphic to process Y"?
I really don't understand what you think people are doing when they're compiling a grocery list. They're clearly thinking, "I need x AND y OR I can substitute z".
Or if they're planning to paint their fence, they're thinking, "I need paint AND brushes AND I have to start before lunch OR I won't finish before dinner".
No. You are confusing the model for the reality. Again, our model may lead to a more impressive reality, but ball players are not doing trig. They are almost certainly simulating things, but that does not require trig. Indeed, it only loosely requires math. Models can be very informal with loose approximations.
You seem to think I have to prove your model false to show others don't do that. But I am specifically not claiming your model is false. I'm saying folks don't think that way, necessarily. For example, many build lists for shopping that they were taught. Not that they reasoned.
The ability to build lists requires reasoning. It requires enumeration, inclusion/exclusion conditions, and stop conditions, which necessarily requires logic. This argument is pointless, you go on believing that some people can't use basic logical connectives, I'm sure next you'll say they can't even count.
By that reasoning, though, we can claim that the earth counts to 364 as it orbits the sun. Or that women's bodies count roughly to 9 as they make a baby. These are ways that we model those things, but that is not what is happening.
Most people learn to build lists through mimicry. They literally mimic the lists they were taught they need to build to go to the store. With enough experience, many of us learn to build our own lists from other principals, but it almost all starts with mimicry and simulation. Is why "going shopping" is such a fun game for kids. They are learning.
None of which is to say that you can't make your thinking better with logic. You almost certainly can. But you are begging the question with your examples and explanations. Heavily.
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.
Implication is not primitive, "x->y" is reducible to "not(x) or y". None of those fallacies derive from a lack of direction, but from not being invalid logical deductions.
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.
Pascal has had variant records since the 1970s.
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.
Given where Algol 68 ended up, I would say Wirth was quite right.
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.
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.
Extended variants of Pascal, like Turbo Pascal, should not be confused with the Pascal language as designed by Niklaus Wirth.
Wirth's Pascal was a language designed for the purpose of teaching programming and it was adequate for that, but it was completely inappropriate for any serious work.
It had no means for writing big programs that must be divided into multiple source files and it had a lot of design errors, like including the size of an array in its data type (which made impossible the writing of any linear algebra library) or the way of handling the variant records (which was insecure and verbose).
The well known paper "Why Pascal Is Not My Favorite Programming Language" by Brian W. Kernighan contains valid arguments against Pascal (against Wirth's Pascal, there have been many extended Pascals, especially following Turbo Pascal, which have corrected some of the most egregious defects of the original Pascal).
People keep playing this tired song, while clearly ignoring that until ISO C89, even C was full of dialects, a mix of K&R C and whatever the compiler writer felt like, filled with tons of Assembly.
Small-C, RatC,....
Additionally forgetting that Modula-2 came out in 1978, as means the sort out all those issues, a language designed for systems programming, instead of the "Python" from 1970, designed for teaching.
With features that C is yet to have, 50 years later, while HN is hypping for having them in a C like syntax delivered in a Zig package.
I know that paper and personally I think some of the critiques are actually qualities of pascal, making it, while certainly not a completely refined language, a more modern language than C
- no escape (AKA no casting): good!
- no default clause in case: good idea, not so good implementation (undefined behaviour)
- no break outside for loops: inconvenient, but that's how FP works. it is still debated today if breaking loops is considered a good or a bad practice
- no separated compilation: I will quote Kernighan on this Theoretically, there is no need for separate compilation - if one's compiler is very fast Pascal compiler was fast, maybe not very fast, but speed was one of the primary goals for Wirth.
many other issues were similar in other languages and in C
Pascal had obviously its faults, but every language back then had some
Pascal was simple enough to make it easy to compile and implement. That's what Wirth thaught, he's the author of Compiler Construction after all, it wasn't like learning Python today as a data scientist
make the language more complex (and more useful/interesting) and you're stuck with a very slow or very buggy compiler that very few people would know how to implement
I think there's a reason why we had Turbo Pascal and not Turbo Algol 68
I beg to differ, after Modula-2 and Object Pascal (Apple designed it with Wirth's feedback).
Most of his languages ended up losing, because they weren't being shipped with a free beer OS, coupled with a free beer compiler.
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).
Doesn't look too bad particually the match tagged version last:
edit: don't have a pascal compiler handy, but that's the ideaYeah, 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).
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.
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?
Absolutely, so you try to seal it in hermetically, only talk to it over a special message bus or something.
Sometimes the upgrade path from 6 onwards isn't as nice as it usually is from 8 up, especially if you built with some old undead libraries that require an heroic effort to understand well enough to reimplement. Takes a very special organisation to divert some person-years to pull it off, and as some middle or other manager it's highly unlikely to catch you a new, better job even if it goes well.
It makes me sad, but I totally understand why someone would stay with Java 6, for the same reason that there's still COBOL stuff hanging around: the stuff "works" as is, upgrading is expensive, and some business person decided that the cost of the upgrade isn't worth it for the value they'd receive.
I do worry that there's "Y2K-esque" bugs hiding in Java 6 programs somewhere. I don't think java.util.date uses 32 bit integers for time so the 2038 problem probably won't be an issue, but I do wonder if there's other stuff hiding.
There might be some limit or bug like that in Java 6, but I think time stuff has been backported, so it'd likely be something else. I don't know enough about the JVM internals to speculate on whether the old ones were simpler and less likely to be defective, or not.
By now most types of issues ought to have popped up though, since it was so widely used for such a long time.
Cryptography is kind of an issue . Certain protocols that by now are expected aren't supported by Java 6.
It is. We run an old version of our application on Java 6. Apparently multiple people have tried to upgrade it in the past but it proved too difficult because it's using a bunch of completely obsolete technology with little available documentation that seems to randomly break when you upgrade even minor things.
The plan has been to gradually replace it with the new version of the software (which runs on Java 17), unfortunately this plan has been ongoing for 10 years and it's not gonna be done anytime soon.
Such are the sad realities of working on legacy code sometimes.
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.
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!
That doesn't work since you cannot pass that as a single argument to a function.
So? make the function accept multiple arguments?
Yep, or C doesn't need arrays just use pointers! And C doesn't need strings, just use a pointer to the first byte and assume it's ASCII!
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.
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.
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.
It also has all the features of Haskell, since you can implement a Haskell compiler in C.
That is not a proper alternative to real pattern matching.
ADT feels like an unfortunately acronym-collision with "Abstract data types."
Yep, people that eventually buy a Modula-2 ADT book, when hunting old stuff, are in for a surprise. :)
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.
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.
More often than not, when I say ADT to someone outside of the FP world, they assume I mean abstract data type.
Or the company that sells the security stickers, for houses.
ADT feels like an unfortunately acronym-collision with "algebraic data types."
They were both introduced in the same decade.
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.
Simple to understand, a nightmare to debug, as you'll be chasing where your data and data contracts across a ton of files.
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)
Syntaxes like: `A | B(Int) | C(String)`. That means A, B, or C.
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?
Reminds me of the fact that software isn’t typically as static as animal taxonomies.
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 this an argument? ’Cause I don’t see it.
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.
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.
Isn’t ADT abbreviation for Abstract Data Type? Or does it depend in context nowadays?
Wait until you switch to unions in rust and ask yourself whether it is a union or a struct.
Oh dear
You answered your own question: it depends and the context and is confusing imo. Both are very common in compsci
No I didn’t, I provided two options and asked which case it was. I could’ve assumed OP had used the wrong abbreviation.
Context. It means algebraic data type here.
I've never written Swift, but it seems like they have it too https://docs.swift.org/swift-book/documentation/the-swift-pr...
I also would love a future where ADTs are more common in imperative languages
Swift “enumerations” are very nice.
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.)
https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hi...
"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.
May not be built in but many mainstream languages such as typescript have libraries or the tools to easily implement them.
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.
Swift, Kotlin and Scala all have had ADTs for a while, even Java has it now.