本稿は Swift Tweets 2017 Summer で発表（ツイート）したものをまとめ、Qiita 用に追記・再構成したものです。
当日のツイート全体像は 2017/7/22 #swtws Swift Tweets 2017 Summer - Togetterまとめを見ると良いかと思います。

はじめに

本稿は、2月のtry!Swiftリジェクトコンで発表したnominal typeについての話の発展的内容です。
とはいえご安心ください。前提知識がなくても、この記事だけで大丈夫な形で構成してます！

本稿では、nominal typeを名前的型、structural typeを構造的型と呼称します。

名前的/構造的型システムとは

名前的/構造的型システムとは何なのか。その真相を明らかにすべく我々はAmazonへと向かった。
参照したのは、「入門」という書名の印象に反して歯応えのある鈍器と名高い「型システム入門」です。
以下、「型システム入門」を、TaPLと呼称します。原題が Types And Programming Languages なので。

TaPLによれば、名前的型システムと構造的型システムの違いは「型名の立ち位置」の違いです。
Javaをはじめ、C++やSwiftなどで用いられる「名前的」な型システムの中では、複合的な型は「裸」の型を書くことができず、すべて名前を伴って型宣言されます。新しい名前が導入されるときには、どのクラスやインタフェースを継承するのかをプログラマが明示的に宣言し、その部分型（継承）関係をコンパイラに保証させます。明示されていなければ、たとえ構造が同じであっても部分型とは見做されません。

一方、 ~~Haskell~~ (7/24追記 Haskellを構造的型システムの例として挙げるのは不適切でした )、 ML系言語などでは構造的型システムが用いられます。そこでは型名はただのエイリアスであり、構造を同じくする「裸」の型はすべての文脈で相互に置き換え可能です。

Swiftの世界での、名前的型・構造的型

Swiftの型にはnamed typeとcompound typeがあります。
named type には class, struct, enum, protocol が、compound type には tuple や function が属しています。
…えーと、文章より図示したいですね。横着して他人様にリンクしますと、こんな感じ。

あらためて Swift の Type をまとめてみた。名前は公式ドキュメントの記述に準拠して書いた。
説明するとき「あの、associated value 持ちの enum…」って言うのはやめさ ( ˘ω˘) #swift pic.twitter.com/1l3DcmXEuI
— ezura (@eduraaa) 2017年7月16日

named/compound type, nominal/structural type と微妙に違う名前をしていますが、これらは同じ名前的型/構造的型を示すと思ってよさそうです。
そう。Swiftの世界は、名前的型システムと構造的型システムが混合した世界なのです。
そんな混合言語のSwiftで名前的型(struct)/構造的型(タプル)の違いを表現しました。ご覧下さい。

tuple_vs_struct.swift

do {
    // タプルは構造的型
    typealias A = (
        int: Int,
        string: String
    )
    typealias B = (
        int: Int,
        string: String
    )
    func handle(a: A) { print(a) }

    handle(a: A(int: 1, string: "Aだよ")) // (int: 1, string: "Aだよ")
    handle(a: B(int: 1, string: "Bだよ")) // (int: 1, string: "Bだよ")
    // tuple Aを引数に受ける関数が、Bを受け付けてしまう！
}

do {
    // structは名前的型
    struct A {
        let int: Int
        let string: String
    }
    struct B {
        let int: Int
        let string: String
    }
    func handle(a: A) { print(a) }

    handle(a: A(int: 1, string: "Aだよ")) // A #1(int: 1, string: "Aだよ")
    handle(a: B(int: 1, string: "Bだよ"))
    // ↑ error: cannot convert value of type 'B' to expected argument type 'A'
    // struct Aを引数に受ける関数は、Bを弾いてくれた！
}

構造的型システムにおいてはAとBを混同してしまいますが、名前的型システムはAとBを区別できています。

Swiftで名前的型にしかextensionを書けない理由

2月の発表の主題は、特定の型にextensionを書こうとした時に発生するコンパイルエラー、 Non-nominal type '***' cannot be extended のエラーメッセージが示すように、名前的型でなければextensionを書けないのは何故か？を探ることでした。その結論は、名前的型は構造的型と比べて、意図しない型の同一視を防ぐために有用だから。
確かに、タプルAの処理を拡張したのに、同じ構造のタプルBにも同じ処理が生えてしまったら大変ですからね。
型安全性を言語の特徴として押し出しているSwiftらしいなと、大層納得しました。

構造的型の利点、名前的型の欠点

…が、逆にそうすると、構造的型システムは名前的型システムに比べてどのような利点があるのでしょうか。関数やタプルが名前的型ではなく、構造的型である理由とは一体？
TaPLに挙げられている、構造的型システムに対する名前的型システムの欠点を見てみましょう。 ¹

整然・洗練されていない。型名とその定義について大域的情報を常に扱わなければならず冗長
型抽象に関する強力な仕組みと相性が良くない

名前的型の欠点①整然・洗練されていない。型名とその定義について大域的情報を常に扱わなければならず冗長

実務の観点からは「洗練とか冗長とか知ったことか、動きゃいいんだよ！」と言いたくなりますか？　いや、落ち着いてください。明確にデメリットあるんですよ。
もし関数が名前的型だった場合を考えてみましょう。先程の、タプルとstructの比較コードでは名前的型の便利さを実感できます。
しかし、~~もし関数が名前的型だった場合の擬似的コードはこうです。わかりますよね。これはアカン…。~~

このブロック、Qiitafyにともなう追記。

これはNominalの問題じゃなく構文の問題かもですね。JavaはNominalだけどラムダ式で書けますし。 #swtws
— koher (@koher) 2017年7月23日

とtwitterで指摘いただきましたがその通りで、リンクしたサンプルコードの発想は根本的に間違っていました。
ここではむしろ、名前的型システムで関数を扱っている例として、Javaのラムダ式を挙げるのが適切でした。
Javaのラムダ式の正体は、関数型インタフェースを継承する匿名クラス。抽象メソッドひとつをフィールドに持っています。匿名クラスの型名は内部的に扱われ、プログラマには意識させないようになっていますが、しくみとしては名前的型システムに基づいています。

import java.util.function.IntConsumer;

class Playground {
    public static void main(String[] args) {
        IntConsumer consumer = v -> System.out.println(v);
        System.out.println(consumer); // Playground$$Lambda$1/834600351@548c4f57
    }
}

関数型インタフェースの一覧を見てみると、その種類の多さや、さらにはジェネリクスも混じっているのを見ることに圧倒されます。筆者にはちゃんとした Java8 の利用経験がないのでしっかりは言えませんが、たしかにこれは冗長と言いたくなるし、名前的型システムの世界観で関数型の型付けを行う苦労が偲ばれるなあと思いました。

追記おわり。

そして関数が構造的型であるならば、タプルも構造的型であるというのも必然ですね。
…え、論理の繋がりがわからないって？　わかりました、細かく説明しましょう。
(Swiftの)関数型は、3つの要素によって構築されています。

引数は、普通に考えてひとつとは限りません。
なのに全関数が (parameter type) -> return type という形で表現できるのは何故か。それはタプルの力です。
関数に与えられる 0...n 個の引数・戻り値を一般化するため、タプルが活躍しています。
タプルが関数の構成要素になっていること、Swiftのコードで確認してみましょうか。

tuple_in_function.swift

struct Hoge<Parameter, Return> {
    let f: (Parameter) -> Return
}

func doSomething(arg1: Int, arg2: String) {
}

// func doSomething をジェネリックな型に渡して、引数の型と戻り値の型をチェック
let hoge = Hoge(f: doSomething) // Hoge<(Int, String), ()>
// つまり、
// 　Parameter: (Int, String)
// 　Return: ()
//　 　※doSomethingの戻り値は「ない」のではなく「Void = 空タプル」

関数の構成要素としてタプルがあることが、おわかりいただけたでしょうか。
よって、関数型が構造的型であるならば、タプルも構造的型である、という結論に繋がるのです。

部分型付け

名前的型システムと構造的型システムの大きな違い、部分型関係（サブタイピング）の話もしましょう。
Swiftで言えば、親クラスを継承したサブクラスであったり、プロトコルに適合する具体型であったり。型理論ではそれらを上位型と部分型と表現します。

規則 S-RcdDepth

複数のフィールドを持つ型において、部分型関係は次のような規則を持つ、とTaPLは述べています。²

なんか変な図がでてきたって？
大丈夫、ｺﾜｸﾅｲﾖｰ。部分型関係を <: という記号で表現しており、線分の上が前提、線分の下が結論です。
つまり、この図は
各 i に対して、 S_i で記述されるすべての値が T_i で記述されるならば、
型S( S₁ から S_n の n 個の項からなる組 )内のラベル l_i は、
型T( T₁ から T_n の n 個の項からなる組 )内のラベル l_i の部分型である
と読みます。
Swiftのコードで確かめてみましょう。

tuple.swift

class 動物 {}
class 人間: 動物 {}
class オレ: 人間 {}

var t: (人間, Int)? = nil

t = (オレ(), 1)
// オレ は 人間 の部分型。 (オレ, Int) も (人間, Int) の部分型

t = (人間(), 1)
// (人間, Int) ≡ (人間, Int)

t = (動物(), 1)
// error: cannot assign value of type '(動物, Int)' to type '(人間, Int)?'
// 動物 は 人間 の上位型。 (動物, Int) も (人間, Int) の上位型

たしかにタプルの部分型関係は、この規則S-RcdDepthによって成立しているようです。

規則 S-Arrow

TaPLはまた、関数型には部分型関係について画像のような型付け規則(S-Arrow)があると述べています。 ³

前提（線の上の部分）で、引数の型に対して部分型関係の向きが反転しています（これを反変といいます）。一方、戻り値の型は関数型自身と同じ向きになっています（これは共変といいます）。
Swiftで書くと、こんな感じ。

covariant.swift

class 動物 {}
class 人間: 動物 {}
class オレ: 人間 {}

func 人間to人間(_ p: 人間) -> 人間 { return 人間() }
func 人間to動物(_ p: 人間) -> 動物 { return 動物() }
func 人間toオレ(_ p: 人間) -> オレ { return オレ() }
func 動物to人間(_ p: 動物) -> 人間 { return 人間() }
func オレto人間(_ p: オレ) -> 人間 { return 人間() }

var f: ((人間) -> 人間) = 人間to人間

// 戻り値は共変
f = 人間toオレ(_:) // ((人間) -> 人間) <: ((人間) -> オレ)
// (人間)->人間 の戻り値として、部分型であるオレを受けられる

f = 人間to動物(_:)
// ↑error: cannot assign value of type '(人間) -> 動物' to type '(人間) -> 人間'
// (人間)->人間 の戻り値として、上位型である動物は受けられない


// 引数は反変
f = 動物to人間(_:) // ((人間) -> 人間) <: ((動物) -> 人間)
// (人間)->人間 の引数に、上位型である動物が渡せる。

f = オレto人間(_:)
// ↑error: cannot assign value of type '(オレ) -> 人間' to type '(人間) -> 人間'
// (人間)->人間 の引数に、部分型であるオレは渡せない。

もちろん、規則S-RcdDepthとS-Arrowは組み合わせることも可能です。

covariant_tuple_and_func.swift

class 動物 {}
class 人間: 動物 {}
class オレ: 人間 {}

func 人間🔢to人間🔢(_ p: 人間, dummy: Int) -> (人間, Int) { return (人間(), 1) }
func 人間🔢to動物🔢(_ p: 人間, dummy: Int) -> (動物, Int) { return (動物(), 1) }
func 人間🔢toオレ🔢(_ p: 人間, dummy: Int) -> (オレ, Int) { return (オレ(), 1) }
func 動物🔢to人間🔢(_ p: 動物, dummy: Int) -> (人間, Int) { return (人間(), 1) }
func オレ🔢to人間🔢(_ p: オレ, dummy: Int) -> (人間, Int) { return (人間(), 1) }

var f: ((人間, Int) -> (人間, Int)) = 人間🔢to人間🔢

f = 動物🔢to人間🔢(_:dummy:)
// ((人間, Int) -> (人間, Int)) <: ((動物, Int) -> (人間, Int))

f = 人間🔢toオレ🔢(_:dummy:)
// ((人間, Int) -> (人間, Int)) <: ((人間, Int) -> (オレ, Int))

このように、構造的型システムでは、部分型は包摂関係から推測できます。
一方、名前的型システムでは先述したように、部分型関係を明示しないと部分型として扱われません。ということは、もし関数型が名前的型だった場合、取りうるサブタイプの数だけインタフェースを用意する必要がある。しかも引数と戻り値の数の掛け合わせで、その数は増えていく。
その結果がJavaの関数型インタフェースのプリミティブ型に対するインタフェースの多さというわけですね！

import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;

class Playground {
    public static void main(String[] args) {
        List<Number> numbers = Arrays.asList(1, 1.5);
        Consumer<Number> consumer = v -> System.out.println(v);
        // int, double が混ざるだけでも名前的型の世界だけでは収まりきらず、ジェネリクスの力を借りる必要がある
        numbers.forEach(consumer);
    }
}

　もしジェネリクスがなかったら、無限にインタフェースを書かなきゃいけないし、そこでは共変・反変の関係もプログラマの手によって明示する必要がある（…のだと思いますが、筆者には知見がないためもし見当違いでしたらご指摘ください）。
それを避け、関数の共変・反変関係をシンプルに導くためにも、関数型・タプル型は構造的型であるほうが望ましいのです。

名前的型の欠点②型抽象に関する強力な仕組みと相性が良くない

名前的型の、もうひとつの欠点の話に入りましょう。
これ、要は Hoge<T> のような記述はどう見ても名前的というよりは構造的だよねという話です。
Hoge<T> は、原子的な名前として扱うことはできません。Hogeは複数の型を抽象的に取り扱っています。

「総称的（注: ジェネリクス）」機能の拡張(…)を施したものは、もはや純粋な名前的型システムではなく、ふたつのアプローチの少々複雑なハイブリッドである ⁴

確かに、具体型のジェネリックな型パラメータであれ、プロトコルのassociatedtypeであれ、そこで用いられる論理は構造的型システムに似たものになります。それが、名前的型システムで表現できる世界の限界ということです。
なお、本発表で触れた構造的型システムの論理体系は、型の項を量化する「単純型付きラムダ計算」というものですが、型抽象を実現する論理体系 System F は、そこに加えて型を量化する「二階ラムダ計算」とも呼ばれるものだそうです。
名前的型システムで表現できない型抽象に関する仕組みとして、TaPLでは次のようなものが紹介されていました。

パラメータ多相
抽象データ型
ユーザ定義の型演算子
ファンクタ

こういった型抽象の世界では、構造的型システムを採用している言語（OCaml, Haskellなど）の知見の多くがSwiftでも適用できそうです。
…正直、今深入りして解説しても火傷する気しかしないので、ここでは、先日開催されたジェネリクス勉強会の資料などを参照すると理解が深まりましたので興味ありましたら、という紹介のみに留めます。

おわりに

以上、Swiftにおける構造的型システムの世界を、TaPLの力を借りながらご紹介しました。
広範にわたるTaPLの内容を理解しきれている自信がないので、もし何か不正確な話をしていることにお気づきでしたら、ご指摘いただけると幸いです。
それでは、御Tweet聴ありがとうございました。

型システム入門 P198 ↩
型システム入門 P142 ↩
型システム入門 P144 ↩
型システム入門 P198 ↩

Swiftに息づくstructural types(構造的型)