函數(shù)式程序設(shè)計(jì)（functional programming）是指編寫函數(shù)式程序的方法與過程，其主要任務(wù)在于定義(或構(gòu)造)函數(shù)以求解所提出的問題。定義的函數(shù)(可看作主程序)可能包括一些輔助函數(shù)(可看作子程序)。計(jì)算機(jī)按照所定義函數(shù)的相應(yīng)表達(dá)式，根據(jù)計(jì)算規(guī)則逐步計(jì)算，最后得到所需的結(jié)果。表達(dá)式中可能包含函數(shù)名，計(jì)算時(shí)可將其相應(yīng)的定義作為歸約規(guī)則。函數(shù)式程序設(shè)計(jì)的一個(gè)顯著特點(diǎn)是：若一個(gè)表達(dá)式有定義，則該表達(dá)式的最后結(jié)果與其計(jì)算次序無關(guān)。[1]

中文名

函數(shù)式程序設(shè)計(jì)

外文名

functional programming

語義基礎(chǔ)

λ-演算

實(shí)質(zhì)

函數(shù)的遞歸構(gòu)造過程

應(yīng)用學(xué)科

計(jì)算機(jī)科學(xué)

組成

原始函數(shù)、定義函數(shù)和函數(shù)型

特性

傳統(tǒng)程序設(shè)計(jì)語言中的賦值等概念，在函數(shù)式程序設(shè)計(jì)語言中消失。函數(shù)式程序的一個(gè)最本質(zhì)的特性，就是函數(shù)值唯一地由其參數(shù)值所確定。只要使用相同的參數(shù)值，對此程序的不同的調(diào)用總是得到相同的結(jié)果。這種性質(zhì)稱為

引用透明性

，有助于程序的模塊化。函數(shù)式程序設(shè)計(jì)語言具有較強(qiáng)的組織數(shù)據(jù)結(jié)構(gòu)的能力，

數(shù)組

可以把某一數(shù)據(jù)結(jié)構(gòu)（如數(shù)組）作為單一值處理；可以把函數(shù)作為參數(shù)，其結(jié)果也可為函數(shù)，這種定義的函數(shù)稱為高階函數(shù)。這些由函數(shù)表達(dá)式所表示的程序簡明、緊湊和易于維護(hù)。

過去，這種程序設(shè)計(jì)稱為應(yīng)用性程序設(shè)計(jì)。1977年，J.巴克斯提出函數(shù)式程序設(shè)計(jì)的概念。一般認(rèn)為表處理語言(LISP)是最早的函數(shù)式程序設(shè)計(jì)語言。但是，LISP的重點(diǎn)是將函數(shù)應(yīng)用于對象，以產(chǎn)生新的對象，必要時(shí)再上升為函數(shù)。巴克斯所提出的函數(shù)式程序設(shè)計(jì)，則是引用函數(shù)型產(chǎn)生新函數(shù)，程序設(shè)計(jì)時(shí)從一般的對象空間上升到函數(shù)空間，因而具有優(yōu)越的數(shù)學(xué)性質(zhì)，有助于程序的理解、推理和驗(yàn)證。

用途

由于函數(shù)式程序設(shè)計(jì)語言的簡明性和獨(dú)特的表達(dá)能力，可用它來研究傳統(tǒng)程序設(shè)計(jì)語言的語義。一種方法是用于確定一個(gè)解釋程序的定義，作為被研究的語言的語義；另一種方法是將被研究的語言寫成的程序轉(zhuǎn)換成與之等價(jià)的函數(shù)式程序。在人工智能領(lǐng)域中，需要用復(fù)雜的算法去處理一些復(fù)雜的（通常是符號的）數(shù)據(jù)結(jié)構(gòu)。LISP語言成功地應(yīng)用于這一領(lǐng)域，說明了函數(shù)式程序設(shè)計(jì)的獨(dú)特優(yōu)越性。巴克斯分析了傳統(tǒng)程序設(shè)計(jì)語言的缺陷，認(rèn)為這些缺陷主要是由于諾伊曼式系統(tǒng)結(jié)構(gòu)所造成的。他所提出的函數(shù)式程序設(shè)計(jì)(簡稱FP)，擺脫了傳統(tǒng)的諾伊曼計(jì)算機(jī)結(jié)構(gòu)，需要一種新的非諾伊曼式的系統(tǒng)結(jié)構(gòu)為后援。一些具有新概念的計(jì)算機(jī)，如歸約機(jī)、數(shù)據(jù)流機(jī)，以及專為某種函數(shù)式語言（如FP）設(shè)計(jì)的計(jì)算機(jī)正在研究和發(fā)展中?，F(xiàn)代既需要研究在諾伊曼式計(jì)算機(jī)上如何更有效地實(shí)現(xiàn)函數(shù)式程序設(shè)計(jì)語言的問題，也需要研究適應(yīng)這種語言的新型計(jì)算機(jī)結(jié)構(gòu)。

重要性

函數(shù)式程序設(shè)計(jì)受到重視的原因有很多。首先，由于產(chǎn)生了“軟件危機(jī)”，人們企圖探討一種擺脫這種困境的新型程序設(shè)計(jì)方式，而函數(shù)式程序設(shè)計(jì)具有不少獨(dú)特之處。其次，超大規(guī)模集成電路技術(shù)的發(fā)展，為發(fā)揮函數(shù)式程序設(shè)計(jì)語言的潛在并行性提供了物質(zhì)基礎(chǔ)?？梢灶A(yù)期，一些具有諸如高度并行性等特點(diǎn)的非諾伊曼式計(jì)算機(jī)將會(huì)出現(xiàn)。隨著硬件技術(shù)的發(fā)展、軟件方法的研究，以及應(yīng)用范圍的不斷擴(kuò)大，函數(shù)式程序設(shè)計(jì)將得到發(fā)展，并在新一代計(jì)算機(jī)系統(tǒng)中起重要作用。

函數(shù)語言

從數(shù)學(xué)觀點(diǎn)看，函數(shù)是從一個(gè)域(定義域)到另一個(gè)域(值域)的映射，即函數(shù)描述了兩個(gè)域上元素的對應(yīng)關(guān)系。因此，函數(shù)語言是一種描述性語言，它只給出需求解問題的定義而不需給出具體的求解過程和細(xì)節(jié)。求解過程是語言本身經(jīng)過應(yīng)用一系列重寫規(guī)則實(shí)現(xiàn)的。

函數(shù)語言

λ-演算作為一個(gè)重寫系統(tǒng)滿足合流性，即一個(gè)項(xiàng)若有范式，則不同的重寫策略將導(dǎo)致相同范式，從而保證程序求解的唯一性。

由上可知，函數(shù)語言具有相當(dāng)清晰簡明的指稱語義和重寫操作語義，這對程序正確性驗(yàn)證尤為重旁。函數(shù)語言的主要優(yōu)點(diǎn)是：(1)數(shù)學(xué)優(yōu)美性,(2)簡單性,（3）引用透明性。正是由于這些優(yōu)點(diǎn)，所以易于語言編寫程序，且程序易讀易維護(hù)，程序也很短小簡練。特別地，程序具有較好的代數(shù)性質(zhì)，易于程序演繹和正確性驗(yàn)證。引用透明性帶來的另一個(gè)主要優(yōu)點(diǎn)是程序具有天生的并行性。

最早的函數(shù)語言可數(shù)Lisp,是McCarthy在1960年創(chuàng)立的，其初始動(dòng)機(jī)是為考慮匿名函數(shù)的表示，開發(fā)一個(gè)用于Al的代數(shù)表處理語言。

應(yīng)該說在Lisp開發(fā)早期卜演算的影響甚微，但由于Lisp本身有很好的數(shù)學(xué)優(yōu)美性，它對函數(shù)語言的發(fā)展產(chǎn)生了重大影響。Lisp至今仍是最流行的函數(shù)語言，主要用于智能系統(tǒng)的編程。出于效率的考慮，它現(xiàn)已變成一種不純的、有副作用的函數(shù)語。