Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algebraic Data Types for C99

github.com

Post reply on HN
Print view View original

51–60 of 233 posts

Re: Algebraic Data Types for C99

#51

Post by chongli »

skywal_l wrote: post #6
different_base wrote: post #3

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.

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]):

    contrived :: ([a], Char, (Int, Float), String, Bool) -> Bool
    contrived    ([],  'b',  (1,   2.0),   "hi",   True) = False
To achieve a result like this using Zig's switch syntax would seem to involve a huge amount of boilerplate code and nested switch statements.

[1] https://www.haskell.org/tutorial/patterns.html

Re: Algebraic Data Types for C99

#52

Post by CraigJPerry »

different_base wrote: post #3

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.

>> not having ADTs (except maybe Rust) built-in

Most of the common languages today have product types.

Java[1], Rust, Haskell, etc. have sum types.

I think it gets a bit more escoteric beyond that though - i don't doubt that there's probably some haskell extension for quotient types[2] or some other category theory high-jinx.

Most languages have ADTs built in.

[1] https://blogs.oracle.com/javamagazine/post/inside-the-langua... [2] https://en.wikipedia.org/wiki/Quotient_type

Re: Algebraic Data Types for C99

#53

Post by floxy »

adrian_b wrote: post #17
different_base wrote: post #3

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

Moreover, they have already been proposed by John McCarthy in October 1964, 60 years ago, for inclusion in the successor of ALGOL 60, which makes even more weird the lack of widespread support. (And in fact Algol 68 had a better implementation than most later languages, but Algol 68 was missing completely any documentation suitable for newbies, like tutorials and programming examples, while not being promoted by any…

>The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hi...

Re: Algebraic Data Types for C99

#54

Post by cess11 »

tombert wrote: post #30
kaashif wrote: post #20

Earlier quoted context omitted.

> when Java 8 added a lot of (well-needed) new syntax, it felt like that was an ideal opportunity to add ADTs and pattern matching Well at least Java does now (as of Java 21) have pattern matching (including nested record destructuring) and sealed classes, which let you have decent sum types. The one issue is that everything is nullable, but that's a wider Java issue.

Yeah, but the annoying part of Java is that people stick with old versions for a long time. Java 21 looks pretty great but most companies are still using Java 17, or even Java 11 still.

Some have even older Java versions in 'prod'. 6 is still alive in some places out there, because management refuses to pay for either upgrade, replacement or dismantling.

I have a mid-sized application I built on 17 that's used to deliver a particular project, really looking forward to finish the project so I get to move to 21 and refactor it with these new features and make it more general.

Re: Algebraic Data Types for C99

#55

Post by mpawelski »

dtech wrote: post #48
fanf2 wrote: post #41

Earlier quoted context omitted.

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?

Supports exhaustiveness checks only if you explicitly opt-in it (by coding to pattern where you use helper function that accepts `never` type). "Dicriminated Unions Type"/"Sum Types" feels very hacky there, at least syntax-wise, because it is constraint by being "JS + types" language. It's remarkable what Typescript can do, but having native Discriminated Unions in JS (hence in TS too) would be much more ergonomic and powerful.

Re: Algebraic Data Types for C99

#56

Post by naasking »

mgaunard wrote: post #38
different_base wrote: post #3

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.

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.

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.

Re: Algebraic Data Types for C99

#57

Post by Hirrolot »

chongli wrote: post #51
skywal_l wrote: post #6

Earlier quoted context omitted.

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]): 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 Programming Languages, pages 78–103. Prentice Hall, 1987.

Re: Algebraic Data Types for C99

#58

Post by Hirrolot »

naasking wrote: 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 :)

Re: Algebraic Data Types for C99

#59

Post by im3w1l »

estebank wrote: post #45
im3w1l wrote: post #39

Earlier quoted context omitted.

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…

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?

Re: Algebraic Data Types for C99

#60

Post by naasking »

taeric wrote: post #36
different_base wrote: post #3

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.

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.
Post reply on HN