Anonymous sum types

[rust-highfive]

Issue by glaebhoerl
Saturday Aug 03, 2013 at 23:58 GMT

For earlier discussion, see rust-lang/rust#8277

This issue was labelled with: B-RFC in the Rust repository

---

Rust has an anonymous form of product types (structs), namely tuples, but not sum types (enums). One reason is that it's not obvious what syntax they could use, especially their variants. The first variant of an anonymous sum type with three variants needs to be syntactically distinct not just from the second and third variant of the same type, but also from the first variant of all other anonymous sum types with different numbers of variants.

Here's an idea I think is decent:

A type would look like this: (~str|int|int). In other words, very similar to a tuple, but with pipes instead of commas (signifying or instead of and).

A value would have the same shape (also like tuples), with a value of appropriate type in one of the "slots" and nothing in the rest:

let foo: (~str|int|int) = (!|!|666);
match foo {
    (s|!|!) => println(fmt!("string in first: %?", s)),
    (!|n|!) => println(fmt!("int in second: %?", n)),
    (!|!|m) => println(fmt!("int in third: %?", m))
} 

(Nothing is a bikeshed, other possible colors for it include whitespace, ., and -. _ means something is there we're just not giving it a name, so it's not suitable for "nothing is there". ! has nothing-connotations from the negation operator and the return type of functions that don't.)

I'm not sure whether this conflicts syntax-wise with closures and/or negation.

Another necessary condition for this should be demand for it. This ticket is to keep a record of the idea, in case someone else has demand but not syntax. (If the Bikesheds section of the wiki is a better place, I'm happy to move it.)

SEE ALSO

• #402
• #514
• #1154

[huonw]

cc #402, #514, #1154

[ticki]

What's the state of this?

[Rufflewind]

Compared to tuples, anonymous enums would become increasingly tedious to use since a match statement would have N^2 pipe (|) characters. At the expense of type inference, it may be better to go with a syntax like:

let foo: enum(String, int, int) = enum 2(666);
match foo {
    enum 0(s) => println!("string in first: {:?}", s),
    enum 1(n) => println!("int in second: {:?}", n),
    enum 2(m) => println!("int in third: {:?}", m),
}

The syntax would be compatible with a future extension that allows enums to be declared with named choices:

let foo: enum { Red(String), Green(int), Blue(int) } = enum Blue(666);
match foo {
    enum Red(s) => println!("string in first: {:?}", s),
    enum Green(n) => println!("int in second: {:?}", n),
    enum Blue(m) => println!("int in third: {:?}", m),
}

[eddyb]

I think the feature would be more useful without allowing matching, just doing trait dispatch. I guess it's a different feature, where T|T has T's representation, as opposed to one bit more.

[plietar]

@eddyb I've been putting some thoughts into a feature like that
I've posted about it on irlo : https://internals.rust-lang.org/t/pre-rfc-anonymous-enum-which-automatically-implement-forwarding-traits/4806

[burdges]

I'd think an Alloca<Trait> analog of Box<Trait> would provide the same functionality as this return enum expr extension of -> impl Trait idea, except there is dynamic dispatch in Alloca<Trait> so optimization suffers.

[OvermindDL1]

Passing by, but if you are curious in syntax's then OCaml has anonymous sum types called Polymorphic Variants. Basically they are just a name, like `Blah, which can have optional values. An example of the syntax:

# let three = `Int 3;;
val three : [> `Int of int ] = `Int 3
# let four = `Float 4.;;
val four : [> `Float of float ] = `Float 4.
# let nan = `Not_a_number;;
val nan : [> `Not_a_number ] = `Not_a_number
# let list = [three; four; nan];;
val list  : [> `Float of float | `Int of int | `Not_a_number ] list

The val lines are the types of the let assignments, left in to see how the typing works.

In the back-end at assembly time the names are given a globally unique integer (in the current implementation it is via hashing, a chance of collision but overall the chance is extremely low as well as warnings can be put in place to catch them), however I've seen talk of making a global registry so they just get incremented on first access efficiently.

A plain Polymorphic Variant with no data is represented internally as an integer:

`Blah

Becomes the integer 737303889 (yes I checked), and comparing those are trivial.
For Polymorphic variants that can hold data (either a single element or a tuple of elements) such as:

`Blah (42, 6.28)

Gets encoded internally as an array of two fields in assembly, the first is the above number as before, the second is the pointer to the data of the tuple (although in most cases these all get inlined into the same memory in OCaml due to inlining and optimization passes). In the typing system the above would be [> Blah of int * float ](in OCaml the types of a tuple are separated by*`).

However, about Polymorphic variants is that they can be opened or closed. Any system can pass any of them that they want, including passing through if you want. For example, a simple way to handle something like a generic event in OCaml would be like:

let f next x = match x with
  | `Blah x -> do_something_with x
  | `Foobar -> do_something_else ()
  | unhandled -> next unhandled

Which is entirely type safe, dependent on what each function handles down the chain and all.

The big thing on the typing system is that things can be open or close typed, I.E. they either accept any amount of Polymorphic Variants or a closed set of Polymorphic Variants. If something like anonymous sum type here were to be accepted then that concept would be exceedingly useful while being very easy and very fast to statically type.

[burdges]

Anonymous sum types might interact with -> impl Trait : At present, this code snippet cannot compile because the iterators have different types :

match x {
    A(a) => once(a).chain(foo),
    B(b) => once(bar).chain(foo).chain(b),
}

You could make this make sense with an anonymous sum type of the form impl Iterator | impl Iterator, that itself becomes an Iterator, but inferring any type like that sounds like chaos.

One could do it in std with enums like :

enum TwoIterators<A,B> {
    IterA(A),
    IterB(B),
}

impl Iterator for TwoIterators where .. { .. }

so the above code becomes

match x {
    A(a) => TwoIterators::IterA( once(a).chain(foo) ),
    B(b) => TwoIterators::IterB( once(bar).chain(foo).chain(b) ),
}

I could imagine some enum Trait sugar that did basically this too. You cannot delegate associated types or constants to an enum at runtime like this, so an enum Trait must enforce that they all agree across all the variants.

[dobkeratops]

this might sound like a weird hack , but how about just making A|B sugar for 'Either', i suppose it might get even weirder to start composing A|B|C as Either<A,Either<B,C>> or have that mapping to something . What if there was some sort of general purpose 'operator overloading' in the 'type syntax' , allowing people code to experiment with various possibilities - see what gains traction
(i had yet another suggestion about allowing general purpose substitutions, e.g. type Either<A,Either<B,C>> = Any3<A,B,C> .. etc https://www.reddit.com/r/rust/comments/6n53oa/type_substitutions_specialization_idea/ now imagine recovering ~T === Box ~[T] ... type Box<RawSlice> = Vec .. through a completely general purpose means )

[ubsan]

@dobkeratops I'd rather just have a variant style type, i.e., with variadics.

[Sgeo]

I wrote some code that could potentially fit into a library now that type macros are stable: https://gist.github.com/Sgeo/ecee21895815fb2066e3

Would people be interested in this as a crate?

[Ekleog]

I've just come upon this issue, while looking for a way to avoid having some gross code that simply doesn't want to go away (actually it's slowly increasing, started at 8 variants and passed by 9 before reaching 12):

use tokio::prelude::*;

pub enum FutIn12<T, E, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12>
where
    F1: Future<Item = T, Error = E>, // ...
{
    Fut1(F1), // ...
}

impl<T, E, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12> Future
    for FutIn12<T, E, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12>
where
    F1: Future<Item = T, Error = E>, // ...
{
    type Item = T;
    type Error = E;

    fn poll(&mut self) -> Result<Async<Self::Item>, Self::Error> {
        use FutIn12::*;
        match *self {
            Fut1(ref mut f) => f.poll(), // ...
        }
    }
}

I was thus thinking that it'd be great to have anonymous sum types that automatically derived the traits shared by all their variants, so that I could get rid of this code and just have my -> impl Future<Item = (), Error = ()> function return the futures in its various branches (with some syntax, that ideally wouldn't expose the total number of variants but let rustc infer it from the returning points, so that adding a branch doesn't require changing all the other return points), and have the anonymous sum type match the -> impl Future return type.

[glaebhoerl]

As I wrote here I think this use case would be better addressed by something modelled after how closures work.

[alexreg]

I don’t think it would be wise to make anonymous sum types nominally typed, as you seem to suggest. Structural typing, as with tuples, is far more useful and less surprising to the programmer.

[Pauan]

@alexreg What they're saying is that the specific use-case of wanting to return impl Trait with different types in each branch is better handled by a secret nominal type, similar to how closures are implemented.

Therefore, anonymous sum types are separate (and mostly unrelated) from that use case.

[alexreg]

@Pauan Oh, well I agree with that. As long as we consider these things two separate features, fine. Thanks for clarifying.

[Ekleog]

Oh indeed good point, thanks! Just opened #2414 to track this separate feature, as I wasn't able to find any other open issue|RFC for it :)

[eaglgenes101]

I'm planning to get out a pull request for this proposed RFC. Most of you following this thread probably know that a number of proposals like this were rejected for being too complex, so its focus is minimalism and implementation simplicity rather than ergonomics and features. Any words before I get it out? (I've asked this question in multiple other areas to try to collect as much feedback before getting the proposed RFC out, fyi)

https://internals.rust-lang.org/t/pre-rfc-anonymous-variant-types/8707/76