[Pitch/plea] Recursive protocol constraints


(Douglas Gregor) #1

Recursive protocol constraints is one small-looking feature that could greatly improve the standard library. The generics manifesto describes it this way:

"Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence { associatedtype Iterator : IteratorProtocol ... associatedtype SubSequence : Sequence // currently ill-formed, but should be possible }
The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well."

It's actually slightly worse than the above implies: the standard library has a pile of underscore-prefixed protocols (e.g., _Sequence) specifically to dodge this restriction. They are ugly, and we want them to go away. Many of these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and basic semantics are pretty direct, but a proposal should also capture the expected effects on the standard library, particularly when combined with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

···

Sent from my iPhone


(Austin Zheng) #2

I'd be happy to put something together, unless someone else wants to take
it on.

Doug, I also owe you a PR adding a minor amendment to one of the accepted
proposals. I'll get to that this week.

Austin

···

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution < swift-evolution@swift.org> wrote:

Recursive protocol constraints is one small-looking feature that could
greatly improve the standard library. The generics manifesto describes it
this way:

"Currently, an associated type cannot be required to conform to its
enclosing protocol (or any protocol that inherits that protocol). For
example, in the standard library SubSequence type of a Sequence should
itself be a Sequence:

protocol Sequence {
  associatedtype Iterator : IteratorProtocol
  ...
  associatedtype SubSequence : Sequence // currently ill-formed, but should be possible}

The compiler currently rejects this protocol, which is unfortunate: it
effectively pushes the SubSequence-must-be-a-Sequence requirement into
every consumer of SubSequence, and does not communicate the intent of
this abstraction well."

<https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#nested-generics>It's
actually slightly worse than the above implies: the standard library has a
pile of underscore-prefixed protocols (e.g., _Sequence) specifically to
dodge this restriction. They are ugly, and we want them to go away. Many of
these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and
basic semantics are pretty direct, but a proposal should also capture the
expected effects on the standard library, particularly when combined with
where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions
on this feature for implementation reasons, e.g., because some recursive
constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some
information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

Sent from my iPhone

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


(David Sweeris) #3

I'm having a bit of trouble understanding what you mean by "unsolvable system". Do you happen to have a handy example?

- Dave Sweeris

···

On Nov 13, 2016, at 14:13, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.


(Douglas Gregor) #4

I'd be happy to put something together, unless someone else wants to take it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the accepted proposals. I'll get to that this week.

Sounds great.

  - Doug

···

Sent from my iPhone

On Nov 13, 2016, at 4:03 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:
Recursive protocol constraints is one small-looking feature that could greatly improve the standard library. The generics manifesto describes it this way:

"Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence { associatedtype Iterator : IteratorProtocol ... associatedtype SubSequence : Sequence // currently ill-formed, but should be possible }
The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well."

It's actually slightly worse than the above implies: the standard library has a pile of underscore-prefixed protocols (e.g., _Sequence) specifically to dodge this restriction. They are ugly, and we want them to go away. Many of these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and basic semantics are pretty direct, but a proposal should also capture the expected effects on the standard library, particularly when combined with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

Sent from my iPhone

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


(Austin Zheng) #5

I'm still working on this. When you mention where clauses on associated
types, how should I handle that in the context of the proposal?

* Consider where clauses part of the proposal (so that the proposal becomes
"recursive associated type constraints + where clauses on associated types")
* Assume that where clauses will definitely be accepted, and write the
stdlib changes assuming that
* Assume that where clauses might not be accepted, and write the stdlib
changes assuming that, but also have a section containing further stdlib
changes conditional on where clauses being accepted

Best,
Austin

···

On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor <dgregor@apple.com> wrote:

Sent from my iPhone

On Nov 13, 2016, at 4:03 PM, Austin Zheng <austinzheng@gmail.com> wrote:

I'd be happy to put something together, unless someone else wants to take
it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the accepted
proposals. I'll get to that this week.

Sounds great.

  - Doug

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution < > swift-evolution@swift.org> wrote:

Recursive protocol constraints is one small-looking feature that could
greatly improve the standard library. The generics manifesto describes it
this way:

"Currently, an associated type cannot be required to conform to its
enclosing protocol (or any protocol that inherits that protocol). For
example, in the standard library SubSequence type of a Sequence should
itself be a Sequence:

protocol Sequence {
  associatedtype Iterator : IteratorProtocol
  ...
  associatedtype SubSequence : Sequence // currently ill-formed, but should be possible}

The compiler currently rejects this protocol, which is unfortunate: it
effectively pushes the SubSequence-must-be-a-Sequence requirement into
every consumer of SubSequence, and does not communicate the intent of
this abstraction well."

<https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#nested-generics>It's
actually slightly worse than the above implies: the standard library has a
pile of underscore-prefixed protocols (e.g., _Sequence) specifically to
dodge this restriction. They are ugly, and we want them to go away. Many of
these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax
and basic semantics are pretty direct, but a proposal should also capture
the expected effects on the standard library, particularly when combined
with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions
on this feature for implementation reasons, e.g., because some recursive
constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some
information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

Sent from my iPhone

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


(Austin Zheng) #6

Never mind, I just saw SE-0142. I need to go back and read all the
proposals again!

···

On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng <austinzheng@gmail.com> wrote:

I'm still working on this. When you mention where clauses on associated
types, how should I handle that in the context of the proposal?

* Consider where clauses part of the proposal (so that the proposal
becomes "recursive associated type constraints + where clauses on
associated types")
* Assume that where clauses will definitely be accepted, and write the
stdlib changes assuming that
* Assume that where clauses might not be accepted, and write the stdlib
changes assuming that, but also have a section containing further stdlib
changes conditional on where clauses being accepted

Best,
Austin

On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor <dgregor@apple.com> wrote:

Sent from my iPhone

On Nov 13, 2016, at 4:03 PM, Austin Zheng <austinzheng@gmail.com> wrote:

I'd be happy to put something together, unless someone else wants to take
it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the accepted
proposals. I'll get to that this week.

Sounds great.

  - Doug

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution < >> swift-evolution@swift.org> wrote:

Recursive protocol constraints is one small-looking feature that could
greatly improve the standard library. The generics manifesto describes it
this way:

"Currently, an associated type cannot be required to conform to its
enclosing protocol (or any protocol that inherits that protocol). For
example, in the standard library SubSequence type of a Sequence should
itself be a Sequence:

protocol Sequence {
  associatedtype Iterator : IteratorProtocol
  ...
  associatedtype SubSequence : Sequence // currently ill-formed, but should be possible}

The compiler currently rejects this protocol, which is unfortunate: it
effectively pushes the SubSequence-must-be-a-Sequence requirement into
every consumer of SubSequence, and does not communicate the intent of
this abstraction well."

<https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#nested-generics>It's
actually slightly worse than the above implies: the standard library has a
pile of underscore-prefixed protocols (e.g., _Sequence) specifically to
dodge this restriction. They are ugly, and we want them to go away. Many of
these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax
and basic semantics are pretty direct, but a proposal should also capture
the expected effects on the standard library, particularly when combined
with where clauses on associated types.

I also have a nagging feeling that we will need some form of
restrictions on this feature for implementation reasons, e.g., because some
recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some
information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

Sent from my iPhone

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


(Austin Zheng) #7

After overpromising and underdelivering, I finally managed to sit down and draft a proposal. Sorry it took so long. You can find it here:

https://github.com/austinzheng/swift-evolution/blob/recursive-constraints/proposals/XXXX-recursive-protocol-constraints.md

It contains both a description of the change itself, as well as a list of stdlib changes that need to be made. I used the “FIXME(ABI)” comments in the codebase to compile that list of changes. I also went over parts of the stdlib myself to see if there was anything else I could find, but didn’t notice anything in particular. (I was hoping protocols like `_Integer` could go away, but I’m not sure the issue they’re working around is related to recursive constraints.)

One thing that needs to be done before this can enter formal review is thinking through cases where “valid” recursive constraints might break the compiler. Help on that (or any other feedback, really) would be greatly appreciated.

Best,
Austin

···

On Nov 21, 2016, at 6:42 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Never mind, I just saw SE-0142. I need to go back and read all the proposals again!

On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:
I'm still working on this. When you mention where clauses on associated types, how should I handle that in the context of the proposal?

* Consider where clauses part of the proposal (so that the proposal becomes "recursive associated type constraints + where clauses on associated types")
* Assume that where clauses will definitely be accepted, and write the stdlib changes assuming that
* Assume that where clauses might not be accepted, and write the stdlib changes assuming that, but also have a section containing further stdlib changes conditional on where clauses being accepted

Best,
Austin

On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

Sent from my iPhone

On Nov 13, 2016, at 4:03 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

I'd be happy to put something together, unless someone else wants to take it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the accepted proposals. I'll get to that this week.

Sounds great.

  - Doug

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Recursive protocol constraints is one small-looking feature that could greatly improve the standard library. The generics manifesto describes it this way:

"Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence { associatedtype Iterator : IteratorProtocol ... associatedtype SubSequence : Sequence // currently ill-formed, but should be possible }
The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well."

<https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#nested-generics>It's actually slightly worse than the above implies: the standard library has a pile of underscore-prefixed protocols (e.g., _Sequence) specifically to dodge this restriction. They are ugly, and we want them to go away. Many of these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and basic semantics are pretty direct, but a proposal should also capture the expected effects on the standard library, particularly when combined with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

Sent from my iPhone

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


(David Sweeris) #8

+1k.9

···

Sent from my iPhone

On Dec 30, 2016, at 18:44, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

After overpromising and underdelivering, I finally managed to sit down and draft a proposal. Sorry it took so long. You can find it here:

https://github.com/austinzheng/swift-evolution/blob/recursive-constraints/proposals/XXXX-recursive-protocol-constraints.md

It contains both a description of the change itself, as well as a list of stdlib changes that need to be made. I used the “FIXME(ABI)” comments in the codebase to compile that list of changes. I also went over parts of the stdlib myself to see if there was anything else I could find, but didn’t notice anything in particular. (I was hoping protocols like `_Integer` could go away, but I’m not sure the issue they’re working around is related to recursive constraints.)

One thing that needs to be done before this can enter formal review is thinking through cases where “valid” recursive constraints might break the compiler. Help on that (or any other feedback, really) would be greatly appreciated.

Best,
Austin

On Nov 21, 2016, at 6:42 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Never mind, I just saw SE-0142. I need to go back and read all the proposals again!

On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng <austinzheng@gmail.com> wrote:

I'm still working on this. When you mention where clauses on associated types, how should I handle that in the context of the proposal?

* Consider where clauses part of the proposal (so that the proposal becomes "recursive associated type constraints + where clauses on associated types")
* Assume that where clauses will definitely be accepted, and write the stdlib changes assuming that
* Assume that where clauses might not be accepted, and write the stdlib changes assuming that, but also have a section containing further stdlib changes conditional on where clauses being accepted

Best,
Austin

On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor <dgregor@apple.com> wrote:

Sent from my iPhone

On Nov 13, 2016, at 4:03 PM, Austin Zheng <austinzheng@gmail.com> wrote:

I'd be happy to put something together, unless someone else wants to take it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the accepted proposals. I'll get to that this week.

Sounds great.

  - Doug

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:
Recursive protocol constraints is one small-looking feature that could greatly improve the standard library. The generics manifesto describes it this way:

"Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence { associatedtype Iterator : IteratorProtocol ... associatedtype SubSequence : Sequence // currently ill-formed, but should be possible }
The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well."

It's actually slightly worse than the above implies: the standard library has a pile of underscore-prefixed protocols (e.g., _Sequence) specifically to dodge this restriction. They are ugly, and we want them to go away. Many of these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and basic semantics are pretty direct, but a proposal should also capture the expected effects on the standard library, particularly when combined with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

Sent from my iPhone

_______________________________________________
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


(Dave Abrahams) #9

After overpromising and underdelivering, I finally managed to sit down
and draft a proposal. Sorry it took so long.

All your help is deeply appreciated, Austin!

You can find it here:

https://github.com/austinzheng/swift-evolution/blob/recursive-constraints/proposals/XXXX-recursive-protocol-constraints.md
<https://github.com/austinzheng/swift-evolution/blob/recursive-constraints/proposals/XXXX-recursive-protocol-constraints.md>

It contains both a description of the change itself, as well as a list
of stdlib changes that need to be made. I used the “FIXME(ABI)”
comments in the codebase to compile that list of changes. I also went
over parts of the stdlib myself to see if there was anything else I
could find, but didn’t notice anything in particular. (I was hoping
protocols like `_Integer` could go away, but I’m not sure the issue
they’re working around is related to recursive constraints.)

It is.

One thing that needs to be done before this can enter formal review is
thinking through cases where “valid” recursive constraints might break
the compiler.

I haven't read it yet; does the document explain what you mean by that?
Because it's not obvious from this message

···

on Fri Dec 30 2016, Austin Zheng <swift-evolution@swift.org> wrote:

Help on that (or any other feedback, really) would be greatly
appreciated.

Best,
Austin

On Nov 21, 2016, at 6:42 PM, Austin Zheng <austinzheng@gmail.com> > wrote:

Never mind, I just saw SE-0142. I need to go back and read all the proposals again!

On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng >> <austinzheng@gmail.com >> <mailto:austinzheng@gmail.com>> wrote:
I'm still working on this. When you mention where clauses on
associated types, how should I handle that in the context of the
proposal?

* Consider where clauses part of the proposal (so that the proposal
becomes "recursive associated type constraints + where clauses on
associated types")
* Assume that where clauses will definitely be accepted, and write the stdlib changes assuming that
* Assume that where clauses might not be accepted, and write the
stdlib changes assuming that, but also have a section containing
further stdlib changes conditional on where clauses being accepted

Best,
Austin

On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor >> <dgregor@apple.com >> <mailto:dgregor@apple.com>> wrote:

On Nov 13, 2016, at 4:03 PM, Austin Zheng >> <austinzheng@gmail.com >> <mailto:austinzheng@gmail.com>> wrote:

I'd be happy to put something together, unless someone else wants to take it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the
accepted proposals. I'll get to that this week.

Sounds great.

  - Doug

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Recursive protocol constraints is one small-looking feature that could greatly improve the standard library. The generics manifesto describes it this way:

"Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence { associatedtype Iterator : IteratorProtocol ... associatedtype SubSequence : Sequence // currently ill-formed, but should be possible }
The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well."

<https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#nested-generics>It's actually slightly worse than the above implies: the standard library has a pile of underscore-prefixed protocols (e.g., _Sequence) specifically to dodge this restriction. They are ugly, and we want them to go away. Many of these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and basic semantics are pretty direct, but a proposal should also capture the expected effects on the standard library, particularly when combined with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org

<mailto:swift-evolution@swift.org>

https://lists.swift.org/mailman/listinfo/swift-evolution

<https://lists.swift.org/mailman/listinfo/swift-evolution>

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

--
-Dave


(Dave Abrahams) #10

After overpromising and underdelivering, I finally managed to sit down
and draft a proposal. Sorry it took so long.

All your help is deeply appreciated, Austin!

You can find it here:

https://github.com/austinzheng/swift-evolution/blob/recursive-constraints/proposals/XXXX-recursive-protocol-constraints.md

<https://github.com/austinzheng/swift-evolution/blob/recursive-constraints/proposals/XXXX-recursive-protocol-constraints.md>

It contains both a description of the change itself, as well as a list
of stdlib changes that need to be made. I used the “FIXME(ABI)”
comments in the codebase to compile that list of changes. I also went
over parts of the stdlib myself to see if there was anything else I
could find, but didn’t notice anything in particular. (I was hoping
protocols like `_Integer` could go away, but I’m not sure the issue
they’re working around is related to recursive constraints.)

It is.

One thing that needs to be done before this can enter formal review is
thinking through cases where “valid” recursive constraints might break
the compiler.

I haven't read it yet; does the document explain what you mean by that?
Because it's not obvious from this message

...or from the document.

I left some commentary in
https://github.com/austinzheng/swift-evolution/commit/ad1d28b3b74bb12cfd07c277322ea4eb2b78b8cd#diff-6b60459047bfe1c675c50d5ca66cfe91R57

in addition, I notice that many of the likely stdlib changes are
missing... but it may be more efficient for you to watch the branch
Doug's working on and see what changes are made there, and then propose
those, than to try to anticipate what will change.

···

on Sat Dec 31 2016, Dave Abrahams <swift-evolution@swift.org> wrote:

on Fri Dec 30 2016, Austin Zheng <swift-evolution@swift.org> wrote:

Help on that (or any other feedback, really) would be greatly
appreciated.

Best,
Austin

On Nov 21, 2016, at 6:42 PM, Austin Zheng <austinzheng@gmail.com> >> wrote:

Never mind, I just saw SE-0142. I need to go back and read all the proposals again!

On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng >>> <austinzheng@gmail.com >>> <mailto:austinzheng@gmail.com>> wrote:
I'm still working on this. When you mention where clauses on
associated types, how should I handle that in the context of the
proposal?

* Consider where clauses part of the proposal (so that the proposal
becomes "recursive associated type constraints + where clauses on
associated types")
* Assume that where clauses will definitely be accepted, and write the stdlib changes assuming that
* Assume that where clauses might not be accepted, and write the
stdlib changes assuming that, but also have a section containing
further stdlib changes conditional on where clauses being accepted

Best,
Austin

On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor >>> <dgregor@apple.com >>> <mailto:dgregor@apple.com>> wrote:

On Nov 13, 2016, at 4:03 PM, Austin Zheng >>> <austinzheng@gmail.com >>> <mailto:austinzheng@gmail.com>> wrote:

I'd be happy to put something together, unless someone else wants to take it on.

Great, thanks!

Doug, I also owe you a PR adding a minor amendment to one of the
accepted proposals. I'll get to that this week.

Sounds great.

  - Doug

Austin

On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Recursive protocol constraints is one small-looking feature that could greatly improve the standard library. The generics manifesto describes it this way:

"Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence { associatedtype Iterator : IteratorProtocol ... associatedtype SubSequence : Sequence // currently ill-formed, but should be possible }
The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well."

<https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#nested-generics>It's actually slightly worse than the above implies: the standard library has a pile of underscore-prefixed protocols (e.g., _Sequence) specifically to dodge this restriction. They are ugly, and we want them to go away. Many of these places are marked with an ABI FIXME in the standard library sources.

Would someone like to write up a proposal for this feature? The syntax and basic semantics are pretty direct, but a proposal should also capture the expected effects on the standard library, particularly when combined with where clauses on associated types.

I also have a nagging feeling that we will need some form of restrictions on this feature for implementation reasons, e.g., because some recursive constraints will form unsolvable systems.

For reference, we've already been implementing this feature. Some information about the compiler internal issues is captured at:

  https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6

  - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org

<mailto:swift-evolution@swift.org>

https://lists.swift.org/mailman/listinfo/swift-evolution

<https://lists.swift.org/mailman/listinfo/swift-evolution>

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

--
-Dave


(Austin Zheng) #11

Thank you for the kind comments and the review, Dave! I will be working to
address the points you brought up throughout the week. This will include
re-auditing the stdlib types based on both manual investigation and Doug's
branch.

Anyone who wants to help, by the way, is more than welcome to; I'm happy to
take PRs or just even a message describing what needs to change, and I'd of
course add you to the authors list...

Regarding "valid" recursive constraints breaking the compiler: it was a
reference to something Doug said in his original email:

I also have a nagging feeling that we will need some form of restrictions

on this feature for implementation reasons, e.g., because some recursive
constraints will form unsolvable systems.

Best,
Austin

···

On Sat, Dec 31, 2016 at 11:29 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Sat Dec 31 2016, Dave Abrahams <swift-evolution@swift.org> wrote:

> on Fri Dec 30 2016, Austin Zheng <swift-evolution@swift.org> wrote:
>
>> After overpromising and underdelivering, I finally managed to sit down
>> and draft a proposal. Sorry it took so long.
>
> All your help is deeply appreciated, Austin!
>
>> You can find it here:
>>
>>
> https://github.com/austinzheng/swift-evolution/
blob/recursive-constraints/proposals/XXXX-recursive-
protocol-constraints.md
>>
> <https://github.com/austinzheng/swift-evolution/
blob/recursive-constraints/proposals/XXXX-recursive-
protocol-constraints.md>
>>
>> It contains both a description of the change itself, as well as a list
>> of stdlib changes that need to be made. I used the “FIXME(ABI)”
>> comments in the codebase to compile that list of changes. I also went
>> over parts of the stdlib myself to see if there was anything else I
>> could find, but didn’t notice anything in particular. (I was hoping
>> protocols like `_Integer` could go away, but I’m not sure the issue
>> they’re working around is related to recursive constraints.)
>
> It is.
>
>> One thing that needs to be done before this can enter formal review is
>> thinking through cases where “valid” recursive constraints might break
>> the compiler.
>
> I haven't read it yet; does the document explain what you mean by that?
> Because it's not obvious from this message

...or from the document.

I left some commentary in
https://github.com/austinzheng/swift-evolution/commit/
ad1d28b3b74bb12cfd07c277322ea4eb2b78b8cd#diff-
6b60459047bfe1c675c50d5ca66cfe91R57

in addition, I notice that many of the likely stdlib changes are
missing... but it may be more efficient for you to watch the branch
Doug's working on and see what changes are made there, and then propose
those, than to try to anticipate what will change.

>> Help on that (or any other feedback, really) would be greatly
>> appreciated.
>>
>> Best,
>> Austin
>>
>>> On Nov 21, 2016, at 6:42 PM, Austin Zheng <austinzheng@gmail.com> > >> wrote:
>>>
>>> Never mind, I just saw SE-0142. I need to go back and read all the
proposals again!
>>>
>>> On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng > >>> <austinzheng@gmail.com > >>> <mailto:austinzheng@gmail.com>> wrote:
>>> I'm still working on this. When you mention where clauses on
>>> associated types, how should I handle that in the context of the
>>> proposal?
>>>
>>> * Consider where clauses part of the proposal (so that the proposal
>>> becomes "recursive associated type constraints + where clauses on
>>> associated types")
>>> * Assume that where clauses will definitely be accepted, and write the
stdlib changes assuming that
>>> * Assume that where clauses might not be accepted, and write the
>>> stdlib changes assuming that, but also have a section containing
>>> further stdlib changes conditional on where clauses being accepted
>>>
>>> Best,
>>> Austin
>>>
>>> On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor > >>> <dgregor@apple.com > >>> <mailto:dgregor@apple.com>> wrote:
>>>
>>>
>>>
>>>
>>> On Nov 13, 2016, at 4:03 PM, Austin Zheng > >>> <austinzheng@gmail.com > >>> <mailto:austinzheng@gmail.com>> wrote:
>>>
>>>> I'd be happy to put something together, unless someone else wants to
take it on.
>>>
>>> Great, thanks!
>>>
>>>>
>>>> Doug, I also owe you a PR adding a minor amendment to one of the
>>>> accepted proposals. I'll get to that this week.
>>>
>>> Sounds great.
>>>
>>> - Doug
>>>
>>>> Austin
>>>>
>>>> On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution < > swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>>>> Recursive protocol constraints is one small-looking feature that
could greatly improve the standard library. The generics manifesto
describes it this way:
>>>>
>>>> "Currently, an associated type cannot be required to conform to its
enclosing protocol (or any protocol that inherits that protocol). For
example, in the standard library SubSequence type of a Sequence should
itself be a Sequence:
>>>>
>>>> protocol Sequence { associatedtype Iterator : IteratorProtocol ...
associatedtype SubSequence : Sequence // currently ill-formed, but should
be possible }
>>>> The compiler currently rejects this protocol, which is unfortunate:
it effectively pushes the SubSequence-must-be-a-Sequence requirement into
every consumer of SubSequence, and does not communicate the intent of this
abstraction well."
>>>>
>>>> <https://github.com/apple/swift/blob/master/docs/
GenericsManifesto.md#nested-generics>It's actually slightly worse than
the above implies: the standard library has a pile of underscore-prefixed
protocols (e.g., _Sequence) specifically to dodge this restriction. They
are ugly, and we want them to go away. Many of these places are marked with
an ABI FIXME in the standard library sources.
>>>>
>>>> Would someone like to write up a proposal for this feature? The
syntax and basic semantics are pretty direct, but a proposal should also
capture the expected effects on the standard library, particularly when
combined with where clauses on associated types.
>>>>
>>>> I also have a nagging feeling that we will need some form of
restrictions on this feature for implementation reasons, e.g., because some
recursive constraints will form unsolvable systems.
>>>>
>>>> For reference, we've already been implementing this feature. Some
information about the compiler internal issues is captured at:
>>>>
>>>> https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6
<https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6>
>>>>
>>>> - Doug
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution@swift.org
>> <mailto:swift-evolution@swift.org>
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> <https://lists.swift.org/mailman/listinfo/swift-evolution>
>>>>
>>>>
>>>
>>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>

--
-Dave

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


(Dave Abrahams) #12

Thank you for the kind comments and the review, Dave! I will be working to
address the points you brought up throughout the week. This will include
re-auditing the stdlib types based on both manual investigation and Doug's
branch.

But Doug hasn't done most of the work on the stdlib that would progress
from having the feature. He doesn't have the feature implemented yet
after all. You won't get any information about what should change in
the stdlib by auditing his changes until he has done some of that.

Anyone who wants to help, by the way, is more than welcome to; I'm happy to
take PRs or just even a message describing what needs to change, and I'd of
course add you to the authors list...

Regarding "valid" recursive constraints breaking the compiler: it was a
reference to something Doug said in his original email:

I also have a nagging feeling that we will need some form of
restrictions on this feature for implementation reasons, e.g.,
because some recursive constraints will form unsolvable systems.

I wouldn't concern myself much with such vague fears-and-doubts if I
were you. Consider that unsolvable systems would be a *fundamental*
reason for needing restrictions, rather than an implementation reason.
If we discover such a scenario, we'll deal with it. My intuition is
that any such unsolvable systems will fall under the rubric of
ambiguities, so the restriction will be something like “don't make
something ambiguous.”

···

on Mon Jan 02 2017, Austin Zheng <austinzheng-AT-gmail.com> wrote:

Best,
Austin

On Sat, Dec 31, 2016 at 11:29 AM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sat Dec 31 2016, Dave Abrahams <swift-evolution@swift.org> wrote:

> on Fri Dec 30 2016, Austin Zheng <swift-evolution@swift.org> wrote:
>
>> After overpromising and underdelivering, I finally managed to sit down
>> and draft a proposal. Sorry it took so long.
>
> All your help is deeply appreciated, Austin!
>
>> You can find it here:
>>
>>
> https://github.com/austinzheng/swift-evolution/
blob/recursive-constraints/proposals/XXXX-recursive-
protocol-constraints.md
>>
> <https://github.com/austinzheng/swift-evolution/
blob/recursive-constraints/proposals/XXXX-recursive-
protocol-constraints.md>
>>
>> It contains both a description of the change itself, as well as a list
>> of stdlib changes that need to be made. I used the “FIXME(ABI)”
>> comments in the codebase to compile that list of changes. I also went
>> over parts of the stdlib myself to see if there was anything else I
>> could find, but didn’t notice anything in particular. (I was hoping
>> protocols like `_Integer` could go away, but I’m not sure the issue
>> they’re working around is related to recursive constraints.)
>
> It is.
>
>> One thing that needs to be done before this can enter formal review is
>> thinking through cases where “valid” recursive constraints might break
>> the compiler.
>
> I haven't read it yet; does the document explain what you mean by that?
> Because it's not obvious from this message

...or from the document.

I left some commentary in
https://github.com/austinzheng/swift-evolution/commit/
ad1d28b3b74bb12cfd07c277322ea4eb2b78b8cd#diff-
6b60459047bfe1c675c50d5ca66cfe91R57

in addition, I notice that many of the likely stdlib changes are
missing... but it may be more efficient for you to watch the branch
Doug's working on and see what changes are made there, and then propose
those, than to try to anticipate what will change.

>> Help on that (or any other feedback, really) would be greatly
>> appreciated.
>>
>> Best,
>> Austin
>>
>>> On Nov 21, 2016, at 6:42 PM, Austin Zheng <austinzheng@gmail.com> >> >> wrote:
>>>
>>> Never mind, I just saw SE-0142. I need to go back and read all the
proposals again!
>>>
>>> On Mon, Nov 21, 2016 at 6:32 PM, Austin Zheng >> >>> <austinzheng@gmail.com >> >>> <mailto:austinzheng@gmail.com>> wrote:
>>> I'm still working on this. When you mention where clauses on
>>> associated types, how should I handle that in the context of the
>>> proposal?
>>>
>>> * Consider where clauses part of the proposal (so that the proposal
>>> becomes "recursive associated type constraints + where clauses on
>>> associated types")
>>> * Assume that where clauses will definitely be accepted, and write the
stdlib changes assuming that
>>> * Assume that where clauses might not be accepted, and write the
>>> stdlib changes assuming that, but also have a section containing
>>> further stdlib changes conditional on where clauses being accepted
>>>
>>> Best,
>>> Austin
>>>
>>> On Sun, Nov 13, 2016 at 7:55 PM, Douglas Gregor >> >>> <dgregor@apple.com >> >>> <mailto:dgregor@apple.com>> wrote:
>>>
>>>
>>>
>>>
>>> On Nov 13, 2016, at 4:03 PM, Austin Zheng >> >>> <austinzheng@gmail.com >> >>> <mailto:austinzheng@gmail.com>> wrote:
>>>
>>>> I'd be happy to put something together, unless someone else wants to
take it on.
>>>
>>> Great, thanks!
>>>
>>>>
>>>> Doug, I also owe you a PR adding a minor amendment to one of the
>>>> accepted proposals. I'll get to that this week.
>>>
>>> Sounds great.
>>>
>>> - Doug
>>>
>>>> Austin
>>>>
>>>> On Sun, Nov 13, 2016 at 10:13 PM, Douglas Gregor via swift-evolution < >> swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>>>> Recursive protocol constraints is one small-looking feature that
could greatly improve the standard library. The generics manifesto
describes it this way:
>>>>
>>>> "Currently, an associated type cannot be required to conform to its
enclosing protocol (or any protocol that inherits that protocol). For
example, in the standard library SubSequence type of a Sequence should
itself be a Sequence:
>>>>
>>>> protocol Sequence { associatedtype Iterator : IteratorProtocol ...
associatedtype SubSequence : Sequence // currently ill-formed, but should
be possible }
>>>> The compiler currently rejects this protocol, which is unfortunate:
it effectively pushes the SubSequence-must-be-a-Sequence requirement into
every consumer of SubSequence, and does not communicate the intent of this
abstraction well."
>>>>
>>>> <https://github.com/apple/swift/blob/master/docs/
GenericsManifesto.md#nested-generics>It's actually slightly worse than
the above implies: the standard library has a pile of underscore-prefixed
protocols (e.g., _Sequence) specifically to dodge this restriction. They
are ugly, and we want them to go away. Many of these places are marked with
an ABI FIXME in the standard library sources.
>>>>
>>>> Would someone like to write up a proposal for this feature? The
syntax and basic semantics are pretty direct, but a proposal should also
capture the expected effects on the standard library, particularly when
combined with where clauses on associated types.
>>>>
>>>> I also have a nagging feeling that we will need some form of
restrictions on this feature for implementation reasons, e.g., because some
recursive constraints will form unsolvable systems.
>>>>
>>>> For reference, we've already been implementing this feature. Some
information about the compiler internal issues is captured at:
>>>>
>>>> https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6
<https://gist.github.com/DougGregor/e7c4e7bb4465d6f5fa2b59be72dbdba6>
>>>>
>>>> - Doug
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution@swift.org
>> <mailto:swift-evolution@swift.org>
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> <https://lists.swift.org/mailman/listinfo/swift-evolution>
>>>>
>>>>
>>>
>>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>

--
-Dave

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

--
-Dave


(Douglas Gregor) #13

Yeah, Dave’s right about my vague fears. If they are actual problems, we can amend the proposal with any additional restrictions that come up. My apologies if I sent you down a wrong path!

Thank you for working on this! I left a few comments on the commits as well, but the proposal is looking good!

  - Doug

···

On Jan 2, 2017, at 1:03 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Jan 02 2017, Austin Zheng <austinzheng-AT-gmail.com <http://austinzheng-at-gmail.com/>> wrote:

Anyone who wants to help, by the way, is more than welcome to; I'm happy to
take PRs or just even a message describing what needs to change, and I'd of
course add you to the authors list...

Regarding "valid" recursive constraints breaking the compiler: it was a
reference to something Doug said in his original email:

I also have a nagging feeling that we will need some form of
restrictions on this feature for implementation reasons, e.g.,
because some recursive constraints will form unsolvable systems.

I wouldn't concern myself much with such vague fears-and-doubts if I
were you. Consider that unsolvable systems would be a *fundamental*
reason for needing restrictions, rather than an implementation reason.
If we discover such a scenario, we'll deal with it. My intuition is
that any such unsolvable systems will fall under the rubric of
ambiguities, so the restriction will be something like “don't make
something ambiguous.”


(Austin Zheng) #14

Thank you for all your feedback! I opened a PR here (
https://github.com/apple/swift-evolution/pull/578) to capture further
improvements and discussion. (If it's too early for a PR, I'll close my PR
and open a new one when the proposal is closer to completion.)

Best,
Austin

···

On Wed, Jan 4, 2017 at 10:35 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Jan 2, 2017, at 1:03 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Mon Jan 02 2017, Austin Zheng <austinzheng-AT-gmail.com > <http://austinzheng-at-gmail.com/>> wrote:

Anyone who wants to help, by the way, is more than welcome to; I'm happy to
take PRs or just even a message describing what needs to change, and I'd of
course add you to the authors list...

Regarding "valid" recursive constraints breaking the compiler: it was a
reference to something Doug said in his original email:

I also have a nagging feeling that we will need some form of
restrictions on this feature for implementation reasons, e.g.,
because some recursive constraints will form unsolvable systems.

I wouldn't concern myself much with such vague fears-and-doubts if I
were you. Consider that unsolvable systems would be a *fundamental*
reason for needing restrictions, rather than an implementation reason.
If we discover such a scenario, we'll deal with it. My intuition is
that any such unsolvable systems will fall under the rubric of
ambiguities, so the restriction will be something like “don't make
something ambiguous.”

Yeah, Dave’s right about my vague fears. If they are actual problems, we
can amend the proposal with any additional restrictions that come up. My
apologies if I sent you down a wrong path!

Thank you for working on this! I left a few comments on the commits as
well, but the proposal is looking good!

- Doug