[swift-evolution] Partially Constrained Protocols [Was: [Proposal] Separate protocols and interfaces]
Douglas Gregor
dgregor at apple.com
Tue Jan 19 14:21:31 CST 2016
> On Jan 19, 2016, at 10:47 AM, David Waite <david at alkaline-solutions.com> wrote:
>
>
>> On Jan 19, 2016, at 7:49 AM, Maximilian Hünenberger <m.huenenberger at me.com <mailto:m.huenenberger at me.com>> wrote:
>>
>> I like the idea to use protocol<> for an abstraction with many constrained protocols but for a single type constraint it is a bit verbose.
>>
>> What about generics in protocols which are only a view to its associated types or generics which create/are associated types?
>
> Since I imagine reusing generics syntax for constraining protocols will be a popular proposal, I figure I’ll give the reasoning I personally didn’t use, at it for my initial placeholder syntax.
>
> The main reason l chose an alternate syntax was that generic type usage and protocol constraints aren’t expressed the same way - protocol constraints on associated types aren’t positional and can be missing. This meant that ConcreteThing<…> and ProtocolType<…> would have different syntaxes inside the angle brackets, and thus felt like it would promote more syntax bike shedding (in addition to personally seeming less clean to me).
>
> Using ProtocolType<…> syntax would I believe be the 5th syntactic usage for <...> (generic type declaration, generic type use, generic constraints on methods, protocol union and now generic protocol use). Swift gets away with the multiple usages today because the syntax within the angle brackets is very similar. Expanding protocol unions meant I stayed closer to generic constraint syntax, while still having was only four syntactic usages (as in, protocol unions would umbrella under/into partial protocol constraints as a new existential type redefinition “thing")
>
> As an example, the liberties I took with SequenceType took it down to a single associated type, but CollectionType would still have a minimum of Index and Element. I would need to declare CollectionType<where .Index == Index> or similar if I were wishing to partially constrain just one parameter. This is also eliminates most of the typing savings of using generic type usage syntax.
Right. There’s also SubSequence, which you almost certainly don’t want to have to specify. For reference, once we get generic typealiases, one would be free to add
typealias AnyCollection<Element> = protocol<CollectionType where .Element == Element>
to cover the common case.
- Doug
>>
>> Example of a simple protocol which models a node of a tree:
>>
>> // Before
>>
>> // NodeType can be anything
>> // currently Swift doesn't allow
>> // `typealias NodeType: Node`
>> //
>> // or even where clauses
>> // `typealias NodeType: Node where NodeType.T == T`
>> protocol Node {
>> typealias T
>> typealias NodeType
>>
>> var value: T { get }
>> var nodes: [NodeType] { get }
>> }
>>
>> // After
>> protocol Node<T> {
>> typealias T // probably remove this declaration (see reason below)
>> var value: T { get }
>> var nodes: [Node<T>] { get }
>> }
>>
>> So a generic parameter is placed after the protocol name. Therefore a corresponding associated type could be synthesized making its declaration in the body of the protocol unnecessary.
>>
>> In order to let this still compile:
>>
>> func afunction<S: SequenceType where S.Generator.Element == Int>(s: S){}
>>
>> there could be a general Swift feature to get the generic type by dot syntax (e.g. synthesized typealiases for every generic parameter).
>>
>>
>> Implementation:
>> The function declaration above could be rewritten to using a function like generic parameter parameter syntax for protocols:
>>
>> // Declaration of SequenceType
>> protocol SequenceType<Element: Generator.Element, Generator: GeneratorType, SubSequence> { … }
>> // ^~~~ using : in oder to allow default types with =
>>
>> // Using "_" to leave it unspecified eg. Any
>> func afunction(s: SequenceType<Element: Int, Generator: GeneratorType<Element: Int>, SubSequence: _>){}
>> // omitting `SubSequence: _` since the type is already unambiguous
>> func afunction(s: SequenceType<Element: Int, Generator: GeneratorType<Element: Int>>){}
>> // omitting `Generator: GeneratorType<Int>` since the type of `Generator` can be inferred from Element
>> func afunction(s: SequenceType<Element: Int>){}
>>
>> The order of arguments is in this case irrelevant, but should probably be in a strict ordering to make it more consistent with the point below.
>>
>> In order to have a more general generic parameter behavior (to work with structs, classes and enums) we could also allow to use these without external names and only their order. So the example above would look like this:
>>
>> func afunction(s: SequenceType<Int, GeneratorType<Int>, _>){}
>> func afunction(s: SequenceType<Int, GeneratorType<Int>>){}
>> func afunction(s: SequenceType<Int>){}
>>
>> // These two functions don't produce an error since `Element` can be inferred
>> func afunction(s: SequenceType<GeneratorType<Int>, _>){}
>> func afunction(s: SequenceType<GeneratorType<Int>>){}
>>
>> // for an unconstrained Sequence "_" can be used in order to make it clear: "there could be generic parameters"
>> func afunction(s: SequenceType<_>){}
>>
>> For instance `Array` and `Dictionary` also can apply to this model.
>>
>> Also where clauses could be used in generic parameter declarations which are disallowed for associated types (currently).
>>
>>
>> What do you think about this approach?
>>
>> Should SequenceType<_> be equal to SequenceType<Any> / SequenceType<Element: Any> ?
>>
>>
>> - Maximilian
>>
>>> Am 19.01.2016 um 00:32 schrieb David Waite via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>>:
>>>
>>>
>>>> On Jan 18, 2016, at 1:18 PM, Douglas Gregor <dgregor at apple.com <mailto:dgregor at apple.com>> wrote:
>>>>>
>>>>> let x:SequenceType = [1,2,3] // no constraints specified whatsoever
>>>>> let y:protocol<SequenceType where Generator.Element == String> = [“foo”, “bar”] // partially constrained
>>>>
>>>> Not wanting to start throwing paint, but "Generator.Element" could be ambiguous with a Generator in the lexical scope. You'll probably want some way to differentiate it (eg, a leading dot). Otherwise, this is the syntactic direction that I think makes the most sense.
>>>
>>> Yes, I’ll use that below. There is a right balance in extending protocol<>. For instance, I did not like the following at all:
>>>
>>> protocol<S:SequenceType where S.Generator.Element == String>
>>>
>>>>
>>>>> One interesting side-effect to note is that SequenceType could be redefined to only have “Element” as an associated type. Instead of Generator or SubSequence being associated types, methods could return partially constrained GenericType or SequenceType from the appropriate methods. This would be one way of eliminating issues today with recursive use of associated types (as well as SubSequence over-constraining the output of various algorithms to a single concrete type)
>>>>
>>>> Assuming nobody cares about the identity of the Generator type, which is probably a safe assumption. Note that one could implement this design today by using a function taking no arguments and returning an Element? in lieu of "Generator”.
>>>
>>> Yes, as an aside I was actually curious GeneratorType existed when I was first diving into the standard library, considering it could just be a closure.
>>>
>>>>
>>>>>
>>>>> For the “opening” of an existential type to find the concrete type it stores dynamically, I’m currently using a different syntax just because the “open x as T” originally given makes ‘open’ a keyword’ and makes it unclear where ’T’ came from
>>>>
>>>> Yes, the issue of "which name did I introduce?" is tricky here.
>>>>
>>>>> - I’m instead overloading the typealias keyword when used within an expression context:
>>>>>
>>>>> typealias T = x.dynamicType
>>>>> let xT = x as! T
>>>>
>>>> x will have to be immutable for this to make sense. That's why my ugly "open" expression extracts a new value and gives it a fresh type in one lexically-scoped block. Both the type and the value end up being scoped. Otherwise, one might reassign "x" with a different dynamic type... Then what does T mean?
>>>
>>> This is an area that I need to understand compiler behavior more here (I’ve been researching)
>>>
>>> If ’T’ internally behaves like an immutable variable with lexical scope, then ’typealias’ in a code block is just another statement, and the type would be based on the value of ‘x’ at the point of execution:
>>>
>>> var x:Any = “Initial”
>>> typealias T = x.dynamicType // String
>>> x = 1
>>> let xT = x as! T // fails precondition as if I had said x as! String
>>>
>>> I’m guessing from your comment however that T would not a variable. In which case, it makes sense to be more restrictive in use (such as requiring immutability). This is also more consistent with the use of typealias in other contexts, if that was the syntax one was going with.
>>>
>>>> I suggest you also look at what can be done with an existential value that hasn't been opened explicitly. Can I call "generate" on a SequenceType value, and what do I get back?
>>>
>>> Depends on how far we are willing to go. If you are only willing to expose the invariants in the face of the constraints given (in this case none), all you would get exposed is “underestimateCount”.
>>>
>>> If you are willing to expose anything which can be expressed by certain type safety rules (needing formal definition later), then you can do quite a bit.
>>>
>>> To start, let me express SequenceType relying on the partially constrained protocols, taking a few liberties:
>>> - pruning some alternate forms
>>> - removing SubSequence and Generator associated types and just having Element
>>> - using the protocol<> syntax described before (with . prefix)
>>> - returning partially constrained SequenceTypes rather than stdlib concrete types like JoinSequence in a few cases.
>>> - eliminate usage of AnySequence in definitions (not needed)
>>> - assuming a change in protocol LazySequenceType to be expressed in terms of Element rather than a base SequenceType
>>>
>>> protocol SequenceType {
>>> associatedtype Element
>>>
>>> var lazy:protocol<LazySequenceType where .Element == Element> { get }
>>> func contains(@noescape predicate:(Element) throws -> Bool) rethrows -> Bool
>>> func dropFirst(n:Int) -> protocol<SequenceType where .Element == Element>
>>> func dropLast(n:Int) -> protocol<SequenceType where .Element == Element>
>>> func elementsEqual(other:protocol<SequenceType where .Element == Element>, @noescape isEquivalent: (Element, Element)) -> Bool
>>> func enumerate() -> protocol<SequenceType where .Element == (Int, Element)>
>>> func filter(@noescape includeElement: (Element) throws-> Bool) rethrows -> [Element]
>>> func flatMap<E>(transform: (Element) throws -> protocol<SequenceType where .Element:E>) rethrows -> [E]
>>> func flatMap<T>(@noescape transform: (Element) throws -> T?) rethrows -> [T]
>>> func forEach(@noescape body: (Element) throws -> ()) rethrows
>>> func generate() -> protocol<GeneratorType where .Element == Element>
>>> func lexicographicalCompare(other: protocol<SequenceType where .Element == Element>, @noescape isOrderedBefore:(Element,Element) throws-> Bool) rethrows -> Bool
>>> func map<T>(@noescape transform: (Element) throws -> T) rethrows -> [T]
>>> func maxElement(@noescape isOrderedBefore: (Element,Element) throws -> Bool) rethrows -> Element?
>>> func minElement(@noescape isOrderedBefore: (Element,Element) throws -> Bool) rethrows -> Element?
>>> func prefix(n:Int) -> protocol<SequenceType where .Element == Element>
>>> func reduce<T>(initial: T, @noescape combine: (T, Element) throws -> T) rethrows -> T
>>> func reverse() -> [Element]
>>> func sort(@noescape isOrderedBefore: (Element,Element) throws -> Bool) rethrows -> [Element]
>>> func split(maxSplit: Int, allowEmptySubsequences: Bool, @noescape isSeparator: (Element) throws -> Bool) rethrows -> [protocol<SequenceType where .Element == Element>]
>>> func startsWith(other: protocol<SequenceType where .Element == Element>, @noescape isEquivalent: (Element, Element) throws -> Bool) rethrows -> Bool
>>> func suffix(n:Int) -> protocol<SequenceType where .Element == Element>
>>> func underestimateCount() -> Int
>>> }
>>>
>>> extension SequenceType where Element:Equatable {
>>> func elementsEqual<OtherSequence : protocol<SequenceType where .Element == Element>(other: OtherSequence) -> Bool
>>> func split(separator: Element, maxSplit: Int, allowEmptySlices: Bool) -> [protocol<SequenceType where .Element == Element>]
>>> func startsWith(other: protocol<SequenceType where .Element == Element) -> Bool
>>> }
>>>
>>> extension SequenceType where Element == String {
>>> func joinWithSeparator(separator:String) -> String
>>> }
>>>
>>> extension SequenceType where Element:protocol<SequenceType>
>>> func flatten() -> protocol<SequenceType where .Element == Element.Element>
>>> func joinWithSeparator(separator: protocol<SequenceType where .Element = Element.Element>) -> protocol<SequenceType where .Element == Element.Element>)
>>> }
>>>
>>> extension SequenceType where Element:Comparable {
>>> func lexicographicalCompare(other: protocol<SequenceType where .Element == Element>) -> Bool
>>> func maxElement() -> Element?
>>> func minElement() -> Element?
>>> func sort() -> [Element]
>>> }
>>> Now, mapping this in terms of just an unconstrained SequenceType, which is shorthand for protocol<SequenceType where .Element:Any>:
>>> - None of the extensions match the constraint on Element, so they are not exposed
>>> - property Lazy is exposed as an unconstrained LazySequenceType, aka protocol<LazySequenceType where .Element:Any>
>>> - the predicate function in contains is not constrained by a particular kind of element, so it becomes (Any)->Bool, e.g.:
>>> func contains(@noescape predicate:(Any) throws -> Bool) rethrows -> Bool
>>> - dropFirst/dropLast would return an unconstrained SequenceType. This would need to leverage rules around constrained protocol variance/equivalence.
>>> - elementsEqual was changed to no longer be generic - one can pass in any SequenceType constrained to have the same Element type. The function parameter, similar to contains above, now has the signature (Any, Any)->Bool
>>> - enumerate() will return a sequence with elements of type (Int, Any)
>>> - filter takes a (Any) throws -> Bool method and returns [Any]
>>> - flatMap and forEach are exposed similar to contains above
>>> - generate returns an unconstrained GeneratorType (so it will have a single method func next() -> Any?)
>>> - lexicographicalCompare fails, more below
>>> - reduce has effective syntax:
>>> func reduce<T>(initial: T, @noescape combine: (T, Any) throws -> T) rethrows -> T
>>> - the rest are exposed as above except for startsWith
>>>
>>> So all functionality except lexicographicalCompare and startsWith could at least in theory be exposed safely. These cannot be exposed cleanly because method expected an input sequence with the same element type, but the element type is not invariantly constrained. Self properties and method arguments are an equivalent problem, except that for a Self argument can only be invariantly constrained when you know the implementing concrete type - hence wanting a system to dynamically reason about said types.
>>>
>>> This seems like a good amount of exposed functionality. Granted, it is not free to work at the level of protocols vs concrete types, and this does not attempt to simplify that. However, this proposal seems to bridge the gap between protocols without associated types and protocols with them. I also am happy with the amount of functionality that can be exposed safely as well as the consistency (A lexicographicalCompare function working on heterogenous sequences would have to be declared differently)
>>>
>>> -DW
>>>
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160119/428b2de5/attachment-0001.html>
More information about the swift-evolution
mailing list