An inheritance problem

Suppose you want to give some functionality to a type, not in terms of concreteness (ex extension String), but in terms of its conformance signature:

protocol Opaque {
    associatedtype T 
}
protocol Mixin {
    func fin () -> Int 
}
extension Opaque: Mixin {
    func fin () -> Int { return 42 }
}

This code seems fine to me: it is given default implementation for all members and as such should be sound to compile, but ...

error: extension of protocol 'Opaque' cannot have an inheritance clause

... this is what compiler gives me. I don't see any reason to prevent it to be extended, do you?

By the way, was this thing send into the abyss, aye?

The error is unrelated to default implementations. The following gives the same error:

protocol X {}
protocol Y {}

extension X: Y {}
1 Like

Are you trying to provide default Mixin implementation to types that also conforms to Opaque? In that case, you'd do:

extension Mixin where Self: Opaque {
  func fin() -> Int { 42 }
}

Ok, but why is it an error though? That seems to me like something that cant set the program on fire :thinking:

Protocols can refine other protocols, but they don't inherit from other protocols. The proper way to do what you want is something like this:

protocol X {
    associatedtype T

    func x()
}

protocol Y: X {}

extension Y {
    func x() { print("x") }
}

struct S: Y {
    typealias T = Int
}

S().x()
2 Likes

Hmm, that worked and ... that's weird :neutral_face: . My intuition about opaques told me to move in a different direction.
It is strange that the spelling is ...

extension Mixin where Self: Opaque { ... }

... rather than ...

extension Opaque: Mixin { ... }

The spelling is different because these two extensions mean different things:

extension Mixin where Self: Opaque { ... }

means "extend all Mixin types which are also already Opaque types with this implementation", but

extension Opaque: Mixin { ... }

means "extend all Opaque types to be Mixin types", which you cannot do retroactively (after the initial protocol declaration) because you could have Opaque types which don't/can't satisfy the requirements for Mixin. The limiting factor is that for protocols you don't own (e.g., Opaque), there could be conforming types in other modules which are internal/private/fileprivate which you cannot extend (and the compiler can't help you if you're linking against binary frameworks); for protocols which you do own, the existing refinement syntax is the way to express this relationship.

1 Like

Gosh :flushed:, just realized that problem remains. Let me give another example:

//lets suppose that you want a type 
//that provides a bunch of default functionality to its conformers
protocol LovelyPrinter {
    func printPrettyStuff ()
}
//to give it default implementation
//the following has to be done
extension LovelyPrinter {
    func printPrettyStuff () {
        print("<3")
    }
}

//now every conforming type receive the 
//printPrettyStuff() method
extension String: LovelyPrinter {}
"".printPrettyStuff () //ok

//unfortunately, this doesn't work
"!".split {_ in true}[0] .printPrettyStuff ()
//because this "!".split {_ in true}[0]
//returns Substring, not a String

//Well, how to make it such that it works with any kind of that stuff?
//"You should extend the existential type, instead of a concrete type" 
//- I thought

//BUT. This is not going to happen, because
extension StringProtocol: LovelyPrinter {}
//is not possible! You'll get an error!

So my question remains why existential types are not extendable by protocol with default implementation (aka mixins)?

@Lantua suggested that something like this might work,

extension LovelyPrinter where Self: StringProtocol

but this restricts to only a certain set of types, which means this is not possible

extension Int: LovelyPrinter {}
//BAM! Error.

How cant they, if they are given default implementation?
I understand that this would not work

protocol ML {}
protocol A {
	var a: Int { get }
}

extension ML: A {} //ruins everything

protocol AA {
	var a: Int { return 42 }
}

extension ML: AA {} //perfectly fine

Why not the latter?

There are indeed some constrained situations in which your protocol could be simple enough that extending in this way would be safe, but there are so many gotchas and restrictions to making this possible that it likely isn't worth the work to make it happen.

Keep in mind that the language doesn't just model protocol refinement as "add these methods/requirements to this protocol"; there's a lot more going on in the runtime metadata that makes this relationship "official" which can't easily be retrofitted. extension ML: AA {} doesn't just add an implementation of a to all ML's, it has to represent in the runtime metadata that all MLs are AAs so that you could write a method generic on AA and pass in an ML. Imagine ML coming from another module which doesn't know about AA at all and has implementations of ML-conforming types. Some of those objects themselves have an a variable with their own implementation; within that module, do you want the implementation of a to dispatch to your default implementation, or their own? What about in your own module, in the generic AA function? Is it okay to get different results at different callsites? (How does the other module know to query for runtime metadata to "see" the implementation of a unless you monkey-patch their types at load time?) Lots of questions without great answers.

To make this concrete with your own example: what if the stdlib had a private StringProtocol-conforming type that happened to itself have a printPrettyStuff method; if you write a method which accepts a LovelyPrinter and got one of these private StringProtocol instances, which method implementation would you expect to be called for prettyPrintStuff and why?

There's certainly an area in the Venn diagram between "write an extension on the protocol you care about directly [e.g. extension StringProtocol { ... }]" and "define a protocol and implement it on all the types you need to" that isn't serviced at the moment, but the constraints to making that possible are extremely narrow.

I remember that in earlier version of swift the problem of member name collision was unhandled, apparently it still is. The main objections I got are: method dispatch and name collision. The former is easy: concrete types always suppress the default implementation of the protocol and the most recent refinement of a protocol for which defimpl is given should suppress the older ones (I believe that it is the current behaviour), and the latter is unlikely to happen (well doesn't matter, because naming collision is still there and aint gonna go away until conformances become named).
Also there is orphanage problem that I got impression that you do care about, but I dont see how internals and family would ever manifest it, because if there is an internal conformance in one module, swift shouldnt be so dumb to not to be able to resolve the dispatch in different module.

The main problem here is that extensions are called using static dispatch but when you declare them it uses a form of dynamic dispatch. This is something that needs to be better explained in swift as it intuitive for me either. The error should have a better explanation. See: https://trinhngocthuyen.github.io/posts/tech/method-dispatch-in-swift/

Well, nice :neutral_face:. Any attempts to solve this, @core-team ?

There's a few things here that aren't quite right:

This isn't necessarily a problem, per se, just a place where Swift and Objective-C differ. Non-public methods in one module can never get invoked from another module or and are never chosen to satisfy requirements for a conformance in another module.

This is a difference between methods in a protocol declaration and methods in a protocol extension, but I don't think it's relevant here: in this case the Mixin protocol does declare fin() as a requirement and thus a dynamic dispatch entry point.

I guess both of these points would be relevant if Swift did use name-based dispatch (like Objective-C does), but it doesn't (when a method's not exposed to Objective-C) because of the problems that @itaiferber brought up. If we're all on the same page about that…


…let's back up. How does protocol inheritance work today? It's essentially a shorthand for an additional requirement on the conforming type. That is, these two are equivalent:

protocol Sub: Base {}
protocol Sub where Self: Base {}

struct Impl: Sub {}

In both cases, anything that's generic over Sub can make use of the value also being a Base, and so there must be a way to take a Sub-constrained value and use it as a Base-constrained value. The implementation of this is for the run-time representation of the Impl: Sub conformance to include a reference to the Impl: Base conformance.

Okay, so how would we extend this to "mixin conformances"? Well, it gets tricky. As you note, we could have a rule that whenever you have an Opaque conformance, you can use that to build a Mixin conformance using the default implementations provided. That's totally implementable! However, it gets weird in cases like this:

struct Concrete: Opaque, Mixin {
  typealias T = String
  func fin() -> Int { return 20 }
}

func useOpaque<T: Opaque>(_ value: T) {
  value.fin()
}
useOpaque(Concrete())

In a language like C++, we'd get a different version of useOpaque for each concrete type that gets used, but Swift doesn't work like that. All useOpaque knows is:

  • the run-time concrete type of T, which is Concrete
  • how that type conforms to Opaque

So if it uses the default implementation of Opaque: Mixin (where fin() returns 42), it'll have different behavior from Concrete: Mixin (where fin() returns 20). Hm. But useOpaque doesn't have access to Concrete: Mixin—at least, not without doing dynamic lookup. And dynamic lookup has its own problems (mostly the "what if two modules independently implement the same protocol" problem).

But let's say we go with dynamic lookup. That still doesn't solve all the problems: what happens in this case?

// Module Base
protocol A {}
protocol B {}

struct Concrete: A, B {}

// Module Mixin
extension A: Mixin {
  func fin() -> Int { return 1 }
}

extension B: Mixin {
  func fin() -> Int { return 2 }
}

Now we have the same problem: which implementation should we use when trying to form Concrete: Mixin? Neither one is obviously better than the other. (This is the same reason why you're not allowed to have a type conform to a protocol with two different sets of conditions—there may not be one that's better than the other.)


None of these problems are insurmountable in the abstract; it would be possible to define behavior in all these cases. But what would be hard is doing it in a way that doesn't compromise performance and doesn't make the language (too much) more complicated than it already is. So the recommended approach today is to build adapters instead:

struct OpaqueMixinAdapter<RawValue: Opaque>: Mixin {
  var rawValue: RawValue
  init(_ rawValue: RawValue) {
    self.rawValue = rawValue
  }

  func fin() -> Int { return 42 }
}

It does mean that anyone who wants to use an Opaque as a Mixin has to hop through your adapter type, but at least the behavior is very clear.

4 Likes

One more thing: this is absolutely a pain point, even within a single library. Splitting out AdditiveArithmetic from Numeric is something that couldn't be done today without breaking ABI compatibility because we don't have this mechanism or something like it. But it turns out to be really hard to design in practice due to other decisions that have been made about the language. (Not that I can point to one in particular that is "the problem".) Everything's a set of tradeoffs.

I think the problem could be tackled by making a compiler track cyclic dependencies and informing programmers and by allowing conformance to be invoking the desired methods by the full path.

extension A: Mixin {
  func fin() -> Int { return 1 }
}

extension B: Mixin {
  func fin() -> Int { return 2 }
}
struct Concrete: A, B {} //collision found. Resolve manually

struct Concrete: Mixin, A, B { func fin () -> Int { return Self.A.fin() } } //1
//now Concrete have implementation from A: Mixin

//or just redeclare it. Both impls from A: Mixin and B: Mixin would be
//suppressed
struct Concrete: Mixin, A, B { func fin () -> Int { 666 } } 
//ok, now implementation is in Concrete: Mixin


//module S
struct Concrete: Mixin {}
//module T
extension Concrete: Mixin { ... } //the most recent refinement
//a single redeclaration within one module should be ok

Is this not all to it? :thinking:

I would like to hear the reply from you to this first, but meanwhile, I object that the intention to make both simple and "system-level" language looks like a contradiction to me, given how dynamic the language already is, wittingly not improving woes that lay beneath the ground is not going to do any good to anyone (because among all, it restricts the expressivity). Solving this particular downfall - I believe - would not introduce any new complexity on the surface (syntax), and could probably remain hidden for some users.
Also to note: I spent some time browsing this topic and revealed a bunch of pain regarding the dispatch facility (this one makes my skin shiver :anguished:), which started me to consider not to come into swift. I hope that sentiment of unimprovement is not of the majority of the core team.

Speaking from experience, I'm in awe with the level of performance Swift can provide.

I was experimenting with Geometric Algebra a while ago. The details doesn't really matter, but there's this one add function which is highly generic and works on any class that conforms to Storage type. The add implementation uses Storage.scalar extensively. I've been juggling between generality and performance for the longest time, then I figured that I can inline Storage.scalar. The results is that I gained ~1000x performance, on par with me manually writing only necessary mutations by hand. What you suggest would most likely prevents that inlining since we need to read the whole program to know which implementation is being used for scalar. So it is making a code somewhere 1000x worse.

I won't say that we don't need dynamism at all, but being unnecessarily dynamic is probably not a good thing.

3 Likes

Ah, I cannot be so sure, because neither I see your code nor I can confidently state the exact behaviour if the correct dispatching would be implemented, because it is not rigorously defined yet. But despite that, I already don't see how this would incur performance degradation for static libs (which yours seems to be). Moreover, I think that in the examples I have shown the dynamic dispatch is unnecessary.
All I have talked about can be implemented completely in compile-time - compiler just has to resolve conformance graph and pick a single witness that is set in the current context (module) and then generate assembly - and nothing prevents it from inlining (as nothing prevents inlining of generic functions and methods now).
To demonstrate:

Prelude
extension A: Mixin {
  func fin() -> Int { return 1 }
}

extension B: Mixin {
  func fin() -> Int { return 2 }
}
struct Concrete: A, B {} //collision found. Resolve manually

struct Concrete: Mixin, A, B { func fin () -> Int { return Self.A.fin() } } //1
//now Concrete have implementation from A: Mixin

//or just redeclare it. Both impls from A: Mixin and B: Mixin would be
//suppressed
struct Concrete: Mixin, A, B { func fin () -> Int { 666 } } 
//ok, now implementation is in Concrete: Mixin
//module S
struct Concrete: Mixin {}
//module T
extension Concrete: Mixin { func fin () -> Int { return 99 } } 
//the most recent refinement
//a single redeclaration within one module should be ok

//at this point if you use module T 
//runtime shouldn't give a damn about all previous 
//refinements of Concrete, because in this module it is explicitly set 
//to be with exact implementation (return 99).
//it just has to construct a correct kind 
//(Archetype it is called?)

So I don't see how this would get it not better, but worse.

ps. I have some hypothesis about the way to nail it:
First, the runtime should be separated into two different domains: private domain for internal, private, fileprivate code etc), and public domain for public, open code. The witness picking should then have the following algorithm:

  1. Construct all the code that is internal for any external modules used
  2. Collect all most recent public declarations of witnesses in the current module
//module S
protocol A { func lp () }
struct Tau: A { func lp () {print("Tau from S")} }
//module R
import S
extension Tau: A { func lp () {print("Tau from R")} }
//this is the most recent declaration
//choose this witness and forget about S.Tau.lp()
  1. Descend the hierarchy of refinements and pick the most recent public witness from imported modules
//module S
protocol A { func lp (); func zx () }
extension A { func zx () {print("A from S")} }
struct Tau: A { func lp () {print("Tau from S")} }
Tau().lp() //"Tau from S"
Tau().zx() //"A from S"

//module R
import S
extension Tau: A { func lp () {print("Tau from R")} }
Tau().lp() //"Tau from R"
Tau().zx() //"A from S"
//this is the most recent declaration
//inherit zx() implementation
//choose new witness for lp() and forget about S.Tau.lp()
  1. If any collisions were found, throw an error and make the programmer to choose single witness manually
extension A: Mixin {
  func fin() -> Int { return 1 }
}

extension B: Mixin {
  func fin() -> Int { return 2 }
}
struct Concrete: A, B {} //Error, collision found. Resolve manually

struct Concrete: Mixin, A, B { func fin () -> Int { return Self.A.fin() } } //1
//now Concrete have implementation from A: Mixin
//Now compiler can eliminate unnecesary code for this particular type
//(Implementation from B: Mixin gets annihilated)

//or just redeclare it. Both impls from A: Mixin and B: Mixin would be
//suppressed and never get to assembly
struct Concrete: Mixin, A, B { func fin () -> Int { 666 } } 
//ok, now implementation is in Concrete: Mixin
//Destroy A: Mixin and B: Mixin impls

Regarding variable parameterization by existential, then I think the best way is to first:

  1. Track all assignments of all valid concrete types to it
  2. Construct a box with the biggest size that could be allocated on the stack (kind of how enums work) or put it on the heap
//module R
var u: A = Tau()
u.lp() //"Tau from R". Yes, the most recent is picked
u.zx() //"A from S"

To spill a bit about generic functions, behaviour that differs from this is basically inferiority of current implementation:

//module R
func useA<T: A>(_ value: T) {
  value.lp()
}
useA(Tau()) 
//if it prints "Tau from R" than we are golden
//otherwise it just a bold bug, because a witness is explicitly set to be 
{print("Tau from R")}

Let's jump back to Mixin example. How can I allow fin inlining. If I have this:

// Module A
import Mixin

protocol A: Mixin {...}
extension A { /* Implements Mixin */ }

func take(a: A) {...}
struct Concrete: A {...}

// Application
import A

protocol B: Mixin {...}
extension B { /* Implements Mixin */ }

We want to compile module A into a binary, and ship it to Application, which is doable. Now, what should happen if I do this in the Application module?

extension Concrete: B {...}

If it shouldn't be allow, I'm not sure of the utility of the manually resolution that we've been working hard for.

If it should be manually resolved, things will be getting interesting. What should happen if I call take(a: Concrete()) from Application? It'd surely use the resolved implementation. What if I call it from within A? It could

  • Uses the resolved implementation. This will surely prevent inlining when compile a binary for A since it can't ascertain the actual fin at that time.
  • Uses the A.mixin implementation. It's, well, is a little weird, but somewhat reasonable.

Either way, welcome to An Implementation Model for Rational Protocol Conformance Behavior

Terms of Service

Privacy Policy

Cookie Policy