Brainstorming: variadic & type expressions

I originally posted this to @fredpointzero's "Pre-RFC: variadic tuple" thread, but felt it veered off too much from the contents there and would be better off in a separate thread.

The following is a very much abbreviated gist of my own brainstorming on the subject. I did not want to spam the forum with tons of separate posts on every part, and hope the basic ideas are understandable (if not, I can always elaborate :wink: )

Disclaimer: as the title indicates, this is still all very much brainstorming. I'm also not sure of the latest state of const fn, may well be that the relevant parts are out of date and/or contain some misunderstandings.


Problem:

My litmus test for variadic syntax is: "Can I write a function that transposes a variadic tuple of variadic tuples?" Bonus: "Can I derive the return type of this function?"

This led me to the following individual suggestions, with the complete implementation that ties everything together at the end.

1.) type consts in traits & compiler traits for types:

trait Aggregate {
    const LEN: usize;
}
trait Tuple : Aggregate { 
    const TYPES: [type; LEN]; 
}

2.) type-level subscription operator, type- and value-level concatenation operator:

(u8, u16, i32) ++ (Foo, Bar) == (u8, u16, i32, Foo, Bar)  // type-level
(8u8, 'a') ++ (64i16, Foo()) == (8u8, 'a', 64i16, Foo())  // value-level

(u8, u16, i32)[1] = u16    // or perhaps (u8, u16, i32)::[1]
struct { a: u8; b: u16; }[0] == struct { a: u8; }

3.) type-level functions, trait kinds: (see below for the explanation of the ..for syntax)

type fn zipify2<T1, T2> where T1: Tuple, T2: Tuple -> impl Tuple {
    // see the full implementation for const_min
    const LMIN: usize = const_min(<T1 as Tuple>::LEN, <T2 as Tuple>::LEN);
    (
        ..for i in 0..LMIN => (T1[i], T2[i]),
        ..for i in LMIN..<T1 as Tuple>::LEN => (T1[i], ()),
        ..for i in LMIN..<T2 as Tuple>::LEN => ((), T2[i]),
    )
}

type fn implements<TYPE, trait TRAIT> -> const bool { TYPE: TRAIT }

4.) generalized where clauses:

where clauses should be able to take any const fn or type fn that returns a bool. See full implementation for an example

5.) omprehension for and where, on value and type-level:

comprehension/looping (for) and filtering (where). My syntax suggestion would be (examples):

// below is equiv. to (b[0], calc(b[0])) ++ (b[1], calc(b[1])) ++ ... 
// I.e., a flat tuple (b[0], calc(b[0]), b[1], calc(b[1]), ...)
(..for a in b => (a, calc(a)))  

Foo(..for a in b where filter_on(a) for i in 0..a => (i,))
[..for a in b => [a, a*2, a*3]]

In detail, a comprehension ..for over a tuple or struct iterates over successive 1-tuples/structs: ..for i in (u8, u16) => ... returns (u8,), then (u16,).

Alternatives:

  • if for filtering, but I think that where reduces ambiguity.
  • Python syntax insteadf of =>.

6.) const str and reflection, anonymous structs, struct field name generation:

Structs with field names are more complicated than arrays and (struct) tuples. In order to generate these, some amount of reflection would be useful.

Suggestion: allow const str in const fn. These are compile time, copy-only strings, no slices or references allowed. A library with useful const fn (e.g., to_lower, to_snake_case) would be handy.

Analogous to array/tuple case, then, a comprehension ..for over structs with named fields returns consecutive anonymous structs with a single field. For those, the compiler provides a trait:

trait Struct1 {
    const FIELD_NAME: const str;
    const TYPE: type;
}

With this, and a syntax that allows us to generate field names:

struct Bar { 
    count: usize;
    ..for field in Baz => struct { 
        // allow const str expressions to be used to generate the field name. 
        // Using square brackets (analogous to indexing) to disambiguate syntax.
        [<field as Struct1>::FIELD_NAME ++ "_flag"]: bool;
        [<field as Struct1>::FIELD_NAME ++ "_value"]: <field as Struct1>::TYPE;
    };  // this anonymous struct gets flattened into Bar
    total_value: usize;
}

The complete variadic transpose implementation:

// These assume we can have use iterators over const aggreagates in const fn

const fn const_fold<T>(initial: T, values: impl IntoIterator<T>, f: const Fn(T, T) -> T) -> T { 
    let mut v = initial; 
    for it in values { v = f(v, *it); }
    v
}
const fn const_all<T: Into<bool>>(values: impl IntoIterator<T>) -> bool { 
    const_fold(From::from(true), values, const |a, b| a.into() && b.into()) 
}
const fn const_max<T: Ord>(initial: T, values: impl IntoIterator<T>) -> T { 
    const_fold(initial, values, const |a, b| if a > b { a } else { b }) 
}

fn variadic_transpose<T, D>(tuple2D: T, default_val: D) 
    where T: Tuple,
          const_all([..for TT in <T as Tuple>::TYPES => TT: Tuple]),
          D: Copy,
    -> impl Tuple  // Note: type fn expressions could derive the specific type
{
    const LMAX = const_max([..for tuple in tuple2D -> <tuple as Tuple>::LEN]);

    (
        ..for hor in 0..LMAX => (
            ..for ver in 0..<tuples2D as Tuple>::LEN => {
                const tuple = tuples2D[ver];
                if hor < <tuple as Tuple>::LEN { tuple[hor] } else { default_val }
            },
        ),
    )
}

Note: ..for could technically be a range expression, with a for expression that returns the range end. But I think that this combination should be rare enough that we can re-purpose it.

Clarification: for today is an expression that always returns () today. (The somewhat complex rules around omitting semicolons after a close block brace allow the use of it as a full statement.)

It needs to remain an expression such that it can be used as a match branch arm. Additionally, a for expression works fine as a $:expr macro match.

Because RangeTo<()> is a "useless type", it would not likely break any "real" code to change the meaning of ..for, and compiler types could be used to "downgrade" the type-level for to a range with a warning.

That said, doing so would not be trivial.

I am deliberately avoiding developing an opinion on how to handle this in the language, and just noting on surface syntax.

TL;DR ..for is a possible syntax but not without difficulty.

1 Like

I'm slightly concerned that this is expanding from a variadic type to a metaprogramming facility, and will satisfy Greenspun's tenth rule.

If you want the power to implement tuple transformations, you may end up wanting other things than transpose, but they may require conditionals or variables, and before you notice, you'll layer another programming language on top of Rust.

So I think it requires an explicit decision: is it just a special case in the type system for tuples (and you have to accept that some perfectly reasonable things just won't be possible), or is it a beginning of a metalanguage for type manipulation and compile-time code generation?

C++ was meant to have templates as just a basic declarative extension to the type system, but ended up creating another programming language layered on top of C++, except a very cumbersome one.

To avoid having a language-in-language, D and newer C++ decided to use their "native" syntax for metaprogramming. D has "static" versions of its constructs and special properties/functions for querying types and emitting code. C++ is adding metaclasses.

In Rust that could be something which brings power of proc_macros to the normal in-crate syntax (something that is declared more like macro_rules, but has access to the types).

5 Likes

Ah, I thought break-with-value can be done with any loop expression. TIL.

It's mostly brainstorming. :wink: The tuple transposing function was just a motivator, not the main goal. I'd rather have the individual parts be considered for their own particular merits.

That said, I'm of course aware that most things in my post are not feasible in the short, or even long run, and others may end up being served better by alternative approaches.

OTOH, there's const fn, which already will require the compiler to interpret and execute at least a subset of the lanugage. Once that gets powerful enough to generate aggregates I don't see much of a stretch to similarly assemble internal type descriptors for new types in the same way.