13 | 7 月 | 2015 | FreeSandal

為了釐清一些關鍵要點，就讓我們從

文中之『河內塔』Towers of Hanoi 的故事開始。

莊子．齊物論

物無非彼，物無非是。自彼則不見，自知則知之。故曰：彼出於是，是亦因彼。彼是，方生之說也。雖然，方生方死，方死方生；方可方不可，方不可方可；因是因非，因非因是。是以聖人不由而照之於天，亦因是也。是亦彼也，彼亦是也。彼亦一是非，此亦一是非。果且有彼是乎哉？果且無彼是乎哉？彼是莫得其偶，謂之道樞。樞始得其環中，以應無窮。是亦一無窮，非亦一無窮也。故曰莫若以明 。

一八八三年法國數學家 Édouard Lucas 講了一個傳說︰

印度梵天寺有『成、住、壞』三根柱子，成柱上串有側見從上往下是由小到大的六十四個金盤子，寺院裡的僧侶必須按照一個古老的預言，預言裡面有宣示的規矩，將成柱上的這些金盤子，大的不能放在小的之上，一次又只能動一柱之最上的一個金盤，或可藉或不藉著它柱，移往壞柱，一旦依法奉行完成，世界就會空亡。

於是其後有人問到依照預言『這個世界多久就會毀滅』？作者並不知道梵天寺之『浮屠』── 塔 ──的傳說是否真實？然而如果想要回答那個問題，得要先談談『遞迴』Recursion 一事，就讓我們先從『數學歸納法』說起吧！

事實上數學歸納法並不是個歸納法，而是個演繹法，它有多種版本變化，這裡講的是普通的一種︰

比方說有若干事件 Event ，讓我們依序排列成
$E_1$ ， $E_2$ ，…， $E_k$ ，…， $E_n$ ， $E_{n+1}$
，已知
第一點， $E_1$ 事件是真的
第二點，假使 $E_n$ 事件是真的，可以邏輯導出 $E_{n+1}$ 事件也是真的
，那麼結論是所有的這些事件都是真的。

在數學裡，數學歸納法很常見，不只經常用來『證明』問題，還可以用來『定義』遞迴性的東西。舉例說『階乘』factorial 可以這樣
定義
0!=1
1!=1
…
n!= n * (n-1)!

。這種方式的好處是什麼呢？它從已知的推向未知的，由已會算的導往還不會算的，彰顯遞迴結構的『核心』，又很簡約所以容易掌握！現在就讓我們分析一下那個傳說的預言── 別稱『河內塔』──的問題

第一條、假如『成』柱上只有一個金盤子，直接將它移至『壞』柱就完成了

第二條、如果『成』柱上有 n + 1 個金盤子，先將上面 n 個移至『住』柱，再將最後一個移至『壞』柱

第三條、最後將『住』柱上的 n 個金盤子，移至『壞』柱

，這三條思路，使我們知道從怎麽處理『一』個金盤子，到處理『二』個金盤子，然後能處理『三』個金盤子，……，以致最終能處理『任意』個金盤子。所以說如果處理 n 個金盤子需要 $S_n$ 步次，那麼就會有這樣子的關係式

$S_{n+1}$ = $S_n$ + 1 + $S_n$

，如果我們將這個式子改寫成

$S_{n+1}$ + 1 = 2 * ( $S_n$ + 1 )

，它變成一個以 2 為倍數的等比級數，所以得到 $S_n$ = $2^n$ – 1。

據《摩訶僧祇律十七》︰則謂

『二十念名為一瞬頃，二十瞬名為一彈指，二十彈指名為一羅豫，二十羅豫名為一須臾，日極長時，有十八須臾，夜極短時，有十二須臾，夜極長時，有十八須臾，日極短時，有十二須臾。』此即一晝夜為三十須臾，一須臾二十分為一羅豫，一羅豫二十分為一彈指，一彈指二十分為一瞬，一瞬二十分即為一念之說也。又《華嚴探玄記十八》謂剎那茲云念頃，一彈指頃有六十剎那。

意思是說一天有二十四個小時是三十個『須臾』＝六百個『羅豫』＝一萬兩千個『彈指』＝七十二萬個『剎那』，所以一剎那是 86400 /720000 = 0.12 秒。那也就是說 $2^{64}$ – 1 的數字之大，即使『念頭』一轉就能移動一個金盤子，『這個世界要毀滅』還得要超過七百億年的時間才有可能！！

……

為了演示『河內塔』的『遞迴結構』，首先作者引用並且改寫了《Towers of Hanoi 》文本中的 hanoi python 程式，希望能更方便閱讀。由於用『串列』 list 來模擬金盤子由小到大的『堆疊』，因為『pop』與『append』作用於『串列』的『尾』部，即『堆疊』之『頂』部。故而『串列』的『頭』部，是『堆疊』之『底』部。這正是

來源柱 = ([‘大’,’中’,’小’], “成柱”)

寫法之原故。

>>> def 河內塔(金盤子數,來源柱,助柱,目的柱):
...     print("河內塔(", 金盤子數,來源柱,助柱,目的柱, "被呼叫")
...     if 金盤子數 > 0:
...         河內塔(金盤子數 - 1,來源柱,目的柱,助柱)
...         if 來源柱[0]:
...             金盤子 = 來源柱[0].pop()
...             print("移動 " + str(金盤子) + " 從 " + 來源柱[1] + " 至 " + 目的 柱[1])
...             目的柱[0].append(金盤子)
...         河內塔(金盤子數 - 1, 助柱,來源柱,目的柱)
... 
>>> 來源柱 = (['大','中','小'], "成柱")
>>> 助柱 = ([], "住柱")
>>> 目的柱 = ([], "壞柱")
>>> 河內塔(len(來源柱[0]), 來源柱, 助柱, 目的柱)
河內塔( 3 (['大', '中', '小'], '成柱') ([], '住柱') ([], '壞柱') 被呼叫
河內塔( 2 (['大', '中', '小'], '成柱') ([], '壞柱') ([], '住柱') 被呼叫
河內塔( 1 (['大', '中', '小'], '成柱') ([], '住柱') ([], '壞柱') 被呼叫
河內塔( 0 (['大', '中', '小'], '成柱') ([], '壞柱') ([], '住柱') 被呼叫
移動 小 從 成柱 至 壞柱
河內塔( 0 ([], '住柱') (['大', '中'], '成柱') (['小'], '壞柱') 被呼叫
移動 中 從 成柱 至 住柱
河內塔( 1 (['小'], '壞柱') (['大'], '成柱') (['中'], '住柱') 被呼叫
河內塔( 0 (['小'], '壞柱') (['中'], '住柱') (['大'], '成柱') 被呼叫
移動 小 從 壞柱 至 住柱
河內塔( 0 (['大'], '成柱') ([], '壞柱') (['中', '小'], '住柱') 被呼叫
移動 大 從 成柱 至 壞柱
河內塔( 2 (['中', '小'], '住柱') ([], '成柱') (['大'], '壞柱') 被呼叫
河內塔( 1 (['中', '小'], '住柱') (['大'], '壞柱') ([], '成柱') 被呼叫
河內塔( 0 (['中', '小'], '住柱') ([], '成柱') (['大'], '壞柱') 被呼叫
移動 小 從 住柱 至 成柱
河內塔( 0 (['大'], '壞柱') (['中'], '住柱') (['小'], '成柱') 被呼叫
移動 中 從 住柱 至 壞柱
河內塔( 1 (['小'], '成柱') ([], '住柱') (['大', '中'], '壞柱') 被呼叫
河內塔( 0 (['小'], '成柱') (['大', '中'], '壞柱') ([], '住柱') 被呼叫
移動 小 從 成柱 至 壞柱
河內塔( 0 ([], '住柱') ([], '成柱') (['大', '中', '小'], '壞柱') 被呼叫
>>> 
>>> print(來源柱, 助柱, 目的柱)
([], '成柱') ([], '住柱') (['大', '中', '小'], '壞柱')
>>>

如果讀者試著用『紙、筆』追跡河內塔程式的『呼叫過程』，將會有很多收穫。假使再考察『呼叫參數』、『遞迴次序』以及此時『變元標識符』之『所指』，或許更能明白遞迴函式『終止條件』

金盤子數 > 0

的作用。如此或將能解釋為什麼多了一個金盤子，柱與柱之間的『移動方式』有很大的不同！看出『遞迴結構』

河內塔(金盤子數 – 1,來源柱,目的柱,助柱)

河內塔(金盤子數 – 1, 助柱,來源柱,目的柱)

之『對應』且『依序而行』的關係！！

>>> 來源柱 = (['超','大','中','小'], "成柱")
>>> 助柱 = ([], "住柱")
>>> 目的柱 = ([], "壞柱")
>>> 河內塔(len(來源柱[0]), 來源柱, 助柱, 目的柱)
河內塔( 4 (['超', '大', '中', '小'], '成柱') ([], '住柱') ([], '壞柱') 被呼叫
河內塔( 3 (['超', '大', '中', '小'], '成柱') ([], '壞柱') ([], '住柱') 被呼叫
河內塔( 2 (['超', '大', '中', '小'], '成柱') ([], '住柱') ([], '壞柱') 被呼叫
河內塔( 1 (['超', '大', '中', '小'], '成柱') ([], '壞柱') ([], '住柱') 被呼叫
河內塔( 0 (['超', '大', '中', '小'], '成柱') ([], '住柱') ([], '壞柱') 被呼叫
移動 小 從 成柱 至 住柱
河內塔( 0 ([], '壞柱') (['超', '大', '中'], '成柱') (['小'], '住柱') 被呼叫
移動 中 從 成柱 至 壞柱
河內塔( 1 (['小'], '住柱') (['超', '大'], '成柱') (['中'], '壞柱') 被呼叫
河內塔( 0 (['小'], '住柱') (['中'], '壞柱') (['超', '大'], '成柱') 被呼叫
移動 小 從 住柱 至 壞柱
河內塔( 0 (['超', '大'], '成柱') ([], '住柱') (['中', '小'], '壞柱') 被呼叫
移動 大 從 成柱 至 住柱
河內塔( 2 (['中', '小'], '壞柱') (['超'], '成柱') (['大'], '住柱') 被呼叫
河內塔( 1 (['中', '小'], '壞柱') (['大'], '住柱') (['超'], '成柱') 被呼叫
河內塔( 0 (['中', '小'], '壞柱') (['超'], '成柱') (['大'], '住柱') 被呼叫
移動 小 從 壞柱 至 成柱
河內塔( 0 (['大'], '住柱') (['中'], '壞柱') (['超', '小'], '成柱') 被呼叫
移動 中 從 壞柱 至 住柱
河內塔( 1 (['超', '小'], '成柱') ([], '壞柱') (['大', '中'], '住柱') 被呼叫
河內塔( 0 (['超', '小'], '成柱') (['大', '中'], '住柱') ([], '壞柱') 被呼叫
移動 小 從 成柱 至 住柱
河內塔( 0 ([], '壞柱') (['超'], '成柱') (['大', '中', '小'], '住柱') 被呼叫
移動 超 從 成柱 至 壞柱
河內塔( 3 (['大', '中', '小'], '住柱') ([], '成柱') (['超'], '壞柱') 被呼叫
河內塔( 2 (['大', '中', '小'], '住柱') (['超'], '壞柱') ([], '成柱') 被呼叫
河內塔( 1 (['大', '中', '小'], '住柱') ([], '成柱') (['超'], '壞柱') 被呼叫
河內塔( 0 (['大', '中', '小'], '住柱') (['超'], '壞柱') ([], '成柱') 被呼叫
移動 小 從 住柱 至 壞柱
河內塔( 0 ([], '成柱') (['大', '中'], '住柱') (['超', '小'], '壞柱') 被呼叫
移動 中 從 住柱 至 成柱
河內塔( 1 (['超', '小'], '壞柱') (['大'], '住柱') (['中'], '成柱') 被呼叫
河內塔( 0 (['超', '小'], '壞柱') (['中'], '成柱') (['大'], '住柱') 被呼叫
移動 小 從 壞柱 至 成柱
河內塔( 0 (['大'], '住柱') (['超'], '壞柱') (['中', '小'], '成柱') 被呼叫
移動 大 從 住柱 至 壞柱
河內塔( 2 (['中', '小'], '成柱') ([], '住柱') (['超', '大'], '壞柱') 被呼叫
河內塔( 1 (['中', '小'], '成柱') (['超', '大'], '壞柱') ([], '住柱') 被呼叫
河內塔( 0 (['中', '小'], '成柱') ([], '住柱') (['超', '大'], '壞柱') 被呼叫
移動 小 從 成柱 至 住柱
河內塔( 0 (['超', '大'], '壞柱') (['中'], '成柱') (['小'], '住柱') 被呼叫
移動 中 從 成柱 至 壞柱
河內塔( 1 (['小'], '住柱') ([], '成柱') (['超', '大', '中'], '壞柱') 被呼叫
河內塔( 0 (['小'], '住柱') (['超', '大', '中'], '壞柱') ([], '成柱') 被呼叫
移動 小 從 住柱 至 壞柱
河內塔( 0 ([], '成柱') ([], '住柱') (['超', '大', '中', '小'], '壞柱') 被呼叫
>>> print(來源柱, 助柱, 目的柱)
([], '成柱') ([], '住柱') (['超', '大', '中', '小'], '壞柱')
>>>

那麼我們用『pyDatalog』寫作『類似』河內塔一般的『遞迴結構』時，為什麼會得到如下的結果呢？

【※注意此處攔截了 python 語言的 print 函式，請參閱 pydatalog 之 Advanced topics 】

pi@raspberrypi ~ $ python3
Python 3.2.3 (default, Mar  1 2013, 11:53:50) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from pyDatalog import pyDatalog
>>> pyDatalog.create_terms('mv,ok,N,X,Y,Z,P,print')

# 定義『移動完成』的『基本事實』
>>> +ok(0)

# 嘗試最核心的遞迴結構
>>> mv(N) <= (N > 0) & mv(N-1) & (P == print(N)) & mv(N -1)
mv(N) <= >(N,'0')&mv((N-'1'))&==(P,('<built-in fun

>>> mv(0) <= ok(0)
mv('0') <= ok('0')

# 輸出結果，似乎只跑了一半？
>>> mv(3)
3
2
1
0
[()]

# 類似河內塔的遞迴結構
>>> pyDatalog.create_terms('move')
>>> move(N,X,Y,Z) <= (N > 0) & move(N-1,X,Z,Y) & (P == print(N,X,Y,Z)) & move(N -1 ,Y,X,Z)
move(N,X,Y,Z) <= >(N,'0')&move((N-'1'),X,Z,Y)&==(P

#
>>> move(0,X,Y,Z) <= ok(0)
move('0',X,Y,Z) <= ok('0')

#
>>> move(3,"A","B","C")
3 A B C
2 A C B
1 A B C
0 A C B
0 B A C
1 C A B
0 C B A
2 B A C
1 B C A
[()]

# 不同寫法
>>> pyDatalog.create_terms('M,move1')
>>> move1(N,X,Y,Z) <= (N > 0) & (M == N -1) & move1(M,X,Z,Y) & (P == print(N,M,X,Y,Z)) & move1(M ,Y,X,Z)
move1(N,X,Y,Z) <= >(N,'0')&==(M,(N-'1'))&move1(M,X

#
>>> move1(0,X,Y,Z) <= ok(0)
move1('0',X,Y,Z) <= ok('0')

#
>>> move1(3,"A","B","C")3 2 A B C
2 1 A C B
1 0 A B C
1 0 C A B
2 1 B A C
1 0 B C A
[()]
>>>

此時我們將會對 pyDatalog 的核心技術之說明有更深一層的了解︰

Core technology

Core technology in pyDatalog	Benefits	Sample applications
The resolution engine determines the best sequence of clauses to use to reach a goal	Spreadsheet-style programming : faster development; fewer bugs, easier to read afterwards	Rule-based models with many input and output, e.g. expert system for price calculation or tax planning, access right management, robot control, intelligent agent in games or automated assistants
The resolution engine can resolve recursive algorithm	Easy to write queries on hierarchical structure	Reporting with hierarchical reference data such as organisational structure
The same clause can solve various mixes of known and unknown parameters	Maximize code reuse : shorter program, simpler query language than SQL	Cross-database queries, data integration
Intermediate results are memoized.	Improved speed by avoiding duplicate work.	Business logic in 3-tier architecture.

一個『邏輯編程』語言追求

‧ 純陳述性

‧ 效能性

‧ 記憶中間結果

‧ 自動決定最佳『子句序列』

‧ ……

對於那些依賴『次序性』、『變元結構』、『狀態相關』、…等等的『演算法』未必能有個合適的『控制程序』，這或許也就是所謂的『領域性』語言之本義。

日	一	二	三	四	五	六
« 6 月				8 月 »
			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	31

FreeSandal

每日彙整: 2015-07-13

勇闖新世界︰《 pyDatalog 》導引《七》……

Core technology

輕。鬆。學。部落客