理解函數語言程式設計的丘奇數

最近一直在閱讀《SICP》，然後下午做其中的習題2。6，對其題意很不理解，於是搜尋了相關資料，不禁如題設所說感到如雷灌頂，特此記錄下來，以供大家閱讀和交流。

題目

請考慮，在一個可以對程式做各類操作的語言中，我們完全可以沒有數（至少是沒有整數，比如說0，1，2）的情況下，可以將 zero 和加一操作實現為：

（define zero （lambda （f） （lambda （x） x））） # 定義zero（define （add-1 n） （lambda （f） （lambda （x） （f （（n f） x））））） # 定義加一操作

上述語言是LISP，同學們不必瞭解其語法，也能大致瞭解語句的含義。下一小節中會做出具體的解釋。

這一表現形式稱為 Church 計數，也就是丘奇數，名字來源於其發明人數理學家 Church，請直接定義 one 和 two（不使用 zero 和 add-1 ）（提示：利用代換法去求值）。請給出加法過程 + 的一個直接定義（不要反覆應用 add-1 ）

丘奇數

說實話，我一直沒有看懂題目中關於 zero 和 add-1 的定義，於是我搜索了相關資料。下邊就結合資料談一下它的概念。

首先要明確的是丘奇數中的 zero，one 並不等同於數值上的 0， 1， 2。你可以理解為它是零概念的一種表現形式。換句話說，它就是零的函式式表現形式，而整數0則是零的數值表現形式。我們先來看一下丘奇數中 zero，one 和 two 的表現形式。

（define zero （lambda （f） （lambda （x） x）））（define one （lambda （f） （lambda （x） （f x））））（define two （lambda （f） （lambda （x） （f （f x）））））

我們會發現 zero，one 和 two 都是一個函式，它接收 （f） 作為引數，其返回結果是一個接收 （x） 作為引數的函式。大家可能需要注意的是，（f） 在這裡顯然也是一個函式，在 LISP 中函式是可以作為輸入引數的。然後我們會發現 zero，one 和 two 的區別好像就是 （f） 函式被使用的次數。 zero 中 （f） 沒有被使用，one 中 （f） 使用了一次，two 中 （f） 使用了兩次。丘奇數就是用這個次數來表示 0， 1， 2 的概念。

我們可以實驗一下檢驗一下

（define （inc n） （+ n 1）） ；inc是加一操作，作為zero的引數，返回一個函式，作用於數字0> （（zero inc） 0） 0 > （（zero inc） 1）1> （（one inc） 1）2> （（（add-1 one） inc） 1）3

我們定義一個過程 inc 就是數值意義上的加一，然後使用 zero， one和 add-1 發現確實如同我們所想的，zero 表示 inc 過程不會被使用，返回原數值；one 表示 inc 被使用一次，返回加一的數值。

替換法求one

我們來使用替換法透過 add-1 和 zero 來求解 one 吧，求解 two 的過程類似。

（add-1 zero） ；展開add-1定義（lambda （f） （lambda （x） （f （（zero f） x））））； 替換zero（lambda （f） （lambda （x） （f （（lambda （x） x） x））））； 簡化，因為（（lambda （x） x） x）就等於x（lambda （f） （lambda （x） （f x）））

加法定義

首先我們要明白丘奇數加法的含義，我們先記其加法為 add-church ，那麼如下程式碼所示，最後一個過程得出的值應該是多少呢？

> （（one incr） 1）2> （（two incr） 1）3> （（（add-church one two） incr） 1）？

根據猜測，應該是4吧。因為 one 表示 incr 對 1 這個數值使用一次，two 標示使用兩次，那麼將二者加起來，那麼就應該是 three 的含義啦，就是表示 incr 對 1 這個數值使用 3 次，那麼就是 4 啦。

add-church 的實現如下

（define （add-church m n） （lambda （f） （lambda （x） （（m f） （（n f） x）））））（define （add-1 n） （lambda （f） （lambda （x） （f （（n f） x））））） # 定義加一操作

如果你將其與 add-1 進行對比，你會發現 add-1 中的 f 變成了（m f） ，如果把 add-1 中的 f 記住（one f），你可能就會更加理解。

比如 （f） 為 incr 函式，（n incr） 的結果就是一個進行 n 次 incr 的函式，（incr （（n incr） x）） 就是在 （n incr） 的基礎上再進行一次 incr，所以就表示了 add-1 操作。所以（（m incr） （（n incr） x））就代表在 （n incr） 的基礎上再進行 m 次 incr，所以就是 add-church 操作。

那麼大家思考一下， add-m 應該如何表示呢？