Live data from Hacker News

Algebraic Data Types for C99

github.com

61–70 of 233 posts

Re: Algebraic Data Types for C99

#61
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 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!

Re: Algebraic Data Types for C99

#62

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…

Java sum types work but still need a bit of syntax sugar on the declaration side, IMHO.

Re: Algebraic Data Types for C99

#63
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…

syntax sugar IS power. also if the mechanical transformation is nontrivial, then so is the power of the sugar

Re: Algebraic Data Types for C99

#64

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 is not a proper alternative to real pattern matching.

Re: Algebraic Data Types for C99

#65
post #61

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

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

Re: Algebraic Data Types for C99

#66

Earlier quoted context omitted.

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…

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

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

Re: Algebraic Data Types for C99

#67
post #39

Earlier quoted context omitted.

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…

You might be interested in taking a look at OCaml's extensible sum types which may straddle the line in the way you're describing.

Re: Algebraic Data Types for C99

#68

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

Seems like Nim can be useful too, plus it compiles to C.

https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62e...

Re: Algebraic Data Types for C99

#69
post #59

Earlier quoted context omitted.

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
        }
    }
which would let you get around the problem of returning a type erased object for a Trait that isn't object safe:

    trait Trait {
        const C: i32 = 0;
    }
    impl Trait for i32 {}
    impl Trait for &'static str {}
    fn foo() -> Box {
        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 {
      |                 ^^^^^^^^^ `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 
     --> 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::Ok { Ok(42) }

    let Ok(val) = foo();
There's some work on this, under the umbrella of "patterns in types". For now the only supported part of it is specifying a value range for integers, but will likely grow to support arbitrary patterns.

---

Having a way to express `impl Trait for Enum {}` when every `Enum` variant already implement `Trait` without having to write the whole `impl`.

---

Anonymous enums:

    fn foo() -> Foo | Bar | Baz
---

Being able to match on Box 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),
    }
---

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

Re: Algebraic Data Types for C99

#70

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…

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