第7章多態(tài)性(參考版)
2025-07-23 12:28本頁(yè)面
【正文】 第 7章 多態(tài)性 ? 本章和下一章介紹類型論的一些概念，它們是程序設(shè)計(jì)語(yǔ)言的多態(tài)性和數(shù)據(jù)抽象的基礎(chǔ) ? 這些概念與下面的語(yǔ)言概念有關(guān) – Ada的程序包和類屬 – C??的模板 – ML以及相近語(yǔ)言 Miranda和 Haskell的多態(tài)性、抽象類型和模塊等 – 現(xiàn)實(shí)語(yǔ)言出于效率上的考慮，所采用的副本沒(méi)有相應(yīng)的類型化 ?演算那么靈活 引 言 ? 本章的主要內(nèi)容 – 多態(tài)類型系統(tǒng)的語(yǔ)法，包括直謂式的，非直謂式的和 type: type版本 – 直謂式多態(tài) ?演算，包括和其它兩個(gè)系統(tǒng)之間的聯(lián)系，它的等式證明系統(tǒng)和歸約、多態(tài)聲明 – 非直謂式多態(tài) ?演算的縱覽 – 數(shù)據(jù)抽象和存在類型 – 類型表達(dá)式的分類 引 言 類型作為函數(shù)變?cè)? ? 簡(jiǎn)單類型化 ?演算有某種明顯的缺點(diǎn) – 很多有計(jì)算意義且有用的表達(dá)式不是良類型的 – 排序函數(shù)：希望能應(yīng)用于許多不同類型的數(shù)據(jù) Sort : (t ? t ? bool ) ? Array[prt t] ? Array [prt t] ? 多態(tài)函數(shù) – 變?cè)念愋涂梢杂卸喾N不同的情況 – 通過(guò)拓展 ?抽象到允許對(duì)類型進(jìn)行 ?抽象，可以把??拓展到包括多態(tài)函數(shù) 引 言 ? 再以更簡(jiǎn)潔一些的函數(shù)合成運(yùn)算為例 posenat, nat, nat ? ?f : nat ? nat.?g: nat ? nat.?x: (g x) posenat, nat ? nat, nat ? ?f : (nat ? nat) ? nat. ?g: nat ? (nat ? nat).?x: (g x) poser, s, t ? ?f : s ? t.?g: r ? s.?x: (g x) pose ? ?r : T. ?s: T. ?t: T. poser, s, t 引 言 ? 考察 pose ? ?r:T. ?s:T. ?t:T. poser, s, t – 對(duì) T（類型的集合） 有幾種可能的解釋 – 類型應(yīng)用 pose nat nat nat = (?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) – pose的類型是什么？ 引 言 ? 以多態(tài)恒等函數(shù)為例 Id ? ?t : T. ?x : t. x – Id的定義域是 T， 但 值域難以描述 – 一種表示： Id : (?t :T? t ? t) ?t :T? t ? t是 無(wú)限積 ?t ?T t ? t ： (nat ? nat) ? (bool ? bool) ? . . . (idnat ? nat, idbool ? bool, . . .)是該類型的一個(gè)值 Id nat = ?x : nat. x = idnat ? nat Id bool = ?x : bool. x = idbool ? bool – 代換僅在 Id的類型上完成，而不是在函數(shù)本身上完成 引 言 ? 以多態(tài)恒等函數(shù)為例 Id ? ?t : T. ?x : t. x – Id的定義域是 T， 但 值域難以描述 – 一種表示： Id : (?t :T? t ? t) – 另一種表示： Id : ?t: T. t ? t ?t: T. t ? t是所有下述函數(shù)構(gòu)成的類型： 每個(gè)函數(shù)對(duì)所有的 t:T， 給出從 t 到 t 的一個(gè)映射 – 下面先只考慮第一種表示法 引 言 ? 對(duì) T有三種自然的選擇 為多態(tài)函數(shù)引入類型后，必須決定這些類型怎樣 來(lái)適合現(xiàn)在的類型系統(tǒng) 直謂式多態(tài)性 – T僅含用 ?、 ?和 ?或 ?及一組類型常量定義的類型 – 這是在已經(jīng)定義了 T的所有成員后才引入 T 非直謂式多態(tài)性 – T還包含所有的多態(tài)類型（例如 ?t: T. t ? t）， 但不把 T本身作為一個(gè)類型 引 言 ? 對(duì) T有三種自然的選擇 為多態(tài)函數(shù)引入類型后，必須決定這些類型怎樣 來(lái)適合現(xiàn)在的類型系統(tǒng) 直謂式多態(tài)性 非直謂式多態(tài)性 type : type – 令 T包含所有的類型，包括它本身 – 從計(jì)算的觀點(diǎn)看，并非立即能看清楚： 引入“所有類型的類型”后會(huì)引起什么錯(cuò)誤 引 言 ? 三種多態(tài)性之間的簡(jiǎn)單區(qū)別 直謂式多態(tài)性 – Id僅能夠應(yīng)用于非多態(tài)類型 ， 例如 nat 或 (nat ? nat) – Id (nat ? nat) = ?x : nat ? nat. x 2. 非直謂式多態(tài)性 – Id可以應(yīng)用到任何類型 – Id (?t: T. t ? t) = ?x : (?t: T. t ? t). x – 不可能把每個(gè)多態(tài) ?項(xiàng)都解釋成集合論的函數(shù) Id = {??, ?x:?. x? | ? ?T}， 其中序?qū)? ?(?t: T. t ? t), ?x: (?t: T. t ? t). x ? 的第一元包含 Id 引 言 ? 三種多態(tài)性之間的簡(jiǎn)單區(qū)別 直謂式多態(tài)性 – Id (nat ? nat) = ?x : nat ? nat. x 2. 非直謂式多態(tài)性 – Id (?t: T. t ? t) = ?x : (?t: T. t ? t). x type : type Id T = ?x:T. x (Id T): T ? T 引 言 ? 參數(shù)多態(tài)性和特定多態(tài)性 參數(shù)化多態(tài)性 – 一個(gè)多態(tài)函數(shù)對(duì)任何類型都使用“本質(zhì)上一樣的算法” 特定多態(tài)性 – 可以 測(cè)試類型變?cè)闹担鶕?jù)它的類型類型選擇某個(gè)分支 ad_hoc_pose ? ?r: T. ?s: T. ?t: T.?f : s ? t. ?g: r ? s. ?x: r. if Eq? s t then f (f (g x)) else f (g x) 直謂式多態(tài)演算 類型和項(xiàng)的語(yǔ)法 ? ??? ?的類型分成兩類 – ??類型 全域 U1 “小”全域 – 用 ?構(gòu)造的多態(tài)類型 全域 U2 “大”全域 ? 各類表達(dá)式（上下文、類型表達(dá)式、項(xiàng)）的語(yǔ)法各由一個(gè)斷言證明系統(tǒng)給出 ? 在 ??? ?中 將使用形式為 ? ? A: B的斷言 – ?是上下文，指出每個(gè)變量的類型或全域 – A是類型表達(dá)式，則 B是 U1， U2 – A是項(xiàng)，則 B是 類型表達(dá)式 直謂式多態(tài)演算 ? 良形上下文的公理和推理規(guī)則 – 上下文是一個(gè)有序序列，它給變量以類型或全域 ?= v1 : A1, …, vk : Ak – 每個(gè) Ai必須僅在假設(shè) v1 : A1, …, vi 1 : Ai–1下就可證明為良形的 – 可以使用公理和推理規(guī)則來(lái)將它形式化 – 例： ?t : U1.?x : t ? t.?y: t. xy 確定 xy類型時(shí)的上下文： t : U1, x : t ? t, y: t 直謂式多態(tài)演算 ? 良形上下文的公理和推理規(guī)則 ? context (empty context) t不在 ?中 (U1 context) x不在 ?中 (Ui type context) ? context ?, t : U1 context ? ? ? : Ui ?, x : ? context 直謂式多態(tài)演算 ? 良形上下文的公
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1