News for hackers. Stuff that matters.
Re:Algebraic Data Types for C99 by CraigJPerry on Thursday May 09, 2024 @11:30AM (#40309251)
>> 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 by LegionMammal978 on Thursday May 09, 2024 @12:50PM (#40310147)
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.
Re:Algebraic Data Types for C99 by munificent on Thursday May 09, 2024 @01:07PM (#40310338)
> 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.

Re:Algebraic Data Types for C99 by LegionMammal978 on Thursday May 09, 2024 @02:24PM (#40311285)
In Rust [0]:

  #[derive(Debug)]
  pub enum Example {
      Foo(i32),
      Bar(&'static str),
  }

  let mut ex: Example = Example::Foo(42);
  println!("{ex:?}"); // Foo(42)

  let ex_ref: &mut Example = &mut ex;
  *ex_ref = Example::Bar("hello");

  println!("{ex:?}"); // Bar("hello")
Given a mutable reference to a value of enum type, you can replace it with another variant. Or you can swap it out with any other value of the same type, even if the variants are different. This is most commonly used for Option<T>, where you can insert or remove the contained value as long as you have a reference.

The limitation here is that for as long as the mutable reference is live, no other code can access the value. So when you do change the variant, you can't have any other references sitting around that point to the removed subfields.

[0] https://play.rust-lang.org/?version=stable&mode=debug&editio...

Re:Algebraic Data Types for C99 by munificent on Thursday May 09, 2024 @04:51PM (#40312840)
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.

Re:Algebraic Data Types for C99 by LegionMammal978 on Thursday May 09, 2024 @07:26PM (#40313959)
> You aren't changing the variant of an existing ADT, you're replacing the entire ADT value with a new one.

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

Re:Algebraic Data Types for C99 by munificent on Saturday May 11, 2024 @08:27PM (#40331484)
What you're describing is pointers and value semantics. Rust (and C and C++ and to some degree Go) has those. Java does not.

Pointers and value semantics are nice, but have nothing to do with ADTs. For example, in Rust, you can also do:

    let mut ex: i32 = 42;
    println!("{ex:?}"); // 42

    let ex_ref: &mut i32 = &mut ex;
    *ex_ref = 53;

    println!("{ex:?}"); // 53
And in C:

    int x = 42;
    printf("%d\n", x); // 42

    int* x_ref = &x;
    *x_ref = 53;

    printf("%d\n", x); // 53
In these examples, we haven't mutated the number 42 into the number 53. We've simply stored an entirely new value in the location of `x`. In your Rust example, you're doing the exact same thing with an ADT. The variant case isn't being changed. You're creating a new value and storing it in an existing storage location. Every pointer pointing to that storage location sees the update because they all point to the same storage.
Re:Algebraic Data Types for C99 by brabel on Thursday May 09, 2024 @01:23PM (#40310505)
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.

Re:Algebraic Data Types for C99 by LegionMammal978 on Thursday May 09, 2024 @02:35PM (#40311404)
> 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 by nextaccountic on Thursday May 09, 2024 @12:24PM (#40309834)
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)
Re:Algebraic Data Types for C99 by brabel on Thursday May 09, 2024 @01:02PM (#40310296)
Yes, since Java 21.

Example:

    sealed interface BinaryTree {
      record Leaf(int value) implements BinaryTree {}
      record Node(BinaryTree lhs,
                BinaryTree rhs,
                int value) implements BinaryTree {}
    }

    public class Hello {
      static int sum(BinaryTree tree) {
        return switch (tree) {
        case BinaryTree.Leaf(var value) -> value;
        case BinaryTree.Node(var lhs, var rhs, var value) -> sum(lhs) + value + sum(rhs);
        };
      }
    
      public static void main(String... args) {
        var tree = new BinaryTree.Node(
                                       new BinaryTree.Leaf(1),
                                       new BinaryTree.Node(
                                                           new BinaryTree.Leaf(2),
                                                           new BinaryTree.Leaf(3),
                                                           4),
                                       5);
        System.out.println(tree);
        System.out.println("Sum: " + sum(tree));
      }
    }
If you added a new subtype to BinaryTree you would need to fix the switch.

EDIT: I didn't handle the `null` case above... so it would be a NullPointerException if someone passed null... apparently, Java decided to make handling `null` optional. More information: https://www.baeldung.com/java-lts-21-new-features

Re:Algebraic Data Types for C99 by nextaccountic on Thursday May 09, 2024 @01:06PM (#40310332)
Okay that's better than I expected!
Re:Algebraic Data Types for C99 by davidalayachew on Thursday May 09, 2024 @01:08PM (#40310348)
It absolutely does. Here is a (modified) snippet of my Java code from yesterday.

    final boolean hasUncollectedSecret =
       switch (each)
       {
               
          case Wall()    -> false;
          case Goal()    -> false;
          case Player p  -> false;
          case BasicCell(Underneath(_, var collectible), _)
             ->
                switch (collectible)
                {
                        
                   case NONE, KEY -> false;
                   case SECRET -> true;
                        
                };
          case Lock()    -> false;
               
       };
Re:Algebraic Data Types for C99 by thewakalix on Thursday May 09, 2024 @12:31PM (#40309914)
> The intent is to introduce a more-advanced construction called pattern matching in a later release.
Re:Algebraic Data Types for C99 by brabel on Thursday May 09, 2024 @01:07PM (#40310337)
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

Re:Algebraic Data Types for C99 by j2kun on Thursday May 09, 2024 @12:38PM (#40310000)
Your examples, on the TIOBE index, are #4, #18, and #28. https://www.tiobe.com/tiobe-index/
Re:Algebraic Data Types for C99 by CraigJPerry on Thursday May 09, 2024 @05:26PM (#40313131)
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
Re:Algebraic Data Types for C99 by dannymi on Thursday May 09, 2024 @06:16PM (#40313483)
When you have natural numbers and a multiplication operation (product) would you say that those form an algebra? (ADT means algebraic data type)
Re:Algebraic Data Types for C99 by CraigJPerry on Friday May 10, 2024 @02:45AM (#40316050)
You’ve got both a carrier (the set of natural numbers) and a morphism (product operation) so yeah you have an algebra.
Re:Algebraic Data Types for C99 by thewakalix on Thursday May 09, 2024 @12:32PM (#40309921)
Java doesn't have pattern-matching yet. Haskell is not an imperative language.
Re:Algebraic Data Types for C99 by speed_spread on Thursday May 09, 2024 @11:53AM (#40309488)
Java sum types work but still need a bit of syntax sugar on the declaration side, IMHO.
Re:Algebraic Data Types for C99 by brabel on Thursday May 09, 2024 @01:19PM (#40310453)