scala type system (0) unit, top, bottom, and null

這算是我最喜歡 scala 的部份，所以想試著解釋這些東西。
以下假設讀者有基本的 object-oriented programming 概念，
或是有基本的 Java/C++ 的 OOP 經驗。怎麼樣算是基本的 OOP 概念？
只要知道 virtual function, dynamic binding 就行了。
嗯，dynamic dispatch 似乎也是類似的意思。
總之大概就是這些概念，名詞混亂也不是一天兩天的事了，別在意...

-

先看最簡單的 top (⊤)
簡單地說，就是 Java 裡的 Object, Ruby 裡的 BasicObject (1.9),
Object (1.8). 在 Scala 裡則是 Any.
在 C++ 中，基本上沒有這種東西，真要說的話，void* 勉強算是
pointer 裡面的 top. 然而 void 本身跟 top 無關，卻是 unit.
這邊先不談 unit, 因為他的概念雖然簡單，有些時候卻容易混淆。

之所以叫做 top, 因為他是整個 type system 中最上層的 class (type)[0],
也是最「大」的一個 type[1], 也就是說如果能夠比較大小的話，
top 比任何的 type 都大，因為他假設最少，可能的值最多。
任何一個值(value)都屬於(classified by) top.

在 Ruby 中，也把繼承(subclass, extends, inheritance, whatever)
寫成 class Derived < Base; 當然這並不見得是在表達大小，
然而 Fixnum < Object 卻真的是 true, 表示 Fixnum 是 Object 的
subclass, 也是在說 Fixnum.ancestors 中，Fixnum 會在 Object 的
前面。以下是 Fixnum 的線性繼承體系，最上層(top)就是 BasicObject.
=> [Fixnum, Integer, Numeric, Comparable, Object, Kernel, BasicObject]

而在 Java 裡，當我們說:

Object obj = new String();

意思是 String 是一種 Object, 如果我們所需要的 value 是一種
Object 的話，事實上並不需要關心實際的 value 是什麼，只要他能夠
被 Object classified, 也就是說所有 Object 該有的性質，
String 都有的話，那就不需要關心實際上確實是什麼東西。
同時這表示如果違反 LSP, 就是違反了這樣的「性質」。
使得實際上在 type system 中比較大的 type, 並不是真的比較大。
很可能他們本身並沒有實際的關聯，不是上下關係，而是左右關係。

-

接下來看 unit, 也就是一個什麼東西都沒有的 singleton pattern
中的 singleton. 在 Haskell 和 Scala 中，都寫成 ()
以 C++ 來看，大概可以寫成:

struct Unit{
  static Unit const& unit() const{
    static Unit unit; return unit;
  }
};

這樣的東西看起來一點意義都沒有，不過如果沒有他，type system
就會變得不完整。比方說 function 一定是一個會回傳某個值的東西，
但有時候我們在具有 side-effect 的 function 中，並不在乎
回傳的東西是什麼，因為我們已經在 side-effect 中達到目的了。

printf("Hello, World!");

當然 printf 可以有回傳，例如一個整數表示實際上 output 了幾個
character. 但大部份的情況下並不在乎這種事。這時候在 C/C++/Java
中往往會把 return type 寫作 void, 表示這個 function 沒有
return value. 但這樣使得 function 本身存在一種特例，並不是一件好事。
我們會希望一個系統能盡量簡單，盡量一致，減少例外，才會一個漂亮好看的系統。
也不需要「背」太多例外。

因此可以把 void 看成是 unit. 這點就是讓人混淆之處了，
void 是虛無的意思，但是 unit 卻是某個東西的意思。
在用到 unit 的 programming language 中，我們不會用 void
表示沒有 return value, 而是用 unit. 因為得到 unit
就表示我們得到了一個沒有用的東西，也就是說，我們關心的事，
在這個 function call 裡的 side-effect 就已經處理了。

而在 C/C++/Java 裡，我們有時候也會在 return type 是 void 的
function 中寫 return; 這又表示什麼？？我剛學的時候，
真的覺得很混淆，不是說沒有 return, 那這 return 是 return 什麼？
如果這邊不是用 void, 而是用 unit 的話，那就很清楚了。
事實上 return; 就是 return unit; 的意思。
可以把 return; 想成是 return Unit::unit(); 的縮寫。

當我們有一個 type 的洞在那裡，不知道要填什麼進去時，就選 unit 吧。

-

here comes the dragon. 最抽象難懂的 bottom (⊥).
相對於 top, bottom 是最小的 type, 位於繼承體系的最下端，
是所有 class 的 subclass, 他的 value(instance) 會擁有所有
其他 class 的所有東西––而這樣的東西並不存在。

因此在 Scala 中，bottom 叫做 Nothing.
我們會用 Nothing 來表達一個 function 真的不會 "return",
因為 bottom 並沒有一個值，因此不可能找到一個值真的去 return.
這跟 void 是完全不一樣的，void 只是說我們對那個 return value
不感興趣，但他還是會 return, 程式還是正常在執行。
那什麼時候真的沒有一個 return value?

1. exception 發生了。這時我們絕不會說這個 function 真的
"return" 了，因為這是某種形式的 goto. 這邊不多討論 exception.

2. 這個 function block 住，永遠結束不了。
例如裡面有無限迴圈，或是無窮遞迴。

在這兩種情況下，我們都會說這個 function 實際上還是 return 了
一個東西，而這個東西其實是 "bottom", 所有 type 的 subtype.

考慮一個 Java method:

String toString(){ ... }

因為 halting problem, 我們無法驗證 toString 到底會不會
terminate, 因此實際上這個 String 是有可能永遠不會 terminate,
也就是說他有可能會回傳 "bottom". 那要怎麼讓這個式子合法？

答案就是因為 Nothing 是所有 class 的 subclass,
那 bottom 這個不存在的 value, 當然也是 String 的一種 instance.
就像是這邊 toString 其實是回傳 SuperString 的 instance,
都是 String 的 subclass 的 instance.

同時因為 Nothing 是所有 class 的 subclass,
也意味著所有的 function/method 都有可能永遠不會 terminate,
或是遭遇 exception, 也就是都有可能回傳 bottom.
bottom 之所以抽象難懂，是因為他不存在，不是一個具體的東西。
反之 unit 則是具有唯一的值，是非常具體的。

另一方面，在 Haskell 中有 undefined, 很類似 bottom,
只要 runtime 一看到 undefined, 程式就會壞掉。
所以可以用 undefined 來表示 bottom, 反正 bottom
也表示著永遠不會真的碰到的東西。

-

事實上在 Java/Scala 中，除了上述的 bottom 外，
還有一個可能會在任意 function/method 中回傳的值，
那就是 null. 在 Java 中，其實這樣寫是很怪的:

Cat cat = null;

為什麼 Cat 可以指向 null? 在單純的 OOP 中無法解釋，
這只能當做是一種例外。但如果 null 的 type 是 Null,
而且他也是所有 class 的 subclass 呢？那麼 null 本身
當然也是任何 class 的 instance, 也可能會被任何
function return 出來––除了 return type 是 bottom 的以外。

Nothing this_is_a_function_never_returns();

由於這邊也不允許 null 被 return, 所以 Null 並不是真的
所有 class 的 subclass, 他在 Nothing 之上，
其他所有的 class 之下。以 Scala 為例，大概是長這樣:

  Any
 / | \
A  B  C
 \ | /
 Null
   |
Nothing

箭頭不方便畫，總之大家都知道方向。這在數學上大概就是
partially ordered set, 簡稱 poset.
提這個其實沒有特別的意義，只是想說如果能在數學找到可以對應的東西，
就能拿在數學上有嚴謹定義，並推導出來的性質來用。我們本來就是透過
尋找相似的東西，來推論出不熟悉的東西，可能會有什麼樣的外在與內在。
就像我們看到人，就會拿過去認識的人的經驗，來判斷這個人有什麼可能性。
而我們怎麼知道我們看到的是人？當然也是根據過去對人的認識來推論的...

扯遠了。所以 Null 有個唯一的值，也就是 null, 跟 unit 一樣是個
singleton. 不一樣的地方在於，unit 就只是 unit, 硬要說，
他只繼承了 top, 是 top 的 subtype, 沒有其他性質了。

Cat cat = null;
cat.sleep();

這邊第二行應該會有 null pointer exception,
但當初 compile 為什麼能過？因為 null 也是 Cat 的 instance,
所以 Cat 擁有的 method, null 當然也有。
而造成的 null pointer exception,
表示 Null override 了 Cat 的 sleep method,
而實作的內容就是很單純地丟出一個 null pointer exception.

我們可以說 null 擁有所有的 method, 但是這所有的 method,
實際上只有一個實作，就是 throw null pointer exception.
在 Ruby 中，這件事非常容易做，就是在 NilClass (nil(null)
的 class) 上實作 method_missing, 在裡面 raise nil pointer
exception 就行了。但在 Ruby 裡不會這樣做，因為他不是
static typing 的語言，因此不會刻意去遵守這樣的規則。

就算 Java 本身並沒有 Null, 也沒有所有 class 的 subclass 的
概念，在 JVM 底層倒是可以考慮用這種想法去實作。儘管我不知道
實際上有沒有 JVM 用這種概念去做。至少 Scala 本身是用這種概念。
或是說這本來就是 high level 的概念，VM 本身不需要知道這種事。

-

下集講 covariant and contravariant,
Scala 的 List[Nothing] 和 Function1[-T, +R]

-

[0]
這邊有時候 class 跟 type 混著講，因為在 OOP 中，
class 也是一種 type. (duck typing 例外),
因此有時候講 subclass 和 subtype 的意思是一樣的。
老實說，在口語中要講得很精確，真的是不容易...

[1]
Ordered Sets