Functional Programming 說的就是 Lambda Calculus 嗎？

01-14

看起來lambda calculus基本已經包含了functional programming的特點：也就是把function 當作first class citizen。然後用作一系列的操作。

不是。純lambda calculus里你要用Church Encoding來把整數、布爾運算表示成lambda表達式，反直覺而且低效率。

最起碼，拿來做真實的函數式語言模型的話，你需要拓展純lambda calculus，添加內建的值和操作符，這個模型叫ISWIM，是動態類型的，去掉賦值之後的「純」Scheme就是這個樣子。

然後繼續拓展就是加類型系統了。

推薦題主看看SPJ的The Implementation of Functional Languages，看看函數式語言的各種複雜特性如何通過一層一層的desugaring最後規約到（稍加拓展的）lambda calculus。

建議看David Turner在TFP12上的文章https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf

，嫌長也有slide http://www-fp.cs.st-andrews.ac.uk/tifp/TFP2012/TFP_2012/Turner.pdf

從Lambda Calculus到：

Lambda Calculus (Church 1930s)

LISP (McCarthy 1960)

Algol 60 (Naur et al. 1963)

ISWIM (Peter Landin 1965)

PAL (Evans 1968)

SASL (1973–83)

FP（J.Backus 1978)

Edinburgh系列 (1969–80) — NPL, early ML, HOPE

Miranda (D.Turner 1986)

Haskell (1992 . . . )

...

不是。

我大概可以理解題主所要表達的意思，函數式語言的計算模型的確是建立在lambda calculus之上的。但是lambda calculus也僅僅是一個語圖靈模型等價的計算模型而已。

誠然，你可以用lambda calculus的var abs app 三個元素就可以輕易的表達出與其他語言等價的運算。但是對程序語言而言，我們關心的不僅僅是表達出我們想要的計算，更重要的是這個語言是如何去表達的。

所以光有lambda calculus是不夠的，我們不可能在編寫代碼的時候，手寫f.x.x 去表示0，這對程序員來說就像是手寫機器碼一樣的噩夢，所以我們至少要在其中拓展自然數和字元串這樣內建的數值，並且定義內建的操作符。

這樣就足夠了嗎？當然遠遠不夠，有了這些內建的值和操作，對於1 + "ab"這樣的運算，在沒有預先定義的情況下，我們無法給出答案，所以我們還得建立一個類型系統。

等等等等。