Swift Generics: connection between equality constraints on generic parameters and GADTs


(Gabriel Scherer) #1

I'm not familiar with Swift, but happened to find the Generics
Manifesto document at
  https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

I wonder if the Swift community is aware of the strong connection
between equalities on generic type parameters of the form "where T ==
Foo" in method or extension declarations, and the Generalized
Algebraic Datatypes (GADTs) of the functional programming community.
To my knowledge, this relation has first been established in the 2006
article "Generalized Algebraic Data Types and Object-Oriented
Programming", by Andrew Kennedy and Claudio Russo, that contain
examples that you might find interesting:
  https://www.microsoft.com/en-us/research/publication/generalized-algebraic-data-types-and-object-oriented-programming/

There has been a lot of work on GADTs and their expressiveness in the
functional programming community, and I think that realizing the
connection could be helpful for some further generics language design.

The connection is rather subtle because, while sets of definitions by
cases on algebraic datatypes are known to correspond exactly to sets
of class extensions on a fixed method signature (this is the general
FP/OO duality), the duality do not extend to GADTs and equality
constraints as one could expect. There are simple functional
programming examples that require type parameter constraints to be
expressed in an object-oriented style, and correspondingly some GADTs
that don't need method-level parameter constraints in object-oriented
style. The latter has resulted in some wrong claims in the past that
GADTs are un-necessary in object-oriented languages. See the article
for more details.


(Douglas Gregor) #2

There are some in the Swift community that have a deep interest in and understanding of type theory. However, as a general rule, we try to keep the Swift language—and discussions of its evolution—accessible to everyone. One should not need to have a copy of TAPL on their desk to participate in the discussions here, and if an idea isn’t presented in the context of how it can improve Swift directly (with specific motivating code examples written in Swift), it’s really not relevant to the discussion.

  - Doug

···

On Aug 2, 2016, at 9:36 AM, Gabriel Scherer <gabriel.scherer@gmail.com> wrote:

I'm not familiar with Swift, but happened to find the Generics
Manifesto document at
https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

I wonder if the Swift community is aware of the strong connection
between equalities on generic type parameters of the form "where T ==
Foo" in method or extension declarations, and the Generalized
Algebraic Datatypes (GADTs) of the functional programming community.
To my knowledge, this relation has first been established in the 2006
article "Generalized Algebraic Data Types and Object-Oriented
Programming", by Andrew Kennedy and Claudio Russo, that contain
examples that you might find interesting:
https://www.microsoft.com/en-us/research/publication/generalized-algebraic-data-types-and-object-oriented-programming/

There has been a lot of work on GADTs and their expressiveness in the
functional programming community, and I think that realizing the
connection could be helpful for some further generics language design.