Live data from Hacker News

Algebraic Data Types for C99

github.com

121–130 of 233 posts

Re: Algebraic Data Types for C99

#121
post #97

Earlier quoted context omitted.

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

Re: Algebraic Data Types for C99

#122
post #51

Earlier quoted context omitted.

While this is a step up from C, it is still a long way from the full power and generality of algebraic data types. The key word here is algebraic. In a language with ADTs, such as Haskell, you can pattern match on an arbitrarily complex types, not just the outermost tag. A contrived example (from [1]): contrived :: ([a], Char, (Int, Float), String, Bool) -> Bool contrived ([], 'b', (1, 2.0), "hi", True) = False To ac…

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…

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.

Re: Algebraic Data Types for C99

#123
post #16
post #11

Earlier quoted context omitted.

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…

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

Re: Algebraic Data Types for C99

#124

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.

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

Re: Algebraic Data Types for C99

#125
post #104

Earlier quoted context omitted.

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.

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 no…

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

[0] https://doc.rust-lang.org/proc_macro/enum.TokenTree.html

Re: Algebraic Data Types for C99

#126
post #51

Earlier quoted context omitted.

While this is a step up from C, it is still a long way from the full power and generality of algebraic data types. The key word here is algebraic. In a language with ADTs, such as Haskell, you can pattern match on an arbitrarily complex types, not just the outermost tag. A contrived example (from [1]): contrived :: ([a], Char, (Int, Float), String, Bool) -> Bool contrived ([], 'b', (1, 2.0), "hi", True) = False To ac…

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…

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.

Re: Algebraic Data Types for C99

#128
post #23

Earlier quoted context omitted.

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 qualitie…

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

Re: Algebraic Data Types for C99

#129
post #2

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

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?

Re: Algebraic Data Types for C99

#130

Earlier quoted context omitted.

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…

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 structure…

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.

Post reply on HN