typelift / swift Goto Github PK
View Code? Open in Web Editor NEWThis project forked from swiftlang/swift
The Swift Programming Language
License: Apache License 2.0
This project forked from swiftlang/swift
The Swift Programming Language
License: Apache License 2.0
This proposal details the addition of a left-biased sum type to the
Swift Standard Library. Earlier attempts at adding this have been too
specifically focused on error handling (duplicating functionality
throws
already provides), whereas this implementation will focus on
data, organization, and type safety. We believe that adding the type
to the standard library and simultaneously emphasizing its use cases
-that is, when you need a type that represents exactly 2 disjoint possibilities-
can dispel the confusion caused in other languages
and quell the conflict with throws
.
Inevitably, it seems languages reach the point where they see the need
to handle finite-argument disjoint variants with a data type as was
done in C++, C#, D, F#, SML, Haskell, Scala, ALGOL, and many others.
When coupled with a strong, static type system they can be made even
more useful because support for totality checking and safety come from
the language itself. Recently, certain prominent implementations have
chosen to use an Either
type to represent control flows that can
possibly raise errors. But Either can be written without this
convention to simply be a generic type, which is what we propose.
As before, unlike throws
, a disjoint union type can be applied in arbitrary
positions, used as a member, and easily checked for completeness
at compile time. In addition, the lack of a standard union type has
led the Swift community to create numerous duplicate implementations of the
same mutually incompatible types over and over and over again. In the
interest of promoting a type that there has received clear interest by the
community, the addition to the Standard Library is necessary.
The Swift Standard Library will be updated to include a left-biased
sum type we have called Either
- though other names may be
appropriate depending on how the type is implemented.
A complete implementation, based on the Swiftx library's implementation, with comments is given below:
/// The `Either` type represents values with two possibilities:
/// `.Left(LeftValue)` or `.Right(RightValue)`.
///
/// The `Either` type is left-biased by convention. That is, the values in the
/// `Left` half of the `Either` are considered fair game to be transformed using
/// e.g. `map` and `flatMap` while values in the `Right` half of the `Either`
/// are considered constant.
public enum Either<LeftValue, RightValue> {
case Left(LeftValue)
case Right(RightValue)
/// Much like the ?? operator for `Optional` types, takes a value and a
/// function, and if the receiver is `.Right`, returns the value, otherwise
/// maps the function over the value in `.Left` and returns that value.
public func fold<U>(value : U, @noescape f : (LeftValue) throws -> U) rethrows -> U {
return try self.either(onLeft: f, onRight: { _ in value });
}
/// Applies the given function to any left values contained in the receiver,
/// leaving any right values untouched.
public func map<U>(@noescape f: (LeftValue) throws -> U) rethrows -> Either<U, RightValue> {
switch self {
case let .Left(l):
return .Left(try f(l))
case let .Right(r):
return .Right(r)
}
}
/// If the `Either` is `Right`, simply returns a new `Right` with
/// the value of the receiver. If `Left`, applies the function `f`
/// and returns the result.
public func flatMap<U>(@noescape f: (LeftValue) throws -> Either<U, RightValue>) rethrows -> Either<U, RightValue> {
switch self {
case let .Left(l):
return try f(l)
case let .Right(r):
return .Right(r)
}
}
/// Case analysis for the `Either` type.
///
/// If the value is `.Left(a)`, apply the first function to `a`. If it is
/// `.Right(b)`, apply the second function to `b`.
public func either<U>(@noescape onLeft onLeft : (LeftValue) throws -> U, @noescape onRight : (RightValue) throws -> U) rethrows -> U {
switch self {
case let .Left(e):
return try onLeft(e)
case let .Right(e):
return try onRight(e)
}
}
/// Reverses the order of values of the receiver.
public var flip : Either<RightValue, LeftValue> {
switch self {
case let .Left(l):
return .Right(l)
case let .Right(r):
return .Left(r)
}
}
/// Determines if this `Either` value is a `Left`.
public var isLeft : Bool {
switch self {
case .Left(_):
return true
case .Right(_):
return false
}
}
/// Determines if this `Either` value is a `Right`.
public var isRight : Bool {
switch self {
case .Right(_):
return true
case .Left(_):
return false
}
}
}
extension Either : CustomStringConvertible {
/// A textual representation of `self`.
public var description : String {
switch self {
case let .Left(l):
return "Left(\(l))"
case let .Right(r):
return "Right(\(r))"
}
}
}
public func == <LeftValue : Equatable, RightValue : Equatable>(lhs : Either<LeftValue, RightValue>, rhs : Either<LeftValue, RightValue>) -> Bool {
switch (lhs, rhs) {
case let (.Left(l), .Left(r)) where l == r:
return true
case let (.Right(l), .Right(r)) where l == r:
return true
default:
return false
}
}
public func != <LeftValue : Equatable, RightValue : Equatable>(lhs : Either<LeftValue, RightValue>, rhs : Either<LeftValue, RightValue>) -> Bool {
return !(lhs == rhs)
}
As this is an addition to the Standard Library, no existing code should be affected
unless the author happens to be using the identifier Either - in which case
there is a strong chance that their Either and our Either are the same
thing, aligning with the goal of removing duplicate implementations of
this common type.
The fears of the previous proposal that attempted to put a Result<T>
type in the Standard Library, of duplicating existing functionality with respect to
throws
remain, but as noted before throws
is not as
flexible or declarative enough for all possible cases. If necessary,
a note can be left in the documentation warning away users of the
Either
type that really need throws
.
The bias in this definition of Either may be a sticking point, but the
presence of an unbiased Either would lead to confusion as to what both
lobes of the type were for. As noted in the mailing list, such a type would
be equivalent to (A?, B?)
with convenience methods to extract values
and induct on the "cases" of each side of the tuple.
In addition, the name Either
does not lend much to the imagination,
and the use of Left
and Right
cause considerable confusion to
novices in Haskell precisely because the type is used mostly for error
handling. If that case were discouraged, and this type treated like
data first, the use of Left
and Right
and Either
becomes less nebulous. Mostly, the
name does not matter so much as the structure, so possibilities for a
renaming including cases are:
Higher-Kinded Types are an extension to the Swift type system that allows for more expressive generic quantification and protocols that are aware of more of the structure of their conforming types. Kinds, used to great effect in Haskell and Scala, have made generic programming with types easier, richer, and safer in these languages, and have recently attracted the attention of the Rust community because of this.
The implementation of lawful structures and protocols in Swift occasionally necessitates being able to ask the Swift type system to check the shape of a type, not just its name. To that end, Higher Kinded Types enable not just a new class of programs to be written safely, but open the doors to better error checking and reporting, and the creation of higher-order structures and patterns.
For example, the standard library implements a number of declarative primitives and combinators, among them map
. In order to create a model that abstracts over just those types capable of being map
ped over, we wrote this Functor
protocol:
/// Functors are mappings from the functions and objects in one set to the functions and objects
/// in another set.
public protocol Functor {
/// Source
typealias A
/// Target
typealias B
/// A Target Functor
typealias FB = K1<B>
/// Map a function over the value encapsulated by the Functor.
func fmap(f : A -> B) -> FB
}
From this signature, it is possible to implement Functor
in a type-unsafe or unsuitably generic way by mixing up the associated types. In addition, because there was no way to indicate the kind of FB
, we developed a stack of so-called "Kind Classes" to serve as markers, but the implementor may still overwrite FB
with whatever type they so choose. In addition, any type can claim to be this Functor
, meaning that quantification over Functor
-like things is a fundamentally unsafe operation. This makes our abstraction leaky, fragile, and fundamentally non-composable.
With Higher-Kinded Types, that Functor
protocol can be rewritten as such:
NB: Not final syntax, here for demonstration.
// Higher-kinded protocol with no other constraints.
protocol<A> Functor {
// Inside this definition, `Self<B>` allows exchanging the type parameter.
func fmap<B>(f: A -> B) -> Self<B> // Self is inferred to have kind * -> *
}
This definition uses Kind inference to enforce that any type that wishes to implement Functor<A>
must have at least the Kind * -> *
to instantiate the parameter A
.
The compiler must be modified to produce and check kind information for classes, structs, and protocols. In addition, Protocols must now be capable of introducing kind parameters that are reflected in their conforming types. We demonstrate a proposed syntax for these in the next section.
Unlike GHC, our proposal involves implementing Kinds with just 1 possible constructor *
or Kind
for the type of data types. True to Haskell's kind system, *
and k1 -> k2
(where k1, k2 : *
) will be the only possible constructors for Kind
. Kind inference for data types proceeds as a consequence of type checking. For example:
Int // Has kind *
[String] // Has kind *
struct Foo<A> {} // Has kind * -> *
enum Bar<A, B> {} // Has kind * -> * -> *
final class Baz<A : Functor, B, C : Functor, D, E> { //... } // Has kind (* -> *) -> * -> (* -> *) -> * -> * -> *
NB: NOT FINAL
The most visible user-facing change will be the introduction of parametrized protocols. The syntax for protocol declarations must be amended:
- protocol-declaration → attributes opt access-level-modifier opt **protocol** protocol-name type-inheritance-clause opt protocol-body
+ protocol-declaration → attributes opt access-level-modifier opt **protocol** protocol-name generic-parameter-clause opt type-inheritance-clause opt protocol-body
protocol-declaration → attributes opt access-level-modifier opt **protocol** protocol-name generic-
parameter-clause opt type-inheritance-clause opt protocol-body
protocol-name → identifier
protocol-body → { protocol-member-declarations opt }
protocol-member-declaration → protocol-property-declaration
protocol-member-declaration → protocol-method-declaration
protocol-member-declaration → protocol-initializer-declaration
protocol-member-declaration → protocol-subscript-declaration
protocol-member-declaration → protocol-associated-type-declaration
protocol-member-declarations → protocol-member-declarationprotocol-member-declarations opt
And, though it does not appear in the grammar, the Self
keyword for parameter types must be extended to allow for generic-argument-clause
s in protocol type parameter lists.
New errors that can now be checked as a result:
protocol<A> Functor { func fmap<B>(f: A -> B) -> Self<B> }
protocol<A> Pointed { func point(x : A) -> Self<A> }
// Kind constraint inherited from `Functor` and `Pointed` declarations
protocol Applicative : Pointed, Functor { func ap<B>(f : Self<A -> B>) -> Self<B> }
protocol Monad : Applicative { func bind<B>(f : A -> Self<B>) -> Self<B> }
extension Int : Functor { // Error: Type 'Int' (*) does not satisfy kind requirement (* -> *)
// ...
}
extension Array<Element> : Functor { // Error: Array does not implement Functor
public func fmap<Other>(f : Element -> Other) -> Array<Element> { //... }
}
// Has kind (* -> *) -> * -> *
struct MaybeT<M : Monad, A> = MaybeT { let runMaybeT : () -> M<Maybe<A>> { get; } }
let m : MaybeT<Int, Int> = //... // Error: Type 'Int' (*) does not satisfy kind requirement (* -> *)
func binary<A, B, G : Functor, F : Functor>(f : A -> B, d : F<G<A>>) -> F<G<B>> { //... }
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.