λ 運算︰概念導引《一》

《論語‧子路篇》

子路曰：『衛君待子而為政，子將奚先？』子曰：『必也正名乎！』子路曰：『有是哉，子之迂也！奚其正？』子曰：『野哉由也！君子於其所不知，蓋闕如也。名不正，則言不順；言不順，則事不成；事不成，則禮樂不興；禮樂不興，則刑罰不中；刑罰不中，則民無所措手足。故君子名之必可言也，言之必可行也。君子於其言，無所苟而已矣。』

《説文解字》：

名，自命也。从口，从夕。夕者，冥也。冥不相見，故以口自名。

古來『名字』的傳統，幼時口呼『命名』，成年書寫『取字』。

許多讀過『λ 運算』的人，多半覺得它既『難懂』又『難解』。這是有原因的，如果用『抽象辦法』談論著『抽象事物』，又不知道為何如此表述當然『難懂』；假使不能『困思勉行』多次的『深思熟慮』，以至於能夠一旦了悟那就自然『難解』。通常越是『基本』的概念，由於太過『直覺』了，反而容易『誤解』。就像化學元素『週期表』上的元素不過一一八個，它所構成的世界卻是千嬌萬媚繁多複雜，要講『鐵』的『性質』與『作用』，也許一大本書都不能窮盡，但換個方向說鐵不就是日用之物的嗎？

邱奇發展『λ 運算』Lambda calculus，這裡的『calculus』不是指『微積分』，是用著『函式』Function 和『變元』Variable 的概念，來談論『計算』一事是什麼？複雜的『函式』是如何清晰明白無歧異的『結構』而成？『變元』的『替換』Substitution 規則，要如何系統化的處理變元替換時『異物同名』衝突之問題？如果從『函式求值』上講，一個『λ 表達式』用著怎樣的『規則』可以『轉換』成為『同等』equivalent 的另一個 λ 表達式呢？……種種。假使給定了兩個『λ 表達式』是否會有一個普適的『演算法』能夠判定彼此間的『同等性』呢？……等等。

『λ 表達式』可以用『數學歸納法』定義如下︰

變元集合 $V = \{ v_1, v_2, v_3, \dots, v_n, \dots \}$
抽象符號 『 λ 』與『 . 』，符號本身不是λ 表達項
結構括號 『 ( 』與『 ) 』，括號本身不是λ 表達項

λ 表達式的集合 $\Lambda$ ，由下面三條規則歸納界定︰

一、如果 $x \in V$ ，那麼 $x \in \Lambda$

二、如果 $x \in V$ 而且 $M \in \Lambda$ ，那麼 $( \lambda x. M ) \in \Lambda$

三、如果 $M, N \in \Lambda$ ，那麼 $( M \ N) \in \Lambda$

假如使用數學上函數的觀點來解釋，『第一條』規則是說︰『變數』是一個『λ 表達式』。『第二條』規則用以抽象建構單一變數的『函數』，變數 $x$ 是『函數』的『輸入之數』， $M$ 是『函數』的『計算表達式』，結構括號表示『函數』的在表達式裡的範圍。『第三條』規則是應用『函數求值規則』，假使該應用合理的話，計算表達式 $M$ 在 $N$ 表達式下的值。舉個例子說︰

假設 $x, a$ 是變數，所以 $x, a$ 是 λ 表達式，因此
$(\lambda x. \ x)$ 是一個函數的 λ 表達式，因是
$( ( \lambda x. \ x) \ a)$ 是一個應用求值的 λ 表達式。

如果參造著一般數學上的描述，首先得將『匿名的』 $(\lambda x. \ x)$ 給個『命名』，假使叫做 $I$ ，寫作 $I(x) = x$ ，這樣 $((\lambda x. \ x) a)$ ，假如依據函數求值就是 $I(a) = a$ 。雖然我們還沒有定義 λ 表達式之改寫『化約』的三個『同等』 $\equiv$ 轉換規則，於此比擬的講它會依據『 $\beta$ 化約』的規則而得到 $((\lambda x. \ x) a) \equiv_{\beta} a$ 。那麼為什麼 λ 中的函數表達式並不需要『名字』的呢？因為『第二條』規則已經把函數的『計算規則』── 那個叫做 $M$ 的表達式 ──『抽象之封裝』了起來，而『第三條』規則又將『輸入變數』 $N$ 給打包『封裝其應用』了。因此『計算規則』與『輸入物項』兩者都『內在』且『俱全』，所以無需『外部』其它的指稱，當然也可以自足的作計算了。反觀通常數學上的函數記號法，寫作 $y = M(x)$ ，是用著『對應域』或者說用著『值域』來表達『計算結果』的，也就是說用著 $(x,y) \in M$ 的集合論述，因此才用著不同的『命名』變數，來區分『計算過程』中的『函數』、『函數之輸入值』或是『函數之輸出值』。然而假使將 $\lambda x. \ M$ 想像成函數上的 $\lambda(x) = M(x)$ ，雖說是『不恰當的』── 每個封裝函數都叫做 $\lambda(\dots)$ ──，但是對於了解那個 λ 表達式到底在說什麼還是很『有幫助的』。現在我們再看一個比較複雜的例子，式中 $x, y, z$ 都是變數︰

$((\lambda z. (( \lambda y. y + 1) (( \lambda x. x^2)z)))3)$
$\equiv_{\beta}(( \lambda y. y + 1) (( \lambda x. x^2)3))$
$\equiv_{\beta}(( \lambda y. y + 1) 3^2)$
$\equiv_{\beta} 3^2 + 1$

。此處特別停於『 $3^2 + 1$ 』是想指出︰假使在函數求值計算過程中，如果不知道『如何平方』？也不知道『 + 』是『什麼意意』？那就可能會『止於』某個 λ 表達式無法繼續計算。其次如果按造定義的方式『建構』的 λ 表達式將會有很多的括號，這使得『閱讀』以及『化約』都十分『麻煩』，必須小心警慎的平衡括號。雖然通常有著一些『簡化括號』的『約定』，然而此時還是『辛苦』點的好，因為『表達式』的『結構』就在『括號的結構』之中，假使遭遇到了『化約結果』不如預期，這也許正是『反思』與『除錯』之重要的『關鍵處』。

假使再看一個例子 $(\lambda s. (s s))$ ，它到底在說什麼的呢？如果用著前面的 $\lambda(s)= s(s)$ 的想法來看，這是講有某個 λ 表達式『 $s$ 』應用於『自身』Self 之上的函數。如果 $a$ 是一個『變數』數值之輸入，那麼 $((\lambda s. (s s))a)$ 化約成了 $(a a)$ ，也許應用『數值對數值』之求值，是一件『不知說的是什麼』的事吧！那如果 $f$ 是一個『函數』之輸入的呢？那麼 $((\lambda s. (s s))a)$ 化約成了 $(f f)$ 彷彿是種『回歸求值』。
比方說︰
$I =_{df} (\lambda x. x)$

$((\lambda s. (s s)) I)$
$\equiv_{\beta}(I I)$
$\equiv_{\beta}((\lambda x. x) (\lambda x. x))$
$\equiv_{\beta} (\lambda x. x)$
$\equiv_{\beta} I$

$((\lambda s. (s s)) (\lambda s. (s s)))$
$\equiv_{\beta}((\lambda s. (s s)) (\lambda s. (s s)))$
$\equiv_{\beta} \dots$
$\equiv_{\beta}((\lambda s. (s s)) (\lambda s. (s s)))$

這時如果思考什麼是函數之『定點概念』是否會似曾相識呢？由於並非是所有的函數都有定點，也就像不是所有的 λ 表達式之化約都能在『有限』的步驟裡被完成，它有可能會陷入『無窮』的循環。

那麼什麼是『異物同名』呢？如果考慮下面的 λ 表達式︰

$(((\lambda f. (\lambda a. (f a))) a ) b )$

，式子裡有兩種『 $a$ 』的出現，一種是在函數抽象中的虛名變數 $M =_{df} (\lambda a. (f a))$ ，另一種是在函數應用中的輸入變數 $((\lambda f. M) a )$ ，這樣就發生了變數的『同名衝突』。所以需要將 $(\lambda a. (f a))$ 裡的虛名變數『重新命名』── 比方說改成 $t$ ──，於是該函數就變成了 $M^{'} =_{df} (\lambda t. (f t))$ ，雖然虛名變數改變了名字，但是還是表達著一個同等的函數。此類『異名同物』的變數替換規則，一般稱作『 $\alpha$ 變換』，也就是說 $M[a := t] \equiv_{\alpha} M^{'}$ ，此處 $[a := t]$ 表示 $a$ 被 $t$ 所替換，而 $M[a := t]$ 是講， $M$ 表達式中所有的 $a$ 都被 $t$ 所替換。在此作個表達式計算化約的比較︰