Generics in Val

[AbhinavK00]

I have some questions about generics, mainly about how powerful would they be in val.

1. Will they support something similar to cpp's template template parameters?
2. Can we pass concrete values as generic parameters? Like for writing trypes similar to std::array.
3. Variadic generics?
4. Generics specialisation?
5. Will there be something like constraint-less generics, that you can pass all types to?

[kyouko-taiga]

Sorry for the late reply.

Will they support something similar to cpp's template template parameters?

IIUC what template template parameters are, I think the answer is yes, using type requirements (a.k.a. associated types) in traits. If you point me to a concrete example, then I might be able to give a more comprehensive and definitive answer.

Can we pass concrete values as generic parameters? Like for writing trypes similar to std::array.

Yes.

Variadic generics?

That's on our wishlist but we haven't defined them yet.

Generics specialisation?

Yes, using conditional extensions and conformances.

Will there be something like constraint-less generics, that you can pass all types to?

Yes, but note that operations like copying, moving, or destructing will require a trait bound.

[dabrahams]

template template parameters correspond to higher-kinded types, whose capabilities are not covered by Swift associated type requirements.

[AbhinavK00]

Thanks for the answer! So, if there's nothing corresponding to HKTs, will there be other features to give similar power to generics?

[kyouko-taiga]

Val's support for generics will be very similar to Swift's, so you might have a look here for some details.

Currently, the two most significant improvements we have in the pipes are scoped conformances and generic value parameters. Scoped conformance lets us declare conformance of a type to a trait (in Swift, a protocol) in a specific scope. Generic value parameters let us express things like "a buffer of 12 integers" (Int[12] a.k.a. Buffer<Int, 12>) at the type-system level.

[kyouko-taiga]

Regarding HKT, I'm still on the fence as to whether or not the feature is worth its complexity. I think that associated types + opaque types + overloaded return types already offer a decent solution for most common use cases, like homomorphisms. For example, assume we define a Collection trait as such:

trait Collection {
  /// The type of the elements in the collection.
  type Element
  /// Returns a collection containing the elements in `self` transformed by `transform`.
  fun map<T>(_ transform: (Element) -> T) -> some Collection where .Element == Element
}

Then we could have an implementation of Set that returns a set and an implementation of Array that returns an array.

conformance Array: Collection {
  // This satisfies the requirement since `Array<T> <: some Collection where .Element == T`
  fun map<T: Sinkable>(_ transform: (Element) -> T) -> Array<T> { ... }
}
conformance Set: Collection {
  // This satisfies the requirement since `Set<T> <: some Collection where .Element == T`
  fun map<T: Sinkable>(_ transform: (Element) -> T) -> Set<T> { ... }
}
public fun main() {
  let s: Set([1, 2])
  let t = s.map(String.new(describing:))
  // The dynamic type of `t` is `Set<String>`
}

Of course, at compile time, the use site doesn't know that map is a homomorphism, meaning that the static type of t in this example is some Collection where .Element == String. So if we were to use methods specific to Set, the compiler would complain. But there are two ways to deal with that.

1. We can downcast the opaque type as an instance of the desired type:
   let s = Set([1, 2]); let t = s.map(String.new(describing:)) as! Set
2. We can overload map in each type implementing Collection. Overload selection will always prefer a concrete type over an opaque one so if we write s.map(...) where s is a Set, the result will be another Set rather than an opaque collection.

[griotspeak]

I was going to say that this example feels like it makes a solid case for HKT but, honestly, I think HKT as a term is just too loaded at this point.

One thing I want is something like this.

trait Collection {
  /// The type of the elements in the collection.
  type Element
  
  /// Returns a collection containing the elements in `self` transformed by `transform`. The default `Collection` type is `Self` but isn't strictly constrained to `Self`
  fun map<T, NextContext>(_ transform: (Element) -> T, _ nextContext, NextContext = Self) -> NextContext where
   NextContext: Collection, NextContext.Element == T
}

[kyouko-taiga]

The problem with this approach is that the conforming type won't know how to build an instance of NextContext without additional requirements. So it is not possible to create a generic map that's able to build any kind of collection.

We can pick a specific set of requirements but that would inevitably restrict choices.

trait Collection {
  type Element
  fun map<T, Next: Extendable>(_ transform: (Element) ->) -> Next
}

trait Extendable: Collection {
  /// Creates an empty instance.
  init()
  /// Appends an element to `self`.
  fun append(_ e: sink Element) inout
}

For instance, with this setup, you we no longer return a Set from Collection.map.

[kyouko-taiga]

Note that reduce(into:_:) is amenable to your wish:

public fun main() {
  let x = [1, 2, 3, 4]
  let y = x.reduce(into: Array<Bool>(), fun(s, i) { &s.append(i % 2 == 0) })
  let z = y.reduce(into: Set<String>(), fun(s, b) { &s.insert(b.description) })
  ...
}

[griotspeak]

I didn't feel like writing an augmented Collection type to get around this but it's not that much of a burden to include one of these

• a version of Collection that includes the necessary initializer and an append method
• a version of Collection that includes an initializer that takes an array of Element

or map could accept a closure to convert a collection of Element to the destination Collection type.

I don't know that the ability to create any Collection is what I was really after. Your initial code snippet doesn't achieve that and I don't miss it there. (one can only get the collections that implementors of map provide.) I'm not even saying that this should replace your initial proposal.

[kyouko-taiga]

or map could accept a closure to convert a collection of Element to the destination Collection type.

The problem is not to convert a collection into another. You can always write Next(x.map(foo)). The problem is to create instances of Next efficiently, i.e., without re-iterating over the base collection. We can do that with append because it tells the base collection how to construct the next representation.

Please have a look at my reduce(into:_:) example. I think it does what you want.

[griotspeak]

I gave three options in the hope that it would be clear that I do, in fact, understand the problem. I understand that there are compromises which is why, again, I'm not actually suggesting that you abandon the approach you initially described.

What I was spitballing was something like this:
fun map<T, NextContext>(_ transform: (Element) -> T, someNameImTooTiredToDreamUp: ([T]) -> NextContext) -> NextContext where…

because I was trying to avoid the argument about potentially creating a new NextContext with each append or allocating with each append or anything like that. The closure is basically a finalizer after you've transformed each element to T because the only thing we're missing is a constructor that we can pass neatly along with enough information to choose it at the appropriate moment.

heck, map(into:) is another idea since you've pointed at reduce a couple times and only requires that the into has an append or insert.

[DmT021]

I'd like to highlight several Swift's generics flaws so they could be considered beforehand.

• Generic associated types

protocol P {
  associatedtype Q<T>
}

Protocols in Swift support associated types, but there is no way to express a requirement for this type to be generic itself. The lack of this prevents composition of generics. A real world example why is it bad could be found in the Swift's stdlib. There is the Encoder protocol with the function func container<Key>(keyedBy type: Key.Type) -> KeyedEncodingContainer<Key> link
KeyedEncodingContainer<T>: KeyedEncodingContainerProtocol is a struct that wraps another value of KeyedEncodingContainerProtocol type with the generic class _KeyedEncodingContainerBox derived from the non-generic class _KeyedEncodingContainerBase to erase real type of the container.
All of this is required because there is no way to express this:

protocol Encoder {
  associatedtype KeyedEncodingContainer<Key: CodingKey>
  func container<Key>(keyedBy type: Key.Type) -> KeyedEncodingContainer<Key>
}

• Generic parameterization of extensions

extension<T> Array<T?> { ... }

• Type narrowing in a scope conditioned by type equality
• Parameterized generic parameters

type MyType<T<Q>> { ... }

Pretty much like the generic associated types this expresses the requirement of T to be a generic type (or type factory) with 1 parameter.

Also, I have some thoughts about where clauses. I think they might be used broader to support much more flexibly of generic types. For example support of several where clauses might be useful to provide different type implementations under the same name:

type MyType<T: String | Int> where T == String {
  // Implementation for String specialized MyType
} where T == Int {
  // Implementation for Int specialized MyType
}

Or where clause inside of the type's scope could express that some type's members included conditionally:

type MyType<T> {
  var field1: T
  
  where T: P {
    var field2: T
  }
}

[dabrahams]

Saying "consider Equatable (see also Rust's Eq)" doesn't, for me, point to any obvious use-case for generic associated types. The question isn't what generalities you can now capture with this feature, but what programs can you now write that you couldn't write—or couldn't write cleanly—before. Every language feature needs to be worth its weight, and I've not seen any examples that make generic associated types more compelling than HKTs, which we're regarding with a certain amount of skepticism.

Note that this example

protocol Encoder {
  associatedtype KeyedEncodingContainer<Key: CodingKey>
  func container<Key>(keyedBy type: Key.Type) -> KeyedEncodingContainerProtocol<Key>
}

I think is much better served by existing language features:

protocol KeyedEncodingContainerProtocol<Key: CodingKey> {
  associatedtype Key
  ...
}
protocol Encoder {
  associatedtype Container: KeyedEncodingContainerProtocol
  func container<Key>(keyedBy type: Key.Type) -> some KeyedEncodingContainer<Key>
}

[kyouko-taiga]

The ability to describe "equatability" to other types than Self seemed obvious to me.

trait Equatable<T = Self> {
  fun infix== (_: Self, _: T) -> Bool
  fun infix!= (_ a: Self, _ b: T) -> Bool { !(a == b) }
}

conformance Int: Equatable<Int8> {
  public fun infix== (_ a: Self, _ b: Int8) -> Bool { a == Int(b) }
}

public fun main() {
  let x = 1
  let y: Int8 = 2
  assert(x != y) // got 'infix!=' for free
}

[DmT021]

@dabrahams Are you talking about Swift in your alternative approach to Encoder issue? Correct me if I'm wrong, but you can't have an opaque return type in a protocol

[dabrahams]

Sorry, I missed that it was a protocol. In that case I understand… but I'm weakly skeptical that expressing this is worth the weight of the feature. I think that generic associated types are expressively equivalent to HKTs, FWIW:

protocol HKT {
  associatedtype G<T>
}

func f<K: HKT, T>(K.Type, T) -> K.G<T> { ... }

[kyouko-taiga]

I'm in two minds about this one. On one hand it's cool because it declares an explicit scoped key: Key. On the other hand if there is not one value but many of them with the same type, this would force us to check each of them.
Also I find it look a bit like optional dynamic casting syntactically.

Maybe we could do this kind of static narrowing with where clauses on local scopes instead:

fun foo<T,U>() -> Int {
  where T == U { return fast_path() }
  return slow_path()
}

[dabrahams]

The ability to describe "equatability" to other types than Self seemed obvious to me.

Sure that's obvious, but for its weight, this feature should enable some nontrivial algorithms to be written that couldn't be expressed well otherwise. I don't think deriving != from == counts. I don't think the need for heterogenous equality comes up enough to justify its weight. xs.indexOf(y) isn't much better than xs.indexOf(X(y)) and xs.elementsEqual(ys) isn't much better than xs.elementsEqual(y.lazy.map(X.init)). This feature is expressively equivalent (AFAICS), to multi-type traits, which might be a better fit for this particular case as there's not obvious "primary" type in this relationship. I thought I would want multi-type protocols when I started working on Swift and was surprised to find YAGNI, and I think there are a lot of "reasonable" generics features that are similar.

[Also == is an equivalence relation so you need to support both orders]

[kyouko-taiga]

I'm happy to let the need for this feature emerge. I suspect it will because there are many cases where it is inconvenient to be "stuck" with only one specific conformance to traits like Equatable, Comparable, or Encodable. I won't be sad if I'm wrong.

[DmT021]

btw, will function/subscript types be a part of the common type system or they will be kinda separate? This is a broad question to discuss, but in general there are only three questions:

1. Is it possible to express a constraint for a type to be function-type?
2. Is it possible for a given function type (A) -> B derive A and B
3. If (2) is yes, is it possible to statically derive (A) -> B from a closure/function. For example:

fun f(_: A) -> B

var x: TypeOf(f).ReturnType

[kyouko-taiga]

I haven't been able to find a good way to represent a function "bound" yet. I think we'd need variadics and a way to express passing conventions. Without the ability to describe the function's parameters, I'm not sure a trait would be that useful:

fun f<G: Function>(_ g: G) {
  // What can I do with `g`?
}

There's no type-level operation to query the parts of a function type, but that seems like a low hanging fruit in comparison to feature 1.

With some level of type erasure we can probably implement feature 3. Back to the opaque Function trait:

public fun main() {
  fun forty_two() -> Int { 42 }
  let f: any Function = forty_two
  print(f.return_type) // I can see that working reasonably easily
}

[DmT021]

I think we'd need variadics and a way to express passing conventions.

Arguments of functions with finite count of arguments could be expressed as a tuple, I think. But for args of variadic functions we would definitely need variadic generics.

trait Function<SelfType, Arguments, ReturnType, Throws> {
  associatedtype SelfType
  associatedtype Arguments: Tuple
  associatedtype ReturnType
  associatedtype Throws: Error | Never
  fun call(self: SelfType, arguments: Arguments) -> Result<ReturnType, Throws>
}

It doesn't make much of a difference, although there is function withoutActuallyEscaping whose signature would benefit from such constraint, but its more like an exception. What is tempting is that this way we are bringing function-types to the domain of nominal-types. For example it gives us an ability to write extensions on them.

extension Function {
  fun bind(self: SelfType) -> some Function<Void, Self.Arguments, Self.ReturnType, Self.Throws> 
}

About (3):
The reason I ask is a recent question on the swift forum where it was desired to passthrough a value of an opaque type, but to do this you should somehow refer to ReturnType of a function. I've found a workaround for Swift, but it would be better if there were a simpler solution.
Thread for context