Integer generic parameters for protocols

Evolution Discussion
1

I’m working on a toy program that computes hashes of files. The user can choose from different hash algorithms—MD5, SHA1, etc. I therefore have a protocol HashAlgorithm that the different implementations conform to:

protocol HashAlgorithm {
  /// Initializes a new hash algorithm state.
  init()

  /// The number of bytes in each block.
  static var blockSize: Int { get }

  /// The number of bytes in the final digest.
  static var digestSize: Int { get }

  /// Mixes a single block into this hash state.
  mutating func iterate(blockBytes: UnsafeMutableRawBufferPointer)

  /// Copies the final digest into the provided buffer and destroys the hash state.
  consuming func finalize(into: UnsafeMutableRawBufferPointer)
}

All the buffer sizes must be checked at runtime. If HashAlgorithm were a generic struct, I could lift these constraints into the type system using InlineArray. SE-0452 doesn’t speak to the possibility of extending integer generics to protocols.

Given the subtle differences between generics and associated types, is it a sound thing to consider? Just trying to mock up a syntax raises some interesting questions:

protocol HashAlgorithm {
  init()

  static let blockSize: Int
  static let digestSize: Int
  // `let` requirements are currently not allowed in protocols.
  // `var { get }` would allow the answer to change at runtime.
  // Perhaps this even requires the compile-time constant expressions feature?

  typealias Digest = InlineArray<digestSize, UInt8>
  // Neither `typealias` nor `associatedtype` seems correct here.
  // `typealias` seems wrong because the concrete type is dependent on the value of `digestSize`.
  // `associatedtype` seems wrong because InlineArray is a concrete type, so it can’t be used as a constraint.
  // Does this require a new hybrid syntax? `associatedtype Digest = InlineArray<digestSize, UInt8>`?

  mutating func iterate(block: borrowing [digestSize * InlineArray])
  // Does this pose parsing problems?
  // Maybe `digestSize` needs to be fully qualified with `Self.`?

  consuming func finalize() -> Digest
}

func hash<H: HashAlgorithm>(data: UnsafeRawBufferPointer, using _: H.Type) -> H.Digest {
  var hashState = H.init()
  var offset = 0
  while offset < data.count {
    let block = data[offset..<min(offset + H.blockSize, data.count)]
    // The type of `block` can’t depend on the range argument.

    hashState.iterate(block: block)
    // How does the caller massage `block` into the appropriate `InlineArray<_, UInt8>` concrete type?

    offset += algorithm.blockSize
  }

  return hashState.finalize()
}

let chosenAlgorithm: any HashAlgorithm.Type
chosenAlgorithm = askUser()
// What is the type of `chosenAlgorithm`’s methods?

let data = readFromInput()
let digest = hash(data: data, using: chosenAlgorithm)
// What is the type of `digest`?

print("\(digest)")
2 Likes
2

This was discussed: Compile-Time Values and Integer Generics

Once we get @const values, at implementation level it will become possible to define @const static let digestSize: Int, which can be used in InlineArray<digestSize, UInt8> declaration.

How this will play at protocol level is interesting question.

2 Likes
3

This is within the realm of possibility, but for everything to work it would need to be declared as an “integer associated type” so that it can be witnessed by an “integer type alias” or integer generic parameter.

It would still not be possible to implement an integer associated type via an arbitrary static let, because that can compute any value.

For the same reason, you cannot implement an ordinary associated type with a static let property which computes an existential metatype.

Remember that plain old integer values are the existential types in the integer generics world.

1 Like
4

It also seems like the compiler would need to model any types that involve an “integer type alias” as a dependent type. In my example, this would include the argument to hash() and the return value of finalize(). Would this be a straightforward extension of the compiler’s existing support for opaque types, or are there dragons lurking here?

5

They wouldn't be much different than ordinary member type parameters. That actually happens to be what Swift (and C++) calls a "dependent type", but it's not the same thing as the usual meaning of "dependent type" in programming language theory, which is a "type dependent on a value".

If that means nothing to you, consider this:

protocol P {
  associatedtype A
}

func f<T: P>(...) {
  let myArray = Array<T.A>
}

We can refer to T.A inside f() and form the type Array<T.A>, because T conforms to P, and P declares an associated type named A. You can conform to P in various ways:

struct S1: P {
  typealias A = Int
}

struct S2: P {
  struct A {}
}

struct S3<A>: P {}

struct S4<T: P>: P {
  typealias A = T.A
}

Now if you had an integer associated type with this made up syntax:

protocol P {
  associatedtype A: let Int  // just to be clear Int is not a protocol
}

You could also do this:

func f<T: P>(...) {
  let myArray: InlineArray<T.A, Int> = ...
}

And you could conform to P in various ways:

struct S1: P {
  typealias A = 5  // not supported today, but could be
}

// no direct equivalent of S2

struct S3<let A: Int>: P {}

struct S4<T: P>: P {
  typealias A = T.A  // this is an integer type alias even though there is no direct indication!
}

The only new question is, given an arbitrary type parameter T.A.B..., to decide if it is an integer or a type. Today, the only type parameters of the integer kind are root generic parameters declared as such. If you added integer associated types, a member type could also be an integer, so the requirement machine would need to do a lookup to figure this out. This requires resolving the type parameter and checking the kind of the final associated type in the path, basically. It's not any different than how we implement the other generic signature queries like "is T a valid type parameter", "does T conform to P', and so on.

6

Can’t the type depend on the value of an existential?

7

It can, but you have to lift the existential's wrapped type to a type parameter by opening it first.

let p: any P = ...

func f<T: P>(_: T) {}

f(p)

It's true that the substituted type for T in the call to f() depends on the runtime value of p, so T.A (and just T itself) are unknown at compile time inside f(), but we're not directly referring to a type p.A in our syntax.

The classic example of a dependent type is a function type where the result depends on the parameter. For example, if you have a series of types 1, 2, 3, 4, ..., then a dependently-typed + operator would have a result type that depends on the input types -- it would be type of the integer that is their sum.

8

…and here I was thinking that the classic example of a dependent type was the return value of type(of:)

Although, something very similar to your example would arise naturally in a function that concatenates inline arrays:

concatenate<M, N, T>(_ a1: InlineArray<M, T>, _ a2: InlineArray<N, T>) -> InlineArray<M+N, T> {
    // insert magic here
}
9

I know the implementation is magic, but according to the type system the return type of type(of:) is provided as a type parameter: <T, Metatype>(T) -> Metatype.

In order to be able to spell it as a true dependent type, we’d need to be able to express something like <T>(a: T) -> <a.Type>.

(Doing a little experimentation, I found out that Swift already reserves the name Type, so the value.Type syntax is already available for dependent types :slightly_smiling_face:)

1 Like
10

I'm struggling to think of this as a type, even if it may be to the type system.

In SE-0452, I think we call them integer generic parameters. In the "Future directions" section, non-integer value generic parameters are considered, which are referred to as value generic parameters.

Maybe we could consider a new kind of associated parameter if protocols ever got this:

protocol P {
  associatedvalue a: let Int  // just to be clear Int is not a protocol
}

Maybe it would help answering this question:

1 Like