【正文】 Node (Leaf 17) (Leaf 49))) [3] 3 3 17 49 leaf 1 tree 1 leaf 1 第 [2]行執(zhí)行后 第 [3]行執(zhí)行后 多態(tài)函數(shù)定義及調(diào)用 設函數(shù) max_tree 為求樹中葉子值最大 max_tree (Leaf ldata) = ldata [1] max_tree (Node n1 n2) = max1， max1 max2 [2] = max2， max2 max1 [3] = max1， otherwise where max1 = (max_tree n1) [4] max2 = (max_tree n2) [5] 如有應用： (max_tree leaf1) //結果值為 3， leaf1用上例(max_tree tree1)//結果值為 49， tree1用上例? 表 (list) Miranda表的表示法 [ ] //空表 [1..n] //1到 n,域表示 odd_number = [1， 3， ..100] //1到 100內(nèi)奇數(shù)表，頭兩項及最后項必寫 eleven_up = [11...] //10以上， 無限表表示 evens = [10， 12...100] //10以上偶數(shù)表至 100，頭兩項及最后項必寫 evens_up = [12， 14...] //10以上偶數(shù)無限表， week _days = [“Mon”， “Tue”， “Wed”， “Thur”， “Fri”] //五個串值的表 內(nèi)定義操作 Miranda定義了常規(guī)的算術運算符 (+、 、 *、 /、div、 mod)并按中綴表示使用。 ? 輸入輸出流就是一個值的無限表， 每次處理輸入流一個新值就附在表尾并為程序訪問。 Miranda實現(xiàn)： Answere a b = (a b c s ) where s= sin (c* c) c= a+b //多么清晰， 全然沒有順序 序 ? 用懶求值代替順序 ? 利用衛(wèi)式進一步消除順序性 Miranda的衛(wèi)式表達式 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 (diference b a )))) （ T a ))) 輸出問題 ? 利用數(shù)據(jù)對象內(nèi)部原有的順序 ? 結構對象是第一類對象， 語言支持的任何形式 (交互、非交互 )的輸出都可以用在表和元組上。 LISP 實現(xiàn) ： (print (let ((c(+ a b))) let ((s (sin (* c c)))) list a b c s )))) //仍有順序但在一個 //表達式內(nèi)。 消除順序 一旦語義相關無法傳遞數(shù)據(jù)， 非得寫成嵌套函數(shù)不可 (返回值自動束定到外套函數(shù)的變元上 ) 例 :pascal實現(xiàn)： c： =a+b； s： =sin(c * c)； 。 [4]:禁止賦值意味著數(shù)據(jù)結構一旦創(chuàng)建不得修改 ,故采用如下函數(shù)式語言結構數(shù)據(jù)修改方式 A B C E H G D F’ B’ C A F J I 以遞歸代替 while_do 組織仿真的要點是把遞歸函數(shù)體寫入條件表達式。 對于 順序值也都用表寫個映射函數(shù)即可隱式迭代。 對整個表操作實 則是隱式迭代。 解決辦法 [1]： 保留全局量、局部量 (符號名 )以及參數(shù)名 。 [3] 用于循環(huán)控制變量。 在函數(shù)式 語言中取消會有什么問題： [1] 存儲計算子表達式的中間結果。 ? 范式 的唯一性：如 果有范式則在 ?變換下一定唯一。 ? 需要明確變量的自由出現(xiàn) ? 計算規(guī)則 ? ( ?y. x+y) [y/x] = ?z. y+z 關于 Lambda演算 ? 范式（性質(zhì)及其計算） ? 假設 E是一個表達式，且其中沒有任何一個歸約基，則稱該表達式為 范式 。 如 : sqr = λ n. multiply n n //整個是 λ 函數(shù)表達式 sqr n = multiply n n //兩應用表達式也相等 let表達式在 ML. LISP中直接采用， Miranda用 where關鍵字使程序更好讀， let直到 E完結構成一個程序塊。 例 ： 當條件表達式為真時 if_then_else函數(shù)的歸約 (if_then_else) T M N = (λ p. λ m. λ n. p m n) T M N = (λ n. ( T m n))M N = (λ m. λ n. (λ ) m n) M N = (λ m. λ n. (λ ) n) M N = (λ m. λ n. m) M N = (λ n. M) N =M ? if表達式 可保留顯式 ifthenelse形式： (if_then_else) E1 E2 E3= if E1 then E2 else E3 其中 E1， E2， E3為 λ 表達式。時， 執(zhí)行 m否則為 n。例如，我們可以定義一個 if_then_else為名的函數(shù)：if_then_else =λ m n， 當 p為 39。用高層命名函數(shù)，語義清晰。 ? 解釋 :范式即 λ 演算的語義解釋， 形如 x x， (y (λ ))就只能解釋為數(shù)據(jù)了 。 例如： (λ x. (λ )) (z y) //(zy)中 y是自由變量 = λ y.(zy) //此時 (zy)中 y被束定了， 錯誤！ = (λ x.(λ ))(zy) //因 (λ )中函數(shù)體 無 y， 可換名 = λ w.(zy) // 正確！ (4)歸約約定 ? 順序 :每次歸約只要找到可歸約的子公式即可歸約， λ 演算沒有規(guī)定順序。 對應為程序設計語言中的無限遞歸。 =(zz)(λ x.(xy)) //正確 例 115 高層表示的 β 歸約 ? (λ n n) 3 = add 3 3