算術的編碼

December 14, 2021

在具備一級函式的語言中,都會強調的是,函式也是值,可以如同數字、布林值等那般傳遞,而不是靜靜地在那邊等待被呼叫,函式的傳遞與 C/C++ 中傳遞函式位址相較,雖然就目的而言可能有某些地方重疊,然而本質上並不相同,函式位址傳遞是低階、機器層面的概念,然而,一級函式的傳遞,是數學、lambda 演算上的概念。

值就是編碼

在〈是的!不是!〉中,對於程式語言中,開發者熟悉的布林值,首次使用了箭號函式來表示,也就是使用了 lambda 表示式來表現布林值,這讓值與函式有了進一步的連結,值就是函式,函式就是值,值就是 lambda 表示式,lambda 表示式就是值。

從另一個角度來想,值就是編碼,你可以想想看,當你在電腦螢幕上看到一個 true,它真的是一個「true」嗎?不是!那只是畫出來的符號,而這個符號背後是 0 與 1 的編碼,至於是什麼編碼,那就視各程式語言而有所不同。

在 lambda 演算中,值就是使用 lambda 表示式編碼,例如,就目前看到的 yes 來說,它編碼為 f => y => f(),而 no 編碼為 x => f => f()(這並不是純綷的 lambda 表示式,之後有篇幅會改進它),函式由 lambda 表示式編碼,因此函式也是值。

yesno 之間會有什麼關係嗎?有的,yesno 的相反,不過,這只是人類語言上的描述,不夠精確,就如數學上會有函數可以將 a 映射至 b,從而使得 ab 有了關係,能不能用數學上的表示,更精確地定義出 yesno 之間的相反關係。

那麼,就來定義一個 notnot(yes) 會是 nonot(no) 會是 true,就目前的定義來說,因為 yes 始終呼叫第一個值,因此若是 yes,只要令第一個值呼叫後必然傳回 no 就可以了,相對地,若是 no,只要令第二個值必然傳回 yes,就可以定義出 not 了:

let not = b => b(() => no)(() => yes);

函式讓值對應至另一個值,也就是從一個編碼到另一個編碼,轉換後的值會形成一個集合,就像 not 轉換後會有 yesno,因而 yesno 形成了一個集合,這個集合是由布林值組成。

數字編碼

那麼,該如何定義算術上的數字呢?野心先不要太大,先來看個 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,先用指定的 fx 循環呼叫 n 次(也就是 n(f)(x) 的部份),然後再用 f 呼叫結果一次,就是 n 的下個數了。

加/減編碼

那麼加法呢?mn 要如何表示?結果其實就是 m 的第 n 個後續數,也就是 succm 循環呼叫了 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 的前一個數,就可以用來定義減法了,mn 其實就是 m 之前第 n 個數,也就是 prevm 循環呼叫了 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