C 與 Prolog 之比較

語法理論說明了程式語言語法的描述方式,但是,卻沒有告訴我們,為何要設計這樣的語法,而語義理論則彌補了這個缺憾。

語義理論說明了語法所對應的意義,也就是程式應該如何執行的規範。透過語義理論,程式才能被賦予明確的意義,並且確定每個語句的執行方式。

舉例而言,下列兩個程式具有相當不同的語法結構,但是所做的事情卻相當類似,兩者均實作了泡沫排序法,但不同的是,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語法,利用以『比對、遞迴』為主的結構。這兩種不同的構造方式,造成了截然不同的程式設計方式。

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

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