函數式編程，或稱函數程序設計、泛函編程（英語：Functional programming），是一種編程范型，它將電腦運算視為函數運算，並且避免使用程式狀態以及可變物件。
在函數式編程中，函數是頭等對象即頭等函數，這意味着一個函數，既可以作為其它函數的輸入參數值，也可以從函數中返回值，被修改或者被分配給一個變量。λ演算是這種范型最重要的基礎，λ演算的函數可以接受函數作為輸入參數和輸出返回值。
比起指令式編程，函數式編程更加強調程序執行的結果而非執行的過程，倡導利用若干簡單的執行單元讓計算結果不斷漸進，逐層推導複雜的運算，而不是設計一個複雜的執行過程。
阿隆佐·邱奇在1930年代開發的λ演算[1]，是建造自函數應用的一種計算形式系統。在1937年，艾倫·圖靈證明了λ演算和圖靈機是等價的計算模型[2]，展示了λ演算是圖靈完備性的。λ演算形成了所有函數式編程語言的基礎。另一種等價的理論公式化是組合子邏輯，它由Moses Schönfinkel和哈斯凱爾·柯里在1920年代和1930年代開發[3]。
邱奇後來又開發了簡單類型λ演算，它通過向所有的項指定一個類型而擴展了λ演算。[4]這個系統形成了靜態類型函數式編程的基礎。
於20世紀50年代後期，John McCarthy在麻省理工學院，開發了早期的函數式語言LISP，運行在大型IBM主機（IBM700/7000系列）上[5]。LISP的函數定義借鑑了邱奇的λ表示法[6]，並擴展了標籤構造來允許遞歸函數[7]。最開始的LISP是多范型語言，並且隨着新的范型的發展，越來越多的編程風格得到了支持。後來發展出來的方言比如Scheme、Clojure，和分支語言比如Dylan等，試圖圍繞一個清晰的函數式核心，來得出簡化和理性化的LISP，而Common Lisp旨在保留並更新它所替代的各種更早先LISP方言的那些范型特徵。[8]
而於1956年發明的IPL語言，一般被認為是第一個基於計算機的函數式編程語言。[9] 它是一種用於操縱符號列表的匯編式語言。它有一個生成器的概念，相當於一個接受函數作為參數的函數，並且，由於它是匯編級語言，代碼可以是數據，因此IPL可以被視為具有高階函數。但是，它在很大程度上依賴於改變列表的結構和類似的指令式編程特徵。
在1960年代早期，Kenneth E. Iverson開發了APL語言，在他1962年出版的《A Programming Language》一書中對其有所介紹。[10]APL對John Backus的FP語言施加了巨大的影響。在20世紀90年代早期，Iverson和Roger Hui創造了J語言。在20世紀90年代中期，以前曾與Iverson合作過的Arthur Whitney創建了K語言，後者在金融行業中與其衍生出來的Q語言一起被商業化使用。
1977年John Backus在他的圖靈獎頒獎演講《編程可以從馮·諾依曼式風格中解放出來嗎？一種函數式風格及其程序代數》中，展示了他提出的FP[11]。他將函數式編程定義為通過「組合形式」以分層方式構建，允許「程序代數」; 在現代語言中，這意味着函數式程序應遵循複合性原理。Backus的論文推廣了函數式編程的研究，雖然它強調的是函數級編程而不是現在所說的λ演算風格。
1973年愛丁堡大學的Robin Milner發明了ML語言，它的語法受到了ISWIM的啟發。同年，David Turner在聖安德魯斯大學開發了SASL語言，它基於了ISWIM的應用式子集[12]。在1976年，Turner重新設計並重新實現它為惰性求值語言[13]。在20世紀70年代的愛丁堡，Rod Burstall和John Darlington開發了NPL語言。[14] NPL基於Kleene的遞歸方程，並在他們的程序轉換工作中首次引入。[15] 然後Rod Burstall、David MacQueen和Don Sannella結合了來自ML的多態類型檢查，從NPL派生出了Hope語言。[16]ML最終發展成幾種語言，其中最常見的是OCaml和Standard ML。
在1970年代，Guy L. Steele和Gerald Jay Sussman開發了Scheme，如有影響力的「λ論文集」和經典的1985年教科書《計算機程序的構造和解釋》中所描述的那樣。Scheme是使用詞法作用域和尾調用優化的第一個Lisp方言，將函數式編程的影響力提升到更廣泛的範圍，讓更多的編程語言社區接觸到它們。
在1980年代，佩爾·馬丁-洛夫開發了直覺類型論（也稱為構造類型論），它將函數式編程與表現為依賴類型的數學證明聯繫起來。這導致了交互式定理證明的新方法的產生，並影響了後續的函數式編程語言的發展。
在1985年David Turner開發的惰性求值函數式語言Miranda出現，它採用了來自ML與Hope語言的概念，作為他先前所設計的SASL和KRC語言的後繼者。Miranda對後來的Haskell有很強的影響，由於它當時是專有軟件，所以Haskell社區於1987年開始達成共識，以形成函數式編程研究的開放標準，對標準的實現自1990年以來一直在進行中。
最近，它在基於CSG幾何框架構建的OpenSCAD語言的參數CAD中得到了應用，雖然在重新賦值上的限制（所有值都被當作常量），導致了不熟悉函數式編程的用戶混淆。[17]
函數式編程長期以來在學術界流行，但幾乎沒有工業應用。造成這種局面的主因是函數式編程常被認為嚴重耗費CPU和記憶體資源[18] ，這是由於在早期實現函數式編程語言時並沒有考慮過效率問題，而且面向函數式編程特性，如保證參照透明性等，要求獨特的數據結構和算法。[19]
然而，最近幾種函數式編程語言已經在商業或工業系統中使用[20]，例如：
其他在工業中使用的函數式編程語言包括多范型的Scala[23]、F#，還有Wolfram語言、Common Lisp、Standard ML和Clojure等。
教育方面，函數式編程一直受到了很大的重視，很多學校使用函數式編程來教授算法和幾何的相關概念[24]。
純函數式編程語言通常不允許直接使用程式狀態以及可變對象，典型語言有：Miranda、Haskell和Idris等。
非純函數式編程語言可按類型系統分為兩類：
其他特殊風格的函數式編程語言有：APL/J和jq等。
McCarthy, John. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-09-23]. （原始內容 (PDF)存檔於2020-11-07）. There were two motivations for developing a language for the IBM 704. First, IBM was generously establishing a New England Computation Center at M.I.T. …… Second, IBM was undertaking to develop a program for proving theorems in plane geometry (based on an idea of Marvin Minsky’s), ……. ……
In connection with IBM’s plane geometry project, Nathaniel Rochester and Herbert Gelernter (on the advice of McCarthy) decided to implement a list processing language within FORTRAN, ……. This work was undertaken by Herbert Gelernter and Carl Gerberich at IBM and led to FLPL, standing for FORTRAN List Processing Language. ……
I spent the summer of 1958 at the IBM Information Research Department at the invitation of Nathaniel Rochester and chose differentiating algebraic expressions as a sample problem. It led to the following innovations beyond FLPL:
a. Writing recursive function definitions using conditional expressions. …… b. The maplist function that forms a list of applications of a functional argument to the elements of a list. …… c. To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers. d. The recursive definition of differentiation made no provision for erasure of abandoned list structure. ……
The implementation of LISP began in Fall 1958. …… The programs to be hand-compiled were written in an informal notation called M-expressions intended to resemble FORTRAN as much as possible.
John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-09-23]. （原始內容存檔 (PDF)於2020-11-07）. To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers.
David Turner. Some History of Functional Programming Languages (PDF). [2021-10-25]. （原始內容 (PDF)存檔於2020-04-15）. LISP was not based on the lambda calculus, despite using the word 「LAMBDA」 to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions. (McCarthy made these statements, or very similar ones, in a contribution from the floor at the 1982 ACM symposium on LISP and functional programming in Pittsburgh. No written version of this exists, as far as know.)
John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. (PDF). Communications of the ACM (ACM New York, NY, USA). 1960, 3 (4): 184–195 [2021-02-24]. doi:10.1145/367177.367199. （原始內容 (PDF)存檔於2021-02-19）.
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-09-23]. ISBN 0-262-13011-4. （原始內容 (PDF)存檔於2021-03-02）. A function can be simply a name. In this case its meaning must be previously understood. A function may be defined by using the lambda notation and establishing a correspondence between the arguments and the variables used in a form. If the function is recursive, it must be given a name by using a label. ……
When a symbol stands for a function, the situation is similar to that in which a symbol stands for an argument. When a function is recursive, it must be given a name. This is done by means of the form LABEL, which pairs the name with the function definition on the a-list. The name is then bound to the function definition, just as a variable is bound to its value.
In actual practice, LABEL is seldom used. It is usually more convenient to attach the name to the definition in a uniform manner. This is done by putting on the property list of the name, the symbol EXPR followed by the function definition. The pseudo-function define used at the beginning of this section accomplishes this. When apply interprets a function represented by an atomic symbol, it searches the p-list of the atomic symbol before searching the current a-list. Thus a define will override a LABEL.
The memoir of Herbert A. Simon (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 claims that he, Al Newell, and Cliff Shaw are "...commonly adjudged to be the parents of [the] artificial intelligence [field]," for writing Logic Theorist, a program that proved theorems from Principia Mathematica automatically. To accomplish this, they had to invent a language and a paradigm that, viewed retrospectively, embeds functional programming. Turner, D.A. An Implementation of SASL. University of St. Andrews, Department of Computer Science Technical Report.
R.M. Burstall. Design considerations for a functional programming language. Invited paper, Proc. Infotech State of the Art Conf. "The Software Revolution", Copenhagen, 45–57 (1977)
