William Cook 談物件導向與抽象資料型別

我一直搞不懂物件導向,也不認為我有資格談物件導向。今天從 Lambda the Ultimate 上看到了 William Cook 在 OOPSLA 09 的文章 On Understanding Data Abstraction, Revisited,一下子覺得學到了不少。推薦這篇文章給大家看。

標題是延續 Luca CardelliPeter Wegner 有名的論文 On Understanding Types, Data Abstraction, and Polymorphism. 自從 1985 年發表以來,該論文啟發了許多關於物件導向的語意和型別理論的研究。但雖然廿五年過去了,Cook 說,我們對於抽象資料型別(abstract data type)物件(objects)這兩種達到資料抽象化的方法仍有普遍的誤解:

過去廿年中我問過很多電腦科學家,「物件和抽象資料型別有什麼關係?」我通常在晚餐或喝酒的時候問,典型的回答大約是「物件是一種抽象資料型別。」很多程式語言課本也這麼說。

所以這有什麼好問呢?書上不是都寫了嗎?

我想指出的就是這些書都錯了!物件和抽象資料型別是不一樣的東西,前者不是後者的一種,反之也不成立。

每次聊起這個話題時,我總喜歡一直提出問題促使大家思考。通常討論總是很踴躍,因為大部分的概念在文件中都收錄得好好的,大家也已知道所有的基本知識。有趣的是大家對這些事實指向的結論卻知道得不多。

所以到底他們有什麼不同?Cook 說,抽象資料型別與物件各自可回溯到數學中兩種抽象地描述集合的方法:代數 (algebra), 與特徵函數 (characteristic function).

一個抽象資料型別有個內部資料結構和一些操作函數。使用者只知該型別的名字,內部的實作方法是隱藏起來的。這種抽象化讓我們能輕易抽換一個型別的實作方式。但在同一個程式中,一個型別原則上只有一種實作法。兩種以上不同的實作很難共同操作 — 例如兩個集合的實作若不同,除非在抽象化上做些妥協,很難寫一個函數算他們的交集。

從型別理論的角度看,抽象資料型別可以用既存型別 (existential type) 描述。既存型別是 universal type 的對偶,而後者是參數化多型 (parametric polymorphism) 的理論基礎。大家自然覺得,談到資料抽象化,這當然是唯一方案了。可能因為這樣,許多人誤以為物件也是抽象資料型別的一種。

但 Cook 分析道,物件隱藏資訊的方式並非透過型別,而是透過函數的不透明性 — 函數只有名字,外界不知道其內容。物件更像是高次函數 (higher-order function)。一個物件導向程式其實是大量使用高次函數的程式,將這些函數傳來傳去的。這也是為什麼物件導向程式的驗證相當困難,因為分析含副作用的高次函數一直是難解的問題。和抽象資料型別比較之下,每一個物件都是同一個界面的不同實作。(但在物件導向中,如上所述的二元運算也是一個難題。)

物件也可以用既存型別表示。一但這麼做,我們會發現這正是 final coalgebra 的 Church 編碼。物件與 final coalgebra 的關係在近年來也是熱門話題。

Cook 接下來則談到各語言為了克服最佳化的難題實際上採取的設計。結論一節也相當精彩:許多課本作者往往拿堆疊、集合等等資料結構當作例子,並將「複雜」method(此處指需要檢查兩個以上的型別/物件內容的 method)輕輕帶過,因此看不出抽象資料型別與物件的差異。學界對物件的熱衷程度不如業界,一方面可能因為程式語言學界需要的東西大都較適合用抽象資料型別來作。但「如果你要描述視窗、檔案系統、或驅動程式,讓一個界面有很多實作就是很基礎的需求。」另一方面則可能是程式語言學界對物件的相關理論還不熟悉。我則想起大家也發現我們對 coalgebra, coinduction 的了解遠不如 induction。近年來漸漸有人在做相關研究,也許會慢慢有所改變的。

如果你對型別理論或物件導向之一還算熟悉,想補足另一邊的知識,這是一篇深入淺出的好文章,推薦給大家。

This entry was posted in 計算算計 and tagged , , , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*