上次課程小結(jié)市公開課特等獎市賽課微課一等獎課件

上次課程小結(jié)類型系統(tǒng)：賦給程序各部分一組規(guī)則類型表示式：由類型結(jié)構(gòu)符作用與基本類型表示式?；绢愋捅硎臼剑夯绢愋?、類型名、類型變量值類型結(jié)構(gòu)符：×、＋、array(I,T)、pointer(T)、record（F1×F2×...)、D→R簡單類型檢驗：語法制導翻譯申明時結(jié)構(gòu)類型表示式引用時計算類型表示式（類型檢驗）第1頁4.4類型表示式等價在簡單類型檢驗中，經(jīng)過判定所給兩個類型表示式是否相等來進行類型檢驗。對于單態(tài)類型，我們引入一個更專業(yè)術(shù)語，類型等價來描述類型檢驗。類型等價與類型表示相關，表示不一樣，等價概念也不一樣。本節(jié)討論三個主要問題：有哪些類型等價程序設計語言要求什么樣等價以及等價判別第2頁4.4.1結(jié)構(gòu)等價與等價判別若兩個僅由類型結(jié)構(gòu)符作用于基本類型組成類型表示式完全相同，則稱兩個類型表示式結(jié)構(gòu)等價。換句話說，類型表示式結(jié)構(gòu)等價當且僅當二者完全相等。若類型表示式中沒有名字，則結(jié)構(gòu)等價就是類型等價。比如int與int結(jié)構(gòu)等價，array(1..10,real)與array(1..10,real)結(jié)構(gòu)等價。反應在類型表示式語法樹上，就是兩棵語法樹完全相同。第3頁<1>結(jié)構(gòu)等價判別算法4.1判別類型是否結(jié)構(gòu)等價輸入兩個類型表示式輸出若兩個類型表示式結(jié)構(gòu)等價則返回true不然false方法用下述遞歸函數(shù)進行判別：functionsequiv(s,t)returnbooleanisbegin

endsequiv;ifsandtarethesametypethenreturntrue;elsifs=array(s1,s2)andt=array(t1,t2) thenreturnsequiv(s1,t1)andsequiv(s2,t2);elsifs=s1×s2andt=t1×t2 thenreturnsequiv(s1,t1)andsequiv(s2,t2);elsifs=pointer(s1)andt=pointer(t1)thenreturnsequiv(s1,t1);elsifs=s1→s2andt=t1→t2 thenreturnsequiv(s1,t1)andsequiv(s2,t2);elsereturnfalse; endif;第4頁<1>結(jié)構(gòu)等價判別（續(xù)）例4.13再考慮函數(shù)申明functionmax(x,y:integer):integer和調(diào)用max(5,8)：在對調(diào)用語句max(5,8)類型檢驗中，因為函數(shù)形參類型和實參類型等價（sequiv(s,E2.type)=true），所以最終函數(shù)值類型為int。申明時：調(diào)用時：E→E1,E2 {E.type:=E1.type×E2.type;}|E1(E2) {E.type:=ifE2.type=sandE1.type=s→t thentelsetype_error;}第5頁<2>類型表示式優(yōu)化表示sequiv(s,t)算法弱點：需要對兩棵語法樹完全遍歷后才能確定它們是否等價。當類型結(jié)構(gòu)符層次很多而且僅在最底層不等價時，算法效率較低。改進思緒：在調(diào)用sequiv之前，先用一個簡單方法將明確能夠確定不等價情況排除。即為了提升效率，犧牲一些次要信息，只有當兩個類型表示式主要信息相等時才判定次要信息是否也相等。詳細方法：對類型表示式主要信息進行編碼。將類型結(jié)構(gòu)符表示每個內(nèi)部節(jié)點多于一個孩子分支剪去，僅保留一個主要分支，類型表示式語法樹就退化為一個鏈，即一條從根到葉子路徑。對鏈上每個節(jié)點編碼，形成一個類型編碼字符串或者整型數(shù)。因為類型編碼僅反應了類型表示式主要成份，所以兩個編碼不一樣，則類型表示式一定不等價（從而起到過濾作用），反之不一定。第6頁<2>類型表示式優(yōu)化表示（續(xù)1）數(shù)組類型表示式array(s,t)簡化為array(t)，即忽略下標類型保留數(shù)組元素類型。函數(shù)類型表示式s→t簡化為freturns(t)，即忽略參數(shù)類型保留返回值類型。指針類型表示式pointer(t)本身就是一個一元結(jié)構(gòu)符，所以無需簡化。問題：×與record簡化怎樣處理？簡化類型表示式編碼：基本類型類型結(jié)構(gòu)符類型編碼結(jié)構(gòu)符編碼boolean0000pointer01char0001array10int0010freturns11real0011non00類型表示式化簡：第7頁<2>類型表示式優(yōu)化表示（續(xù)2）基本類型類型結(jié)構(gòu)符類型編碼結(jié)構(gòu)符編碼boolean0000pointer01char0001array10int0010freturns11real0011non00例4.14

考慮類型表示式array(1..10,pointer(int→char))：簡化后類型表示式為array(pointer(freturns(char)))。將其從左到右轉(zhuǎn)換為編碼，得到1001110001。第8頁4.4.2引入類型名等價判別若每個類型名作為一個可區(qū)分類型出現(xiàn)在表示式中而且使得兩個類型表示式完全相同，則稱它們名字等價。若將類型表示式中全部名字均用其定義類型表示式替換后兩個類型表示式完全相同，則稱它們結(jié)構(gòu)等價。例4.15

對于下述Pascal程序段：typecell=array[1..10,int];typelink=^cell;var next :link; last :link; p :^cell; q,r :^cell;采取名字等價，則變量next和last類型表示式為link，變量p、q、r類型表示式為pointer(cell)，顯然next和last名字等價，p、q、r名字等價。若將名字用它們所代表結(jié)構(gòu)代替，則5個變量類型表示式均為pointer(array(1..10,int))。所以它們?nèi)拷Y(jié)構(gòu)等價。第9頁4.4.2引入類型名等價判別（續(xù)1）名字等價經(jīng)過對取值范圍相同不過代表不一樣意義對象取不一樣類型名，使得它們含有不一樣類型。不一樣類型對象不能進行運算，從而防止了潛在錯誤；名字等價提升了程序可靠性，不過降低了程序靈活性；程序設計語言能夠依據(jù)不一樣需求采取不一樣等價策略。比如Algol68采取結(jié)構(gòu)等價，而Ada采取名字等價。例4.16

下述Ada類型定義語句將完全相同結(jié)構(gòu)定義為不一樣名字：typemale_typeisnode_array;typefemale_typeisnode_array;male:male_type;female:female_type;在名字等價下，變量male和female類型不一樣，使得這兩個變量之間不能運算。

第10頁為何要求采取何種類型等價

Pascal沒有要求采取何種等價，其等價問題依賴于實現(xiàn)，給熟悉名字等價或結(jié)構(gòu)等價程序員帶來無須要使用上混亂。Pascal關于類型等價一個處理方案是：變量申明時對類型每次引用，均隱含地為它結(jié)構(gòu)一個類型名，然后采取名字等價。type cell=array[1..10,int];type link=^cell;

np=^cell;

nqr=^cell;var next:link; last:link; p:np; q,r:nqr;typecell=array[1..10,int];typelink=^cell;var next :link; last :link;

p :^cell;

q,r :^cell;在名字等價定義下，原來與q和r類型等價p現(xiàn)在被認為不與任何變量類型等價。第11頁為何要求采取何種類型等價（續(xù)）Pascal這種類型等價實現(xiàn)方法，似乎比名字等價更為嚴格。程序員能夠采取一個變通方法將Pascal程序轉(zhuǎn)換為名字等價，若有不一樣變量申明含有結(jié)構(gòu)等價類型時，一定要先定義這類型，即為這類型命名。例4.17定義下述兩個申明語句，變量a和參數(shù)x實質(zhì)上結(jié)構(gòu)等價：vara:array[1..10]ofinteger;functiontest(x:array[1..10]ofinteger):integer;依據(jù)Pascal等價策略，a與x類型不等價，所以a不能作為函數(shù)test實參。若希望a作為test實參，則必須首先為它們共同類型命名，然后a和x均被申明為這類型名所定義類型：typearr_type=array[1..10]ofinteger;vara:arr_type;functiontest(x:arr_type):integer;從而使得a與x類型等價。第12頁單態(tài)類型檢驗普通過程確定一個類型等價方式：沒有類型名情況下全部等價問題均是結(jié)構(gòu)等價；名字能夠作為類型表示式時，就需要確定等價策略，是采取名字等價還是采取結(jié)構(gòu)等價；依據(jù)類型信息結(jié)構(gòu)類型表示式，名字等價與結(jié)構(gòu)等價唯一區(qū)分就是類型名是否能夠出現(xiàn)在類型表示式中；判定表示式類型等價就是判定它們類型表示式是否相等。第13頁4.5多態(tài)函數(shù)類型檢驗通俗講，程序設計語言中多態(tài)就是一個符號能夠有各種意思。多態(tài)與強類型是密不可分，即使一個符號能夠有各種意思，不過編譯器必須確保它每次使用是確定而且是類型正確，不然并不是多態(tài)而是弱類型。弱類型經(jīng)典例子是C，比如在C程序中char類型變量和int類型變量能夠運算，不過運算結(jié)果正確性由程序員負責。第14頁4.5.1多態(tài)函數(shù)與類型變量表示通用多態(tài)中參數(shù)多態(tài)被稱為多態(tài)函數(shù)。多態(tài)函數(shù)基本特征是參數(shù)類型是類型變量且該變量能夠取無窮多個值，不過全部類型均對應同一代碼序列。多態(tài)函數(shù)中形參類型是變量，稱為類型變量，用α、β、δ等表示。從語言結(jié)構(gòu)使用方式推斷其類型，被稱為類型推斷（typeinference）。比如從函數(shù)體推斷函數(shù)類型。例4.18對于函數(shù)定義：functionderef(p);beginreturnp^end；從函數(shù)體中能夠看出，p類型應該是指向某對象指針，而p^返回它所指向?qū)ο?。設該對象類型為α，則p類型是pointer(α)，所以函數(shù)deref(p)類型應該是：

α.pointer(α)→α (4.1)即對于任何一個類型為α對象，函數(shù)deref(p)是將指向α對象一個指針類型映射到該對象。deref習慣上也被稱為脫引用。<1>多態(tài)函數(shù)、類型變量與類型推斷第15頁<2>含多態(tài)函數(shù)語言文法多態(tài)函數(shù)與單態(tài)函數(shù)本質(zhì)區(qū)分是形參不但能夠是常量也能夠是變量。所以對(AG4.1)和(AG4.4)文法進行擴充，將含有類型變量類型定義引入產(chǎn)生式。P→D;ED→D;D|id:QQ→

type-variable.Q|T (G4.6)T→T'→'T|T×T|unary-constructor(T)|basic-type|type-variable|(T)E→E(E)|E,E|id此擴充與將數(shù)據(jù)簡單變量擴充為含有數(shù)組元素類似。首先，文法將原來單態(tài)類型T擴展為多態(tài)類型Q，Q除了包含T產(chǎn)生式全部，又引入了受約束類型變量。同時T產(chǎn)生式中增加了類型變量，即將類型變量引入類型。引入數(shù)組元素后賦值句文法A→V:=EV→id[EL]|idEL→EL，E|EE→E+E|(E)|V第16頁<2>含多態(tài)函數(shù)語言文法（續(xù)1）例4.19

按文法(G4.6)書寫一個程序以下：

P→D;ED→D;D|id:QQ→

type-variable.Q|T (G4.6)T→T'→'T|T×T|unary-constructor(T)|basic-type|type-variable|(T)E→E(E)|E,E|idderef:

α.pointer(α)→α;q:pointer(pointer(int));defef(deref(q));首先申明deref和q，然后是函數(shù)調(diào)用defef(deref(q))，其中內(nèi)層函數(shù)調(diào)用返回值作為外層調(diào)用實參。顯然，兩個相同函數(shù)在不一樣位置出現(xiàn)含有不一樣參數(shù)類型和返回值類型。

第17頁<2>含多態(tài)函數(shù)語言文法（續(xù)2）deref:

α.pointer(α)→α;q:pointer(pointer(int));defef(deref(q));P→D;ED→D;D|id:QQ→

type-variable.Q|T (G4.6)T→T'→'T|T×T|unary-constructor(T)|basic-type|type-variable|(T)E→E(E)|E,E|id函數(shù)名作用于參數(shù)得到函數(shù)返回值每次引入一個固定變元第18頁結(jié)束（4月29日）

“五一”節(jié)高興！

（五一后第一周兩次課?。┑?9頁多態(tài)函數(shù)簡單回顧多態(tài)函數(shù)、類型變量與類型推斷含多態(tài)函數(shù)語言文法deref:

α.pointer(α)→α;q:pointer(pointer(int));defef(deref(q));P→D;ED→D;D|id:QQ→

type-variable.Q|T (G4.6)T→T'→'T|T×T|unary-constructor(T)|basic-type|type-variable|(T)E→E(E)|E,E|idP→D;ED→D;D|id:QQ→

type-variable.Q|T (G4.6)T→T'→'T|T×T|unary-constructor(T)|basic-type|type-variable|(T)E→E(E)|E,E|id每次引入一個新類型變量替換變量試圖得到匹配保留替換結(jié)果以繼續(xù)匹配第20頁4.5.2代換、實例與合一多態(tài)函數(shù)類型檢驗普通方法：首先設法消除類型變量，然后判定消除類型變量后類型表示式是否結(jié)構(gòu)等價。詳細有三點與單態(tài)類型檢驗不一樣：(1)消除約束變元類型表示式中約束變元在語法樹中每次出現(xiàn)均要被替換為自由變元，且同一類型表示式多態(tài)函數(shù)不一樣出現(xiàn)，變元能夠有不一樣類型。方法是每引入一個多態(tài)類型表示式，就為變元引入一個新類型變量。如將

α.pointer(α)→α改為pointer(α0)→α0或pointer(αi)→αi，從而消除了全稱量詞和約束變元。第21頁4.5.2代換、實例與合一（續(xù)1）(2)合一（unify）類型表示式

判斷類型表示式s和t是否等價變成能否使s和t“合一”，即當把s和t類型變量用不含類型變量類型表示式替換后判斷s和t是否結(jié)構(gòu)等價。比如在對derefi進行類型檢驗時，將αi用pointer(int)替換，即αi=pointer(int)，可使得函數(shù)形參類型pointer(αi)與實參類型pointer(pointer(int))等價。(3)統(tǒng)計合一結(jié)果

對每次合一結(jié)果，需要統(tǒng)計下來，方便后續(xù)類型檢驗使用。比如將αi用pointer(int)替換后結(jié)果是正確，則此結(jié)果需要統(tǒng)計下來，再用于deref0類型檢驗。第22頁4.5.2代換、實例與合一（續(xù)2）術(shù)語（基本概念）：代換（Substitutions）代換是從類型變量到類型表示式一個映射。比如類型變量αi到類型表示式pointer(int)映射。實例（instances）代換結(jié)果被稱為代換一個實例，用S(t)表示。S(t)<t表示S(t)是t一個代換實例。類型表示式pointer(int)是類型變量αi一個實例，能夠表示為pointer(int)<αi。不含類型變量類型表示式是其本身一個實例，比如int<int。合一（Unification）若存在代換S，使得S(t1)=S(t2)，則稱表示式t1和t2能合一，該代換過程被稱為合一操作。S(αi)=pointer(int)，所以αi和pointer(int)能合一。第23頁最普通合一代價最小代換被稱為最普通合一。所謂代價最小代換含有下述性質(zhì)：S(t1)=S(t2)

S'.S'(t1)=S'(t2)都有S'<S，即

t.S'(t)<S(t)或者說S是代換次數(shù)最少一個實例，即一旦有了能夠確定類型是否等價代換結(jié)果，就馬上停頓代換。代換算法與類型等價算法很相同。此處代換算法僅考慮了函數(shù)情況，而其它類型結(jié)構(gòu)符類型代換與之類似。第24頁代換算法算法4.2代換算法輸入類型表示式t輸出t代換實例方法用下述遞歸函數(shù)進行代換：functionsubs(t:type_expression)returntype_expressionisbeginendsubs;if tisabasic_type thenreturnt;--基本類型代換是其本身elsiftisavariablethen returnS(t);--返回類型變量一個代換實例elsif tist1→t2 thenreturnsubs(t1)→subs(t2);--分別代換映射兩邊類型表示式end if;與等價算法比較在算法中加入其它類型結(jié)構(gòu)符第25頁代換算法（續(xù)）iftisabasic_typethenreturnt;--基本類型代換是其本身elsiftisavariablethenreturnS(t);--類型變量代換實例elsif tist1→t2thenreturnsubs(t1)→subs(t2);--分別代換end if;real<realint→int<α→αpointer(int)<pointer(α)α<β而：int≮real，因為int和real是不一樣基本類型表示式。int→real≮α→α，因為α代換不一致，映射左邊被代換為int，而右邊被代換為real。int→α≮α→α，因為α代換不完全，映射左邊被代換，而右邊沒有代換。例4.20依據(jù)算法4.2能夠判斷：第26頁4.5.3多態(tài)函數(shù)類型檢驗多態(tài)函數(shù)類型檢驗基本思想是對兩個要被檢驗類型進行合一操作。所謂判定類型表示式e和f是否能合一，就是能否找到一個代換S，使得S(e)=S(f)，即檢驗e和f在代換S下是否等價。檢驗方法是分別給出e和f語法樹，假如兩棵語法樹經(jīng)過代換之后重合為一棵語法樹，則說明e和f能合一。第27頁4.5.3多態(tài)函數(shù)類型檢驗（續(xù)1）fresh(t)：將類型表示式t中約束變元用一新自由變元來代替，若t是一個類型常量則結(jié)果依然是t本身。這一過程類似于產(chǎn)生暫時變量語義函數(shù)newtemp。不一樣是fresh產(chǎn)生是類型變量自由變元α、β、δ等。比如fresh(deref:

α.pointer(α)→α)能夠得到pointer(α1)→α1，fresh(int)=int。union(m,n)：結(jié)構(gòu)m和n等價類，并在等價類中選取一個代表。union(m,n)選取等價類代表關鍵是：兩個類型表示式中非類型變量類型表示式被優(yōu)先選取為代表，從而確保了類型變量到類型表示式代換。不然任選其一作為代表，比如能夠選取節(jié)點編號小。find(m)：找到并返回m所在等價類中代表。語義函數(shù)：第28頁4.5.3多態(tài)函數(shù)類型檢驗（續(xù)2）算法4.3

類型表示式合一算法輸入以m和n為根兩棵類型表示式語法樹輸出若m和n代表類型表示式能合一則返回true不然false方法用下述遞歸函數(shù)進行代換：

functionunify(m,n:nptr)returnbooleanisbeginendunify;s:=find(m); t:=find(n); --分別找到m和n所在等價類代表if s=t thenreturntrue;elsif s和t代表相同基本類型thenunion(s,t);

returntrue;elsif s和t代表相同類型結(jié)構(gòu)符并分別有孩子節(jié)點(s1,s2)和(t1,t2)thenunion(s,t);

--結(jié)構(gòu)等價類returnunify(s1,t1)andunify(s2,t2);--分別合一左右孩子elsif s或t代表一個變量thenunion(s,t);

returntrue;else returnfalse;

--其它均不可合一endif;第29頁4.5.3多態(tài)函數(shù)類型檢驗（續(xù)3）多態(tài)函數(shù)文法(G4.6)中表示式類型檢驗語義規(guī)則：E→E1(E2){ γ:=mkleaf(newtypevar); unify(E1.type,mknode('→',E2.type,γ); E.type:=γ;} (AG4.6)|E1,E2{ E.type:=mknode('×',E1.type,E2.type);}|id { E.type:=fresh(id.type);}函數(shù)調(diào)用E→E1(E2)語義處理：設E1.type=α且在函數(shù)申明時α已確定(α=s→t)，設E2.type=β。則應有未知類型γ，使得S(α)=S(β→γ)。為此設α語法樹根節(jié)點為n，并建立一個類型為γ葉節(jié)點和一個類型為β→γ新節(jié)點m。若m與n合一成功則其結(jié)果γ成為E.type類型。第30頁deref(deref(q))類型檢驗例4.21用算法4.3和(AG4.6)，對deref(deref(q))進行類型檢驗。E→E1(E2){ γ:=mkleaf(newtypevar); unify(E1.type,mknode('→',E2.type,γ); E.type:=γ;} (AG4.6)|id { E.type:=fresh(id.type);}E1→