純函數式程式設計

電腦科學中,純函數式編程通常指示一種程式設計範式,這是建造電腦程式的結構和元素的一種風格,就是將所有計算都當作數學函式的求值(evaluation)。純函數式程式設計還可以定義為禁用狀態英語State (computer science)變更和可變資料。

純函數式程式設計主要在於確保函式遵守函數式範式,只依賴於它們的實際參數,而不用管任何全域或局部的狀態。

純與非純的區別

編輯

在純與非純函數式程式設計之間的確切區別是有爭議的事情[1]

當一個程式使用了某些函數式程式設計概念的時候, 比如頭等函式高階函式,它通常就被稱為是函數式的[2]。但是,頭等函式不必然是純函數式的,由於它可以使用來自指令式範式的技術,比如陣列輸入/輸出方法,故而它們不是純函式程式。事實上,最早被引證為函數式的程式語言,IPLLISP[3][4],按照當前定義都是非純函數式語言。

純函數式資料結構英語Purely functional data structure必然是永續性資料結構。永續性是函數式程式設計所要求的,如果沒有它,相同的計算就可能返回不同的結果。函數式程式設計可以使用非純函數式的永續性資料結構,比如永續性陣列英語Persistent array,而這些資料結構不可以用在純函數式程式中。

純粹採用函數式程式設計的基礎部件(如mapreducefilter等),進行回應式編程非同步資料流程編程)的程式設計範式,被稱為函數式回應式編程

純函數式程式設計的性質

編輯

單賦值

編輯

任何改變現存值的賦值(比如x := x + 1),在純函數式程式設計中都是不允許的[5]。在現今的函數式程式設計中,賦值是被勸阻的,用以支援也叫做「初始化」的單賦值。單賦值是名字繫結的用例,不同於本文其他部分描述的賦值之處在於,它只能做一次,通常是在變數被建立的時候,不允許後續的重新賦值。純函數式程式設計共通於資料流程編程的這個特徵,簡化了平行計算[6],因為求值的兩個部份如果都是純函數式的就會永不互動。

參照透明性

編輯

如果將一個表達式替代為它的值只在程式執行的特定點上是有效的,則這個表達式不是參照透明性英語Referential transparency的。這些順序點的定義和次序是指令式編程的理論基礎。參照透明性的表達式可以在任何時間求值,既不需要定義順序點也根本不需要對求值次序的任何保證,不需要做這些考慮的編程叫做純函數式程式設計。

寫參照透明性風格的代碼的好處是能得到智慧型編譯器,易於靜態代碼分析,和自動進行更好的代碼最佳化。強制參照透明性的語言的主要缺點是,使得表達天然適合指令式編程的步驟序列的運算,更加蠢笨和更不簡潔。這些語言通常結合某種機制,使得這些任務更加容易而又保持語言的純函數式性質,比如明確子句文法英語definite clause grammar單子

參照透明性英語Referential transparency要求表達式是純函式的,也就是表達式的值對於相同的輸入也必須是相同的,它的求值不能有副作用。在現今的函數式程式設計中,很少使用副作用。缺少副作用導致程式易於形式驗證。函數式語言比如Standard MLSchemeScala不限制副作用,但是編程者會習慣性的避免使用它們[7]。函數式語言Haskell使用單子行動來表達副作用,比如輸入/輸出和其他有狀態的計算[8][9]

資料結構

編輯

純函數式資料結構,是可以用純函數式語言如Haskell實現的資料結構。實際上,這意味著建造這種資料結構,必須只使用永續性資料類型比如元組和類型積類型英語product type,和基本類型如整數、字元、字串。純函數式資料類型,同它們的指令式對應者相比,經常以不同的方式表現[10]。例如,具有以恆定時間來訪問和更新的陣列,是多數指令式語言的基本構件,而且很多指令式資料結構,比如雜湊表二元堆積,也是基於陣列的。陣列可以被替代為對映隨機訪問列表英語Linked list#Random access lists,它容許純函數式實現,但是訪問和更新時間複雜度是對數。因此,純函數式資料結構可以用在非純函數式語言中,但是它們可能不是能得到的最有效率的工具,特別是不要求永續性的情況下。

一般而言,把一個指令式程式轉換成純函數式程式,還需要確保原先可變的那些資料結構,變為顯式的傳遞給並返回自更新它們的函式,這是叫做儲存傳遞風格的一種程式結構。

求值策略

編輯

每種求值策略對當純函數式程式設計時都返回相同的結果。特別是,它確保編程者不需要考慮程式是按什麼次序求值的,因為及早求值(嚴格求值)將返回同惰性求值(非嚴格求值)相同的結果。但是,仍有可能一個及早求值可以不終止,而相同程式的惰性求值會停機。純函數式的好處是惰性求值是可以被更容易的實現,因為所有表達式在任何時刻都返回同樣的結果,不用管程式的狀態,它們的求值可以隨著需要而推延。

純函數式語言

編輯

純函數式語言是只認可純函式編程的語言。但是純函數式程式可以用非純函數式的語言寫成。純函數式語言主要有:

歷史上曾有重要影響的還有NPLHopeSASLKRCMiranda以及Joy等。

參見

編輯

參照

編輯
  1. ^ Sabry, Amr. What is Purely Functional Language ?. Journal of Functional Programming. January 1993, 8 (1): 1–22. doi:10.1017/S0956796897002943. 
  2. ^ Atencio, Luis. Functional Programming in Javascript. Manning Publications. 18 June 2016. ISBN 978-1617292828. 
  3. ^ 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.
  4. ^ 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). 
  5. ^ Crossing borders: Explore functional programming with Haskell 網際網路檔案館存檔,存檔日期November 19, 2010,., by Bruce Tate
  6. ^ Marlow, Simon. Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. O'Reilly Media. 18 June 2013. ISBN 978-1449335946. 
  7. ^ Matthias Felleisen et al., How To Design Programs, MIT Press. [2021-02-07]. (原始內容存檔於2021-05-02). 
  8. ^ Haskell 98 report, http://www.haskell.org頁面存檔備份,存於網際網路檔案館).
  9. ^ 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
  10. ^ Purely functional data structures頁面存檔備份,存於網際網路檔案館) by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4