[Pitch] Dependent Integer Expressions in Generic Arguments

[Brennanium]

Hey all,

I've been working on several small prototypes of this ever since SE-0452 originally introduced integer generic parameters and mentioned arithmetic generics in the "Future directions" section. Since SE-0531 (literal expressions in integer generic argument positions) got accepted recently too, I decided to make another prototype and got far enough this time that I wanted to pitch it for real.

Basically, Swift still cannot use arithmetic with integer generic parameters in generic argument positions to do things like this:

struct Vector<let count: Int, Element> {}

func concatenated<let lhsCount: Int, let rhsCount: Int, Element>(
    _ lhs: Vector<lhsCount, Element>,
    _ rhs: Vector<rhsCount, Element>
) -> Vector<(lhsCount + rhsCount), Element>

The pitch keeps SE-0531's required parentheses, but extends the expressions inside them to include integer generic parameters and a bounded set of Int operations. In my prototype, the signature above is accepted, allowing the result type to retain the relationship between its input sizes.

Literal subexpressions continue to use SE-0531's existing folding rules. For example, Vector<(count + (2 + 3)), Element> still becomes Vector<(count + 5), Element>. The dependent generic part of an expression retains its ordered tree though: Vector<(n + m), Element> and Vector<(m + n), Element> are distinct. I initially tried to add a more general algebraic-equivalence system, but obviously the complexity of that really ballooned, even when my prototype was just working with + and * operators. I think keeping the whole expression tree structure ended up making the most sense for many reasons.

I've currently got support for all of the Int arithmetic, bitwise, shift, and unary operators supported by the literal expressions from SE-0531. For now, division and remainder require a divisor that SE-0531 can fold to a nonzero integer. Supporting a dependent divisor would require a way to state a divisor != 0 constraint in a generic signature, which this pitch deliberately leaves out of scope.

This is my first pitch (and first post!) even though I've followed the Swift Evolution forums for several years now. I'm really looking forward to hearing your feedback and thoughts!

The current proposal draft is here:

https://github.com/Brennanium/swift-evolution/blob/dependent-integer-generic-expressions/proposals/NNNN-dependent-integer-expressions.md

The compiler prototype and tests are here:

https://github.com/Brennanium/swift/tree/dependent-integer-generic-expressions

[jrose (Jordan Rose)]

I'm mostly going to stay out of this, but please make sure the compiler doesn't assume Foo<(n + m)> and Foo<(m + n)> (and Foo<n> and Foo<7> and Foo<(a + b + c)>) are not the same type. That should be fine since Foo<T> and Foo<U> are already a well-tested version of this, but it'd be really bad to get it wrong.

[Brennanium]

Yeah for sure! The compiler does not assume they are unequal once the generic arguments become concrete. Foo<(n + m)>and Foo<(m + n)> are distinct symbolic forms in a generic context, just like Foo<n> and Foo<7>. Once the generic arguments are concrete, the expressions evaluate normally, so both Foo<(3 + 4)> and Foo<(4 + 3)> are Foo<7>.

[xwu (Xiaodi Wu)]

This looks good. Just want to drop in with two edge-case nits:

Only an expression whose resolved operator is the corresponding standard library operation on Int is accepted. If ordinary lookup selects a user-defined overload, the expression is rejected; the compiler does not perform a second, special lookup for a standard library overload.

It is also currently possible (probably shouldn't be, but alas) for end users to alter the precedence group (and hence associativity and precedence) of stdlib operators locally within their own code. It would probably be right to (and also sufficient to) reject attempts to use stdlib operators in generic contexts when their precedence group has been altered, so as to avoid 2 * 2 + 3 evaluating to different results inside versus outside angle brackets.

Vector<(count << -1), Element>	Evaluates as count >> 1.

It's sort of implied by your text, but the implementation must be sure that whether this is accepted and evaluates to count >> 1 depends on whether << resolves to the expected stdlib function, not >>.

[Brennanium]

Holy good catch! Allowing local precedence override like that is crazy tbh I just checked and it appears to not be properly handled by both this prototype and the already accepted SE-0531 literal expressions as well actually. I've got a quick fix for both now.

Also adding a small wording change to not imply that << gets resolved as >> for real, just that the result is the same based on normal << smart shift behavior.