輪扁斲輪？！

2014-09-05 懸鉤子

《莊子‧天道》
…
世之所貴道者，書也。書不過語，語有貴也。語之所貴者，意也，意有所隨。意之所隨者，不可以言傳也，而世因貴言傳書。世雖貴之哉，猶不足貴也，為其貴非其貴也。故視而可見者，形與色也；聽而可聞者，名與聲也。悲夫！世人以形色名聲為足以得彼之情。夫形色名聲，果不足以得彼之情，則知者不言，言者不知，而世豈識之哉！

桓公讀書於堂上，輪扁斲輪於堂下，釋椎鑿而上，問桓公曰：『敢問：公之所讀者，何言邪？』公曰：『聖人之言也。』曰：『聖人在乎？』公曰：『已死矣。』曰：『然則君之所讀者，古人之糟魄已夫！』桓公曰：『寡人讀書，輪人安得議乎！有說則可，無說則死！』輪扁曰：『臣也以臣之事觀之。斲輪，徐則甘而不固，疾則苦而不入，不徐不疾，得之於手而應於心，口不能言，有數存焉於其間。臣不能以喻臣之子，臣之子亦不能受之於臣，是以行年七十而老斲輪。古之人與其不可傳也死矣，然則君之所讀者，古人之糟魄已夫！』
…

《孔子家語‧好生》有言曰︰

楚王出遊，亡弓，左右請求之。王曰：『止，楚王失弓，楚人得之，又何求之！』孔子聞之，惜乎其不大也，不曰人遺弓，人得之而已，何必楚也。

或有人會說︰

何必『人』？『得失』而已。

又有人會講︰

天地果有『得失』之乎？

古之學者為己。然而問『學』之『道』貴在能『心有疑』又還『感覺怪』，『去疑除怪』以至於『哈哈大笑』幽默一番，有益於『身心健康』。故

─── 所謂文字，得意忘言，能不能傳，誰知誰了？！ ───

樹莓派、樹莓派之學習、樹莓派之教育

λ 運算︰計物數《遞迴補遺》

2014-09-04 懸鉤子

我喃喃自語說︰我做了一個夢。在那夢中我做了一個夢，我喃喃自語說︰我做了一個夢。宛如我置身『鏡廊』一面『鏡子』前，我見着了『鏡裡』的我置身『鏡廊』一面『鏡子』前，… $\infty$ 。

俄羅斯娃哇是『有趣的』事物，雖然只有『有限』的幾個『迭套』，它卻是『象徵』一個『不思議』的『奧秘』。其實『遞迴』Recursion 與『疊代』 Iteration 兩個概念，彼此間有著很深刻的『聯繫』。

為什麼數學上常常要用『遞迴定義』的呢？假使你出於『好玩』，想『定義』一個『數列』，那麼有什麼『簡單』的辦法的呢？

有人說︰這很簡單啊！就給一個 $F_n$ 『公式』Formula 就好了，就好比講這個數列是

$F_n =_{df} \Box \Box, n=0 \cdots \infty$ 。

有人問︰萬一你不知道『那個公式』呢？還是說如果『公式不存在』這樣子就根本『沒辦法』去定義『數列』的呢？

有人答︰『可以』的啊！比方說假使你『知道』

一、 $F_0$ 的『值』

二、曉得如何從 $F_k$ 『計算』出 $F_{k+1}$ 的『值』，這樣就算是不知道 $F_n$ 是能不能夠表達，一樣可以『定義』這個『數列』的啊！

據說義大利的數學家李奧納多‧費波那契 Leonardo Fibonacci 描述各代『兔子生育』總數目時得到這個數列︰

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$

因此 $F_2 = F_1 + F_0 = 1 + 0 = 1, F_3 = F_2 + F_1 = 1 + 1 = 2. \cdots$ ，所以可以逐步的得到『費波那契數列』。當然可以求解那一個『差分方程式』得到

$F_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]$ 。

然而並非所有可以『遞迴定義』的數列，都能有『公式解』，或者說還沒將它『算出來』。所以能這樣從幾個『初始資料』和一個『遞迴關係』來定義東西的方式，自然有它的好處的了。

一般人們用程式計算『數列』 $a_n$ 的『級數和』

$S_n = a_0 + a_1+\cdots +a_n$

，很自然的會用『疊代』的想法，可以表達為

$R := a_0$
$R := R+ a_n, n=1 \cdots N$

，此處『:=』表示變數『賦值』，逐項累加到所需要的 $N$ 次。這或許是大部分的程式語言都有『FOR LOOP』的原因。但是遇到了像『河內塔』這一類問題，由於那個 $a_n$ 本身就先需要計算出來，況且還和 $a_k, k=1 \cdots n-1$ 有關，這時想寫個『疊代法』程式就很困難的了。所以『方法選擇』應當針對『問題狀況』，難有『萬能之法』的啊！

為了談談『疊代』與『遞迴』之間的『聯繫』，我們先舉一個如何用『遞迴』來寫『加法』例子︰

$addr \ x, y =_{df}$
IF y is 0 THEN x
ELSE addr (SUCC x) (PRED y)

將之翻譯成『Y組合子』用的『 λ表達式』︰

$addr =_{df} \lambda f. \lambda x. \lambda y. IFTHENELSE \ (ISZERO \ y) \ (x) \ (f \ (SUCC \ x) \ (PRED \ y))$

從這個翻譯來看，因為 λ表達式不能直接指涉『 $addr$ 』之故，所以才需要這個『佔位置』變元 $f$ ，當化約『 $addr (Y \ addr) \ 3 \ 2$ 』時，變元 $f$ 就是表示『 $Y \ addr$ 』這個函式。

假使我們知道 $y \leq 1$ ，那麼可以『手動』改寫『addr』為︰

$addi \ x, y =_{df}$
IF y is 0 THEN x
ELSE (
IF ((PRED y) is 0) THEN (SUCC x)
ELSE (
IF (PRED (PRED y) is 0) THEN SUCC(SUCC x)
ELSE (0) ※FAIL
)

並且翻譯成 Lambda Calculator 寫法

\x.\y. IFTHENELSE (ISZERO y) (x) (IFTHENELSE (ISZERO (PRED y)) (SUCC x) (IFTHENELSE (ISZERO (PRED (PRED y))) (SUCC (SUCC x) ) (0) ))

addi 5 1

addi 7 0

也就是說有限的遞迴通常可以手動的『複製遞迴計算』，自己賦與遞迴中所需要的『呼叫參數值』，改寫成『非遞迴』的『長版本程式』。這個程式中有許多的『自我相似』的『程式碼』，彷彿是個『俄羅斯娃娃』的『構造』一般！如果將它翻譯成『疊代』的程式，經常會作『概念改寫』︰將 $y$ 減一，且將 $x$ 加一，直到 $y = 0$ 為止。它雖然經常能夠得到『短版本程式』，但是兩者間的『概念聯繫』是很明晰的啊！！

所以當我們還不清楚可能的『計算步驟』時『遞迴』有『優勢』，如果有對等的『疊代』程式通常『執行速度』會比較『快』，因此許多程式語言也有使用『中止條件』的『WHILE LOOP』之建構。萬一『中止條件』在有限時間裡始終達不到，或許將會陷入『無窮循環』，這時兩者狀況是相似的。但是也不要以為『無窮循環』就一定是『不好的』，有時候它正是所要的『目的』，就像『CPU』開機後就一直運作執行一樣。

為什麼 λ表達式無法『直接指涉』自身的呢？因為在『純 λ語言』裡你無法『定義』標示符號，所以當表達成

$\Box =_{df} \cdots \Box \cdots$

，這只是為了方便的說法，無法如設想的『化約』表達式中 $\Box$ 是『定義』的『引用』，它在『化約』時只會被當成一個叫做 $\Box$ 的『變元』，於是根本就達不成『遞迴』之目的了。

樹莓派、樹莓派之學習、樹莓派之教育

λ 運算︰計物數《下》

2014-09-03 懸鉤子

${1\over 2} < \left\lfloor \mathrm{mod}\left(\left\lfloor {y \over 17} \right\rfloor 2^{-17 \lfloor x \rfloor - \mathrm{mod}(\lfloor y\rfloor, 17)},2\right)\right\rfloor$

二零零一年加拿大傑夫‧塔珀 Jeff Tupper 所發現的自指公式，它的二維『函數圖像』，與數學的『公式外觀』相仿。

一九二九年比利時畫家雷內‧弗朗索瓦‧吉蘭‧馬格利特 René François Ghislain Magritte 名作《形象的叛逆》The Treachery of Images 上用法文寫著『你看到的不是煙斗』。

一九零四年荷蘭著名品牌德羅斯特 Droste 所販售的可可粉之包裝盒上的圖片是一位護士拿著一個上有杯子及紙盒的托盤，托盤裡的杯子和紙盒上之圖案也就是這張圖片。

不過『自我指涉』可能會產生『矛盾』，『遞迴』也許將陷入『無窮循環』，然而它們的『魅力』卻是歷久彌新！！

『抽象』的概念雖然『無象』可以用來作『想象』，就如同前面談到過的『思想實驗』一樣，還是可以建造『情境』方便『觀相』的。假使說『思考』是根『概念磁鐵』，那麼『思維』就是『磁力線』。從『創造發想』的『發散處』出發，抵達『清晰自恰』之『收斂點』。因此『磁力線』的『封閉性』也可比喻成『思維』是『自我遞迴』的了。這樣或許『思考』在『博』與『精』的方面能夠成為『自行車』之『雙輪』，而這個『操控』之人也逐漸地步上了『收發自如』的道路。

讓我們再次思考邱奇自然數的構造

$n =_{df} \lambda f. \lambda x. \ f^n \ x$
$\equiv \lambda f. \lambda x. \ f(\cdots(f x))$
$\equiv \lambda f. \lambda x. \ f(f^{n-2}(f x))$

，這說明了變元 $f, x$ 在結構中的位置，以及『應用求值策略』也許是『外到內』 $f [f^{n-1} x]$ 或者是『內到外』 $f^{n-1}(f x)$ 。當我們在『解讀』一個表達式時，什麼將會是『變元』 $f, x$ 的『賦值』，以及它們的『性質』，往往就是『理解』表達式的『關鍵處』，以及自己『構思』的『起始點』。舉個『ISZERO』例子說

$ISZERO =_{df} \lambda n. n (\lambda x. \ FALSE) \ TRUE$

$ISZERO \ n$
$\equiv_{\beta} n \ (\lambda x. \ FALSE) \ TRUE$
$\equiv_{\beta} (\lambda f. \lambda x. \ f^n \ x) \ (\lambda x. \ FALSE) \ TRUE$
$\equiv_{\beta} {(\lambda x. \ FALSE)}^{n-1} (\lambda x. \ FALSE \ TRUE)$
$\equiv_{\beta} (\lambda x. \ FALSE) \ {(\lambda x. \ FALSE)}^{n-1} (TRUE)$

，然而 $((\lambda \bigcirc. \ FALSE) \ \Box) \equiv_{\beta} FALSE, \ n \geq1$ ，這就是為什麼選擇『 $(\lambda x. \ FALSE)$ 』函式的原因。現在只剩下『0』的情況需要考慮了

$ISZERO \ 0$
$\equiv_{\beta} 0 \ (\lambda x. \ FALSE) \ TRUE$
$\equiv_{\beta} (\lambda f. \lambda x. \ x) \ (\lambda x. \ FALSE) \ TRUE$
$\equiv_{\beta} (\lambda x. \ x) \ TRUE$
$\equiv_{\beta} TRUE$

，所以也就是會用『TRUE』的理由。

在數學上既然有『加法』也就有『減法』，那麼能不能仿造 $n$ 的『後繼數』是 $n+1$ ，定義一個『前導數』predecessesor $n-1$ 的呢？也就是說在 $n$ 中想辦法『去掉一個 $f$ 』，下面的這個

$PRED =_{df} \lambda n. \lambda f. \lambda x. \ n \ (\lambda g. \lambda h. \ h \ (g \ f)) (\lambda u. x) \ (\lambda u. u)$

就是一個精巧的設計。為了『解讀』這個設計，讓我們先定義幾個『縮寫』以利表達的『簡潔』︰

$T =_{df} \lambda g. \lambda h. \ h \ (g \ f)$
$D =_{df} \lambda u. x$
$I = _{df} \lambda u. u$
$PHED =_{df} \lambda n. \lambda f. \lambda x. \ n \ T\ D \ I$

Lambda Calculator 化約例子

PRED 3
⇒ λf.λx.3 T D I
⇒ λf.λx.(λi0.T (T [T i0])) D I
3⇒ λf.λx.T (T (T D)) I
4⇒ λf.λx.(λh.h (T [T D] f)) I
5⇒ λf.λx.I (T (T D) f)
6⇒ λf.λx.T (T D) f
⇒ λf.λx.(λh.h (T D f)) f
⇒ λf.λx.f (T D f)
⇒ λf.λx.f ((λh.h [D f]) f)
⇒ λf.λx.f (f (D f))
⇒ 2

PRED 2
⇒ λf.λx.2 T D I
⇒ λf.λx.(λi0.T (T i0)) D I
3⇒ λf.λx.T (T D) I
4⇒ λf.λx.(λh.h (T D f)) I
5⇒ λf.λx.I (T D f)
6⇒ λf.λx.T D f
⇒ λf.λx.(λh.h (D f)) f
⇒ λf.λx.f (D f)
⇒ 1

PRED 1
⇒ λf.λx.1 T D I
⇒ λf.λx.(λi0.T i0) D I
3⇒ λf.λx.T D I
4⇒ λf.λx.(λh.h (D f)) I
5⇒ λf.λx.I (D f)
6⇒ λf.λx.D f
⇒ 0

PRED 0
⇒ λf.λx.0 T D I
⇒ λf.λx.I D I
3⇒ λf.λx.D I
⇒ 0

仔細觀察左邊化約例子的過程，我們可以說︰
甲、 $D =_{df} \lambda u. x$ 之主要目的就是『去掉一個 $f$ 』，它是一個值為變元 $x$ 的『常函式』。

乙、 $I =_{df} \lambda u. u$ 的目的︰一、由於在自然數中並沒有『負數』的概念。在『PRED 0』中 $D \ I \equiv_{\beta} x$ ，所以『化約』依然為『0』，這至少是我們所期望的『結果』。二、化約過程的『第 3 步』是展開 $T(T^{n-2}(TD))$ 最左邊的第一個 $T$ ，這時 $T$ 中的變元 $g$ 已經替換成 $T^{n-2}(TD)$ 所以得到 $\lambda h. \ h \ ( T^{n-2}(TD) \ f)$ 。假使沒有『結尾』的 $I$ ，是化約不掉這一個變元 $h$ 函式封裝，進行『第 4 步』的，它將於化約過程中『駐留』。又因為 $I$ 是恆等函式 $I \ \Box \equiv_{\beta} \Box$ ，所以才能夠得到『第 6 步』的 $T^{n-2}(TD \ f)$ 。然後逐步化約透過 $\lambda h. \ h \ \Box \ f$ 將 $n-1$ 個變元 $f$ 從『 $\Box$ 』的右邊『複製』到『 $\Box$ 』之左邊，於是最終止於 $D \ f \equiv_{\beta} x$ 的化約。『丟掉』了這個『 $f$ 』，以及『保留』變元 $x$ 完成了 $n$ 的『前導數』 $n - 1$ 之運算。

讀者可以用 Lambda Calculator 多練習幾個例子，自己嘗試作一些『概念實驗』，細心體會一下『高階函式』運用的『巧妙處』。有時後用有意義的『單個符號』當作『運算子』，常常較容易『理解』與『運用』，因為這在『量子力學』中早已經行之多年的了。

既然已經有了『前導數』，我們就可以將『減法』 $m - n$ 定義成

$- =_{df} \lambda m. \lambda n. n \ PRED \ m$

。也就是說 $m - n$ 是自然數 $m$ 『用前導數』 $n$ 次的那個數。在《λ 運算︰概念導引之《補充》※真假祇是個選擇？？》一文中，我們談到過一些『邏輯』運算的定義。比方說藉著『非』NOT 、『ISZERO』和『減法』，我們可以將自然數之『大於』關係 $m > n$ 定義為

$> =_{df} \lambda m. \lambda n. NOT (ISZERO \ (- \ m \ n))$

。這是為什麼呢？因為假使 $m > n$ ，那麼 $(m - n) > 0$ ，所以 $ISZERO \ (m - n)$ 為假，因此 $NOT \ (ISZERO \ (m - n))$ 就為真。有人說萬一 $m \leq n$ ，這時根據『PRED』的定義，因此 $m - n$ 為『0』，所以 $ISZERO \ (m - n)$ 為真，那麼 $NOT \ (ISZERO \ (m - n))$ 就為假。

當然自然數的『等於』與『小於』關係也都是可以『定義』的，於此就不一一介紹的了。不如列出作者驗證文本『正確與否』用的一些 Lambda Calculator 『字典定義』，提供有興趣的讀者研究︰

* [\m.\n.m (+ n) 0] = \m.\n.m (\i0.\f.\x.n f (i0 f x)) FALSE
+ [\m.\n.\f.\x.m f (n f x)] = \m.\n.\f.\x.m f (n f x)
– [\n. \m. m PRED n] = \n.\m.m PRED n
0 [\f.\x.x] = \f.\x.x
1 [SUCC 0] = \f.\x.f x
2 [SUCC 1] = \f.\x.f (f x)
3 [SUCC 2] = \f.\x.f (f (f x))
4 [SUCC 3] = \f.\x.f (f (f [f x]))
5 [SUCC 4] = \f.\x.f (f (f [f (f x)]))
6 [SUCC 5] = \f.\x.f (f (f [f (f (f x))]))
7 [SUCC 6] = \f.\x.f (f (f [f (f (f {f x}))]))
8 [SUCC 7] = \f.\x.f (f (f [f (f (f {f (f x)}))]))
9 [SUCC 8] = \f.\x.f (f (f [f (f (f {f (f (f x))}))]))
< [\m. \n. AND (ISZERO (- m n)) (NOT(ISZERO (- n m)))] = \m.\n.n PRED m (\x.FALSE) TRUE (m PRED n (\x.FALSE) TRUE FALSE TRUE) FALSE
= [\m. \n. AND (ISZERO (- m n)) (ISZERO (- n m))] = \m.\n.n PRED m (\x.FALSE) TRUE (m PRED n (\x.FALSE) TRUE) FALSE
> [\m. \n. NOT (ISZERO (- m n))] = \m.\n.n PRED m (\x.FALSE) TRUE FALSE TRUE
AND [\p. \q. p q FALSE] = \p.\q.p q FALSE
FALSE [\x.\y.y] = \x.\y.y
IFTHENELSE [\p. \x. \y. p x y] = \p.\x.\y.p x y
ISZERO [\n.n(\x.FALSE) TRUE] = \n.n (\x.FALSE) TRUE
NOT [\p. p FALSE TRUE] = \p.p FALSE TRUE
OR [\p. \q. p TRUE q] = \p.\q.p TRUE q
PRED [\n. \f. \x. n (\g. \h. h (g f)) (\u.x)(\u.u)] = \n.\f.\x.n (\g.\h.h (g f)) (\u.x) (\u.u)
SUCC [\n.\f.\x.f(n f x)] = \n.\f.\x.f (n f x)
TRUE [\x.\y.x] = \x.\y.x
Y [\g. (\x. g(x x)) (\x. g(x x))] = \g.(\x.g (x x)) (\x.g (x x))
g [\f. \n. IFTHENELSE (ISZERO n) (SUCC 0) (+ n (f ( PRED n)) )] = \f.\n.n (\x.FALSE) TRUE 1 (\i0.\x.n i0 (f [\i1.\i2.n (\g.\h.h (g i1)) (\u.i2) (\u.u)] i0 x))
h [\f. \n. IFTHENELSE (ISZERO n) (SUCC 0) (@ n (f ( PRED n)) )] = \f.\n.n (\x.FALSE) TRUE 1 (@ n (f [\i0.\x.n (\g.\h.h (g i0)) (\u.x) (\u.u)]))

既然談『λ 運算』表達式，如果不講『遞迴』函式；就彷彿是人到了『巴黎』，卻又沒見着『艾菲爾鐵塔』。之前在《自我再現》中提到函數 $f$ 之『定點』的定義是 $x = f(x)$ ，此時 $x = f^n(x)$ 。然而『 λ 表達式』無法『直接』的『自我指涉』。有人問為什麼呢？回顧一下它的『定義』，每一個寫出來的表達式都是『匿名的』，如果連『名字』都沒有，又怎麼能夠『指涉其名』的呢？所以只能『迂迴』的『間接』透過其它函式來『指涉』所說的就是那個『匿名的□□』。就像『自我應用』組合子，在函式應用時，可以產生『自我作用』一樣。著名的哈斯凱爾‧卡瑞 Haskell Brooks Curry ── 組合邏輯的發展者，Haskell 與 Brooks 程式語言都用他的名字來命名 ──，發現了『 $Y$ 』組合子，現今稱作『Curry 之悖論組合子』。為什麼要叫做『悖論』的呢？因為『自我指涉』恐怕會產生『羅素悖論』之故！但是『 $Y$ 組合子』雖可能會『陷入』無窮推導，卻沒有『矛盾』，它的一個特性，就是使用『 λ 表達式』做『遞迴的關鍵』︰

$(Y \ g) \equiv_{\beta} (g \ ( Y \ g))$

，比對『定點』的定義，就可以知道函式應用 $(Y \ g)$ 是變元函式 $g$ 的『定點函式』，也就是說『藉著 $Y$ 』，將一個命名的變元函式 $g$ 轉成了『自我調用』。為了避免 $g$ 的『無窮推導』，就像數學裡『迴歸定義』一樣，總要有一個『中止條件』。假使

$r =_{df} \lambda f. \lambda n. IFTHENELSE \ (ISZERO \ n) \ (n_0) \ (\bigotimes n \ (f \ ( PRED \ n)))$

，如果定義的自然數二元運算 $\bigotimes$ 類似具有『加法』或『乘法』的性質， $r \ (Y \ r) \ n$ 的結果就是

$\bigotimes \ n \bigotimes (n-1) \cdots \bigotimes \ 1 \ n_0$

，這個 $r$ 就是使用『 λ 表達式』寫作『遞迴函式』的一般範例，而 $n_0$ 就是『中止條件』的化約『傳回值』。

圖一

圖二

圖三

由於 Lambda Calculator 預設的『最大化約步驟』是兩百步，所以作者沒有給『階乘』 $n!$ 的例子，讀者可以自己寫。左圖一是『字典表列』中有的 $g$ ，它是『連加法』，中止條件是 $SUCC \ 0 = 1$ ，所以 $g \ (Y \ g) \ 3$ 的計算結果是 $3 + 2 + 1 + 1 = 7$ 。

左圖二中叫做『 $h$ 』的其實就是那個『 $r$ 』，它的中止條件是 $SUCC \ 0 = 1$ ，並將二元運算符號由 $\bigotimes$ 改成了『@』。為什麼『初始值』都不用『0』的呢？其實這樣做是為了『測試』演算法，有沒有『打錯字』以及『0』的表達式有『多義性』而考慮的。

左圖三計算 $(z\ (Y \ z) \ 3)$ ， $z$ 函式如同上面的 $g$ 函式一樣，但是它的初始值就是『0』。

傳說中講『西楚霸王』項羽，不只是『力拔山兮，氣蓋世！』，更神奇的是︰自己還能『舉起自己』，但是依據『牛頓作用反作用力定律』這是『可能』的嗎？？

樹莓派、樹莓派之學習、樹莓派之教育

λ 運算︰計物數《中》

2014-09-02 懸鉤子

【越調】天淨沙‧秋思
元 馬致遠

枯籐老樹昏鴉，
小橋流水人家，
古道西風瘦馬。
夕陽西下，
斷腸人在天涯。

繪畫、照片與書法是哪種比較『寫實』？哪個又較為『抽象』？《秋思》中用具象《『藤』、『樹』、『鴉』》，來虛寫『時光變化』之《『枯』、『老』、『昏』》；以實景《『橋』、『水』、『家』》，將串成『應歸之所』的《『小』、『流』、『人』》；終至於『道』得『古』、『風』是『西』、『馬』又怎能不『廋』？此刻也許只該是『夕陽西下』？？否則哪歸結的出『胡不歸去』之『斷腸人在天涯』！！

或許『失重』的『實物』漂浮於天之涯海之角，反而更顯得『虛幻』的了！！而『抽象』的『圖形』一旦擬似具體構物，或會因『沈重』終將失去『空靈』的嗎？？

在《啃一塊唄 K TCPIP！！下》一文中，我們談到『TCP/IP』規範堆疊的『層層包裹』，目的是為了方便寫程式的人，無須理會太多『具體詳細』的『實作』，這能減少程式的『複雜度』，也使得它容易『分層除錯』。也就是說計算機科學中一般所謂的『抽象化』Abstraction 是一種『程序』與『資料』的『封裝』方式，使用該程序或資料的人透過封裝之『應用界面』的『用法說明』來調用，不必知道『那裡頭是怎麼作的』。這麼說來這個『抽象的目的』反倒是為了『實用性』的了！！

就讓我們進入邱奇數的『抽象世界』稍稍『領略』一下到底如何建構這個『抽象物』的系統的呢？首先我們列出幾個上一篇中定義的邱奇自然數︰

0 [\f.\x.x] = \f.\x.x
1 [SUCC 0] = \f.\x.f x
2 [SUCC 1] = \f.\x.f (f x)
3 [SUCC 2] = \f.\x.f (f (f x))
4 [SUCC 3] = \f.\x.f (f (f [f x]))
…

，它是一個有兩個輸入變元 $f, x$ 的函式，對於自然數 $n$ 的結構也許可以簡潔點的表達為

$n =_{df} \lambda f. \lambda x. \ f^n \ x$

，也就是說變元 $x$ 為變元函式 $f$ 應用 $n$ 次。那麼

$(n \ \Diamond \ \tau \equiv_{\beta} \Diamond^n(\tau))$

，就是『自然數 $n$ 之函式』針對變元 $f$ 替換為 $\Diamond$ ，變元 $x$ 替換為 $\tau$ 的化約求值，這時它已經沒有輸入變元 $f, x$ 的了。這有什麼重要的嗎？由於我們只能夠使用函式『應用』來『解封』函式，比方說要怎麼樣才能得到 $\lambda x. M$ 中的『運算規則』 $M$ 的呢？難道不能用 $((\lambda x. M) x) \equiv_{\beta} M$ 的嗎？這就是『解讀』SUCC 定義的關鍵，它使用 $(n \ f \ x)$ 『解封』輸入的自然數變元 $n$ ，然後再用變元 $f, x$ 將多作一次 $f$ 的結果『封裝』起來成為自然數 $n+1$ ︰

$(\lambda n. \lambda f. \lambda x. f \ (n \ f \ x)) n$
$\equiv_{\beta} \lambda f. \lambda x. f \ (n \ f \ x))$
$\equiv_{\beta} \lambda f. \lambda x. f \ f^n \ x$
$\equiv_{\beta} \lambda f. \lambda x. f^{n+1} \ x$

，因此 SUCC 之所以用 $f \ (n \ f \ x)$ 的結構，它的目的是十分自然清楚，因為所謂的『後繼數』需要多一個 $f$ 。

從數學的角度上來看，如果知道怎麼作『 $n + 1$ 』，那麼所謂的『 $n+m$ 』就是將『 $+ 1$ 』作 $m$ 次，於是

$ADD =_{df} \lambda n. \lambda m. \ m \ SUCC \ n$

$ADD \ n \ m$
$\equiv_{\beta} (\lambda n. \lambda m. \ m \ SUCC \ n) \ n \ m$
$\equiv_{\beta} m \ SUCC \ n$
$\equiv_{\beta} ( \lambda f. \lambda x. \ f^m \ x) \ SUCC \ n$
$\equiv_{\beta} SUCC^m \ n$

就是它的程式設計『實作』。

左上圖是『ADD 3 2』的化約過程，而上一篇中的『 + 』的定義

$\lambda m. \lambda n. \lambda f. \lambda x. \ m \ f (n \ f \ x)$

並不是『間接』使用『後繼數』作法，而是將該作法結構 $f (n \ f \ x)$ 『直接』利用，可以看成是將加法程式作『最佳化』，左下圖是它的化約過程，讀者可以自行比較。

一個『演算法』當然最好能夠既『清晰』易解，又『執行』快速，然而當這兩方『不可兼得』的時候，也許需要考慮『硬體限制』與『應用目的』才能作『取捨』的吧！

再從數學的角度上來講，假使我們已經知道了兩個數的『加法』，那麼『乘法』 $m \ \times \ n$ 就是將 $0$ 加上 $n$ 作 $m$ 次。也就是說 $m \ \times \ n = (0 + n) \times m = 0 + n \cdots m \ times \cdots + n$ ，於是我們可以將『乘法』寫成︰

$MULT =_{df} \lambda m. \lambda n. \ m \ (ADD \ n) \ 0$

$MULT \ m \ n$
$\equiv_{\beta} m \ (ADD \ n) \ 0$
$\equiv_{\beta} ( \lambda f. \lambda x. \ f^m \ x) \ (ADD \ n) \ 0$
$\equiv_{\beta}{ (ADD \ n) }^m \ 0$

左圖是『MULT 3 2』的 $\beta$ 化約過程。

由於邱奇自然數是一種稱之為『高階函式』Higher-order function 的構造，所以『算術加乘』的定義也就在泛函式的運作下來考量。數學上的『對等的表達式』是很有用的『實作』方向『指引』。或許『玩 λ 運算』未必會『喪志』，過程中的『樂趣』也許正在於『思考』之『苦惱』以及『表達』的『困難』。

佛經上有言︰煩惱即菩提！！

─── 待續… λ 運算︰計物數《下》───

樹莓派、樹莓派之學習、樹莓派之教育

λ 運算︰計物數《上》

2014-09-01 懸鉤子

韓信點兵多多益善

『孫子算經』的作者不知何許人也，成書的年代不詳，一些學者根據書中事物發生的時間來看，約是在魏晉南北朝，距今已超過一千五百年了。

《卷下‧第三十一題》︰雞兔同籠問題的始祖

今有雉、兔同籠，上有三十五頭，下九十四足。問雉、兔各幾何？
答曰：雉二十三。兔一十二。
術曰：上置三十五頭，下置九十四足。半其足，得四十七。以少減多，再命之，上三除下三，上五除下五。下有一除上一，下有二除上二，即得。
又術曰：上置頭，下置足。半其足，以頭除足，以足除頭，即得。

《卷下‧第二十六題》︰中國餘數定理

今有物，不知其數。三、三數之，賸二；五、五數之，賸三；七、七數之，賸二。問物幾何？
答曰：二十三。
術曰：「三、三數之，賸二」，置一百四十；「五、五數之，賸三」，置六十三；「七、七數之，賸二」，置三十。并之，得二百三十三。以二百一十減之，即得。凡三、三數之，賸一，則置七十；五，五數之，賸一，則置二十一；七、七數之，賸一，則置十五。一百六以上，以一百五減之，即得。

【孫子歌】

三人同行七十稀，
五樹梅花廿一枝，
七子團圓正半月，
除百零五便得知。

《孫子算經‧序》孫子曰：

夫算者，天地之經緯，群生之元首；五常之本末，陰陽之父母；星辰之建號，三光之表裹；五行之準平，四時之終始；萬物之祖宗，六藝之綱紀。稽群倫之聚散，考二氣之降升；推寒暑之迭運，步遠近之殊同；觀天道精微之兆基，察地理從橫之長短；采神祇之所在，極成敗之符驗；窮道德之理，究性命之情。立規矩，準方圓，謹法度，約尺丈，立權衡，平重輕，剖毫釐，析黍絫；歷億載而不朽，施八極而無疆。散之不可勝究，斂之不盈掌握。嚮之者富有餘，背之者貧且窶；心開者幼沖而即悟，意閉者皓首而難精。夫欲學之者必務量能揆己，志在所專。如是則焉有不成者哉。

南宋時的數學家秦九韶著作《數書九章》內有『大衍求一術』，正好用來『解詩』，『七十』除三餘一，卻為『五、七』整除；『二十一』除五餘一，卻為『三、七』整除；『十五』除七餘一，卻為『三、五』整除；三數的最小公倍數『三乘五乘七』是為『百零五』，所以答案是 $105 \times n + 1$ 。『科技』與『人文』難道一定是『南轅北轍』不能『對話共歌』的嗎？？

義大利的數學家朱塞佩‧皮亞諾 Giuseppe Peano 提出『自然數』之五條公設的系統。用著『未定義』的『基元』數『零 $0$ 』，以及『後繼數』successor 的概念，打造了一階算術系統，現今稱之為『皮亞諾算術系統』︰

一、 $0$ 是自然數。
二、如果 $n$ 是自然數，則 $n$ 的後繼數也是自然數。
三、 $0$ 不是任何自然數的後繼數。
四、如果兩個自然數的後繼數相等，則這兩個自然數相等。
五、任何關於自然數的命題，假使證明了這個命題對於自然數 $0$ 是真的，如果它對自然數 $n$ 為真時，又可以證明它對 $n$ 後繼數也真，那麼這個命題對所有的自然數都是真的── 數學歸納法 ──。

於是可以將皮亞諾算術表達成︰此處 $S$ 代表某數之後繼數

$\forall n (Sn \neq 0)$
$\forall m, n ((Sm = Sn) \Rightarrow m = n)$
$\varphi[0] \wedge \forall n \ (\varphi[n]\Rightarrow\varphi[Sn]) \Rightarrow \forall n \ (\varphi[n])$ ，就是數學歸納法
$\forall n (n + 0 = n)$
$\forall m, n(m + Sn = S(m + n))$
$\forall n (n \cdot 0 = 0)$
$\forall m, n (m \cdot Sn = (m \cdot n) + m)$

唐賈島《尋隱者不遇》
松下問童子，
言師採藥去。
只在此山中，
雲深不知處。

果真身緣此山中，不識廬山真面目！！

皮亞諾將『算術』公設化變成了祇有『零』、『後繼數』以及『相等』三個關於『計物數』之『基本』的『概念』。抽象了的『自然數』是否一樣『自然』，能如『骨牌』從『零』開始，一個推倒一個以至於『無窮』的嗎？？

自從坎特爾用『集合論』將『數是什麼』以『一對一』『函數』來說明『有限集合』的『元素數目相等』概念之時，目的是通向『無限大』的『詮釋』，然而這使得人們重新發現『數ㄕㄨˇ數ㄕㄨˋ』的概念原來並非是『那麼簡單』。一八八九年皮亞諾所寫之《算術原理：用一種新方法的說明》的書開啟了自然數公設化的先河。或許這就是邱奇之所以會用著『一一對應』的方式，創造了一種將整體『自然數』都給『編碼』encode 成了『 λ函式』的方法。在此為了避免『歷史事實』的爭議，就讓我們先拋掉所謂的『自然數』是不是該『始於一』之『歷史包袱』吧！也許簡單假設它是『起於無』的吧！由於『 λ 表達式』中根本就沒有『數』的『概念』，只有『變元』、『函式』和『應用』與可以『運用』，因此將『計物』比擬成『記點函式』應用於『所數之物』，彷彿用指點著它『一個一個』的數，『指點幾次』就是『該物之數』也是很自然的吧！！這樣我們就可以在『純 λ語言』裡『定義』邱奇數 ── 皮亞諾自然數的編碼 ──，是︰

一、 $0 =_{df} \lambda f. \lambda x. x$ ，零
二、 $SUCC =_{df} \lambda n. \lambda f. \lambda x. (n \ f \ x)$ ，後繼數產生方法
三、 $n =_{df} SUCC ( SUCC \cdots (SUCC \ 0))$ ，某數 $n$

。假使你將『第一條』與『第二條』輸入設定為『純 λ 運算』且沒有『 $\eta$ 變換』的 Lambda Calculator，然後用著『逐次逐個』的方式定義『 $1, 2, 3, \cdots, 9, \cdots$ 』，你會得到︰

0 [\f.\x.x] = \f.\x.x
1 [SUCC 0] = \f.\x.f x
2 [SUCC 1] = \f.\x.f (f x)
3 [SUCC 2] = \f.\x.f (f (f x))
4 [SUCC 3] = \f.\x.f (f (f [f x]))
5 [SUCC 4] = \f.\x.f (f (f [f (f x)]))
6 [SUCC 5] = \f.\x.f (f (f [f (f (f x))]))
7 [SUCC 6] = \f.\x.f (f (f [f (f (f {f x}))]))
8 [SUCC 7] = \f.\x.f (f (f [f (f (f {f (f x)}))]))
9 [SUCC 8] = \f.\x.f (f (f [f (f (f {f (f (f x))}))]))
…

假使將 $f$ 詮釋成的『作記號函式』── 在『物上作《 . 》記號』──，這樣 $SUCC$ 就是調用『作記號函式』針對『當下物』 $x$ 多作『一次』記號。由於這是『一一對應』的『記點』作法，那麼『物之數』自然就會『相等』於『做了幾次記號』的函式。難到這樣當真是『可行』的嗎？這一種『鏡花水月』的『定義』方式就已經能夠產生『算術』的了嗎？？

忘了誰說的︰檢驗是測試『真理』唯一的『辦法』。不如看看能否定義一個『計算之始』的簡單『加法』︰

+ [\m.\n.\f.\x.m f (n f x)] = \m.\n.\f.\x.m f (n f x)

，計算一個容易的『 $+ \ 3 \ 2$ 』，左圖是該式子『 λ 運算』化約的『推導過程』。

終究什麼是『數字』Number 呢？什麼又是『資料』Data 勒？？更別說這早已經是『雲端大數據』的時代了！！

─── 待續… λ 運算︰計物數《中》───

日	一	二	三	四	五	六
« 8 月				10 月 »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

FreeSandal

每月彙整: 2014 年 9 月

輪扁斲輪？！

λ 運算︰計物數《遞迴補遺》

λ 運算︰計物數《下》

λ 運算︰計物數《中》

λ 運算︰計物數《上》

輕。鬆。學。部落客