韓濟澎，李陳志航

(北京華規(guī)科技有限公司技術(shù)部 北京 100081)

0 引言

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

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

1 語法

1.1 函數(shù)

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

代碼 1 函數(shù)聲明示例：

@add(a,b){

return:a+b;

}

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

代碼2返回表達式的函數(shù)示例：

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

return:(a+b)*c;

}

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

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

代碼3具有權(quán)重的函數(shù)示例：

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

a = b;

}

1.2 變量

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

代碼4“out”使用示例：

new:a = 1;

{

new:a=0;

a=out:a+1;

}

1.3 完整代碼示例

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

代碼5完整代碼示例：

/*定義求解二次方程的函數(shù)*/

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

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

}

/*定義加法的逆向函數(shù)*/

@(10){$a+b}{

a=ans-b;

}

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

new:a = x+y;

$x+1==y;

new:z=0;

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

return:a+x+z;

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

new:x = 0;

new:y = 3;

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

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

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

1.4 類

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

代碼6類繼承示例

system:MainProcess<

……

}

2 編譯

2.1 預編譯

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

2.2 代碼類型

通過詞法分析程序與語法分析程序?qū)㈩A編譯后的代碼編譯為字符碼。字符碼由三部分組成，包括代碼類型標志位、四元式、四元式參數(shù)類型標志位數(shù)組。

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

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

3 預執(zhí)行

3.1 加載字符碼

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

3.2 推理過程

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

（1）初始化

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

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

（2）第k輪匹配

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

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

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

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

圖2 表達式語法樹形成環(huán)狀結(jié)構(gòu)示例

因此每當代碼替換后都需要查找并刪除代碼段中脫離表達式語法樹的代碼片段并展開生成的環(huán)狀結(jié)構(gòu)。

（3）匹配結(jié)束條件

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

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

圖3展示了在預執(zhí)行結(jié)束后表達式與函數(shù)的綁定情況。

圖3 代碼段21預執(zhí)行后表達式與函數(shù)的綁定效

3.3 推導函數(shù)

當代碼類型標志為“推導函數(shù)”時，利用指定的正向函數(shù)推導逆向函數(shù)的函數(shù)實現(xiàn)，依次執(zhí)行以下步驟：

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

代碼塊，由序號、代碼段、代碼塊信息組成，越早創(chuàng)建的代碼塊序號越?。淮a塊信息包括：代碼塊類型，反映代碼段中代碼的類型；代碼塊依賴待定輸入?yún)?shù)標志位，反映代碼段中是否存在依賴待定輸入?yún)?shù)的變量。變量依賴于待定輸入?yún)?shù)，指的是在正向執(zhí)行函數(shù)體代碼的過程中，確定待定輸入?yún)?shù)的值是確定此變量的值的必要條件，反之則獨立于待定輸入?yún)?shù)。

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

（2）利用代碼塊推導逆向函數(shù)的執(zhí)行過程

a將B中的代碼塊根據(jù)是否依賴待定輸入?yún)?shù)，重組為依賴待定輸入?yún)?shù)代碼塊隊列Bdependent，和獨立于待定輸入?yún)?shù)代碼塊隊列Bindependent，重組的兩個隊列中代碼塊根據(jù)序號從小到大排列；b當Bdependent不為空時，通過動態(tài)規(guī)劃算法進行逆推。

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

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

圖4 依賴關(guān)系樹T合并至根節(jié)點的過程

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

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

圖5 由 B逆推得到的函數(shù)體

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

4 執(zhí)行

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

表1 包含正向、逆向函數(shù)調(diào)用的代碼段的執(zhí)行順序示例

5 結(jié)語

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