上次課程小結(jié)-在線瀏覽
2024-12-15 13:44本頁面
【正文】 同的需求采用不同的等價(jià)策略。 例 下述 Ada類型定義語句將完全相同的結(jié)構(gòu)定義為不同的名字： type male_type is node_array。 male : male_type。 在名字等價(jià)下，變量 male和 female的類型不同，使得這兩個(gè)變量之間不能運(yùn)算。 Pascal關(guān)于類型等價(jià)的一種解決方案是：變量聲明時(shí)對(duì)類型的每次引用，均隱含地為它構(gòu)造一個(gè)類型名，然后采用名字等價(jià)。 type link = ^cell。 nqr = ^cell。 last : link。 q,r : nqr。 type link = ^cell。 last : link。 q,r : ^cell。 為什么規(guī)定采用何種類型等價(jià)（續(xù)） Pascal的這種類型等價(jià)的實(shí)現(xiàn)方法，似乎比名字等價(jià)更為嚴(yán)格。 例 定義下述兩個(gè)聲明語句 ， 變量 a和參數(shù) x實(shí)質(zhì)上結(jié)構(gòu)等價(jià)： var a : array [ 1..10] of integer。 根據(jù) Pascal的等價(jià)策略， a與 x類型不等價(jià)，因此 a不能作為函數(shù) test的實(shí)參。 var a : arr_type。 從而使得 a與 x類型等價(jià) 。 多態(tài)函數(shù)的類型檢查 通俗的講，程序設(shè)計(jì)語言中的多態(tài)就是一個(gè)符號(hào)可以有多種意思。 弱類型的典型例子是 C，例如在 C程序中 char類型的變量和 int類型的變量可以運(yùn)算，但是運(yùn)算結(jié)果的正確性由程序員負(fù)責(zé)。 多態(tài)函數(shù)的基本特征是參數(shù)的類型是類型變量且該變量可以取無窮多個(gè)值 ， 但是所有類型均對(duì)應(yīng)同一代碼序列 。從語言結(jié)構(gòu)的使用方式推斷其類型，被稱為 類型推斷（ type inference）。 例 對(duì)于函數(shù)定義： function deref(p)。 設(shè)該對(duì)象的類型為 α ， 則 p的類型是pointer(α) ， 因此函數(shù) deref(p)的類型應(yīng)該是： ?α .pointer(α) → α () 即對(duì)于任何一個(gè)類型為 α 的對(duì)象，函數(shù) deref(p)是將指向 α 對(duì)象的一個(gè)指針類型映射到該對(duì)象。 1 多態(tài)函數(shù)、類型變量與類型推斷 2 含多態(tài)函數(shù)語言的文法 多態(tài)函數(shù)與單態(tài)函數(shù)的本質(zhì)區(qū)別是形參不但可以是常量也可以是變量。 P → D 。 D | id : Q Q → ? | T () T → T 39。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id 此擴(kuò)充與將數(shù)據(jù)的簡單變量擴(kuò)充為含有數(shù)組元素類似。同時(shí) T產(chǎn)生式中增加了類型變量，即將類型變量引入類型。 E D → D?！?9。 q : pointer(pointer(int))。 首先聲明 deref和 q，然后是函數(shù)調(diào)用 defef(deref(q))，其中內(nèi)層函數(shù)調(diào)用的返回值作為外層調(diào)用的實(shí)參。 2 含多態(tài)函數(shù)語言的文法（續(xù) 2） deref : ?α .pointer(α)→α 。 defef(deref(q))。 E D→D ?！?9。 q : pointer(pointer(int))。 (b) deref ( deref (int)) 的語法樹deref0 →iderefi q→0P→D 。 D | id : Q Q→ ?|T () T→T 39。 T|T T|unaryconstructor(T) |basictype|typevariable|(T) E→E(E)|E,E|id P → D 。 D | id : Q Q → ? | T () T → T 39。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id (c) deref(deref(int)) 語法樹上各節(jié)點(diǎn)的類型deref0 →derefi qpointer (αi) → αipointer (pointer(int) )pointer(α0)→α0i αi= pointer(int)→0α0=int? 每次引入一個(gè)新類型變量 ? 替換變量試圖得到匹配 ? 保留替換結(jié)果以繼續(xù)匹配 代換、實(shí)例與合一 多態(tài)函數(shù)類型檢查的一般方法：首先設(shè)法消除類型變量，然后判定消除類型變量后的類型表達(dá)式是否結(jié)構(gòu)等價(jià)。 方法是每引入一個(gè)多態(tài)類型表達(dá)式，就為變?cè)胍粋€(gè)新類型變量。 代換、實(shí)例與合一（續(xù) 1） (2) 合一（ unify）類型表達(dá)式 判斷類型表達(dá)式 s和 t是否等價(jià)變成能否使 s和 t“合一 ” ，即當(dāng)把 s和 t的類型變量用不含類型變量的類型表達(dá)式替換后判斷 s和 t是否結(jié)構(gòu)等價(jià)。 (3) 記錄合一的結(jié)果 對(duì)每次合一的結(jié)果，需要記錄下來，以便后續(xù)的類型檢查使用。 代換、實(shí)例與合一（續(xù) 2） 術(shù)語（基本概念）： 1. 代換（ Substitutions） 代換是從類型變量到類型表達(dá)式的一個(gè)映射。 2. 實(shí)例（ instances） 代換的結(jié)果被稱為代換的一個(gè)實(shí)例，用 S(t)表示。 ? 類型表達(dá)式 pointer(int)是類型變量 α i的一個(gè)實(shí)例，可以表示為 pointer(int)α i。 3. 合一（ Unification） 若存在代換 S，使得 S(t1)=S(t2)，則稱表達(dá)式 t1和 t2能合一，該代換過程被稱為合一操作。 最一般的合一 代價(jià)最小的代換被稱為最一般的合一。.S39。(t2)均有 S39。(t)S
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1