最近玩游戲 《Functional》，發(fā)現(xiàn)完全使用 lambda 做各種抽象還蠻有趣的，這里做一些關(guān)于實(shí)踐 lambda 的筆記，順路把 Y 組合子也給咔嚓掉——已經(jīng)很長一段時(shí)間想要去學(xué)習(xí)它但擱置了。這里使用 js 去實(shí)現(xiàn)，它使用箭頭函數(shù)時(shí)的語法已經(jīng)足夠簡潔；所有 lambda 符號都寫作λ，且所有字面量的 abstraction 都會給予括號。

回顧

這里先把 lambda 回顧一遍，在 lambda 中，存在著三種表達(dá)式——variable，abstraction，application。variable 的語法為任何小寫字母，如 x，y，abstraction 的語法如λx.x，application 的語法如A B，其中 A，B 均為表達(dá)式。

下面都是合法的 lambda：

對 lambda，我們能做的唯一一件事其實(shí)就是化簡，具體來說，是把 Application 化簡；比如對(λx.x x) y，對其進(jìn)行化簡就是把 x 替換成 y，得到它的函數(shù)體，即y y。

最后是 abstraction 和 application 的結(jié)合性問題，abstraction 是右結(jié)合的，application 是左結(jié)合的，這就是說：

從 js 的上下文來看，abstraction 就是函數(shù)定義，application 就是函數(shù)應(yīng)用，下面均以此來稱呼 abstraction 和 application。

Boolean

在一切開始之前，先預(yù)先定義一個(gè) VOID 變量用于填充，它是一個(gè) identity 函數(shù)：

布爾值是最簡單的數(shù)據(jù)結(jié)構(gòu)，它僅有兩個(gè)值 True 和 False。

使用 Lambda 時(shí)，我們可以這樣定義 Boolean：

對應(yīng)的 js 為：

這里其實(shí)我并不明確這里的 a 和 b 為何需要是函數(shù)，可能是為延遲求值，也可能是為統(tǒng)一“模式匹配”的形式（見下面的部分總結(jié)），下面有些地方使用了這個(gè)形式，有些地方也沒有。

它們的含義都很明確——TRUE 表示一個(gè)兩參數(shù)的函數(shù)，返回第一個(gè)參數(shù)，F(xiàn)ALSE 表示一個(gè)兩參數(shù)的函數(shù)，返回第二個(gè)參數(shù)。可以認(rèn)為，我們把 boolean 通過 lambda 去“編碼”了。至于為何要這樣編碼，去問丘奇吧 hh。

這樣抽象后，我們能夠?qū)崿F(xiàn) if，if 是這樣的結(jié)構(gòu)——它接受三個(gè)參數(shù)，其中第一個(gè)參數(shù)是布爾值，若其為真，返回第二個(gè)參數(shù)，否則返回第三個(gè)參數(shù)，它的實(shí)現(xiàn)是顯然的。

可以做一下演算，假設(shè) 1 和 2 是合法的 lambda 變量：

對其的使用類似這樣：

在這里，由于 javascript 的弱類型，可以注意到，IF 其實(shí)就是 identity 函數(shù)x => x——IF(TRUE)(1)(2) = TRUE(1)(2) = 1，IF(TRUE) = TRUE。

實(shí)現(xiàn) AND 和 OR 也是簡單的，它們的參數(shù)均為布爾值，返回值也為布爾值：

Cons

Cons 的實(shí)現(xiàn)如下：

Cons 的這個(gè)定義a => b => onNil => onCons => onCons (a) (b)十分有趣，我們可以給它加點(diǎn)括號來更突出這有趣之處：

可以建立這樣的心智模型，即 CONS 是這樣一個(gè)函數(shù)，它接受兩個(gè)參數(shù)，去返回一個(gè)數(shù)據(jù)結(jié)構(gòu)，而我們通過去傳遞給它一個(gè)“Matcher”（模式匹配）去獲取該數(shù)據(jù)結(jié)構(gòu)中的值。同時(shí)也可以注意到，NIL 的結(jié)構(gòu)和調(diào)用 CONS 返回的數(shù)據(jù)結(jié)構(gòu)是一致的。

然后，顯然需要實(shí)現(xiàn)一個(gè)檢查 PAIR 是否是 NIL 的函數(shù)，這個(gè)函數(shù)的實(shí)現(xiàn)同樣很 trick 但能找到模式：

為何這么實(shí)現(xiàn)？推導(dǎo)一下就行了：

這很像模式匹配——只不過我們必須通過函數(shù)參數(shù)的形式去綁定所有值就是了，比如這個(gè) IS_NIL 函數(shù)可以看成這樣（使用 Scala 的模式匹配語法）：

Maybe

照葫蘆畫瓢，我們可以嘗試去抽象 Maybe：

map 的操作如 map，flatMap，orElse 也可以定義出來：

使用類似這樣：

部分總結(jié)

在 haskell 中，Bool，Cons，Maybe，Either，Tree（二叉樹）的類型定義分別如下：

使用 lambda 對其的抽象如下：

可以發(fā)現(xiàn)，對任何 ADT，它似乎都能通過 lambda 去抽象，其中，每一個(gè)值構(gòu)造器對應(yīng)一個(gè)函數(shù)，其接受值構(gòu)造器的參數(shù)，去構(gòu)造相應(yīng)數(shù)據(jù)結(jié)構(gòu)；然后，我們傳遞給這個(gè)數(shù)據(jù)結(jié)構(gòu)一個(gè) Matcher，對其進(jìn)行“模式匹配”并獲得值。

丘奇數(shù)

通過上面的觀念，我們嘗試操作一下自然數(shù)，皮亞諾自然數(shù)的 Haskell 定義是這樣的：

定義相應(yīng) lambda，并去推演 ONE，TWO，THREE……

但這樣的自然數(shù)定義實(shí)在有點(diǎn)難以形容，這時(shí)候就來了丘奇數(shù)，它修改了 SUCC，把“Matcher”提前應(yīng)用給了它的“值”：

可以發(fā)現(xiàn)，自然數(shù)的值就是 f 應(yīng)用的次數(shù)，f 應(yīng)用 n 次，則對應(yīng)的自然數(shù)的值就是 n；其 js 表述如下：

根據(jù)丘奇數(shù)的形式，可以很容易地將丘奇數(shù)轉(zhuǎn)換為 js 的數(shù)字：

這種形式非常有趣，它像某種 reduce，其中 x 為初始值，f 為 step 函數(shù)，我們可以把 f 換成不同的函數(shù)（只要它的簽名滿足A => A），把 x 換成不同的值（即這里的類型A），比如我們可以去構(gòu)造一個(gè)同這個(gè)自然數(shù)大小相同長度的列表：

這個(gè)性質(zhì)對定義四則運(yùn)算非常重要，比如考慮加法，對任意自然數(shù) n，我們將其加 a，就是將其應(yīng)用 a 次 SUCC，形式化地來說，就是：

那么，如何在 n 上應(yīng)用 a 次 SUCC 呢？答案很明白了：

測試一下：

乘法也很簡單——自然數(shù) n 乘以自然數(shù) a，就是0 + n + n + ... + n，其中 n 的個(gè)數(shù)為 a，我們只需要讓 f 的值變?yōu)?code>λx. PLUS x n即可，一個(gè)簡單的閉包罷了：

要定義減法，我們需要先定義 PRED 即前驅(qū)，減一操作，即從λx.λf. f (f x) 到λx.λf.f x。這個(gè)操作對皮亞諾自然數(shù)來說是非常容易的，但對丘奇數(shù)（，對我）來說完全不 trival，這里參考 如何理解丘奇計(jì)數(shù)的減法？ - Thomas Lin 的回答 - 知乎。

我們可以去嘗試構(gòu)造這樣一個(gè) PAIR 的序列，其中對每一個(gè)元素，它的第一個(gè)元素是第二個(gè)元素的后繼，且對序列中后一個(gè)元素，它的第一個(gè)元素為前一個(gè)元素的第一個(gè)元素的后繼，第二個(gè)元素為前一個(gè)元素的第二個(gè)元素；定義PRED ZERO = ZERO，依此定義這個(gè)序列的起始值為(ZERO, ZERO)；

根據(jù)示意圖能發(fā)現(xiàn)，對任意自然數(shù) n，只要找到這個(gè)序列中第 n 個(gè)值，它的第二個(gè)元素就是它的前驅(qū)。

因此，能夠定義起始元素以及步進(jìn)函數(shù)：

根據(jù)上面的把自然數(shù)轉(zhuǎn)換成 js 數(shù)字，列表的操作，我們同樣可以把自然數(shù)直接轉(zhuǎn)換成這個(gè)序列中的元素，只消 x，f 的值確定即可，其中 x 為 START（類型為(Nat, Nat)），f 為 STEP（類型為(Nat, Nat) => (Nat, Nat)），因此，要獲取自然數(shù)的前驅(qū)，我們得到這樣的代碼：

老實(shí)說，它的純 lambda 形式我實(shí)在化簡不下去了，這里直接開擺，把上面的 PRED 用 js 實(shí)現(xiàn)：

有了 PRED，我們能夠定義減法了，自然數(shù) n 減去自然數(shù) a，就是 n 減去 a 次 1，即執(zhí)行 n 次 PRED

Y 組合子

這一節(jié)參考了https://stackoverflow.com/a/6713431和https://stackoverflow.com/a/6714066。

遞歸，也就是自己引用自己，比如下面的階乘函數(shù) fact，在其函數(shù)體中引用了自己：

但在 lambda 演算中我們無法這樣做，因?yàn)樵?lambda 演算中不存在所謂的“名字”，因此無法直接去編寫遞歸的函數(shù)；而通過 Y 組合子，我們便能在不引用自身的情況下編寫遞歸函數(shù)，放到 js 的語境下，就是說我們能編寫匿名的遞歸函數(shù)。

但在研究 Y 組合子之前，先來思考一下，怎樣的情況下我們能讓一個(gè)函數(shù)去不通過名字來引用自己？顯然，這時(shí)候要拿到自己只可能通過兩種方式——去捕獲上層變量，或者去從函數(shù)參數(shù)中拿；其中后者的實(shí)現(xiàn)還是比較容易想到的——調(diào)用函數(shù)的時(shí)候，把自身傳遞過去就好了！比如這里編寫一個(gè) fib 函數(shù)：

雖然乍一眼看起來有點(diǎn)作弊，但這是 lambda 可以實(shí)現(xiàn)出來的。我們考慮再來一個(gè)階乘函數(shù)：

容易注意到，這玩意調(diào)用的時(shí)候是有特定的模式的——F(F)(...args)，我們將這個(gè)模式抽象一波：

可以看到，這玩意已經(jīng)部分能滿足需求了，但蛋疼的一點(diǎn)是，在編寫該遞歸函數(shù)的時(shí)候，每次調(diào)用自己都得寫f(f)(...)，這比較麻煩，這種思考方式不可行。

現(xiàn)在回到遞歸函數(shù)，第一步，來寫一個(gè)遞歸的 fact 函數(shù)：

第二步，我們可以把這個(gè)函數(shù)變成“Supplier”，這種形式和上面的顯然是等價(jià)的，其中參數(shù)_顯然被直接扔掉了：

第三步：直到上一步，事情還是 trival 的，函數(shù)仍舊引用了自己，為了解決這個(gè)問題，再抽象一層，我們可以把函數(shù)體里的fact(_)通過參數(shù)去傳入，這要求_ = fact(_)，這里令_ = recur，得到recur = fact(recur)，將參數(shù)_替換為recur，將函數(shù)體中的fact(_)替換為fact(recur)，替換為recur，得到：

而 recur 的定義其實(shí)就是這個(gè)：recur = fact(recur)，這里引用了自己，所以必須要使用遞歸函數(shù)去定義；而且這不是 haskell，所以不能用 point-free 風(fēng)格，這里必須要知道 recur 的類型，而這是容易看出來的：number => number，下面便是結(jié)果：

好的，現(xiàn)在 fact 不是遞歸函數(shù)了，但我們又引入了一個(gè)新的遞歸函數(shù) recur（欣慰的是，所有遞歸函數(shù)最后都能抽象成無顯式遞歸的“body”和這樣一個(gè) recur 函數(shù)。

我們對 recur 采用和第一步到第二步同樣的手段，即給它包一層 Supplier：

然后，問題就在于如何處理_和recur(_)了，我實(shí)在弄不明白，把答案直接列出來：

現(xiàn)在，所有的顯式遞歸都已經(jīng)移除，把最終的代碼都列出來：

容易發(fā)現(xiàn)，這里只有 fact 是“變”量，換成其它的遞歸函數(shù)，只有 fact 會改變，因此，我們將這個(gè)模式抽象出來，就得到了 Y 組合子：

它很容易使用 lambda 去表述：

這形式比想象中簡單多了 hhh，可惜它的發(fā)現(xiàn)過程怕是值幾篇博士論文吧？

Lazy List

有了 Y 組合子，現(xiàn)在可以自由地耍花活了，該操作操作列表了，但在此之前先和皮亞諾自然數(shù)過兩招，不然列表存啥元素呢？這里首先給出皮亞諾自然數(shù)的定義，以及其到 javascript 數(shù)字類型的轉(zhuǎn)換函數(shù)：

皮亞諾自然數(shù)的加法也是簡單的——對兩個(gè)自然數(shù)a，b相加，檢查a是否是ZERO，若是，則返回b，若不是，則令a為(SUCC c)，對c，(SUCC b)相加；乘法同樣簡單，對兩個(gè)自然數(shù)a，b相乘，檢查a是否是ZERO，若是，則返回ZERO，若不是，則令a為(SUCC c)，求c，b的乘積和b的和：

這就足夠了，下面實(shí)現(xiàn)列表相關(guān)操作，這里要求列表是惰性的，即 b 為返回 CDR 的函數(shù)，下面實(shí)現(xiàn)一下 map-filter-reduce，并實(shí)現(xiàn) take 和 iterate，最終去實(shí)現(xiàn)一個(gè)自然數(shù)列表，取前 10 項(xiàng)奇數(shù)（本想取前 100 項(xiàng)，然而發(fā)現(xiàn)這爆棧了）的和；其中因?yàn)椴紶栔岛妥匀粩?shù)都未使用上面那種非嚴(yán)格求值的形式，這里定義了一個(gè)LAZY_IF來保證 if 為“短路”操作：

就這樣了，之后預(yù)備看《The Little Schemer》，多去了解一下遞歸，以及深入了解 Y 組合子。

參考資料

• https://www.zhihu.com/question/64274105

• https://zhuanlan.zhihu.com/p/298996358

• https://zhuanlan.zhihu.com/p/312895562

• https://matt.might.net/articles/js-church/

• https://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/