[Pitch] Remove type inference for associated types


(Austin Zheng) #1

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin


Some generics type inference questions
(Dmitri Gribenko) #2

Hi Austin,

Thank you for starting this discussion! There's one other alternative
that I mentioned in one of the previous threads on this subject. The
idea is to limit the inference so that the sizes and the complexity of
the problems that the type checker has to solve become tractable with
a simple algorithm, not a full constrain solver.

Currently, as far as I understand, the type checker solves for all
associated types for a protocol conformance in a single giant step,
during which every decision can affect every other decision. My
suggestion is that we keep associated type inference for the simple
cases where it is obvious what the user meant. The author of the
protocol would be able to identify these simple cases and define how
exactly the inference should happen. For example:

protocol Collection {
  associatedtype Index

  @infers(Index)
  var startIndex: Index

  // Does not affect associated type inference, types have to match
with decisions made by other declarations.
  var endIndex: Index

  // Does not affect associated type inference.
  subscript(i: Index) -> Iterator.Element

  associatedtype Iterator

  @infers(Iterator)
  func iterator() -> Iterator
}

Under the current system, every declaration in a conforming type that
matches a requirement that mentions 'Index' can affect the inference.
That is, 'Index' is inferred from all declarations in the conforming
type. But there is no reason to make it that general -- the protocol
author knows that 'var startIndex' in the conforming type has be of
the right type, and there is no reason for other declaration to affect
the decision about what 'Index' is resolved to. Under the proposed
rule, there is at most one declaration that the protocol author is
allowed to designate with @infers, that is allowed to affect the
inference. If there is no @infers for a certain associated type, then
it is never inferred and should always be specified explicitly.

This is the basic idea, I'm sure there are corner cases I haven't
thought about (e.g., how does this interact with constrained
extension, can we still solve everything with a simple algorithm?)
But the reason why I'm suggesting this alternative is that I'm
concerned that in simple cases like inferring the 'Index' and
'Iterator' typealiases having to specify them manually is just
boilerplate, that does not add to clarity, and, I believe, can be
inferred by the type checker without involving a heavy constrain
solver.

Dmitri

···

On Fri, Jun 24, 2016 at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics
(http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put
together a proposal for removing type inference for associated types.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Matthew Johnson) #3

Hi Austin,

I’m sorry to say, but this proposal makes me really sad. I consider associated type inference one of the more elegant aspects of Swift. It would be very unfortunate to lose it.

I am really pleased to see that Dmitri has offered an alternative that looks very reasonable. I’m hoping the Doug or Chris (or someone else from the core team) can chime in on the feasibility of this alternative. If it is considered viable and Dmitri isn’t able to write the proposal I would be happy to do so.

If the alternative isn’t viable and we must proceed with a proposal to remove inference I think there is one crucial thing to consider that isn’t discussed in this proposal: retroactive modeling. As far as I can tell, this proposal will *prohibit* some types from conforming to some protocols. Specifically, if a type defines a typealias with a name that matches the name of an associatedtype in a protocol it would not be possible to retroactively model that protocol. Because of the name conflict an associatedtype declaration would not be allowed and the existing typealias would not meet the requirement. Consider this example:

// Module A
public struct S {
    public typealias Foo = Int
}

// Module B
public protocol P {
    associatedtype Foo
}

// Module C
import A
import B

// compiler error: `S` does not meet the `Foo` associatedtype requirement
extension S : P {
    // compiler error: cannot define associatedtype `Foo` for `S` which already declares typealias `Foo`
    associatedtype Foo = String
}

I cannot support any proposal that breaks retroactive modeling in this way.

Another item that is not mentioned in this proposal is that typealias is not the only way to meet an associatedtype requirement in the language today. For example, this code is legal:

protocol Foo {
    associatedtype Bar
}
struct S : Foo {
    struct Bar {}
}

If we *must* drop inference I prefer the alternative of just doing that: dropping inference, but otherwise leaving things alone. All associated type requirements would need to be explicitly satisfied using one of the mechanisms that is currently valid for satisfying a non-inferred associated type requirement. The ability to satisfy these requirements in a variety of ways is a *benefit* that provides valuable flexibility.

I agree that something should look for a good solution to the subclass typealias issue, but I don’t think this is it. Ideally we would find a solution that works well in the presence of retroactive modeling making code such as the following valid:

// module A
protocol P1 {
    associatedtype Foo

   @infers(Foo)
    var foo: Foo { get }
}
// module B
protocol P2 {
    associatedtype Foo

    @infers(Foo)
    func bar() -> Foo
}

// module C
class Base {
    let foo: String = "foo"
}
class Derived : Base {
    func bar() -> Int { return 42 }
}

// module D
import A
import B
import C
import D
extension Base : P1 {}
extension Derived : P2 {}

We don’t always control the protocol or type definitions we want to make work together. The ability to make code that “should work together” actually do so with minimal fuss is one of the great things about Swift. Any time we interfere with retroactive modeling we increase the need for boilerplate adapter types, etc.

One detail appears to be implied by the proposal but isn’t explicitly stated. Specifically, it looks like the intent is that other than only being valid when used to meet a protocol requirement, associatedtype otherwise works like a typealias. It would be good to have this behavior clarified if the proposal moves forward.

-Matthew

···

On Jun 25, 2016, at 12:50 AM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Austin Zheng) #4

Hi all,

Thank you for all your comments and feedback! I've rewritten and expanded the proposal to address as many peoples' concerns as possible.

Best,
Austin

···

On Jun 24, 2016, at 10:50 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin


(Pyry Jahkola) #5

Hi Austin,

I also think it's better to make associated types explicit in protocol conformance. But I'm not sure the requirement to use the `associatedtype` keyword on the conformance site is the right way to do so, especially since you haven't addressed how nested types could fulfill associated type requirements in the new design:

    extension Foo : P {
        struct A { ... }
    }

— Pyry

···

Austin Zheng wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin


(Douglas Gregor) #6

Thanks for working on this. I have a couple of comments.

I don’t think we should be adding the ability to write ‘associatedtype’ declarations in classes/structs/enums. We already have the ability to explicitly state the associated type witness by declaring a typealias, struct, enum, or class with the appropriate name. Indeed, I feel like a lot of complexity of the proposal is linked to adding ‘associatedtype’ declarations into the language, and I’d rather this proposal stay narrow.

I think it’s important for this proposal to show the other ways in which one can get associated type witnesses without writing them explicitly in the conforming type, even once inference goes away. For example, we have associated type defaults, e.g.,

  protocol P {
    associatedtype Associated = Int
  }

  struct X : P {
    // Associated becomes Int if not otherwise specified
  }

and with typealiases in protocol extensions becoming real and useful, one could also use protocol extensions:

  protocol P2 {
    associatedtype Index
  }

  extension P2 {
    typealias Index = Int
  }

which, of course, implies that one can use various tricks with constrained protocol extensions and such. There isn’t any proposed change here, but it illustrates that Swift programmers aren’t without recourse if type inference for associated types go away.

One concern with applying the above tricks is that existing code can change meaning when inference goes away. For example, let’s think about the “Iterator” type of a Sequence. It already uses default associated type witnesses (not associated type witness inference!) to give a default of IndexingIterator<Self>, e.g.,

  protocol Sequence {
    associatedtype Iterator: IteratorType
    func makeIterator() -> Iterator
  }

  protocol Collection : Sequence {
    associatedtype Iterator = IndexingIterator<Self>
    func makeIterator() -> Iterator // redeclaration helps inference
  }

When a type that conforms to Collection doesn’t provide makeIterator, it gets a default one via:

  extension Collection where Iterator == IndexingIterator<Self> {
    public func makeIterator() -> IndexingIterator<Self> { … }
  }

That will still work (yay). However, simply removing associated type inference means that a collection type that *does* provide makeIterator()—but not, directly, Iterator—would change behavior:

  struct IntCollection : Collection {
    typealias Element = Int
    func makeIterator() -> IntCollectionIterator { … }
  }

With associated type inference, we infer Iterator = IntCollectionIterator and select IntCollection.makeIterator() to satisfy the makeIterator() requirement.

Without associated type inference, we use the default Iterator = IndexingIterator<Self> and select the makeIterator() from the protocol extension (because IntCollection.makeIterator() now returns the wrong type), which turns an error of omission into an unpleasant surprise. We might need something like near-miss checking for defaulted protocol requirements (which we discussed in the thread at http://thread.gmane.org/gmane.comp.lang.swift.devel/1799) to help find those surprises. They already exist today, of course, but removing associated type inference would make them worse.

Finally, one of the chief concerns is that we won’t be able to provide a nice experience when conforming to the standard library’s collection protocols. I would *love* to see some more thought to into how we can use the above tools to handle it, although I suspect the only way to do that is to implement some part of this proposal experimentally and see what it takes to get the standard library and it’s tests working again. How far can the tools above go toward reducing the need to specify various associated type witnesses in conforming types? What are the surprises?

  - Doug

···

On Jun 24, 2016, at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.


(Austin Zheng) #7

Hi Dmitri,

Thanks for bringing this up. I surmise this option involves a user optionally marking a specific requirement in a protocol as being "chosen" to bind one or more associated types, with other requirements being forced to defer to that @infers-marked requirement.

I don't think there should be any problematic corner cases - either way, the set of associated types belonging to a type need to be solved in a consistent way, and the main difference would be the type of error emitted if the associated types could not be determined (e.g. "Associated type 'C' is inferred to be 'Int' by the declaration of 'foo(a:)' at line 1234, but was redefined as 'String' at line 1239").

I will add it to the alternatives section. The core team seems to be quite good about picking and choosing whatever they feel are the best parts of whatever alternatives are listed, so I think they will consider it very carefully.

Best,
Austin

···

On Jun 25, 2016, at 12:51 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Fri, Jun 24, 2016 at 10:50 PM, Austin Zheng via swift-evolution > <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics
(http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put
together a proposal for removing type inference for associated types.

Hi Austin,

Thank you for starting this discussion! There's one other alternative
that I mentioned in one of the previous threads on this subject. The
idea is to limit the inference so that the sizes and the complexity of
the problems that the type checker has to solve become tractable with
a simple algorithm, not a full constrain solver.

Currently, as far as I understand, the type checker solves for all
associated types for a protocol conformance in a single giant step,
during which every decision can affect every other decision. My
suggestion is that we keep associated type inference for the simple
cases where it is obvious what the user meant. The author of the
protocol would be able to identify these simple cases and define how
exactly the inference should happen. For example:

protocol Collection {
associatedtype Index

@infers(Index)
var startIndex: Index

// Does not affect associated type inference, types have to match
with decisions made by other declarations.
var endIndex: Index

// Does not affect associated type inference.
subscript(i: Index) -> Iterator.Element

associatedtype Iterator

@infers(Iterator)
func iterator() -> Iterator
}

Under the current system, every declaration in a conforming type that
matches a requirement that mentions 'Index' can affect the inference.
That is, 'Index' is inferred from all declarations in the conforming
type. But there is no reason to make it that general -- the protocol
author knows that 'var startIndex' in the conforming type has be of
the right type, and there is no reason for other declaration to affect
the decision about what 'Index' is resolved to. Under the proposed
rule, there is at most one declaration that the protocol author is
allowed to designate with @infers, that is allowed to affect the
inference. If there is no @infers for a certain associated type, then
it is never inferred and should always be specified explicitly.

This is the basic idea, I'm sure there are corner cases I haven't
thought about (e.g., how does this interact with constrained
extension, can we still solve everything with a simple algorithm?)
But the reason why I'm suggesting this alternative is that I'm
concerned that in simple cases like inferring the 'Index' and
'Iterator' typealiases having to specify them manually is just
boilerplate, that does not add to clarity, and, I believe, can be
inferred by the type checker without involving a heavy constrain
solver.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Austin Zheng) #8

Hi Austin,

I’m sorry to say, but this proposal makes me really sad. I consider associated type inference one of the more elegant aspects of Swift. It would be very unfortunate to lose it.

There are lots of "elegant" things that Swift could do, but has chosen not to do for pragmatic reasons (e.g. generalized implicit conversions, type inference that crosses statement boundaries). Given how terrible the development experience can be right now in the worst case, I would happily trade off some measure of convenience for better tooling.

I am really pleased to see that Dmitri has offered an alternative that looks very reasonable. I’m hoping the Doug or Chris (or someone else from the core team) can chime in on the feasibility of this alternative. If it is considered viable and Dmitri isn’t able to write the proposal I would be happy to do so.

If the alternative isn’t viable and we must proceed with a proposal to remove inference I think there is one crucial thing to consider that isn’t discussed in this proposal: retroactive modeling. As far as I can tell, this proposal will *prohibit* some types from conforming to some protocols. Specifically, if a type defines a typealias with a name that matches the name of an associatedtype in a protocol it would not be possible to retroactively model that protocol. Because of the name conflict an associatedtype declaration would not be allowed and the existing typealias would not meet the requirement. Consider this example:

I actually think that the delineation between `associatedtype` and `typealias` should make this legal, and will change the proposal as such. It should be legal to bind an associated type to a type alias, and it should be possible to define a type alias that shadows (but does not conflict with) an associated type definition. This would fix the issue with retroactive modeling.

// Module A
public struct S {
    public typealias Foo = Int
}

// Module B
public protocol P {
    associatedtype Foo
}

// Module C
import A
import B

// compiler error: `S` does not meet the `Foo` associatedtype requirement
extension S : P {
    // compiler error: cannot define associatedtype `Foo` for `S` which already declares typealias `Foo`
    associatedtype Foo = String
}

I cannot support any proposal that breaks retroactive modeling in this way.

Addendum aside, retroactive modeling is already suboptimal or broken in multiple ways today - try conforming a protocol with associated type 'Element' to a different protocol whose 'Element' means something completely different.

Another item that is not mentioned in this proposal is that typealias is not the only way to meet an associatedtype requirement in the language today. For example, this code is legal:

protocol Foo {
    associatedtype Bar
}
struct S : Foo {
    struct Bar {}
}

I don't see how this is relevant.

struct S : Foo {
  associatedtype S = Bar
  struct Bar { }
}

If we *must* drop inference I prefer the alternative of just doing that: dropping inference, but otherwise leaving things alone. All associated type requirements would need to be explicitly satisfied using one of the mechanisms that is currently valid for satisfying a non-inferred associated type requirement. The ability to satisfy these requirements in a variety of ways is a *benefit* that provides valuable flexibility.

I disagree that it's a benefit. It certainly saves a couple of keystrokes, but you gain or lose no expressive power from this proposal, addendum included. I'm happy to expand the alternatives section to discuss the other ways to satisfy associated type requirements, though.

···

On Jun 25, 2016, at 6:23 AM, Matthew Johnson <matthew@anandabits.com> wrote:

I agree that something should look for a good solution to the subclass typealias issue, but I don’t think this is it. Ideally we would find a solution that works well in the presence of retroactive modeling making code such as the following valid:

// module A
protocol P1 {
    associatedtype Foo

   @infers(Foo)
    var foo: Foo { get }
}
// module B
protocol P2 {
    associatedtype Foo

    @infers(Foo)
    func bar() -> Foo
}

// module C
class Base {
    let foo: String = "foo"
}
class Derived : Base {
    func bar() -> Int { return 42 }
}

// module D
import A
import B
import C
import D
extension Base : P1 {}
extension Derived : P2 {}

We don’t always control the protocol or type definitions we want to make work together. The ability to make code that “should work together” actually do so with minimal fuss is one of the great things about Swift. Any time we interfere with retroactive modeling we increase the need for boilerplate adapter types, etc.

One detail appears to be implied by the proposal but isn’t explicitly stated. Specifically, it looks like the intent is that other than only being valid when used to meet a protocol requirement, associatedtype otherwise works like a typealias. It would be good to have this behavior clarified if the proposal moves forward.

-Matthew

On Jun 25, 2016, at 12:50 AM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(L Mihalkovic) #9

Sometimes I get the sense that the pleasure of discussing takes precedence over the goal it serves, namely to create a language that will be the most attractive it can be within a given complexity budget (meaning a balance between the immediate reward of shiny new things and the long term evolvability of the compiler). I seem to recall this item coming directly from chris as a compiler cleanup task.

···

On Jun 25, 2016, at 3:23 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

Hi Austin,

I’m sorry to say, but this proposal makes me really sad. I consider associated type inference one of the more elegant aspects of Swift. It would be very unfortunate to lose it.

I am really pleased to see that Dmitri has offered an alternative that looks very reasonable. I’m hoping the Doug or Chris (or someone else from the core team) can chime in on the feasibility of this alternative. If it is considered viable and Dmitri isn’t able to write the proposal I would be happy to do so.

If the alternative isn’t viable and we must proceed with a proposal to remove inference I think there is one crucial thing to consider that isn’t discussed in this proposal: retroactive modeling. As far as I can tell, this proposal will *prohibit* some types from conforming to some protocols. Specifically, if a type defines a typealias with a name that matches the name of an associatedtype in a protocol it would not be possible to retroactively model that protocol. Because of the name conflict an associatedtype declaration would not be allowed and the existing typealias would not meet the requirement. Consider this example:

// Module A
public struct S {
    public typealias Foo = Int
}

// Module B
public protocol P {
    associatedtype Foo
}

// Module C
import A
import B

// compiler error: `S` does not meet the `Foo` associatedtype requirement
extension S : P {
    // compiler error: cannot define associatedtype `Foo` for `S` which already declares typealias `Foo`
    associatedtype Foo = String
}

I cannot support any proposal that breaks retroactive modeling in this way.

Another item that is not mentioned in this proposal is that typealias is not the only way to meet an associatedtype requirement in the language today. For example, this code is legal:

protocol Foo {
    associatedtype Bar
}
struct S : Foo {
    struct Bar {}
}

If we *must* drop inference I prefer the alternative of just doing that: dropping inference, but otherwise leaving things alone. All associated type requirements would need to be explicitly satisfied using one of the mechanisms that is currently valid for satisfying a non-inferred associated type requirement. The ability to satisfy these requirements in a variety of ways is a *benefit* that provides valuable flexibility.

I agree that something should look for a good solution to the subclass typealias issue, but I don’t think this is it. Ideally we would find a solution that works well in the presence of retroactive modeling making code such as the following valid:

// module A
protocol P1 {
    associatedtype Foo

   @infers(Foo)
    var foo: Foo { get }
}
// module B
protocol P2 {
    associatedtype Foo

    @infers(Foo)
    func bar() -> Foo
}

// module C
class Base {
    let foo: String = "foo"
}
class Derived : Base {
    func bar() -> Int { return 42 }
}

// module D
import A
import B
import C
import D
extension Base : P1 {}
extension Derived : P2 {}

We don’t always control the protocol or type definitions we want to make work together. The ability to make code that “should work together” actually do so with minimal fuss is one of the great things about Swift. Any time we interfere with retroactive modeling we increase the need for boilerplate adapter types, etc.

One detail appears to be implied by the proposal but isn’t explicitly stated. Specifically, it looks like the intent is that other than only being valid when used to meet a protocol requirement, associatedtype otherwise works like a typealias. It would be good to have this behavior clarified if the proposal moves forward.

-Matthew

On Jun 25, 2016, at 12:50 AM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(David Hart) #10

Hi Matthew,

I really like this proposal (even outside of its goal to simplify the type inference engine). The two other motivations in the proposal make very good points which can not be easily dismissed (especially to me as it took me a while to understand associated types):
It improves the type system's function as a form of code documentation by making it very clear to readers of a type declaration how the type's associated types are defined.

It makes it significantly easier for those learning the language to understand how associated types work.

I added some more comments inline your email:

Hi Austin,

I’m sorry to say, but this proposal makes me really sad. I consider associated type inference one of the more elegant aspects of Swift. It would be very unfortunate to lose it.

I am really pleased to see that Dmitri has offered an alternative that looks very reasonable. I’m hoping the Doug or Chris (or someone else from the core team) can chime in on the feasibility of this alternative. If it is considered viable and Dmitri isn’t able to write the proposal I would be happy to do so.

For me, this solution is worse than the current status quo. A feature (inference) which works only in certain cases but not all can be very confusing.

If the alternative isn’t viable and we must proceed with a proposal to remove inference I think there is one crucial thing to consider that isn’t discussed in this proposal: retroactive modeling. As far as I can tell, this proposal will *prohibit* some types from conforming to some protocols. Specifically, if a type defines a typealias with a name that matches the name of an associatedtype in a protocol it would not be possible to retroactively model that protocol. Because of the name conflict an associatedtype declaration would not be allowed and the existing typealias would not meet the requirement. Consider this example:

// Module A
public struct S {
    public typealias Foo = Int
}

// Module B
public protocol P {
    associatedtype Foo
}

// Module C
import A
import B

// compiler error: `S` does not meet the `Foo` associatedtype requirement
extension S : P {
    // compiler error: cannot define associatedtype `Foo` for `S` which already declares typealias `Foo`
    associatedtype Foo = String
}

I cannot support any proposal that breaks retroactive modeling in this way.

This is noteworthy, but solutions can be found. And we already have the problem today:

protocol Foo {
    associatedtype Baz : Integer
}

struct Bar {
    struct Baz { }
}

There’s no way to make Bar conform to Foo (that I know of).

Another item that is not mentioned in this proposal is that typealias is not the only way to meet an associatedtype requirement in the language today. For example, this code is legal:

protocol Foo {
    associatedtype Bar
}
struct S : Foo {
    struct Bar {}
}

If we *must* drop inference I prefer the alternative of just doing that: dropping inference, but otherwise leaving things alone. All associated type requirements would need to be explicitly satisfied using one of the mechanisms that is currently valid for satisfying a non-inferred associated type requirement. The ability to satisfy these requirements in a variety of ways is a *benefit* that provides valuable flexibility.

I agree that something should look for a good solution to the subclass typealias issue, but I don’t think this is it. Ideally we would find a solution that works well in the presence of retroactive modeling making code such as the following valid:

// module A
protocol P1 {
    associatedtype Foo

   @infers(Foo)
    var foo: Foo { get }
}
// module B
protocol P2 {
    associatedtype Foo

    @infers(Foo)
    func bar() -> Foo
}

// module C
class Base {
    let foo: String = "foo"
}
class Derived : Base {
    func bar() -> Int { return 42 }
}

// module D
import A
import B
import C
import D
extension Base : P1 {}
extension Derived : P2 {}

We don’t always control the protocol or type definitions we want to make work together. The ability to make code that “should work together” actually do so with minimal fuss is one of the great things about Swift. Any time we interfere with retroactive modeling we increase the need for boilerplate adapter types, etc.

One detail appears to be implied by the proposal but isn’t explicitly stated. Specifically, it looks like the intent is that other than only being valid when used to meet a protocol requirement, associatedtype otherwise works like a typealias. It would be good to have this behavior clarified if the proposal moves forward.

It looks like it, but it makes it clear that its there to satisfy an associated type. Its documentation.

···

On 25 Jun 2016, at 15:23, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

-Matthew

On Jun 25, 2016, at 12:50 AM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Charlie Monroe) #11

I'm not quite what would be the behavior of this in the proposal:

extension IntBag : StringBag {
    associatedtype Element = Element
}

since both IntBag and StringBag are classes - would IntBag use StringBag's code, but replace String with Int? Or would it just contain both

func object(at index: Int) -> Int?

and

func object(at index: Int) -> String?

if that is the case, what if the protocol contains a non-generic function like

func countElements() -> Int

?

···

On Jun 25, 2016, at 8:35 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

Thank you for all your comments and feedback! I've rewritten and expanded the proposal to address as many peoples' concerns as possible.

Best,
Austin

On Jun 24, 2016, at 10:50 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Douglas Gregor) #12

Hello all,

Per Chris Lattner's list of open Swift 3 design topics
(http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put
together a proposal for removing type inference for associated types.

Hi Austin,

Thank you for starting this discussion! There's one other alternative
that I mentioned in one of the previous threads on this subject. The
idea is to limit the inference so that the sizes and the complexity of
the problems that the type checker has to solve become tractable with
a simple algorithm, not a full constrain solver.

Currently, as far as I understand, the type checker solves for all
associated types for a protocol conformance in a single giant step,
during which every decision can affect every other decision.

That’s correct. It’s limiting that inference to a single conformance, but solving for all of the associated type witnesses simultaneously, using educated guesses as to which value witnesses will eventually be used (this is unchecked and seriously buggy). The fact that it’s only solving for a single conformance—e.g., “X : Collection” helps restrict the inference, but it’s also somewhat incorrect: why shouldn’t implementing a requirement from MutableCollection allow one to infer some associated type witness—say, the Index type—for a Collection? IIRC, we have some requirements duplicated in the standard library’s protocols simply to push the associated type inference into handling these cases.

My
suggestion is that we keep associated type inference for the simple
cases where it is obvious what the user meant. The author of the
protocol would be able to identify these simple cases and define how
exactly the inference should happen. For example:

protocol Collection {
associatedtype Index

@infers(Index)
var startIndex: Index

// Does not affect associated type inference, types have to match
with decisions made by other declarations.
var endIndex: Index

// Does not affect associated type inference.
subscript(i: Index) -> Iterator.Element

associatedtype Iterator

@infers(Iterator)
func iterator() -> Iterator
}

Under the current system, every declaration in a conforming type that
matches a requirement that mentions 'Index' can affect the inference.
That is, 'Index' is inferred from all declarations in the conforming
type. But there is no reason to make it that general -- the protocol
author knows that 'var startIndex' in the conforming type has be of
the right type, and there is no reason for other declaration to affect
the decision about what 'Index' is resolved to. Under the proposed
rule, there is at most one declaration that the protocol author is
allowed to designate with @infers, that is allowed to affect the
inference. If there is no @infers for a certain associated type, then
it is never inferred and should always be specified explicitly.

Pragmatically, this approach can reduce associated type inference and its associated problems. It might even provide a way for us to stage in the removal of type inference for associated types from the language, by removing it from the “user-facing” language but leaving it enabled in key standard library protocols so we don’t regress too badly, giving us more time to sort out how defaulted associated types and type aliases in protocol extensions can fill the gap.

However, this doesn’t actually achieve the simplification in the type checker that is intended. We would still need to maintain the existing global inference algorithm, and while it would (overall) reduce the number of requirements we need to consider when inferring associated type witnesses, it’s still a global problem because you can still have several possible “startIndex” or “iterator()” potential witnesses to consider (e.g., in the type, protocol extensions, constrained protocol extensions, and so on; and it gets more interesting with conditional conformances). And as soon as you mark that subscript with @infers(Index), all of the complexity becomes apparent again.

That brings me to the other point about this: it’s changing the default, but nothing would prevent a user from simply marking every requirement with @infers(each-associated-type-listed), in which case we’ve not actually fixed the problem.

This is the basic idea, I'm sure there are corner cases I haven't
thought about (e.g., how does this interact with constrained
extension, can we still solve everything with a simple algorithm?)
But the reason why I'm suggesting this alternative is that I'm
concerned that in simple cases like inferring the 'Index' and
'Iterator' typealiases having to specify them manually is just
boilerplate, that does not add to clarity, and, I believe, can be
inferred by the type checker without involving a heavy constrain
solver.

The solver for associated type witnesses is not simple, despite my assertions in that amusing commit message. It’s just simpler than going through the (expression) constraint solver, which we had before. It has to track multiple solutions from different possible requirement/witness pairings, rank the results, etc. Nothing in this proposal simplifies any of that… it just tries to give that solver smaller problems to work with.

  - Doug

···

On Jun 25, 2016, at 12:51 AM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:
On Fri, Jun 24, 2016 at 10:50 PM, Austin Zheng via swift-evolution > <swift-evolution@swift.org> wrote:


(Austin Zheng) #13

Thank you for your detailed feedback. Would it be helpful if I prepared a PR?

Austin

···

On Jun 28, 2016, at 10:33 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 24, 2016, at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Thanks for working on this. I have a couple of comments.

I don’t think we should be adding the ability to write ‘associatedtype’ declarations in classes/structs/enums. We already have the ability to explicitly state the associated type witness by declaring a typealias, struct, enum, or class with the appropriate name. Indeed, I feel like a lot of complexity of the proposal is linked to adding ‘associatedtype’ declarations into the language, and I’d rather this proposal stay narrow.

I think it’s important for this proposal to show the other ways in which one can get associated type witnesses without writing them explicitly in the conforming type, even once inference goes away. For example, we have associated type defaults, e.g.,

  protocol P {
    associatedtype Associated = Int
  }

  struct X : P {
    // Associated becomes Int if not otherwise specified
  }

and with typealiases in protocol extensions becoming real and useful, one could also use protocol extensions:

  protocol P2 {
    associatedtype Index
  }

  extension P2 {
    typealias Index = Int
  }

which, of course, implies that one can use various tricks with constrained protocol extensions and such. There isn’t any proposed change here, but it illustrates that Swift programmers aren’t without recourse if type inference for associated types go away.

One concern with applying the above tricks is that existing code can change meaning when inference goes away. For example, let’s think about the “Iterator” type of a Sequence. It already uses default associated type witnesses (not associated type witness inference!) to give a default of IndexingIterator<Self>, e.g.,

  protocol Sequence {
    associatedtype Iterator: IteratorType
    func makeIterator() -> Iterator
  }

  protocol Collection : Sequence {
    associatedtype Iterator = IndexingIterator<Self>
    func makeIterator() -> Iterator // redeclaration helps inference
  }

When a type that conforms to Collection doesn’t provide makeIterator, it gets a default one via:

  extension Collection where Iterator == IndexingIterator<Self> {
    public func makeIterator() -> IndexingIterator<Self> { … }
  }

That will still work (yay). However, simply removing associated type inference means that a collection type that *does* provide makeIterator()—but not, directly, Iterator—would change behavior:

  struct IntCollection : Collection {
    typealias Element = Int
    func makeIterator() -> IntCollectionIterator { … }
  }

With associated type inference, we infer Iterator = IntCollectionIterator and select IntCollection.makeIterator() to satisfy the makeIterator() requirement.

Without associated type inference, we use the default Iterator = IndexingIterator<Self> and select the makeIterator() from the protocol extension (because IntCollection.makeIterator() now returns the wrong type), which turns an error of omission into an unpleasant surprise. We might need something like near-miss checking for defaulted protocol requirements (which we discussed in the thread at http://thread.gmane.org/gmane.comp.lang.swift.devel/1799) to help find those surprises. They already exist today, of course, but removing associated type inference would make them worse.

Finally, one of the chief concerns is that we won’t be able to provide a nice experience when conforming to the standard library’s collection protocols. I would *love* to see some more thought to into how we can use the above tools to handle it, although I suspect the only way to do that is to implement some part of this proposal experimentally and see what it takes to get the standard library and it’s tests working again. How far can the tools above go toward reducing the need to specify various associated type witnesses in conforming types? What are the surprises?

  - Doug


(Brandon Knope) #14

What's the rationale for having associatedtype in protocols and typealias in the conforming types?

This has actually been a point of confusion for me as it seems inconsistent

Brandon

···

Sent from my iPad

On Jun 29, 2016, at 1:33 AM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

On Jun 24, 2016, at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Thanks for working on this. I have a couple of comments.

I don’t think we should be adding the ability to write ‘associatedtype’ declarations in classes/structs/enums. We already have the ability to explicitly state the associated type witness by declaring a typealias, struct, enum, or class with the appropriate name. Indeed, I feel like a lot of complexity of the proposal is linked to adding ‘associatedtype’ declarations into the language, and I’d rather this proposal stay narrow.

I think it’s important for this proposal to show the other ways in which one can get associated type witnesses without writing them explicitly in the conforming type, even once inference goes away. For example, we have associated type defaults, e.g.,

  protocol P {
    associatedtype Associated = Int
  }

  struct X : P {
    // Associated becomes Int if not otherwise specified
  }

and with typealiases in protocol extensions becoming real and useful, one could also use protocol extensions:

  protocol P2 {
    associatedtype Index
  }

  extension P2 {
    typealias Index = Int
  }

which, of course, implies that one can use various tricks with constrained protocol extensions and such. There isn’t any proposed change here, but it illustrates that Swift programmers aren’t without recourse if type inference for associated types go away.

One concern with applying the above tricks is that existing code can change meaning when inference goes away. For example, let’s think about the “Iterator” type of a Sequence. It already uses default associated type witnesses (not associated type witness inference!) to give a default of IndexingIterator<Self>, e.g.,

  protocol Sequence {
    associatedtype Iterator: IteratorType
    func makeIterator() -> Iterator
  }

  protocol Collection : Sequence {
    associatedtype Iterator = IndexingIterator<Self>
    func makeIterator() -> Iterator // redeclaration helps inference
  }

When a type that conforms to Collection doesn’t provide makeIterator, it gets a default one via:

  extension Collection where Iterator == IndexingIterator<Self> {
    public func makeIterator() -> IndexingIterator<Self> { … }
  }

That will still work (yay). However, simply removing associated type inference means that a collection type that *does* provide makeIterator()—but not, directly, Iterator—would change behavior:

  struct IntCollection : Collection {
    typealias Element = Int
    func makeIterator() -> IntCollectionIterator { … }
  }

With associated type inference, we infer Iterator = IntCollectionIterator and select IntCollection.makeIterator() to satisfy the makeIterator() requirement.

Without associated type inference, we use the default Iterator = IndexingIterator<Self> and select the makeIterator() from the protocol extension (because IntCollection.makeIterator() now returns the wrong type), which turns an error of omission into an unpleasant surprise. We might need something like near-miss checking for defaulted protocol requirements (which we discussed in the thread at http://thread.gmane.org/gmane.comp.lang.swift.devel/1799) to help find those surprises. They already exist today, of course, but removing associated type inference would make them worse.

Finally, one of the chief concerns is that we won’t be able to provide a nice experience when conforming to the standard library’s collection protocols. I would *love* to see some more thought to into how we can use the above tools to handle it, although I suspect the only way to do that is to implement some part of this proposal experimentally and see what it takes to get the standard library and it’s tests working again. How far can the tools above go toward reducing the need to specify various associated type witnesses in conforming types? What are the surprises?

  - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Austin Zheng) #15

Oops, that looks like a typo. All those types should be conforming to Sequence, not StringBag (or nothing at all). I'll fix it.

Best,
Austin

···

On Jun 26, 2016, at 9:39 PM, Charlie Monroe <charlie@charliemonroe.net> wrote:

I'm not quite what would be the behavior of this in the proposal:

extension IntBag : StringBag {
    associatedtype Element = Element
}

since both IntBag and StringBag are classes - would IntBag use StringBag's code, but replace String with Int? Or would it just contain both

func object(at index: Int) -> Int?

and

func object(at index: Int) -> String?

if that is the case, what if the protocol contains a non-generic function like

func countElements() -> Int

?

On Jun 25, 2016, at 8:35 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi all,

Thank you for all your comments and feedback! I've rewritten and expanded the proposal to address as many peoples' concerns as possible.

Best,
Austin

On Jun 24, 2016, at 10:50 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Matthew Johnson) #16

Hi Austin,

I’m sorry to say, but this proposal makes me really sad. I consider associated type inference one of the more elegant aspects of Swift. It would be very unfortunate to lose it.

There are lots of "elegant" things that Swift could do, but has chosen not to do for pragmatic reasons (e.g. generalized implicit conversions, type inference that crosses statement boundaries). Given how terrible the development experience can be right now in the worst case, I would happily trade off some measure of convenience for better tooling.

I understand the technical issues underlying the proposal. I wasn't sure how I would respond to this until Dmitri posted an alternative. IMO if we can solve the technical issues without giving up inference that is a huge win. It looks viable to me (as a non-expert - I hope a compiler engineer can confirm this).

If this is indeed a viable alternative then there is no tradeoff necessary and the discussion becomes one of style / preference. In that discussion I fall strongly on the side of protocol requirement guided inference.

I am really pleased to see that Dmitri has offered an alternative that looks very reasonable. I’m hoping the Doug or Chris (or someone else from the core team) can chime in on the feasibility of this alternative. If it is considered viable and Dmitri isn’t able to write the proposal I would be happy to do so.

If the alternative isn’t viable and we must proceed with a proposal to remove inference I think there is one crucial thing to consider that isn’t discussed in this proposal: retroactive modeling. As far as I can tell, this proposal will *prohibit* some types from conforming to some protocols. Specifically, if a type defines a typealias with a name that matches the name of an associatedtype in a protocol it would not be possible to retroactively model that protocol. Because of the name conflict an associatedtype declaration would not be allowed and the existing typealias would not meet the requirement. Consider this example:

I actually think that the delineation between `associatedtype` and `typealias` should make this legal, and will change the proposal as such. It should be legal to bind an associated type to a type alias, and it should be possible to define a type alias that shadows (but does not conflict with) an associated type definition. This would fix the issue with retroactive modeling.

IIUC you're saying a type is allowed to have an `associatedtype` and `typealias` (or nested type) both bound to the same name as long as they resolve to the same type. Is that correct? That would at least preserve current expressiveness.

// Module A
public struct S {
    public typealias Foo = Int
}

// Module B
public protocol P {
    associatedtype Foo
}

// Module C
import A
import B

// compiler error: `S` does not meet the `Foo` associatedtype requirement
extension S : P {
    // compiler error: cannot define associatedtype `Foo` for `S` which already declares typealias `Foo`
    associatedtype Foo = String
}

I cannot support any proposal that breaks retroactive modeling in this way.

Addendum aside, retroactive modeling is already suboptimal or broken in multiple ways today - try conforming a protocol with associated type 'Element' to a different protocol whose 'Element' means something completely different.

Did you mean conforming a type to two protocols with an 'Element' associatedtype?

I consider that issue to be in the realm of multiple conformances rather than retroactive modeling. I can still

Another item that is not mentioned in this proposal is that typealias is not the only way to meet an associatedtype requirement in the language today. For example, this code is legal:

protocol Foo {
    associatedtype Bar
}
struct S : Foo {
    struct Bar {}
}

I don't see how this is relevant.

struct S : Foo {
  associatedtype S = Bar
  struct Bar { }
}

Do you mean this?

struct S : Foo {
  associatedtype Bar = Bar
  struct Bar { }
}

That would preserve current expressiveness.

If we *must* drop inference I prefer the alternative of just doing that: dropping inference, but otherwise leaving things alone. All associated type requirements would need to be explicitly satisfied using one of the mechanisms that is currently valid for satisfying a non-inferred associated type requirement. The ability to satisfy these requirements in a variety of ways is a *benefit* that provides valuable flexibility.

I disagree that it's a benefit. It certainly saves a couple of keystrokes, but you gain or lose no expressive power from this proposal, addendum included. I'm happy to expand the alternatives section to discuss the other ways to satisfy associated type requirements, though.

Thank you for adding the clarifications. I feel a little better knowing we wouldn't lose expressive power, but still prefer the directed inference suggested by Dmitri.

···

Sent from my iPad

On Jun 25, 2016, at 12:41 PM, Austin Zheng <austinzheng@gmail.com> wrote:

On Jun 25, 2016, at 6:23 AM, Matthew Johnson <matthew@anandabits.com> wrote:

I agree that something should look for a good solution to the subclass typealias issue, but I don’t think this is it. Ideally we would find a solution that works well in the presence of retroactive modeling making code such as the following valid:

// module A
protocol P1 {
    associatedtype Foo

   @infers(Foo)
    var foo: Foo { get }
}
// module B
protocol P2 {
    associatedtype Foo

    @infers(Foo)
    func bar() -> Foo
}

// module C
class Base {
    let foo: String = "foo"
}
class Derived : Base {
    func bar() -> Int { return 42 }
}

// module D
import A
import B
import C
import D
extension Base : P1 {}
extension Derived : P2 {}

We don’t always control the protocol or type definitions we want to make work together. The ability to make code that “should work together” actually do so with minimal fuss is one of the great things about Swift. Any time we interfere with retroactive modeling we increase the need for boilerplate adapter types, etc.

One detail appears to be implied by the proposal but isn’t explicitly stated. Specifically, it looks like the intent is that other than only being valid when used to meet a protocol requirement, associatedtype otherwise works like a typealias. It would be good to have this behavior clarified if the proposal moves forward.

-Matthew

On Jun 25, 2016, at 12:50 AM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Best,
Austin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #17

Well, the type checker's inference engine has *always* been kinda
unreliable, and the experience is made much worse by the lack of
recursive protocol requirements and the inability to express other
constraints that would better guide inference, and by the “underscored
protocols” such as _Indexable that are required to work around those
limitations. IMO it's premature to remove this feature before the
inference engine is made sane, the generics features are added, and the
library is correspondingly cleaned up, because we don't really know what
the user experience would be.

Finally, I am very concerned that there are protocols such as Collection,
with many inferrable associated types, and that conforming to these
protocols could become *much* uglier.

···

on Sat Jun 25 2016, Austin Zheng <swift-evolution@swift.org> wrote:

On Jun 25, 2016, at 6:23 AM, Matthew Johnson <matthew@anandabits.com> wrote:

Hi Austin,

I’m sorry to say, but this proposal makes me really sad. I consider
associated type inference one of the more elegant aspects of Swift.
It would be very unfortunate to lose it.

There are lots of "elegant" things that Swift could do, but has chosen
not to do for pragmatic reasons (e.g. generalized implicit
conversions, type inference that crosses statement boundaries). Given
how terrible the development experience can be right now in the worst
case, I would happily trade off some measure of convenience for better
tooling.

--
Dave


(Douglas Gregor) #18

Thank you for your detailed feedback. Would it be helpful if I prepared a PR?

Yes, it would be very helpful.

  - Doug

···

Sent from my iPhone

On Jun 28, 2016, at 10:45 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Austin

On Jun 28, 2016, at 10:33 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 24, 2016, at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Thanks for working on this. I have a couple of comments.

I don’t think we should be adding the ability to write ‘associatedtype’ declarations in classes/structs/enums. We already have the ability to explicitly state the associated type witness by declaring a typealias, struct, enum, or class with the appropriate name. Indeed, I feel like a lot of complexity of the proposal is linked to adding ‘associatedtype’ declarations into the language, and I’d rather this proposal stay narrow.

I think it’s important for this proposal to show the other ways in which one can get associated type witnesses without writing them explicitly in the conforming type, even once inference goes away. For example, we have associated type defaults, e.g.,

  protocol P {
    associatedtype Associated = Int
  }

  struct X : P {
    // Associated becomes Int if not otherwise specified
  }

and with typealiases in protocol extensions becoming real and useful, one could also use protocol extensions:

  protocol P2 {
    associatedtype Index
  }

  extension P2 {
    typealias Index = Int
  }

which, of course, implies that one can use various tricks with constrained protocol extensions and such. There isn’t any proposed change here, but it illustrates that Swift programmers aren’t without recourse if type inference for associated types go away.

One concern with applying the above tricks is that existing code can change meaning when inference goes away. For example, let’s think about the “Iterator” type of a Sequence. It already uses default associated type witnesses (not associated type witness inference!) to give a default of IndexingIterator<Self>, e.g.,

  protocol Sequence {
    associatedtype Iterator: IteratorType
    func makeIterator() -> Iterator
  }

  protocol Collection : Sequence {
    associatedtype Iterator = IndexingIterator<Self>
    func makeIterator() -> Iterator // redeclaration helps inference
  }

When a type that conforms to Collection doesn’t provide makeIterator, it gets a default one via:

  extension Collection where Iterator == IndexingIterator<Self> {
    public func makeIterator() -> IndexingIterator<Self> { … }
  }

That will still work (yay). However, simply removing associated type inference means that a collection type that *does* provide makeIterator()—but not, directly, Iterator—would change behavior:

  struct IntCollection : Collection {
    typealias Element = Int
    func makeIterator() -> IntCollectionIterator { … }
  }

With associated type inference, we infer Iterator = IntCollectionIterator and select IntCollection.makeIterator() to satisfy the makeIterator() requirement.

Without associated type inference, we use the default Iterator = IndexingIterator<Self> and select the makeIterator() from the protocol extension (because IntCollection.makeIterator() now returns the wrong type), which turns an error of omission into an unpleasant surprise. We might need something like near-miss checking for defaulted protocol requirements (which we discussed in the thread at http://thread.gmane.org/gmane.comp.lang.swift.devel/1799) to help find those surprises. They already exist today, of course, but removing associated type inference would make them worse.

Finally, one of the chief concerns is that we won’t be able to provide a nice experience when conforming to the standard library’s collection protocols. I would *love* to see some more thought to into how we can use the above tools to handle it, although I suspect the only way to do that is to implement some part of this proposal experimentally and see what it takes to get the standard library and it’s tests working again. How far can the tools above go toward reducing the need to specify various associated type witnesses in conforming types? What are the surprises?

  - Doug


(Sean Heber) #19

Another issue here (perhaps) is, what if you misspelled the associated type when you attempted to typealias it manually? Would it not just make a new typealias with your misspelled name and then, potentially, you’d get an error or would something end up working but in unexpected ways? Would the typo be easy to identify if you had a lot of typealiases or associatedtypes or typos?

  protocol P {
    associatedtype Index = Int
  }

  struct X : P {
    typealias index = String // whoops - no capital I - how long does this bug take to find? :stuck_out_tongue:
  }

There will always be bugs, of course. Maybe this isn’t a significant concern?

l8r
Sean

···

On Jun 29, 2016, at 8:55 AM, Brandon Knope via swift-evolution <swift-evolution@swift.org> wrote:

What's the rationale for having associatedtype in protocols and typealias in the conforming types?

This has actually been a point of confusion for me as it seems inconsistent

Brandon

Sent from my iPad

On Jun 29, 2016, at 1:33 AM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

On Jun 24, 2016, at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Thanks for working on this. I have a couple of comments.

I don’t think we should be adding the ability to write ‘associatedtype’ declarations in classes/structs/enums. We already have the ability to explicitly state the associated type witness by declaring a typealias, struct, enum, or class with the appropriate name. Indeed, I feel like a lot of complexity of the proposal is linked to adding ‘associatedtype’ declarations into the language, and I’d rather this proposal stay narrow.

I think it’s important for this proposal to show the other ways in which one can get associated type witnesses without writing them explicitly in the conforming type, even once inference goes away. For example, we have associated type defaults, e.g.,

  protocol P {
    associatedtype Associated = Int
  }

  struct X : P {
    // Associated becomes Int if not otherwise specified
  }

and with typealiases in protocol extensions becoming real and useful, one could also use protocol extensions:

  protocol P2 {
    associatedtype Index
  }

  extension P2 {
    typealias Index = Int
  }

which, of course, implies that one can use various tricks with constrained protocol extensions and such. There isn’t any proposed change here, but it illustrates that Swift programmers aren’t without recourse if type inference for associated types go away.

One concern with applying the above tricks is that existing code can change meaning when inference goes away. For example, let’s think about the “Iterator” type of a Sequence. It already uses default associated type witnesses (not associated type witness inference!) to give a default of IndexingIterator<Self>, e.g.,

  protocol Sequence {
    associatedtype Iterator: IteratorType
    func makeIterator() -> Iterator
  }

  protocol Collection : Sequence {
    associatedtype Iterator = IndexingIterator<Self>
    func makeIterator() -> Iterator // redeclaration helps inference
  }

When a type that conforms to Collection doesn’t provide makeIterator, it gets a default one via:

  extension Collection where Iterator == IndexingIterator<Self> {
    public func makeIterator() -> IndexingIterator<Self> { … }
  }

That will still work (yay). However, simply removing associated type inference means that a collection type that *does* provide makeIterator()—but not, directly, Iterator—would change behavior:

  struct IntCollection : Collection {
    typealias Element = Int
    func makeIterator() -> IntCollectionIterator { … }
  }

With associated type inference, we infer Iterator = IntCollectionIterator and select IntCollection.makeIterator() to satisfy the makeIterator() requirement.

Without associated type inference, we use the default Iterator = IndexingIterator<Self> and select the makeIterator() from the protocol extension (because IntCollection.makeIterator() now returns the wrong type), which turns an error of omission into an unpleasant surprise. We might need something like near-miss checking for defaulted protocol requirements (which we discussed in the thread at http://thread.gmane.org/gmane.comp.lang.swift.devel/1799) to help find those surprises. They already exist today, of course, but removing associated type inference would make them worse.

Finally, one of the chief concerns is that we won’t be able to provide a nice experience when conforming to the standard library’s collection protocols. I would *love* to see some more thought to into how we can use the above tools to handle it, although I suspect the only way to do that is to implement some part of this proposal experimentally and see what it takes to get the standard library and it’s tests working again. How far can the tools above go toward reducing the need to specify various associated type witnesses in conforming types? What are the surprises?

  - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Brandon Knope) #20

This is true! Swift is suppose to be a safe language that can prevent these kind of pitfalls.

But I feel there was a rationale for having the way it is...I just don't know it

Brandon

···

On Jun 29, 2016, at 10:21 AM, Sean Heber <sean@fifthace.com> wrote:

Another issue here (perhaps) is, what if you misspelled the associated type when you attempted to typealias it manually? Would it not just make a new typealias with your misspelled name and then, potentially, you’d get an error or would something end up working but in unexpected ways? Would the typo be easy to identify if you had a lot of typealiases or associatedtypes or typos?

   protocol P {
     associatedtype Index = Int
   }

   struct X : P {
     typealias index = String // whoops - no capital I - how long does this bug take to find? :stuck_out_tongue:
   }

There will always be bugs, of course. Maybe this isn’t a significant concern?

l8r
Sean

On Jun 29, 2016, at 8:55 AM, Brandon Knope via swift-evolution <swift-evolution@swift.org> wrote:

What's the rationale for having associatedtype in protocols and typealias in the conforming types?

This has actually been a point of confusion for me as it seems inconsistent

Brandon

Sent from my iPad

On Jun 29, 2016, at 1:33 AM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

On Jun 24, 2016, at 10:50 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello all,

Per Chris Lattner's list of open Swift 3 design topics (http://article.gmane.org/gmane.comp.lang.swift.evolution/21369), I've put together a proposal for removing type inference for associated types.

It can be found here: https://github.com/austinzheng/swift-evolution/blob/az-assoctypeinf/proposals/XXXX-remove-assoctype-inference.md

Thoughts, criticism, and feedback welcome. There are at least two slightly different designs in the proposal, and I'm sure people will have ideas for even more.

Thanks for working on this. I have a couple of comments.

I don’t think we should be adding the ability to write ‘associatedtype’ declarations in classes/structs/enums. We already have the ability to explicitly state the associated type witness by declaring a typealias, struct, enum, or class with the appropriate name. Indeed, I feel like a lot of complexity of the proposal is linked to adding ‘associatedtype’ declarations into the language, and I’d rather this proposal stay narrow.

I think it’s important for this proposal to show the other ways in which one can get associated type witnesses without writing them explicitly in the conforming type, even once inference goes away. For example, we have associated type defaults, e.g.,

   protocol P {
     associatedtype Associated = Int
   }

   struct X : P {
     // Associated becomes Int if not otherwise specified
   }

and with typealiases in protocol extensions becoming real and useful, one could also use protocol extensions:

   protocol P2 {
     associatedtype Index
   }

   extension P2 {
     typealias Index = Int
   }

which, of course, implies that one can use various tricks with constrained protocol extensions and such. There isn’t any proposed change here, but it illustrates that Swift programmers aren’t without recourse if type inference for associated types go away.

One concern with applying the above tricks is that existing code can change meaning when inference goes away. For example, let’s think about the “Iterator” type of a Sequence. It already uses default associated type witnesses (not associated type witness inference!) to give a default of IndexingIterator<Self>, e.g.,

   protocol Sequence {
     associatedtype Iterator: IteratorType
     func makeIterator() -> Iterator
   }

   protocol Collection : Sequence {
     associatedtype Iterator = IndexingIterator<Self>
     func makeIterator() -> Iterator // redeclaration helps inference
   }

When a type that conforms to Collection doesn’t provide makeIterator, it gets a default one via:

   extension Collection where Iterator == IndexingIterator<Self> {
     public func makeIterator() -> IndexingIterator<Self> { … }
   }

That will still work (yay). However, simply removing associated type inference means that a collection type that *does* provide makeIterator()—but not, directly, Iterator—would change behavior:

   struct IntCollection : Collection {
     typealias Element = Int
     func makeIterator() -> IntCollectionIterator { … }
   }

With associated type inference, we infer Iterator = IntCollectionIterator and select IntCollection.makeIterator() to satisfy the makeIterator() requirement.

Without associated type inference, we use the default Iterator = IndexingIterator<Self> and select the makeIterator() from the protocol extension (because IntCollection.makeIterator() now returns the wrong type), which turns an error of omission into an unpleasant surprise. We might need something like near-miss checking for defaulted protocol requirements (which we discussed in the thread at http://thread.gmane.org/gmane.comp.lang.swift.devel/1799) to help find those surprises. They already exist today, of course, but removing associated type inference would make them worse.

Finally, one of the chief concerns is that we won’t be able to provide a nice experience when conforming to the standard library’s collection protocols. I would *love* to see some more thought to into how we can use the above tools to handle it, although I suspect the only way to do that is to implement some part of this proposal experimentally and see what it takes to get the standard library and it’s tests working again. How far can the tools above go toward reducing the need to specify various associated type witnesses in conforming types? What are the surprises?

   - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution