[Prolog] 先寫 A + B 再指定 A, B 值

一般人學新的程式語言,大概都是先問:怎麼寫變數,以及怎麼指派值。

Prolog 程式語言很不一樣。慎重地說, Prolog 程式語言的重點,跟 C 語言的重點不一樣。

例如,當我們寫一行 Prolog 的句子:

?- 2 + 3.

它只是定義一句邏輯句子,而這句句子並不會自動歸算為 5 。

在敘述邏輯上,對於 2 + 3 的句子,我們可以關心句子是不是「及地」 (ground) 。一句邏輯敘述句,若其中的每一個變數都賦值,就稱為及地敘述 (ground expression) 。相對地,以下一句 “A + B." 為非及地敘述,因為 A, B 變數未賦值。

?- ground(2 + 3).
true.

?- ground(A + B).
false.

如果你直接寫 “2 + 3." 並交由系統評估, Swi-prolog 系統會檢查在當前運作環境中,能不能找得到 “2 + 3." 的定義。雖然系統認得本句為置中算式,也認得 (+)/2 是動詞或稱為運算子,卻因為找不到 (+)/2 的定義,而得到錯誤結果。

?- 2 + 3.
ERROR: toplevel: Undefined procedure: (+)/2 (DWIM could not correct goal)

稍微孰悉 Prolog 的人會知道 is/2 這個動詞,甚至可能以為它就等同於 C 程式語言的 assignment 。可是,這並不是正確答案。

?- N is 2 + 3.
N = 5.

?- N is A + B.
ERROR: is/2: Arguments are not sufficiently instantiated

正確答案是, Prolog 的變數可以發生二種作用:賦值 (unifying) 與匹配 (pattern-matching) 。(前者或有人稱為 binding 或 assignment 都可以。)因此, Prolog 中的賦值,是隨著變數所在之處而到處發生的:例如,以下程式做 “append(A, B, C)." , A, B, C 都可以發生 “assignment" 。

?- A = [a, b], B = [c, d], append(A, B, C).
A = [a, b],
B = [c, d],
C = [a, b, c, d].

?- C = [a, b], append(A, B, C).
C = B, B = [a, b],
A = [] ;
C = [a, b],
A = [a],
B = [b] ;
C = A, A = [a, b],
B = [] ;
false.

?- C= [a, b], append(A, B, C).
C = B, B = [a, b],
A = [] ;
C = [a, b],
A = [a],
B = [b] ;
C = A, A = [a, b],
B = [] ;
false.

於是,可以將 “C = [a, b], append(A, B, C)." 這二句反過來寫,故事變得比較有趣一點。

?- append(A, B, C), C = [a,b].
A = [],
B = C, C = [a, b] ;
A = [a],
B = [b],
C = [a, b] ;
A = C, C = [a, b],
B = [] ;
(陷入無窮迴圈)

拆解其內容,首先,試著平白無故使用 A, B, C 三個未賦值變數,會得到將三個變數的組合結構,並且無窮產出。

?- append(A, B, C).
A = [],
B = C ;
A = [_G5103],
C = [_G5103|B] ;
A = [_G5103, _G5109],
C = [_G5103, _G5109|B];
(無窮產出下一組組合結構, A, C 二變數的值越來越長)

因此可知,在 “append(A, B, C), C = [a, b]" 這樣的程式裡,將 a, b 二個值組合到 A, B, C 裡頭,就會得到前三個有效的解,以及後續的無窮迴圈。後續有無窮迴圈,是因為 A, B, C 的組合結構持續產生,卻沒有任何一個組合結構能讓 a, b 嵌入而使 A, B, C 符合 append/3 的意思。

先產生組織結構,然後賦值,這個辦法可能會是相當好的做法,可以避免人們太過度花費精力在設計對於具體值產出的計算。

以下這個題目,來自於 P-99: Ninety-None Prolog Problems 的 P65 題。這問題的特色是,它需要先知道樹有多高,以及,每個節點需要往右移動多遠,才可以順著樹由上往下展開。而我們卻需要先把一個二元樹走到底,才能發現樹有多高,以及從樹根走到左子樹的左緣有多遠。

擷取

我的解題方法寫在這裡。 “% P65″ 位置是先賦值再計算的風格,而 “% P65a" 則是先計算再賦值的風格。在我的 “P65a" 解答裡, layout_binary_tree_2a/7 的參數,以 “(+, -, ?, ?, +, -, -)" 標示七個參數的操作方向: “+" 代表先賦值再進入這個 predicate , “-" 代表變數會由這個 predicate 獲得產出,而 “?" 則代表操作方式曖昧,可能用來輸入也可能用來輸出。而在此我標示 “?" 的變數,一方面是用來在未賦值的時候建構新的二元樹,另一方面是在 predicate 被使用時,與其他變數匹配。所以 layout_binary_tree_2a/7 本身做了三件事情:

  1. 建立帶位址的二元樹:包括用未賦值變數 LPos 計算每一層左、右臂的寬度,並且也用未賦值變數 Height 記錄每一層的高度。二元樹的每個節點, X, Y 都是以非及地敘述 (non-ground expression) 表達。
  2. 找到樹根到最左樹緣的距離: LPos1 。
  3. 找到樹的高度: Height1 。

而當 layout_binary_tree_2a/2 使用 layout_binary_tree_2a/7 的時候,則利用 LPos, Height 將未賦值變數,與經由 predicate 產出賦值的變數連接起來,於是,所產出帶位址的二元樹裡頭的每個節點位址 X, Y 都轉變為及地敘述 (ground expression) ,之後可以用 is/2 加以計算。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Problem, Prolog, Uncategorized。將永久鏈結加入書籤。