[swift-evolution] Partially Constrained Protocols [Was: [Proposal] Separate protocols and interfaces]

[David Waite]

> On Jan 18, 2016, at 1:18 PM, Douglas Gregor <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

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