An Implementation Model for Rational Protocol Conformance Behavior

@Douglas_Gregor, for your consideration sometime after the WWDC crush ends:

Regarding conformance of a type to a progressively refined protocol hierarchy, it appears that the Protocol Witness Table Pattern for a conditional conformance to a "child" protocol disregards the default implementations declared by that protocol.

For the sake of clarity, here is a minimum example:

protocol P { var id: Int { get } }
extension P { var id: Int { 1 } }

protocol Q: P {}
extension Q { var id: Int { 2 } }

struct X<T>: P {}
extension X: Q where T: Equatable {}

func callId<T: Q>(_ t: T) -> Int { t.id } // dispatches to `P.id` even thought T: Q

print( callId( X<Int>() ) ) // "1", not "2"

In the resultant binary, the Protocol Witness Table Pattern for X: Q does not point to Q.id as the witness for the id requirement. AFAICS, the table pattern for X: Q solely points to the protocol witness table for X: P.

excerpts from binary
_$s4main1XVyxGAA1QAASQRzlWp:  
    // protocol witness table pattern 
    // for <A where A: Swift.Equatable> main.X<A> : main.Q in main
0000000100002030         db  0xe4 ; '.'  << first word points to Q protocol descriptor
0000000100002031         db  0x1e ; '.'
0000000100002032         db  0x00 ; '.'
0000000100002033         db  0x00 ; '.'
0000000100002034         db  0x01 ; '.'
0000000100002035         db  0x00 ; '.'
0000000100002036         db  0x00 ; '.'
0000000100002037         db  0x00 ; '.'
0000000100002038         db  0x20 ; ' '  << second word points to PWT for X: P
0000000100002039         db  0x20 ; ' '
000000010000203a         db  0x00 ; '.'
000000010000203b         db  0x00 ; '.'
000000010000203c         db  0x01 ; '.'
000000010000203d         db  0x00 ; '.'
000000010000203e         db  0x00 ; '.'
000000010000203f         db  0x00 ; '.'
_$s4main1XVyxGAA1PAAWP:        
    // protocol witness table for main.X<A> : main.P in main
0000000100002020         db  0x18 ; '.'  << points to protocol conf descriptor for X: P
0000000100002021         db  0x1e ; '.'
0000000100002022         db  0x00 ; '.'
0000000100002023         db  0x00 ; '.'
0000000100002024         db  0x01 ; '.'
0000000100002025         db  0x00 ; '.'
0000000100002026         db  0x00 ; '.'
0000000100002027         db  0x00 ; '.'
0000000100002028         db  0x60 ; '`'  << points to P.id.getter witness
0000000100002029         db  0x19 ; '.'
000000010000202a         db  0x00 ; '.'
000000010000202b         db  0x00 ; '.'
000000010000202c         db  0x01 ; '.'
000000010000202d         db  0x00 ; '.'
000000010000202e         db  0x00 ; '.'
000000010000202f         db  0x00 ; '.'

When calling into the Q-constrained generic context of callId<T: Q>(_ t: T) -> Int, the assembly code correctly selects and passes an instantiated X: Q Protocol Witness Table. But, since the table doesn't point at the Q.id witness, the call to id is dispatched to the P.id witness.

excerpt from assembly code
                     _main:
push       rbp
mov        rbp, rsp
sub        rsp, 0x20
mov        rax, qword [_$sSiN_100002008]      ; _$sSiN_100002008
mov        dword [rbp+var_4], edi
mov        rdi, rax                           ; argument #1 for method X.init
mov        qword [rbp+var_10], rsi
call       _$s4main1XVACyxGycfC               ; main.X.init() -> main.X<A>
xor        ecx, ecx
mov        edi, ecx                           ; argument #1 for method _$s4main1XVySiGMa
call       _$s4main1XVySiGMa                  ; type metadata accessor for main.X<Swift.Int>
mov        qword [rbp+var_18], rax
mov        qword [rbp+var_20], rdx
call       _$s4main1XVySiGACyxGAA1QAASQRzlWl   ; lazy protocol witness table accessor
                                               ; for type X<Int> and conformance 
                                               ; <A where A: Equatable> X<A> : main.Q

mov        rsi, qword [rbp+var_18]             ; argument #2 for method main.callId
mov        rdx, rax                            ; argument #3 for method main.callId
call       _$s4main6callIdySixAA1QRzlF         ; callId<A where A: main.Q>(A) -> Int
xor        ecx, ecx
mov        qword [_$s4main6resultSivp], rax    ; _$s4main6resultSivp
mov        eax, ecx
add        rsp, 0x20
pop        rap
ret

Yes, the X: Q conformance is conditional, but since the table is used only in contexts in which the condition is satisfied, the table should (?) point to Q's implementations.

Am I misunderstanding?

Hi Matt,

AFAICT this code is almost the same as my earlier example. My id2 (which corresponds to callID in your example) would be on an extension of Q rather than of P. So your example effectively points out that the P requirement id is satisfied the same way for the X<T>:P witness table as for the X<T>:Q witness table. I find that mostly unsurprising given the (always re-surprising!) fact that X<T> can only conform to P “in one way.” It's also nearly the same as your earlier example except in that example your P requirement a() (which corresponds to id) is being accessed through a different P requirement b(), rather than a non-requirement (callId/id2).

Also, all of these semantics seem consistent with what @Jens pointed out about the original proposals: we were warned. It's only since I realized this had serious negative consequences for generic programming that I've started hearing @Douglas_Gregor suggest that it could be changed. However, there are two very open questions still, AFAICT:

  • Is Doug actually talking about the same things we are? So far his description has been in very implementation-centric terms that don't map clearly onto a programming model.
  • Can we change the language semantics and call it a bug fix, even if the language implements exactly or nearly what was proposed and accepted?

Surely WWDC pressure explains why we don't have answers yet; I look forward to Doug's re-engagement after the conference is over.

1 Like

Ok. This is awful, wonderful, ironic, annoying and hopeful. Awful: my mental model of the system is broken. Wonderful: my eyes have been opened, now, thanks to patient feedback from you and several others. Ironic: my mental model was learned from experimenting with Sequence, Collection, et al. Annoying: it is remarkable how much isn't written down. Hopeful: mental models can be repaired.

After very carefully re-reading SE-0143 and, especially, the parts pointed to by @Jens, I can say that @Douglas_Gregor certainly used some very precise language ("When satisfying a protocol requirement, Swift chooses the most specific member that can be used given the constraints of the conformance") to explain a very specific example ((X1<X2>() as P).f()). Originally, I'd understood, "given the constraints of the conformance," to refer to the constraints imposed at the point of use of the type. I also understood that (X1<X2>() as Q).f() (note the Q rather than P) would yield the specialized implementation of f(), as defined on Q. As I'll explain in a moment, there exists good precedent for that (mis-)interpretation.

BTW, hats off to the compiler engineers. After digging into the guts of the implementation, I am amazed by the level of complexity required to model the semantics, by the precision with which they do so, and by the enormous amounts of care and attention that must go into making all the parts work together correctly. I have a great deal of respect for them and what they do.

"In One Way"

So, about the in-one-way rule: exactly how is it defined? It sounds simple enough, but, in practice, it appears more nuanced. In the context of my example, I see at least three different ways that it could be applied:

Sequentially conforming to `P` and then to `Q`.

X<T> conforms to P, as follows:

  1. P requires that a conforming type have a var id: Int { get }.
  2. X<T> is unconditionally conformed to P.
  3. X<T> itself does not implement P's id requirement, and so it needs to rely upon a default implementation of id.
  4. In the context of X<T> conforming to P, the only default implementation available is P.id, and so, through that implementation, X<T> satisfies the requirement.

X<T> conditionally conforms to Q, as follows:

  1. Q: P.
  2. Q has no requirements of its own other than that the conforming type must conform to P.
  3. The conformance to P already is satisfied, and so X<T> conforms to Q.
  4. Since the Q.id implementation is not used by X<T> to conform to Q, it merely "shadows" P.id.

OR

Holistically conforming to both `P` and `Q` in the most specialized way possible.

X<T> conforms to both P and Q, as follows:

  1. The conformance to P is unconditional.
  2. The conformance to Q is conditional.
  3. The only requirement is the P.id requirement.
  4. X<T> itself does not implement P's id requirement, and so it needs to rely upon a default implementation of id.
  5. Both P and Q have default implementations of id.
  6. We would prefer the Q.id implementation, as the more specialized implementation of id.
  7. But Q.id is available only when the condition for the Q conformance is satisfied, so Q.id is not always available to satisfy the id requirement.
  8. Since X<T> can conform to P only in one way, the sometimes not available Q.id implementation cannot be used to satisfy the requirement.
  9. The P.id default implementation is available at all times, and can satisfy the requirement, so it is used by X<T> to conform to P.
  10. Since Q has no requirements of its own other than conformance to P, X<T> conforms to Q by virtue of its having satisfied the requirements of P in the manner specified, here. In other words, for purposes of conforming to Q, X<T> does not independently redetermine if there is a better way to conform to P under the state that exists when the condition to the conditional conformance is satisfied.

OR

Independently conforming to each of `P` and `Q`.

As described, above, X<T> satisfies the requirements of P via the default implementation provided by P.id. Then, independently, the best possible conformance for X<T> to Q is determined, with the conformance to P effectively being re-evaluated on the basis of the condition to the Q conformance assumed to be true. On that basis, Q.id would be selected as the implementation that satisfies the id requirement for purposes of Q.

I'm not sure there are on-point discussions or examples in SE-0143 that clearly specifies the intent. And, AFAICT, the formal documentation of protocol conformance does not address this aspect of the matter.

It seems that, what I characterize as the "holistic" conformance method, is closest to what the compiler actually does and what those well-versed in the system understand it to be doing.

If the possibility of revising conformance behavior is put on the table, I'd suggest consideration of whether the "independent" conformance method (A) is better aligned with what intuition would provide and (B) might help to facilitate providing more specialized conformances at the ultimate point of use.

The Collection Protocol Irony

The irony is that (unless I am mistaken) the "expected" behavior of P, Q and X<T> in my example in the post, above, is the behavior that is actually provided today by Swift via the canonical example of Collection, BidirectionalCollection and custom collection types.

I first learned about conditional conformance and the power of a protocol hierarchy by progressively conforming types to Sequence, Collection/MutableCollection, BidirectionalCollection, et al. I observed and internalized their behavior.

Of particular relevance, I saw and appreciated that, as a type was progressively, conditionally conformed through the steps of the hierarchy, certain methods gained functionality and/or improved in efficiency. Using our standby example of Collection's requirement of distance(from:to:), it goes from a default implementation of one-way on Collection to bidirectional on BidirectionalCollection. That enhanced capability is available both on concrete instances and in appropriately-constrained generic contexts.

Take for example:

A walk through a custom type conformed to `Collection`, and its protocol conformance behavior.
// Create a type.
public struct Things<T> {
  private var _elements: [T]
  init(_ elements: T...) { _elements = elements }
}

// Extend it to conform to MutableCollection with just a few keystrokes.
extension Things: MutableCollection {
  public var startIndex: Int { 0 }
  public var endIndex: Int  { 3 }
  public func index(after i: Int) -> Int { _elements.index(after: i) }
  public subscript(position: Int) -> T {
    get { _elements[position] }
    set { _elements[position] = newValue }
  }
}

// Use Collection's algorithms, like its distance(from:to:) requierment.
let fourStrings = Things("A", "B", "C", "D")
let d1 = fourStrings.distance(from: 0, to: 3) // 3

// The default implementation of distance(from:to:) declared by Collection is restricted to forwards-only traversal.
let d2 = fourStrings.distance(from: 3, to: 0) // TRAP: Can't go backwards

// Extend it to conform to BidirectionalCollection.
extension Things: BidirectionalCollection where T: StringProtocol {
  public func index(before i: Int) -> Int { _elements.index(before: i) }
}

// Now, distance(from:to:) works backwards.  BidirectionalCollection declares a better default implementation in one of its extensions.
//let d2 = fourStrings.distance(from: 3, to: 0) // -3

// We can use it in a generic context.
// And we still get that cool bidirectional implementation of distance(from:to:).
func distanceFromEndToStart<T: BidirectionalCollection>(from t: T) -> Int {
  t.distance(from: t.endIndex, to: t.startIndex)
}
let d3 = distanceFromEndToStart(from: fourStrings) // -3

// But, wait. The methods distance(from:to) is a requirement of 
// Collection, and the conformance of Things to BidirectionalCollection 
// is conditional, and since Things<T> can conform in "only 
// one way" to Collection's requirement of distance(from:to), 
// that one way should be the unconditional Collection.distance(from:to:)
// implementation.  But, Collection and BidirectionalCollection 
// aren't playing by that rule.

My example, in the post, above, mirrors this sort of usage of the Collection hierarchy:
X<T> = a generic type ready to be turned into a collection
P = Collection
Q = BidirectionalCollection
id = direction(from:to)

I posit that, what people intended with conditional conformance is the behavior exhibited by direction(from:to). In a generic context constrained to BidirectionalCollection, when one calls direction(from:to), they get the more-specialized BidirectionalCollection implementation. By contrast in my example in the previous post, in a generic context constrained to Q, when one calls id, they get the less-specialized P implementation.

Miscellaneous

some specific responses that may not be of general interest

Plagiarism.

Precisely. I posit that, by not specializing the PWT for X<T>:Q, the system may be missing an opportunity. In my (totally incomplete and ill-informed) look at the implementation details, it seems that Q.id could be noted and used in the X<T>:Q PWT without any impact on the runtime and with little impact on binary size and compile times. I must be wrong, but until someone shows me why, I'll keep asking about it.

At the end of the day, it doesn't get you all the way to being able to have a P.id2 default implementation that can dynamically dispatch to P.id or Q.id depending upon the underlying concrete type, but it gets you pretty far down that road.

I simplified it (taking your suggestion), and then moved it into a generic function to highlight that the context is constrained to Q.

2 Likes

There are many threads going on here, so I'll redirect to where folks have uncovered more. The override/@_nonoverride behavior for protocols is there to approximate a model where one gets the most-specifialized witness at the point where all types have been made concrete (even if that's at runtime).

Doug

2 Likes

Hi Doug,

I took some care to craft questions for you in this thread that would help move the conversation forward. I understand of course that WWDC prevented timely answers, but seeing your post here I'm wondering how to proceed. Do you want to catch up with this thread and discover the questions, or shall I re-post them, and if they should be re-posted, would you prefer to follow up in the other thread?

[EDIT: FWIW, I've been thinking of the other thread as a free-wheeling place to explore details. It seems like it has multiple different ideas being discussed. I'd like to suggest keeping the questions raised by Dave, here, in this thread.]

Thanks, Doug.

On a separate note, FWIW, I've been writing up a semantic-level explanation of protocol conformance. Out of that explanation, I am starting to see the makings of a mental model that might helpfully encapsulate the workings of the system, as it exists today. To be continued...

At a technical implementation level, I'm wondering about the plusses and minuses of slightly revising the logic for selecting witnesses for protocol witness tables. Take our running example involving P, Q: P, X<T>: P, and X: Q where T: Equatable. The "slight" change would be, when the PWT for X: Q is constructed, it is recognized that Q has an id implementation and that that implementation happens to correspond to a requirement of a protocol from which Q inherits, namely P. Based on that recognition, the Q.id implementation is inserted into the PWT for X: Q. As is already the case in the current system, when entering a context in which a given X<T> actually does conform to Q, the Q witness table will be selected. Thus, when a call to id is made in that context, the call would be dispatched to the Q.id witness. If generalized, does that approach seem feasible, technically? Am I failing to think of obvious other cases where that approach creates trouble? (Leaving aside the fundamental issue of source breakage.)

Thanks, again.

Yes, it's the same things. In the example with P, Q, and X<T>. I think expanding the example is useful to illustrate the "conforms in one way" bit, e.g., add

struct NotEquatable { }

print( callId( X<NotEquatable>() ) ) // "1"

When the conformance of X<T>: P is established, there is only a single definition of id that is guaranteed to work for any T: the one on the extension of P. So that one gets picked, and will be the same regardless of what T ends up being substituted with. The conformances for any X<T> to P behave uniformly.

Y'all have found override and @_nonoverride. One can use @_nonoverride to introduce a new requirement in a more-refined protocol, which then selects a witness on its terms. Let's extend the example to introduce a non-overriding id requirement in Q.

protocol P { var id: Int { get } }
extension P { var id: Int { 1 } }

protocol Q: P {
  @_nonoverride var id: Int { get } // introduces a unique requirement `id`
}
extension Q { var id: Int { 2 } }

struct X<T>: P {}
extension X: Q where T: Equatable {}

func callIdAsP<T: P>(_ t: T) -> Int { t.id } // dispatches through `P.id`
func callIdAsQ<T: Q>(_ t: T) -> Int { t.id } // dispatches through `Q.id`

print( callIdAsP( X<Int>() ) ) // "1"
print( callIdAsQ( X<Int>() ) ) // "2"

In the conformance of X<T>: P, the id defined in the extension of P is the only viable witness that works for any T. Hence, the requirement P.id is satisfied by the id defined in the extension of `That's the same answer we had in the prior example.

In the conformance of X<T>: Q, both the id defined in the extension of P and the id defined in the extension of Q can be used to satisfy the requirement Q.id. The id defined in the extension of Q is more specific, so that is used to satisfy the requirement Q.id.

These two choices are made independently.

Now, to the uses. In callIdAsP, the only way to type-check t.id is to go through the requirement P.id, so we get "1" in the call given X<Int>.

In callIsAsQ, the expression t.id can either call through the requirement P.id or the requirement Q.id. Overload resolution picks Q.id, because it is more specific, so we get "2" in the call given X<Int>.

We can change the semantics. That might need to be staged in with a version bump (e.g., Swift 6), but I wouldn't get too caught up with the "when" part of this. Figure out what the model should be.

The model I've been imagining would collect the set of potential witnesses at the point where the conformance was declared, but delay the selection of the "best" witness to satisfy a given requirement until enough information is available---whether that happens at compile time or at run time.

For example, rewind back to the conformance X<T>: P. The id defined in the extension of P is a viable witness that works for any T. The id defined in the extension of Q is potentially viable; it depends on whether the actual type substituted for T conforms to Equatable and, if so, it is more specific than the id defined in the extension of P. Hence, we would need to delay the decision of the "best" witness until we have a concrete type substituted in for T. For T=Int, Int conforms to Equatable so the id defined in the extension of Q will be selected as the witness. For T=NotEquatable, the id defines in the extension of P will be selected as the witness.

For the conformance X<T>: Q, both the iddefined in the extension ofPand theiddefined in the extension ofQare viable, and the one in the extension ofQis better, so the one in the extension ofQ` is selected as the witness. There is no reason to delay the decision until concrete types are available, because the decision won't change.

All of the examples written/mentioned above would print 2 for X<Int>, regardless of how they are called. And 1 for X<NotEquatable>, of course.

In this model, @_nonoverride can probably remain a hidden relic, needed only to maintain ABI for the Standard Library where it is used.

The shape of a protocol's witness table is established by the protocol itself; each type that conforms to a protocol must provide a witness table that matches that shape. The protocol Q from the original example does not contain an entry for id; only P contains such an entry, because P declares the requirement id. What you describe matches up with the @_nonoverride trick I describe above.

There are 135 messages in this thread, 65 in this thread, and 67 in this thread.

Doug (just one me)

2 Likes

Yeah, I see why you say that this band-aid only provides “mostly” the right behavior, because it's not really reflective of the right semantics. It only happens to work out to the extent that every specializable algorithm is reimplemented for for a generic type's conditional conformance, so that the instance never “escapes” into a context where a less-refined protocol is the constraint. As SR-12881 shows, that requires more care than even the standard library team can apply, and is not going to scale at all to a world where new specializable algorithms can be added retroactively—a feature we need in order to fulfill the goal of fully supporting generic programming.

The right semantics are that an algorithm defined for protocol P and specialized for protocol Q uses the Q implementation when invoked on a Q-conforming type, no matter the constraints in effect when the algorithm is invoked.

Good. If we can agree that the current semantics should change, whether we call the current behavior a bug or just a design that needs to be updated doesn't matter.

(emphasis mine)

Okay, before we go much further: from what we're doing here @mattrips and I intend to produce reference documentation that can be used by programmers to understand the intended behavior of the language. I consider it my job in this discussion to ensure the terms we end up using to describe the semantics are in the domain of a viable programming model. I trust you to keep an eye on implementability and to translate between those terms and your implementation model. I'm not saying we can't discuss implementation details here, just that we need to draw a line that distinguishes implementation details from the programming model and end with a result that can be described entirely on the programming model side of the line.

  • Right now, “witness” is not a part of the Swift programming model. I think it could be, especially if it has a simple definition in programming-model terms, like “implementation or type used to satisfy a protocol requirement.” Do you think we need this term in the programming model, and is that a good definition?
  • I would like to keep “witness tables” out of the programming model if at all possible; my sense is that it would couple the model to the current implementation too tightly, and the implied obligation to keep the term meaning the same thing in both domains would make the programming model hard to understand. In particular…
  • I am very motivated to avoid describing the programming model in terms of anything like the decision procedure you've talked about putting in PWTs. I believe that creates an unnecessary level of complexity for users and the semantics of the system can be described much more simply, whatever the implementation. [edit: to be clear, I mean that if we talk about PWTs containing entries that may point to decision procedures, we won't end up with a good programming model. I'm actually quite certain that the logic encoded in your decision procedure is going to have to be described in one form or another as part of the programming model]
  • The “as if” rule, of course, applies to the programming model. Given the agreed-upon desire to change the semantics, and the facts of separate compilation and infinite types, some generic dispatching decisions always need to be made at run time. Therefore for the programming model, there's no point in discussing compile time dispatching decisions except as a possible optimization.

All of the examples written/mentioned above would print 2 for X<Int> , regardless of how they are called. And 1 for X<NotEquatable> , of course.

Good, that's the right behavior.

In this model, @_nonoverride can probably remain a hidden relic, needed only to maintain ABI for the Standard Library where it is used.

Also good. I still believe we want a feature to unambiguously identify intended specializations, but @_nonoverride is only in the same ballpark, not the right feature.

I understand. I'm still very interested in your reaction to the suggestion at the bottom of this post, if you have a moment to think about it.

3 Likes

Scoped conformances are a reasonable direction; I have quibbles with the dynamic casting approach taken in that proposal, but having the ability to keep conformances scoped within a module seems reasonable. Capping retroactive conformances at internal visibility seems surprising to me, because I don't think programmers tend to think about retroactive conformances any differently from "normal" conformances, so it would take a lot of explaining to say "ahh, for this one you need an explicit public, but over here it's implicit."

From an implementation standpoint, I'd really rather see us fix the implementation of the model that exists before extending it with more features. The type checker needs to properly diagnose ambiguous conformances when it sees them at compile time. The runtime needs to diagnose ambiguous conformances when it sees them at run time. The runtime demangle-to-type-metadata path needs to account for retroactive conformances---they're literally there in the mangling scheme in the ABI, but we ignore them---so we get consistent behavior. You can't implement scoped conformances without getting these fundamentals right.

Doug

2 Likes

Maybe. I'd have to talk specifics before agreeing to this point, because it depends on how retro "retroactively" really is.

See, there are lots of implementation-level concerns here that make this statement probably too absolutist. Is the algorithm a protocol requirement or is it only implemented in a protocol extension? Is the specialization for Q visible at the point where the the algorithm was defined? I care less about specific answers to these questions and more that there is an awareness that the dispatch mechanism remains predictable and efficiently implementable.

Sounds great!

That's a good definition, but it's also a mouthful. I find it useful to have the term "witness" be in the lexicon.

That's fine. Witness tables collect together the witnesses that are used to specify a particular conformance of a type to a protocol. We can just talk about "the conformance" here.

That's fine, so long as an efficient decision procedure exists. From a semantics standpoint, it's better to characterize the solution than the algorithm that produces the solution.

Again, I disagree because implementability is not a second-order concern. If your programming model requires the decision procedure that is executed at runtime, its efficiency is crucial. If there is no efficient implementation, you don't get to have that programming model.

Doug

1 Like

So ask me a question; I don't know what you're thinking of as potentially problematic. That said, I'm not committed that all specializable algorithms, for all time, should be described in terms of protocol requirements. As I've mentioned in this thread before, I think there are good arguments for an orthogonal language feature to support this capability—one that probably wouldn't be constrained in the same way a feature like “retroactive addition of protocol requirements” would have to be.

I think this is just about getting terminology straight. When I say "specializable algorithm" I'm speaking the language of generic programming, above even the level at which the programming model must be communicated. In talking that way, I'm trying to describe what the eventual programming model needs to be able to cleanly express. The implementation used for a specialized algorithm that is invoked from a generic context should depend on the dynamic types of the arguments. The only thing about the invocation context that should be able to affect the outcome is visibility of the specializations at that point, not the static type constraints.

In Swift today, the only language-supported way of defining a specializable algorithm (other than via non-final methods of classes) is via protocol requirements. Overloading and masking don't count as algorithm specialization in the way that I mean it.

Is the specialization for Q visible at the point where the the algorithm was defined?

Today the only language-supported way of expressing an algorithm specialization (other than via methods of classes) is via a constrained protocol extension. The visibility of a specialization at the point where the protocol requirement is defined is not relevant to whether the specialization gets used, and I can't imagine changing that.

I care less about specific answers to these questions and more that there is an awareness that the dispatch mechanism remains predictable and efficiently implementable.

Predictability: of course. Remember I'm the one going on about framing a usable programming model. Efficiently implementable: of course. I'm not even interested in negotiating about the dispatch mechanism.

Are you asking for a shorter/simpler definition of the term “witness?”

  • …Schnipp good schtuff I agree with…

Sorry, I think we're mixing up two things here. AFAICT you're talking about how we decide what the programming model is, which I of course agree must be governed by efficiency and implementability concerns. I'm talking about how the programming model is described to programmers. Swift has never gone out of its way to describe to its users what calls are dispatched at compile-time except as an optimization. While many of us would like to see that change, I don't think it's feasible to initiate that kind of change here. If the programming model can be entirely described in terms of run-time dispatching but not in terms of compile-time dispatching, trying to use both kinds of description is just going to make the description needlessly complicated.

If I define an algorithm in an extension on Collection in module A, can I add a new specialization of that algorithm in module B?

We're at the point where talking in the abstract is not really helpful. I know what algorithm specialization is in the abstract, and Swift's overloading allows you to express algorithm specialization when working entirely with concrete types, but I don't know what you're thinking for expressing algorithm specialization in a manner that meets your expectations.

Doug

If I define an algorithm in an extension on Collection in module A , can I add a new specialization of that algorithm in module B ?

Yes, being able to publicly vend a generic algorithm that can be composed with other generic algorithms and specialized for a specific model of the protocol it operates on, from the module where that model is defined, is important.

FWIW, this capability can be mapped directly onto support for retroactive protocol refinement without raising any of the dynamic casting burdens that are the only obstacle to the feature mentioned by the Manifesto. In any case, I'm trying to say this capability is a long term goal of mine that—conceivably—might not even look like protocol extensions: maybe it's some kind of multimethod. I don't think it affects the work we do in this thread much, except that I'll keep my eyes open for anything that definitively rules out solving the problem eventually.

We're at the point where talking in the abstract is not really helpful. I know what algorithm specialization is in the abstract, and Swift's overloading allows you to express algorithm specialization when working entirely with concrete types, but I don't know what you're thinking for expressing algorithm specialization in a manner that meets your expectations.

I was trying to define algorithm specialization for the context of this discussion about generic dispatching. But if that bugs you, forget about it. I believe my reply to you contains concrete, non-abstract answers to everything you've asked me, so if there are unanswered questions please re-ask them.

Hopefully Apple will announce their iClone project along with their new iPhones this fall.

Hey, @Douglas_Gregor!

I've prepared this gist to demonstrate something I keep asserting but I can't tell whether you agree with: given the lack of monomorphizability, some ambiguities in witness selection cannot possibly be detected until runtime if you want to change semantics in the way we've been discussing.

So... What is the current consensus? Fixing this by the 6.0 release? :relaxed:
Because I have just come to a great idea, which is: let's add to a process of archetype construction a notion of context (that is the current module, aka the most recent refinement).

//module S
protocol A { var uo: Int {get} }
extension A { var uo: Int {42} }
struct Alpha: A {} 
//this has archetype S.Aplha with witness from S.A

//module T
import S
extension Alpha: A { var uo: Int {69}}
//this has archetype T.Alpha with witness from T.Alpha
//Yes, single redeclaration in different module should be allowed

From here, we dance: compiler builds the internal code from external modules and then it becomes a different realm (nothing can touch it from public domain), then it selects the witnesses (redeclarations) in the current root (in the example above it is module T), and after, it descends the imports graph, picking the witnesses of most recent refinement from external modules for missing conformances.
What do you think about that kind of a monomorphizing solution?

Checkout this btw

As you are probably well aware, a conformance is abstractly a function that takes a type and returns a set of witnesses. If we want to be able to make these witness choice decisions deterministically, then we need to somehow incorporate the relevant conditional conformances into the inputs to that conformance function. Today, in a conformance like your example struct X<T, U>: P, the only input to the conformance is the conforming type X<T, U>, which by itself carries no conformance information about T or U, so in the most general case, there's too little information to see the conditional conformances without doing global lookup (and thereby introducing nondeterminism due to the shared mutable nature of the global conformance set). If we had a mechanism for making the relevant conditional conformances be direct inputs to the conformance, that could provide a way out of the problem. One way to do this might be to have a formal concept of optional generic constraints; these could work by telling the type system to grab a protocol conformance for the constraint if it has it, or pass null otherwise. That would let you declare your type as (stealing ?Protocol syntax from Rust as a strawman):

struct X<T: ?Equatable, U: ?CustomStringConvertible> { ... }

That would let us know that, any time we instantiate X, we capture the conditional conformances for the generic arguments when we have them. Instantiations would notionally lower like this:

let xis = X<Int, String>.self // swift_getGenericMetadata(X, Int, String, `Int: Equatable`, `String: CustomStringConvertible`)

struct Foo {}
struct Bar {}

let xfb = X<Foo, Bar>.self // swift_getGenericMetadata(X, Foo, Bar, nullptr, nullptr)

We would probably also want to raise errors or warnings for non-concrete generic arguments that don't forward the optional requirements, to ensure that the information gets plumbed through:

func lossyGeneric<A, B>() -> X<A, B> // error: instantiation of X<A, B> loses optional requirements on T = A and U = B
func losslessGeneric<T: ?Equatable, U: ?CustomStringConvertible>() -> X<T, U> // ok

With the optional requirements captured into the metadata, then checks whether T conforms to Equatable, or U conforms to CustomStringConvertible, can be answered using local data, and unlike as? Protocol checks today, these local state checks can be made to behave deterministically, and reliably specialized away when we monomorphize. That would also enable your example case of choosing a P.foo witness based on the conformances of T and U to be done deterministically.

OTOH, if we treat optional requirements the way we do requirements today, that would mean new optional requirements can't be added retroactively to types, and couldn't even be added by the API author without breaking ABI, which wouldn't be very expressive. I can however see us having more flexibility with optional constraints in protocols. A protocol could use optional constraints to capture conditional conformance information into its conforming types, which would be appropriate for capability towers like *Collection, where it is common to want to deterministically query the higher capabilities of a collection. If the protocol were declared:

protocol Collection: ?BidirectionalCollection, ?RandomAccessCollection /*etc.*/ { ... }

that would direct the compiler to capture the BidirectionalCollection and RandomAccessCollection conformances for a type when available, and make them available for deterministic capability checking on any type that conforms to Collection. The situation for extension, both proactively and retroactively, is a bit more promising too. Protocols can already add new requirements resiliently, so if the standard library expands the Collection hierarchy, it can also extend Collection with optional constraints to capture the extended hierarchy. The story for retroactive expansion is a bit sadder within the confines of the language today, but if we had the ability to extend protocols with new dispatched requirements, that could also conceivably be used to introduce new optional requirements, and give a third party library the ability to expand the Collection hierarchy as well.

8 Likes

Yep.

If we want to be able to make these witness choice decisions deterministically, then we need to somehow incorporate the relevant conditional conformances into the inputs to that conformance function.

If you said, “if we want to make the witness choices based on conditional conformances of X…” I'd agree. I think determinism is totally desirable, but also orthogonal. Am I missing something?

Today, in a conformance like your example struct X<T, U>: P , the only input to the conformance is the conforming type X<T, U> , which by itself carries no conformance information about T or U, so in the most general case, there's too little information to see the conditional conformances

Agreed so far.

without doing global lookup

When you say “without doing global lookup” I think I know what you mean: that lookup can't proceed from any data structure that is currently passed as a parameter into the context where the decision must be made at runtime. Is that right?

One of the questions I keep asking in this thread is whether there is any way of expanding the information passed into these contexts, or whether we have in fact frozen that limitation into the ABI. It seems to me that, because conformances can already differ across module contexts, the witness table for T: P (for any type T and protocol P) can't be assumed to be unique across the whole program, and, so long as there is any constraint at all on the generic, witness tables themselves could serve as such a vehicle. Why couldn't that work?

(and thereby introducing nondeterminism due to the shared mutable nature of the global conformance set).

This part seems a little too significant to pass off in a parenthesized aside. How do you imagine this becomes nondeterministic? Are you thinking of conformances coming in from dynamically loaded shared libraries?

I've got a few of problems with this approach. To begin with, I find the notion of an “optional constraint” as absurd and meaningless as that of an “optional requirement,” which you'll remember we had to cope with for interoperability reasons, but relegated to Objective-C protocols to keep them from weakening the language. These things don't appear to constrain anything. You could say, “OK, we'll pick a better name,” but I think the poor name comes from the fact that the meaning of the feature is hard to describe and understand.

Next, the approach seems like it's entirely directed at mechanics of the language implementation that are—and should remain—below the level of the programming model. To understand what this does, and why it might be needed, one has to think about conditional conformances of generic types, how witness tables are generated, etc.

Most importantly, it seems to make the programming model much worse. The situation today is that simple, valid code appears to have a straightforward meaning but doesn't. Adding the ability to complicate code with these ?-“constraints” doesn't fix that: the same simple code would have the same surprising and hard-to-describe meaning. Your proposal adds another wrinkle to all the things the authors and consumers of these generics need to consider.

The feature doesn't lead me to any obvious understanding of how to use the language to express the classic ideas of generic programming. I would certainly find ways to get the system to do what I wanted, and would probably even be able to identify some idioms and programming techniques, but I can almost guarantee that you'd loathe the results even more than you abhor the hackery of C++ type-based metaprogramming :wink:.

Lastly, as I've remarked in another thread that I can't find at the moment (but where IIRC you didn't challenge my assertion), I don't think advance declaration of which conformances may be relevant to witness selection should be necessary, because the potential relevance of a conformance can be known from declarations that are visible in the same way that overload sets are resolved based on which declarations are visible.

The problem with having to do this where Collection is declared is that one doesn't always know the shape of these “capability towers” at the point where their roots are discovered. It's very similar to the reason people want to be able to retroactively add requirements to a protocol: the set of interesting customizable operations is not known at the point where the protocol is declared.

2 Likes

I think we can semantically separate a function availability into two posets of scopes and constraints. Conformances and functions are associated with a scope and a constraint. And the scope-constraint pair of a function call determines which the implementation to use.


Let's use 'scope to denote the scope. The scopes of protocols, conformances, and functions are tied to where they are declared. Say, we have

// Module Base
public protocol Foo {
  func bar()
}

extension Int: Foo { // Int:Foo'Base
  func bar() { ... } // Int.bar'Base
}

/// Module A
import Base // 'Base < 'A

In this example, Foo conformance of Int, and Int.bar all have the scope set to 'Base. The set of all scopes then admits a partial ordering. I'm not defining the ordering here, but import relation is a good candidate. In this example, 'Base < 'A.

We could separate 'A into 'internalA and 'publicA. For the sake of simplicity, I'll omit that for now.


Let's use '(constraint) to denote a constraint. This easily forms a poset using a more specific relation. For example:

           '(T == Int)
              ^    ^
             /      \
'(T: Comparable)   '(T: Hashable)
            ^        ^
             \      /
         '(T: Equatable)

So '(T: Equatable) < '(T: Comparable), etc.


Now, let's call a pair of scope and conformance a visibility. I'll use ''visibility1 to denote the visibility. We also define a partial order over visibility using the product order on Scope x Constraints. That is, ''v1 < ''v2 iff:

  • The scope of ''v1 < the scope of ''v2, and
  • The constraint of ''v1 < the constraint of ''v2.

Now that we defined visibility, every function call is associated with visibility:

A.foo() // A.foo''caller()

Then, we check all foo''candidate implementations where ''candidate < ''caller and choose the maximal one according to the partial ordering of the visibility.

To demonstrate, consider:

// Base
protocol Foo {
  func foo()
}
extension Int: Foo {
  // foo'Base'(Self == Int) or foo''Base
  func foo() { ... }
}

// Module A
import Base

func test() {
  // foo'A'(Self == Int) or foo''caller
  Int().foo()
}

In this case, assuming ''Base < ''caller, then foo''Base is a candidate for the function, if there are another function with visibility ''another which ''Base < ''another < ''caller, we will use that function instead.


The important part is that we orthogonalize the visibility of a function into scope and constraint, which can be dealt with separately. There are still a few gaps in the model:

  • I haven't specified the partial ordering of the scopes. I believe that, currently, we could say that each file has three scopes:

    • 'file: scopes for fileprivate declarations,
    • 'internalModule: scopes for internal declarations, and
    • 'publicModule: scopes for public declarations, including protocol conformances

    with the import rule saying that:

    'publicImportee < 'publicImporter
    

    If we're to have scoped conformance, we can put protocol conformances in 'internalModule, or even 'file instead of 'publicModule.

  • I haven't said how the visibility of function calls are constructed. This is where we fill in the information from this discussion, for example, with as? operator, we could say that it queries a runtime, application-wide lookup:

    a as? Protocol
    // Succeed if 'runtime'(Self: Protocol) < 'runtime(Self == concreteA), break ties arbitrarily
    

    or that it queries the scope where a is created, which we'd also need to attach scopes to each type/generic parameter:

    func foo<A'generic>(a: A'generic) {
      ...
      a as? FooProtocol
      // Succeed if `'generic'(Self: FooProtocol) < 'generic'(Self == concreteA)`, break ties arbitrarily.
    

I think the model is flexible enough, given the gap we can fill, to fit essentially any conformance model that's realistically implementable. It should also be easy to explain as (Swift) programmers should already be familiar with the conformance and scope partial ordering given it is relatively common to break ties between functions with different constraints.

If anything, I think attaching a visibility name to the function function''v1 and having partial ordering over visibility ''v1 < ''v2 would make the discussion go smoother, even if visibility is not a cartesian product of scope and constraint.

3 Likes

Bump @Joe_Groff. I asked a lot of questions in that post and would be grateful if you could address them!

Thanks