第五代編程語言設(shè)計(jì)與實(shí)現(xiàn)

韓濟(jì)澎，李陳志航

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

0 引言

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

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

1 語法

1.1 函數(shù)

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

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

@add(a,b){

return:a+b;

}

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

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

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

return:(a+b)*c;

}

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

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

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

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

a = b;

}

1.2 變量

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

代碼4“out”使用示例：

new:a = 1;

{

new:a=0;

a=out:a+1;

}

1.3 完整代碼示例

求解以下數(shù)學(xué)問題：對兩個(gè)數(shù)字量x，y依次進(jìn)行以下操作：將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值以默認(rèn)方式輸出*/

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

1.4 類

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

代碼6類繼承示例

system:MainProcess<

……

}

2 編譯

2.1 預(yù)編譯

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

2.2 代碼類型

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

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

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

3 預(yù)執(zhí)行

3.1 加載字符碼

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

3.2 推理過程

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

（1）初始化

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

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

（2）第k輪匹配

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

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

圖1 分支脫離表達(dá)式語法樹示例

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

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

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

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

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

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

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

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

3.3 推導(dǎo)函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 執(zhí)行

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

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

5 結(jié)語

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