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

中文名

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

外文名

functional programming

語義基礎(chǔ)

λ-演算

實質(zhì)

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

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

計算機科學(xué)

組成

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

特性

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

引用透明性

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

數(shù)組

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

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

用途

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

重要性

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

函數(shù)語言

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

函數(shù)語言

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

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

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

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