語意理論:邏輯式語言 Prolog

由於目前大部分的語言都採用結構化的構造方式,因此,程式設計師很難想像出其他的語義構造方式,因此,我們特別以一個截然不同的程式語言-Prolog,說明語義構造可以是多麼的不同。

要理解Prolog的語義之前,必須先理解其語法,Prolog有三種基本的句型 1. 事實 (Facts) 2. 推論 (clause) 3. 問題 (query),這三個基本句型又都以『謂詞』(predicate) 語法為基礎。

一個謂詞 <PR> 的語法可用 <P>(<ARGS>) 表示,這個語法有點像結構化中的函數,但其傳回值永遠為布林值,只有真與假兩種。例如,表格 7.3中的Mother(Mary, Peter), Ancestor(a,c), Ancestor(a,b), Ancestor(b,c), Ancestor(x,Peter) 等,都是謂詞。

表格 7.3程式語言Prolog的構造方式

結構類型 BNF 語法 範例
謂詞結構 <PR> ::= <P>(<ARGS>) Mother(Mary, Peter)
事實結構 <FACT> ::= <PR>. Mother(Mary, Peter).
推論結構 <CLAUSE> ::= <PR> :- <PR>{, <PR>}. Ancestor(a, c) :- Ancestor(a, b),Ancestor(b,c).
問題結構 <QUERY> ::= ?- <PR>. ?- Ancestor(x,Peter).

Prolog 中的事實結構 <FACT>,語法為單一個謂詞後加上句點表示,其意義為該謂詞為真的,例如,Mother(Mary, Peter). 這樣一個語句,代表『Mary為 Peter的母親』這個語句是一個事實。

Prolog 中的推論結構 <CLAUSE>,語法為 <PR> :- <PR>{, <PR>}.,其意義為一個推論規則,例如,Ancestor(a, c) :- Ancestor(a, b),Ancestor(b,c). 這樣一個推論語句,代表當 Ancestor(a, b) 與 Ancestor(b,c) 均為真的情況下,就可推論出 Ancestor(a, c) 必定為真。若翻譯成中文,該語句代表『若a 是 b 的祖先,且 b 是 c 的祖先,則 a 是 c 的祖先』。

Prolog 中的問題結構 <QUERY>,語法為 <QUERY> ::= ?- <PR>.,其意義為一個問句,例如,?- Ancestor(x,Peter).這樣一個問句,乃是在問哪些人 (x變數) 是 Peter的祖先。

當問題一出現的時候,Prolog 系統就會呼叫其邏輯引擎,透過『列舉、比對、推論』等程序,找出符合 Ancestor(x, Peter) 問句的解答,然後,回答誰是 Peter 的祖先。

於是,我們可以撰寫下列的程式,用來推論親屬當中的祖先關係。然後,當我們於Prolog系統中提出 Parent(x,Peter) 這個問題時,Prolog 會回答Ancestor(Mary, Peter), Ancestor(Bob, Peter) 等語句,告訴我們Peter 的祖先是誰。

範例 7.3 Prolog 的程式範例與回答

Prolog 推論                                       ; 說明 
Ancestor(a, c) :- Ancestor(a, b), Ancestor(b,c).  ; 若a是b的祖先,且b是c的祖先,  則 a 是 c 的祖先
Ancestor(a, b) :- Parent(a,b).                    ; 若a是b的尊親,則a是b的祖先
Parent(a,b) :- Mother(a,b).                       ; 若a是b的母親,則a是b的尊親
Parent(a,b) :- Father(a,b).                       ; 若a是b的父親,則a是b的尊親

Prolog 事實                                       ; 說明 
Mother(Mary, Peter).                              ; Mary 是 Peter 的母親
Father(Bob, Mary).                                ; Bob 是 Mary 的父親

Prolog 問題                                       ; 說明 
?- Ancestor(x,Peter).                             ; 誰是 Peter 的組先 ? 

Prolog 的回答                                     ; 說明 
Ancestor(Mary, Peter).                            ; Mary 是 Peter 的祖先
Ancestor(Bob, Peter).                             ; Bob 是 Peter 的祖先

在本節中,我們利用C與 Prolog 兩者的比較,說明了語法和語義之間的關係,由於C與Prolog是兩種截然不同的典型,透過這樣的比較,讀者應可體會語義系統的構造方式,可以多麼的不同,進而理解語義理論的精神。

範例 7.2快速排序法的Prolog程式

quicksort([X|Xs],Ys) :-
  partition(Xs,X,Left,Right),
  quicksort(Left,Ls),
  quicksort(Right,Rs),
  append(Ls,[X|Rs],Ys).
quicksort([],[]).

partition([X|Xs],Y,[X|Ls],Rs) :-
  X <= Y, partition(Xs,Y,Ls,Rs).
partition([X|Xs],Y,Ls,[X|Rs]) :-
  X > Y, partition(Xs,Y,Ls,Rs).
partition([],Y,[],[]).

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

範例 7.1快速排序法的C語言程式

void quicksort(double a[], int left, int right) {
    int last = left, i;

    if (left >= right) return;

    swap(a,left,Random(left,right));
    for (i = left + 1; i <= right; i++)
        if (a[i] < a[left])
            swap(a,++last,i);
    swap(a,left,last);
    quicksort(a,left,last-1);
    quicksort(a,last+1,right);
}
void swap(double a[], int i, int j) {
    double tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License