之前有發(fā)布一篇文章《用Ruby簡(jiǎn)單模擬Lambda演算》討論了如何用Ruby的Lambda來(lái)表達(dá)0， 1焙糟， 2這些整數(shù)口渔。專業(yè)上稱他們?yōu)?strong>邱奇數(shù)，順手貼一段Wiki穿撮。
邱奇編碼是把數(shù)據(jù)和運(yùn)算符嵌入到Lambda演算內(nèi)的一種方式缺脉，最常見的形式是邱奇數(shù)，它是使用Lambda符號(hào)的自然數(shù)的表示法混巧。這種方法得名于阿隆佐·邱奇枪向，他首先以這種方法把數(shù)據(jù)編碼到Lambda演算中勤揩。
但如果要構(gòu)建一個(gè)程序咧党，僅僅有這些基本的數(shù)據(jù)類型是不夠的。很多時(shí)候我們會(huì)想對(duì)我們生成的這些數(shù)字做些猥瑣的操作陨亡。比如我們常用的加法傍衡，減法，乘法负蠕，以及階乘等等蛙埂。下面我們就來(lái)實(shí)現(xiàn)這些操作。
0. 熱身
古人云：“溫故而知新遮糖，可以為師矣”绣的。那么開始實(shí)現(xiàn)基本數(shù)值運(yùn)算之前我們先來(lái)溫習(xí)一下之前的知識(shí)，順手實(shí)現(xiàn)幾個(gè)邱奇數(shù)
ZERO = -> p { -> x { x } }
ONE = -> p { -> x { p[x] } }
然后寫一個(gè)函數(shù)把對(duì)應(yīng)的邱奇數(shù)以我們熟悉的方式展示出來(lái)
def to_integer(n)
n[-> x {x + 1}][0]
end
>> to_integer(ONE)
=> 1
>> to_integer(ZERO)
=> 0
更多的邱奇數(shù)
TWO = -> p { -> x { p[p[x]] } }
THREE = -> p { -> x { p[p[p[x]]] } }
FOUR = -> p { -> x { p[p[p[p[x]]]] } }
# ....
只要反復(fù)調(diào)用p我們便能夠構(gòu)建更大的邱奇數(shù)欲账，那么我們是否能夠創(chuàng)建一個(gè)函數(shù)來(lái)完成這個(gè)反復(fù)調(diào)用p的過(guò)程呢屡江？我期待的函數(shù)是這樣工作的
F(ONE) => TWO
F(TWO) => THREE
F(THREE) => FOUR
似乎有點(diǎn)意思，那這里我姑且命名這個(gè)函數(shù)為SUCC赛不。
SUCC = -> n {
-> p {
-> x {
p[n[p][x]]
}
}
}
講解: 簡(jiǎn)單地可以把這個(gè)函數(shù)拆開來(lái)看惩嘉，我們?cè)?code>x的基礎(chǔ)上調(diào)用
n次p就會(huì)得到我們期待的數(shù)字n。當(dāng)我們?cè)诘玫浇Y(jié)果的基礎(chǔ)上再執(zhí)行一次p的時(shí)候就會(huì)得到n + 1了踢故。
>> to_integer(SUCC[ZERO])
=> 1
>> to_integer(SUCC[ONE])
=> 2
OK文黎，結(jié)果正是我們所期待的惹苗。 但好像熱身熱過(guò)頭了，那我們馬上開始用Lambda實(shí)現(xiàn)基本數(shù)值運(yùn)算耸峭。
1. 加法
熱身里面好像隱藏了一些東西桩蓉，我們平時(shí)所定義的一個(gè)數(shù)字，其本質(zhì)就是在0的基礎(chǔ)上執(zhí)行 加一操作得到的劳闹，我們想要什么數(shù)字就執(zhí)行多少次加一操作触机，而這個(gè)時(shí)候我們的起始值是0。那么如果起始值不是0呢玷或？那會(huì)發(fā)生什么事情?
這不就是加法的本質(zhì)嗎儡首？我們把兩個(gè)數(shù)m，n相加偏友， 其實(shí)就相當(dāng)于在m的基礎(chǔ)上做了n次加一操作罷了蔬胯。只是這個(gè)過(guò)程太平常了，平常到我們幾乎意識(shí)不到它的存在位他。
那現(xiàn)在就要把代碼寫下來(lái)了氛濒， 可以復(fù)用我們熱身的時(shí)候定義的SUCC函數(shù)，寫下如下代碼
ADD = -> n {
-> m {
n[SUCC][m]
}
}
講解: 我們用到了我們已經(jīng)實(shí)現(xiàn)的
SUCC函數(shù)鹅髓，從字面上來(lái)理解就是我們從基礎(chǔ)數(shù)m開始舞竿，不斷遞增自身，當(dāng)遞增n次的時(shí)候我們就能夠得到n + m的結(jié)果了窿冯。如果拆開來(lái)看會(huì)更加明顯骗奖，我們當(dāng)n為THREE，m為TWO的時(shí)候醒串，代入函數(shù)执桌，便可得到這樣一個(gè)表達(dá)式SUCC[SUCC[SUCC[TWO]]]，其實(shí)就是把TWO遞增3次芜赌，最后會(huì)得到FIVE仰挣。
驗(yàn)證一下結(jié)果是否正確
>> to_integer(ADD[FOUR][FIVE])
9
>> to_integer(ADD[FIVE][ONE])
6
結(jié)果還是另人滿意的。
2. 乘法
實(shí)現(xiàn)了加法之后缠沈，似乎乘法已經(jīng)離我們不遠(yuǎn)了膘壶。我們回想一下最初學(xué)習(xí)乘法的時(shí)候，小學(xué)老師肯定不是一上來(lái)就講乘法的洲愤。一般他們都會(huì)列出這樣一條式子m + m + m + m + .....颓芭，就是一個(gè)數(shù)m加上自身n次，這就是乘法的本質(zhì)了禽篱。然后他們會(huì)把這個(gè)式子表示成m x n畜伐。那既然我們已經(jīng)實(shí)現(xiàn)了加法了，是否可以利用我們已經(jīng)實(shí)現(xiàn)的ADD函數(shù)來(lái)實(shí)現(xiàn)乘法呢?
按照乘法的原理來(lái)實(shí)現(xiàn)MULTI函數(shù)
MULTI = -> n {
-> m {
n[ADD[m]][ZERO]
}
}
講解: 從字面上來(lái)理解就是我們要從基礎(chǔ)數(shù)
ZERO開始躺率，累加m這個(gè)數(shù)n次玛界。拆開來(lái)看會(huì)更加直觀万矾，我們假設(shè)m為TWO，n為THREE的時(shí)候慎框，會(huì)轉(zhuǎn)化為ADD[TWO][ADD[TWO][ADD[TWO][ZERO]]]良狈。
檢驗(yàn)一下結(jié)果
>> p to_integer(MULTI[FOUR][FIVE])
20
>> p to_integer(MULTI[ONE][FIVE])
5
3. 減法
加法和乘法似乎都不會(huì)很難，但是減法就有點(diǎn)麻煩了笨枯。我們前面都感受到加法的本質(zhì)就是一個(gè)不斷重復(fù)調(diào)用指定函數(shù)的過(guò)程薪丁。但減法應(yīng)該是一個(gè)同他相反的過(guò)程，這該怎么做跋诰严嗜？調(diào)用方法我們還知道該怎么調(diào)，但是我們沒有辦法把已經(jīng)調(diào)用了的方法回退洲敢，讓它返回前一次調(diào)用的結(jié)果漫玄。因此，這個(gè)作者才會(huì)說(shuō)Lambda Calculus: Subtraction is hard压彭。咋整睦优？下面先介紹一下我們需要用到的輔助函數(shù)。
1) 有序?qū)?/h3>
Wiki上面對(duì)有序?qū)?/a>的解釋
在數(shù)學(xué)中壮不，有序?qū)?/strong>是兩個(gè)對(duì)象的搜集汗盘，使得可以區(qū)分出其中一個(gè)是“第一個(gè)元素”而另一個(gè)是“第二個(gè)元素”（第一個(gè)元素和第二個(gè)元素也叫做左投影和右投影）。帶有第一個(gè)元素a和第二個(gè)元素b的有序?qū)νǔ憺?a, b)询一。
我們嘗試用Lambda表達(dá)式來(lái)實(shí)現(xiàn)這個(gè)有序?qū)?/p>
PAIR = -> first {
-> second {
-> p {
p[first][second]
}
}
}
LEFT -> first {
-> second {
first
}
}
RIGHT -> first {
-> second {
second
}
}
我們定制了一個(gè)PAIR隐孽，它接受3個(gè)參數(shù)，分別是兩個(gè)邱奇數(shù)以及一個(gè)訪問(wèn)函數(shù)家凯，訪問(wèn)函數(shù)就是我們的LEFT, RIGHT分別用來(lái)提取PAIR中的兩個(gè)邱奇數(shù)缓醋。驗(yàn)證一下這個(gè)PAIR是否能夠像我期望那樣去運(yùn)行?
>> p to_integer(PAIR[TWO][FIVE][LEFT])
2
>> p to_integer(PAIR[TWO][FIVE][RIGHT])
5
工作正常。接下來(lái)我們看看滑動(dòng)窗口绊诲。
2) 滑動(dòng)窗口
計(jì)算機(jī)網(wǎng)絡(luò)里面有過(guò)這樣一個(gè)概念。形式上理解就是
[ 1 2 ] 3 4 5 6
1 [ 2 3 ] 4 5 6
1 2 [ 3 4 ] 5 6
1 2 3 [ 4 5 ] 6
1 2 3 4 [ 5 6 ]
這能看出什么褪贵？在中括號(hào)括起來(lái)的地方不就是我們有序?qū)岬嘀可厦孢@個(gè)滑動(dòng)窗口，其實(shí)我們可以用有序?qū)?lái)模擬脆丁。當(dāng)初始值設(shè)置為(0, 0)的時(shí)候滑動(dòng)3次就會(huì)有如下效果
[0, 0]
[0, 1]
[1, 2]
[2, 3]
有點(diǎn)像是我們之前定義的SUCC方法世舰，只是我們那時(shí)候只操作一個(gè)邱奇數(shù)，返回一個(gè)邱奇數(shù)槽卫。而在這里我們是傳入一個(gè)PAIR, 然后返回這個(gè)PAIR向右滑動(dòng)的結(jié)果跟压。
那我們嘗試編寫這個(gè)函數(shù)
SLIDE = -> p {
PAIR[p[RIGHT]][SUCC[p[RIGHT]]]
}
講解: 該函數(shù)接受一個(gè)
PAIR作為參數(shù)，然后創(chuàng)建一個(gè)新的PAIR歼培，以原來(lái)PAIR的右邊的元素作為新PAIR的左邊的元素震蒋。而新PAIR右邊的元素用的是原來(lái)PAIR右邊元素遞增之后的值茸塞。
在驗(yàn)證這個(gè)方法正確性之前我還需要實(shí)現(xiàn)to_pair這個(gè)方法，用來(lái)方便我們對(duì)PAIR內(nèi)容的檢查
def to_pair(pair)
"(#{to_integer(pair[LEFT])}, #{to_integer(pair[RIGHT])})"
end
>> puts to_pair(PAIR[ONE][TWO])
(1, 2)
>> puts to_pair(SLIDE[PAIR[ONE][TWO]])
(2, 3)
>> puts to_pair(SLIDE[SLIDE[PAIR[ONE][TWO]]])
(3, 4)
哈哈查剖，SLIDE的行為已經(jīng)跟我們的預(yù)期一樣了钾虐。
3) 實(shí)現(xiàn)減法
說(shuō)了一大堆，并且實(shí)現(xiàn)了PAIR, SLIDE笋庄。但是我們還是沒有解決問(wèn)題效扫。我們通過(guò)PAIR以及SLIDE的配合可以獲取到當(dāng)前的邱奇數(shù)還有它的前驅(qū)邱奇數(shù)。那么接下來(lái)怎么搞直砂？我們換個(gè)角度想想這個(gè)問(wèn)題菌仁，我們現(xiàn)在已經(jīng)能夠構(gòu)造一個(gè)PAIR以及SLIDE了，那么我們是否可以實(shí)現(xiàn)一個(gè)函數(shù)静暂，讓它能夠直接返回我們傳入某個(gè)邱奇數(shù) 的前一個(gè)邱奇數(shù)掘托？如果我們能夠?qū)崿F(xiàn)這樣一個(gè)函數(shù)PRED，那么當(dāng)我對(duì)一個(gè)數(shù)m重復(fù)調(diào)用PRED這個(gè)函數(shù)n次的時(shí)候籍嘹，不就可以獲取到m - n的值了嗎闪盔？（當(dāng)然我們的前提是 m >= n畢竟我們現(xiàn)在還沒有考慮到負(fù)數(shù)）
有了前面的基礎(chǔ)PRED方法似乎比較好實(shí)現(xiàn)
PRED = -> n {
n[SLIDE][PAIR[ZERO][ZERO]][LEFT]
}
講解: 當(dāng)我們傳入的邱奇數(shù)為
n的時(shí)候，我們對(duì)最基本的有序?qū)?code>(0, 0)向右滑動(dòng)n次辱士，然后就能得到新的有序?qū)?code>(n - 1, n)泪掀，我們?nèi)∮行驅(qū)ψ筮呑鳛榻Y(jié)果就能夠得到n-1
檢驗(yàn)一下PRED的執(zhí)行情況
>> p to_integer(PRED[FOUR])
3
>> p to_integer(PRED[TWO])
1
>> p to_integer(PRED[ONE])
0
Cool，已經(jīng)可以獲取到指定邱奇數(shù)的前一個(gè)邱奇數(shù)了颂碘。接下來(lái)干嘛呢异赫？好像減法的實(shí)現(xiàn)已經(jīng)呼之欲出了。其實(shí)我們實(shí)現(xiàn)的PRED就是一個(gè)減一操作头岔，如果我們想要得到m - n的結(jié)果塔拳，那么只需要對(duì)m執(zhí)行減一操作n次即可達(dá)到目的。
SUBT = -> m {
-> n {
n[PRED][m]
}
}
檢驗(yàn)結(jié)果
>> p to_integer(SUBT[FIVE][ONE])
4
>> p to_integer(SUBT[FIVE][TWO])
3
>> p to_integer(SUBT[THREE][TWO]
1
我去峡竣，總算大功告成靠抑。相比起加法還有乘法，要用Lambda來(lái)實(shí)現(xiàn)減法居然要耗費(fèi)這么多力氣适掰。最后簡(jiǎn)單總結(jié)一下減法的思路: 首先我們需要設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)PAIR用來(lái)存儲(chǔ)兩個(gè)邱奇數(shù)颂碧。然后我們實(shí)現(xiàn)一個(gè)SLIDE讓我們可以從一個(gè)基本的邱奇數(shù)有序?qū)?/strong>PAIR[ZERO][ZERO]開始滑動(dòng)，當(dāng)我們滑動(dòng)n次的時(shí)候就會(huì)得到n的邱奇數(shù)以及n-1的邱奇數(shù)类浪。利用這兩個(gè)函數(shù)我們可以實(shí)現(xiàn)一個(gè)PRED函數(shù)载城，通過(guò)這個(gè)函數(shù)我們可以直接獲取到我們作為參數(shù)的邱奇數(shù)的前一個(gè)邱奇數(shù) - 1。最后我們只需要對(duì)一個(gè)數(shù)m反復(fù)調(diào)用PRED函數(shù)n次就能夠得到我們期望的m - n费就。把這個(gè)過(guò)程封裝一下之后就能夠得到我們期望減法SUBT函數(shù)了诉瓦。
4. 階乘
最后我們討論一下階乘，其實(shí)搞懂了前面這些之后，階乘實(shí)現(xiàn)起來(lái)就非常簡(jiǎn)單了睬澡。我們知道乘法m x n就是m從0開始累加n次m固额。那么階乘呢？m ^ n其實(shí)就是從1開始連續(xù)乘n次m猴贰。原理知道了对雪，代碼其實(shí)也就很好寫了。
POWER = -> m {
-> n {
n[MULTI[m]][ONE]
}
}
最后檢驗(yàn)運(yùn)算結(jié)果
>> p to_integer(POWER[FIVE][FIVE])
3125
>> p to_integer(POWER[FOUR][FOUR])
256
>> p to_integer(POWER[FOUR][ONE])
4
5. 尾聲
用《我編程米绕，我快樂(lè)》里面的一則建議來(lái)說(shuō)就是：“如果你想學(xué)懂某一種技術(shù)瑟捣，就把它教給別人吧≌じ桑”相關(guān)的代碼片段已經(jīng)貼到了gist迈套。
不好意思，又一口氣啰嗦了一大堆碱鳞，分別講了加法桑李，減法，乘法窿给， 階乘這些運(yùn)算的Lambda實(shí)現(xiàn)方式贵白。如果你覺得作者表達(dá)得不夠清晰的話，還可以參考一下這些文章崩泡。
Introduction to Lambda Calculus: 簡(jiǎn)單地講解了Lambda實(shí)現(xiàn)基本數(shù)值運(yùn)算的基礎(chǔ)知識(shí)禁荒。
Lambda Calculus: Subtraction is hard： 詳細(xì)講解了如何用Lambda演算來(lái)實(shí)現(xiàn)減法。
Lambda 演算Wiki：簡(jiǎn)單講解Lambda演算的一些基礎(chǔ)知識(shí)角撞。
私人推薦書籍
《我編程呛伴，我快樂(lè)》：一本關(guān)于編程還有就業(yè)的好書，正在讀第二遍感覺很值得一讀谒所。
