《程式設計原本 》一1.7 概念

如果一個過程使用了一個類型,它就會依賴于該類型的文法、語義,還有其計算基的複雜性.在文法上,它依賴于一些确定的文字量和一些具有特定名字和簽名(signature)的過程的存在;其語義依賴于基過程的語義;其複雜性依賴于基過程的時間和空間複雜性.如果用另一個具有同樣性質的類型取代這個類型,程式将仍然是正确的.如果不是基于具體的類型,而是基于對類型的一些要求(通過文法和語義性質描述)來設計軟體部件,例如設計庫過程或資料結構,一定能提高它們的可用性.我們将這樣的一組要求稱為一個概念(concept).類型表示類别;而概念表示類屬.

要描述概念,就需要有一些處理類型的機制,包括類型屬性、類型函數和類型構造符.類型屬性(typeattribute)是從一個類型到一個值的映射,它描述有關類型的某種特征.類型屬性的例子如c++裡提供的内部類型屬性

sizeof(t),一個類型的對象的對齊方式,以及一個struct 的成員個數等.如果f是一個函數式過程類型,arity(f)傳回其輸入的個數.

類型函數(typefunction)是從一個類型到一個從屬類型的映射.類型函數的一個例子是:從給定的“到t的指針”得到類型t.在某些情況下,定義一個帶有一個附加的整數參數的帶索引(indexed)類型函數可能很有用.例如定義一個類型函數,它傳回一個結構類型的第i個成員的類型(從0開始計).如果f是一個函數式過程類型,類型函數codomain(f)傳回其結果的類型.如果f是一個函數式過程且i類型構造符(typeconstructor)是從一些已有類型出發構造新類型的機制.舉例說,pointer(t) 是一個内部提供的類型構造符,它從一個類型t 出發傳回“指向t 的指針”類型;struct 是一種内部提供的n元類型構造符;一個結構模闆是一個使用者定義的n元類型構造符.

如果t是一個n元類型構造符,下面用tt0,...,tn.1表示将它應用于類型t0,...,tn.1.一個重要例子是pair(二進制組),将其應用于規範類型t0和t1,就得到了一個struct 類型pairt0,t1 ,它有一個類型為t0的成員m0和一個類型為t1的成員m1.要保證類型pairt0,t1 本身也是規範的,就要求它的相等、指派、析構和構造操作都是基于類型t0和t1,通過按兩個成員分别做的方式定義.同樣的技術可以用于任何其他元組類型,例如triple(三元組).第12章将說明如何實作pairt0,t1 , 并說明更複雜的類型構造符如何維持規範性.

采用更形式化一點的說法,一個概念(concept)是對一個或多個類型的需求的一個描述,這一描述以對類型上的過程、類型屬性和類型函數的存在及其相關性質的方式給出.如果某個(某些)特定類型滿足這些需求,就說這一概念被這個(或這些)類型模組化(modeled),或者說它們是這一概念的模型(model).要斷言概念c被類型t0,...,tn.1模組化,我們寫c(t0,...,tn.1).如果任意的滿足概念c. 的類型也必定滿足概念c,就說概念c. 精化(re.ne)概念c.如果c. 精化c,也說c弱于c..

類型概念(typeconcept)指定義在一個類型上的一個概念.舉例說,c++定義了類型概念整數類型,它被無符号整數類型和有符号整數類型精化.而stl定義了類型概念序列(sequence).前面一直用基本類型概念regular和

5.附錄b說明了怎樣在c++裡定義類型屬性和類型函數.

functionalprocedure,它們對應于前面給出的非形式化定義.我們可以用标準的數學記法來形式化地定義各種概念.要定義概念c,采用的寫法是

c(t0,...,tn.1).

e0∧e1∧...

∧ek.1

其中的.讀作“按定義相等”,ti 是形式類型參數,ej 是概念子句.概念子句可以有如下三種形式:

1.前面已定義的概念的應用,說明相應類型參數的一個子集模組化此概念.

2.類型屬性、類型函數或者過程簽名,模組化相應概念的類型裡必須有它們.過程簽名的形式是f:tt.,其中t是過程的定義域而t. 是其值域.類型函數簽名的形式是f:c→ c.,其定義域和值域都是概念.

→

基于這些類型屬性、類型函數和過程表述的公理.

我們有時也在第二類概念子句裡的類型屬性、類型函數或過程的簽名之後包含它們的定義.這種定義的形式是x.→ f(x),其中的f是表達式.在特定模型裡,這一定義可以被另一個不同的但與之協調的實作所覆寫.

舉個例子,下面概念描述的是一進制函數式過程:

unaryfunction(f).

functionalprocedure(f)∧arity(f)=1∧domain:unaryfunctionregular

f .→ inputtype(f,0)

下面概念描述的是同源的函數式過程:

homogeneousfunction(f).functionalprocedure(f)

∧arity(f)>0

∧ (.i, j ∈ n)(i,j.

∧domain:homogeneousfunctionregular

應該看到

(.f ∈ functionalprocedure)unaryfunction(f)homogeneousfunction(f)

.

抽象(abstract)過程指用類型和常量參數化的過程,帶有對這些參數的要求.6 下面将為此使用函數模闆和函數對象模闆.參數放在template 關鍵字後面,類型參數用typename 引入,常量值用int 或其他整數類型名引入.對函數的需求通過requires 子句嚴格描述,該子句的内容是一個表達式,基于常量值、具體類型、形式參數、類型屬性和類型參數的應用,值和類型的相等,相關概念,以及邏輯連接配接詞等描述.7

這裡是一個抽象過程的例子:

定義域裡的值可能很大,是以這裡通過常量引用的方式傳遞該參數.操作一般說比較小(例如是函數指針或很小的函數對象),是以用值方式傳遞.

概念描述的是一個類型的所有對象都滿足的性質,其中的前條件(precon-dition)描述特定對象的性質.舉例說,一個過程可能要求它的某個參數是素數,對整數類型的這一需求就需要用一個概念描述,其中的素數性質用一個前條件描述.函數指針的類型隻描述了它的簽名,未描述其語義性質.例如,一個過

6.本質上具有我們所采用的形式的抽象過程出現在1930vanderwaerden[1930],基于emmynoether和emilartin的演講,georgecollins和davidmusser20世紀60年代後期和70年代前期的論文在計算機代數的研究中使用了它們.例如可以參考musser[1975].

7.requires子句的完整文法見附錄b.

程可能要求它的一個參數是指向函數的指針,并要求函數實作的是整數上的一個可結合的二進制運算.有關整數上二進制運算的要求可以用一個概念描述,而函數的結合性用一個前條件描述.

為一集類型定義一個前條件,需要使用一些數學記法,例如全稱和存在量詞,蘊涵等.舉例說,要描述整數的素數性質,用下面定義

property(n:integer)prime:n=1)∧(.u, v ∈ n)uv=n(|u|=1∨|v|=1)n .→ (|n|..

這裡的第一行引入了一些形式類型參數和它們模組化的概念,第二行說明一個性質并給出其簽名,第三行是描述有關的參數應滿足的特定性質的謂詞.

一進制函數式過程的規範性可以定義如下

這一定義很容易擴充到n元函數:将相等的函數作用于相等的參數得到相等的結果.通過擴充,我們要求規範的抽象函數的所有執行個體化也都是規範的.除非另有說明,本書後面說到過程時都是指規範過程,是以下面讨論中将不明确寫出這一前條件.

項目

1.1請将相等、指派、指派構造操作擴充到不同類型的對象上.請考慮兩個類型的解釋和聯系起跨類型的過程的公理.