前言
最近看一本叫做《計算的本質》的書，這本書主要說了一些底層計算方面的知識。可以說它刷新了我的三觀，而當今天看到可以使用Y組合子來實現遞歸的時候我的世界觀基本崩塌了。故借著七夕來寫一篇文章總結一些關于計算的一些基本認識。以便后續可以更好地學習。也借著Ruby的語法來闡述一下關于Lambda的一些故事。
0. 題外話
為了慶祝一下這個七夕節日，我提前關掉了LOL，打開了Emacs，敲下如下代碼(這里順便推廣一下Ruby的單件方法)
|
1
2
3
4
5
6
7
8
9
10
11
|
subject = "情侶"object = "狗"def subject.do_something(who) "#{self} 虐 #{who}"endif __FILE__ == $0 p subject.do_something(object) p object.do_something(subject)end |
上面代碼的運行結果是
|
1
2
|
"情侶 虐 狗"dog.rb:11:in `<main>': undefined method `do_something' for "狗":String (NoMethodError) |
很明顯，情侶可以“虐”狗但狗不能“虐”情侶。因此第二句執行語句會報錯。以上也是Ruby優雅的地方，我可以直接在指定實例上定義方法，而不影響其他其他的同類的實例(以上實例都是字符串)。
1. 函數的一些基本認識
“題外話”有個卵子用？額， 說沒用，它還是有一點作用的。我們今天的主題是用Ruby來模擬Lambda演算。Lambda演算在Wiki上面的解釋是這樣的
Lambda演算可以被稱為最小的通用程序設計語言。它包括一條變換規則（變量替換）和一條函數定義方式，Lambda演算之通用在于，任何一個可計算函數都能用這種形式來表達和求值。
平時我們使用命令式的編程語言會更傾向于關注字符串， 數字，布爾 這些可以充當主語或者賓語的類型。而我們平時跟他們打交道更多會以變量的形式，就如同“題外話”中的"狗"和"情侶"。但這篇文章的重點放在"虐"這個詞上，也就是我們常稱的謂語。在計算機里面我們通常稱他做方法 或者 函數。
既然Wiki上也說了Lambda是最小的通用程序設計語言，那我們有沒有可能用Lambda來模擬出數字， 字符串， 布爾等等的這些常用的數據類型呢？這就是接下來要講的東西。
1) Ruby中的函數
在Ruby中，函數其實可以算是一等公民，只是它的鋒芒往往被Ruby強大的面向對象特征給掩蓋掉了（它使得我們更多地關注類還有模塊）。Ruby里面有個十分簡單的創建函數的方式
|
1
2
|
[1] pry(main)> -> x { x + 2 }=> #<Proc:0x007fc171dc6010@(pry):1 (lambda)> |
它返回了一個Proc對象。其實這個對象，就類似于我們平時操作的函數對象。但是這里我們并沒有給函數賦予名字，可以理解為它是一個匿名函數。那么這種函數如何調用呢？有一種很語義化的調用方式，我們甚至不需要用變量來接受這個函數就可以調用它。
|
1
2
3
4
5
|
[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還提供了參數檢測，如果傳入的參數與定義該函數的時候不匹配的話，則會拋出ArgumentError異常。此外，Ruby還提供了一種語法糖，我們可以用Proc#[]包裹參數來調用Proc實例。
使用方式如下:
|
1
2
3
4
|
[4] pry(main)> ADD_THREE = -> x { x + 3 }=> #<Proc:0x007fd8341ffc48@(pry):4 (lambda)>[5] pry(main)> ADD_THREE[1000]=> 1003 |
2) 柯里化
Wiki 上的解釋如下
在計算機科學中，柯里化（英語：Currying），又譯為卡瑞化或加里化，是把接受多個參數的函數變換成接受一個單一參數（最初函數的第一個參數）的函數，并且返回接受余下的參數而且返回結果的新函數的技術。
既然上面已經講了Ruby創建匿名函數的基本方式，那下面來看看如何用Ruby來模擬一個柯里化的過程， 假設我有一個函數接收三個參數， 我定義如下
|
1
2
3
4
|
[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: 定義函數時參數用括號包裹是為了提高識別度，其實括號可加可不加，定義函數也可以寫成 -> x, y, z { x + y + z }
上述函數如何柯里化？按照柯里化的定義，我們可以把多參數的函數寫成嵌套返回多個單一參數函數的形式，為了方便閱讀我把代碼寫在Ruby腳本文件里面
|
1
2
3
4
5
6
7
8
9
10
11
12
|
# currying.rbADD_THREE_NUMBER_NEW = -> (a) { -> (b) { -> (c) { a + b + c } }}if __FILE__ == $0 p ADD_THREE_NUMBER_NEW.call(1).call(2).call(3)end |
運行結果
|
1
|
6 |
其實這個函數每次調用都返回了一個只帶一個參數的函數，而且返回的函數會保存著調用當前函數時傳入的參數，就是我們通常講的閉包。直到最后一個函數被調用并返回的時候，才會真正得到期望的計算結果。
當然我們可以更簡單的用Proc#[]來調用(在文章的后半部分我會統一用這種方式，比較節省代碼)
|
1
2
3
4
|
[1] pry(main)> require('./currying')=> true[2] pry(main)> ADD_THREE_NUMBER_NEW[1][2][3]=> 6 |
2. 模擬Lambda演算
Lambda既然是最小的通用編程語言，那么我們現在嘗試一下用Ruby的Proc這個現成的Lambda來演算一些東西。難的東西我自己都還接受不了，這里只能先來模擬一些最為簡單的東西了。
1) 數字
首先嘗試模擬一下數字。《計算的本質》一書中提供了一個比較直觀的段子，以下是我概括的大意
我們如果沒辦法直接使用數字，而只能使用謂語(動作)，那么我們只能重復數這個動作來描述數字這個特征，而數這個動作其實就是我們需要寫的Lambda表達式
直觀點講當我們要表示0的時候就數0次，調用方法0次，表示1的時候就調用方法一次。
那我們簡單地表示0~2就可以是
|
1
2
3
|
ZERO = -> (p) { -> (x) { x } }ONE = -> (p) { -> (x) { p[x] } }TWO = -> (p) { -> (x) { p[p[x]] } } |
這樣或許看起來有點迷糊，其實他們都用Lambda演算出來的，他們都接受一個函數p(數數這個動作)以及一個基礎值x作為參數，如果是ZERO就直接返回基礎值x， 如果是ONE就以x這個基礎值作為參數調用函數p表示數了一次。
這里我們并沒有辦法很好的表示這個基礎值x，為了直觀，我需要借用一下Ruby內置的數字0 作為一個基礎值，并且要另外定義數數這個動作。
|
1
|
CALCULATE = -> (n) { n + 1 } |
其實數數的動作就是在原來的基礎值上加1，最后我統一寫腳本
|
1
2
3
4
5
6
7
8
9
10
11
12
|
# coding: utf-8# number.rbZERO = -> (p) { -> (x) { x } }ONE = -> (p) { -> (x) { p[x] } }TWO = -> (p) { -> (x) { p[p[x]] } }def to_integer(proc) calculate = -> (n) { n + 1 } # 其中0是基礎值 proc[calculate][0]end |
在解析環境里面引入腳本并執行一些相關的語句，就能得到我們想要的結果了
|
1
2
3
4
5
6
7
8
|
[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 |
雖然對于已經含有內置數字類型的Ruby來說這種模擬完全沒有任何實用價值，不過對于了解Lambda演算這可以是一個不錯的開始。
2) 布爾型
說完數字，再來簡單說一下布爾類型吧，他們也算是比較基礎的數據類型了。而且布爾型模擬起來還更簡單些。畢竟布爾型，不是true就是false。我們可以分別寫兩個都接受兩個參數的函數，一個代表true一個代表false。true函數就返回其中的第一個參數，false函數直接返回第二個參數。
|
1
2
|
TRUE = -> (x) { -> (y) { x }}FALSE = -> (x) { -> (y) { y }} |
我們再寫一個解析腳本，作為驗證。我記得在C這種沒有布爾類型的語言中我們是用0代表false 用大于1代表true。這里我就簡單用0和1作為基礎值來驗證我們的Lambda演算是否正確
|
1
2
3
4
5
6
7
|
# boolean.rbTRUE = -> (x) { -> (y) { x }}FALSE = -> (x) { -> (y) { y }}def to_boolean(proc) proc[1][0]end |
引入運行腳本試試
|
1
2
3
4
5
6
7
8
|
[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 |
跟預期的一樣，我們的模擬是正確的，FALSE函數最后被解析成0， 而TRUE函數最后被解析成1。
以上的警告是重復定義常量所致，這里可以暫時忽略。
3) 簡單判斷一個數是否為0
最后我們再做個簡單的模擬，用到我們前面模擬的數字以及布爾兩種類型來定義一個方法，判斷傳入的參數是否為0(是否我們定義的ZERO), 并返回一個布爾類型(TRUE或者FALSE)的模擬結果。算法很簡單
|
1
2
3
4
5
6
7
|
def zero?(n) if n == 0 true else false endend |
那如何用Lambda表示？我們前面都講過了，ZERO這個函數會接收兩個參數: 第一個參數是函數，第二個為基礎值，如果傳入的是ZERO函數的話，我們調用ZERO的時候，不管傳入第一個參數是什么，調用結果都會直接返回第二個參數(也就是基礎值)。
那我們回過頭來想如果把TRUE作為它第二個參數，把一個返回FALSE的函數作為第一個參數，那當我們新函數接收的是ZERO函數并且調用它的時候不就會直接返回TRUE了嗎？而其他的方法，如ONE, TWO就會執行-> (x) { FALSE }這個過程。
可以把代碼寫成
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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 |
運行結果是
|
1
2
3
|
100 |
只有第一個ZERO是我們期望的值，最后返回了1(就是true)。其他的都不是我們需要的代表數值0的Lambda表達式。
3. 尾聲
這篇文章有點長，主要介紹了Ruby里面的Proc類，以及對函數柯里化和Lambda表達式做了最基本的講解。最后舉了一些例子，用Lambda表達式來模擬數字和布爾類型，另外使用我們模擬出來的類型作為基礎來定義一個實用的方法IS_ZERO。
本文沒有涉及太多高深的東西，因為有很多高深的東西我還吸收不了，當吸收了之后會繼續發文講述。很感謝您的閱讀。以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
原文鏈接：http://www.jianshu.com/p/f1e5280f8e0b
