語義理論

語法理論說明了程式語言語法的描述方式,但是,卻沒有告訴我們,為何要設計這樣的語法,而語義理論則彌補了這個缺憾。
語義理論說明了語法所對應的意義,也就是程式應該如何執行的規範。透過語義理論,程式才能被賦予明確的意義,並且確定每個語句的執行方式。

舉例而言,下列兩個程式具有相當不同的語法結構,但是所做的事情卻相當類似,兩者均實作了泡沫排序法,但不同的是,C與Prolog語言具有不同的語法結構,也擁有不同的語意邏輯。

範例 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;
}

範例 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).

C語言屬於結構化程式語言的一種,使用的是『運算、循序、分支、迴圈、函數』等結構,這是目前產業界的主流語言結構。但是Prolog則使用了串列 (LIST) 結構,採用邏輯推論中的Horn Clause語法,利用以『比對、遞迴』為主的結構。這兩種不同的構造方式,造成了截然不同的程式設計方式。

當語法樹建構完成時,就可以進行語義上的組合。在語法樹中的父子節點關係,是語義構造的重點所在。

結構化的語義

在結構化的程式語言 (例如 C , C# 等) 中,『指定、運算、循序、分支、迴圈、函數』等是主要的結構,表格 7.2顯示了結構化程式的構造方式,讓我們來看看這些結構所隱含的語義。

表格 7.2結構化程式的構造方式

結構類型 語法 範例
指定結構 <ASSIGN> ::= <VAR> = <EXP> x = 3*y+5
運算結構 <EXP> ::= <T> { ["+"|"-"] <T> } 3*y+5
循序結構 <BASE_LIST > ::= { <BASE> } t=a; a=b; b=t;
分支結構 <IF> ::= if (<COND>) <BASE> { else if (<COND>) <BASE> } [else <BASE> ] if (a>b) c=a; else c=b;
迴圈結構 <WHILE> ::= while (<COND>) <BASE> while (i<=10) { sum = sum+i; i++;}
函數結構 <FUNC_DEF> ::= <FUNC>({<ARGS>}) <BLOCK> <FUNC_CALL>::= <FUNC>({<PARAMS>}); 定義:max(a,b) {if (a>b) return a; else return b;} 呼叫:c = max(3,5);

指定結構的語法是 <VAR> = <EXP>,其意義乃是將 <EXP> 的運算結果傳送給變數 <VAR>,於是,<VAR> 變數將會設定為 <EXP> 的數值。舉例而言,指定敘述 x = 3*y+5 會將 3*y+5 的結果傳送給 x,假如 y 的值為 4,則執行完後 x 的值將變成 17。

運算結構的語法是從數學中借用過來的,基本上圖 7.10的四個規則就是運算結構的語法??但表7.2中只有加、減??。其語意正是數學中的加減乘除之語義,舉例而言,規則 <EXP> ::= <T> { ["+"|"-"] <T> } 定義了加減的語法,而其語意則是將 <T>+<T> 或 <T>-<T> 的結果傳回。

循序結構的語法是{ <BASE> },代表 <BASE> 可以連續出現很多次,其意義是順序執行每個 <BASE> 敘述,例如像 t=a; a=b; b=t; 這樣的語句,其意義是當 t=a 執行完後,接著執行 a=b,然後再執行 b=t。

分支結構可以用 if (<COND>) <BASE> { else if (<COND>) <BASE> } [else <BASE> ] 這樣的語法表示,其意義是當條件 <COND> 成立時,就執行值型對應的 <BASE> ,如果都不成立,則執行最後的 else 語句,例如像 if (a>b) c=a; else c=b; 這樣的語句,其意義是當 a>b 條件成立時,就執行c=a,否則,就執行 else 中的敘述 c=b。

迴圈結構通常有 for 迴圈與 while 迴圈,其中,while 迴圈的語法為 while (<COND>) <BASE>,其意義是當是當 <COND> 條件成立時,就繼續執行 <BASE> 區塊??<BASE>是一個區塊嗎??,直到 <COND> 條件不成立才離開 while 迴圈。例如,while (i<=10) { sum = sum+i; i++;} 這樣的語句,在 i<=10 時,會執行 { sum = sum +I; i++; } 區塊,直到 i大於10為止。

函數結構的語法可用 <FUNC> ({<ARGS>}) <BLOCK> 的方式定義,例如,max(a,b) {if (a>b) return a; else return b;} 這樣的函數 max,可用來取得 a, b 中的較大值直傳回。接著,我們可用 max(3,5) 這樣的語句呼叫,將 3 傳給a, 5傳給b,其語法為<FUNC>({<PARAMS>}); 的方式呼叫,呼叫時會將 <PARAMS> 中的引數,傳遞給 <ARGS> 參數,然後開始才開始執行 <BLOCK> 區塊的程式。

物件導向語義

第一個物件導向語言是 SmallTalk,SmallTalk 80的物件導向概念成為後來許多語言競相模仿的對象,像是 C++, Java, C# 等都是將 C 語言擴充以支持物件導向與義的結果,物件導向語意主要是將資料與函數綁在一起,形成類別與物件結構。

類別的語法可用 class <CLASS_NAME> { <VAR_DEF>* <FUNC_DEF>* } 這樣的結構進行宣告,其中的 * 代表 <VAR_DEF> 與 <FUNC_DEF> 都可以出現數次。程式人員可以利用 new <CLASS_NAME>() 這樣的語法,呼叫 <function> 中的建構函數,建構出該類別的物件。然後,透過 <CLASS_NAME>.<VAR> 的方式,存取該物件的變數,也可以透過 <CLASS_NAME>.<FUNC> 這樣的語法,呼叫該物件的函數。

舉例而言,我們可以用 class Stack { String array[], push(o) {…}, pop {…} } 這樣的語法,宣告一個堆疊物件,然後透過 s = new Stack() 建立物件 s,接著,再透過 s.array 取得 s 物件中的陣列變數,或者透過 s.push(“hello”) 這樣的語法,呼叫 push函數,以便將 “hello” 字串推入堆疊中。

物件導向的語義,與人類對『物體』的概念一致,具有容易想像與理解的特性,這對高階語言而言是一大貢獻。因此,2003 年的圖靈獎頒給了Smalltalk的發明人 Alan Kay,以表彰他的貢獻。

邏輯式語義

由於目前大部分的語言都採用結構化的構造方式,因此,程式設計師很難想像出其他的語義構造方式,因此,我們特別以一個截然不同的程式語言-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是兩種截然不同的典型,透過這樣的比較,讀者應可體會語義系統的構造方式,可以多麼的不同,進而理解語義理論的精神。

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License