C 與 Prolog 之比較

mm117777

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

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

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

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