lmihalkovic/extended_existentials.md

## extended_existentials.md

      
    Raw
  

              extended_existentials.md
            
          
    Generalized Existentials

Background

Proposal 0095

The proposal pushed forward a new syntax for expressing constraints in the generics system
== Swift 2.x

// argument type constraint
func f(a: protocol<A,B>) {}

// generic method constraint
func g<T : A>(x : T) where T : B {}		// equivalent to next
func g<T : protocol<A,B>>(x : T) {}		// equivalent to previous


== Swift 3.0

// argument type constraint
func f(a: A & B) {}

// generic method constraint
func g<T: A & B>(x: T) {}
The syntax leaves a gap when it comes to expressing the so called Top type:
== Swift 2.x

/// The protocol to which all types implicitly conform.
public typealias Any = protocol<>

== Swift 3.0

==> no way to express the Top type other than for the compiler to artbitrarily designate one
Starting from the 0095 syntax for protocol compositions, it is possible to explore possible syntax extensions of which 0095 would merely form a special case. These extensions can be the basis for a generalized existential notation.
Swift collection shorthands

Swift currently offers shorthand notations for a number of collection types.
var a:Array<Int>
var a:[Int]				// shorthand defining an Array type

var s:Set<Int>
						// no shorthand

var d:Dictionary<K,V>
var d:[K,V]				// shorthand defining a Dictionary type
These shorthand establish a precedent in the language for establishing an association between a protocol, one or more associated types and the subscript notation [ ] .
Generalized Existentials

The rest of this document explores a possible existential type notation based on generalizing the syntax from 0095, and extending use of the shorthand notation used to express collections.
In the following sections, each of the examples is compared with this alternative proposal, which explores a broadening of the protocol<> syntax for generalized existentials.
Syntax

Before looking into concrete examples, the following is an overview of the grammar changes entailed by this proposal.
type → array-type | ... | implicitly-unwrapped-optional-type |
	 protocol-composition-type | metatype-type

// 0095: former : protocol<...>
protocol-composition-type → protocol-identifier-list

// 0095: new infix operator for composition
protocol-identifier-list → protocol-identifier | protocol-identifier & protocol-identifier-list

// supplemental definition for compositions
protocol-composition-type → type-identifier [ existential-type-body ] |
							protocol-identifier [ existential-type-body ] |
							class [ existential-type-body? ]

existential-type-body → protocol-identifier-list
existential-type-body → protocol-identifier-list & existential-requirement-list  // could also be ';'

existential-requirement-list → existential-requirement |
							   existential-requirement & existential-requirement-list

existential-requirement → conformance-requirement | same-type-requirement

conformance-requirement 	→ ... // TODO describe '.Xxxx' shorthand notation
same-type-requirement		→ ... // TODO describe '.Xxxx' shorthand notation


Filling the Gap left by 0095

Applying the proposed syntax to the degenerate case of a unnamed zero-elements types composition lends a definition for the so-called top type, to which all other types implicitely conform. For convenience, the standard library can define a more conveninent shorthand notation for it: Any is its current value.
== Swift 2.x

/// The protocol to which all types implicitly conform.
public typealias Any = protocol<>

== Swift 3.0

public typealias Any = _[]				// a zero-elements composition applied to no 
										// specific type is de-facto a definition for Any
Simple existential declarations

This section explores simple compositions involving multiple protocols, as well as shows how 0095 is in fact a shorthand for the notation proposed in this document.
// Can be any type that conforms to both Equatable and Streamable.
let a : Any<Equatable, Streamable>

==> BECOMES
let a : _[Equatable & Streamable]		// '_' signifies that the final composition does not refine an existing type
let a : Equatable & Streamable			// possible shorthand equivalant
// Can be any type that conforms to ProtocolA, ProtocolB, and ProtocolC.
let a : Any<ProtocolA, Any<ProtocolB, ProtocolC>>

==> BECOMES
let a : _[ProtocolA & ProtocolB & ProtocolC]	// '_' signifies that the final composition does not refine an existing type
In the alternative proposal, the relationship with 0095 rests on the fact that if it is redundant to express Any-ness twice
let a : Any<ProtocolA, ProtocolB, ProtocolC>
let a : ProtocolA & ProtocolB & ProtocolC			// synonymous
In this proposal the relationship with 0095 is clear and logical as it is manifest that 0095 refers to protocol compositions that do not refine an existing class type
let a : _[ProtocolA & ProtocolB & ProtocolC]	// '_' signifies that the final composition does not refine an existing class type
let a : ProtocolA & ProtocolB & ProtocolC		// which is the exact definition of this declaration
Constraint on class types

This section deals with class types

Straight class type

// "Any type which is a class"
typealias AnyObject = Any<class>

==> BECOMES
typealias AnyObject = class[]			// class, no refinements

Class with specific protocol conformance

protocol A : class { }
let a : Any<class, UITableViewDelegate>

==> BECOMES
let a : class[UITableViewDelegate]		// basically the OBJ-C id<UITableViewDelegate> 
// Any type which is a class conforming to Streamable
typealias SteamableObject = Any<class, Streamable> 

==> BECOMES
typealias SteamableObject = class[Streamable]

The case of AnyObject

// Any type which is a class conforming to Streamable
typealias AnyObject = Any<class> 

==> BECOMES
typealias AnyObject = class[]			// a zero-protocol composition
Nesting

This section deals with refining a given class type with specific protocol conformances. This is a type that can currently not be expressed in Swift today.

Clarity and concision

One of the problem with the alternate proposal is that the implementation will need to have a lot of validations built into the typechecker to eliminate some of the combinations that the parser would recognize as valid. The proposed grammar in this proposal would simply reject some of these early.
// Can be any type that is a UITableView conforming to ProtocolA.
// UITableView is the most specific class, and it is a subclass of the other
// two classes.
let a : Any<UIScrollView, Any<UITableView, Any<UIView, ProtocolA>>>

==> BECOMES
let a : UITableView[ProtocolA]

More complex scenarios

// Any custom UIViewController that serves as a delegate for a table view.
typealias CustomTableViewController = Any<UIViewController, UITableViewDataSource, UITableViewDelegate>

// Pull in the previous typealias and add more refined constraints.
typealias PiedPiperResultsViewController = Any<CustomTableViewController, PiedPiperListViewController, PiedPiperDecompressorDelegate>


==> BECOMES

typealias CustomTableViewController = UIViewController[UITableViewDataSource & UITableViewDelegate]

typealias PiedPiperResultsViewController = CustomTableViewController[PiedPiperListViewController & PiedPiperDecompressorDelegate]
where clause

typealias AnyCollection<T> = Any<Collection where .Element == T>
let a : AnyCollection<Int> = [1, 2, 3, 4]

==> BECOMES
typealias AnyCollection<T> = Collection[.Element == T]
// this is the explicit syntax
let a : Collection[.Element:Int] = Set([1,2,3,4])

// But with an addition to protocol definitions
protocol Collection : Indexable, Sequence {
	// 'default' being introduced here (ok, maybe in IteratorProtocol instead)
	default associatedType Element
}
let a : Collection[:Int] = [1,2,3,4]		// this might become possible
let a : Collection[Int] = [1,2,3,4]		// or even this if there is no where clause
// Can be any Collection whose elements are Ints.
let a : Any<Collection where .Element == Int>

==> BECOMES
let a : Collection[.Element : Int]
// Can be any Collection whose elements are Streamable; the Collection itself 
// must also be Streamable.
let b : Any<Streamable, Collection where .Element : Streamable> 

==> BECOMES
let b : Collection[Streamable & .Element:Streamable]
let b : Collection[Streamable ; .Element:Streamable]	// possible alternative also include ','  
Generics bridging

let a : Any<SomeClass, SomeProtocol, where .Assoc1 == SomeType, .Assoc2 : AnotherProtocol>

func foo<T>(z: T) where T : SomeClass, T : SomeProtocol, T.Assoc1 == SomeType, T.Assoc2 : AnotherProtocol {
    // ...
}

==> BECOMES
// a is compatible with foo()
let a : SomeClass[SomeProtocol & .Assoc1 == SomeType & .Assoc2 : AnotherProtocol]

func foo<T>(z: T) 
	where T : SomeClass & SomeProtocol,
		  T.Assoc1 == SomeType,
	      T.Assoc2 : AnotherProtocol {
    // ...
}
Alternatives

let b : Collection[Streamable]
		where .Element:Streamable

let a : SomeClass[SomeProtocol] 
		where .Assoc1 == SomeType & .Assoc2 : AnotherProtocol
The following proposal: Enhanced Existential Support