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

1、函數(shù)式程序設(shè)計語言函數(shù)式程序設(shè)計語言1、概論 面向過程程序設(shè)計 面向?qū)ο蟪绦蛟O(shè)計 函數(shù)式程序設(shè)計2、什么是函數(shù)式程序設(shè)計In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. From wikipedia函數(shù)式程序設(shè)計是一種程序設(shè)計模型，它將計算機運算看作是數(shù)學(xué)中函數(shù)的計算，并且避免了狀態(tài)狀態(tài)以及變量變量的概

2、念。3、變量的不變性如果有多個進程在同時跑這一個程序，那么程序應(yīng)該先desposit 還是先 despositTwice？無論多少個進程在跑，因為我們本身沒有賦值操作，所以都不會影響到我們的最終結(jié)果。采用這樣的方式?jīng)]有辦法保持狀態(tài)，這也就是我們在之前概念中看到的無狀態(tài)性。程序設(shè)計能從馮諾依曼式的設(shè)計風(fēng)格中解放出來嗎？函數(shù)式程序設(shè)計及其程序代數(shù)John Backus于1977年接受ACM圖靈獎時的講演稿4、馮諾依曼和函數(shù)式程序的比較 求內(nèi)積的馮諾依曼程序該程序值得注意的幾個性質(zhì):1) 程序中的語句以某種復(fù)雜的規(guī)則作用在不可見的“狀態(tài)”上。2) 程序不是層次性的，除了賦值語句的右部外。3) 程序是

3、動態(tài)和重復(fù)的。4) 程序是通過對變量i的修改和賦值語句的重復(fù)而逐字計算的。5) 部分?jǐn)?shù)據(jù)(如n)是局部于程序的,因而缺少通用性。6) 程序命名了其中的量, 因而只對名為a 和b 的向量有效。7) 程序的“內(nèi)務(wù)” 操作是用分散在幾處的符號來表示的。 求內(nèi)積的函數(shù)式程序Def Innerproduct (Insert +)(Apply To All )Transpose或簡寫為Def IP ( / + )( )Trans將已知函數(shù)組合成新函數(shù)的函數(shù)型。fg 是先作用g再作用f所得的函數(shù)。f是把f作用到每個分量上的函數(shù)。f : x 表示把f作用到對象x上所得的結(jié)果Def IP ( / + )( )T

4、ransIP: , =(IP的定義) = ( / + ) ( )Trans: , ( 的作用) = ( / + ) :( ( ) : ( Trans: , ) )(Trans的作用) = ( / + ) :( ( ) : , , )( 的作用) = ( / + ) : : , : , : ( 的作用) = ( / + ): ( / 的作用) = +: 6, +: ( + 的作用) = +: ( + 的作用) = 28Def IP ( / + )( )Trans和馮諾依曼程序的比較：1) 該程序只作用在單個變元上, 沒有隱含的狀態(tài)及狀態(tài)轉(zhuǎn)換規(guī)則。2) 該程序具有層次性, 它由三個較簡單的函數(shù)(

5、+ , , Trans ) 和三個函數(shù)型fg，f和/f構(gòu)成。3) 該程序是靜態(tài)和非重復(fù)的, 無需考慮其執(zhí)行情況。4) 該程序作用在整個概念單位上, 而不是作用在單個的字上, 它可分為三步, 但沒有一步是重復(fù)的。5) 該程序本身不涉及任何數(shù)據(jù), 它是完全通用的, 對任何相容向量對都有效。6) 該程序?qū)λ饔玫淖冊幻? 因而無需過程說明或復(fù)雜的代入規(guī)則就能作用到任一向量對上去。7) 該程序中所用到的“內(nèi)務(wù)” 函數(shù)及函數(shù)型在其它許多程序中也是通用的。5、FP系統(tǒng) “程序”只是沒有變量的函數(shù)。 FP系統(tǒng)是建立在使用一固定的函數(shù)型集合的基礎(chǔ)上的。這些函數(shù)型再加上一些簡單的定義，是由已知函數(shù)構(gòu)造新函數(shù)

6、的唯一手段。它們不涉及到變量和代入規(guī)則的使用，而是與程序相伴的代數(shù)的運算。 FP系統(tǒng)的所有函數(shù)都是同一類型的, 即從對象到對象的單一映射。1 ) 對象集合O;2 ) 把對象映射成對象的函數(shù)f的集合F ;3 ) 一個運算, 即作用;4 ) 函數(shù)型的集合F , 函數(shù)型的作用是將F中的已知函數(shù)或?qū)ο蠼M合成新的函數(shù);5 ) 定義集臺D , 它用來足義F 中的某些函數(shù), 并且對每個函數(shù)指定一個名;底元6、FP系統(tǒng)的組成7、函數(shù)式程序的性質(zhì)函數(shù)式程序?qū)ζ渥饔脤ο蠡蛑虚g結(jié)果不命名, 它不含變量, 沒有循環(huán), 沒有控制語句, 也沒有過程說明；它不需要初啟指令,不是逐字式性質(zhì)的程序；它是從簡單到復(fù)雜逐層構(gòu)造的；

7、程序中所用的是普遍適用的內(nèi)務(wù)操作型和運算符；該程序是完全通用的, 當(dāng)作用對象不滿足要求時, 一律得到結(jié)果; 它沒有限制不必要的求值次序 ; 利用代數(shù)法則能把該程序變?yōu)楦坝行А?、更易讀的程序(即遞歸定義的程序)。8、作為程序設(shè)計語言的FP系統(tǒng) 函數(shù)f是一個程序, 對象x是存貯單元的內(nèi)容, f : x 是對存貯單元的內(nèi)容x作用f后所得到的存貯單元的內(nèi)容, 定義集合是程序庫, 系統(tǒng)提供的原始函數(shù)和函數(shù)型是某種特定的程序設(shè)計語言中的基本語句。 一旦選定了原始函數(shù)和函數(shù)型, FP系統(tǒng)的基本結(jié)構(gòu)部分便為許多類型的語言提供了各種程序設(shè)計風(fēng)格和設(shè)計能力。9、 函數(shù)式程序設(shè)計的數(shù)學(xué)本質(zhì) 一切問題，歸根結(jié)底到最

8、后都是數(shù)學(xué)問題。 對于數(shù)學(xué)函數(shù)f(x) = y，無論在什么場景下，都會得到同樣的結(jié)果，這個我們稱之為函數(shù)的確定性。 對于賦值模型，同一個函數(shù)，同一個參數(shù)，會在不同的場景下計算出不同的結(jié)果。這正是賦值模型與數(shù)學(xué)模型的不兼容之處。 而函數(shù)式程序設(shè)計取消了賦值模型，則使數(shù)學(xué)模型與編程模型完美地達成了統(tǒng)一。10、狀態(tài)到底怎么辦？ 函數(shù)式編程是無狀態(tài)的，可是在現(xiàn)實情況中，狀態(tài)不可能一直保持不變，而狀態(tài)必然需要改變、傳遞。所以在函數(shù)式程序設(shè)計中將其保存在函數(shù)的參數(shù)中，作為函數(shù)的附屬品來傳遞。例：求例：求x的的n次方次方命令式程序設(shè)計命令式程序設(shè)計函數(shù)式程序設(shè)計函數(shù)式程序設(shè)計遞歸！11、相關(guān)的重要概念 St

9、ackOverflow與尾遞歸 惰性求值與并行 Lambda演算 高階函數(shù)與函數(shù)抽象性 Erlang、Haskell、Miranda、Lisp.12、函數(shù)式程序設(shè)計語言介紹 Lisp語言：最早的函數(shù)式語言McCarthy在1960年創(chuàng)立。其初始動機是為考慮匿名函數(shù)的表示, 開發(fā)一個用于Al的代數(shù)表處理語言。應(yīng)該說在L isp開發(fā)早期演算的影響甚微, 但由于Lisp本身有很好的數(shù)學(xué)優(yōu)美性, 它對函數(shù)語言的發(fā)展產(chǎn)生了重大影響。Lisp至今仍是最流行的函數(shù)語言, 主要用于智能系統(tǒng)的編程出于效率的考慮, 它現(xiàn)已變成一種不純的、有副作用的函數(shù)語言。12、函數(shù)式程序設(shè)計語言介紹 FP語言：開創(chuàng)純函數(shù)語言研

10、究之先河FP 語言用固定的泛函數(shù)結(jié)構(gòu)和一些簡單定義作為從現(xiàn)存函數(shù)構(gòu)造新函數(shù)的唯一工具, 沒有使用變量和替換規(guī)則, 程序的構(gòu)造可視為程序代數(shù)操作。FP語言擺脫了以演算為基礎(chǔ)的函數(shù)語言中存在的實現(xiàn)和表達能力方面的問題。在FP中, 函數(shù)是無類型的, 這極大簡化了語法和語義, 然而, 由于任意函數(shù)可互相組合, 所以某些總產(chǎn)生的函數(shù)也可被構(gòu)造, 這樣當(dāng)構(gòu)造函數(shù)時, 程序員必須仔細檢查所用的構(gòu)造函數(shù), 加重了編程負擔(dān)。FP沒有高階能力, 從而也給表達能力帶來了一些影響。12、函數(shù)式程序設(shè)計語言介紹 Miranda語言：商用純函數(shù)語言Miranda程序是定義、函數(shù)和其他數(shù)據(jù)目標(biāo)的集合, 寫成遞歸方程的形式。它無需類型說明, 類型推理由編譯器完成。其用戶定義類型的引入主要通過說明一個自由代數(shù)實現(xiàn), 這個自由代數(shù)還可附有一組規(guī)則。很多在其他語言中必須表示成抽象類型的數(shù)據(jù)類型可在Miranda中用代數(shù)數(shù)據(jù)類型和相關(guān)規(guī)則來表示。盡管如此，它還是提供了抽象類型機制, 通過顯式的Abstype說明來實現(xiàn)。12、函數(shù)式程序設(shè)計語言介紹 Haskell語言：通用的純函數(shù)語言Yale大學(xué)的Hudak等從統(tǒng)一函數(shù)語言的目的出發(fā), 設(shè)計了Haskell語言, 它幾乎包括了現(xiàn)今函數(shù)語言的所有優(yōu)點, 當(dāng)然, 它能否取代現(xiàn)行語言還有特時間來證明。 其他函數(shù)式語