在具備一級函式的語言中,都會強調的是,函式也是值,可以如同數字、布林值等那般傳遞,而不是靜靜地在那邊等待被呼叫,函式的傳遞與 C/C++ 中傳遞函式位址相較,雖然就目的而言可能有某些地方重疊,然而本質上並不相同,函式位址傳遞是低階、機器層面的概念,然而,一級函式的傳遞,是數學、lambda 演算上的概念。
在〈是的!不是!〉中,對於程式語言中,開發者熟悉的布林值,首次使用了箭號函式來表示,也就是使用了 lambda 表示式來表現布林值,這讓值與函式有了進一步的連結,值就是函式,函式就是值,值就是 lambda 表示式,lambda 表示式就是值。
從另一個角度來想,值就是編碼,你可以想想看,當你在電腦螢幕上看到一個 true
,它真的是一個「true」嗎?不是!那只是畫出來的符號,而這個符號背後是 0 與 1 的編碼,至於是什麼編碼,那就視各程式語言而有所不同。
在 lambda 演算中,值就是使用 lambda 表示式編碼,例如,就目前看到的 yes
來說,它編碼為 f => y => f()
,而 no
編碼為 x => f => f()
(這並不是純綷的 lambda 表示式,之後有篇幅會改進它),函式由 lambda 表示式編碼,因此函式也是值。
yes
與 no
之間會有什麼關係嗎?有的,yes
是 no
的相反,不過,這只是人類語言上的描述,不夠精確,就如數學上會有函數可以將 a
映射至 b
,從而使得 a
與 b
有了關係,能不能用數學上的表示,更精確地定義出 yes
與 no
之間的相反關係。
那麼,就來定義一個 not
,not(yes)
會是 no
,not(no)
會是 true
,就目前的定義來說,因為 yes
始終呼叫第一個值,因此若是 yes
,只要令第一個值呼叫後必然傳回 no
就可以了,相對地,若是 no
,只要令第二個值必然傳回 yes
,就可以定義出 not
了:
let not = b => b(() => no)(() => yes);
函式讓值對應至另一個值,也就是從一個編碼到另一個編碼,轉換後的值會形成一個集合,就像 not
轉換後會有 yes
、no
,因而 yes
與 no
形成了一個集合,這個集合是由布林值組成。
那麼,該如何定義算術上的數字呢?野心先不要太大,先來看個 addOne
如何定義:
let addOne = x => x + 1;
因此 addOne(0)
就是 (x => x + 1)(0)
,也就是說可以使用 (x => x + 1)(0)
來表示 1 這個結果了,2 的話就是 (x => x + 1)(1)
,也就是 (x => x + 1)((x => x + 1)(0))
,依此類推,就可以得到更多的數字了。
仔細想想,若不展開 addOne
的話,1 是 addOne(0)
,2 是 addOne((addOne)(0))
,3 就是 addOne(addOne((addOne)(0)))
,也就是說數看看有幾個 addOne
,就是代表哪個數字。
如果不限於加法操作,可以是某個 f
操作,並使用 x
作為 0 的箭號函式表示,那麼就可以使用箭號函式表示來定義 1 為 f => x => f(x)
,2 為 f => x => f(f(x))
,3 為 f => x => f(f(f(x)))
:
let $1 = f => x => f(x);
let $2 = f => x => f(f(x));
let $3 = f => x => f(f(f(x)));
如此持續下去,就可以使用箭號函式來為正整數編碼了,簡單來說,看到 n 個 f
就是代表數字 n 了,那麼一個 f
都沒有的話,就可當成 0 了:
let $0 = f => x => x;
這就形成了自然數集合了,現在,如果想判斷自然數是不是 $0
呢?由於 $0
是唯一會直接傳回 x
的(函式)值,因此 x
的部份若是 yes
,而 f
的部份無論如何都傳回 no
,那麼 $1
、$2
、$3
…等就必然一定傳回 no
,這就可以寫出個 is_$0
函式:
let is_$0 = n => n(x => no)(yes);
一旦規則確定了,實際上可以由機器來自動產生編碼,例如,輸入 $4
自動產生 f => x => f(f(f(f(x))))
,不過,就 lambda 表示式來說,是不用有 $0
、$1
、$2
這些名稱,這只是為了方便討論,才放寬至可以將 lambda 表示式指定給某名稱,實際上,完全可以用箭號函式來產生自然數,可以定義一個 succ
,給它一個自然數,自動產生下個自然數的編碼:
let succ = n => f => x => f(n(f)(x));
succ
簡單來說,給一個自然數 n
,先用指定的 f
對 x
循環呼叫 n
次(也就是 n(f)(x)
的部份),然後再用 f
呼叫結果一次,就是 n
的下個數了。
那麼加法呢?m
加 n
要如何表示?結果其實就是 m
的第 n
個後續數,也就是 succ
對 m
循環呼叫了 n
次:
let add = m => n => n(succ)(m);
那麼減法呢?雖然可以用 succ
求得 n
的後繼數 f => x => f(n(f)(x))
,然而沒辦法再從這個值取出 n
了,如果有個函式可一併傳回 n
與後繼數,也就是若可以是 pair(n)(succ(n))
這樣的結果,那麼傳回結果為 p
的話,後繼數就是 left(p)
,原本的 n
就是 right(p)
。
函式可一併傳回 n
與後繼數,那就讓這個函式傳回 pair(n)(succ(n))
好了,那這個函式可以接受什麼?也令其接受 pair
的值如何?若用 p
表示,那目前的數 n
就是 right(p)
,那麼需要的函式就是:
let pair_succ = p => pair(right(p))(succ(right(p)));
對於 pair_succ(pair($0)($1))
,$1
代表目前的數字,而 $0
代表 $1
的前一個數字,用來套用 pair_succ
的結果會是 pair_succ(pair($1)($2))
,也就是目前數字為 $2
,而前一個數字為 $1
,如此依此類推下去…
問題來了,如果有個 pair
的呼叫結果中,$0
表示目前數字,那前一個數字該是什麼?看看 pair_succ
的定義,實際上只關心右邊的值,那就 pair($0)($0)
,$0
的前一個數字就還是 $0
吧!
於是,若有個數字 n
,想要得到一個有 n
後繼數的 pair
傳回值,那就是 n(pair_succ)(pair($0)($0))
,取得這個傳回值的左值,就會得到 n
的前一個數了:
let prev = n => left(n(pair_succ)(pair($0)($0)));
可以取得 n
的前一個數,就可以用來定義減法了,m
減 n
其實就是 m
之前第 n
個數,也就是 prev
對 m
循環呼叫了 n
次:
let sub = m => n => n(prev)(m);
有了加、減法的定義之後,1 + 2 - 3
就可以寫成 sub(add($1)($2))($3)
,為了便於觀看,來寫個輔助函式:
function natural(n) {
return n(i => i + 1)(0);
}
這輔助函式與 lambda 演算無關,純綷便於人類觀看結果罷了,例如:
console.log(natural($0)); // 顯示 0
console.log(natural($1)); // 顯示 1
console.log(natural(add($1)($2))); // 1 + 2,結果顯示 3
console.log(natural(sub(add($1)($2))($3))); // 1 + 2 - 3,結果顯示 0