函數式程序設計

傳統程序設計語言中的賦值等概念，在函數式程序設計語言中消失。函數式程序的一個最本質的特性，就是函數值唯一地由其參數值所確定。只要使用相同的參數值，對此程序的不同的調用總是得到相同的結果。這種性質稱為引用透明性，有助於程序的模塊化。函數式程序設計語言具有較強的組織數據結構的能力，可以把某一數據結構（如數組）作為單一值處理；可以把函數作為參數，其結果也可為函數，這種定義的函數稱為高階函數。這些由函數表達式所表示的程序簡明、緊湊和易於維護。

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

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

函數式程序設計受到重視的原因有很多。首先，由於產生了“軟件危機”，人們企圖探討一種擺脱這種困境的新型程序設計方式，而函數式程序設計具有不少獨特之處。其次,超大規模集成電路技術的發展,為發揮函數式程序設計語言的潛在並行性提供了物質基礎。可以預期，一些具有諸如高度並行性等特點的非諾伊曼式計算機將會出現。隨着硬件技術的發展、軟件方法的研究，以及應用範圍的不斷擴大，函數式程序設計將得到發展，並在新一代計算機系統中起重要作用。

函數語言以λ-演算為其語義基礎,它的基本機制是函數對參數的作用,函數是程序的基本項,程序的編制便是函數的遞歸構造過程。從數學觀點看,函數是從一個域(定義域)到另一個域(值域)的映射,即函數描述了兩個域上元素的對應關係。因此,函數語言是一種描述性語言,它只給出需求解問題的定義而不需給出具體的求解過程和細節。求解過程是語言本身經過應用一系列重寫規則實現的。λ-演算作為一個重寫系統滿足合流性,即一個項若有範式,則不同的重寫策略將導致相同範式,從而保證程序求解的唯一性。

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

最早的函數語言可數Lisp,是McCarthy在1960年創立的,其初始動機是為考慮匿名函數的表示,開發一個用於Al的代數表處理語言。

應該説在Lisp開發早期卜演算的影響甚微,但由於Lisp本身有很好的數學優美性,它對函數語言的發展產生了重大影響。Lisp至今仍是最流行的函數語言,主要用於智能系統的編程。出於效率的考慮,它現已變成一種不純的、有副作用的函數語 ^[1]  。