λ 運算︰概念導引《三》

Y

python-lambda-calculus-module-01

Lambda Animator

黃帝內經‧素問

黃帝坐明堂,始正天綱,臨觀八極,考建五常,請天師而問之曰:論言天地之動靜,神明為之紀,陰陽之升降,寒暑彰其兆。余聞五運之數於夫子,夫子之所言,正五氣之各主歲爾,首甲定運,余因論之。鬼臾區曰:土主甲己,金主乙庚,水主丙辛,木主丁壬,火主戊癸。子午之上,少陰主之。丑未之上,太陰主之。寅申之上, 少陽主之。卯酉之上,陽明主之。辰戌之上,太陽主之。巳亥之上,厥陰主之。不合陰陽,其故何也。歧伯曰:是明道也,此天地之陰陽也。夫數之可數者,人中之陰陽也,然所合數之可得者也。夫陰陽者,數之可十,推之可百,數之可千,推之可萬。天地陰陽者,不以數推以象之謂也。

金文素

金文學

禮記‧學記

善學者,師逸而功倍,又從而庸之;不善學者,師勤而功半,又從而怨之。善問者,如攻堅木,先其易者,後其節目,及其久也,相說以解;不善問者反此。善待問者,如撞鐘,叩之以小者則小鳴,叩之以大者則大鳴,待其從容,然後盡其聲;不善答問者反此。此皆進學之道也。

在《測不準原理》一文中,提到揚‧武卡謝維奇的『波蘭表示法』,它是一種四則運算的『前綴表示法』prefix。如果我們此處再將『 λ表達式』 視履考祥一番,由於一切都是以『函式』為中心,因此『二元運算』Binary operation  也將是用著『函式』來表達。因為『應用化約』的語法形式是『 ( M 視為函式  N 看作變元)』,如此的方式一般就會是用『前綴法』的了。比方說用著 ((ADD  a)  b) 表示二元運算函數 ADD (x, y) = x + y 的求值計算。然而一個  λ表達式並沒有規定它的文本長度,所以如果用著定義『標示符』identifier 來『表現』λ表達式,這就更像是在寫『 λ語言的程式』了。

於此再度回顧一下變元的『替換規則』的定義︰

E[x := M] 是指 E表達式』中所有『自由出現』的『 x 變元』,都使用 M表達項』來取代我們可以歸納的定義如下︰

x, y 是所指 E 表達式的任意變元
A, B. M, 是所指 E 表達式的任意構成項── 該式在建構過程中的各個合乎語法的子表達式 ──。

一、 x[x := M] \equiv M

二、 y[x := M] \equiv y,只要 y 變元不是 x 變元

三、 (A B)[x := M] \equiv (A[x := M] B[x := M])

四、 (\lambda x. A) [x := M] \equiv (\lambda x. A)

五、 (\lambda y. A) [x := M] \equiv (\lambda y. A[x := M] ),只要 y 變元不是 x 變元

假使有一個簡單的函式 (\lambda x. E),它不包含著其它『子函式』以及『函式應用』,當我們說『(\lambda x. E) \equiv_{\alpha} (\lambda y. E^{\alpha})』是指 E^{\alpha} 是由上面的變元『替換規則』從 E[x := y]  得到的。這時我們講 (\lambda y. E^{\alpha}) 是經由『\alpha 變換』從 (\lambda x. E) 變更『受約束變元 x』成為 『受約束變元 y』而得來。為什麼那一邊說著『自由的』,這一邊又講著『受約束』?是因為 E 表達式中 x 變元是『自由的』,『抽象封裝』成為『函式(\lambda x. E),這時那個  x 變元就成『受約束』的了。其次為何要先『限定簡單』的函式呢?如果看一看 (\lambda x. (y x)) 的表達式, 那麼我們又要如何替換它呢?人們之所以需要『重新命名』受約束變元,是因為『應用化約』可能產生的『命名衝突』,或許『直覺』上講又怎麽會去用了『\alpha 變換』以後,卻反而又製造了『新的衝突』的呢?因此與其將它『一碼歸一碼』的煩雜分解的說,不如就建立某些『不成文的規矩』,每當提到受約束的變元『重新命名』時,就是說使用從來『不曾出現』或者說『不起衝突』的新的變元名字的意思!這樣不管再複雜的表達式都可以用著『\alpha 變換』『一步一步』的『系統化』轉換成另一個同等的表達式,於是我們可以說︰

M \equiv_{\alpha} N

。再者,與『函式所約束之虛名變元』無關的『自由變元』一般都來自於『函式應用』 ── 比方 ((\lambda x. M) y) 的『輸入項y 變元 ──,通常除非為了表達清晰起見,人們不會『重新命名』輸入項。如果從『程式計算』的角度講,『計算資料』是程式外部來的,在程式裡當然要叫它什麼名字都可以。於是那個『系統化』的『更名』辦法,自然可以行使於任何『函式』或者『應用』的『子函式表達項』中,也許就不會再有『表達轉換』作法上彼此之歧見的了!!

假使再次細思『 λ 表達式』的歸納定義,最簡單的表達式『始於變元』,然後方在其上建立『函式』,之後才『應用』函式於『變元』之上。因此前面說的那個簡單的函式 (\lambda x. E) 的可能構成是極其有限的,比方說 E 中只能有一個變元,假使 E 有兩個以上的變元,那一定是由『函式應用』或者『多元函式』所產生的。所以它只可能像是 (\lambda x. x) 或者 (\lambda x. y) 這樣。也許有人會想難道它不能是像 (\lambda x. \ 2\times x) 或者 (\lambda x.  + x \ y) 的嗎?在某些『應用 λ語言』中,這種語法是合宜的;然而這裡用的卻是『純粹』Pure 的 λ語法,這個『語法集』中根本沒有『什麼是 \times+』,因此表達所需要用的一切都得在『基元』Primitive 上自己建立。複雜』與『難題』是兩種不同的『困難性』。許多『難題』表述起來很簡單── 比方說費瑪最後定理x^n + y^n = z^n, n \geq 3 沒有整數解 ──,想解決卻十分困難。而『複雜』是源於構成『部份』眾多或者『結構』縱橫多層,雖然基本『單元』並不『困難』,基礎結構『組件』也很『簡單』,由於『數大層多就是難』這就是 λ 表達式的『寫照』。這個『複雜性』或許也就是『 λ 語法』之所以『方言』崛起的緣故。

終於我們可以無歧義的說

((\lambda x. M) N) \equiv_{\beta} M[x :=N] \equiv_{\beta} M^{\beta}

,是講 M^{\beta} 是函式『 \beta 化約』的結果,它是由系統化的變元之替換規則所得來。簡約的講那些 N 中原有的『自由變元』在 M^{\beta} 裡依然還是『自由變元』,不會變成『受約束變元』。假使說函式用『抽象封裝』 λ表達式,函式應用『解封函式』產生『結果』的 λ表達式。然而從『字串改寫系統』來看,不管是『 \alpha 變換』或者是『 \beta 化約』都不過是一種字串的『改寫規則』,是將那一個『 λ表達式』的字串改寫成『同等計算』之這一個『 λ表達式』而已!!

現在讓我們談談『 \eta 變換』。假設 M 函式中沒有 x 變元,那麼 (\lambda x. (M x))M 除了『文本』不同,『計算結果』上能有什麼不同的嗎?對任何的輸入變元 z 來講,

((\lambda x. (M x)) z) \equiv_{\beta} (M z)

,這樣從函式的『對應域』或者說『值域』的考察『觀點』,就是『 \eta 變換』的由來,寫作︰

(\lambda x. (M x))  \equiv_{\eta} M

。然而這個『 \eta 擴張』卻有些『哲學上』的爭議,人們對於什麼是『函式等同』的定義與看法並不相同。比方講假設說『』是種『行為』函式,『』或『不愛』的結果取決於『』;那麼『愛物之心』與『』兩者是否會有差異呢?(λ物. (愛 物)) \equiv 愛 嗎??

 

─── 待續…… ───