今天是虐狗節(jié)，其實(shí)我總是期待著哪天我可以不需要再當(dāng)賓語(yǔ)了誉己，我也可以充當(dāng)一下主語(yǔ)去虐虐別人巨双，不過(guò)世事往往讓人揪心啊霉祸。既然無(wú)法改變，那就讓我們好好享受一下這個(gè)節(jié)日吧慢宗！最起碼在自己的文章敏晤，以及自己寫的代碼里面我還是可以充當(dāng)一下主語(yǔ)的。
最近看一本叫做《計(jì)算的本質(zhì)》的書痹雅，這本書主要說(shuō)了一些底層計(jì)算方面的知識(shí)》銎剑可以說(shuō)它刷新了我的三觀蔬蕊，而當(dāng)今天看到可以使用Y組合子來(lái)實(shí)現(xiàn)遞歸的時(shí)候我的世界觀基本崩塌了岸夯。故借著七夕來(lái)寫一篇文章總結(jié)一些關(guān)于計(jì)算的一些基本認(rèn)識(shí)猜扮。以便后續(xù)可以更好地學(xué)習(xí)。也借著Ruby的語(yǔ)法來(lái)闡述一下關(guān)于Lambda的一些故事齿桃。
0. 題外話
為了慶祝一下這個(gè)節(jié)日短纵，我提前關(guān)掉了LOL香到，打開了Emacs报破，敲下如下代碼(這里順便推廣一下Ruby的單件方法)
subject = "情侶"
object = "狗"
def subject.do_something(who)
"#{self} 虐 #{who}"
end
if __FILE__ == $0
p subject.do_something(object)
p object.do_something(subject)
end
上面代碼的運(yùn)行結(jié)果是
"情侶 虐 狗"
dog.rb:11:in `<main>': undefined method `do_something' for "狗":String (NoMethodError)
很明顯泛烙，情侶可以“虐”狗但狗不能“虐”情侶蔽氨。因此第二句執(zhí)行語(yǔ)句會(huì)報(bào)錯(cuò)帆疟。以上也是Ruby優(yōu)雅的地方踪宠，我可以直接在指定實(shí)例上定義方法柳琢，而不影響其他其他的同類的實(shí)例(以上實(shí)例都是字符串)柬脸。
1. 函數(shù)的一些基本認(rèn)識(shí)
“題外話”有個(gè)卵子用倒堕？額垦巴， 說(shuō)沒(méi)用骤宣，它還是有一點(diǎn)作用的序愚。我們今天的主題是用Ruby來(lái)模擬Lambda演算爸吮。Lambda演算在Wiki上面的解釋是這樣的
Lambda演算可以被稱為最小的通用程序設(shè)計(jì)語(yǔ)言。它包括一條變換規(guī)則（變量替換）和一條函數(shù)定義方式，Lambda演算之通用在于埂软，任何一個(gè)可計(jì)算函數(shù)都能用這種形式來(lái)表達(dá)和求值勘畔。
平時(shí)我們使用命令式的編程語(yǔ)言會(huì)更傾向于關(guān)注字符串丽惶， 數(shù)字钾唬，布爾 這些可以充當(dāng)主語(yǔ)或者賓語(yǔ)的類型侠驯。而我們平時(shí)跟他們打交道更多會(huì)以變量的形式吟策，就如同“題外話”中的"狗"和"情侶"檩坚。但這篇文章的重點(diǎn)放在"虐"這個(gè)詞上匾委，也就是我們常稱的謂語(yǔ)赂乐。在計(jì)算機(jī)里面我們通常稱他做方法 或者 函數(shù)沪猴。
既然Wiki上也說(shuō)了Lambda是最小的通用程序設(shè)計(jì)語(yǔ)言运嗜，那我們有沒(méi)有可能用Lambda來(lái)模擬出數(shù)字担租， 字符串奋救， 布爾等等的這些常用的數(shù)據(jù)類型呢尝艘？這就是接下來(lái)要講的東西背亥。
1) Ruby中的函數(shù)
在Ruby中狡汉，函數(shù)其實(shí)可以算是一等公民盾戴，只是它的鋒芒往往被Ruby強(qiáng)大的面向?qū)ο筇卣鹘o掩蓋掉了（它使得我們更多地關(guān)注類還有模塊）橄仆。Ruby里面有個(gè)十分簡(jiǎn)單的創(chuàng)建函數(shù)的方式
[1] pry(main)> -> x { x + 2 }
=> #<Proc:0x007fc171dc6010@(pry):1 (lambda)>
它返回了一個(gè)Proc對(duì)象沿癞。其實(shí)這個(gè)對(duì)象，就類似于我們平時(shí)操作的函數(shù)對(duì)象具温。但是這里我們并沒(méi)有給函數(shù)賦予名字铣猩，可以理解為它是一個(gè)匿名函數(shù)天吓。那么這種函數(shù)如何調(diào)用呢龄寞？有一種很語(yǔ)義化的調(diào)用方式物邑，我們甚至不需要用變量來(lái)接受這個(gè)函數(shù)就可以調(diào)用它色解。
[2] pry(main)> -> x { x + 2 }.call(1000)
=> 1002
[3] pry(main)> -> x { x + 2 }.call(1000, 100000)
ArgumentError: wrong number of arguments (given 2, expected 1)
from (pry):3:in `block in __pry__'
Ruby還提供了參數(shù)檢測(cè)，如果傳入的參數(shù)與定義該函數(shù)的時(shí)候不匹配的話，則會(huì)拋出ArgumentError異常朴读。此外噪伊，Ruby還提供了一種語(yǔ)法糖鉴吹，我們可以用Proc#[]包裹參數(shù)來(lái)調(diào)用Proc實(shí)例夺荒。
使用方式如下:
[4] pry(main)> ADD_THREE = -> x { x + 3 }
=> #<Proc:0x007fd8341ffc48@(pry):4 (lambda)>
[5] pry(main)> ADD_THREE[1000]
=> 1003
2) 柯里化
Wiki 上的解釋如下
在計(jì)算機(jī)科學(xué)中，柯里化（英語(yǔ)：Currying），又譯為卡瑞化或加里化，是把接受多個(gè)參數(shù)的函數(shù)變換成接受一個(gè)單一參數(shù)（最初函數(shù)的第一個(gè)參數(shù)）的函數(shù)榄笙，并且返回接受余下的參數(shù)而且返回結(jié)果的新函數(shù)的技術(shù)杆逗。
既然上面已經(jīng)講了Ruby創(chuàng)建匿名函數(shù)的基本方式罪郊，那下面來(lái)看看如何用Ruby來(lái)模擬一個(gè)柯里化的過(guò)程靶累， 假設(shè)我有一個(gè)函數(shù)接收三個(gè)參數(shù)， 我定義如下
[10] pry(main)> ADD_THREE_NUMBER = -> (x, y, z) { x + y + z}
=> #<Proc:0x007fd834aa4150@(pry):10 (lambda)>
[11] pry(main)> ADD_THREE_NUMBER.call(1,2,3)
=> 6
PS: 定義函數(shù)時(shí)參數(shù)用括號(hào)包裹是為了提高識(shí)別度，其實(shí)括號(hào)可加可不加勃教，定義函數(shù)也可以寫成
-> x, y, z { x + y + z }
上述函數(shù)如何柯里化汞贸？按照柯里化的定義删铃，我們可以把多參數(shù)的函數(shù)寫成嵌套返回多個(gè)單一參數(shù)函數(shù)的形式顷蟆，為了方便閱讀我把代碼寫在Ruby腳本文件里面
# currying.rb
ADD_THREE_NUMBER_NEW = -> (a) {
-> (b) {
-> (c) {
a + b + c
}
}
}
if __FILE__ == $0
p ADD_THREE_NUMBER_NEW.call(1).call(2).call(3)
end
運(yùn)行結(jié)果
6
其實(shí)這個(gè)函數(shù)每次調(diào)用都返回了一個(gè)只帶一個(gè)參數(shù)的函數(shù)，而且返回的函數(shù)會(huì)保存著調(diào)用當(dāng)前函數(shù)時(shí)傳入的參數(shù)逐纬，就是我們通常講的閉包削樊。直到最后一個(gè)函數(shù)被調(diào)用并返回的時(shí)候，才會(huì)真正得到期望的計(jì)算結(jié)果甸箱。
當(dāng)然我們可以更簡(jiǎn)單的用Proc#[]來(lái)調(diào)用(在文章的后半部分我會(huì)統(tǒng)一用這種方式迅脐，比較節(jié)省代碼)
[1] pry(main)> require('./currying')
=> true
[2] pry(main)> ADD_THREE_NUMBER_NEW[1][2][3]
=> 6
2. 模擬Lambda演算
Lambda既然是最小的通用編程語(yǔ)言谴蔑，那么我們現(xiàn)在嘗試一下用Ruby的Proc這個(gè)現(xiàn)成的Lambda來(lái)演算一些東西。難的東西我自己都還接受不了窃躲，這里只能先來(lái)模擬一些最為簡(jiǎn)單的東西了钦睡。
1) 數(shù)字
首先嘗試模擬一下數(shù)字。《計(jì)算的本質(zhì)》一書中提供了一個(gè)比較直觀的段子撩嚼，以下是我概括的大意
我們?nèi)绻麤](méi)辦法直接使用數(shù)字逻族，而只能使用謂語(yǔ)(動(dòng)作)，那么我們只能重復(fù)數(shù)這個(gè)動(dòng)作來(lái)描述數(shù)字這個(gè)特征搏嗡，而數(shù)這個(gè)動(dòng)作其實(shí)就是我們需要寫的Lambda表達(dá)式
直觀點(diǎn)講當(dāng)我們要表示0的時(shí)候就數(shù)0次，調(diào)用方法0次悍赢，表示1的時(shí)候就調(diào)用方法一次。
那我們簡(jiǎn)單地表示0~2就可以是
ZERO = -> (p) { -> (x) { x } }
ONE = -> (p) { -> (x) { p[x] } }
TWO = -> (p) { -> (x) { p[p[x]] } }
這樣或許看起來(lái)有點(diǎn)迷糊甩栈，其實(shí)他們都用Lambda演算出來(lái)的殴蹄，他們都接受一個(gè)函數(shù)p(數(shù)數(shù)這個(gè)動(dòng)作)以及一個(gè)基礎(chǔ)值x作為參數(shù)橘茉，如果是ZERO就直接返回基礎(chǔ)值x髓介， 如果是ONE就以x這個(gè)基礎(chǔ)值作為參數(shù)調(diào)用函數(shù)p表示數(shù)了一次一膨。
這里我們并沒(méi)有辦法很好的表示這個(gè)基礎(chǔ)值x，為了直觀巷蚪，我需要借用一下Ruby內(nèi)置的數(shù)字0 作為一個(gè)基礎(chǔ)值淌喻，并且要另外定義數(shù)數(shù)這個(gè)動(dòng)作烁落。
CALCULATE = -> (n) { n + 1 }
其實(shí)數(shù)數(shù)的動(dòng)作就是在原來(lái)的基礎(chǔ)值上加1，最后我統(tǒng)一寫腳本
# coding: utf-8
# number.rb
ZERO = -> (p) { -> (x) { x } }
ONE = -> (p) { -> (x) { p[x] } }
TWO = -> (p) { -> (x) { p[p[x]] } }
def to_integer(proc)
calculate = -> (n) { n + 1 }
# 其中0是基礎(chǔ)值
proc[calculate][0]
end
在解析環(huán)境里面引入腳本并執(zhí)行一些相關(guān)的語(yǔ)句童本，就能得到我們想要的結(jié)果了
[1] pry(main)> require('./number')
=> true
[2] pry(main)> to_integer(ZERO)
=> 0
[3] pry(main)> to_integer(ONE)
=> 1
[4] pry(main)> to_integer(TWO)
=> 2
雖然對(duì)于已經(jīng)含有內(nèi)置數(shù)字類型的Ruby來(lái)說(shuō)這種模擬完全沒(méi)有任何實(shí)用價(jià)值携添，不過(guò)對(duì)于了解Lambda演算這可以是一個(gè)不錯(cuò)的開始锥腻。
2) 布爾型
說(shuō)完數(shù)字匹摇，再來(lái)簡(jiǎn)單說(shuō)一下布爾類型吧，他們也算是比較基礎(chǔ)的數(shù)據(jù)類型了冰悠。而且布爾型模擬起來(lái)還更簡(jiǎn)單些。畢竟布爾型休溶，不是true就是false孽尽。我們可以分別寫兩個(gè)都接受兩個(gè)參數(shù)的函數(shù)速勇，一個(gè)代表true一個(gè)代表false呕乎。true函數(shù)就返回其中的第一個(gè)參數(shù)褐耳，false函數(shù)直接返回第二個(gè)參數(shù)嗤军。
TRUE = -> (x) { -> (y) { x }}
FALSE = -> (x) { -> (y) { y }}
我們?cè)賹懸粋€(gè)解析腳本，作為驗(yàn)證哲嘲。我記得在C這種沒(méi)有布爾類型的語(yǔ)言中我們是用0代表false 用大于1代表true霍弹。這里我就簡(jiǎn)單用0和1作為基礎(chǔ)值來(lái)驗(yàn)證我們的Lambda演算是否正確
# boolean.rb
TRUE = -> (x) { -> (y) { x }}
FALSE = -> (x) { -> (y) { y }}
def to_boolean(proc)
proc[1][0]
end
引入運(yùn)行腳本試試
[1] pry(main)> require('./boolean')
/Users/lan/Personal/Ruby/boolean.rb:1: warning: already initialized constant TRUE
/Users/lan/Personal/Ruby/boolean.rb:2: warning: already initialized constant FALSE
=> true
[2] pry(main)> to_boolean(FALSE)
=> 0
[3] pry(main)> to_boolean(TRUE)
=> 1
跟預(yù)期的一樣炼吴，我們的模擬是正確的涮瞻，FALSE函數(shù)最后被解析成0， 而TRUE函數(shù)最后被解析成1。
以上的警告是重復(fù)定義常量所致，這里可以暫時(shí)忽略。
3) 簡(jiǎn)單判斷一個(gè)數(shù)是否為0
最后我們?cè)僮鰝€(gè)簡(jiǎn)單的模擬，用到我們前面模擬的數(shù)字以及布爾兩種類型來(lái)定義一個(gè)方法铝噩，判斷傳入的參數(shù)是否為0(是否我們定義的ZERO), 并返回一個(gè)布爾類型(TRUE或者FALSE)的模擬結(jié)果谋右。算法很簡(jiǎn)單
def zero?(n)
if n == 0
true
else
false
end
end
那如何用Lambda表示？我們前面都講過(guò)了，ZERO這個(gè)函數(shù)會(huì)接收兩個(gè)參數(shù): 第一個(gè)參數(shù)是函數(shù)债朵，第二個(gè)為基礎(chǔ)值藏杖，如果傳入的是ZERO函數(shù)的話，我們調(diào)用ZERO的時(shí)候同廉，不管傳入第一個(gè)參數(shù)是什么隅津，調(diào)用結(jié)果都會(huì)直接返回第二個(gè)參數(shù)(也就是基礎(chǔ)值)棺克。
那我們回過(guò)頭來(lái)想如果把TRUE作為它第二個(gè)參數(shù)搀缠，把一個(gè)返回FALSE的函數(shù)作為第一個(gè)參數(shù)瑰步，那當(dāng)我們新函數(shù)接收的是ZERO函數(shù)并且調(diào)用它的時(shí)候不就會(huì)直接返回TRUE了嗎？而其他的方法靴拱，如ONE, TWO就會(huì)執(zhí)行-> (x) { FALSE }這個(gè)過(guò)程他托。
可以把代碼寫成
require "./number"
require "./boolean"
IS_ZERO = -> (proc) {
proc[-> (x) {FALSE}][TRUE]
}
if __FILE__ == $0
p to_boolean(IS_ZERO[ZERO])
p to_boolean(IS_ZERO[ONE])
p to_boolean(IS_ZERO[TWO])
end
運(yùn)行結(jié)果是
1
0
0
只有第一個(gè)ZERO是我們期望的值郎楼，最后返回了1(就是true)膘融。其他的都不是我們需要的代表數(shù)值0的Lambda表達(dá)式臼疫。
3. 尾聲
這篇文章有點(diǎn)長(zhǎng)湾盗，主要介紹了Ruby里面的Proc類，以及對(duì)函數(shù)柯里化和Lambda表達(dá)式做了最基本的講解败富。最后舉了一些例子，用Lambda表達(dá)式來(lái)模擬數(shù)字和布爾類型嘁捷，另外使用我們模擬出來(lái)的類型作為基礎(chǔ)來(lái)定義一個(gè)實(shí)用的方法IS_ZERO。本文沒(méi)有涉及太多高深的東西龙致，因?yàn)橛泻芏喔呱畹臇|西我還吸收不了，當(dāng)吸收了之后會(huì)繼續(xù)發(fā)文講述湖笨。很感謝您的閱讀。
祝大家七夕節(jié)快樂(lè)
