[swift-evolution] [Proposal draft] Conditional conformances

[Alexis]

Below I’ve provided a more fleshed out version of what Dave is suggesting, for anyone who had trouble parsing the very hypothetical example. It reflects the kind of implementation specialization I would expect to see in the standard library. In fact we have exactly this concern baked into value witness tables today by differentiating the various *Buffer methods so that they can be no-ops or memcpys for trivial values (rather than requiring code to loop over all the elements and call potentially-no-op methods on each element).

But the value witness table’s approach to this problem suggests some healthier solutions to the problem (for Swift’s particular set of constraints):

1) Add default-implemented fullAlgorithm() methods to the protocol. Anyone who can beat the default algorithm provides their own implementation. Consumers of the protocol then dispatch to fullAlgorithm(), rather than the lower-level primitives.

2) Add “let hasInterestingProperty: bool” flags to the protocol. Consumers of the protocol can then branch on these flags to choose a “slow generic” or “fast specific” implementation. (this is, after all, exactly what we’re asking the runtime to do for us!)

Of course, (1) and (2) aren’t always applicable solutions. Both only really apply if you’re the original creator of the protocol; otherwise no one will know about fullAlgorithm or hasInterestingProperty and be able to modify the default. It can also be really tedious to provide your own implementation of fullAlgorithm(), especially if everyone overloads it in the same way. These are, however, perfectly reasonable approaches if you’re just trying to specialize for a small, closed, set of types. Something like:

genericImpl()
stringImpl()
intImpl()

You can handle that pretty easily with extensions or super-protocols, I think.

I’m cautiously optimistic we can get pretty far before we really feel the need to introduce specialization like this. Although I’m used to handling this issue in a world of monomorphic generics; so I’m not sure if the performance characteristics of polymorphic generics will shift the balance to making specialization more urgent. Or perhaps the opposite — the runtime impact of specialization could be too high!


// Some kind of "super copy" operation
public protocol Clone {
  func clone() -> Self
}

// Can just memcpy instead of calling Clone
public protocol TrivialClone: Clone { }

// A terrible data structure
public struct FakeArray<T> { let vals: (T, T, T) }



// --------------------------------------------------
// A dirty hack to get overlapping impls (specifically specialization)
// through overlapping extensions.

internal protocol CloneImpl {
  associatedtype TT: Clone
}

extension CloneImpl {
  static func clone(input: FakeArray<TT>) -> FakeArray<TT> {
    // Have to manually invoke generic `clone` on each element
    FakeArray(vals: (input.vals.0.clone(),
                     input.vals.1.clone(),
                     input.vals.2.clone()))
  }
}

extension CloneImpl where TT: TrivialClone {
  static func clone(input: FakeArray<TT>) -> FakeArray<TT> {
    // Can just copy the whole buffer at once (ideally a memcpy)
    FakeArray(vals: input.vals)
  }
}


// Inject our specialized Clone impl
// (doesn't compile today because this is a conditional conformance)
extension FakeArray: Clone where T: Clone {
  // A dummy to get our overlapping extensions
  // (doesn't compile today because we can't nest types in a generic type)
  struct CloneImplProvider : CloneImpl {
    typealias TT = T
  }
  
  func clone() -> FakeArray {
    CloneImplProvider.clone(input: self)
  }
}

// -------------------------------------------------
// Using Clone and the specialization

// Some plain-old-data
struct POD : TrivialClone {
  func clone() -> POD { return self }
}

// Works with any Clone type
func generic<T: Clone>(_ value: T) -> T {
  return value.clone()
}

// Pass in a FakeArray that should use the fast specialization for Clone
generic(FakeArray(vals: (POD(), POD(), POD())))




> On Sep 30, 2016, at 11:18 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> on Fri Sep 30 2016, Matthew Johnson <swift-evolution at swift.org> wrote:
> 
>>> It’s a valid concern, and I’m sure it does come up in practice. Let’s create a small, self-contained example:
>>> 
>>> protocol P {
>>>  func f()
>>> }
>>> 
>>> protocol Q: P { }
>>> 
>>> struct X<T> { let t: T}
>>> 
>>> extension X: P where T: P {
>>>  func f() {
>>>    /* general but slow */
>>>  }
>>> }
>>> 
>>> extension X where T: Q {
>>>  func f() {
>>>    /* fast because it takes advantage of T: Q */
>>>  }
>>> }
>>> 
>>> struct IsQ : Q { }
>>> 
>>> func generic<U: P>(_ value: u) {
>>>  value.f()
>>> }
>>> 
>>> generic(X<IsQ>())
>>> 
>>> We’d like for the call to “value.f()” to get the fast version of f()
>>> from the second extension, but the proposal doesn’t do that: the
>>> conformance to P is “locked in” to the first extension.
> 
> I suppose that's true even if the second extension introduces X : Q?
> 
>>> If we assume that we can see all of the potential implementations of
>>> “f” to which we might want to dispatch, we could implement some
>>> dynamic scheme that tries to pick the most specialized one. Of
>>> course, as with overlapping conformances in general, this selection
>>> process could result in ambiguities.
>> 
>> This is what I suspected.  I’ll defer to Dave A on how big a concern
>> this is, but it seems to me like a bit of a slippery slope towards
>> sub-optimal performance.
> 
> Well, it's unfortunate.  We have a similar problem today due to the lack
> of conditional conformance, and we deal with it by injecting an
> underscored requirement where it doesn't belong, then dispatch through
> that.  I wonder if the workaround for this limitation is like that, or
> something completely different.
> 
> Does this work?  If not, why not?  If so, what makes it fundamentally
> different, since it is trying to express the same thing through
> different means?
> 
> -----
> 
> public protocol P {
>  func f()
> }
> 
> public protocol Q: P { }
> 
> public struct X<T> { let t: T}
> 
> internal protocol XFImpl {
>  associatedtype TT: P
>  static func f(X<T>)
> }
> 
> extension XFImpl {
> static func f(X<TT>) { /* general but slow */ }
> }
> 
> extension XFImpl where TT: Q {
>  static func f(X<TT>) { /* fast because it takes advantage of T: Q */ }
> }
> 
> extension X: P where T: P {
>  struct FImpl : XFImpl {
>    typealias TT = T
>  }
> 
>  func f() {
>    FImpl.f(self)
>  }
> }
> 
> struct IsQ : Q { }
> 
> func generic<U: P>(_ value: u) {
>  value.f()
> }
> 
> generic(X<IsQ>())
> 
> -- 
> -Dave
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161003/980414db/attachment.html>