專家系統/Prolog

歷史

Prolog 是一種邏輯程式語言。它是一種通用語言，通常與人工智慧和計算語言學相關聯。它具有一個純粹的邏輯子集，稱為“純 Prolog”，以及許多非邏輯特性。

它由 Alain Colmerauer 和 Philippe Roussel 約於 1972 年建立，基於 Robert Kowalski 對 Horn 子句的程式解釋。它部分受到希望將邏輯作為一種宣告性知識表示語言的使用與 1960 年代後期和 1970 年代初在北美流行的知識程式表示方式相協調的願望的驅動。

第五代計算機系統專案 (FGCS) 為其第一個作業系統開發了 Prolog 的一個變體，名為核心語言，促進了 Prolog 的許多現代發展。

純 Prolog 最初僅限於使用具有以下形式的 Horn 子句的解析定理證明器

H :- B₁, …, B_n..

定理證明器的應用將此類子句視為過程

顯示/解決H, 顯示/解決B₁和 … 和B_n.

然而，純 Prolog 很快得到擴充套件，包括否定為失敗，其中形式為 not(B_i) 的否定條件透過嘗試並失敗來解決相應的正條件 B_i 來顯示。

資料型別

Prolog 的單一資料型別是項。項要麼是原子、數字、變數或複合項。

原子示例：x、blue、'Some atom' 和 []。

數字可以是浮點數或整數。許多 Prolog 實現還提供無界整數和有理數。

變數由一個字串表示，該字串包含字母、數字和下劃線字元，並以大寫字母或下劃線開頭。變數與邏輯中的變數非常相似，因為它們是任意項的佔位符。變數可以透過統一進行例項化。單個下劃線 (_) 表示匿名變數，表示“任何項”。

複合項具有一個函子和多個引數，這些引數又是項。引數的數量稱為項的元數。（原子可以看作是元數為零的複合項的特例。）

項的示例為 f(a,b) 和 p(x,y,z)。某些運算子可以在中綴表示法中使用。例如，項 +(a,b) 和 =(X,Y) 也可以分別寫成 a+b 和 X=Y。使用者還可以將任意符號序列宣告為新的中綴或字尾運算子，以允許特定於領域的表示法。表示法f/n 通常用於表示具有函子f 和元數n 的項。

複合項的特例

• 列表是透過歸納法定義的：原子 [] 是一個列表。具有函子 . (點) 和元數 2 的複合項，其第二個引數是列表，它本身也是一個列表。存在用於表示列表的特殊語法：.(A, B) 等效於 [A|B]。例如，列表 .(1, .(2, .(3, []))) 也可以寫成 [1,2,3]。
• 字串：用引號括起來的字元序列等效於 (數字) 字元程式碼的列表，通常以本地字元編碼或 Unicode 表示（如果系統支援 Unicode）。

Prolog 程式設計

Prolog 程式描述關係，透過子句來定義。純 Prolog 限於 Horn 子句，這是謂詞邏輯的一個圖靈完備子集。子句有兩種型別：事實和規則。規則的形式為

Head :- Body.

讀作“如果主體為真，則頭部為真”。規則的主體包含對謂詞的呼叫，這些謂詞稱為規則的目標。內建謂詞 ,/2 表示目標的合取，而 ;/2 表示析取。合取和析取只能出現在主體中，而不能出現在規則的頭部。沒有主體的子句稱為事實。事實的示例如下

cat(tom).

等效於規則

cat(tom) :- true.

內建謂詞 true/0 始終為真。

根據以上事實，可以詢問

tom 是貓嗎？

?- cat(tom).  
Yes

什麼東西是貓？

?- cat(X).  
X = tom

由於許多內建謂詞的關聯性質，它們通常可以用於多個方向。例如，length/2 可以用來確定列表的長度（length(List, L)，給定一個列表List）以及生成給定長度的列表骨架（length(X, 5)），還可以生成列表骨架及其長度（length(X, L)）。類似地，append/3 可以用來附加兩個列表（append(ListA, ListB, X)給定列表ListA和ListB）以及將給定列表拆分為多個部分（append(X, Y, List)，給定一個列表List）。出於這個原因，相對較小的庫謂詞集足以滿足許多 Prolog 程式的需要。所有謂詞也可以用來執行單元測試：查詢可以嵌入到程式中，並允許自動編譯時迴歸測試。

作為一種通用語言，Prolog 還提供了各種內建謂詞來執行常規活動，例如輸入/輸出、使用圖形以及以其他方式與作業系統通訊。這些謂詞沒有賦予關聯含義，僅對它們對系統的副作用有用。例如，謂詞write/1在螢幕上顯示一個項。

評估

Prolog 程式的執行由使用者釋出的單個目標（稱為查詢）啟動。在邏輯上，Prolog 引擎嘗試找到否定查詢的解析反駁。Prolog 使用的解析方法稱為 SLD 解析。如果否定查詢可以被反駁，則查詢（在適當的變數繫結到位的情況下）是程式的邏輯結果。在這種情況下，所有生成的變數繫結都將報告給使用者，並且查詢被認為已成功。在操作上，Prolog 的執行策略可以被認為是其他語言中函式呼叫的概括，不同之處在於多個子句頭可以匹配給定的呼叫。在這種情況下，系統建立一個選擇點，將目標與第一個備選方案的子句頭統一，並繼續執行該第一個備選方案的目標。如果在執行程式的過程中任何目標失敗，則自建立最近的選擇點以來進行的所有變數繫結都會被撤消，並且執行將繼續執行該選擇點的下一個備選方案。這種執行策略稱為按時間順序回溯。例如

sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

這導致以下查詢被評估為真

?- sibling(sally, erica).
Yes

這是這樣得到的：最初，查詢 sibling(sally, erica) 唯一匹配的子句頭是第一個子句頭，因此證明查詢等效於證明該子句的主體（在適當的變數繫結到位的情況下），即合取 (parent_child(Z,sally), parent_child(Z,erica))。要證明的下一個目標是此合取的最左邊的目標，即 parent_child(Z, sally)。有兩個子句頭匹配此目標。系統建立一個選擇點，並嘗試第一個備選方案，其主體是 father_child(Z, sally)。此目標可以使用事實 father_child(tom, sally) 來證明，因此生成了繫結 Z = tom，要證明的下一個目標是上述合取的第二部分：parent_child(tom, erica)。同樣，這可以透過相應的事實來證明。由於所有目標都可以被證明，因此查詢成功。由於查詢不包含任何變數，因此不會向用戶報告任何繫結。包含變數的查詢，例如

?- father_child(Father, Child).

在回溯上列舉所有有效答案。

注意，在上面給出的程式碼中，查詢 sibling(sally, sally) 也成功了（X = Y）。如果需要，可以插入額外的目標來描述相關的限制。

迴圈和遞迴

迭代演算法可以透過遞迴謂詞來實現。Prolog 系統通常實現一種稱為尾呼叫最佳化 (TCO) 的著名最佳化技術，用於展示尾遞迴或更普遍地尾呼叫的確定性謂詞：在尾部位置執行呼叫之前，會丟棄子句的堆疊幀。因此，確定性的尾遞迴謂詞以恆定的堆疊空間執行，就像其他語言中的迴圈一樣。

否定

內建 Prolog 謂詞 \+/1 提供否定為失敗，這允許非單調推理。規則中的目標 "\+ illegal(X)"

legal(X) :- \+ illegal(X).

的評估如下：Prolog 嘗試證明 illegal(X)。如果可以找到該目標的證明，則原始目標（即 \+ illegal(X)）失敗。如果找不到證明，則原始目標成功。因此，\+/1 字首運算子被稱為“不可證明”運算子，因為查詢 "?- \+ Goal" 在 Goal 不可證明時成功。如果其引數是接地，則這種否定是合理的。如果引數包含變數，則會失去合理性。特別是，查詢 "?- legal(X)." 現在不能用於列舉所有合法的事物。

操作注意事項

在宣告式閱讀下，規則的順序以及規則中目標的順序無關緊要，因為邏輯析取和合取是可交換的。然而，在程式上，通常重要的是要考慮 Prolog 的執行策略，無論出於效率原因，還是由於非純內建謂詞的語義，其評估順序很重要。

DCG 和解析

有一種稱為確定性子句語法 (DCG) 的特殊表示法。透過 -->/2 而不是 :-/2 定義的規則由預處理器 (expand_term/2，一個類似於其他語言中的宏的功能) 根據一些簡單的重寫規則進行擴充套件，從而產生普通的 Prolog 子句。最值得注意的是，重寫為謂詞配備了兩個額外的引數，這些引數可以用來隱式地將狀態傳遞給周圍，類似於其他語言中的單子。DCG 通常用於編寫解析器或列表生成器，因為它們還提供了一個方便的介面來進行列表差異。

解析器示例

一個更大的示例將展示在解析中使用 Prolog 的潛力。

給定用 BNF 表達的句子

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

這可以用 Prolog 中的 DCG 來編寫，對應於具有一個標記前瞻的預測解析器

sentence(S)                --> statement(S0), sentence_r(S0, S).
sentence_r(S, S)           --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).

statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].

expression(E) --> term(T), expression_r(T, E).
expression_r(E, E)  --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).

term(T)       --> factor(F), term_r(F, T).
term_r(T, T)  --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).

factor(id(ID))   --> id(ID).
factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}.

id(a) --> [a].
id(b) --> [b].

此程式碼定義了一個句子（以標記列表的形式給出）與其抽象語法樹 (AST) 之間的關係。示例查詢

?- phrase(sentence(AST), [a,=,1,+,3,*,b,;,b,=,0,;]).
AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;

AST 使用 Prolog 術語表示，可以用於應用最佳化、將這些表示式編譯為機器程式碼，或者直接解釋這些語句。正如謂詞的關聯性質所典型的那樣，這些定義既可以用於解析和生成句子，也可以用於檢查給定的樹是否對應於給定的標記列表。使用迭代加深進行公平列舉，每個任意但固定的句子及其相應的 AST 最終都會被生成

?- length(Tokens, _), phrase(sentence(AST), Tokens).
 Tokens = [a, =, a, (;)], AST = assign(a, id(a)) ;
 Tokens = [a, =, b, (;)], AST = assign(a, id(b)) 
 etc.

高階程式設計

由於可以在執行時構造和評估任意 Prolog 目標，因此很容易編寫像 maplist/2 這樣的高階謂詞，它將任意謂詞應用於給定列表的每個成員，以及 sublist/3，它過濾滿足給定謂詞的元素，也允許柯里化。

為了將解從時間表示（回溯時的答案替換）轉換為空間表示（術語），Prolog 具有各種所有解謂詞，這些謂詞將給定查詢的所有答案替換收集到一個列表中。這可以用於列表推導。例如，完美數等於其真因子的總和

perfect(N) :-
    between(1, inf, N), U is N // 2,
    findall(D, (between(1,U,D), N mod D =:= 0), Ds),
    sumlist(Ds, N).

這可以用來列舉完美數，也可以用來檢查一個數是否為完美數。

元直譯器和反射

Prolog 是一種同像語言，並提供了許多用於反射的功能。它的隱式執行策略使編寫簡潔的元迴圈評估器（也稱為元直譯器）成為可能，用於純 Prolog 程式碼。由於 Prolog 程式本身是 Prolog 術語的序列（:-/2 是一箇中綴運算子），這些術語很容易使用內建機制（如 read/1）讀取和檢查，因此很容易編寫自定義直譯器，這些直譯器為 Prolog 新增特定於域的功能。

實現技術

為了提高效率，Prolog 程式碼通常被編譯為抽象機器程式碼，通常受基於暫存器的 Warren 抽象機 (WAM) 指令集的影響。一些實現採用抽象解釋，在編譯時推匯出謂詞的型別和模式資訊，或者編譯為真正的機器程式碼以獲得高效能。為 Prolog 程式碼設計高效的實現技術是邏輯程式設計社群中一個活躍的研究領域，在一些實現中採用了各種其他執行技術。這些包括子句二元化和基於堆疊的虛擬機器。

例子

下面是一些用 Prolog 編寫的示例程式。

快速排序

快速排序排序演算法，將一個列表與其排序後的版本相關聯

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).

quicksort([])     --> [].
quicksort([X|Xs]) --> 
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

圖靈機

可以透過使用 Prolog 模擬圖靈機來證明 Prolog 的圖靈完備性

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

一個簡單的示例圖靈機由以下事實指定

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

此機器執行以一元編碼表示的數字加一：它迴圈遍歷任何數量的“1”單元格，並在末尾附加一個額外的“1”。示例查詢和結果

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

此示例說明如何將任何計算宣告性地表示為一系列狀態轉換，在 Prolog 中實現為感興趣的連續狀態之間的關係。作為另一個示例，具有三個最佳化步驟的最佳化編譯器可以實現為初始程式與其最佳化形式之間的關係

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

或者等效地使用 DCG 表示法

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

動態規劃

以下 Prolog 程式使用動態規劃以多項式時間找到兩個列表的最長公共子序列。子句資料庫用於記憶

:- dynamic stored/1.

memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).

lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
    memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
    length(Ls1, L1), length(Ls2, L2),
    (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

示例查詢

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]

一些 Prolog 系統，如 BProlog 和 XSB，實現了一種稱為表化的擴充套件，這使使用者無需手動儲存中間結果。

擴充套件

• 約束邏輯程式設計對於許多 Prolog 在工業環境中的應用至關重要，例如時間表和其他的排程任務。大多數 Prolog 系統至少附帶一個有限域的約束求解器，通常還附帶其他域的求解器，例如有理數。
• HiLog 和 λProlog 為 Prolog 擴充套件了高階程式設計功能。
• F-logic 為 Prolog 擴充套件了用於知識表示的框架/物件。
• OW Prolog 是為了解決 Prolog 缺乏圖形和介面而建立的。
• Logtalk 是一種開源面向物件擴充套件，用於 Prolog 程式語言。它將邏輯程式設計與面向物件和事件驅動程式設計相結合，與大多數 Prolog 編譯器相容。它支援原型和類。此外，它還透過基於類別的組合支援基於元件的程式設計。
• Prolog-MPI 是一個開源的 SWI-Prolog 擴充套件，用於透過訊息傳遞介面進行分散式計算。

相關語言

• Visual Prolog，以前也稱為PDC Prolog和Turbo Prolog。Visual Prolog 是 Prolog 的一種強型別面向物件方言，它與標準 Prolog 大不相同。作為 Turbo Prolog，它由 Borland 推出，但現在由最初開發它的丹麥公司 PDC（Prolog 開發中心）開發和銷售。
• Datalog 實際上是 Prolog 的一個子集。它僅限於可以分層的語義關係，並且不允許複合項。與 Prolog 相反，Datalog 不是圖靈完備的。
• 在某種程度上，Prolog 是 Planner 的一個子集，例如，參見 Kowalski 關於邏輯程式設計的早期歷史。Planner 中的思想後來在科學社群隱喻中得到進一步發展。

也存在可以為 Prolog 和 Java 程式語言之間提供橋樑的框架

• InterProlog，一個在 Java 和 Prolog 之間的程式設計庫橋樑，實現了兩種語言之間雙向謂詞/方法呼叫。Java 物件可以對映到 Prolog 項，反之亦然。允許在 Java 中開發 GUI 和其他功能，同時將邏輯處理保留在 Prolog 層。支援 XSB、SWI-Prolog 和 YAP。
• Prova 提供與 Java 的原生語法整合、代理訊息傳遞和反應規則。Prova 將自己定位為用於中介軟體的基於規則的指令碼 (RBS) 系統。該語言在結合指令式程式設計和宣告式程式設計方面開闢了新的領域。

參考資料

• Michael A. Covington，Donald Nute，Andre Vellino，《Prolog Programming in Depth》，1996 年，ISBN 0-13-138645-X。
• Michael A. Covington，《Natural Language Processing for Prolog Programmers》，1994 年，ISBN 0-13-629213-5。
• Leon Sterling 和 Ehud Shapiro，《The Art of Prolog: Advanced Programming Techniques》，1994 年，ISBN 0-262-19338-8。
• Ivan Bratko，《PROLOG Programming for Artificial Intelligence》，2000 年，ISBN 0-201-40375-7。
• Robert Kowalski，《The Early Years of Logic Programming》，CACM 1988 年 1 月。
• 《ISO/IEC 13211: Information technology — Programming languages — Prolog》。國際標準化組織，日內瓦。
• Alain Colmerauer 和 Philippe Roussel，《The birth of Prolog》，收錄在《The second ACM SIGPLAN conference on History of programming languages》中，第 37-52 頁，1992 年。
• Richard O'Keefe，《The Craft of Prolog》，ISBN 0-262-15039-5。
• Patrick Blackburn，Johan Bos，Kristina Striegnitz，《Learn Prolog Now!》，2006 年，ISBN 1-904987-17-6。

另請參見

• Prolog 中的 literate programming
• Prolog Tutorial 由 J.R.Fisher 撰寫
• Visual Prolog 教程
• Visual Prolog Wiki
• 可執行的示例 由 Lloyd Allison 撰寫
• Prolog Programming A First Course 由 Paul Brna 撰寫
• Adventure in Prolog，由 Amzi! Inc. 撰寫，線上書籍
• Prolog 程式設計線上指南 由 Roman Bartak 撰寫
• Prolog 小冊子，由 Faiz ul haque Zeya 撰寫
• Learn Prolog Now! 由 Patrick Blackburn，Johan Bos 和 Kristina Striegnitz 撰寫
• Prolog and Logic Programming 由 Peter Hancox 博士撰寫
• Strawberry Prolog 幫助，線上幫助
• Building Expert Systems in Prolog，由 Amzi! Inc. 撰寫，線上書籍
• comp.lang.prolog FAQ
• Prolog：ISO 標準
• Prolog 開發中心