第五代編程語言設計與實現

韓濟澎，李陳志航

(北京華規科技有限公司技術部 北京 100081)

0 引言

編程語言的發展經歷了機器語言、匯編語言、高級語言、函數語言、邏輯語言[1]。其中，邏輯編程語言亦被稱作第五代編程語言。最早的邏輯語言是列表處理語言LISP（LISt Processing），其特點是用符號表達式而不是數字進行計算；不足是數值運算能力較弱和數學語義不清晰[2]。后來PROLOG問世，其特點是基于符號邏輯進行運算，通過模式匹配完成計算，語言清晰、可讀、簡潔[3-4]；不足是對規則和目標的表示有嚴格限制，難以適用于復雜的應用環境[5-7]。

具體改進如下：第一，COOL支持面向過程與面向對象，便于應用于生產項目；第二，COOL支持將表達式作為函數聲明以及函數返回，同時支持將函數參數嵌入函數名字字符串中；第三，COOL引入了權重機制并通過累計權重法加速推理過程；第四，COOL引入正向函數、逆向函數的概念，以處理邏輯上具有先后順序約束的問題；第五，通過回溯算法和動態規劃算法實現計算機利用正向求解過程推導逆向求解過程；第六，引入預執行步驟，將推理過程從程序的執行過程中分離，提升程序的執行速度。

1 語法

1.1 函數

函數構成了COOL的推理框架。此節介紹了返回表達式的函數、返回運算值的函數、附加權重的函數、正向函數、逆向函數、函數權重。在COOL中函數由函數聲明和函數體兩部分組成，表示相加的函數可以用如代碼1的方式進行定義。

代碼 1 函數聲明示例：

@add(a,b){

return:a+b;

}

通過為函數聲明加上屬性“exp”來表明此函數的返回是一個表達式。這種函數用來表述變換規則，用戶不能直接調用此類函數，如代碼2通過函數描述乘法分配律的逆運算。

代碼2返回表達式的函數示例：

exp:@{a*c+b*c}{

return:(a+b)*c;

}

正向函數與逆向函數均指返回運算值的函數；返回表達式的函數不具備此屬性。正向函數，即所有函數參數均確定，函數返回值待定的函數。正向函數的執行過程即利用輸入參數推導函數的返回值。逆向函數，即函數返回值確定，函數輸入參數中存在待定參數的函數。逆向函數的執行過程即利用函數的返回值與確定的輸入參數計算待定的輸入參數。

函數權重用于控制推理系統的推理方向。用戶可以為那些更容易導向正確推理結果的變換賦予更大的權重，不容易導向正確推理結果的變換賦予更小的權重。函數的權重在函數聲明時確定，例如代碼3中定義了一個權重為10的函數：

代碼3具有權重的函數示例：

@(10){$a == b;}{

a = b;

}

1.2 變量

COOL的非臨時變量在使用前必須被聲明。變量的類型由最近一次所賦值的類型決定。默認類型為浮點數。變量從其被聲明處至其所在作用域結束處之間均可被訪問。一個表達式優先使用當前作用域的變量。用戶可以通過使用“out”修飾變量以使表達式使用上層作用域的變量。例如代碼4：

代碼4“out”使用示例：

new:a = 1;

{

new:a=0;

a=out:a+1;

}

1.3 完整代碼示例

求解以下數學問題：對兩個數字量x，y依次進行以下操作：將x,y求和，結果記為a；修改x的值，使其滿足x+1值等于y；求解變量z，滿足z^2+x*z+y等于100；x，y，a求和，得到最終結果；求解問題的完整代碼如代碼5，最終結果為36.1005。

代碼5完整代碼示例：

/*定義求解二次方程的函數*/

@(100){a*$x^2+b*x+c}{

x=(-b+(b^2-4*a*(c-ans))^0.5)/(2*a);

}

/*定義加法的逆向函數*/

@(10){$a+b}{

a=ans-b;

}

@由(x)與(y)得結果{

new:a = x+y;

$x+1==y;

new:z=0;

1*$z^2+x*z+y==100;

return:a+x+z;

}=>@由($x)與(y)得結果;

new:x = 0;

new:y = 3;

由($x)與(y)得結果==50;

x-->0;/*“-->”表示輸出，意為將x值以默認方式輸出*/

企業發展需要員工具有較高的綜合職業能力，包括創新意識和創新能力、組織執行力、交往與合作能力、學習與思維能力、獨立性與責任感等，這就需要我們在教學過程中突出強化和滲透這種能力。

1.4 類

解決相似問題的規則可以單獨封裝成類，通過繼承用戶可以更靈活地復用、修改和拓展規則，實現對復雜問題的分治處理和程序的模塊化開發。在COOL中類由聲明和類的作用域組成，在定義一個類時可以使其繼承其他的類以使用其成員函數和變量，如代碼6所示：

代碼6類繼承示例

system:MainProcess<

……

}

2 編譯

2.1 預編譯

預編譯過程中將源代碼標識符中出現的非ASCII碼替換為ASCII碼字符串；同時，將所有函數參數移動至函數名字字符串后，并保持函數參數順序不變，在函數參數原來位置用特定字符串（例如：“_Arg_”）代替形成新的字符串；例如add(A)and(B)to(C)在預編譯后變形成add_Arg_and_Arg_to(A,B,C)。

2.2 代碼類型

通過詞法分析程序與語法分析程序將預編譯后的代碼編譯為字符碼。字符碼由三部分組成，包括代碼類型標志位、四元式、四元式參數類型標志位數組。

代碼類型及其所描述的功能包括變量聲明（聲明一個變量）；函數操作（綁定函數聲明作用域與函數體作用域，或綁定權重、返回類型與函數聲明作用域）；推導函數（根據指定的正向函數推導逆向函數的實現邏輯）；域起始（表示作用域的起始）；域結束（表示作用域的結束）；表達式（表明此行代碼的四元式是表達式的一部分，包括運算、函數調用、將屬性（“$”“#”“out”）賦予變量）；跳轉（當一定條件跳轉到指定代碼繼續執行）；表達式結束（截斷表達式）；返回（從函數返回）；成員訪問（給計算機指明訪問成員的路徑）；類操作（用于聲明類、繼承類、將類名與作用域綁定）。

四元式及四元式參數類型標志位數組：在代碼類型為“表達式”時用于儲存四元式的左運算對象、右運算對象、運算符、運算結果以及對應的數據類型；當代碼為其他類型時僅用于儲存參數。

3 預執行

3.1 加載字符碼

四元式形參標志位數組：當代碼位于函數聲明作用域時有效，標識四元式中參數是否為形式參數；當代碼位于函數聲明作用域外時有效，標識查詢四元式中對應參數是從當前代碼所在作用域內開始查詢（標志位為真）還是從當前代碼所在作用域的上層作用域開始查詢（標志位為假）。四元式參數待定標志位數組：用于標識在此行代碼被執行時，四元式中對應參數的值是否待定，若參數待定（標志位為真），則此參數的值將被視作未知（或無效）；若參數確定（標志位為假），則此參數的值將被視作已知條件；對于返回表達式的函數，由于很多情形下其代表的變換規則與變量是否待定無關，故允許其函數聲明中的參數具有“待定”“確定”“無關”三種狀態，相應地表示為真、假、無關三種值。綁定函數地址：用以標識代碼所綁定的函數的地址；由于COOL中所有函數聲明均儲存為語法樹形式，因此調用某個函數需要將此函數的地址與函數聲明表達式進行綁定，在執行此行段代碼時就會調用所綁定的函數。此地址在函數根結點標志位為真，說明此行代碼對應所綁定函數的聲明表達式的根結點，為假則對應子結點。

3.2 推理過程

定義數據的表示格式a(b│c)，表示數據a和 周期（匹配輪數）內被創建或賦值，在周期c內被使用；定義一種鍵值對的表示方式，其以a為鍵以b為值。在不引起歧義的情況下，本節允許代碼段、表達式、語法樹互相代指。

（1）初始化

復制當前執行代碼所在最長的表達式對應代碼段e,獲得以初始累計權重值0為鍵、復制代碼段為值的鍵值對<0,e>；將復制代碼段鍵值對添加至當前代碼倉S；其中，S為一個以累計權重值為鍵、代碼段為值的二維表；

代碼倉的容量由用戶設定，當嘗試向一個已滿的代碼倉添加新鍵值對時，如果其鍵大于代碼倉中最小的鍵，則代碼倉刪除鍵最小的鍵值對后再添加新的鍵值對；如果其鍵不超過代碼倉中最小的鍵，則添加失敗；此外，代碼倉中不允許存在值完全一樣的鍵值對。

（2）第k輪匹配

對于k∈N*，在當前代碼倉S(k-1│k)不為空時，對于所有∈S(k-1│k)，{i|i∈N∧i

代碼段匹配函數，指將代碼段對應的表達式exp1與函數聲明表達式exp2進行比較，若exp1與exp2的語法樹結構相同，且任取exp1的一個結點node1以及exp2中與node1對位的結點nod12，node1與node2均滿足以下五種情況之一，則匹配成功：node1是具體值且node2是相同的值；node1是具體值且node2是類型相同的形式參數；node1是變量且node2是類型相同的形式參數；node1與node2是同一個變量。當fun代表的是一個化簡操作，在進行代碼替換后，可能產生脫離表達式語法樹的代碼片段，如1中所示。

圖1 分支脫離表達式語法樹示例

當fun代表的是一個化繁操作，則在使用返回表達式的函數進行代碼替換后，表達式的語法樹可能產生環狀結構（例如變換(a+b)*(x+1)→a*(x+1)+ b*(x+1)在語法樹只有一個x+1分支的時候會導致a*(x+1)和b*(x+1)引用同一個x+1分支的根結點，產生了環狀結構）；如2中所示：

圖2 表達式語法樹形成環狀結構示例

因此每當代碼替換后都需要查找并刪除代碼段中脫離表達式語法樹的代碼片段并展開生成的環狀結構。

（3）匹配結束條件

當ej滿足所有代碼均與函數綁定時，匹配過程以成功結束，用ej替換掉當前執行代碼所在最長的表達式對應的代碼段；否則將添加到S(k│k+1)中并繼續進行匹配：

當匹配輪數k超出用戶規定上限時以失敗結束；當本輪和下一輪均無可用元素參與匹配時以失敗結束：

圖3展示了在預執行結束后表達式與函數的綁定情況。

圖3 代碼段21預執行后表達式與函數的綁定效

3.3 推導函數

當代碼類型標志為“推導函數”時，利用指定的正向函數推導逆向函數的函數實現，依次執行以下步驟：

（1）將正向函數的函數體代碼段拆解為代碼塊

代碼塊，由序號、代碼段、代碼塊信息組成，越早創建的代碼塊序號越小；代碼塊信息包括：代碼塊類型，反映代碼段中代碼的類型；代碼塊依賴待定輸入參數標志位，反映代碼段中是否存在依賴待定輸入參數的變量。變量依賴于待定輸入參數，指的是在正向執行函數體代碼的過程中，確定待定輸入參數的值是確定此變量的值的必要條件，反之則獨立于待定輸入參數。

拆解過程需從前向后逐行分析正向函數的函數體的每一行代碼，若當前分析代碼的可執行標志位為假，跳過；若為真或“一定條件下執行”，根據代碼類型執行以下步驟，a域起始：創建代碼塊，類型為“域起始”，依賴待定輸入參數標志位為假，代碼段為當前分析代碼；將其加入代碼塊隊列B中；b域結束：創建代碼塊，類型為“域結束”，依賴待定輸入參數標志位為假，代碼段為當前分析代碼；將其加入代碼塊隊列B中；c表達式結束：跳過；d表達式：若函數根結點標志位為假，跳過；否則，復制當前代碼所在函數調用表達式對應的代碼段，并對此復制代碼段依次執行操作創建代碼塊；f返回：創建代碼塊，類型為“返回”，依賴待定輸入參數標志位為假。由于逆推時返回值已知，故在代碼段中將正向函數返回值ans賦予被返回的變量，同時將代碼類型“返回”修改為“表達式”；最后將代碼塊加入代碼塊隊列B中；g其他情況：創建代碼塊，類型為“默認”，依賴待定輸入參數標志位為假，代碼段為當前分析代碼；將其加入代碼塊隊列B中。

（2）利用代碼塊推導逆向函數的執行過程

a將B中的代碼塊根據是否依賴待定輸入參數，重組為依賴待定輸入參數代碼塊隊列Bdependent，和獨立于待定輸入參數代碼塊隊列Bindependent，重組的兩個隊列中代碼塊根據序號從小到大排列；b當Bdependent不為空時，通過動態規劃算法進行逆推。

所采用的優先順序，具體為待定輸入參數的必要變量數目越少越優先，依賴關系樹的結點數越少越優先。其中，依賴待定輸入參數的必要變量，即依賴待定輸入參數、且同時被依賴關系樹的結點和Bdependent中代碼塊使用的變量，否則依賴待定輸入參數的非必要變量；例如對于依賴關系樹T1={[12],[11]}，變量$_ARG_1為依賴待定輸入參數的必要變量，因為其在代碼塊[4]中被使用，變量$tmp7和$ans3則屬于非必要變量，因為其僅在T1中被使用。將依賴關系樹的各個結點重新合并成代碼段，具體為從依賴關系樹的末端葉結點開始，不斷將葉結點代碼塊的代碼段合并到其父結點的代碼段，并從樹中移除合并成功的葉結點，直至依賴關系樹只有一個根結點，此時依賴關系樹合并成功。

圖4展示了將依賴關系樹T={[12],[11],[4],[3]}合并至根結點[12]的過程：

圖4 依賴關系樹T合并至根節點的過程

若依賴關系樹合并成功，記原依賴關系樹為Torg，合并得到的依賴關系樹為Tfinal，Tfinal只有一個結點[root]final，對[root]final的代碼段進行函數匹配與綁定。

若匹配與綁定成功，則將[root]final從后端壓入逆向執行代碼塊隊列Bback；由于[root]final的代碼段在被執行后，Torg中所有的待定的變量均被確定，因此在進行下一輪逆推之前，需要將Torg中所有結點從Bdependent中移除，并更新Bdependent中其他代碼塊的待定變量，若其代碼段語法樹中使用了Torg中的待定變量，則將此待定變量改為確定變量。若失敗，則重新執行b-2，由代碼塊隊列B所逆推得到的函數體，如圖5中所示。

圖5 由 B逆推得到的函數體

預執行過程僅根據語句創建變量以保證參數環境正確而不進行實際的函數調用與運算，此過程中所有代碼最多只被執行一次，相較同時進行執行和推理，避免了一個問題可能被多次推理的可。

4 執行

此過程執行預執行生成的拓展代碼表。宏觀上程序仍由前向后執行，但由于逆向函數與正向函數的引入，局部代碼段的執行順序并不一定與宏觀上的執行順序一致。對于一個最長表達式對應的代碼段，執行時先正向依次執行其中的正向函數，再反向執行其中的逆向函數，如表1所示。

表1 包含正向、逆向函數調用的代碼段的執行順序示例

5 結語

本文所提出的編程語言COOL開創性地允許將復雜的表達式作為函數聲明，相較已有的邏輯編程語言擁有更強的數學表達能力，并可以描述更復雜的問題。COOL提供了利用函數正向執行過程進行逆向推理的功能，相較已有的邏輯編程語言，減輕了用戶逆推問題的負擔。COOL支持面向過程與面向對象，相較大多數的邏輯編程語言，規則的使用和管理更簡便。