Skip to content

function

ccckmit edited this page Apr 18, 2022 · 3 revisions

函數

函數式語言與 Lambda Calculus

我們大部分的人,都會從 C / Java / Python / JavaScript 這類的《程序導向語言》開始學。

但是 LISP 這類的《函數式程式語言》,其設計想法和《程序導向語言》有很大不同。

不同點在哪呢?

基本上就是:一切皆函數!

於是在 LISP 當中,沒有 for/while 這類迴圈,一切都要用遞迴的方式去寫,要重複 n 次就從 n 開始遞迴到 0 結束

於是,程式設計只剩下了《基本型態與函數》,一個非常潔淨的世界

潔淨到極致,差不多就是 Lambda Calculus 了!

Lambda Calculus 是 Alonzo Church 在電腦還沒發明的1930 年代,透過紙和筆,在腦袋中發展出來的一種數學代換形式。

Church 發展並探討了這種代換形式的能力極限,將 1900 年希爾伯特提出 23 個問題中的第二題《算術公理之相容性》,用不同於《哥德爾不完備定理》的方式呈現出來。

於是 Church 寫了以下這篇論文

其中的結論如下

後來圖靈 (Alan Turing) 用機器的想法,發展出圖靈機,並證明了《停止問題》不可解。

現在很多程序員都知道《停止問題》,但是 Church 的《不可解之數論問題》則很少人知道。

畢竟,機器是比較容易形象化的,而數學與推論,則很難形象化!

但是,Church 的 Lambda Calculus 對程序員而言,比圖靈機更有價值,那些函數式的寫法,雖然奇特,但卻完全能變成一種程式語言,於是 LISP / ML / Haskell 這些語言被創造出來了。

雖然 JavaScript 不算是函數式語言,但由於函數在 JavaScript 裡也是第一等公民,屬於基本型態的一種,而且支援《閉包》的機制,所以很適合用來學習 Lambda Calculus 的那些概念。

於是 Structure and Interpretation of Computer Programs 就有了 JavaScript 版本,讓我可以避開 LISP 卻又能學習 Lambda Calculus 了。

Clone this wiki locally