第7章多態(tài)性

1、第7章 多態(tài)性,本章和下一章介紹類型論的一些概念，它們是程序設(shè)計語言的多態(tài)性和數(shù)據(jù)抽象的基礎(chǔ)這些概念與下面的語言概念有關(guān) Ada的程序包和類屬 C??的模板 ML以及相近語言Miranda和Haskell的多態(tài)性、抽象類型和模塊等 現(xiàn)實語言出于效率上的考慮，所采用的副本沒有相應(yīng)的類型化?演算那么靈活,7.1 引 言,本章的主要內(nèi)容多態(tài)類型系統(tǒng)的語法，包括直謂式的，非直謂式的和type: type版本直謂式多態(tài)?演算

2、，包括和其它兩個系統(tǒng)之間的聯(lián)系，它的等式證明系統(tǒng)和歸約、多態(tài)聲明非直謂式多態(tài)?演算的縱覽數(shù)據(jù)抽象和存在類型類型表達式的分類,7.1 引 言,7.1.2 類型作為函數(shù)變元簡單類型化?演算有某種明顯的缺點很多有計算意義且有用的表達式不是良類型的排序函數(shù)：希望能應(yīng)用于許多不同類型的數(shù)據(jù) Sort : (t ? t ? bool ) ? Array[prt t] ? Array [prt t]多態(tài)函數(shù)變元的類型可以

3、有多種不同的情況通過拓展?抽象到允許對類型進行?抽象，可以把??拓展到包括多態(tài)函數(shù),7.1 引 言,再以更簡潔一些的函數(shù)合成運算為例composenat, nat, nat ??f : nat ? nat.?g: nat ? nat.?x: nat.f (g x) composenat, nat ? nat, nat ? ?f : (nat ? nat) ? nat.?g: nat ? (nat ? nat)

4、.?x: nat.f (g x)composer, s, t ? ?f : s ? t.?g: r ? s.?x: r.f (g x)compose ? ?r : T. ?s: T. ?t: T. composer, s, t,7.1 引 言,考察compose ? ?r:T. ?s:T. ?t:T. composer, s, t對T（類型的集合）有幾種可能的解釋類型應(yīng)用compose nat nat nat =

5、(?r:T. ?s:T. ?t:T. ?f :s ? t. ?g:r ? s. ?x:r. f (g x)) nat nat nat= ?f :nat ? nat. ?g:nat ? nat. ?x:nat. f (g x)compose的類型是什么？,7.1 引 言,以多態(tài)恒等函數(shù)為例Id ? ?t : T. ?x : t. xId的定義域是T，但值域難以描述一種表示：Id : (?t :T? t ? t)?t :

6、T? t ? t是無限積 ?t ?T t ? t ： (nat ? nat) ? (bool ? bool) ? . . . (idnat ? nat, idbool ? bool, . . .)是該類型的一個值Id nat = ?x : nat. x = idnat ? natId bool = ?x : bool. x = idbool ? bool代換僅在Id的類型上完成，而不是在函數(shù)本身上完成,7.1 引

7、 言,以多態(tài)恒等函數(shù)為例Id ? ?t : T. ?x : t. xId的定義域是T，但值域難以描述一種表示：Id : (?t :T? t ? t)另一種表示： Id : ?t: T. t ? t?t: T. t ? t是所有下述函數(shù)構(gòu)成的類型：每個函數(shù)對所有的t:T，給出從t 到t 的一個映射下面先只考慮第一種表示法,7.1 引 言,對T有三種自然的選擇為多態(tài)函數(shù)引入類型后，必須決定這些類型怎樣來適合

8、現(xiàn)在的類型系統(tǒng)1、直謂式多態(tài)性T僅含用?、?和?或?及一組類型常量定義的類型這是在已經(jīng)定義了T的所有成員后才引入T2、非直謂式多態(tài)性T還包含所有的多態(tài)類型（例如?t: T. t ? t），但不把T本身作為一個類型,7.1 引 言,對T有三種自然的選擇為多態(tài)函數(shù)引入類型后，必須決定這些類型怎樣來適合現(xiàn)在的類型系統(tǒng)1、直謂式多態(tài)性2、非直謂式多態(tài)性3、type : type令T包含所有的類型，包括它本身從計算

9、的觀點看，并非立即能看清楚：引入“所有類型的類型”后會引起什么錯誤,7.1 引 言,三種多態(tài)性之間的簡單區(qū)別1、直謂式多態(tài)性Id僅能夠應(yīng)用于非多態(tài)類型，例如nat 或 (nat ? nat)Id (nat ? nat) = ?x : nat ? nat. x2. 非直謂式多態(tài)性Id可以應(yīng)用到任何類型Id (?t: T. t ? t) = ?x : (?t: T. t ? t). x不可能把每個多態(tài)?項都解釋成集合

10、論的函數(shù)Id = {??, ?x:?. x? | ? ?T}，其中序?qū)?(?t: T. t ? t), ?x: (?t: T. t ? t). x ? 的第一元包含Id,7.1 引 言,三種多態(tài)性之間的簡單區(qū)別1、直謂式多態(tài)性Id (nat ? nat) = ?x : nat ? nat. x2. 非直謂式多態(tài)性Id (?t: T. t ? t) = ?x : (?t: T. t ? t). x3、type : ty

11、peId T = ?x:T. x(Id T): T ? T,7.1 引 言,參數(shù)多態(tài)性和特定多態(tài)性1、參數(shù)化多態(tài)性一個多態(tài)函數(shù)對任何類型都使用“本質(zhì)上一樣的算法”2、特定多態(tài)性可以測試類型變元的值，根據(jù)它的類型類型選擇某個分支ad_hoc_compose ? ?r: T. ?s: T. ?t: T.?f : s ? t. ?g: r ? s. ?x: r. if Eq? s t then f (f (

12、g x)) else f (g x),7.2 直謂式多態(tài)演算,7.2.1 類型和項的語法??? ?的類型分成兩類??類型全域U1“小”全域用?構(gòu)造的多態(tài)類型 全域U2 “大”全域各類表達式（上下文、類型表達式、項）的語法各由一個斷言證明系統(tǒng)給出在??? ?中將使用形式為? ? A: B的斷言?是上下文，指出每個變量的類型或全域A是類型表達式，則B是U1，U2A是項，則B是類型表達式,7.2 直謂式

13、多態(tài)演算,良形上下文的公理和推理規(guī)則上下文是一個有序序列，它給變量以類型或全域 ?= v1 : A1, …, vk : Ak每個Ai必須僅在假設(shè)v1 : A1, …, vi -1 : Ai–1下就可證明為良形的可以使用公理和推理規(guī)則來將它形式化例：?t : U1.?x : t ? t.?y: t. xy 確定xy類型時的上下文：t : U1, x : t ? t, y: t,7.2 直謂式多態(tài)演算,良形上下文的公

14、理和推理規(guī)則? context (empty context) t不在?中(U1 context) x不在?中 (Ui type context),7.2 直謂式多態(tài)演算,良形上下文的公理和推理規(guī)則 (var) (add var) 這兩條規(guī)則可用于多個類型系統(tǒng) 第二條規(guī)則可用于推

15、導(dǎo)x:A, y:B ? x:A這樣的斷言,7.2 直謂式多態(tài)演算,U1和U2類型表達式的語法規(guī)則U1的類型表達式由三個公理和推理規(guī)則給出? ? b: U1 (cst U1) （限制到U1的變量） (var) (? U1),7.2 直謂式多態(tài)演算,第二個全域U2包含類型U1和多態(tài)函數(shù)類型

16、 (U1?U2) (?U2)雖然有屬于U2的類型表達式，但是沒有U2的變量如果加了變量和?抽象到U2上，它就會導(dǎo)致形式是?t:U2.?的類型，它將屬于第三個全域U3,7.2 直謂式多態(tài)演算,例證明?t: U1.t ? t是屬于U2的良形的類型表達式? context由(empty context)t: U1 context由(U1 context)t: U1 ?

17、t: U1(var)t: U1 ? t ? t: U1(?U1)t: U1 ? t ? t: U2(U1?U2)? ? ( ?t: U1.t ? t) : U2(?U2),7.2 直謂式多態(tài)演算,項的語法（先給??, ? 預(yù)備項的文法 ）M ::= b | x | ?x:?. M | MM | ?t: U1.M | M?定型規(guī)則用來判斷項是否為良類型的 (var)

18、 (add var),7.2 直謂式多態(tài)演算,? ? c: ? (cst) (?Intro) (?Elim)任何??項（可能包括了用類型變量取代類型常量）都是??,?的項,7.2 直謂式多態(tài)演算,(? Intro) (? Elim)

19、 (type eq)在類型?t: U1.?中將省略t所屬的全域U1，寫成?t.?,7.2 直謂式多態(tài)演算,(? Intro) (? Elim) (type eq)若? ? M??是從公理和??, ?定型規(guī)則可推導(dǎo)，則說，M在上下文?中是類型為?的??, ?項,7.2 直謂式多態(tài)演算,規(guī)則U1 ?U2 和規(guī)則U1 :U21、規(guī)則U1 ?U2可以只用一

20、個?形成規(guī)則U1 ?U2沒有在該語言上設(shè)置任何額外的語義限制2、規(guī)則U1 :U2因為????在任意U2類型上無任何有意義的運算，因此看起來沒有任何理由取U1 :U2在????的非直謂式拓展中，加入U1 :U2規(guī)則將是一個合理的語言設(shè)計,7.2 直謂式多態(tài)演算,7.2.2 和其它形式多態(tài)性的比較其它兩種演算都可看成直謂式多態(tài)演算的特殊情況非直謂式類型化?演算強加“全域等式”U1 = U2 “type: type”演算

21、強加了等式U1 = U2和條件U1:U2,7.2 直謂式多態(tài)演算,非直謂式演算在??, ?中已經(jīng)有U1 ?U2,加入逆向包含U2 ?U1來獲得U1 = U2(U2?U1),7.2 直謂式多態(tài)演算,例證明語法斷言? ? (I (?t.t?t))I: ? t.t?t， 其中I ? ?t:U1.?x:t.x? 由（??, ?的定型規(guī)則） ? ? I: (?t.t?t)，其中

22、(?t.t?t):U2? (?t.t?t):U1 由(U2 ?U1)? I (?t.t?t) : (?t.t?t) ? (?t.t?t) 由(? Elim)? I (?t.t?t) I : (?t.t?t) 由(? Elim),7.2 直謂式多態(tài)演算,type : type加上U2 = U1和U1:U2 對前者加語法規(guī)則（U2 ?U1）對后者加公理 ? ? U1:U2 (U1:U2)

23、可以寫出非常復(fù)雜的類型函數(shù)一個有效的編譯時的類型檢查算法是不可能的,7.2 直謂式多態(tài)演算,??? ?的簡化語法第一個約定是使用兩類變量項變量x, y, z, …類型變量r, t, s, …代表U1的類型第二個約定對U1的類型表達式使用?, ??, ?1, … 對U2的類型表達式使用?, ??, ?1, … U1和U2的類型表達式的語法? ::= t | b | ? ? ?? ::=

24、? | ?t.?,7.2 直謂式多態(tài)演算,上下文? = {x1: ?1, … , xk: ?k}－－不再需要類型變量語法簡化后的規(guī)則 {x: ?} ? x: ? (var)? ? c:? (cst) (add var) (?Intro),7.2 直謂式多態(tài)演算,(?Elim) （t在?中不是自由的）

25、(? Intro) (? Elim),7.2 直謂式多態(tài)演算,7.2.3 等式證明系統(tǒng)和歸約??, ?等式的形式是? ? M = N:?，其中M和N都是類型?的項??,?的等式推理系統(tǒng)是??證明系統(tǒng)的一個拓展，增加了一些公理和推理規(guī)則該證明系統(tǒng)包含自反公理，對稱和傳遞規(guī)則同項形成規(guī)則對應(yīng)的推理規(guī)則同普通的?抽象和應(yīng)用對應(yīng)的推理規(guī)則,7.2 直謂式多態(tài)演算,增加了類型抽象和類型應(yīng)用公理?

26、 ? ?t. M = ?s. [s?t]M : ?t.? (?)?? ? (?t. M)? = [??t]M : [??t]? (?)?? ? ?t. Mt = M : ?t.? t在M中沒有自由出現(xiàn) (?)?,7.2 直謂式多態(tài)演算,對類型抽象和應(yīng)用，還有下面的同余規(guī)則 (?)? (?)?,7.2 直謂式多態(tài)演算,這些等式公理可以從左

27、向右定向,得到一個歸約系統(tǒng)例 (?t.?x: t.x) ? y ? (?x: ?.x) y ? y 可以證明歸約多態(tài)??,?項的合流性和強范式化命題7.1 歸約保項的類型,7.2 直謂式多態(tài)演算,7.2.4 ML風(fēng)格的多態(tài)聲明ML的類型系統(tǒng)可看成??? ?的一個拓展主要區(qū)別是，ML包含多態(tài)的let聲明通過調(diào)查多態(tài)函數(shù)在??? ?中的使用來啟發(fā)這種let聲明的形式??? ?可以寫出Id ? (?t. ?x : t

28、.x) : ?t. t ? tId nat 3和 Id bool true都是良類型的項寫不出(?f :(?t.t ?t). … f nat 3…f bool true)?t.?x:t.x因為?t. t ? t是U2的一個類型,7.2 直謂式多態(tài)演算,對于U2類型，使用一種非常有限的變量約束形式，對需要多態(tài)函數(shù)的許多實際程序設(shè)計來說已經(jīng)足夠了這種方式利用let x: ? = N in M和(?x:?.M)N在語義上都等價于

29、[N/x]M，而定型卻不一樣,7.2 直謂式多態(tài)演算,對于U2類型，使用一種非常有限的變量約束形式，對需要多態(tài)函數(shù)的許多實際程序設(shè)計來說已經(jīng)足夠了ML的方式??? ?, let使用 let x : ? = N in M 表達式，增加規(guī)則和公理： (let)? ? (let x:? = N in M) = [N/x]M:? (let)eq,7.2 直謂式多態(tài)演算,例考慮compose: ?r.

30、?s.?t.?其中? = (s?t) ? (r?s) ? (r?t)compose在一個表達式中使用多次，讓其函數(shù)體僅寫一次 let x: (?r.?s.?t.?) = compose in M，則? ? ( let x: (?r.?s.?t.?) = compose in M) = [compose/x]M: ? 避免寫下面的表達式，并能達到同樣的效果(?f :(?t.t ?t). … f

31、nat 3…f bool true)?t.?x:t.x,7.3 非直謂式多態(tài)演算,7.3.1 引言非直謂式多態(tài)?演算忽略直謂式??? ?的全域U1和U2的區(qū)別由所有類型的一個聚集T來代替U1和U2用????表示，以區(qū)別直謂式系統(tǒng)????類型由文法? ::= b | t | ? ? ? | ?t.?定義，無須用公理和推理規(guī)則給出,7.3 非直謂式多態(tài)演算,????類型表達式的文法? ::= b | t | ? ?

32、 ? | ?t.?項的形成依據(jù)7.2.2節(jié)的變量公理(var)、常量公理(cst)、增加自由變量類型假設(shè)的規(guī)則(add var)、規(guī)則(? Intro)、規(guī)則(? Elim)、規(guī)則(? Intro)和規(guī)則(? Elim)這些規(guī)則中的?由?代替并且對有關(guān)的類型全域沒有限制,7.3 非直謂式多態(tài)演算,非直謂演算可能是最廣泛研究的一種多態(tài)性1、其語法的簡單性該語言語法上比??? ?簡單，因為沒有全域的限制但是證明它的強范

33、式性非常困難2、語義的復(fù)雜性想提供直觀和數(shù)學(xué)嚴格的語義，本質(zhì)上很困難多態(tài)恒等函數(shù)可應(yīng)用到它自己的類型，造成了不可能把這樣的類型解釋成普通集合論函數(shù)的集合Id = {??, ?x: ?. x? | ? ?T}，其中序?qū)?(?t: T. t ? t), ?x: (?t: T. t ? t). x ? 的第一元包含Id,7.3 非直謂式多態(tài)演算,非直謂演算可能是最廣泛研究的一種多態(tài)性3、編程的靈活性提供了一個非常靈活的多態(tài)類型

34、系統(tǒng)，象Ada、CLU和ML等語言的多態(tài)性特征都可以看成是作了某種限制的????多態(tài)性可以用????中的?抽象來模仿ML的let? ? let x:?t.? = M in N:? （ ML方式）它是項? ? (? x:?t.?.N)M:?的一種語法美化,7.3 非直謂式多態(tài)演算,7.3.2 非直謂式多態(tài)?演算的表達能力給出一個例子來展示非直謂式多態(tài)?演算的表達能力在二階Peano算術(shù)中 可證明為全函數(shù)的

35、遞歸函數(shù)恰好是在非直謂式多態(tài)?演算中可以定義的數(shù)值函數(shù) 這是多態(tài)?演算和二階邏輯的證明論之間的聯(lián)系的一部分在此僅概述數(shù)值函數(shù)的某些表示方面的內(nèi)容,7.3 非直謂式多態(tài)演算,在無類型常量的純????中，自然數(shù)類型的一種自然選擇若有常量zero:nat和succ:nat?nat，則可以用表達式succ(succ…(succ zero)… )表示自然數(shù)n在純????中，沒有常量zero和succ，但是可以把這些

36、符號當作變量看待，并且對它們進行?抽象 ?zero:nat.?succ:nat?nat.succ(succ…(succ zero)…),7.3 非直謂式多態(tài)演算,類型名nat是任意選擇的，把這個符號也當作變量看待，并且對它進行?抽象?nat.?zero:nat.?succ:nat?nat.succ(succ…(succ zero)…)通常用更簡單的變量名寫出，作為自然數(shù)的一種有用表示(Church數(shù)碼)n?

37、 ? ?t.?f : t ? t.?x : t. f nx所有的Church數(shù)碼都具有類型nat ? ?t.(t ? t) ? t ? t,7.3 非直謂式多態(tài)演算,多態(tài)Church數(shù)碼上的加法和乘法運算是合成函數(shù)的形式mult ? ?x:nat.?y:nat.?t.?f: t?t.x t (y t f)add ? ?x:nat.?y:nat.?t.?f: t?t.?z:t.x t f (y t f z),7.3 非直謂式多

38、態(tài)演算,mult 2 3 ? (?x:nat.?y:nat.?t.?f: t?t.x t (y t f))(?t.?f : t ? t.?x : t. f 2x) (?t.?f : t ? t.?x : t. f 3x)= ?t.?f: t?t. (?t.?f : t ? t.?x : t. f 2x) t ((?t.?f : t ? t.?x : t. f 3x) t f)= ?t.?f: t?t. (?t.?f

39、 : t ? t.?x : t. f 2x) t (?x : t. f 3x)= ?t.?f: t?t. (?x : t. (?x : t. f 3x) ((?x : t. f 3x) x))= ?t.?f: t?t. (?x : t. (?x : t. f 3x) (f 3x))= ?t.?f: t ? t. ?x : t. f 6x? 6,7.3 非直謂式多態(tài)演算,還可以用一個正好帶兩個范式的類型來表示布爾值true ?

40、?t.?x:t.?y:t.xfalse ? ?t.?x:t.?y:t.ybool ? ?t.t?t?tzero? ? ?x:nat.x bool (?x:bool.false) true,7.3 非直謂式多態(tài)演算,7.3.3 歸約的終止性略去不介紹,7.4 數(shù)據(jù)抽象和存在類型,數(shù)據(jù)抽象以及相應(yīng)的程序規(guī)范和模塊性的概念可能是二十世紀七十年代有關(guān)程序設(shè)計語言最有影響的研究抽象數(shù)據(jù)類型的聲明，作為一種支持數(shù)據(jù)抽象的語言機制，已出現(xiàn)

41、在一些程序設(shè)計語言中，包括Ada、Clu和ML本節(jié)調(diào)查抽象數(shù)據(jù)類型聲明的一種一般形式,7.4 數(shù)據(jù)抽象和存在類型,形式為abstype t with x1: ?1, …, xk: ?k is ??, M1, …, Mk? in N的聲明描述抽象類型t例abstype stream withs: stream,first: stream ? nat,rest: stream?stre

42、amis??, M1, M2, M3?inN,7.4 數(shù)據(jù)抽象和存在類型,使用笛卡兒積，可以把任何抽象數(shù)據(jù)類型聲明寫成abstype t with x:? is ??, M? in N的形式抽象數(shù)據(jù)類型聲明可以加到直謂式或非直謂式語言中分別考慮抽象數(shù)據(jù)類型聲明和數(shù)據(jù)類型實現(xiàn)拓展類型表達式的語法，以包含存在類型? ::= … | ?t.?存在類型用于抽象數(shù)據(jù)類型的實現(xiàn)存在類型?t.?的每個元

43、素由一個類型?和類型[?/t]?的一個元素組成,7.4 數(shù)據(jù)抽象和存在類型,例：stream的實現(xiàn)總有類型?t. (t ? (t ? nat) ? (t ? t))抽象數(shù)據(jù)類型的實現(xiàn)將以?t =?, M:??的形式寫出，其中 t =?表示在該表達式的剩余部分將t約束到?? 稱為t的表示類型,7.4 數(shù)據(jù)抽象和存在類型,存在類型的公理和推理規(guī)則 (? Intro)? ? ?t = ?

44、, M :?? = ?s = ?, M : [s/t]??: ?t.?s在?中不是自由的下面規(guī)則允許把名字約束到數(shù)據(jù)類型實現(xiàn)的類型成分和值成分 (? Elim),7.4 數(shù)據(jù)抽象和存在類型,作為記號上的方便，把多于一個運算的聲明作為一種語法美化：abstype t with x1:?1, …, xn:?n is M in N ? abstype t with y:?1?

45、 … ??n is M in [Proj1 y, …, Projn y/x1, …, xn]N,n,n,7.4 數(shù)據(jù)抽象和存在類型,例: abstype cmplx withcreate: real ? real ? cmplx,plus: cmplx ? cmplx ? cmplx,re: cmplx ? realim: cmplx ? realis ?t = rea

46、l ? real, ?C, P, R, I?: (real ? real ?t) ? (t ? t ? t) ? (t ? real) ? (t ?real)?inN,7.4 數(shù)據(jù)抽象和存在類型,?C, P, R, I? :…?可以寫成：C = ?p: real ? real. pP = ??z: real ? real, w: real ? real?. ?Proj1 z + P

47、roj1 w, Proj2 z + Proj2 w?R = ?z: real ? real. Proj1 zI = ?z: real ? real. Proj2 z,7.4 數(shù)據(jù)抽象和存在類型,abstype的主要等式公理? ? (abstype t with x:? is ?t = ?, M:?? in N) = [M/x][?/t]N:? (?)?? ? (?x??.M)N =[N/x]

48、M :? (?)? ? abstype t with x:? is M in N =abstype s with y: [s/t]? is M in [y/x][s/t]N:? (?)?? ? ?x??.M =?y??.[y/x]M :? ??,其中y?FV(M) (?)? ? abstype t with x:? is y in ?t = t, x:?? = y: ?

49、t.? (?)? ? ? ?x??.(Mx) =M :? ??, 其中x? FV(M) (?),7.5 類型表達式的分類,7.5.1 類型表達式的種類 （1）7.2節(jié)把類型表達式分成兩個層次普通類型和多態(tài)類型在給出一些簡化約定的情況下，類型表達式可用文法分成同樣的兩個層次由于除了類型常量和類型變量外，只涉及函數(shù)類型，使得用文法推出的類型表達式都是良形的,7.5 類型表達式的分類,（2

50、）類型表達式分成小全域和大全域，不足以解決類型表達式是否為良形的問題在??? ?演算上再增加積類型或和類型時若類型變量t代表二元積類型，則fst(t)（取t的第一元）是良形的類型表達式，否則fst(t)不是良形的類型表達式這時良形的類型表達式很難用7.2節(jié)的文法形式表示,7.5 類型表達式的分類,（3）需要考慮類型表達式新的分類方式例如，所有的函數(shù)類型、所有的表類型、所有的二叉樹類型等，并且對類型表達式的量化是以這樣的類型族

51、為論域可以通過豐富語言結(jié)構(gòu)來解決這些問題用類型對項進行分類用較高層次的種類（kind）來對類型進行分類當前很多研究工作中的類型系統(tǒng)都是按這種思路來設(shè)計,7.5 類型表達式的分類,??? ?, ?演算有項、類型和種類三種語法范疇語法范疇項目具體形式種類?::= Type | ? ?? | ? ??類型?::= b | t | ? ?? | ? ?? | fst(?)

52、 | snd(?) | ?t:?.? | ??項M ::= c | x | ?x:?.M | MM | ?M, N?| Proj1M | Proj2M | ?t:?.M | M?種類文法產(chǎn)生的任何種類表達式都是良形的符號?和?在這里是重載的基本類型和普通函數(shù)類型歸到Type種類,7.5 類型表達式的分類,??? ?, ?演算有項、類型和種類三種語法范疇語法范疇項目具體形式種類?::

53、= Type | ? ?? | ? ??類型?::= b | t | ? ?? | ? ?? | fst(?) | snd(?) | ?t:?.? | ??項M ::= c | x | ?x:?.M | MM | ?M, N?| Proj1M | Proj2M | ?t:?.M | M?任意兩個類型，它們的積屬于某個積種類?1??2由?t:?.?表示的類型上的函數(shù)屬于某個函

54、數(shù)種類????,7.5 類型表達式的分類,7.5.2 類型表達式的定類與相等類型表達式的定類（kinding）斷言斷言的形式為? ? ? : ?，其中定類上下文? 是形式為? = {t1 : ?1, …, tn : ?n} 其中dom(?) = {t1, …, tn}類似于項的定型斷言? ? M : ?,7.5 類型表達式的分類,7.5.2 類型表達式的定類與相等類型表達式的定類（kindin

55、g）斷言斷言的形式為? ? ? : ?，其中定類上下文? 是形式為? = {t1 : ?1, …, tn : ?n} 其中dom(?) = {t1, …, tn}它給類型變量進行種類指派，類似于項的定型斷言? ? M : ?,7.5 類型表達式的分類,定類規(guī)則? ? b : Type（每個類型常量b : Type） (cstt)t : ? ? t : ? (vark)

56、 (add vark) (WF-Type) (?k Intro),7.5 類型表達式的分類,定類規(guī)則 (?k Elim)1 (?k Elim)2 (?k Intro) (?k Elim),7.5 類型表達式的分類,類型表達式的相等規(guī)則

57、(Projt)1(Projt)2 (spt)? ? (?t:?.?) = (?t?:?.[t?/t]?) : ? ? ?? 其中t??FV(?) (?t),7.5 類型表達式的分類,類型表達式的相等規(guī)則 (?t) (?t)上述類型表達式的定類規(guī)

58、則和相等規(guī)則給出了類型表達式上一個簡單的演算系統(tǒng)類型表達式被稱為語言的靜態(tài)數(shù)據(jù)，而項被稱為語言的動態(tài)數(shù)據(jù),7.5 類型表達式的分類,7.5.3 項的定型定型斷言? ? ? M : ?種類指派? = {t1 : ?1, …, tn : ?n}類型指派 ? = {x1 : ?1, …, xn : ?n}?和?都是無序集合，兩者的次序不能顛倒下面默認：出現(xiàn)定型公理和推理規(guī)則的?在定類上下文?下都是良種類的類型表達式?

59、 ? ? c : ?（對基調(diào)中的每個項常量c : ?）(cst)? ?, x :? ? x :? (var),7.5 類型表達式的分類,(add var) (? Intro) (? Elim) (? Intro),7.5 類型表達式的分類,(? Elim)1 (? E