Value-based generics

Evolution Discussion
1

I’ve had this idea for a while now, and recently I saw a mention of basically the same idea on the compile-time constants thread. I also recently learned that rust has this feature, so it’s not as unique of an idea as I may have originally thought, but this encouraged me to start a discussion about it.

Instead of only allowing types, generic arguments should also support regular values. This would mean a type could have some value associated with it when it is used (like generic types now can have a type associated with them), and types would be treated as different if this value was different.

Since this concept works with the type system, and all types must be known at compile type, the value of these generic arguments would need to be known at compile time. This means that this idea would rely on compile-time constants, and generic value arguments would need to be compile-time known values.

A couple examples of how this could be useful:

  • Fixed length arrays. Using value-based generics, an array could be guaranteed to have a specific number of elements at compile time, and arrays of different lengths could be treated as different types.
var foo: FixedLengthArray<String, length: 3> = ["bar", "baz"]
// Error: Cannot convert value of type '[String]' to specified type 'FixedLengthArray<String, length: 3>'
  • Matrices could be introduced in an elegant way.
let matrix: Matrix<m: 2, n: 4>
  • Assuming compile-time values support enums, it could be used to replace somewhat unintuitive phantom types.
let document = Document<.pdf>()

A major question related to this feature is how value-based generics would be defined in a type. The way that I find most intuitive would be to use the same syntax that generics currently use:

struct FixedLengthArray<Element, length: Int> {}

This has a major flaw, though. If you define a type with a generic parameter that is constrained to a protocol:

struct Foo<Bar: SomeProtocol> {}

It is impossible to know if Bar: SomeProtocol is classic generic, where Bar is a type that conforms to SomeProtocol, or if it's an existential of SomeProtocol, and bar is a value.

Here are a few solutions I came up with just after thinking for a minute.

  • Don’t allow existentials here.
    I can’t currently think of a place where you would want to use an existential in this context, but arbitrarily adding this limitation feels wrong.
  • Represent classic generics with metatypes. Type based generics could be thought of as accepting an instance of a metatype. This would be a large breaking change and might be confusing, but it would be simple in that there aren’t two different types of generic, instead type based generics are a form of value-based generics using metatypes. I’m also not sure how feasible this is technically.
struct Set<Element: Hashable.Type> {}
  • Possibly my favorite option, and the one Rust uses, is using a keyword to identify value-based generic parameter. This could use whatever keyword is used for compile-time constants. For example:
struct FixedLengthArray<Element, length: const Int> {}

Value-based generics could support specialized extensions with where clauses:

extension FixedWidthArray where length == 1 {}

Since comparing values isn’t nearly as simple as comparing types, this isn’t trivial; that == is a normal operator that would normally be executed at runtime. However, if compile-time functions are added to swift, where clauses could support any compile-time function, which could allow for complex and very powerful extensions.

extension Matrix where n == m && n > 3 {
    // square matrix larger than 3x3
}

I haven’t yet thought about how this might apply to generic functions/inits/subscripts, but in theory it could work similarly?

This is my first proposal, so it’s not very polished, but I just wanted to start a discussion about it and see what everyone thinks. Please lmk your thoughts!

8 Likes
2

This is covered under the heading of “Generic value parameters” in the Generics Manifesto, and you can find past discussion in these forums about the topic using the search function.

3 Likes
3

One problem with adding generic value parameters to Swift before something like hygenic macros or compile time function evaluation, is that there's only a handful of good use cases.

You can't really use it to implement fixed sized arrays without some other feature.

// marking Size const would be redundant in this position.
struct FixedSizedArray<Element, Size: Int>  {
    // what do you write here?
}

If you had hygenic macros, or a templating system, or even just magic syntax for a fixed sized array you could write the stuff that goes in the middle. But without that you've got nothing. The most useful thing you could do would be something like:

struct LinearCongruentialGenerator<M: UInt64, A: UInt64, C: UInt64>: RandomNumberGenerator {
    var state: UInt64
    mutating func next() -> UInt64 {
        state = (state &* A &+ C) % M
        return state
    }
}
4

Hm, I agree that they would have limited usefulness without compile-time functions, but I still think you could implement a fixed size array

I have basically no experience with low-level programming, so I don’t know exactly how an array structure would be implemented, but I came up with this just wrapping an array.

struct FixedSizeArray<Element, length: Int> {
    private var value: [Element]
    
    init(repeating value: Element) {
        self.value = Array(repeating: value, count: length)
    }

    // FixedSizeArray would have all array methods and properties except for ones that add and remove elements
}

func needs3LongArray(_ arr: FixedSizeArray<Int, length: 3>) {} // can’t currently do something like this 
// arr is guaranteed to be of length 3 at compile time

However there’s no way to conform to ExpressibleByArrayLiteral that I can think of since you couldn’t check it’s length and throw an error at compile time, which makes this fairly useless.

Regardless, I assumed compile time functions would exist in the section about where clauses, and now I see that they would be essential for the idea to work at all.

1 Like
5

A fixed sized array (that anyone would want to use) of size N, would be have the same layout as a homogenous tuple of N elements. Having to get dynamic allocation involved defeats the entire purpose.

2 Likes
6

Yeah I know that this example isn’t actually useful; as I said, I know very little about low-level programming and was just giving an example that works with what I know

7

It doesn't exactly defeat the entire purpose though. There are uses for fixed size arrays other than just performance. It would definitely help increase expressiveness in certain cases where your function requires that an array be of a certain length. I have run into that in the past and ended up just using a precondition which isn't exactly the nicest solution.

I do agree with you that value-based generics would be much more useful with compile-time evaluation. But it's definitely interesting to think about even if it's not feasible yet.

3 Likes