勇闖新世界︰《 pyDatalog 》導引《八上》

2015-07-15 懸鉤子

二零一三年，PyCon 上有一個『競賽問題』︰

Pcarbonn 先生寫了兩個 pyDatalog 的程式︰

”’
Created on 2 avr. 2013

The HASHTAG problem was the subject of a contest at PyCon 2013.

Problem description : https://picasaweb.google.com/lh/photo/u_6ZWCrTUNVADkPAyyFvfKbReIcFkkE5l5WZw-QBbLc
Discussion : http://uthcode.appspot.com/2013/03/Hashtag-at-pycon

Below is a solution based on pyDatalog

@author: pcarbonn
”’

執行結果如下︰

《hashtag.py》

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, pyEngine
>>> import time
>>> pyDatalog.create_terms('solution,move,X,Y,Z, Path,Path1,Path2, Steps,Steps1,Steps2')

# valid moves are exchange of 1<->2, 1<->4, ... 
>>> @pyDatalog.predicate()
... def move3(X,N,Y):
...     for n1,n2 in ((0,1),(0,3),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)):
...         if X.id[n1]=='*' or X.id[n2]=='*':
...             y = list(X.id)
...             y[n1], y[n2] = y[n2], y[n1]
...             yield (X.id, '%s-%s,' % (n1+1, n2+1), ''.join(y))
... 

# a solution to go from X to Y is a direct move, 
# or a solution from X to Z, followed by a direct move from Z to Y
>>> (solution[X,Y]==(Steps,Path)) <= (  (solution[X,Z]==(Steps1,Path1)) & move(Z,Steps2,Y)
... )
solution[2]==(*,X,Y,'["('f', 'Steps')", "('f', 'Pa
>>> (solution[X,Y]==(Steps,Path)) <= (  (solution[X,Z]==(Steps1,Path1)) & move(Z,Steps2,Y) & (Path==Path1+[Z]) & (Steps==Steps1+Steps2))
solution[2]==(*,X,Y,'["('f', 'Steps')", "('f', 'Pa
>>> (solution[X,Y]==(Steps,Path)) <= move(X, Steps, Y) & (Path==[])
solution[2]==(*,X,Y,'["('f', 'Steps')", "('f', 'Pa
>>> start_time = time.time()
>>> print((solution['HAAHS*T*G', 'HASHTAG**']==(Steps,Path)) >= Steps)
5-6,2-5,2-3,3-6,5-6,7-8,5-8,8-9,7-8,

# prints 5-6,2-5,2-3,3-6,5-6,7-8,5-8,8-9,7-8,

>>> print("Computed in %f seconds" % (time.time() - start_time))
Computed in 54.467103 seconds

現在的問題是這兩個程式『都對』嗎？還是某一個『有錯』的呢？我們要如何『確認』的耶！

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

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

2015-07-14 懸鉤子

就讓我們試著構造一組有先後次序的子句，看看 pyDatalog 的推理引擎的運作方式。這個想法很簡單，我們定義一個『次序( □ )』的述詞，一開始只有『次序(‘一’)』是事實。隨著子句的執行帶出其它『次序( □ )』之事實，執行結果如下︰

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('連接, 鄰近, 能達, 所有路徑')
>>> +連接('台北車站', '中山')
>>> +連接('台北車站', '善導寺')
>>> +連接('台北車站', '西門')
>>> +連接('台北車站', '台大醫院')
>>> +連接('西門', '龍山寺')
>>> +連接('西門', '小南門')
>>> +連接('西門', '北門')
>>> +連接('中山', '北門')
>>> +連接('中山', '雙連')
>>> +連接('中山', '松江南京')
>>> +連接('中正紀念堂', '小南門')
>>> +連接('中正紀念堂', '台大醫院')
>>> +連接('中正紀念堂', '東門')
>>> +連接('中正紀念堂', '古亭')
>>> +連接('東門', '古亭')
>>> +連接('東門', '忠孝新生')
>>> +連接('東門', '大安森林公園')
>>> +連接('善導寺', '忠孝新生')
>>> +連接('松江南京', '忠孝新生')
>>> +連接('忠孝復興', '忠孝新生')
>>> +連接('松江南京', '行天宮')
>>> +連接('松江南京', '南京復興')
>>> +連接('中山國中', '南京復興')
>>> +連接('台北小巨蛋', '南京復興')
>>> +連接('忠孝復興', '南京復興')
>>> +連接('忠孝復興', '忠孝敦化')
>>> +連接('忠孝復興', '大安')
>>> +連接('大安森林公園', '大安')
>>> +連接('科技大樓', '大安')
>>> +連接('信義安和', '大安')
>>> +連接('信義安和', '世貿台北101')

#
>>> pyDatalog.create_terms('X站名, Y站名, Z站名, P路徑甲, P路徑乙')
>>> 連接(X站名, Y站名) <= 連接(Y站名, X站名)
連接(X站名,Y站名) <= 連接(Y站名,X站名)

#
>>> 能達(X站名, Y站名) <= 能達(X站名, Z站名) & 連接(Z站名, Y站名) & (X站名 != Y 站名) 
能達(X站名,Y站名) <= 能達(X站名,Z站名)&連接(Z站名,Y站名)&!=(X站名,Y站名)
>>> 能達(X站名,Y站名) <= 連接(X站名,Y站名)
能達(X站名,Y站名) <= 連接(X站名,Y站名)

#
>>> 鄰近(X站名, Y站名) <= 連接(X站名, Z站名) & 連接(Z站名, Y站名) & (X站名 != Y 站名)
鄰近(X站名,Y站名) <= 連接(X站名,Z站名)&連接(Z站名,Y站名)&!=(X站名,Y站名)
>>> 鄰近(X站名,Y站名) <= 連接(X站名,Y站名)
鄰近(X站名,Y站名) <= 連接(X站名,Y站名)

#
>>> 所有路徑(X站名, Y站名, P路徑甲) <= 所有路徑(X站名, Z站名, P路徑乙) & 連接(Z 站名, Y站名) & (X站名 != Y站名) & (X站名._not_in(P路徑乙)) & (Y站名._not_in(P路 徑乙)) & (P路徑甲 == P路徑乙 + [Z站名])
所有路徑(X站名,Y站名,P路徑甲) <= 所有路徑(X站名,Z站名,P路徑乙)&連接(Z站名,Y站
>>> 所有路徑(X站名, Y站名, P路徑甲) <= 連接(X站名, Y站名) & (P路徑甲 == []) 
所有路徑(X站名,Y站名,P路徑甲) <= 連接(X站名,Y站名)&==(P路徑甲,'[]')

#
>>> pyDatalog.create_terms('F費用, F費用小計, 計費所有路徑')
>>> 計費所有路徑(X站名, Y站名, P路徑甲, F費用小計) <= 計費所有路徑(X站名, Z站名, P路徑乙, F費用) & 連接(Z站名, Y站名) & (X站名 != Y站名) & (X站名._not_in(P路徑 乙)) & (Y站名._not_in(P路徑乙)) & (P路徑甲 == P路徑乙 + [Z站名]) & (F費用小計 == F費用 + 1)
計費所有路徑(X站名,Y站名,P路徑甲,F費用小計) <= 計費所有路徑(X站名,Z站名,P路徑乙,
>>> 計費所有路徑(X站名, Y站名, P路徑甲, F費用小計) <= 連接(X站名, Y站名) & (P路 徑甲 == []) & (F費用小計 == 0)
計費所有路徑(X站名,Y站名,P路徑甲,F費用小計) <= 連接(X站名,Y站名)&==(P路徑甲,

#
>>> print(計費所有路徑('台北車站', '世貿台北101', P路徑甲, F費用小計))
P路徑甲                                                                                                          | F費用小計
--------------------------------------------------------------------------------------------------------------|------
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                  | 11   
('西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                                    | 8    
('西門', '北門', '中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                      | 8    
('善導寺', '忠孝新生', '東門', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                 | 13   
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                      | 12   
('西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                      | 8    
('台大醫院', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                   | 10   
('善導寺', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                                         | 5    
('善導寺', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                         | 7    
('台大醫院', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                   | 8    
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                              | 11   
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')      | 14   
('台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                                               | 6    
('台大醫院', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                         | 9    
('善導寺', '忠孝新生', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                       | 12   
('善導寺', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                                                 | 6    
('西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                              | 11   
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                              | 11   
('西門', '北門', '中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                              | 9    
('中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                          | 9    
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                  | 13   
('西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                    | 10   
('中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                                  | 6    
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                              | 9    
('善導寺', '忠孝新生', '東門', '古亭', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')           | 14   
('西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                              | 9    
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')       | 14   
('西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                              | 11   
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                        | 12   
('西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                    | 8    
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和') | 15   
('台大醫院', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                         | 7    
('中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                                  | 6    
('西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                                          | 7    
('台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                                         | 7    
('中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                                          | 7    
('善導寺', '忠孝新生', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                 | 13   
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                        | 10   
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                        | 10   
>>>

讀者只要讀讀維基百科『圖論』 Graph theory 詞條，

將可以知道『圖』的應用廣泛，而這也正是 pyDatalog 的『強項』之一呢！

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

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

2015-07-13 懸鉤子

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

《啃一塊唄 K TCPIP！！下》

文中之『河內塔』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.

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

‧ 純陳述性

‧ 效能性

‧ 記憶中間結果

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

‧ ……

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

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

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

2015-07-12 懸鉤子

在我們進一步探討『台北捷運網』之前，先回顧一下『遞迴』這個重要『概念』，《 λ 運算︰計物數《遞迴補遺》》一文中談到︰

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

有人說︰這很簡單啊！就給一個 $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$ 有關，這時想寫個『疊代法』程式就很困難的了。所以『方法選擇』應當針對『問題狀況』，難有『萬能之法』的啊！……

這個『費波那契數』我們可以用著『pyDatalog 範例』中所講的『縮寫』辦法，寫作如下︰

>>> pyDatalog.create_terms('費波那契數')
>>> 費波那契數[N] = 費波那契數[N - 1] + 費波那契數[N - 2]
>>> 費波那契數[0] = 0
>>> 費波那契數[1] = 1
>>> print(費波那契數[5] == N)
N
-
5
>>>

由於這樣的作法『駕輕就熟』，以至於有時會『忘記』，或許根本不知道這個『縮寫』是指，下面的程式，

>>> pyDatalog.create_terms('factorial, N')
>>> factorial[N] = N*factorial[N-1]
>>> factorial[1] = 1
>>> print(factorial[25]==N)
N                         
--------------------------
15511210043330985984000000
>>>

『語法』上『完整』的寫法是︰

>>> pyDatalog.create_terms('階乘,T數')
>>> (階乘[N] == T數) <= (T數 == N * 階乘[N - 1]) 
階乘[1]==(*,N,T數) <= 階乘[1]==(*,(N-'1'),_pyD_X28)&==(
>>> (階乘[1] == T數) <= (T數 == 1) 
階乘[1]==(*,'1',T數) <= ==(T數,'1')
>>> print(階乘[3] == T數)
T數
--
6 
>>>

或許反而容易誤解下面的『條件取值』的意義，以及事實上陳述的『內容』與『條件安排』相關的事實了。

# the tax rate for salaries above 0 is 33%, and above 100 is 50 %
(tax_rate_for_salary_above[X] == 0.33) <= (0 <= X)
(tax_rate_for_salary_above[X] == 0.50) <= (100 <= X)
print(tax_rate_for_salary_above[70]==Y)
print
print(tax_rate_for_salary_above[150]==Y)

為什們人們覺得『遞迴思維』很困難呢？或許是因為還不『習慣』這麼一種思考方式。也由於它要求『邏輯之嚴密』性，否則很可能會自陷泥沼，自相矛盾的吧！舉個例子︰讀者可以想一想要如何用『遞迴』表達簡單的自然數之『加法』和『乘法』呢？嘗試寫一個 pyDatalog 程式，在這個過程裡，你將對 pyDatalog 語言，以及遞迴『終止條件』都能有更深入的了解！【※參考程式】

>>> pyDatalog.create_terms('加,乘, X數, Y數')
>>> 加[X數, Y數] = 1 + 加[X數, Y數 - 1]
>>> 加[X數, 0] = 1 + 加[X數 - 1, 0]
>>> 加[0, 0] = 0
>>> pyDatalog.create_terms('Z數')
>>> print(加[3, 2] == Z數)
Z數
--
5 
>>> print(加[7, 8] == Z數)
Z數
--
15
>>> 乘[X數, Y數] = 加[X數, 0] + 乘[X數, Y數 - 1]
>>> 乘[X數, 1] = 加[X數, 0]
>>> print(乘[3, 2] == Z數)
Z數
--
6 
>>> print(乘[7, 8] == Z數)
Z數
--
56
>>>

如果說人們常常卡在『字面意義』上，是指『語法』上不如電腦的一板一眼，『語意』上不像計算機般斤斤計較，也許此時讀一讀

《 λ 運算︰計物數》《上》‧《中》‧《下》三篇文章，多一些『思考機會』，累積些『實務經驗』，也許可以是個『起始點』的吧。

如是我們是否已能『解讀』下面文本之『片段』的呢？！

【例子捷運網】

【所有路徑述詞定義】

‧ 所有路徑(X站名, Y站名, P路徑甲) <=

所有路徑(X站名, Z站名, P路徑乙) & 【※前段】

連接(Z站名, Y站名) & 【※後段】

(X站名 != Y站名) & 【※避免迴路】

(X站名._not_in(P路徑乙)) & 【※避免迴路】

(Y站名._not_in(P路徑乙)) & 【※避免迴路】

(P路徑甲 == P路徑乙 + [Z站名]) 【※ 經過路徑累計】

‧ 所有路徑(X站名, Y站名, P路徑甲) <=

連接(X站名, Y站名) & 【※基本連接事實】

(P路徑甲 == []) 【※基本直通，無經由路徑。】

【範例程式】

# 探尋一般情況
>>> 所有路徑(X站名, Y站名, P路徑甲) <= 所有路徑(X站名, Z站名, P路徑乙) & 連接(Z站名, Y站名) & (X站名 != Y站名) & (X站名._not_in(P路徑乙)) & (Y站名._not_in(P路徑乙)) & (P路徑甲 == P路徑乙 + [Z站名])
所有路徑(X站名,Y站名,P路徑甲) <= 所有路徑(X站名,Z站名,P路徑乙)&連接(Z站名,Y站
>>> 所有路徑(X站名, Y站名, P路徑甲) <= 連接(X站名, Y站名) & (P路徑甲 == []) 
所有路徑(X站名,Y站名,P路徑甲) <= 連接(X站名,Y站名)&==(P路徑甲,'[]')
>>> print(所有路徑('台北車站', '世貿台北101', P路徑甲))

P路徑甲
                                                                                                         
-------------------------------------------------------------------------------------------------------------
('西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                                         
('善導寺', '忠孝新生', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                      
('台大醫院', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                        
('西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                   
('西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                             
('善導寺', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                                                
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')      
('西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                     
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                             
('台大醫院', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                        
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                       
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                             
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')
('善導寺', '忠孝新生', '東門', '古亭', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')          
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                             
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                       
('西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                                   
('中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                                         
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                       
('善導寺', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                                        
('西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                             
('西門', '北門', '中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                             
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                     
('台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                                              
('西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                   
('台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                                        
('中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                         
('西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                             
('善導寺', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                        
('中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                                 
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                 
('台大醫院', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                  
('善導寺', '忠孝新生', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                
('善導寺', '忠孝新生', '東門', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')     
('中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                                 
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                 
('台大醫院', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                  
('西門', '北門', '中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                     
>>> 
>>> Ans = P路徑甲.data
# 尋找第一個最短路徑
>>> [len(i) for i in Ans].index(min(map(len, Ans)))
21
>>> Ans[21]
('善導寺', '忠孝新生', '忠孝復興', '大安', '信義安和')

# 尋找第一個最長路徑
>>> [len(i) for i in Ans].index(max(map(len, Ans))) 
22 
>>> Ans[22] 
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和') 
>>> 

# 探尋連接站情況
>>> print(所有路徑('忠孝新生', '忠孝復興', P路徑甲))
P路徑甲 
-------------------------------------------------------------------------------
('松江南京', '中山', '台北車站', '台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安') 
('松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '古亭', '中正紀念堂', '小南門', '西門', '台北車站', '中山', '松江南京', '南京復興') 
('東門', '中正紀念堂', '小南門', '西門', '台北車站', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
() 
('松江南京', '中山', '台北車站', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
('松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興') 
('東門', '古亭', '中正紀念堂', '台大醫院', '台北車站', '中山', '松江南京', '南京復興') 
('松江南京', '中山', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興') 
('東門', '中正紀念堂', '台大醫院', '台北車站', '西門', '北門', '中山', '松江南京', '南京復興') 
('松江南京', '中山', '北門', '西門', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安')
('善導寺', '台北車站', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('松江南京', '中山', '台北車站', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '中正紀念堂', '台大醫院', '台北車站', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '中山', '松江南京', '南京復興') 
('松江南京', '中山', '北門', '西門', '台北車站', '台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安') 
('東門', '古亭', '中正紀念堂', '台大醫院', '台北車站', '西門', '北門', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '西門', '北門', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '古亭', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興') 
('松江南京', '南京復興') 
('東門', '大安森林公園', '大安') 
>>> Ans = P路徑甲.data

# 尋找第一個最短路徑
>>> [len(i) for i in Ans].index(min(map(len, Ans)))
6
# [()] 一致性
>>> Ans[6]
()

# 尋找第一個最長路徑
>>> [len(i) for i in Ans].index(max(map(len, Ans)))
15
>>> Ans[15]
('松江南京', '中山', '北門', '西門', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安')
>>>

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

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

2015-07-11 懸鉤子

在

《 Simply Logical
Intelligent Reasoning by Example 》

之第三章開始處， Peter Flach 說︰

3 Logic Programming and Prolog
In the previous chapters we have seen how logic can be used to represent knowledge about a particular domain, and to derive new knowledge by means of logical inference. A distinct feature of logical reasoning is the separation between model theory and proof theory: a set of logical formulas determines the set of its models, but also the set of formulas that can be derived by applying inference rules. Another way to say the same thing is: logical formulas have both a declarative meaning and a procedural meaning. For instance, declaratively the order of the atoms in the body of a clause is irrelevant, but procedurally it may determine the order in which different answers to a query are found.

Because of this procedural meaning of logical formulas, logic can be used as a programming language. If we want to solve a problem in a particular domain, we write down the required knowledge and apply the inference rules built into the logic programming language. Declaratively, this knowledge specifies what the problem is, rather than how it should be solved. The distinction between declarative and procedural aspects of problem solving is succinctly expressed by Kowalski’s equation

algorithm = logic + control

Here, logic refers to declarative knowledge, and control refers to procedural knowledge. The equation expresses that both components are needed to solve a problem algorithmically.

In a purely declarative programming language, the programmer would have no means to express procedural knowledge, because logically equivalent programs would behave identical. However, Prolog is not a purely declarative language, and therefore the procedural meaning of Prolog programs cannot be ignored. For instance, the order of the literals in the body of a clause usually influences the efficiency of the program to a large degree. Similarly, the order of clauses in a program often determines whether a program will give an answer at all. Therefore, in this chapter we will take a closer look at Prolog’s inference engine and its built-in features (some of which are non-declarative). Also, we will discuss some common programming techniques.

就讓我們舉個典型例子 ── 『台北捷運網』一小部份 ──，講講『陳述地』 declaratively 以及『程序地』procedurally 的『意義』不同，如何展現在程式『思考』和『寫作』上。

在這個例子裡，我們將以『忠孝新生』站為中心，含括了二十五個捷運站，隨意不依次序給定站名如下︰

松江南京、大安森林公園、善導寺、南京復興、忠孝復興

台北小巨蛋、小南門、忠孝新生、中山、台北車站

龍山寺、忠孝敦化、西門、雙連、中山國中

信義安和、中正紀念堂、古亭、大安、行天宮

東門、台大醫院、北門、科技大樓、世貿台北101

【例子捷運圖】

假使我們定義

連接( □, ○) 代表 □ 捷運站，僅經過 □ 站，直通 ○ 捷運站，方向是 □ → ○。如此我們可以把這部份『捷運網』，表示為︰

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('連接, 鄰近, 能達, 所有路徑')
>>> +連接('台北車站', '中山')
>>> +連接('台北車站', '善導寺')
>>> +連接('台北車站', '西門')
>>> +連接('台北車站', '台大醫院')
>>> +連接('西門', '龍山寺')
>>> +連接('西門', '小南門')
>>> +連接('西門', '北門')
>>> +連接('中山', '北門')
>>> +連接('中山', '雙連')
>>> +連接('中山', '松江南京')
>>> +連接('中正紀念堂', '小南門')
>>> +連接('中正紀念堂', '台大醫院')
>>> +連接('中正紀念堂', '東門')
>>> +連接('中正紀念堂', '古亭')
>>> +連接('東門', '古亭')
>>> +連接('東門', '忠孝新生')
>>> +連接('東門', '大安森林公園')
>>> +連接('善導寺', '忠孝新生')
>>> +連接('松江南京', '忠孝新生')
>>> +連接('忠孝復興', '忠孝新生')
>>> +連接('松江南京', '行天宮')
>>> +連接('松江南京', '南京復興')
>>> +連接('中山國中', '南京復興')
>>> +連接('台北小巨蛋', '南京復興')
>>> +連接('忠孝復興', '南京復興')
>>> +連接('忠孝復興', '忠孝敦化')
>>> +連接('忠孝復興', '大安')
>>> +連接('大安森林公園', '大安')
>>> +連接('科技大樓', '大安')
>>> +連接('信義安和', '大安')
>>> +連接('信義安和', '世貿台北101')
>>>

此處『連接』次序是『隨興』輸入的，一因『網路圖』沒有個經典次序，次因『事實』『陳述』不會因次序而改變，再因『程序』上『pyDatalog』對此『事實』『次序』也並不要求。由於『連接』之次序有『起止』方向性，上面的陳述並不能代表那個『捷運網』，這可以從下面程式片段得知。【※ 在 pyDatalog 中，沒有變元的『查詢』 ask or query ，以輸出『set([()]) 』表示一個存在的事實，以輸出『None』表達所查詢的不是個事實。】

# 單向性
>>> pyDatalog.ask("連接('信義安和', '世貿台北101')") == set([()]) 
True
>>> pyDatalog.ask("連接('世貿台北101', '信義安和')") == set([()]) 
False
>>> pyDatalog.ask("連接('世貿台北101', '信義安和')") == None
True
>>>

所以我們必須給定『連接( □, ○)』是具有『雙向性』的，也就是

連接(X站名,Y站名)<=連接(Y站名,X站名)

，這樣的『規則』 Rule 。由於 pyDatalog 的『語詞』 Term 使用前都必須『宣告』，而且『變元』必須『大寫開頭』，因此我們得用

pyDatalog.create_terms(‘X站名, Y站名, Z站名, P路徑甲, P路徑乙’)

這樣的『陳述句』 Statement。【※ 中文沒有大小寫，也許全部被當成了小寫，所以變元不得不以英文大寫起頭。】

繼續前，就讓我們先閱讀一小段程式︰

#
>>> pyDatalog.create_terms('X站名, Y站名, Z站名, P路徑甲, P路徑乙')

# 定義雙向性規則
>>> 連接(X站名, Y站名) <= 連接(Y站名, X站名)
連接(X站名,Y站名) <= 連接(Y站名,X站名)

# 兩站當然『能達』？
>>> 能達(X站名, Y站名) <= 能達(X站名, Z站名) & 連接(Z站名, Y站名) & (X站名 != Y站名) 
能達(X站名,Y站名) <= 能達(X站名,Z站名)&連接(Z站名,Y站名)&!=(X站名,Y站名)

>>> 能達(X站名, Y站名) <= 連接(X站名, Y站名)
能達(X站名,Y站名) <= 連接(X站名,Y站名)

# 測試
>>> print(能達(X站名, '世貿台北101'))
X站名   
------
雙連    
松江南京  
大安森林公園
中山    
善導寺   
台大醫院  
科技大樓  
台北小巨蛋 
行天宮   
中正紀念堂 
南京復興  
中山國中  
台北車站  
忠孝敦化  
西門    
小南門   
龍山寺   
忠孝新生  
東門    
北門    
大安    
古亭    
忠孝復興  
信義安和  

# 嘗試驗證
>>> Ans = pyDatalog.ask("能達(X站名, '世貿台北101')")
>>> Ans.answers
[('東門',), ('西門',), ('龍山寺',), ('忠孝敦化',), ('台北車站',), ('中正紀念堂',), ('台北小巨蛋',), ('中山國中',), ('科技大樓',), ('台大醫院',), ('南京復興',), ('中山',), ('行天宮',), ('善導寺',), ('信義安和',), ('大安森林公園',), ('松江南京',), ('忠孝復興',), ('雙連',), ('大安',), ('北門',), ('小南門',), ('忠孝新生',), ('古亭',)]
>>> Ans1 = pyDatalog.ask("能達('世貿台北101', X站名)") 
>>> set(Ans1.answers) == set(Ans.answers)
True
>>> Ans2 = pyDatalog.ask("能達('忠孝新生', X站名)") 
>>> set(Ans.answers + [('世貿台北101',)]) == set(Ans2.answers +[('忠孝新生',)])
True
>>>

如果此刻我們思考如下三條『規則』︰

‧ 連接(X站名, Y站名) <= 連接(Y站名, X站名)

‧ 能達(X站名, Y站名) <= 能達(X站名, Z站名) & 連接(Z站名, Y站名) & (X站名 != Y站名)

‧ 能達(X站名, Y站名) <= 連接(X站名, Y站名)

，加上『事實陳述』到底完成了些什麼？辜且不論其它規則擴張，僅就此事而論，寫作一個『對當的』 equivalent 演算法程序，搜尋『網路』這種『資料結構』也不簡單！一不小心還很容易犯錯！！如是假使『邏輯編程』語言越『純』，越用不著『程序』的『控制』，至此也許可以說所謂『程式』就是『知識的呈現』，那個自動『推理引擎』，早已建置在能夠『呈現知識』的語言中了。

不管是出於『必要』，或者是『好奇』，我們能夠如何『驗證』 pyDatalog 語言的『推論』是正確的呢？這個

Ans = pyDatalog.ask(“能達(X站名, ‘世貿台北101’)”)

Ans2 = pyDatalog.ask(“能達(‘忠孝新生’, X站名)”)

set( Ans.answers + [ ( ‘世貿台北101’ , ) ] ) == set( Ans2.answers + [ ( ‘忠孝新生’ , ) ] )

True

一方面為了這個『驗證』目的，另一方面提示 pyDatalog 『文件』中沒有講的部份。【※ 請讀者先行思索，要如何知道的耶？】如果我們對這二十五個捷運站，都做了這樣的『測試』，那麼我們能否做出『已驗證』的結論呢？！

就讓我們仿效 Peter Flach 定義一個稱之為『鄰近』 nearby 述詞︰

‧ 鄰近(X站名, Y站名) <= 連接(X站名, Z站名) & 連接(Z站名, Y站名) & (X站名 != Y站名)

‧ 鄰近(X站名, Y站名) <= 連接(X站名, Y站名)

多作一些『確認』︰

# 定義兩站『鄰近』為兩站『連接』或相距一站之遙
>>> 鄰近(X站名, Y站名) <= 連接(X站名, Z站名) & 連接(Z站名, Y站名) & (X站名 != Y站名)
鄰近(X站名,Y站名) <= 連接(X站名,Z站名)&連接(Z站名,Y站名)&!=(X站名,Y站名)

>>> 鄰近(X站名, Y站名) <= 連接(X站名, Y站名)
鄰近(X站名,Y站名) <= 連接(X站名,Y站名)

# 再次驗證檢查
>>> print(鄰近('雙連', X站名))
X站名 
----
中山  
北門  
松江南京
台北車站
>>>

，假使我們也對這二十五個捷運站，都做了這樣的『測試』，那麼我們能否做出『已驗證』的結論呢！？也許我們應當仔細的思考︰一隻黑天鵝能證明，不是所有的天鵝都是白的；但是再多的白天鵝雖能增加可信度，卻邏輯上不可能證明所有的天鵝都是白的。因此『二十五個捷運站』正確的程式，用於『□□個捷運站』只可能是正確的吧！！

── 待續………

FreeSandal

勇闖新世界︰《 pyDatalog 》導引《八上》

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

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

Core technology

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

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

輕。鬆。學。部落客

2024 年 5 月
日	一	二	三	四	五	六
« 4 月
			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