[Pitch] Light-weight same-type constraint syntax

Words have meanings. We can’t just call chickens ducks because they seem vaguely similar. Similarly, “generic” is not some catch-all term for any sort of polymorphism.

Array<Int> and Array<String> are two distinct types. That’s what makes Array generic over its Element type.

(Independent of whether we use <> solely to denote generics or not, which is the overall topic of this thread:) If we have a protocol Sequence that’s generic over its Element type, then Sequence<Int> and Sequence<String> are two distinct protocols.

And if they are two distinct protocols, then a single type can conform to both of them.

Because P is not generic over its associated type T: there is only ever a single protocol P.

8 Likes

The other counter to "why not just have generic protocols" is to look at the list of associated types for Collection: Element, Index, Indices, Iterator, and SubSequence. While you can represent this as a protocol with five(ish) generic parameters, it wouldn't be a good user experience. (Rust traits allow both generic parameters and associated types for this reason.)

Generic protocols are a valid if complicated feature that we may or may not add to Swift, but they won't obviate associated types. It is possible that every associated type we would make "primary" is one it would make sense to be generic over, though.

9 Likes

Words have the meanings we ascribe to them. This would be a deliberate decision to (re)define “generic types” in a way that encompasses all function types, structs, classes, and protocols with type parameters.

My argument is that Array<Int> and Array<String> are distinct types in the same way that IteratorProtocol where Element == Character is distinct from IteratorProtocol where Element == Int. In the future, with generalized existentials, any Array and any IteratorProtocol are both unconstrained existential types. Values of type any Array can be constructed from values of type Array<Int> and Array<String>, just like values of type any IteratorProtocol can be constructed from values of type IndexingIterator<Int>.

Only by particular definitions of “generic type”. This particular definition conflates two different meanings of “type”. If we want to be more precise, struct S { } defines a type S, but also defines a datatype S. Values of datatype S have type S.

Meanwhile, struct Array<Element> { } defines a type Array, but there is no Swift expression with type Array. There are only Swift expressions of type “Array<Element> for some Element”. Yet the type Array certainly exists: it is the name of a type constructor whose kind is * -> *.

Generalized existentials propose the any operator, which can be applied to types. As such, for any Array to exist, Array must in fact be a type. And in fact, it is only useful to apply any to a higher-kinded type, since any Array<String> has only one inhabitant, Array<String>.

So an alternative definition of “generic type” could be “any type which, when prefixed with any, has one or more free type variables.” That definition encompasses not only any Array but also any IteratorProtocol. Allowing for that Swift spell the existential type as IteratorProtocol, you can substitute IteratorProtocol for anywhere Array appears above.

Do you have any use cases for generic protocols handy? Every way I could think of to use the ConstructibleFromValue example could also be achieved with conditional conformances, generics or existential types.

I believe the main feature they add over associated types is the capability to conform to a protocol in multiple ways. @OneSadCookie already pointed out the most common examples I can think of in Rust: conversion/borrowing traits (like From<T>) and operator traits (like Mul<T>). Swift, for better or worse, has arbitrary operator overloading instead of tying them to protocols, but the conversion traits are useful in practice (partly for operating on wrapped values, and partly just for providing a standard method name for conversions). So someone else would have to come up with a good example outside that.

My own use of Rust has had me defining very few generic traits, but I wouldn't necessarily take that as indicating they're useless. After all, our "folk knowledge" in Swift has been that plenty of people never need to define a protocol at all; they just use the ones defined in the stdlib or the SDK or their dependencies.

On the other hand, a certain past colleague who's worked on both the Rust and Swift standard libraries has commented that generic traits were more trouble than they were worth in Rust. I can ask them if they have more to say on this but they may or may not respond. (One example I can think of, though, is that if, say, String conformed to both Collection<Character> and Collection<UnicodeScalar>, String.Iterator would become ambiguous.)

I'm not yet convinced that "we're gonna want 'em" in Swift, but it's true that if we did add them, this would be the syntax people would expect, and if we took this proposal and then added generic protocols, we'd have some protocols you could conform to in multiple ways and some you couldn't.

7 Likes

Well this is exactly why I'm worried about this proposal and why I previously said that we're trying to jump over too many hoops at once. This proposal is additive but not incremental at all.

The community and the core team already explored the next steps in depth:

  1. unlocking the where clause in typealiases
  2. improving the UX with "one" possible, but unambiguous spelling such as P<.Assoc == T>

It won't kill anyone to start with (1), as it's purely incremental add-on. (2) is just "one" option to improve upon (1). However the proposal to me reads like (2) was already too much for the users to deal with and we need to improve even further. Excuse me, with all my respect, please give us at least (1) so we can start using the actual feature in question and not elaborate on how to improve with sugar code (proposal) over other hypothetical non-existing sugar code (2).


I'm sorry to bring this up again, but I have this quote stuck in my mind from @Chris_Lattner3 for similar sugar proposals:

6 Likes

There is one more thing that came back to my mind today. I don't see how the concept of primary associated types can deal with generic associated types. Making seemingly generic type parameters (primary associated types) generic (e.g. protocol P<G<T>>) seems to be fairly strange unless this would eventually become a generalized feature in regular generics as well (e.g. struct Foo<G<T>>). As far as my knowledge in that area goes, generic associated types could be used to workaround the absence of HKT in some places. In fact, this is also a note in the document linked above:

Note: generic associatedtypes address many use cases also addressed by higher-kinded types but with lower implementation complexity.

4 Likes

Pavel and I have done our research on the Generics Manifesto, Improving the UI of Generics, and many other generics discussions that have taken place on these forums. I am not aware of any official core team decisions that were made on the "next steps" for generics in Swift. Just because possible features have been discussed before does not mean that people are unable to propose new ideas, or variations of an already-discussed idea.

What we are proposing here is obviously different than what has been explored in the past. We hear your opinion that you're strongly against this proposal because it is the most obvious syntax for generic protocols. We believe that feature is unlikely to be added to Swift -- as explicitly stated in the Generics Manifesto -- and even if it was, that is a very advanced feature and we believe it's worth using the Collection<Int> syntax to mean a same-type constraint as proposed here. We also feel that Collection<.Element == Self.Element> or similar would be really onerous because this is the most common form of constraint that would be written using this syntax. (Note also that we're not completely tied to primary associated types being declared in angle brackets at a protocol declaration. There are alternatives.)

This is not an appropriate place to request that we work on a different generics feature that you're interested in. We have clearly stated our goal of designing more progressive disclosure and guidance into the generic programming experience, and that is what we are pursuing.

3 Likes

Please don't feel offended on the pushback through my commentary as I'm just trying to express my feedback the best way I can. That out of the way, please note that it's not only the generic protocols. Generic protocols is one thing, but I already mentioned several other features that cross the line with the proposal and issues I see with the prosed syntax and it's potential inflexibility from my personal day to day user experience.

Well I'm fairly surprised right now as "same-type constraint" as per this threads title is exactly the type of generic feature I outlined with (1) and there is nothing fundamentally different from what I was asking about. The proposal wants to unlock it, but without unlocking the incremental intermediate form of it, which I find very unnatural way of evolution.

Interestingly, C# has generic interfaces with multiple conformance but does not actually allow you to fulfill requirements more than once, nor does it allow partial specialization:

using System;

interface IGeneric<T> {
	int valP { get; }
	int valF<T>();
}

partial class C : IGeneric<int> {
	int valP { get { return 1; } }
	int valF<int>() { return 1; } // error CS0081: Type parameter declaration must be an identifier not a type
}

partial class C : IGeneric<string> {
	string valP { get { return 2; } } // error CS0102: The type `C' already contains a definition for `valP'
	string valF<string>() { return 2; } // error CS0081: Type parameter declaration must be an identifier not a type
}

static class M {
	public static int ExtMethod<T>(this IGeneric<T> me) {
		return me.val;
	}
}

I think most likely that's because inference would run into ambiguities (which might not be possible to resolve at the use-site?), or pick a wrong thing in some situations without the developer noticing, just like what Jordan mentioned with Collection<Character> and Collection<UnicodeScalar> conformances at the same time.

The ambiguity could be resolved with partial specialization, which Rust permits but C# does not.

Right, that’s what I was referring to when I said that ambiguities might not be possible to resolve at the use site.

In my opinion, the angle-bracket syntax on the protocol declaration implies a feature different than associated types, which may confuse users. While simplicity and progressive disclosure are high-priority goals, it is imperative that they be consistent with existing features. Nevertheless, I find the let list: Collection<Int>-style syntax incredibly appealing.

The obvious solution is to require that the associated type be declared with our current syntax. This raises the question: how will the compiler know what Collection<Int> refers to? Before searching for any solutions, we must ensure that the feature is intuitive, which requires that the declaration (e.g. protocol P<T>) and the use site (e.g. P<Int>) be syntactically similar. These are some approaches for preserving consistent associated-type syntax:

  1. Inline Signature Type Aliases

    (Naming suggestions are more than encouraged!)

    This is the simplest in my opinion. It employs the familiar generic-signature syntax with a twist: ostensive generic parameters (T in protocol P<T>) must refer to a formally declared associated type:

    protocol P<Self.T> { associatedtype T }
    protocol I<T> {} // ❌ No associated type 'T'
    
    let a: P, b: P<Int> // ✅
    
  2. Typealias Overloading

    I think it's been proposed before, due to its simplicity. It is a powerful and effective feature, that utilizes the existing protocol-declaration syntax, and enhances it with type alias' power to simplify and clarify API:

    protocol P { associatedtype T }
    typealias P<T> = P where .T == T
    
    let a: P, b: P<Int> // ✅
    

Other than this critique I wholeheartedly support the proposal!

EDIT: As @Tino points out, let b: P<Int> isn't in the scope of the proposal, so the example should be func b(_: P<Int>).


PS: Please don't mind my counterproposing. My goal isn't to shift the discussion to a topic the thread-starter finds irrelevant, but to offer a realistic solution to my criticism. Thanks to everyone involved for putting their time and energy that you put into this!

3 Likes

But exactly this won't be possible with the pitched change (will it??)

However, with generic protocols…

protocol AnyIterator<Element> {
  // no associated objects, but
  mutating func next() -> Self.Element?
}

protocol AnyCollection<Element> {
   // no associated objects, but maybe some methods that need no parameters but Element
  func makeIterator() -> AnyIterator<Element>
}

extension Iterator: AnyIterator<Element> {} // hey, that's easy - everything is already there!
extension Collection: AnyCollection<Element> {}

would be good enough for me — especially when you consider

protocol CollectionWithIndex<Index> { // too bad we can't have named parameters for generics :-/
    // Collection-requirements…
}

extension Collection: CollectionWithIndex<Index> {}

protocol CollectionWithElementAndIndex<Element, Index>: AnyCollection<Element>, CollectionWithIndex<Index> {}

var list: CollectionWithIndex<Int, Int> = [3, 1, 4, 1, 5, 9, 2]
// do some collection-stuff
list = someOtherCollectionOfInts

If we did have a shorthand for protocol constraints, I think it's very important that it handle subtype constraints, too. I don't think they can be separated; same-type constraints alone aren't work the radical new syntax.

IMO, same-type constraints often aren't what you want, especially as a beginner to generics. Imagine I have some algorithm which starts as operating on an array of strings:

func frobinate(strings: [String])

Then one day I learn about Swift's cool lazy collection views, but this code doesn't work with them. So I try to make it generic to any Collection, using this obvious syntax that we've decided to make so lightweight:

func frobnicate<C: Collection<String>>(strings: C)

// or:
// func frobinate(string: some Collection<String>)

OK - that works. Later, I realise that all of these Strings live as separate heap allocations with their own lifetimes, and creating all of those strings is slowing my App down. I used String when I wrote this function, because that's the default text type people should reach for -- but it could work just as well with Substring.

Swift has a protocol to make that kind of processing easier - StringProtocol. So I change my function again:

func frobnicate<C: Collection<StringProtocol>>(strings: C)

// or:
// func frobinate(string: some Collection<StringProtocol>)

Now something very interesting happens - my function will work for Arrays of strings and substrings, but not for other collections :thinking:

protocol MyStringProtocol {}
extension String: MyStringProtocol {}
extension Substring: MyStringProtocol {}

func frobinate<C>(
  strings: C
) where C: Collection, C.Element == MyStringProtocol {}

let arrayOfStrings: [String] = ["hello"]
frobinate(strings: arrayOfStrings) // OK

let lazyCollectionOfStrings = (0..<10).lazy.map { String($0) }
frobinate(strings: lazyCollectionOfStrings) // ERROR - 'String' and 'MyStringProtocol' must be equivalent

See the problem? Collection<StringProtocol> means a collection of existentials - and while Array has special implicit conversions, other collections don't. What the developer actually wanted to write was Collection where Element: StringProtocol - with a subtype constraint for the element type, not a same-type constraint.

With SE-0306, all protocols will be usable as existentials, so things like Collection<StringProtocol>, Collection<Numeric>, etc. would be valid. That adds a whole new dimension to the problem, IMO.

I think that observation applies generally - when a subtype constraint will do what you want, it's generally preferable to a same-type constraint. They definitely do have uses (Collection where Element == UInt8 is very important for working with sources of bytes, for example), but the whole point of generic programming is to loosen your algorithms to be based on semantics and capabilities rather than specific types.

So what I'm saying is: I don't think same-type constraints alone are worth this fuss.

6 Likes

Are you proposing that <T: Collection<Numeric>> be interpreted as <T: Collection> where T.Element: Numeric?

I think you're referring to 309.

Note that the pitch proposes that in requirement positions, like you mentioned, the new syntax is a shortcut for a long version with associated type name in a where clause, so <T: Collection<String>> would indeed be <T: Collection> where Collection.Element == String we could support more bound kinds too if that is desirable… Although the idea here is to unify the angle branches between protocols and generics which only support same-type constraints.

I think this is more evidence that you’re trying to unify things that are actually more different than they appear, and supports my contention that this will make it harder to go from beginner generic programmer to actually understanding how stuff works.

2 Likes

I'm not sure what you mean by more evidence. We did unify the behavior in the pitch with generic parameters in the where clause e.g.

protocol P {
}

class A<T: P> {
}

func test<T: A<P>>(_: T) {}

Doesn't work either because P is considered a same-type constraint in <T: A<P>> context.