What have you found for these years?

2010-05-02

scala type system (1) covariance and contravariance

covariance and contravariance
那麼當我們說以下,又是什麼意思?

Animal animal = new Cat();

這其實就是 covariant, 意思是當我們要的是某一個 type (Animal) 時,
我們能夠給他一個相等於這個 type (Animal) 的東西,或是比之更小的
type (Cat). 就是假設這邊我們可以寫:

A a = new B();

則可以得知 B <= A

反過來說,contravariant 就是當我們要某一個 type, 假設是 Cat,
我們必須給他一個大於等於 Cat 的 type, 就是 Cat 或 Animal.
這邊比較抽象一點,因為在 Java 裡面,可能看不到這樣的東西。
我不確定有沒有,因為沒有很熟悉 Java. 但在 C++ 裡,好像也沒有?
Scala 裡則很明確告訴你有這樣東西。我們可以簡單歸納成,
在 return type 裡,可以存在 covariance, 而在 parameter type
裡,則可以存在 contravariance.

在上面的例子就是 new Cat() 本身可以當成一種 function,
是一個 Unit -> Cat 的 function. 而前面寫 Animal animal =
則是表示我們要一個 Animal.

在 Ruby 裡,可以很明確看成是一種 function, 因為我們會寫成這樣:

animal = Cat.new

在 Scala 裡,如果 Cat 是一種 case class 的話,也可以寫成:

val animal:Animal = Cat()

我會建議盡量用這種形式來寫,避免使用 new operator,
這樣才比較像是 functional programming. Python 也是直接用 Cat()

-

那麼哪裡會有 contravariance 呢?在這之前,先把其他 covariance 的例子看完。
另外還有兩個例子,其中一個是具有 covariant return type 的 method,
是否能夠具備 override 原本 method 的資格?考慮以下:

Animal popup(){ return new Dog(); }
Cat popup(){ return new Cat(); }

第二個 method 是否能夠 override 第一個 method?
在 C++ 和 Java 1.5+ 的答案是可以的。在 Java 1.4- 則不行。
可以這樣做的原因也非常簡單,就跟 Animal animal = new Cat() 的
理由完全相同。考慮以下:

class Ground{ Animal popup(); }
class Grass extends Ground{ Cat popup(); }

Animal animal = ground.popup();

無論那個 ground 的實際 class 是 Ground 或是 Grass,
反正 popup() return 回來的一定是 T <= Animal,
那麼是否真的是 Animal 有關係嗎?因此 overriding method
的 return type 可以是 covariant. 而這樣有個好處,
當你很清楚你在使用 grass 時,就可以獲得 cat 的能力,
而不會受限於 Ground 對 Cat 一無所知。

Cat cat = grass.popup();

-

第三個 covariance 的例子是,如果我們有一個 list of animal 的
pointer/reference/variable, 他可以指向 list of cat 嗎?

ArrayList<Animal> animals = new ArrayList<Cat>();
animals.add(new Cat());
animals.get(0).sleep();

可乎?在 Java 裡不行,但在 Scala 裡面可以。先不談為什麼可以,
先看為什麼這樣做沒關係?在 ArrayList<Animal> 裡,type parameter 是 Animal,
意味著在 add 時我們是用 Animal 去接受 Cat, 這邊是 covariant,
就算在 Java 裡也是可以。然而 get 時,這時得到的也是 Animal,
因為 animals 的知識僅止於 ArrayList<Animal>.
那麼我們當然可以把 Cat 當成 Animal 來用,不是嗎?那為什麼要禁止:

ArrayList<Animal> animals = new ArrayList<Cat>();

呢?那又要怎麼讓這樣的作法也同樣符合 covariance 的規則?
那就是如果 Cat 是 Animal 的 subclass, 那 ArrayList<Cat> 也
應該要是 ArrayList<Animal> 的 subclass.
這在 Scala 裡,是這樣定義:

class List[+T]

如果這邊只寫 T, 那表示這是 invariant 關係,跟 Java 一模一樣。
但如果這邊是寫 +T, 那就表示如果有一個 type 叫 U,
而 T 跟 U 的關係是 T < U, 則可以得到 List[T] < List[U]
Cat < Animal, 因此 List[Cat] < List[Animal],
也因此以下是合法的:

val animals: List[Animal] = List[Cat]()

反過來說,contravariance 就是 -T 了。
如果有 Something[-T], 且 T < U, 則:
Something[U] < Something[T]
這個乍看之下很不合理,且聽我娓娓道來....

-

先整理一下有哪些地方會發生 covariance.
1. LHS, left hand side (等號左邊)
2. overriding method return type
3. type parameter (generic)

contravariance 比較少見,大概只有上面的 2~3 這兩個例子,
只是 2 要把 return type 改成 parameter type, 也就是:

2. overriding method parameter type
3. type parameter (generic)

然而 2 就算在 Scala 裡面也是不能用的,我不清楚原因,
或許作者覺得加這個下去會使得程式變得過分複雜,
也使得 overloading (ad-hoc polymorphism) 變得比較弱。

考慮以下的例子:

AnimalUtil:
Int mood(Cat cat){ return cat.life() + cat.mana(); }

DerivedAnimalUtil:
Int mood(Animal animal){ return animal.life(); }

別在意名稱,一時想不到要叫什麼,隨便亂打的。問題是下面的 method
是否可以 override 上面的 method? 考慮我們什麼時候會需要
virtual function:

AnimalUtil util = new DerivedAnimalUtil();
util.mood(cat);

這邊無論如何,因為 AnimalUtil 的 mood 的 parameter type 是 Cat,
一定得傳一個 cat 進去。那麼就算 mood 實際上是呼叫到 DerivedAnimalUtil 的
mood, 其 parameter type 是 Animal, 那麼就只是在做這件事而已:

Animal animal = cat;

然後在 mood 裡面就把 cat 當成 animal 來用。
因此我們可以說,對於 parameter type, 我們可以利用 contravariance.
也就是說,隨著 T 變小,return type 可以一起變小,
而 parameter type 則可以變大。這也是為什麼 Scala 裡的
Function1 的定義是 Function1[-T, +R].

至於為什麼 parameter type 不能是 covariant 的?
考慮以下例子,把上面的例子反過來:

AnimalUtil:
Int mood(Animal animal){ return animal.life(); }

DerivedAnimalUtil:
Int mood(Cat cat){ return cat.life() + cat.mana(); }

可否讓下面的 method 去 override 上面的 method?

AnimalUtil util = new DerivedAnimalUtil();
util.mood(new Dog()); // BOOM!!

由於 AnimalUtil 是吃 Animal, 把 Dog 傳進去當然合理了。
但 DerivedAnimalUtil 卻是要吃 Cat, 這樣就爆炸了。

-

在 Scala 裡,這種 parameter type 是 contravariant 的 overriding,
實際上是不能用的。因此在 Scala 裡,真正會看到 contravariance 的地方,
只有上面提到的 3. type parameter (generic), 也就是上面提到的
Function1[-T, +R]

這個狀況大概可以用這個例子表達:

val f: Function1[Null, Any] = (any: Any) => null
f(null) // => null

就是說我們要的 function 是 Null -> Any,
但是實際上指到的 function 卻是 Any -> Null, 這是合法的。
先假設左邊的 type 是 T = Null -> Any
再假設右邊的 type 是 U = Any -> Null
那麼如果我們能寫 T = U, 則表示 U <= T

假設以下縮寫:
T 的 parameter type 是 PT (Null)
U 的 parameter type 是 PU (Any)
T 的 return type 是 RT (Any)
U 的 return type 是 RU (Null)

再根據 return type 是 covariant, parameter type 是 contravariant,
則可推論:

U <= T
PU >= PT
RU <= RT

代回這邊的例子,則得到:

Function1[Any, Null] <= Function1[Null, Any]
Any >= Null
Null <= Any

可以發現確實是對的。也就是說,Function1[Any, Null] 是
Function1[Null, Any] 的 subclass.
parameter type 變小了,而 return type 則變大了。
正好就可以看出是 Function1[-T, +R]

f 是一個只能吃一個 null 的 function, 他會回傳 any
而實際上的 function 是吃 any, 但 null 當然屬於 any,
所以沒問題。而回傳了 null 回去,null 也是一種 any, 也沒問題。
因此實際呼叫:

f(null)

就會給一個 null, 對兩邊而言,都是完全 type check 的。
無論我們要吃什麼 argument, 都有可能會吃到 null,
簡單地說就是這麼一回事了。在 Java 裡這件事叫做例外,
在 Scala 裡,這件事則可以被一般的 typing rule 說明,不需要例外。

雖然說在 Scala 裡是這樣哩...

null.isInstanceOf[String] // => false

也許現實並沒辦法做到這麼理想吧? XD
倒是可以這樣做:

null.asInstanceOf[String] // a String, but the value is null

-

[全劇終]

0 retries:

Post a Comment

Note: Only a member of this blog may post a comment.



All texts are licensed under CC Attribution 3.0