你可能其實不懂繼承 - 什麼是 Covariance 跟 Contravariance

在近代高等程式語言快（ㄏㄨˋ）速（ㄒ一ㄤ）演（ㄔㄠ）化（ㄒㄧˊ）的狀況下，很多 strong type 的程式語言都開始有了 generic 的設計，舉例來說：

（這只是大略分類）

Mobile: Swift, Kotlin
Frontend: Flowtype, TypeScript
後端語言：Python (pyre), Scala, C#, Java （沒錯！現在連 Java 都有）

Generic type 雖然看起來是比較新的東西，但如果要做到嚴格的 strong type 基本上是少不了的。例如 Array/List 如果沒有 generic 的話，只能有兩種做法：

把所有東西都轉成 Object or Any type 才能塞進 List，然後在從 List 取出物件的時候再做 down casting。
針對需要的 object type 個別實作相對應的 List type，例如：Cat 就有 CatList。

第一個方法的問題是：你有可能 down cast 到錯的 type，譬如說你本來塞的是 Cat，但你拿出來後 cast 成 Dog。這樣就會噴 Runtime Error。而第二種方法的確是 type safe ，但因為每個 type 都要重寫一堆邏輯，非常不方便。

現在我們知道 generic 的方便性及重要性了。接下來我們來進入本篇想討論的：Covariance 跟 Contravariance。

基本上， generic 的出現代表了 type system 增加了一個新的維度，碰上有 subtype 的 type system 會變得比平常複雜。偏偏現代幾乎所有程式語言都有 inheritance，所以這變成了現在 programmer 早晚會碰到的問題。我聽到的 case 都幾乎是走「碰到就想辦法繞過」這種解決方式。而個人在工作上也有碰到因為對 generic 一知半解而設計出來得詭異架構。要了解什麼是 covariance ，我們必須先了解 generic 碰上 subtype 會出現什麼樣的問題。不過首先，讓我們先複習一下什麼是 subtype。

什麼是 Subtype、Supertype

從 Java 派 OOP 的角度來說，如果 A 繼承 B ，我們稱 A 為 B 的 subtype，而 B 為 A 為 supertype。但因為我們接下來要理解在 generic 的 context 下怎麼去理解 subtype，所以從語法來看並不是一個很泛用的方法。

比較好的方式應該是使用這個定義：

如果 A 是 B 的 subtype（或 B 是 A 的 supertype），那 B 有的東西、能做的事情，都可以從 A 身上找得到。

例如 Cat 是 Animal 的 subtype，這個很明顯應該不用特別解釋。而 Animal 不是 Cat 的 subtype，其中一個原因是不是所有 Animal 都會喵貓叫。

以下我們用這個 subtype 關係鏈來舉例：

波斯貓 < Cat < Animal
Dog < Animal

現在我們對 subtype 有共識了，接下來我們可以回來看怎麼來解 generic type 的 subtype 關係。其中最經典的：

`List<Cat>` 是不是 `List<Animal>` 的 subtype？

乍看之下答案是「當然是啊，Cat 是 Animal，當然 List<Cat> 就是 List<Animal> 啊」，但實際上並沒有這麼簡單。我們先假設 List<Cat> 是 List<Animal> 這件事情成立好了，這就代表：

List<Cat> listOfCat = // 總之，某個方法生出來的，不是重點所以略過
List<Animal> listOfAnimal = listOfCat;

以上，根據假設沒問題，但接下來的 code 就不合理了：

listOfAnimal.add(new Dog());

光看這一行可能沒問題，但同時考慮前段 code 就能看出錯誤：listOfAnimal 實際上是 listOfCat，而其 type 是 List<Cat>。也就是，你正在把 dog 塞進一個只能放 Cat 的 List，而如果其他地方還持有 listOfCat 的 reference 的話，就有可能拿到 dog，而 dog 不是 cat，當然就是個 type error。

也就是如果一個 list 允許你「塞」值進去的話，那它就不會是 subtype。

既然 List<Cat> 不是 List<Animal> 的 subtype，那

`List<Cat>` 能不能是 `List<Animal>` 的 supertype？

答案是....看情況。

那麼什麼情況下不行呢？

如果你今天試著從 list 拿值出來就不行。

Cat cat = listOfCat.get(0) // 取得 Animal

因為 listOfCat 如果是 listOfAnimal 的 supertype 的話，代表 listOfCat 有可能實際上是 listOfAnimal，也就是你取到的值有可能是 Animal 而不是 Cat，而 Animal 並不是 Cat 的 subtype，於是這邊會產生另外一個 type error。

所以以常識上的通用 List 來說的話，List<Cat> 既不是 List<Animal> 的 subtype 也不是 supertype。

那假設我們想做一個特殊的 List 使得 List<Cat> 是 List<Animal> 的 subtype 呢？

什麼是 Covariance？

假設 A 是 B 的 subtype，那麼 ConstList<A> 就是 ConstList 的 subtype

首先，在上述的例子中我們已經知道如果我們可以「塞」東西進去這個 List ，那就不可能做到「List<Cat> 是 List<Animal> 的 subtype」。所以我們要另外定一個 list 叫做 ConstList，意思是這個 list 是 constant，也就是我們不能改動裡面的值。你可能會問：「既然這個 list 不能塞東西進去，那我要這個 list 幹麻？」，雖然不能塞東西進去，但是你可以在產生這個 list 的時候就把值設定好，例如

ConstList<Cat> list = new ConstList<Cat>(cat1, cat2, cat3);

那麼，我們要怎麼告訴 typechecker 說「假設 A 是 B 的 subtype，那麼 ConstList<A> 就是 ConstList 的 subtype」呢？

以下舉幾個程式語言當例子：

FlowType

class ConstList<+T> { ... }

(其實我本來想要用 TypeScript 說明的，結果一查資料才發現 TypeScript 在這塊實作其實是有問題的 issue 1394）

Kotlin

class ConstList<out T> { ... }

Java

Java 無法在宣告 class 時宣告是否為 covariant，只能在宣告變數時使用。也就是在撰寫的時候要特別小心。某種程度上也是算是 type system 設計上的缺失。

ConstList<? extends Animal> list = new ConstList<Cat>();

以上就是所謂的 Covariance：「假設 A 是 B 的 subtype，那麼 ConstList<A> 就是 ConstList 的 subtype」

什麼是 Contravariance？

假設 A 是 B 的 subtype，那麼 Comparator 就是 Comparator<A> 的 subtype

那麼有沒有反過來「假設 A 是 B 的 subtype，那麼 Comparator 就是 Comparator<A> 的 subtype」的呢？有！它叫做 Contravariance。

當 generic type variable 只出現在 function input 的時候。

例如 Comparator，內含一個 function 可以比較兩個東西的大小，如果前者比較大則輸出大於 0 的數值，如果一樣就輸出 0，比較小則輸出小於零的數值。 Comparator<Animal> 可以比較 Animal 的大小，而 Comparator<Cat> 可以比較 Cat 的大小。然後我們就可以來問一樣的問題：Comparator<Animal> 是不是 Comparator<Cat> 的 subtype？

要來回答個問題，我們要來複習一下什麼是 subtype：「如果 A 是 B 的 subtype，那 B 能做到的事情 A 一定都能做到。」

Comparator<Animal> 可以比較 Animal，而因為 Cat 是 Animal ，所以 Comparator<Animal> 當然也可以比較 Cat。所以 Comparator<Animal> 是 Comparator<Cat> 的 subtype。

光這樣講可能不是很清楚，讓我們先舉個反例，寫成 code 的話就是：

// FlowType
let catComparator: Comparator<Cat> = // ....
let animalComparator: Comparator<Animal> = // ...
animalComparator = catComparator; // 假設 Comparator<Cat> 是 Comparator<Animal> 的 subtype
animalComparator.compare(animal, animal);

乍看之下沒問題，但實際上是拿 Comparator<Cat> 來比較 Animal，方式可能是比較喵喵叫的可愛程度，可是並不是所有 Animal 都會喵喵叫。

與 Covariance 相對應，他們分別的寫法是

FlowType

class Comparator<-T> { ... }

Kotlin

class Comparator<in T> { ... }

Java

一樣，Java 無法在宣告 class 時宣告是否為 contravariant，只能在宣告變數時使用。

Comparator<? super Cat> list = new Comparator<Animal>();

Exercise

如果熟悉 FlowType 的話，這邊有一道題：

為什麼以下 FlowType 程式不能 typechecked？如何修改呢？

// FlowType
const a: 1 = 1
const b: number = a

const c: { [string]: 1 } = { 'a': 1 }
const d: { [string]: number } = c;

Subtype Function?

其實沒有 generic 也有可能碰到 variance 問題。例如：

請問 function Cat => void 是不是 function Animal => void 的 subtype?

奇技淫巧

上面提到，如果可以「塞」東西進去的 generic type 就不能可能是 covariant，這看起來有點像 immutable，所以有些人會以為寫上 covariant 等於宣告了 immutable data type。的確在某些狀況下是可以這麼做的，例如上面的 flowtype 練習題。但這並不全然是對的，因為它其實只描述了 subtyping 的關係，而不是 immutability。

那麼在什麼樣的情況下不能當 immutable 呢？

// FlowType
type Cat = { name: string }
const cat: Cat = { name: 'Kitty' }
const boxedValue: { +cat: Cat } = { cat }
boxedValue.cat.name = 'Cookie'

其實跟 const (or val in Kotlin, Scala, etc) 一樣，他只限制了你不能改這個 reference，但並沒有限制你不能改這個 value 裡面的內容。

小結

在查找資料後才發現原來到今天為止，號稱 strong type 並有支援 generic 的語言有部分並沒有完善支援，例如 Java 沒有提供語法可以在宣告 generic type 的時候描述 variance，TypeScript 也是類似狀況。而 Swift 則沒有支援 variance 語法，奇怪的是 Objective C 有。

因為 generic 會讓 subtyping check 變複雜，如果不用繼承，就能減少 subtyping 造成的 variance 問題。但是是不是沒有 subtyping 就完全沒有 variance 的問題呢？答案是否定的，有興趣的朋友可以了解一下 Functor 跟 Contravariant Functor。

希望這篇文章可以幫助你更好地理解 subtyping （繼承）而能更容易地設計出良好的架構。

最後謝謝 @wu_ct 跟 @_cybai 的 review

rayshih/understand_subtyping_variance.md