函數(shù)式程序設(shè)計語言

《函數(shù)式程序設(shè)計語言》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第5章函數(shù)式程序設(shè)計語言過程式程序設(shè)計語言由于數(shù)據(jù)的名值分離，變量的時空特性導(dǎo)致程序難于查錯、難于修改命令式語言天生帶來的三個問題只解決了一半濫用goto已經(jīng)完全解決懸掛指針沒有完全解決函數(shù)副作用不可能消除問題是程序狀態(tài)的易變性(Mutability)和順序性(Sequencing)Backus在圖靈獎的一篇演說《程序設(shè)計能從馮·諾依曼風(fēng)格下解放出來嗎？》中極力鼓吹發(fā)展與數(shù)學(xué)連系更密切的函數(shù)式程序設(shè)計語言5.1過程式語言存在的問題（1）易變性難于數(shù)學(xué)模型代數(shù)中的變量是未知的確定值，而程序設(shè)計語言的變量是對存儲的抽象根本解決：能不能不要程序意義的“變量”只保留數(shù)學(xué)意義的“變量”？能不

2、能消除函數(shù)的副作用？例：有副作用的函數(shù)intsf_fun(intx)staticintz=0；//第一次裝入賦初值returnx+(z++)；sf_fun(3)={3

3、4

4、5

5、6

6、7…}//隨調(diào)用次數(shù)而異，不是數(shù)學(xué)意義的確定函數(shù)。（2）順序性更難數(shù)學(xué)模型順序性影響計算結(jié)果，例如，前述急求值、正規(guī)求值、懶求值同一表達式就會有不同的結(jié)果。有副作用更甚，因而難于為程序建立統(tǒng)一的符號數(shù)學(xué)理論。應(yīng)尋求與求值順序無關(guān)的表達方式理想的改變途徑?jīng)]有變量，就沒有破壞性賦值，也不會有引起副作用的全局量和局部量之分。調(diào)用通過引用就沒有意義。循環(huán)也沒有意義，因為只有每次執(zhí)行循環(huán)改變了控制變量的值，循環(huán)才能

7、得到不同的結(jié)果。那么程序結(jié)構(gòu)只剩下表達式、條件表達式、遞歸表達式。5.2λ演算λ演算是符號的邏輯演算系統(tǒng)，它正好只有這三種機制，它就成為函數(shù)式程序設(shè)計語言的模型λ演算是一個符號、邏輯系統(tǒng)，其公式就是符號串并按邏輯規(guī)則操縱Church的理論證明，λ演算是個完備的系統(tǒng)，可以表示任何計算函數(shù)，所以任何可用λ演算仿真實現(xiàn)的語言也是完備的。λ演算使函數(shù)概念形式化，是涉及變量、函數(shù)、函數(shù)組合規(guī)則的演算。λ演算基于最簡單的定義函數(shù)的思想：一為函數(shù)抽象λx.E，一為函數(shù)應(yīng)用(λx.E)(a)。一切變量、標(biāo)識符、表達式都是函數(shù)或(復(fù)合)高階函數(shù)。如λx.C(C為常量)是常函數(shù)。λ演算公式舉例x變量、

8、公式、表達式。(λx.((y)x))函數(shù)，體內(nèi)嵌入應(yīng)用。(λz.(y(λz.x)))函數(shù)，體內(nèi)嵌入應(yīng)用，再次嵌入函數(shù)。((λz.(zy))x)應(yīng)用表達式。λx.λy.λz.(xλx.(uv)w)復(fù)雜表達式由于λ演算中一切語義概念均用λ表達式表達。為了清晰采用命名替換使之更易讀。T=λx.λy.x//邏輯真值F=λx.λy.y//邏輯假值1=λx.λy.xy//數(shù)12=λx.λy.x(xy)//數(shù)2zerop=λn.n(λx.F)T//判零函數(shù)注：zerop中的F、T可以用λ表達式展開形式語法核心的λ演算沒有類型，沒有順序控制等概念，程序和數(shù)據(jù)沒有區(qū)分。語法極簡單：<λ-表達式>::

9、=<變量>

10、λ<變量>.<λ-表達式>

11、(<λ-表達式><λ-表達式>)

12、(<λ-表達式>)<變量>::=<字母>基本函數(shù)TRUE和FALSE的λ表達式T=λx.λy.xF=λx.λy.y整數(shù)的λ表達式：0=λx.λy.y1=λx.λy.xy2=λx.λy.x(xy)n=λx.λy.x(x(…(xy))n個基本操作函數(shù)not=λz.((zF)T)=λz.((zλx.λy.y)(λx.λy.x))and=λa.λb.((ab)F)=λa.λb.((ab)λx.λy.y))or=λa.λb.((aT)b)=λa.λb.((aλx.λy.x)b)以下是算術(shù)操作函數(shù)舉例：+=add=λx.

13、λy.λa.λb.((xa)(ya)b)*=multiply=λx.λy.λa.((x(ya)))**=sqr=λx.λy.(yx)identity=λx.x//同一函數(shù)succ=λn.(λx.λy.nx(xy))//后繼函數(shù)zerop=λn.n(λx.F)T=λn.n(λz.λx.λy.y)(λx.λy.y)//判零函數(shù)例：3+4就寫add34，add3返回“加3函數(shù)”應(yīng)用到4上當(dāng)然就是7。寫全了是：（λx.λy.λa.λb.((xa)(ya)b)）(λp.λq.(p(p(pq)))(λs.λt.(s(s(s(st)))?λa.λb.(a(a(a(a(a(a(ab)))))))歸

14、約與范式歸約將復(fù)雜的表達式化成簡單形式，即按一定的規(guī)則對符號表達式進行置換。例：歸約數(shù)1的后繼(succ1)=>(λn.(λx.λy.nx(xy))1)=>(λx.λy.1x(xy))=>(λx.λy.(λp.λq.pq)x(xy))=>(λx.λy.(λq.xq)(xy))=>(λx.λy.x(xy))=2注：succ和1都是函數(shù)(1是常函數(shù))，第一步是λn束定的n被1置換。展開后，x置換p，(xy)置換q，最后一行不能再置換了，它就是范式，語義為2。（1）β歸約：