Higher Kinded Types Proposal

[CodaFi]

Proposal: Higher Kinded Types in Swift

• Proposal:
• Authors: TypeLift et al.
• Status: Review
• Review manager: TBD

Introduction

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.

Motivation

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 mapped 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.

Proposed Solution

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.

Detailed Design

Syntax

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-clauses in protocol type parameter lists.

Errors

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>> { //... }

[CodaFi]

I realize HKT is going to be a very large undertaking and a significant change to the language. So, I'd like to kick off the higher-Kinded types proposal drafting process with this issue. The top comment is the proposal itself, and the comments will be reserved for discussion of current drafts. By the end, we will submit the complete proposal to swift-evolution for community review.

[CodaFi]

Protocols being the most obvious place to start with new stuff, here's a couple versions of our Functor with HKTs:

Version 1: Attack of the angle brackets.

protocol Functor<Self<_>> {
  typealias A

  func fmap<B>(f : A -> B) -> Self<B>
}

Version 2.1: Where clauses with angles

protocol Functor where Self<_> {
  typealias A

  func fmap<B>(f : A -> B) -> Self<B>
}

Version 2.2: Where clauses with no parameter binding

protocol Functor where Self : _ -> _ {
  typealias A

  func fmap<B>(f : A -> B) -> Self<B>
}

Version 2.3: Where clauses with parameter binding

protocol Functor where Self : A -> _ {  
  func fmap<B>(f : A -> B) -> Self<B>
}

[CodaFi]

I lean towards the last of these (because I hate associated types with a passion, but I recognize it requires the most change and a significant amount of syntax.

[pthariensflame]

Can't we regard v2.3 as sugar for v2.2?

[CodaFi]

I wanted to make a distinction between typealiases and type parameters. I don't want swift to start dumping implicit typealiases all over the place - tho it would be a very swift-y thing to do. I was thinking 2.3 would bring the parameter into scope without introducing a new type into the protocol.

[pthariensflame]

Actually, how about:

v1.2: Angles in the outfield

protocol<A> Functor {
  func fmap<B>(f : A -> B) -> Self<B>
}

[pthariensflame]

That would also allow us to write such things as:

// ignore Functor, etc. dependencies for this demo
protocol<A> Monad {
  static func unit() -> Self<A>
  func bind<B>(f : A -> Self<B>) -> Self<B>
}

protocol<M : Monad, A> MonadTrans {
  init(lifting: M<A>) -> Self<M, A>
}

[CodaFi]

What does conformance look like (say, in an extension)?

[jckarter]

Kind is a constraint on a type parameter, so it makes sense to me to have it be a form that appears after the :, which works both on protocols and generic type params:

protocol Functor: <*> {...}

func mapM<M: <*>>(...)

I would focus on figuring out the technical work involved before ratholing on syntax too much though.

[mpurland]

I personally prefer @pthariensflame v1.2 without associated types. I think it would be cleaner and easier to work with.

[mpurland]

I agree with @CodaFi in that v2.2/v2.3 would be a next logical step for the language that is addicted to type aliases.

[CodaFi]

@jckarter I agree, but wouldn't syntax (and tactictly, features to be added) influence those technical details?

[pthariensflame]

@CodaFi I imagine conformance working like:

extension<A> Array<A>: Functor {
  public func fmap<B>(f: A -> B) -> Array<B> { return map(f) }
}

EDIT: Or, for short, extension Array: Functor { … }, although you'd have to use the longer form for Either and the like.

[adamkuipers]

I always thought the way SML was able to encode HKT was the most Swift-like. This requires generic type-aliases, which seems to be a more manageable (and approved by Apple for an implementation) solution.

Taken from https://existentialtype.wordpress.com/2011/05/01/of-course-ml-has-monads/

signature MONAD = sig
  type 'a monad
  val ret : 'a -> 'a monad
  val bnd : 'a monad -> ('a -> 'b monad) -> 'b monad
end

And converted to Swift

protocol MonadOps {
  typealias Monad<A>
  static func unit<A>(a: A) -> Monad<A>
  static func bind<A, B>(monad: Monad<A>, transform: A -> Monad<B>) -> Monad<B>
}

[pthariensflame]

@adamkuipers That representation, and any others like it, requires explicit dictionary passing. I want to avoid that at nearly any cost, and I'm sure @CodaFi feels similarly.

EDIT: Never mind, I misread the proposal. Nonetheless, I don't like it because it's not very “clean” conceptually, and it makes higher kinds second class citizens in the type system.

[CodaFi]

The common thread among all of these is that protocols need to start carrying kind information, so I'll start examining what it would take to start doing that.

[pthariensflame]

I think types in general need to start carrying kind information! Otherwise, how are we going to maintain kind-safety?

[CodaFi]

@pthariensflame Sorry, I meant *as user-facing syntax! The compiler can probably do fine inferring kinds for existing generic types.

[pthariensflame]

Oh, I see. Sorry for the misunderstanding. :)

[pyrtsa]

Here's a lengthy example that I think better convers the necessary use cases to consider: carrying kind information around, protocol extensions, protocol requirements in functions, protocol inheritance, mapping associated types to higher-kinded protocol parameters, and operators as part of protocol definition.

The key insight here is that, in my view, higher-kinded protocols carry the type argument along when conforming to, i.e. Functor<A>, not just Functor.

(TBH, this is also the weak point here, since it maps badly to existing Swift practice where it's e.g. okay to return Array when you mean just Array<Element>. On the other hand, I don't really get the fact where associated types are magic names that just appear in all extensions. Why not always give associated types local names, e.g. extension Array<T> { ... }. But I digress. — Edit: Another suggestion of not using typealias for associated types.)

So let's define Functor<A>:

// Higher-kinded protocol with no other constraints.
protocol Functor<A> {
    // Inside this definition, `Self<B>` allows exchanging the type parameter.
    func fmap<B>(f: A -> B) -> Self<B>
}

// Function definition. `F` is higher-kinded and must be applied with a type.
infix operator <^> { associativity left }
func <^> <F : Functor, A, B>(f: A -> B, x: F<A>) -> F<B> {
    return x.fmap(f)
}

Applicative<A>:

// Higher-kinded protocol with inheritance. Repeating `<A>` in the definition
// is necessary, since `A` wouldn't otherwise be visible in the body. (I can't
// make up my mind whether it's required to always write `Self<A>` in the body
// or if the `Self` shortcut should be allowed. But probably shouldn't.)
protocol Applicative<A> : Functor<A> {
    static func pure(x: A) -> Self<A>
    func <*> <B>(f: Self<A -> B>, x: Self<A>) -> Self<B>
}

Monad<A>:

protocol Monad<A> : Applicative<A> {
    func >>- <B>(f: A -> Self<B>) -> Self<B>
}

// Higher-kinded protocol extension.
extension Monad<A> {
    func bind<B>(f: A -> Self<B>) -> Self<B> {
        return self >>- f
    }
}

Array<A> shall be the simple example conforming to all of the above.

extension Array : Functor<Element> {
    func fmap<B>(f: Element -> B) -> [B] {
        return self.map(f)
    }
}

extension Array : Applicative<Element> {
    static func pure(x: Element) -> Array {
        return [x]
    }
}

func <*> <A, B>(fs: [A -> B], xs: [A]) -> [B] {
    return fs.flatMap {f in xs.map(f)}
}

extension Array : Monad<Element> {}

func >>- <A, B>(xs: [A], f: A -> [B]) -> [B] {
    return xs.flatMap(f)
}

Here's a Functor<A> instance for Dictionary<Key, A>. Fmapping over it keeps the keys intact:

extension Dictionary : Functor<Value> {
    func fmap<B>(f: Value -> B) -> [Key: B] {
        var result = [Key: B]()
        for (k, v) in self {
            result[k] = f(v)
        }
        return result
    }
}

I can't bend my head into thinking what it would take to support even higher kinds in the syntax, let alone implementing it! But maybe this level of expressivity would be a good start.

[pthariensflame]

What I don't like about all the proposals that put the higher-kinded Self parameters as the parameters of the protocol name is that they preclude us from considering actual parametrized protocols (i.e., multiparameter type classes in Haskell). My intent with putting them after the keyword instead was to make it clear that they were parameters to Self, rather than to the protocol proper.

[pyrtsa]

@pthariensflame If we want to do that, we need to gather a significant amount of evidence that there's real use for it in Swift. Partially applied type operators are quite a foreign concept in Swift today. Support for currying was dropped from function definitions too.

[griotspeak]

Use cases and implementation details seem like the biggest stumbling blocks for this proposal followed by syntax.

I think that a first use case we should/could provide is making an Array of Equatable conform to Equatable. A second use case could be making Collections of Hashable conform with a generalized algorithm.

[pthariensflame]

@griotspeak Neither of those are addressed by higher kinds; in fact, the two things you cited are actually concerns for the standard library, too, and Apple is in favor of them (although I can't seem to find where I read that).

[griotspeak]

I could easily be mistaken. I was thinking something along the lines of:

protocol EquatableSequenceType where Self<Equatable> : Equatable, SequenceType {
}

public func ==(lhs:EquatableSequenceType, rhs:EquatableSequenceType) -> Bool {
// iterate the collections comparing as we go.
}

EDIT: There is no way–at the language level–that I can see, at present, to express the idea that an Array of Equatable is Equatable. That is what I was referring to.

[pthariensflame]

I'm not completely sure what that would do. As far as I remember, the syntax they were considering for that was something like:

extension (SequenceType where Self.Element == Equatable) : Equatable {
  …
}

EDIT: but I could easily be wrong.

[mpurland]

Compared to the current syntax of:

extension SequenceType where Generator.Element : Equatable {
...
}

[griotspeak]

Here is a question which should simplify my confusion. Am I mistaken in my understanding that HKT could provide a consistent means to express that an [Equatable] is Equatable?

[pthariensflame]

They should not (by themselves). The purpose of HKTs is to allow you to express generics parameters that are themselves generic. Here is a good article on them (written for a language which just got them recently).

[mpurland]

@griotspeak I believe this will be addressed by Swift in the next version with complete generics. See: https://github.com/apple/swift-evolution

EDIT:

Complete generics: Generics are used pervasively in a number of Swift libraries, especially the standard library. However, there are a number of generics features the standard library requires to fully realize its vision, including recursive protocol constraints, the ability to make a constrained extension conform to a new protocol (i.e., an array of Equatable elements is Equatable), and so on. Swift 3.0 should provide those generics features needed by the standard library, because they affect the standard library's ABI.

[griotspeak]

Alright then, my mistake.

[pthariensflame]

@mpurland Ah! You found the reference I was looking for! Thanks!

[mpurland]

@pthariensflame It would be nice to have more clarification on complete generics to inform this discussion further.

[CodaFi]

I just had a crazy idea that would simplify this proposal. Instead of depending on getting generic protocols, let's scrap the idea altogether and force root protocols to declare their kind constraints as actual constraints. I propose the following reformulation of the proposal example:

// Higher-kinded protocol with no other constraints.
protocol Functor : Self<A> {
    func fmap<B>(f: A -> B) -> Self<B> // Self is checked to have kind * -> *
}

This way we stop performing kind inference and start performing kind checking which is more in line with one of the original goals of the proposal (fixing a class of programmer error with higher-order structures). For more complex kinds, we support the arrow kind like so

/// Ridiculous contrived thing
protocol IFunctorTrans : Self<A, I, M<T>> {
    func map<B, J>(trans : A -> B, itrans : I -> J) -> Self<B, J, M<T>>
}

Naturally, we must restrict kind constraints to non-derived protocols only to remove the ability to re-kind a protocol.

[JadenGeller]

That's a really nice solution! I'd definitely +1 it. I wish there were a way to still support protocol inheritance though.

Jaden Geller

On May 20, 2016, at 1:08 AM, Robert Widmann [email protected] wrote:

I just had a crazy idea that would simplify this proposal. Instead of depending on getting generic protocols, let's scrap the idea altogether and force root protocols to declare their kind constraints as actual constraints. I propose the following reformulation of the proposal example:

// Higher-kinded protocol with no other constraints.
protocol Functor : Self {
func fmap(f: A -> B) -> Self // Self is checked to have kind * -> *
}
This way we stop performing kind inference and start performing kind checking which is more in line with one of the original goals of the protocol (fixing a class of programmer error with higher-order structures). For more complex kinds, naturally we support the arrow kind like so

/// Ridiculous contrived thing
protocol IFunctorTrans : Self<I, M : A -> _> {
func imap<B, J>(trans : A -> B, itrans : I -> J) -> Self<J, M>
}
Naturally, we must restrict kind constraints to non-derived protocols only to remove the ability to re-kind a protocol.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub

[CodaFi]

There, I've updated it to make arrows implicit in the structure of generics. That will need to be a separate proposal...

[CodaFi]

The trouble is how currying interacts with kind arrows. I'd like to be able to do this in the future:

protocol MonadTrans : Self<M<A>> { /* ... */ }

struct StateT<S, M<A>> { /* ... */ }

extension StateT<S, _> : MonadTrans { /* ... */ }

But that kind of abstraction makes no sense syntactically.

[sighoya]

Are higher kinded types aka Nested Generics not already supported in Swift 3.1 ?

[pthariensflame]

@sighoya No. That's Generic Currying. It only gets you some of Higher Kinds.

[sighoya]

@pthariensflame
Ah, my fault, then
+10 for HKT in Swift

[alickbass]

Hey guys! Maybe one example of where the lack of higher kinded types is a blocker: there are a lot of different Reactive Stream libraries (RxSwift, ReactiveSwift etc.) but if you would like to create a library that would build on top of them, you would have to choose one and stick to it. So this means that it's now impossible in swift to write code that would work for any Stream. This means, if, potentially you want to write an abstraction over all the Streams, you will have to repeat your code for all of them and (what is even worse and is an actual blocker) you would have to import all of these Reactive Libraries which is just ridiculous. The example of such project: ReactiveReSwift and we were trying to write a Router for it, but had to choose RxSwift because the Router itself uses operations over streams (map, flatMap etc).