- 註冊時間
- 2006-10-8
- 最後登錄
- 2019-6-20
- 主題
- 查看
- 積分
- 1306
- 閱讀權限
- 110
- 文章
- 1393
- 相冊
- 0
- 日誌
- 1
狀態︰
離線
|
由於目前大部分的語言都採用結構化的構造方式,因此,程式設計師很難想像出其他的語義構造方式,因此,我們特別以一個截然不同的程式語言-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;
}
|
|