泛代數(shù)和代數(shù)數(shù)據(jù)類型.ppt

第3章 泛代數(shù)和代數(shù)數(shù)據(jù)類型,PCF語言的三部分組成 帶函數(shù)和積類型的純類型化演算 自然數(shù)類型和布爾類型 不動點算子 第3章到第5章對這三部分進行透徹的研究 本章研究像自然數(shù)類型和布爾類型這樣的代數(shù)數(shù)據(jù)類型,3.1 引 言,代數(shù)數(shù)據(jù)類型包括 一個或多個值集 一組在這些集合上的函數(shù) 基本限制是其函數(shù)不能有函數(shù)變元 基本“類型”符號被稱為“類別” 泛代數(shù)（也叫做等式邏輯） 定義和研究代數(shù)數(shù)據(jù)類型的一般數(shù)學框架 本章研究泛代數(shù)和它在程序設計中定義常用數(shù)據(jù)類型時的作用,3.1 引 言,本章主要內(nèi)容： 代數(shù)項和它們在多類別代數(shù)中的解釋 等式規(guī)范（也叫代數(shù)規(guī)范）和等式證明系統(tǒng) 等式證明系統(tǒng)的可靠性和完備性（公理語義和指稱語義的等價） 代數(shù)之間的同態(tài)關系和初始代數(shù) 數(shù)據(jù)類型的代數(shù)理論 從代數(shù)規(guī)范導出的重寫規(guī)則（操作語義） 大多數(shù)邏輯系統(tǒng)中一些公共的議題將被覆蓋,3.2 代數(shù)、基調和項,3.2.1 代數(shù) 代數(shù) 一個或多個集合，叫做載體 一組特征元素和一階函數(shù)，也叫做代數(shù)函數(shù) f : A1 Ak A 例：N N, 0, 1, +, 載體N是自然數(shù)集合 特征元素0, 1N，也叫做零元函數(shù) 函數(shù)+, : N N N,3.2 代數(shù)、基調和項,多個載體的例子 Apcf N, B, 0, 1, , +, true, false, Eq ?, 下面開始逐步給出代數(shù)的一種語法描述，有窮的語法表示在計算機科學中十分重要 定義數(shù)據(jù)類型 證明性質 進行化簡 還必須討論這種語法描述的語義 A5pcf N5, B, 0, 1, 2, 3, 4, +5, true, false, Eq ?, ,3.2 代數(shù)、基調和項,3.2.2 代數(shù)項的語法 基調 S，F(xiàn) S是一個集合，其元素叫做類別 函數(shù)符號f : s1 sk s的集合F ，其中表達式s1 sk s叫做類型 零元函數(shù)符號叫做常量符號 例N S，F(xiàn) sorts : nat fctns : 0, 1 : nat , : nat nat nat,3.2 代數(shù)、基調和項,定義基調的目的是用于寫代數(shù)項 考慮項中有變量的情況，需假定有一個無窮的符號集合V，其元素稱為變量 類別指派 x1 : s1, , xk : sk 基調 S，F(xiàn)和類別指派上類別s的代數(shù)項集合Termss (, ) 如果x : s ，那么x Termss (, ) 如果f : s1 sk s并且Mi Termssi(, ) (i 1, , k)，那么f M1 Mk Termss (, ) 當k 0時，如果f : s，那么f Termss (, ),3.2 代數(shù)、基調和項,例 0, 0 1 Termsnat (N, ) 0 x Termsnat (N, )，其中 x : nat, 代數(shù)項中無約束變元，NxM就是簡單地把M中x的每個出現(xiàn)都用N代替就是了 記號 , x : s x : s 引理 如果M Termss (, , x : s)并且N Termss(, )，那么NxM Termss (, ) 證明 按Termss(, )中項的結構進行歸納,3.2 代數(shù)、基調和項,例 用基調stk S, F來寫自然數(shù)和棧表達式 sorts : nat, stack fctns : 0, 1, 2, : nat , : nat nat nat empty : stack push : nat stack stack pop : stack stack top : stack nat push 2 (push 1 (push 0 empty) )是該基調的項,3.2 代數(shù)、基調和項,3.2.3 代數(shù)以及項在代數(shù)中的解釋 代數(shù)是為代數(shù)項提供含義的數(shù)學結構 是一個基調，則代數(shù)A包含 對每個s S，正好有一個載體As 一個解釋映射I 把函數(shù)I (f ) : As1 Ask As指派給函數(shù)符號 f : s1 sk s F 把I (f ) As指派給常量符號f : s F N代數(shù)N寫成 N N, 0N, 1N, N, N,3.2 代數(shù)、基調和項,代數(shù)A的環(huán)境 : V s As 環(huán)境 滿足 如果對每個x : s 都有(x)As M Termss (, )的含義AM Ax (x) AM f A (AM1, , AMk) 若f : s是常量符號，則Af f A A清楚時，省略A而直接寫成M 不依賴于時，用AM表示M在A中的含義,3.2 代數(shù)、基調和項,例 若(x) 0N x 1 N(x,1) N (x), 1N) N (0N, 1N) 1N,3.2 代數(shù)、基調和項,例 Astk N, N, 0A, 1A, , A, A, emptyA, pushA, pop A, top A empty A , 空序列 push A (n, s) n : s pop A(n : s) s pop A( ) top A(n : s) n top A( ) 0 A 若把x : nat映射到3A，把s : stack映射到2A,1A pop(push x s) popA(pushA( x ,s) ) popA(pushA(3A, 2A, 1A ) ) popA( 3A, 2A, 1A ) 2A, 1A ,3.2 代數(shù)、基調和項,引理 令A是一個代數(shù)，M Termss (, )，并且是滿足的環(huán)境，那么M As 證明 根據(jù)Termss (, )中項的結構進行歸納 引理 令x1, , xk是由出現(xiàn)在M Termss (, )中的所有變量構成的變量表，1和2是滿足的兩個環(huán)境, 并且對i 1, , k有1(xi) 2(xi), 那么M1 M2 證明 基于項結構的歸納,3.2 代數(shù)、基調和項,3.2.4 代換引理 引理 令M Termss (, , x : s)并且 N Termss(, )，那么NxMTermss(, )。并且對任何環(huán)境，有 NxM M(x a)， 其中a N是N在下的含義 證明 根據(jù)項M的結構進行歸納,3.3 等式、可靠性和完備性,3.3.1 等式 代數(shù)規(guī)范：一個基調 + 一組等式 調查什么樣的代數(shù)滿足這些等式強加的要求 使用等式證明系統(tǒng)可推導新的等式 可靠性：從規(guī)范可證明的等式在任何滿足該規(guī)范的代數(shù)中都成立 完備性：在滿足規(guī)范的所有代數(shù)中都成立的等式都可從該規(guī)范證明 代數(shù)規(guī)范是描述代數(shù)數(shù)據(jù)類型公理語義的工具,3.3 等式、可靠性和完備性,空載體提出一個技術問題 邏輯公式 若A = ，則公式x:A. F(x) 為真 若A = ，則公式x:A. F(x) 為假 對任意的M, N Termss (, )，如果x : s 且As為空，那么M和N看成是相等的項 只有一個類別時，假定該類別非空是有意義的,3.3 等式、可靠性和完備性,等式 公式M N 對某個s，M, N Termss (, ) 如果滿足，那么若M N，就說代數(shù)A在環(huán)境下滿足M N，寫成 A, M N 若A在任何環(huán)境下都滿足，寫成 A M N 如果一類代數(shù)C中的任何一個代數(shù)A都滿足，寫成 C M N 任何一個代數(shù)都滿足等式M N，寫成 M N (永真的、有效的 ),3.3 等式、可靠性和完備性,如果A滿足上的所有等式，就說代數(shù)A是平凡的 例 令有兩個類別a和b，令A是一個代數(shù)，其中Aa0,1并且Ab。 A不可能滿足x yx : a, y : a，即下式不成立 A x yx : a, y : a 但是A x yx : a, y : a, z : b無意義地成立,3.3 等式、可靠性和完備性,3.3.2 項代數(shù) 項代數(shù)Terms(, ) 類別s的載體：集合Termss (, ) 函數(shù)符號f : s1 sk s的解釋 I (f ) (M1, , Mk) f M1 Mk 項代數(shù)Terms(, )的環(huán)境也叫做一個代換 如果S是代換，則用SM表示同時把M中的各個變量x用Sx替換的結果 因此用M表示把代換作用于M的結果,3.3 等式、可靠性和完備性,例 類別u 函數(shù)符號f : u u和g : u u u a : u, b : u, c : u Tu a, b, c, fa, fb, fc, gaa, gab, gac, gbb, , g (f ( fa ) ) (f (gbc) ), 若環(huán)境把變量x映射到a，把y映射到f b，則 T g(f x) (f y) g(f a) (f ( f b) ),3.3 等式、可靠性和完備性,引理 令M Terms(, )，并且是滿足的項代數(shù)Terms(, )的環(huán)境，那么M M 證明 對項進行歸納證明 從項代數(shù)可以知道，只有M和N是語法上相同的項時，等式M N才會永真,3.3 等式、可靠性和完備性,代數(shù)規(guī)范Spec , E : 一個基調和一組等式E 語義蘊涵：E M N 滿足E的所有代數(shù)A都滿足等式M N 語義理論： 如果E M N蘊涵M N E 代數(shù)A的理論Th(A) 在A中成立的所有等式的集合 這是一個語義理論,3.3 等式、可靠性和完備性,證明系統(tǒng)的可靠性：若一個等式從一組假設E是可證明的，那么E語義上蘊涵該等式 證明系統(tǒng)的完備性：如果E語義上蘊涵一個等式，那么該等式可從E證明 下面先給出代數(shù)證明系統(tǒng),3.3 等式、可靠性和完備性,語義相等是個等價關系，因此有 M M 在等式中增加類別指派的規(guī)則 等價代換 P , Q Termss(, ),3.3 等式、可靠性和完備性,等式是可證明：如果從E中的等式和公理(ref)及推理規(guī)則(sym)、(trans)、(subst) 和(add var) 可以推出等式M N，那么就說該等式可證明，寫成 E M N 語法理論 如果E M N蘊涵M N E E的語法理論Th(E) 從E可證明的所有等式的集合,3.3 等式、可靠性和完備性,等式集合E是語義一致的 如果存在某個等式M N，它不是E的語義蘊涵 等式集合E是語法一致的 如果存在某個等式M N，它不能由E證明,3.3 等式、可靠性和完備性,例 在基調stk S, F上增加等式 top (push x s ) = xs : stack, x : nat pop (push x s ) = ss : stack, x : nat 使用這些等式可以證明等式 top (push 3 empty ) = 3,3.3 等式、可靠性和完備性,導出規(guī)則 f : s1 sk s Mi, NiTermssi(, ) M和N中沒有x，Termss(, )非空,3.3 等式、可靠性和完備性,定理（可靠性）如果E M N ， 那么E M N 證明 可以根據(jù)該證明的長度進行歸納 歸納基礎：長度為1的證明，它是公理或E的一個等式 歸納假設： M N的最后一步是從E1, , En得到。那么，如果A E，則A滿足E1, , En 要證明：如果A滿足最后一條規(guī)則的這些前提，那么A滿足M N 證明 根據(jù)證明規(guī)則的集合，分情況進行分析,3.3 等式、可靠性和完備性,命題 存在一個代數(shù)理論E和不含x的項M和N，使得E M=N, x : s，但是E M=N 證明 令基調有類別a和b，函數(shù)符號f : a b和c, d : b 令E是包含能從 f x = cx : a和 f x = d x : a證明的所有等式 顯然c = d x : a E 可以找到一個使等式c = d 不成立的模型 由可靠性，c = d 是不可能從E證明的,3.3 等式、可靠性和完備性,例 棧代數(shù)規(guī)范 sorts : nat, stack fctns : 0, 1, 2, : nat +, : nat nat nat empty : stack push : nat stack stack pop : stack stack top : stack nat eqns : s : stack; x : nat 0 + 0 = 0, 0 + 1 = 1, 0 0 = 0, 0 1 = 0, top (push x s ) = x pop (push x s ) = s,3.3 等式、可靠性和完備性,等式push (top s) (pop s) = ss : stack是不可證明的 任何形式為 top empty = M 的等式都是不可證明的，假定M是類別為nat的項，并且不含empty,3.3 等式、可靠性和完備性,3.3.4 完備性的形式 用于不同邏輯系統(tǒng)的三種形式的完備性 最弱的形式：所有的永真公式都是可證的 演繹完備性：每個語義蘊涵在證明系統(tǒng)中都是可推導的 最小模型完備性：每個語法理論是某一個“最小”模型的語義理論 對代數(shù)來說，最小模型完備性意味著每個語法理論是某個代數(shù)A的Th(A) “最小模型”是指它的理論包含的內(nèi)容最少,3.3 等式、可靠性和完備性,最小模型完備性不一定成立，考慮等式 E =def x = y x : a, y : a, z : b 情況1：a的載體只含一個元素，則E滿足，此時 E1 =def x = y x : a, y : a 成立 情況2： b的載體為空，則E也滿足，此時 E2 =def z = w z : b, w : b 成立 E1和E2都不是E的語義蘊涵 不存在一個代數(shù)，其理論正好就是由E的等式推論組成的語法理論,3.3 等式、可靠性和完備性,3.3.5 同余、商和演繹完備性 同余關系：等價關系加上同余性 同余性：指函數(shù)保可證明的相等性 對單類代數(shù)A = A, f1A, f2A,，同余關系是載體A上的等價關系，使得對每個k元函數(shù)fA，如果aibi(i=1, k)，即ai和bi等價，那么f A(a1, , ak ) fA (b1, , bk )。 對多類代數(shù)A = As, I ，同余關系是一簇等價關系 s, s AsAs，使得對每個f : s1 sks及變元序列a1, , ak和b1, , bk(其中ai sibi Asi),有f A (a1, , ak ) s f A (b1, , bk ),3.3 等式、可靠性和完備性,A模的商的代數(shù)A 把A中有關系的元素a a 壓縮成A的一個元素 等價類a a a As a a 商代數(shù)A定義： (A)s是由As的所有等價類構成的集合 Ass as a As 函數(shù)fA由A的函數(shù)fA確定： 對適當載體的a1, ak， f A (a1, , ak) = f A (a1, , ak),3.3 等式、可靠性和完備性,上面定義有意義的條件是f A (a1, , ak)必須只依賴于a1, , ak，而不能依賴于所選的代表a1, , ak。 例 單類別代數(shù)N，0，1，上的同余關系“模k等價” 這個商代數(shù)是大家熟悉的整數(shù)模k加結構。如果k等于5，那么3 4 2,3.3 等式、可靠性和完備性,如果是A的一個環(huán)境，是一個同余關系，那么A的環(huán)境 定義如下： (x) = (x) 反過來，對于A的環(huán)境，對應它的A的環(huán)境有多種選擇 引理 令是代數(shù)A上的同余關系，項MTerms(, )并且是滿足的環(huán)境。那么項M在商代數(shù)A 和環(huán)境下的含義(A)M由下式?jīng)Q定 (A)M = AM,3.3 等式、可靠性和完備性,引理 令E是一組等式集合，令Terms(, )是基調上的項集。由E的可證明性確定的關系E,是Terms(, )上的同余關系 定理（ 完備性）如果E M N ， 那么E M N 完備性定理加上可靠性定理表明語法理論和語義理論相同,3.3 等式、可靠性和完備性,3.3.6 非空類別和最小模型性質 類別s非空：集合Termss(, )不是空集 對應的載體肯定非空 沒有空載體時，可以增加推理規(guī)則(nonempty) 定理 令E是封閉于規(guī)則（nonempty）的語法理論，那么存在所有載體都非空的代數(shù)A，使得E Th (A) 沒有空載體的代數(shù)有最小模型完備性,3.4 同態(tài)和初始性,3.4.1 同態(tài)和同構 將同態(tài)和同構的概念從單類代數(shù)推廣到多類代數(shù) 同態(tài)是從一個代數(shù)到另一個代數(shù)的保結構的映射（或叫做翻譯） 從代數(shù)A到B的同態(tài)h : A B 一簇映射h = hs | s S ，使得對的每個函數(shù)符號f : s1 sk s，有 hs (f A (a1, , ak) ) = (f B (hs1a1, , hskak) ),3.4 同態(tài)和初始性,例 令N = N, 0, 1, ，令是模k的等價關系。那么把nN映射到它的等價類n是從N到N的一個同態(tài)，因為 h (0) = 0N = 0 h (n + m) = h (n) N h (m) = n + m 任何代數(shù)到它商代數(shù)的同態(tài)都用這種方式定義,3.4 同態(tài)和初始性,例 含義函數(shù)是從項代數(shù)T = Terms(, )到任意代數(shù)A的一個同態(tài)h : T A。如果是A的一個滿足的環(huán)境，該同態(tài)的定義是 h(M) = AM 這是一個同態(tài)，因為 h (f M1 Mk ) = Af M1 Mk = f A(AM1 AMk) = f A(h (M1 ) h (Mk ) ),3.4 同態(tài)和初始性,引理 令h : A B是任意同態(tài)，并且是滿足類別指派的任意A環(huán)境。那么對任何項M Terms(, )，有 h (AM) = BMh 當M中不含變量時，h (AM) =BM 證明 基于項的歸納 引理 如果h : A B和k : B C都是代數(shù)的同態(tài)，那么合成k h : A C也是代數(shù)的同態(tài)。 ( (k h)s = ks hs ) 同構 一個雙射的同態(tài), 寫成A B,3.4 同態(tài)和初始性,3.4.2 初始代數(shù) C是一類代數(shù)并且AC，若對每個BC，存在唯一的同態(tài)h : A B，那么A在C中叫做初始代數(shù) 初始代數(shù)是“典型”的 初始代數(shù)有盡可能少的非空載體 初始代數(shù)滿足盡可能少的閉等式,3.4 同態(tài)和初始性,例 基調0 類別nat， 函數(shù)符號0 : nat和S : nat nat。 令C是所有0代數(shù)構成的代數(shù)類 閉項代數(shù)T Terms(0, )是C的初始代數(shù) 它的載體是所有閉項0, S (0), , S k(0), 該代數(shù)的函數(shù)S把Sk(0)映射到Sk1(0) 該代數(shù)的元素少到能解釋所有的函數(shù)符號 該代數(shù)滿足項之間盡可能少的等式,3.4 同態(tài)和初始性,引理 假定h : A B和k : B A都是同態(tài)，并且h k=IdB，k h =IdA。那么A和B同構 命題 如果A和B在代數(shù)類C中都是初始代數(shù)，那么A和B是同構的 命題 令E是一組等式，并且令A = Terms(, )E, 是?？勺C明的相等性的代數(shù)。那么，A對E來說是初始代數(shù) 由項代數(shù)和商的性質可知，從E可證明的等式在A中都成立 還要證明從A到任何滿足E的代數(shù)有唯一的同態(tài),3.4 同態(tài)和初始性,例 基調1：類別nat；函數(shù)符號0 : nat，S : nat nat和 : nat nat nat；等式集合E： x + 0 = x x + (Sy) = S (x + y) Sk0 + Sl0 = Sk + l0 對任何閉項M，存在某個自然數(shù)k，使得M = Sk0 等式Sk0 = Sl0是不可證明的，除非k = l 每個等價類正好包含一個形式為Sk0的項 等價類和形式為Sk0的項集間有一個雙射 載體看成由閉項0, S0, , Sk0, 構成的集合，函數(shù)S映射Sk0 Sk10，映射(Sk0, Sl0) Skl0，得一個初始代數(shù) 這個初始代數(shù)和該基調的標準模型（有后繼算子和加法的自然數(shù)） 同構,3.4 同態(tài)和初始性,該規(guī)范的初始代數(shù)可以和其它有更多或較少元素的代數(shù)相對照 如果一個代數(shù)有更多元素的話，那么這些多余的元素不能由項定義。（有假貨） 整數(shù)代數(shù)Z A = Anat, 0A, SA, +A Anat = (0 N) (1 Z) 0A = 0, 0 SAi, n = i, n +1 i, n +A j, m = max(i, j), n +m 如果一個代數(shù)有較少元素的話，那么就有一些不能被證明為相等的有區(qū)別的元素被等同。（出現(xiàn)混淆） 模k的自然數(shù),3.4 同態(tài)和初始性,初始代數(shù)可能滿足不能由E證明的額外的等式 例 上面的自然數(shù)基調例子中，初始代數(shù)滿足等式 x + y = y + x 因為 E M = Sk0和E N = Sl0 蘊涵 E M + N = Sk+l0 = N + M 不滿足交換性的代數(shù) Anat是所有f : X X的函數(shù)的集合（X至少有兩個元素） 0A是X上的恒等函數(shù)，SA是Anat上的恒等映射 +A是Anat上的函數(shù)合成 A = Anat 0A SA +A 滿足E +A沒有交換性，因為函數(shù)合成沒有交換性,3.4 同態(tài)和初始性,基項、基代換、基實例（項、等式） 如果M N是Termss(, )的項之間的等式，并且S是一個，基代換，那么就把SM SN稱為M N的基實例 命題 令E是一組等式，并且A對E來說是初始代數(shù)。對任何等式M N，下面三個條件等價 A滿足M N A滿足M N的每一個基實例 M N的每一個基實例都可以從E證明,3.5 代數(shù)數(shù)據(jù)類型,3.5.1 代數(shù)數(shù)據(jù)類型 很多數(shù)據(jù)類型 不存在標準的數(shù)學構造 沒有單一和標準的計算機實現(xiàn) 列出它們的操作并描述這些操作的行為 公理化地定義而不是由數(shù)學構造來定義 對于一個數(shù)據(jù)類型，是否可以斷定有了“足夠”的公理 本節(jié)討論數(shù)據(jù)類型公理化方法的一般特征,3.5 代數(shù)數(shù)據(jù)類型,數(shù)據(jù)抽象的一般原理 抽象數(shù)據(jù)類型由它的規(guī)范定義。使用這樣數(shù)據(jù)類型的程序應該只依賴于由它的規(guī)范保證的性質，而不依賴于它的任何特定實現(xiàn) 一個數(shù)據(jù)類型的函數(shù)可以劃分成 構造算子：產(chǎn)生該數(shù)據(jù)類型的一個新元素 運算算子：是該數(shù)據(jù)類型上的函數(shù)，但不產(chǎn)生新的元素 觀察算子：作用于該數(shù)據(jù)類型的元素，但返回某其它類型的元素，如自然數(shù)或布爾值,3.5 代數(shù)數(shù)據(jù)類型,3.5.2 初始代數(shù)語義和數(shù)據(jù)類型歸納 代數(shù)規(guī)范有幾種不同的“語義”形式 寬松語義：滿足一個代數(shù)規(guī)范的所有代數(shù)所構成的代數(shù)類 初始代數(shù)語義：滿足一個代數(shù)規(guī)范的所有初始代數(shù)所構成的同構類 終結代數(shù)語義：滿足一個代數(shù)規(guī)范的所有終結代數(shù)所構成的同構類 生成語義：滿足一個代數(shù)規(guī)范的所有生成代數(shù)所構成的代數(shù)類,3.5 代數(shù)數(shù)據(jù)類型,初始代數(shù)的性質 沒有假貨 沒有混淆 支持基于數(shù)據(jù)類型構造符的歸納 構造符集合 Spec , E的函數(shù)符號子集F0，使得Terms(,)E,的每個等價類正好只含一個由F0的函數(shù)符號所構成的基項 可以基于對構造符的歸納來證明初始代數(shù)的性質,3.5 代數(shù)數(shù)據(jù)類型,sorts: set, nat, bool 構造符、運算符、觀察符 fctns: 0, 1, 2, : nat + : nat nat nat Eq? : nat nat nat true, false bool empty : set insert : nat set set union : set set set ismem? : nat set bool condn : bool nat nat nat . . . eqns: x, y : nat, s, s : set, u, v : bool 0 + 0 = 0, 0 +1= 1, 1 +1 = 2, . . . Eq? x x = true Eq? 0 1 = false, Eq? 0 2 = false, . . . ismem? x empty = false ismem? x (insert y s) = if Eq? x y then true else ismem ? x s union empty s = s union (insert y s) s = insert y (union s s) condn true x y = x condn false x y = y . . .,3.5 代數(shù)數(shù)據(jù)類型,終結代數(shù) 在一個代數(shù)類C中，如果從每個BC到AC，都存在唯一的同態(tài)，那么代數(shù)A是終結代數(shù) 一個代數(shù)類中的所有終結代數(shù)都同構 若用終結代數(shù)作為語義，則稱之為終結語義 如果所有載體都是單元素集合的代數(shù)也在C中，則這個代數(shù)一定是C的終結代數(shù),3.5 代數(shù)數(shù)據(jù)類型,初始語義和終結語義 初始語義：不能證明為相等的就是不相等的 終結語義：不能證明為不相等的則是相等的 如果把某些類別的解釋固定，而其它類別的解釋用終結語義，則它是一個有用的方法 從初始語義角度看，前面給出的不是集合的規(guī)范,而是表的規(guī)范。因為不能證明 insert x(insert y z)=insert y(insert x z) x: nat, y: nat, z: set insert x (insert x z) = insert x zx : nat, z : set 若用終結語義，且bool的解釋固定,則為集合規(guī)范,3.5 代數(shù)數(shù)據(jù)類型,3.5.3 解釋沒有意義的項 表達式?jīng)]有意義的情況 除法是一個部分函數(shù)，除數(shù)為零的表達式?jīng)]意義 調用不終止的函數(shù)也構成一個沒有意義的表達式 如果想在代數(shù)規(guī)范中表示這些情況，必須在基調中增加表示錯誤的項（簡稱錯誤值） 怎樣規(guī)定這些項的值？有三種可能： 什么也不規(guī)定 任意做一個決定 非常仔細地說明什么是所需要的,3.6 重寫系統(tǒng),3.6.1 基本定義 重寫系統(tǒng)：用于代數(shù)項的歸約系統(tǒng) 兩種重要的應用 為代數(shù)項提供一種計算模型 自動定理證明 由一組叫做重寫規(guī)則(LR)的有向等式組成 限制：Var(R) Var(L) 由R 確定的一步歸約關系R SLxM R SRxM 關系 R是R的自反傳遞閉包,3.6 重寫系統(tǒng),sorts : nat fctns : 0 : nat : nat nat + : nat nat nat 在這個基調上的一些歸約規(guī)則如下： x 0 x x + (x) 0 (x y ) z x + (y + z) 實例：(x y ) (y) x + (y + (y) x 0 x,3.6 重寫系統(tǒng),引理（歸約保類別 ） 令R是上的重寫系統(tǒng).如果M Termss (, )，并且M R N，那么N Termss (, ) 關系 （重寫系統(tǒng)）是合流的，如果N M P蘊涵N P的話 關系 （重寫系統(tǒng)）是終止的，如果不存在一步歸約的無窮序列M0 M1 M2 不能再歸約的項稱為范式 合流并且終止的重寫系統(tǒng)通常又叫做典范系統(tǒng),3.6 重寫系統(tǒng),可變換性 如果存在M M1 M2 M3 Mk N 則項M, N Termss (, )是可變換的，寫成 M R N 箭頭的方向并沒有什么意義 對任何重寫系統(tǒng)，可變換性和可證明的相等性是一致的,3.6 重寫系統(tǒng),項中的一個位置：便于引用子項的某個特定出現(xiàn) 位置n = 1, 2的子項是hab 用M n表示M在位置n的子項 用N n M表示M在n的子項 由N代換的結果,3.6 重寫系統(tǒng),3.6.2 合流性和可證明的相等性 記號 如果R是一組重寫規(guī)則，ER用來表示對應的無向的等式集合 定理 對任何重寫系統(tǒng)R，MR N當且僅當ER M N 對任何合流的重寫系統(tǒng)R，ER M N當且僅當M R R N,3.6 重寫系統(tǒng),3.6.3 終止性 良基關系：集合A上的一個關系是良基的，如果不存在A上元素的無窮遞減序列a0 a1 a2 的話。 如果能在項和有良基關系的集合A的元素間建立起一個對應，那么可以利用它去證明不存在無窮的歸約序列M0 M1 M2 有幾種方式可把項映射到有良基關系的集合 利用代數(shù)的語義結構,3.6 重寫系統(tǒng),代數(shù)A = As1, As2, , f1A, f2A, 是良基的，如果 每個載體As上有一個良基關系s 對每個n元函數(shù)符號f，如果x1 y1, , xn yn并且對某個i（1 i n）有xi yi，那么 f A(x1, , xn) f A(y1, , yn) 若A是一個良基代數(shù)，并且M和N都是類別s上的項，如果M s N，那么寫成 A， M N 如果對任何環(huán)境都有A， M N，那么寫成A M N。,3.6 重寫系統(tǒng),定理 令R是項上的一個重寫系統(tǒng)，并且令A是一個良基的代數(shù)。如果對R中每條規(guī)則L R有A L R，那么R是終止的 例 x x 載體Abool N 0, 1 (x y) (x y) A (x, y) = x + y + 1 (x y) (x y) A(x, y) = x y x (y z) (x y) (x z) A(x) = 2x (y z) x (y x) (z x) 每條重寫規(guī)則的左部定義的值都大于其右部定義的值,3.6 重寫系統(tǒng),3.6.4 臨界對 局部合流 關系是局部合流的，如果N M P蘊涵N P 局部合流關系嚴格弱于合流關系 例 a b, b a a a0, b b0,3.6 重寫系統(tǒng),cond B (cdr(cons s l) (cons(car l)(cdr l) ) 規(guī)則如下： cdr(cons x l) l cons(car l)(cdr l) l 不相交的歸約,3.6 重寫系統(tǒng),cdr(cons x(cons(car l)(cdr l) 規(guī)則如下： cdr(cons x l) l cons(car l)(cdr l) l 平凡的重迭,3.6 重寫系統(tǒng),cdr(cons(car l)(cdr l) 規(guī)則如下： cdr(cons x l) l cons(car l)(cdr l) l 非平凡的重迭,3.6 重寫系統(tǒng),臨界對 L R cdr(cons x l) l L R cons(car l)(cdr l) l 非平凡重迭是一個三元組SL，SL，m 二元組SR，SR m SL叫做臨界對 該例有兩個臨界對，第一個如下： SL是cdr(cons(car l)(cdr l) 臨界對是cdr l, cdr l,3.6 重寫系統(tǒng),第二個如下： L R cons(car l)(cdr l) l L R cdr(cons x l) l SL是cons(car (cons x l)(cdr(cons x l) 臨界對是cons x l, cons (car (cons x l) l 若f (gxy) R，L中有子項f