9 ms·
Sum Types in Julia and Rust
- chandraravi 6y agoGreat informative content, Keep doing the good work. https://chennaitraining.in/java-training-in-chennai/ https://chennaitraining.in/java-training-in-chennai/ https://chennaitraining.in/python-training-in-chennai/ https://chennaitraining.in/python-training-in-chennai/ https://chennaitraining.in/r-programming-training-in-chennai/ https://chennaitraining.in/r-programming-training-in-chennai... https://chennaitraining.in/selenium-training-in-chennai/ https://chennaitraining.in/selenium-training-in-chennai/ https://chennaitraining.in/digital-marketing-training-in-chennai/ https://chennaitraining.in/digital-marketing-training-in-che... https://chennaitraining.in/angular-js-training-in-chennai/ https://chennaitraining.in/angular-js-training-in-chennai/ https://chennaitraining.in/aws-training-in-chennai/ https://chennaitraining.in/aws-training-in-chennai/ https://chennaitraining.in/big-data-training-in-chennai/ https://chennaitraining.in/big-data-training-in-chennai/ https://chennaitraining.in/ccna-training-in-chennai/ https://chennaitraining.in/ccna-training-in-chennai/ https://chennaitraining.in/hadoop-training-in-chennai/ https://chennaitraining.in/hadoop-training-in-chennai/ https://chennaitraining.in/informatica-training-in-chennai/ https://chennaitraining.in/informatica-training-in-chennai/ https://chennaitraining.in/pmp-training-in-chennai/ https://chennaitraining.in/pmp-training-in-chennai/ https://chennaitraining.in/scrum-master-training-in-chennai/ https://chennaitraining.in/scrum-master-training-in-chennai/ https://chennaitraining.in/seo-training-in-chennai/ https://chennaitraining.in/seo-training-in-chennai/ https://chennaitraining.in/tally-training-in-chennai/ https://chennaitraining.in/tally-training-in-chennai/ https://chennaitraining.in/dotnet-training-in-chennai/ https://chennaitraining.in/dotnet-training-in-chennai/ https://chennaitraining.in/etl-testing-training-in-chennai/ https://chennaitraining.in/etl-testing-training-in-chennai/ https://chennaitraining.in/salesforce-admin-training-in-chennai/ https://chennaitraining.in/salesforce-admin-training-in-chen... https://chennaitraining.in/salesforce-developer-training-in-chennai/ https://chennaitraining.in/salesforce-developer-training-in-... https://chennaitraining.in/sap-hana-training-in-chennai/ https://chennaitraining.in/sap-hana-training-in-chennai/
- amitport 6y agoI may be wrong, but I don't think this is what people mean by 'sum types'. I was expecting union types (e.g., https://www.typescriptlang.org/docs/handbook/unions-and-intersections.html#union-types https://www.typescriptlang.org/docs/handbook/unions-and-inte... or https://dotty.epfl.ch/docs/reference/new-types/union-types.html https://dotty.epfl.ch/docs/reference/new-types/union-types.h... ) I guess enums are a type of sum type, but seems this is more specifically about enums
- edflsafoiewq 6y agoUnion types aren't sum types. One difference is A | A = A, but A + A = 2 * A.
- muglug 6y agoI think the use of an enum (in the Rust example) makes this a sum type situation: https://tonyarcieri.com/a-quick-tour-of-rusts-type-system-part-1-sum-types-a-k-a-tagged-unions https://tonyarcieri.com/a-quick-tour-of-rusts-type-system-pa...
- enricozb 6y agoI believe another word for enums (in the Rust sense, not in the C++ or Java sense) are tagged unions.
- curryhoward 6y agoThat's right. It's unfortunate that Rust calls them "enums", since as you noted that term already had a well-established meaning in other languages, and the concept that Rust calls "enums" also had several existing names (sum type, coproduct type, disjoint union, and, more generally, algebraic data type) in the literature and in prior languages. Language designers: stop changing the meanings of words! I know you mean well and you're trying to tie unfamiliar ideas to familiar ones for beginners, but you end up causing more confusion for everyone in the long run.
- richardwhiuk 6y ago
- muglug 6y agoGreat article — I’ve never written a line of Julia or Rust, but could still understand it perfectly
- siraben 6y agoWhen I think of sum types, I like the categorical definition the best, which is that a sum A+B has two morphisms (i.e. constructors) Inl : A -> A+B and Inr : B -> A+B, with a simple commuting diagram[0]. Or in Rust, enum Sum<A, B> { Inl(A), Inr(B), } Why do I prefer this definition? Well, category theory abstracts away irrelevant details, and sums have a "universal property" associated with them. Roughly speaking that means that it doesn't matter how you define sum types in your language, if they fit the universal property of sums (up to isomorphism) then they truly can be considered sum types. In the Rust PlayerClass example the corresponding sum is (Solarian + (Polarian + Centaurian)), and morphisms Sol = Inl . Inl Pol = Inl . Inr Cent = Inr . Inr [0] https://en.wikipedia.org/wiki/Coproduct https://en.wikipedia.org/wiki/Coproduct
- millstone 6y agoI don't know any category theory whatsoever. What happens in your example if A = B? Would it have two morphisms or just one?
- siraben 6y agoThere'll still be two morphisms, Inl : A -> A + A and Inr : A -> A + A
- cakoose 6y agoWhat might be causing confusion is the difference between tagged unions and untagged unions. A union type "A | B" means "a value of type A or a value of type B". Example: function f1(): String | Integer { if (rand()) { return "hello" } else { return 12 } } function f2(x: String | Integer) { switch (typeof x) { case String: return "string: " + x case Integer: return "integer: " + x } } The type "String | String" is exactly equivalent to "String". A tagged union (aka sum type) "A + B" means "either a left value or a right value; if it's the left, it has type A, if it's the right it has type B". function g1(): String + Integer { if (rand()) { return Inl("hello") } else { return Inr("bye") } } function g2(x: String + String) { switch (x) { case Inl(s): return "left value: " + x case Inr(s): return "right value: " + x } } The type "String + String" has one bit of additional information than just "String".
- snicker7 6y agoTraits are possible in Julia [0] and may be a better solution. [0] https://ahsmart.com/pub/holy-traits-design-patterns-and-best-practice-book/ https://ahsmart.com/pub/holy-traits-design-patterns-and-best...
- chalst 6y agoTwo thoughts: For this problem, I would use union types in Julia. Union types are a sort of sum, but they are amalgamated sums whilst sums types in PL semantics usually means disjoint sums. The difference is that disjoint sums 'mark' whether a value is of the left or right type, while with amalgamated sums the value may belong unmarked to the intersection. The distinction does not matter in the example the post gives. Second, Julia does not give the benefit that Rust gives of type coverage, that is, ensuring that functions that take the sum type as argument actually are defined for each branch of the sum type. The Rust compiler guarantees this automatically. AFAICS, with Julia it is up to the user to provide tests exploring the branches.
- bocckoka 6y agoJulia is a dynamic language, I don't think having the rigor of a compiled language (probably the most rigorous out there) is a reasonable expectation. It would be nice to have as an external linter service, probably.
- pa7x1 6y agoI think you are mixing two different things. Julia is a compiled language and Rust is too. Julia is dynamically typed while Rust is statically typed.
- chalst 6y agoIt is possible to check type coverage for dynamically typed languages, if the compiler/interpreter has enough type information to infer what types need coverage. In the case of multimethods, Julia's compiler is given this information.
- bocckoka 6y agoJulia enums do not equal to Rust enums. You can achieve that functionality (that a type can be one of a set of cases, type algebra in general) with subtypes. Which is fine I'd say, but there could be terser syntax for it (which is available through packages, and it's slower). Having abstract types which cannot be instantiated is also nice.
- celrod 6y ago> Use subtyping in Julia and enums in Rust. I would use enums in Julia, making the enum you define a field of the PlayerClass: @enum PlayerStar Sol Pol Cent struct PlayerClass star::PlayerStar # other fields end Julia's compiler will split small unions into static dispatches behind branches, and can also decide whether or not to specialize on types or create a generic functions. But if your code is performance sensitive, I'm more comfortable controlling the behavior than relying on these optimizations. The problem is, dispatch is often a more convenient coding style than long branches.
- amelius 6y agoThere are sum types, and product types, but what would "exponentiation types" look like?
- pwdisswordfish4 6y agoThose are just (pure) function types.
- Someone 6y agoFixed-length sequences, but they would be constructed from a type and a non-negative integer, not from two types. The sum of a type with m possible values and a type with n possible values has (m+n) possible values, the product of a type with m possible values and a type with n possible values has (m×n) possible values, a sequence of n items of a type with m possible values has m^n possible values.
- guerrilla 6y agoExponential types are functions [1]. The type A -> B could be written B^A. Interestingly, if you take functions to be lookup tables, then that's related to the number of possible unique lookup tables. First, notice that the type A + B has |A| + |B| values, the type A × B has |A| + |B| values and then we can see that A -> B has |B|^|A| values by remembering that functions can be seen as binary relations with the property of being functional. This means that there are |B|^|A| possible unique functions. Try an example by counting the number of functions from the set { 0, 1 } to { 2, 3, 4 }. You will see that there are 3^2 = 9 possible unique functions. 1. https://en.wikipedia.org/wiki/Function_type https://en.wikipedia.org/wiki/Function_type
- amelius 6y agoInteresting! Now I wonder what "tetrated" types correspond to [1] [1] https://en.wikipedia.org/wiki/Tetration https://en.wikipedia.org/wiki/Tetration
- guerrilla 6y agoWell, I don't know of any type theory that has that but you could make something up. C^(B^A) = (B^A) -> C = (A -> B) -> C. So you'd get nested higher-order monomorphic functions like if the base is A and the height |B| = 5 then the result of tetration would be (((A -> A) -> A) -> A) -> A. I don't really know what that means though. Maybe an expert Haskeller could recognize a pattern.
- thom 6y agoSomeone Rustier than I am, what's the story with this enum solution when I want to add a _new_ star later? Can one implement this in a way that respects the open-closed principle?
- richardwhiuk 6y agoYou can flag an enum as `non_exhaustive` to indicate that it might contain additional values in the future. If you do that, then anyone writing the code must add code to handle other cases, or it's a compile error (i.e. you must match the enum as: #[non_exhaustive] enum Foo { CaseA, CaseB } let f : Foo = get_foo(); match foo { CaseA => {}, CaseB => {}, // Exhaustive matching _ => {}, } https://doc.rust-lang.org/reference/attributes/type_system.html https://doc.rust-lang.org/reference/attributes/type_system.h...
- thom 6y agoBut how can the PlayerClass trait methods get extended in the future without opening them back up to add cases to the match expression?
- ragnese 6y agoI'm slightly confused. First, PlayerClass is not a trait. And the methods would have to be edited when you add a case to the enum. Is that what you're asking? It's different than if you were implementing those methods on a trait and just had several types that implemented the trait. But the article does show the potential complications that sometimes arise with Rust traits. The difference is that a trait is "open" and an enum is "closed". So the enum's methods can/must account for all variants. A trait method calls to the implementor for work, much like inheritance in other languages.
- thom 6y agoSorry, somehow my brain had thought impl and trait went hand in hand, I see that's incorrect. My question is just - do people really accept this tradeoff? The Rust advice in the article seems to create a maintenance burden compared to the Julia version. Every time you want to extend the system you have to go back and crack open old code. Is the performance difference really that great? Is this really the default approach for Rust programmers? Not snarking about Rust at all, I'm fascinated, but the open-closed principle would be front of mind for me when deciding on these sorts of abstractions (both as a language designer and just a developer).
- richardwhiuk 6y agofn greet<T: Player>(&self, other: &T); Yeah, this doesn't work, but the equivalent to what you are writing in Julia does: fn greet(&self, other: Box<dyn Player>);
- JoshMcguigan 6y agoI’m not sure what is meant here, because that top example would compile. edit - Alright I think I see what the original article was trying to express. In the original article that top example method was defined as part of a trait. Because that method is generic that would make the trait not object safe. On its own that is fine (this would still compile), but there was some previous example code which relied on this trait being object safe.
- kevincox 6y agoOr even just pass by reference if you don't need to take the box: fn greet(&self, other: &dyn Player);
- daralthus 6y ago> Use subtyping in Julia and enums in Rust. One caveat though: Enums can not be extended from the “outside”. If you plan to let users of your library add new type variants, you will have to use some kind of trait approach. This extensibility from the outside is the most important idea behind Julia! For example this is why a generic deep learning library doesn't need any extra implementation details to be able to run on GPU as well. https://fluxml.ai/Flux.jl/stable/gpu/ https://fluxml.ai/Flux.jl/stable/gpu/
- alskjd__ 6y agorust nightly #![feature(specialization)] #![allow(incomplete_features)] struct Solarian; struct Polarian; struct Centaurian; trait Greet { fn greet(&self); } trait Player {} impl Player for Solarian {} impl Player for Polarian {} impl Player for Centaurian {} impl<T: Player> Greet for (Polarian, T) { default fn greet(&self) { println!("Hi"); } } impl Greet for (Polarian, Solarian) { fn greet(&self) { println!("Your star doesn't even consist of three separate stars? Pathetic!"); } } fn main() { (Polarian, Solarian).greet(); (Polarian, Centaurian).greet(); }