純函數式編程
在計算機科學中，純函數式編程通常指示一種編程范型，這是建造計算機程序的結構和元素的一種風格，就是將所有計算都當作數學函數的求值（evaluation）。純函數式編程還可以定義為禁用狀態變更和可變數據。
純與非純的區別
編輯在純與非純函數式編程之間的確切區別是有爭議的事情[1]。
當一個程序使用了某些函數式編程概念的時候， 比如頭等函數和高階函數，它通常就被稱為是函數式的[2]。但是，頭等函數不必然是純函數式的，由於它可以使用來自指令式范型的技術，比如數組或輸入/輸出方法，故而它們不是純函數程序。事實上，最早被引證為函數式的編程語言，IPL和LISP[3][4]，按照當前定義都是非純函數式語言。
純函數式數據結構必然是持久性數據結構。持久性是函數式編程所要求的，如果沒有它，相同的計算就可能返回不同的結果。函數式編程可以使用非純函數式的持久性數據結構，比如持久性數組，而這些數據結構不可以用在純函數式程序中。
純粹採用函數式編程的基礎部件（如map、reduce、filter等），進行響應式編程（異步數據流程編程）的編程范型，被稱為函數式響應式編程。
純函數式編程的性質
編輯單賦值
編輯任何改變現存值的賦值（比如x := x + 1），在純函數式編程中都是不允許的[5]。在現今的函數式編程中，賦值是被勸阻的，用以支持也叫做「初始化」的單賦值。單賦值是名字綁定的用例，不同於本文其他部分描述的賦值之處在於，它只能做一次，通常是在變量被創建的時候，不允許後續的重新賦值。純函數式編程共通於數據流程編程的這個特徵，簡化了並行計算[6]，因為求值的兩個部份如果都是純函數式的就會永不交互。
參照透明性
編輯如果將一個表達式替代為它的值只在程序執行的特定點上是有效的，則這個表達式不是參照透明性的。這些順序點的定義和次序是指令式編程的理論基礎。參照透明性的表達式可以在任何時間求值，既不需要定義順序點也根本不需要對求值次序的任何保證，不需要做這些考慮的編程叫做純函數式編程。
寫參照透明性風格的代碼的好處是能得到智能編譯器，易於靜態代碼分析，和自動進行更好的代碼優化。強制參照透明性的語言的主要缺點是，使得表達天然適合指令式編程的步驟序列的運算，更加蠢笨和更不簡潔。這些語言通常結合某種機制，使得這些任務更加容易而又保持語言的純函數式性質，比如明確子句文法和單子。
參照透明性要求表達式是純函數的，也就是表達式的值對於相同的輸入也必須是相同的，它的求值不能有副作用。在現今的函數式編程中，很少使用副作用。缺少副作用導致程序易於形式驗證。函數式語言比如Standard ML、Scheme和Scala不限制副作用，但是編程者會習慣性的避免使用它們[7]。函數式語言Haskell使用單子行動來表達副作用，比如輸入/輸出和其他有狀態的計算[8][9]。
數據結構
編輯純函數式數據結構，是可以用純函數式語言如Haskell實現的數據結構。實際上，這意味着建造這種數據結構，必須只使用持久性數據類型比如元組、和類型、積類型，和基本類型如整數、字符、字符串。純函數式數據類型，同它們的指令式對應者相比，經常以不同的方式表現[10]。例如，具有以恆定時間來訪問和更新的數組，是多數指令式語言的基本構件，而且很多指令式數據結構，比如散列表和二叉堆，也是基於數組的。數組可以被替代為映射或隨機訪問列表，它容許純函數式實現，但是訪問和更新時間複雜度是對數。因此，純函數式數據結構可以用在非純函數式語言中，但是它們可能不是能得到的最有效率的工具，特別是不要求持久性的情況下。
一般而言，把一個指令式程序轉換成純函數式程序，還需要確保原先可變的那些數據結構，變為顯式的傳遞給並返回自更新它們的函數，這是叫做存儲傳遞風格的一種程序結構。
求值策略
編輯每種求值策略對當純函數式編程時都返回相同的結果。特別是，它確保編程者不需要考慮程序是按什麼次序求值的，因為及早求值（嚴格求值）將返回同惰性求值（非嚴格求值）相同的結果。但是，仍有可能一個及早求值可以不終止，而相同程序的惰性求值會停機。純函數式的好處是惰性求值是可以被更容易的實現，因為所有表達式在任何時刻都返回同樣的結果，不用管程序的狀態，它們的求值可以隨着需要而推延。
純函數式語言
編輯純函數式語言是只認可純函數編程的語言。但是純函數式程序可以用非純函數式的語言寫成。純函數式語言主要有：
參見
編輯引用
編輯- ^ Sabry, Amr. What is Purely Functional Language ?. Journal of Functional Programming. January 1993, 8 (1): 1–22. doi:10.1017/S0956796897002943.
- ^ Atencio, Luis. Functional Programming in Javascript. Manning Publications. 18 June 2016. ISBN 978-1617292828.
- ^ 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 which proved theorems from Principia Mathematica automatically. In order to accomplish this, they had to invent a language and a paradigm which, which viewed retrospectively, embeds functional programming.
- ^ McCarthy, John. History of Lisp. In ACM SIGPLAN History of Programming Languages Conference. June 1978: 217–223 [2020-04-24]. doi:10.1145/800025.808387. （原始內容存檔於2008-06-07）.
- ^ Crossing borders: Explore functional programming with Haskell 網際網路檔案館的存檔，存檔日期November 19, 2010，., by Bruce Tate
- ^ Marlow, Simon. Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. O'Reilly Media. 18 June 2013. ISBN 978-1449335946.
- ^ Matthias Felleisen et al., How To Design Programs, MIT Press. [2021-02-07]. （原始內容存檔於2021-05-02）.
- ^ Haskell 98 report, http://www.haskell.org （頁面存檔備份，存於網際網路檔案館）.
- ^ Imperative Functional Programming, Simon Peyton Jones and Phil Wadler, Conference Record of the 20th Annual ACM Symposium on Principles of Programming Languages, pages 71–84, 1993
- ^ Purely functional data structures （頁面存檔備份，存於網際網路檔案館） by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4