每日彙整: 2014-09-07

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

樹莓 λ 者 Lisps

220px-Lisplogo_alien_256

“Lisp has jokingly been called “the most intelligent way to misuse a computer”. I think that description is a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.” — Edsger Dijkstra, CACM, 15:10

一九五四年美國艾倫‧紐厄爾 Allen Newell、克里夫‧蕭 Cliff Shaw 和赫伯特‧西蒙 Herbert Alexander Simon 等人於蘭德公司與卡內基技術學院研發了資訊處理語言 IPL Information Processing Language 。它以『圖靈測試』為目標，被認為是史上第一個用於『人工智慧』── 『符號演算』系統可以衍生出智慧 ── 領域的語言，首先使用了『串列』 Link List 結構與『遞迴』，啟發了之後『Lisp』的發展。一九五八年約翰‧麥卡錫 John McCarthy ── 在一九五五年的達特矛斯會議上提出了『人工智慧』這個概念── 於麻省理工學院發明了 Lisp 這個程式語言。其中採用了 IPL 語言的特徵。一九六零年麥卡錫在《ACM 通訊》上發表了一篇名為《遞迴函式的符號表達式以及由機器運算的方式，第一部》 Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I 之論文。在這篇論文中，他展示了只要透過一些簡單的運算子以及函式的記號法，也就可以建立一個具有『圖靈完備性』的 λ 演算法語言。約翰‧麥卡錫的學生史帝芬‧羅素 Steve Russell ── 著名程式設計師與計算機科學家，曾在 PDP-1 上創造了第一個電子遊戲 Spacewar ！ ── 在閱讀完此論文後，認為 Lisp 程式語言當中的『eval 函式』可以用『機器碼』來實做。他於是在IBM 704 機器上，完成了第一個 LISP 『解譯器』 Interpreter。Lisp 的名稱來自於『串列處理器』 List Processor 之縮寫，最初拼寫為『LI SP』，是一個僅次於 Fortran 語言之歷史悠久的泛函式計算機程式語言，以『波蘭表示法』編程，擁有多種方言家族。

在計算機科學中，『資料結構』 data structure 是電腦中『儲存』 與『組織』資料的方式，通常『精心設計』或者是『擇優選取』的資料結構是可以產生執行速度『最佳化』之演算法。

408px-Singly-linked-list.svg

『串列』 Linked list 是一種基礎的資料結構，它是一種『線性』的資料鏈接，是在每一個『資料節點』裡有指向下一個『資料節點』的『指標』Pointer。所以可以說它是一個『單向線性結構』的『資料容器』。假使你想要取得『第 n 項』的資料，你只能夠『從頭』一次一個的『向後』數到了『第 n - 1 個』，然後『再向後』一次，才能抵達那裡。

我們已經見識了『 λ表達式』可以定義『真假』與『自然數』這種『資料』和『資料操作』的例子，那麽它要如何定義『資料結構』的呢？就讓我們從數學上的『有序對』pair 開始，它是兩個對象的『聚集』collection，其中可以區分出一是『第一個物件』而另一是『第二個物件』，通常寫為 (a, b)。比方說『笛卡爾平面座標系』中的點 (x, y) 就是『定位座標』x 與 y 的聚集，它讓我們可以確定一個『點』在這個『面』上的位置。那麼我們要怎麽用 λ表達式『表徵』這樣的『概念』呢？比方講『杯子與水』，在前的物件是『杯』，在後的是『水』。假使從『操作』的觀點講，如果 『\Box =  (杯，水)』是一個有序對，有兩個取回『操作子』F, S

F(\Box) 是『第一個物件』，『杯』
S(\Box) 是『第二個物件』，『水』

，就算我們不知道真正 \Box 的『結構』是什麼？但它難道會與所謂的『有序對』之操作不一樣的嗎？？由於『(\Box, F, S)』── 資料封裝與資料存取方法 ── 所構成的系統是與『有序對概念』之系統『無法在操作上區分』，因此就將它『歸類』成為等效之抽象『有序對』的系統了，這個『等效』也就是所謂的『抽象資料型態』ADT  Abstract Data Type  的了！！也就是說如果我們定義了『建構有序對』、『取回第一個物件』以及『取回第二個物件』的方法函式，我們就得到了等效的『抽象有序對』。這在『 λ』裡可以定義如下︰

CONS =_{df} \lambda x. \lambda y. \lambda p. IFTHENELSE \ p \ x \ y，建構有序對
CAR =_{df} \lambda x. \ x \ TRUE，取回第一個物件
CDR =_{df} \lambda x. \ x \ FALSE，取回第二個物件

。在進入討論為什麼可以這樣定義之前，先說說這幾個『縮寫』的由來，摘引自 WiKi︰

Lisp was originally implemented on the IBM 704 computer, in the late 1950s. The 704 hardware had special support for splitting a 36-bit machine word into four parts, an “address part” and “decrement part” of 15 bits each and a “prefix part” and “tag part” of three bits each.

Precursors to Lisp included functions:

car (short for “Contents of the Address part of Register number”),
cdr (“Contents of the Decrement part of Register number”),
cpr (“Contents of the Prefix part of Register number”), and
ctr (“Contents of the Tag part of Register number”),

each of which took a machine address as an argument, loaded the corresponding word from memory, and extracted the appropriate bits.

The 704 assembler macro for cdr was

LXD JLOC,4
CLA 0,4
PDX 0,4
PXD 0,4

A machine word could be reassembled by cons, which took four arguments (a,d,p,t).

The prefix and tag parts were dropped in the early stages of Lisp’s design, leaving CAR, CDR, and a two-argument CONS.

就讓我們尊重這個歷史上 Lisp 命名的『傳統』吧！

CONS
圖一 CONS 化約

CONS-a-b
圖二 CONS a b 是 ((p \ a)\ b) 函式

CAR
圖三 CAR (CONS a b) = a

CDR
圖四 CDR (CONS a b) = b

由於『 λ系統』中沒有地方可以『儲存』物件，所以用函式封裝函式應用資料來『記憶』。比方說 ((F \ \Box) \ \bigcirc) 用函式 F 封裝 \Box 與 \bigcirc 兩個物件。所以『建構』Construct 『資料結構』函式，與對應的『存取』資料函式，需要一併考慮。因此『CONS』之所以用『IFTHENELSE』函式『封裝』物件 x, y，是想用變元函式 p 的『真假值』來取得『真時是 x』和『假時是 y』之結構。左圖一的化約與左圖二的『CONS \ a \ b』有序對 (a, b) 的產生，說明了這一件事。在《λ 運算︰概念導引之《補充》※真假祇是個選擇？？》一文中所談的『真假選擇』也就是『CAR』與『CDR』定義的『作用』。因此『CAR』賦與 p 函式『真值』以取回『有序對』的『第一個』物件；『CDR』賦與 p 函式『假值』以取回『有序對』的『第二個』物件。從這個角度講，也可以說『CAR』與『CDR』它們『解封』了『CONS』所『封裝』之『有序對』((p \ a)\ b)) 函式。讀者可以參考左圖三和左圖四的化約過程，了解整個運作的細節。

『真假』果然是個『選擇』！！『To Be or not To Be』 也始終是個『問題』？？

就讓我們試著將它應用於『平面格子點向量』幾何吧。以下是它的 Lambda Calculator 字典定義︰

CAR [\x. x TRUE] = \x.x TRUE
CDR [\x.x FALSE] = \x.x FALSE
CONS [\x. \y. \p. IFTHENELSE p x y] = \x.\y.\p.p x y

P0 [CONS 0 0] = \p.p FALSE FALSE
P1 [CONS 3 2] = \p.p 3 2
P2 [CONS 2 3] = \p.p 2 3
P3 [CONS 1 2] = \p.p 1 2
P4 [CONS 2 1] = \p.p 2 1

v* [\p. \q. (+ (* (CAR p) (CAR q) ) (* (CDR p) (CDR q) ) )] = \p.\q.\f.\x.p TRUE (\n.\i0.\i1.q TRUE i0 (n i0 i1)) FALSE f (p FALSE (\n.\i0.\i1.q FALSE i0 [n i0 i1]) FALSE f x)
v+ [\p. \q. CONS (+ (CAR p) (CAR q)) (+ (CDR p) (CDR q))] = \p.\q.\i0.i0 (\f.\x.p TRUE f (q TRUE f x)) (\f.\x.p FALSE f (q FALSE f x))

v+P3P2

v*P3P2

其中『v+』是『向量加法』v+ =_{df} (a, b) + (c, d) = (a + c, b + d)；『v*』是『向量內積』v+ =_{df} (a, b) \cdot (c, d) = a \times c + b \times d。

左圖是『v+ P3 P2』與『v* P3 P2』的化約顯示。讀者可以自己嘗試寫一些『有序對』的應用。發現『 λ 』魅力的緣由，體會所謂的『資料結構』、『演算法』以及『程式語言』到底是怎麼一回事。

408px-Singly-linked-list.svg

串列＝ (第一個物件，其餘物件)，其餘物件＝ (第一個物件，其餘之其餘物件)，其餘之其餘物件＝…，就是一個『有序對』的『俄羅斯娃娃』結構，它最終截止於無餘物之 (FALSE, FALSE)！！假使說

幸運的七＝df CONS 是 (CONS 誰 (CONS 偷 (CONS 了 (CONS 她 (CONS 的 (CONS 心 (CONS ？ (CONS FALSE FALSE))))))))

，那誰能用『CAR』與『CDR』幫她找回那顆『幸運的七』偷走的『心』嗎？

 

── 俗語講『鴨子聽雷』，祇是因為

雖『春江水暖鴨先知』，但由於牠『口語不清』 lisps ，

所以就彷彿是『對牛彈琴』！！──