Pre-RFC: variadic tuple

I am not a fan of the the ..#T syntax, for several reasons:

  1. It would most definitely break the procedural macro of the quote crate
  2. It's confusing when T is an array
  3. It looks noisy
  4. It diverges from current syntax
  5. With variadic tuple expansion, it's inconsistent and obscures control flow

1. It would most definitely break the macro of the quote crate

The quote crate has a quote! macro that substitutes tokens starting with a hashtag. It's used frequently for creating procedural macros.

2. ..#[T; n] looks like an attribute

Although it might not cause a parse error, it's definitely weird to look at.

3. It looks noisy

Example from the RFC:

fn clone_add<(..#T)>((..#i): (..#T)) -> (..#T) 
where ..#(T: Clone + Add) {
  (..#(<T as Clone>::clone(&i) + i))
}

4. It diverges from current syntax

The syntax of destructuring a variadic tuple is different from destructuring a normal tuple or a struct:

let Foo { a, ..b } = normal_struct;
let Bar(a, ..b) = tuple_struct;
let (a, ..b)  = tuple;
let (a, ..#b) = variadic_tuple;

I believe that this will make the feature harder to learn, understand, and use correctly.

5. With variadic tuple expansion, it's inconsistent and obscures control flow

Example from the RFC:

fn my_func<(..#T)>((..#i): (..#T)) {
  (..#{ println!("{}", i) })
}

What is i here? It's not a tuple, it's what is inside the tuple. But it isn't a value either. It's a special case, that doesn't exist anywhere else, and it can only be used in an expansion form (..#EXPRESSION). I can only imagine how much effort this would be to implement in the compiler.

And what about the expansion form? It "desugars" into a tuple, and the content of the expansion form is repeated n times, where n is the arity of the tuple:

// if T has an arity of 3:
fn my_func<T1, T2, T3>((i1, i2, i3): (T1, T2, T3)) {
  (
    { println!("{}", i1) },
    { println!("{}", i2) },
    { println!("{}", i3) },
  )
}

This means that three values are printed, even though the function contains println! only once, and doesn't have any loops. Also, the expansion form can't take ownership of a value in the function, because then there would be more than one owner. People will find this counter-intuitive.

It would be more intuitive to use a block that introduces the variable, so it has a well-defined scope. Something like:

fn my_func<(..#T)>(tuple: (..#T)) {
  (repeat i in tuple {
    println!("{}", i)
  })
}

However, a macro might be more appropriate for this.

P.S. You're missing a T: Display trait bound in the examples!

4 Likes

@mcy @Aloso, thanks! I appreciate the feedbacks.

Considering the issues pointed out:

  1. function recursion

I think its is a bad idea to include support of variadic tuple in generic parameter group of functions. Mainly because there is no way to specialize an implementation for a function currently in Rust.

  1. Utilities

I totaly agrees, utilities to manipulate tuple will be very valuable. Although those are not required for this RFC to have value, so I prefer to mention these in the Future section for future RFCs.

  1. Syntax

Yes that is ugly, but I needed something to discuss with to establish the main features of the RFCs. So now is the time to think about a nice readable syntax that is way easier to understand and maintain.

It would be nice to have something similiar to existing syntax and way of thinking, but still noticeable that its does not run any code at runtime.

Considering expansion, the current thinking model is macro like with expanded patterns, but maybe we can instead use imperative and functional syntaxes which are easier to understand. (To replicate for loops or iterators).

Still, I need some time to think about it and come up with several ideas.

Recursion

To implement some feature, we may want to use recursion over the arity of the tuple. For instance, let's implement a trait that gives the arity of a tuple as a const value:

trait Arity {
    const VALUE: usize;
}

impl<Head, (..#Tail)> Arity for (Head, ..#Tail) {
    default const VALUE: usize = <(..#Tail) as Arity>::VALUE + 1;
}
impl Arity for () {
    const VALUE: usize = 0;
}

I guess this example won't be work for Rust because Rust want to check generics before monomorphization.

While checking validity of <(..#Tail) as Arity>::VALUE + 1, there is no witness of (..#Tail) being Arity. Instead we could use specialization to ensure all variadic tuple type have instance of Arity:

impl<(..#Ts)> Arity for (..#Ts) {
    default const VALUE: usize = 0;
}
impl<Head, (..#Tail)> Arity for (Head, ..#Tail) {
    const VALUE: usize = <(..#Tail) as Arity>::VALUE + 1;
}

Similarly, the variadic tuple expansion can't be just an "expression template" and there must be a static semantics to be given. For example,

fn test<(..#Ts)>((..#t): (..#Ts)) {
  let s = String::new();
  (..#{ drop(s); t });
}

Defining test should be error because test<(i32, i32)>((0, 0)) expands to a double drop. However, expanded test<(i32)>((0,)) is valid and thus it is an approximate semantics in the sense.

Version 1 - Original

struct MegaMap<(..#(K, V))> {
  maps: (..#HashMap<K, V>),
  keys: (..#[K; 32]),
  values: (..#[V; 32]),
}

impl<(..#(K, V))> MegaMap<(..#(K, V))> {
  fn get(&self, (..#k): (..#K)) -> (..#Option<&V>) {
    let (..#(ref maps)) = &self.maps;
    (..#maps.get(k))
  }
}

impl<(..#T), Last> Hash for (..#T, Last) 
where
    ..#(T: Hash),
    Last: Hash + ?Sized, {

    #[allow(non_snake_case)]
    fn hash<S: Hasher>(&self, state: &mut S) {
        let (..#(ref v), ref last) = *self;			 
      	
        (..#v.hash(state), last.hash(state));   
    }
}

Syntaxes improvements options

Loosing the '#' char

The range syntax .. defines instance not types, so when a type is expected .. can't be used as a Range.

So, we can use the syntax:

struct MegaMap<(..(K, V))> { }
}

impl<(..(K, V))> MegaMap<(..(K, V))> {
  fn get(&self, keys: (..K)) -> (..Option<&V>) { }
}

impl<(..T), Last> Hash for (..T, Last) 
where
    ..(T: Hash),
    Last: Hash + ?Sized, {

    #[allow(non_snake_case)]
    fn hash<S: Hasher>(&self, state: &mut S) { }
}

Destructuring

We can match the existing syntax with ..ident:

Drop the #, directly use ..ident or ..ref ident or ..ref mut ident

So we can write instead:

let (head, ..tail): (Head, ..Tail) = _;
let (ref head, ..ref tail): (&Head, ..&Tail) = _;
let (ref mut head, ..ref mut tail): (&mut Head, ..&mut Tail) = _;

Variadic tuple expansions

Another of thinking the expansion is to use similar syntax for iterators and loops. Something like:

impl<(..(K, V))> MegaMap<(..(K, V))>
where ..(K: Hash), {
  fn get(&self, (..k): (..K)) -> (..Option<V>) {
    let (..ref maps) = &self.maps;

    // iterator like syntax
    k
      // iterate over the members of tuple `(..k): (..K)`
      .into_iter()
      // adaptor to zip with tuple `(..maps): (..&HashMap<K, V>)`
      .zip(maps.into_iter())
      // map a generic fn: `fn<K: Hash, V>(k: K, map: &HashMap<K, V>) -> Option<&V>` 
      .map(|k, map| map.get(k))
      // collect into a tuple
      .collect::<(..Option<&V>)>()
  }

  // Note, the map operation reminds higher kinded type:
  // `fn map<M: for<T, V> Fn(T) -> V>(mapper: M)`
}

impl<(..T), Last> Hash for (..T, Last) 
where
    ..(T: Hash),
    Last: Hash + ?Sized, {

    #[allow(non_snake_case)]
    fn hash<S: Hasher>(&self, state: &mut S) {
        let (..ref tuple, ref last) = *self; 
        // `tuple` is a variable with type `(..&T)`
        
        // imperative style syntax
        for member in tuple {
          member.hash(state);
        }
        // equivalent to
        // `tuple.into_iter().for_each(|member| member.hash(state));`
        last.hash(state);
    }
}

To continue on this way, I think it is best to focus on the iterator syntax, the imperative style syntax can be deduced from it as syntaxic sugar.

For now, I'll investigate the state of higher-kind types and if this can help this RFC as well.

But so far, what do you think of these options?

3 Likes

Thanks for the feedback, indeed that is more consistent with current behaviour, I'll update the RFC accordingly.

I am going to rework this part, taking this into account and trying to find a more consistent and easier to use syntax.

Because tuples are heterogeneous, we could only iterate over an Iterator<Item = &dyn T> or Iterator<Item = Box<dyn T>.

I think the best way forward (without breaking backwards compatibility) is with a built-in macro:

repeat!(member in tuple {
    member.hash(state);
});

This macro could even build a new variadic tuple with the same arity.

1 Like

To be clear, I am not suggesting we make tuples iterable in the traditional sense; I'm suggesting that we add a new construct that does something along the lines of your macro-like construction (but, frankly, should maybe be more first-class than some macro thing)...

Making tuple iterable is not the intent, it was more to start thinking of the variadic tuple as an heterogeneous array that could by iterated on with a specific syntax.

But I agree that it should be first class citizen otherwise it will be a real pain to use. (that is exactly the case for the first version of the RFC).

But still needs to find an appropriate syntax that fits the Rust language and won't be confused with traditional iterators

Hi, I updated the RFC with a new syntax proposition to replace the expansion of variadic tuples, I think it is easier to understand and make more sense, what do you think?

Also, I dropped the # char in the syntax for clarity and to avoid confusions with attributes.

Now the syntax is ambiguous with range syntax.

Yeah, I very much feel that the "..T" syntax is sort-of ok for types, but definitely not for expressions; plus, I want something more explicit like the above repeat! macro. C++'s expr... is way way too subtle.

Also, can we reverse iteration somehow?

I would imagine that would be implemented as a library? Imagine something equivalent to C++:

template<typename>
struct Rev;
template<typename T, typename... Ts>
struct Rev<std::tuple<T, Ts...>> {
  using type = MergeTuples<
    typename Rev<Ts...>::type, std::tuple<T>>;
 private:
  template<typename T, typename U>
  using MergeTuples = decltype(std::tuple_cat(
    std::declval<T>(), std::declval<U>()));
};
template<>
struct Rev<std::tuple<>> {
  using type = std::tuple<>;
}

static_assert(std::is_same_v<
  std::tuple<char*, void*>, 
  Rev<std::tuple<void*, char*>>::type);

(FWIW, I don't think we'd need to play the stupid games with our equivalent of decltype, since this RFC comes with tuple merging).

1 Like

I'd like to keep the (..T) syntax for types and bounds (or something equivalent), it is quite compact and the range notation is not used at these locations.

But for expression, we may drop the .. syntax for expression, it is quite clear inside the for loop:

impl<(..(K, V))> MegaMap<(..(K, V))>
where ..(K: Hash), {
    fn get(&self, (..keys): (..K)) -> (..Option<V>) {
        let (..ref maps) = &self.maps;

        let result: (..Option<&V>) = {
            for (ref key, map) type (Key, Value) in (keys, maps) type (K, V) {
                HashMap::<Key, Value>::get(&map, key)
            }
        };

        result
    }
}

However, this does not provide flexibility on the iterators. We may use the iterator syntax which is more flexible but more verbose:

         let result: (..Option<&V>) = {
            for (ref key, map) type (Key, Value) in keys.zip(maps) type K.zip(V) {
                HashMap::<Key, Value>::get(&map, key)
            }
        };

Note: again this is inlined by the compiler and not executed at runtime. Note 2: zip in that case would be a function implemented by the compiler to zip the tuples, we can have the same for rev and other utilities.

In the end, I find the former syntax more explicit but without flexibility and the latter confusing (too close to existing iterator IMO)

In that case, I think that the iteration syntax is fixed and don't provide iterator flexibility, (so option 1). But we may have those features through libraries as @mcy suggested.

Although, this RFC does not provide this flexibility, see below example.

For the reverse case:

trait Rev {
	type Value;
}
impl<T> Rev for T {
	default type Value = ();
    default fn rev(self) -> Self::Value { () }
}
impl<Head, (..Tail)> Rev for (Head, ..Tail) {
	// There is something missing, we need to be able to "destructure" the
	// associated type as a variadic tuple type and use it in the expansion form
	type Value = (#######, Head);

	// Syntax suggestion:
	let type (..RevTail) = <(..Tail) as Rev>::Value;
	type Value = (..RevTail, Head);
	// The let type seems inappropriate as it is acts as an infaillible assign
	// but we know actually nothing about Rev::Value
	// It is not bounded to be a tuple type
	// End

    fn rev(self) -> Self::Value {
         let (h, ..t) = self;
         let (..rev_t) = <(..Tail) as Rev>::rev((..t));
         (..rev_t, h);
    }
}

trait Merge<(..R)> {
	type Value;
}
impl<(..R), T> Merge<(..R)> for T {
	default type = (T, ..R);
}
impl<(..L), (..R)> Merge<(..R)> for (..L) {
	type Value = (..L, ..R);
}

I guess we'd like something like for the implementation

impl<(..(K, V))> MegaMap<(..(K, V))>
where ..(K: Hash), {
	// Destructure the associated type
	// But same issue: Rev::Value is not bounded to be a tuple
    type (..RevK) = <(..K) as Rev>::Value;
    type (..RevV) = <(..V) as Rev>::Value;

    fn get(&self, (..keys): (..K)) -> (..Option<RevV>) {
        let (..ref maps) = &self.maps;
        let (..rev_maps) = <(..&HashMap<K, V>) as Rev>::rev((..maps))
        let (..rev_keys) = <(..K) as Rev>::rev((..keys));

        let result: (..Option<&RevV>) = {
            for (ref key, map) type (Key, Value) in (rev_keys, rev_maps) type (RevK, RevV) {
                HashMap::<Key, Value>::get(&map, key)
            }
        };

        result
    }
}

So maybe investigating destructuring variadic tuple types and / or better expansion for variadic tuple types. Although, I'd like to keep this simple and not introduce a full syntax to create types from variadic tuple. I think if we can "destructure" an associated type as a tuple it will provide quite a lot of features as library.

Traits will act as function: [type] -> type.

Also, I think that some feature would be available only as compiler intrinsics, like:

  • sorted: create a variadic tuple type that has its member order sorted by TypeId
  • unique: create a variadic tuple type where all its member have different types Something like
mod tuple {
	pub trait UniqueTuple {
		type Value;
	}
	pub trait SortedTuple {
		type Value;
	}
	// impl of these traits are compiler intrinsics on all tuple
	pub type Unique<(..T)> = <(..T) as UniqueTuple>::Value;
	pub type Sorted<(..T)> = <(..T) as SortedTuple>::Value;
}

I think you are underestimating how powerful traits are. We could do this to get a library solution.

trait Rev {
    type Value;

    fn rev(self);
}

impl Rev for () {
    type Value = ();

    fn rev(self) -> Self::Value { () }
}

impl<Head, (..Tail)> Rev for (Head, ..Tail)
where (..Tail): Rev,
      <(..Tail)>::Value: Merge<(Head,)> {
    type Value = <<(..Tail)>::Value as Merge<(Head,)>>::Output;
    
    fn rev(self) -> Self::Value {
         let (h, ..t) = self;
         let rev_t = <(..Tail) as Rev>::rev((..t));
         rev_t.merge((h,))
    }
}

trait Merge<(..R)> {
	type Output;
    
    fn merge(self, other: (..R)) -> Self::Output;
}

impl<(..L), (..R)> Merge<(..R)> for (..L) {
    type Output = (..L, ..R);

    fn merge(self, (..other): (..R)) -> Self::Output {
        let (..s) = self;
        (..other, ..s)
    }
}
2 Likes

You are right, we can implement it as a library. To be more consistent with the RFC, it would be like:


// Library for tuple

trait Merge<(..R)> {
    type Value;
}
impl<(..L), (..R)> Merge<(..R)> for (..L) {
    type Value = (..L, ..R);
    fn merge(self, other: (..R)) -> Self::Value {
        (for (l,) in ..(L,) { l }, for (r,) in ..(R,) { r })
    }
}

trait Rev {
    type Value;

    fn rev(self);
}

impl<(..T)> Rev for (..T) {
    default type Value = (..T);
    default fn rev(self) -> Self::Value { () }
}

impl<Head, (..Tail)> Rev for (Head, ..Tail)
where 
    // (..Tail) does implement Rev with the blanket impl
    // But the blanket impl for Merge is only for tuple
    // so we still need require it here
    <(..Tail) as Rev>::Value: Merge<(Head,)> {

    type Value = <<(..Tail) as Rev>::Value as Merge<(Head,)>>::Output;
    
    fn rev(self) -> Self::Value {
         let (h, ..t) = self;
         let rev_t = <(..Tail) as Rev>::rev((..t));
         rev_t.merge((h,))
    }
}

// Usage

impl<(..(K, V))> MegaMap<(..(K, V))>
where ..(K: Hash), {
    // Destructure the associated type
    // However, there is an issue: Rev::Value is not bounded to be a tuple
    type (..RevK) = <(..K) as Rev>::Value;
    type (..RevV) = <(..V) as Rev>::Value;

    fn get(&self, (..keys): (..K)) -> (..Option<RevV>) {
        let (..ref maps) = &self.maps;
        let (..rev_maps) = <(..&HashMap<K, V>) as Rev>::rev((..maps))
        let (..rev_keys) = <(..K) as Rev>::rev((..keys));

        let result: (..Option<&RevV>) = {
            for (ref key, map) type (Key, Value) in (rev_keys, rev_maps) type (RevK, RevV) {
                HashMap::<Key, Value>::get(&map, key)
            }
        };

        result
    }
}

However, in the variadic tuple iteration we need a destructured identifier. So at some point we need to "destructure" the associated type as a variadic tuple. (type (..RevK) = <(..K) as Rev>::Value).

The issue is that here it is faillible as we don't have bound "is tuple".

IMO, to have a safe way to have library like traits to manipulate tuple, we need to enforce that an associated type is a tuple with bounds.

The variadic tuple type destructuration is another story, here it is required because we need it as an identifier for the tuple iteration loop. So we enforce that it is only valid for this kind of item. Otherwise we may find another syntax that can take directly an associated type as argument.

For the tuple bound, maybe we can express it like this:

impl<(..(K, V))> MegaMap<(..(K, V))>
where 
    ..(K: Hash),
    // Bounds the associated type to be a variadic tuple
    // and associate it to an identifier
    <(..K) as Rev>::Value: (..RevK),
    <(..V) as Rev>::Value: (..RevV),
 {
    fn get(&self, (..keys): (..K)) -> (..Option<RevV>) {
        let (..ref maps) = &self.maps;
        let (..rev_maps) = <(..&HashMap<K, V>) as Rev>::rev((..maps))
        let (..rev_keys) = <(..K) as Rev>::rev((..keys));

        let result: (..Option<&RevV>) = {
            for (ref key, map) type (Key, Value) in (rev_keys, rev_maps) type (RevK, RevV) {
                HashMap::<Key, Value>::get(&map, key)
            }
        };

        result
    }
}

This needs more thinking, also about whether we can keep the arity constraint through associated traits? like

impl<(..(L,R))> MyStruct<(..L), (..R)>
where
   <(..L) as Rev>::Value: (..RevL),
   <(..R) as Rev>::Value: (..RevR), {
    // We know that this is valid because
    // L and R have the same arity and the Rev trait keep the arity
    // But the compiler does know only during monomorphization
    fn do_something() -> (..(RevL, RevR)) { ... }
}

I don't think that we need variadic associated types. Also, the solution I posted doesn't rely on specialization, so we won't be blocked on that.

I think we'll need something like Zip to reverse two variadic tuples and maintain parity. We could do something like this, all without specialization or variadic associated types

trait Zip<T> {
    type Output;

    fn zip(self, other: T) -> Self::Output;
}

impl<(..(T, U))> Zip<(..U)> for (..T) {
    type Output = (..(T, U));

    fn zip(self, (..u): (..U)) -> Self::Output {
        let (..t) = self;
        (..(t, u))
    }
}

fn rev_both<(..(T, U, RevT, RevU))>(t: (..T), u: (..U)) -> ((..RevT), (..RevU))
where <(..T) as Zip<(..U)>>::Output: Rev<Output = (..(RevT, RevU))>
{
    let (..(rev_t, rev_u)): (..(RevT, RevU)) = t.zip(u).rev();
    ((..rev_t), (..rev_u))
}

The reason the specialization feature is involved is because of the point made by @pcpthm:

So, we need a witness of the trait impl for recursive implementations.


This can actually work and will be nice.


However, I notice an issue, I need to update the for loop syntax that replace the variadic tuple expansion to allow tuple merging.

Also, a quick note: the variadic tuple are not supported for function, so if we transform your code with a trait, it will be:

trait Zip<T> {
    type Output;

    fn zip(self, other: T) -> Self::Output;
}

impl<(..(T, U))> Zip<(..U)> for (..T) {
    type Output = (..(T, U));

    fn zip(self, (..u): (..U)) -> Self::Output {
        let (..t) = self;
        (for (t1, u1) in ..(t, u) { (t1, u1) })
    }
}

trait RevBoth<(..(T, U, RevT, RevU))> {
    fn rev_both(t: (..T), u: (..U)) -> ((..RevT), (..RevU))
    where 
        <(..T) as Zip<(..U)>>::Output: Rev<Output = (..(RevT, RevU))> {
        let (..(rev_t, rev_u)): (..(RevT, RevU)) = t.zip(u).rev();
        ((for (v,) in ..(rev_t,) { v }), (for (u,) in ..(rev_u,) { u }))
    }
}

If you use trait bounds, you can get around this, see any of my solutions for examples of this.

Why not for functions? You already have to support them for trait functions so this seems like a weird and unnecessary corner case.

This syntax is ambiguous with ranges

1 Like