面向對象語言

面向對象語言借鑒了20世紀50年代的人工智慧語言LISP，引入了動態綁定的概念和互動式開發環境的思想；始於20世紀60年代的離散事件模擬語言SIMULA67，引入了類的要領和繼承，成形於20世紀70年代的Smalltalk。

面向對象語言的發展有兩個方向：一種是純面向對象語言，如Smalltalk、EIFFEL等；另一種是混合型面向對象語言，即在過程式語言及其它語言中加入類、繼承等成分，如C++、Objective-C等。

面向對象語言刻畫客觀系統較為自然，便於軟體擴充與復用。有四個主要特點：

(1)識認性，系統中的基本構件可識認為一組可識別的離散對象；

(2)類別性，系統具有相同數據結構與行為的所有對象可組成一類；

(3)多態性，對象具有惟一的靜態類型和多個可能的動態類型；

(4)繼承性，在基本層次關係的不同類中共享數據和操作。

其中，前三者為基礎，繼承是特色。四者（有時再加上動態綁定）結合使用，體現出面向對象語言的表達能力。

一般認為，較典型的面向對象語言有：

simula67，支持單繼承和一定含義的多態和部分動態綁定；

Smalltalk支持單繼承、多態和動態綁定；

EIFFEL，支持多繼承、多態和動態綁定；

C++，支持多繼承、多態和部分動態綁定。

Java，支持單繼承、多態和部分動態綁定。

五種語言涉及概念的含義雖然基本相同，但所用術語有別。

C#，也支持單繼承，與Java和C++等有很多類似之處

基於類的面向對象語言是面向對象世界里的主流。它包括：

Simula，第一個面向對象語言

Smalltalk，第一個支持動態類型的語言

C++，它的大部分基於類的特性繼承自Simula.等等等等。

與基於類的語言相對應的是基於對象的面向對象語言。這裡“基於對象”的概念和把Visual Basic叫做基於對象的概念是不同的。這裡的“基於對象”是指一個只以對象為中心，沒有類的概念的語言，類似Python之類的語言。

類和對象

先看一個類的定義：

classcell is

var contents: Integer :=0;

method get(): Integer is

return self.contents;

end;

method set(n:Integer) is

self.contents := n;

end;

end;

一個類是用來描述所有屬於這個類的對象的共同結構的。這個cell類表示的對象擁有一個叫做contents的整數屬性（attribute），這個屬性被初始化成0。它還描述了兩個操作contents的方法。Get和set.這兩個方法的內容都是很直觀的。Self變數表示這個對象自己。

對象的動態語義可以這樣理解：

一個對象在內部被表示為一個指向一組屬性的指針。任何對這個對象的操作都會經過這個指針操作對象的屬性和方法。而當對象被賦值或被當作參數傳遞的時候，所傳遞的只是指針，這樣一來，同一組屬性就可以被共享。

（注，有些語言如C++，明確區分指向屬性組的指針和屬性組本身，而一些其它的語言則隱藏了這種區別）

對象可以用new從一個類中實例化。準確地說，new C分配了一組屬性，並返回指向這組屬性的指針。這組屬性被賦予了初始值，並包括了類C所定義的方法的代碼。

下面來考慮類型。對一個new C所生成的對象，把它的類型記為InstanceTypeOf(c).一個例子是：

var myCell:InstanceTypeOf(cell):=new cell;

這裡，通過引入InstanceTypeOf(cell），開始把class和type區分開來了。也可以把cell本身當作是類型，但接下來，就會發現，那樣做會導致混淆的。

方法解析（Method Lookup)

方法解析給出一個方法的調用o.m（……），一個由各個語言自己實現的叫做方法解析的過程負責找到正確的方法的代碼。（者按：是不是想起了vtable了？）。

直觀地看，方法的代碼可以被嵌入各個單個對象中，而且，對於許多面向對象語言，對屬性和方法的相似的語法，也確實給人這種印象。

不過，考慮到節省空間，很少有語言這樣實現。比較普遍的方法是，語言會生成許多method suite，而這些method suite可以被同一個類的對象們所共享。方法解析過程會延著對象內指向method suite的指針找到方法。

在考慮到繼承的情況，方法解析會更加複雜化。Method suite也許會被組成一個樹，而對一個方法的解析也許要查找一系列method suite.而如果有多繼承的話，method suite甚至可能組成有向圖，或者是環。

方法解析可能發生在編譯時，也可能發生在運行時。

在一些語言中，方法到底是嵌入對象中的，還是存在於method suite中這種細節，對程序員是無關緊要的。因為，所有能區分這兩種模式的語言特性一般在基於類的面向對象語言中都不被支持。

比如說，方法並不能象屬性一樣從對象中取出來當作函數使用。方法也不能象屬性一樣在對象中被更新。（也就是說，更新了一個對象的方法，而同一個類的其它對象的該方法保持不變。）

子類和繼承（Subclassing and Inheritance）

子類和繼承子類和一般的類一樣，也是用來描述對象的結構的。但是，它是通過繼承其它類的結構來漸進式地實現這個目的。

父類的屬性會被隱式地複製到子類，子類也可以添加新的屬性。在一些語言中，子類甚至可以override父類的屬性（通過更改屬性的類型來實現）

父類中的方法可以被複制到子類，也可以被子類override.

一個子類的代碼的示例如下：

subclassreCell of cell is

var backup: Integer:=0;

override set(n:Integer)is

self.backup:=self.contents;

super.set(n);

end;

method restore()is

self.contents:=self.backup;

end;

end;

對有subclass的方法解析，根據語言是靜態類型還是動態類型而有所不同。

在靜態類型的語言（如C++,Java）里，父類，子類的method suite的拓撲結構在編譯時就已經確定，所以可以把父類的method suite里的方法合併到子類的method suite中去，方法解析時就不用再搜索這個method suite的樹或圖了。（按：C++的vtable就是這種方法）

而對於動態類型的語言，（也就是說，父子類的關係是在運行時決定的），method suite就無法合併了。所以，方法解析時，就要沿著這個動態生成的樹或有向圖搜索直到找到合適的方法。而如果語言支持多繼承，這個搜索就更複雜了。

父類和子類

從上述的幾個例子來看，似乎子類只是用來從父類借用一些定義，以避免重複。但是，當考慮到subsumption，事情就有些不同了。什麼是Subsumption呢？請看下面這個例子：

var myCell:InstanceTypeOf(cell):=new cell;

var myReCell:InstanceTypeOf(reCell):=new reCell;

procedure f(x:InstanceTypeOf(cell))is…end;

再看下面這段代碼：

myCell:=myReCell;

f(myReCell);

在這兩行代碼中，頭一行把一個InstanceTypeOf(reCell）類型的變數賦值給一個InstanceTypeOf(cell）的變數。而第二行則用InstanceTypeOf(reCell）類型的變數作為參數傳遞給一個參數類型為InstanceTypeOf(cell）的函數。

這種用法在類似Pascal的語言中是不合法的。而在面向對象的語言中，依據以下的規則，它則是完全正確的用法。該規則通常被叫做subtype polimorphism，即子類型多態（按：其實subtyping應該是OO語言最區別於其它語言的地方了）

如果c’是c的子類，並且o’是c’的一個實例，那麼o’也是c的一個實例。

更嚴格地說：

如果c’是c的子類，並且o’：InstanceTypeOf(c’），那麼o’：InstanceTypeOf(c).

仔細分析上面這條規則，可以在InstanceTypeOf的類型之間引入一個滿足自反和傳遞性的子類型關係，用<；：符號來表示。（按：自反就是說，對任何a,a關係a都成立，比如說，數學里的相等關係就是自反的。而傳遞性是說，如果a關係b,b關係c，就能推出a關係c。大於，小於等關係都是具備傳遞性的）

那麼上面這條規則可以被拆成兩條規則：

1．對任何a:A，如果A<:B，那麼a:B.

2．InstanceTypeOf(c’）<:InstanceTypeOf(c)當且僅當c’是c的子類

第一條規則被叫做Subsumption.它是判斷子類型（注意，是subtype，不是subclass）的唯一標準。

第二條規則可以叫做subclassing-is-subtyping（子類就是子類型，繞嘴吧？）

一般來說，繼承都是和subclassing相關的，所以這條規則也可以叫做：inheritance-is-subtyping（繼承就是子類型）

所有的面向對象語言都支持subsumption（可以說，沒有subsumption，就不成為面向對象）。

大部分的基於類的面向對象語言也並不區分subclassing和subtyping.但是，一些最新的面向對象語言則採取了把subtyping和subclassing分開的方法。也就是說，A是B的子類，但A類的對象卻不可以當作B類的對象來使用。（按：有點象C++里的私有繼承，但內容比它豐富）

好吧，關於區分subclassing和subtyping，後面會講到。

下面，重新回頭來看看這個procedure f.在subsumption的情況下，下面這個代碼的動態語義是什麼呢？

Procedure f(x:InstanceTypeOf(cell))is

x.set(3);

end;

f(myReCell);

當myReCell被當作InstanceTypeOf(cell）的對象傳入f的時候，x.set(3）究竟是調用哪一個版本的set方法呢？是定義在cell中的那個set還是定義在reCell中的那個呢？

這時，有兩種選擇

1．Static dispatch（按照編譯時的類型來決定）

2．Dynamic dispatch（按照對象運行時真正類型來決定）

（按，熟悉C++的朋友們一定微笑了，這再簡單不過了。）

static dispatch沒什麼可說的。

dynamic dispatch卻有一個有趣的屬性。那就是，subsumption一定不能影響對象的狀態。如果在subsumption的時候，改變了這個對象的狀態，比如象C++中的對象切片，那麼動態解析的方法就可能會失敗。

好在，這個屬性無論對語義，還是對效率，都是很有好處的。

（按，C++中的object slicing會把新的對象的vptr初始化成它自己類型的vtable指針，所以不存在動態解析的問題。但實際上，對象切片根本不能叫做subsumption。

具體語言實現中，如C++，雖然subsumption不會改變對象內部的狀態，但指針的值卻是可能會變化的。這也是一個讓人討厭的東西，但C++vtable的方案卻只能這樣。有一種變種的vtable方法，可以避免指針的變化，也更高效。會在另外的文章中闡述這種方法。）

關於類型信息

雖然subsumption並不改變對象的狀態，在一些語言里（如Java），它甚至沒有任何運行時開銷。但是，它卻使丟掉了一些靜態的類型信息。

比如說，有一個類型InstanceTypeOf(Object），而Object類里沒有定義任何屬性和方法。又有一個類MyObject，它繼承自Object。那麼當把MyObject的對象當作InstanceTypeOf(Object）類型來處理的時候，就得到了一個什麼東西也沒有的沒用的空對象。

當然，如果考慮一個不那麼極端的情況，比如說，Object類裡面定義了一個方法f，而MyObject對方法f做了重載，那麼，通過dynamic dispatch，還是可以間接地操作MyObject中的屬性和方法的。這也是面向對象設計和編程的典型方法。

從一個purist的角度看，dynamic dispatch是唯一應該用來操作已經被subsumption忘掉的屬性和方法的東西。它優雅，安全，所有的榮耀都歸於dynamic dispatch！！！

不過，讓purist們失望的是，大部分語言還是提供了一些在運行時檢查對象類型，並從而操作被subsumption遺忘的屬性和方法。這種方法一般被叫做RTTI（Run Time Type Identification）。如C++中的dynamic_cast，或Java中的instanceof.

實事求是地說，RTTI是有用的。但因為一些理論上以及方法論上的原因，它被認為是破壞了面向對象的純潔性。

首先，它破壞了抽象，使一些本來不應該被使用的方法和屬性被不正確地使用。

其次，因為運行時類型的不確定性，它有效地把程序變得更脆弱。

第三點，也許是最重要的一點，它使程序缺乏擴展性。當加入了一個新的類型時，也許需要仔細閱讀dynamic_cast或instanceof的代碼，必要時改動它們，以保證這個新的類型的加入不會導致問題。

很多人一提到RTTI，總是側重於它的運行時的開銷。但是，相比於方法論上的缺點，這點運行時的開銷真是無足輕重的。

而在purist的框架中（按，吸一口氣，目視遠方，做深沉狀），新的子類的加入並不需要改動已有的代碼。

這是一個非常好的優點，尤其是當並不擁有全部源代碼時。

總的來說，雖然RTTI（也叫type case）似乎是不可避免的一種特性，但因為它的方法論上的一些缺點，它必須被非常謹慎的使用。今天面向對象語言的類型系統中的很多東西就是產生於避免RTTI的各種努力。

比如有些複雜的類型系統中可以在參數和返回值上使用Self類型來避免RTTI.這點後面會介紹到。

協變，反協變和壓根兒不變（Covarance,Contravariance and Invariance）

在下面的幾個小節里，來介紹一種避免RTTI的類型技術。在此之前，先來介紹“協變”，“反協變”和“壓根兒不變”的概念。

協變

首先，來看一個Pair類型：A*B

這個類型支持一個getA（）的操作以返回這個Pair中的A元素。

給定一個A’<:A，那麼，可以說A’*B<:A*B。

為什麼呢？可以用Subsumption的屬性加以證明：

假設有一個A’*B類型的對象a’*b，這裡，a’：A’，b:B,a’*b<:A’*B

那麼，因為，A’<:A，從subsumption，可以知道a’：A,getA():A所以，a’*b<:A*B

這樣，就定義A*B這個類型對於A是協變的。

同理，也可以證明A*B對於B也是協變的。

正規一點說，Covariance是這樣定義的：

給定L(T），這裡，類型L是通過類型T組合成的。那麼，

如果T1<:T2能夠推出L(T1)<:L(T2），那麼就說L是對T協變的。

反協變

請看一個函數：A f(B b);（用functional language的定義也許更簡潔，即f:B->A)

那麼，給定一個B’<:B，在B->A和B’->A之間有什麼樣的subtype關係呢？

可以證明，B->A<:B’->A。

基於篇幅，不再做推導。

所以，函數的參數類型是反協變的。

Contravariance的正規點的定義是這樣的：

給定L(T），這裡，類型L是通過類型T組合成的。那麼，

如果T1<:T2能夠推出L(T2)<:L(T1），那麼就說L是對T反協變的。

同樣，可以證明，函數的返回類型是協變的。

壓根兒不變

那麼再考慮函數g:A->A

這裡，A既出現在參數的位置，又出現在返回的位置，可以證明，它既不是協變的，也不是反協變的。

對於這種既不是協變的，也不是反協變的情況，稱之為Invariance

值得注意的是，對於第一個例子中的Pair類型，如果支持setA(A），那麼，Pair就變成Invariance了。

方法特化（Method Specialization）

在前面對subclass的討論中，採取了一種最簡單的override的規則，那就是，overriding的方法必須和overriden的方法有相同的signature.

但是，從類型安全的角度來說，這並不是必須的。

這樣，只要A<:A’，B’<:B，下面的代碼就是合法的：

classc is

method m(x:A):B is…end;

method m1(x1:A1):B1 is…end;

end;

subclassc’ of c is.

傳統的基於類的面向對象語言的一個主要特點就是inheritance,subclassing和subtyping之間的密不可分的聯繫。很多的面向對象語言的語法，概念，就是從這三者而來的。比如說，通過subclassing，可以繼承父類的一些方法，而同時又可以在子類中改寫父類的方法。這個改寫過的方法，通過subtyping、subsumption，又可以從一個類型是父類的對象去調用。

但是，inheritance,subclassing,subtyping這三者並不是永遠和睦相處的。在一些場合，這三者之間的糾纏不清會妨礙到通過繼承或泛型得到的代碼重用。因此，人們開始注意到把這三者分離開來的可能性。區分subclassing和subtyping已經很常見了。而其它的一些方法還處於研究的階段。

在早期的面向對象語言中（如Simula），類型的定義是和方法的實現是混合在一起的。這種方式違反了今天已經被廣泛認識到的把實現和規範（Specification)分離的原則。這種分離得原則在開發是團隊進行的時候尤其顯得重要。

更一些的語言，通過引入不依賴於實現的對象類型來區分實現和規範。Modula-3以及其它如Java等的支持class和interface的語言都是採用的這種技術。

開始引入InstanceTypeOf(cell）時，它代表的概念相當有限。看上去，它似乎只表示用new cell生成的對象的類型，於是，並不能用它來表示從其它類new出來的對象。但後來，當引入了subclassing,method overriding,subsumption和dynamic dispatch之後，事情變得不那麼簡單了。的InstanceTypeOf(cell）已經可以用來表示從cell的子類new出來的對象，這些對象可以包括不是cell類定義的屬性和方法。

如此看來，讓InstanceTypeOf(cell）依賴於一個具體的類似乎是不合理的。實際上，一個InstanceTypeOf(cell）類型的對象不一定會跟classcell扯上任何關係。

它和cell類的唯一共同之處只是它具有了所有cell類定義的方法的簽名（signature）.

基於這種考慮，可以引入對象類型的語法：

針對cell類和reCell類的定義：

class cell is

var contents: Integer:=0;

method get(): Integer is

return self.contents;

end;

method set(n:Integer) is

self.contents:=n;

end;

end;

subclass reCell of cell is

var backup: Integer := 0;

override set(n: Integer) is

self.backup :=self.contents;

super.set(n);

end;

method restore() is

self.contents := self.backup;

end;

end;

可以給出這樣的對象類型定義：

ObjectType Cell is

var contents: Integer;

method get(): Integer;

method set(n:Integer);

end;

ObjectType ReCell is

var contents: Integer;

var backup: Integer;

method get(): Integer

method set(n: Integer);

method restore();

end;

這兩個類型的定義包括了所有cell類和reCell類定義的屬性和方法的類型，但卻並不包括實現。這樣，它們就可以被當作與實現細節無關的的介面以實現規範和實現的分離。兩個完全無關的類c和c’，可以具有相同的類型Cell，而Cell類型的使用者不必關心它使用的是c類還是c’類。

注意，還可以加入額外的類似繼承的語法來避免在ReCell里重寫Cell里的方法簽名。但那只是小節罷了。

在上面的討論中，subtype的關係是建立在subclass關係的基礎上的。但如果想要讓type獨立於class，那麼也需要定義獨立於subclass的subtype.

在定義subtype時，又面臨著幾種選擇：subtype是由類型的組成結構決定的呢？還是由名字決定呢？

由類型的組成結構決定的subtype是這樣的：如果類型一具有了類型二的所有需要具備的屬性和方法，就說類型一是類型二的subtype.

由類型名字決定的subtype是這樣的：只有當類型一具有了類型二的所有需要具備的屬性和方法，並且類型一被明確聲明為類型二的subtype時，才認可這種關係。

而如果的選擇是一，那麼那些屬性和方法是subtype所必需具備的呢？哪些是可有可無的呢？

由組成結構決定的subtype能夠在分散式環境和object persistence系統下進行類型匹配。缺點是，如果兩個類型碰巧具有了相同的結構，但實際上卻風馬牛不相及，那就會造成錯誤。不過，這種錯誤是可以用一些技術來避免的。

相比之下，基於名字的subtype不容易精確定義，而且也不支持基於結構的subtype.

可以先定義一個簡單的基於結構的subtype關係：

對兩個類型O和O’，

O’<:O當O’具有所有O類型的成員。O’可以有多於O的成員。

例如：ReCell<:Cell.

為了簡明，這個定義沒有考慮到方法的特化。

另外，當類型定義有遞歸存在的時候（類似於鏈表的定義），對subtype的定義需要額外地加小心。

因為不關心成員的順序，這種subtype的定義自動地就支持多重的subtype.

比如說：

ObjectType ReInteger is

var contents: Integer;

var backup: Integer;

method restore();

end;

那麼，就有如下的subtype的關係：

ReCell <: Cell

ReCell <: ReInteger

（按，例子中沒有考慮到象interface不能包含數據域這樣的細節。實際上，如果支持對數據域的override，而不支持shadowing--作者的基於結構的subtype語義確實隱含著這樣的邏輯―那麼，interface里包含不包含數據域就無關緊要了，因為令人頭疼的名字衝突問題已經不存在了）

從這個定義，可以得出：

如果c’是c的子類，那麼ObjectTypeOf(c’）<:ObjectTypeOf(c)

注意，這個定義的逆命題並不成立，也就是說：

即使c’和c之間沒有subclass的關係，只要它們所定義的成員符合了subtype的定義，ObjectTypeOf(c’）<: ObjectTypeOf(c）仍然成立。

回過頭再看看在前面的subclass-is-subtyping：

InstanceTypeOf(c’）<:InstanceTypeOf(c)當且僅當c’是c的子類在那個定義中，只有當c’是c的子類時，ObjectTypeOf(c’）<:ObjectTypeOf(c）才能成立。

相比之下，已經部分地把subclassing和subtyping分離開了。Subclassing仍然是subtyping，但subtyping不再一定要求是subclassing了。

把這種性質叫做“subclassing-implies-subtyping”而不是“subclass-is-subtyping”了。

泛型(Type Parameters)

一般意義上來說，泛型是一種把相同的代碼重用在不同的類型上的技術。它作為一個相對獨立於其它面向對象特性的技術，在面向對象語言里已經變得越來越普遍了。這裡之所以討論泛型，一是因為泛型這種技術本身就很讓人感興趣，另外，也是因為泛型是一個被用來對付二元方法問題（binary method problem)的主要工具。

和subtyping共同使用，泛型可以用來解決一些在方法特化等場合由反協變帶來的類型系統的困難。考慮這樣一個例子：

有Person和Vegitarian兩種類型，同時，有Vegitable和Food兩種類型。而且，Vegitable<:Food

ObjectType Person is

…

method eat(food: Food);

end;

ObjectType Vegetarian is

…

method eat(food: Vegitable);

end;

這裡，從常識，知道一個Vegitarian是一個人。所以，希望可以有Vegetarian<:Person.

不幸的是，因為參數是反協變的，如果錯誤地認為Vegetarian<:Person，根據subtype的subsumption原則，一個Vegetarian的對象就可以被當作Person來用。於是一個Vegetarian就可以錯誤地吃起肉來。

使用泛型技術，引入Type Operator（也就是，從一個類型導出另一個類型，概念上類似於對類型的函數）。

ObjectOperator PersonEating[F<:Food] is

…

method eat(food:F);

end;

ObjectOperator VegetarianEating[F<:Vegetable] is

…

method eat(food:F);

end;

這裡使用的技術被稱作Bounded Type Parameterization.(Trelli/Owl,Sather,Eiffel,PolyTOIL,Raptide以及Generic Java都支持Bounded Type Parameterization.其它的語言，如C++，只支持簡單的沒有類型約束的泛型）

F是一個類型參數，它可以被實例化成一個具體的類型。類似於變數的類型定義，一個bound如F<:Vegitable限制了F只能被Vegitable及其子類型所實例化。所以，VegitarianEating[Vegitable],VegitarianEating[Carrot]都是合法的類型。而VegitarianEating[Beef]就不是一個合法的類型。類型VegitarianEating[Vegitable]是VegitarianEating的一個實例，同時它等價於類型Vegitarian.（用的是基於結構的subtype）

於是，有：

對任意F<:Vegitable,VegitarianEating[F]<:PersonEating[F]

對於原來的Vegitarian類型，有：

Vegetarian=VegetarianEating[Vegetable]<:PersonEating[Vegitable]

這種關係，正確地表達了“一個素食者是一個吃蔬菜的人”的概念。

除了Bounded Type Parameterization之外，還有一種類似的方法也可以解決這個素食者的問題。這種方法被叫做：Bounded Abstract Type請看這個定義：

ObjectType Person is

Type F<: Food;

…

var lunch: F;

method eat(food: F);

end;

ObjectType Vegetarian is

Type F<: Vegitable;

…

var lunch: F;

method eat(food: F);

end;

這裡，F<:Food的意思是，給定一個Person，知道他能吃某種Food，但不知道具體是哪一種。這個lunch的屬性提供這個Person所吃的Food.

在創建Person對象時，可以先選定 一個Food的subtype，比如說，F=Dessert.然後，用一個Dessert類型的變數賦給屬性lunch.最後再實現一個eat(food:Dessert）的方法。

這樣，Vegetarian<:Person是安全的了。當把一個Vegetarian當作一個Person處理時，這個Vegitarian可以安全地吃他自帶的午餐，即使不知道他吃的是肉還是菜。

這種方法的局限在於，Person,Vegitarian只能吃他們自帶的午餐。不能讓他們吃買來的午餐。