SOGO論壇

標題: 語意理論：邏輯式語言 Prolog [列印本頁]

作者: mm117777 時間: 2012-7-12 09:12:17 標題: 語意理論：邏輯式語言 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;
}

歡迎光臨 SOGO論壇 (https://oursogo.com/)