第五章函數(shù)式程序設(shè)計(jì)語言(編輯修改稿)
2024-11-29 14:18 本頁面
【文章內(nèi)容簡介】 )=E1 in E2 ≡ let fp=E1 in let x1=first p in let x2=second p in . . . let xn=n_th p in E2 Lambda演算 關(guān)于 Lambda演算 ? ?表達(dá)式 ? 自由變量（計(jì)算一個(gè) ?表達(dá)式的自由變量集合 ） ? 替換（計(jì)算） ? 變換規(guī)則 （三種變換） ? 歸約 ? 范式（性質(zhì)及其計(jì)算） 關(guān)于 Lambda演算 ? ?表達(dá)式 一個(gè) ?表達(dá)式 由變量名、抽象符號 ?， .以及括號等符號構(gòu)成， 其語法為： ?表達(dá)式 ::= 變量名 | ?表達(dá)式 ?表達(dá)式 | ? 變量名 . ?表達(dá)式 | ( ?表達(dá)式 ) 關(guān)于 Lambda演算 ? 變換規(guī)則 （三種變換） ? ?變換：設(shè) E是 ?表達(dá)式， x是變量，則稱下面變換為 α變換（其中 y不在 FV( ? )中） ? 〉 ?y.[y/x] E ? ?變換：設(shè) (?)和 E0為 ?表達(dá)式，則稱下面變換為 β變換（稱 β變換規(guī)則的左部表達(dá)式為 β基） (?)E0 E[E0/x] ? ?變換：假設(shè) ?，且滿足條件 x?FV(M)，則稱下面變換為 η變換 : (? x) M ? ? ? 關(guān)于 Lambda演算 ? 自由變量（計(jì)算一個(gè) ?表達(dá)式的自由變量集合 ） ? 表達(dá)式 E中變量名 x的一次出現(xiàn)稱為 自由出現(xiàn) ，如果 E中任何一個(gè)形如 ?x. E’的子表達(dá)式包含該出現(xiàn)； ? y (?x y. y (?x. x y ) ) (z (?x. x x) )的自由變量集合 {y, z} ? 替換（計(jì)算） 設(shè) E和 E0是表達(dá)式， x是變量名， 替換 E[E0/x]是表示 把 E中的所有 x的自由出現(xiàn)替換成 E0。 ? 需要明確變量的自由出現(xiàn) ? 計(jì)算規(guī)則 ? ( ?y. x+y) [y/x] = ?z. y+z 關(guān)于 Lambda演算 ? 范式（性質(zhì)及其計(jì)算） ? 假設(shè) E是一個(gè)表達(dá)式，且其中沒有任何一個(gè)歸約基，則稱該表達(dá)式為 范式 。 ? 范式 的存在性：如 果有范式，則最左歸約法一定能求出范式。 ? 范式 的唯一性：如 果有范式則在 ?變換下一定唯一。 函數(shù)式描述方法 關(guān)于函數(shù)式描述方法 ? 函數(shù)式語言的特點(diǎn) – 引用透明性；高階性；模式匹配；并行性； ? 函數(shù)式語言的組成部分 – 程序結(jié)構(gòu) – 類型及其操作 – 表達(dá)式 ? 用函數(shù)式語言來描述算法（解釋器） – 函數(shù)空間 – 函數(shù)定義（方程） 關(guān)于函數(shù)式描述方法 ? 函數(shù)式語言的組成部分 – 程序結(jié)構(gòu) ? 函數(shù)定義 ? 目標(biāo)表達(dá)式 – 類型及其操作 – 標(biāo)準(zhǔn)類型 集合類型 – 冪集類型 元組類型 – 聯(lián)合類型 序列類型 – 函數(shù)類型 遞歸類型 – 抽象類型 關(guān)于函數(shù)式描述方法 ? 函數(shù)式語言的組成部分 – 表達(dá)式 ?非 let表達(dá)式（常量，變量， ?表達(dá)式，條件表達(dá)式， 以及各種操作） ?let表達(dá)式 let x = E’ in E ?letrec表達(dá)式 letrec x = E1 in E ?在表達(dá)式中增加類型說明 關(guān)于函數(shù)式描述方法 ? 用函數(shù)式語言來描述算法 – 函數(shù)空間： INT* ? INT ? BOOL – 函數(shù)定義（方程） lookup L a = (null L→FALSE ， a=hd L→TRUE ， lookup (tl L) a ) 函數(shù)式語言怎樣克服命令式語言的缺點(diǎn) ? 消除賦值 賦值語句在過程語言中起什么作用。 在函數(shù)式 語言中取消會有什么問題： [1] 存儲計(jì)算子表達(dá)式的中間結(jié)果。 [2] 條件語句的重要組成。 [3] 用于循環(huán)控制變量。 [4] 處理復(fù)雜數(shù)據(jù)結(jié)構(gòu) (增刪改某個(gè)成分 )。 解決辦法 [1]： 保留全局量、局部量 (符號名 )以及參數(shù)名 。 [2]： 用條件表達(dá)式代替條件語句，其返回值通過 參數(shù)束定或 where子句束定于名字 [3]:函數(shù)式語言都要定義表數(shù)據(jù)結(jié)構(gòu)， 因?yàn)闅w約 和遞歸計(jì)算在表上很方便。 對整個(gè)表操作實(shí) 則是隱式迭代。 不用循環(huán)控制變量。 對于 順序值也都用表寫個(gè)映射函數(shù)即可隱式迭代。 部分達(dá)到作用 [3]， 其它顯式循環(huán)要用遞歸。 [4]:禁止賦值意味著數(shù)據(jù)結(jié)構(gòu)一旦創(chuàng)建不得修改 ,故采用如下函數(shù)式語言結(jié)構(gòu)數(shù)據(jù)修改方式 A B C E H G D F’ B’ C A F J I 以遞歸代替 while_do 組織仿真的要點(diǎn)是把遞歸函數(shù)體寫入條件表達(dá)式。 循環(huán)終止條件是條件測試部分， 函數(shù)如有返回值放在 then部分， 遞歸函數(shù)體放在else部分， 如果不需返回值則取消一部分(else)。 消除順序 一旦語義相關(guān)無法傳遞數(shù)據(jù)， 非得寫成嵌套函數(shù)不可 (返回值自動(dòng)束定到外套函數(shù)的變元上 ) 例 :pascal實(shí)現(xiàn)： c： =a+b； s： =sin(c * c)； 。 write(a， b， c， s)； //上面計(jì)算不進(jìn)行是無法打印 //的邏輯上要有順序。 LISP 實(shí)現(xiàn) ： (print (let ((c(+ a b))) let ((s (sin (* c c)))) list a b c s )))) //仍有順序但在一個(gè) //表達(dá)式內(nèi)。自左至右處理即隱式順序。 Miranda實(shí)現(xiàn)： Answere a b = (a b c s ) where s= sin (c* c) c= a+b //多么清晰， 全然沒有順序 序 ? 用懶求值代替順序 ? 利用衛(wèi)式進(jìn)一步消除順序性 Miranda的衛(wèi)式表達(dá)式 gcd a b= gcd (ab) b， ab = gcd a (ba)， ab = a， a=b LISP的條件選擇 （ define GCD (a b) （ cond (( greaterp a b) (GCD ((diference a b ) b))) ((Lessp a b) (GCD (a (
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1