一種計(jì)算機(jī)代數(shù)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

汪 明

（孔智科技（徐州）有限公司 研發(fā)部，江蘇 徐州 221118）

0 引言

計(jì)算機(jī)代數(shù)是一門主要研究符號計(jì)算算法的學(xué)科，它所運(yùn)算的基本對象是符號，而不是數(shù)值。[1]這里的符號可以看作變量，用以表示數(shù)學(xué)領(lǐng)域中的眾多對象，如實(shí)數(shù)、復(fù)數(shù)、多項(xiàng)式、方程、函數(shù)、微積分和矩陣等。而數(shù)值計(jì)算處理的基本對象是數(shù)值，由于計(jì)算機(jī)內(nèi)部數(shù)值是采用浮點(diǎn)類型進(jìn)行表示的，因此，在運(yùn)算過程中會出現(xiàn)結(jié)果不精確的情況。由于計(jì)算機(jī)代數(shù)系統(tǒng)可以對數(shù)學(xué)公式進(jìn)行自動推導(dǎo)，也可以求解某些方程的精確解，因此，在科研和工程計(jì)算中都發(fā)揮著至關(guān)重要的作用。

通過對國內(nèi)外相關(guān)資料進(jìn)行整理發(fā)現(xiàn)，國外對于計(jì)算機(jī)代數(shù)系統(tǒng)的研究起步較早，約始于20世紀(jì)60 年代，經(jīng)過幾十年的研究積累，創(chuàng)造了在業(yè)界享有盛譽(yù)的產(chǎn)品，如Maple、Mathematica 和Matlab。目前，國內(nèi)對于計(jì)算機(jī)代數(shù)系統(tǒng)的研究還處于初級階段，很多學(xué)者的研究都是基于計(jì)算機(jī)代數(shù)系統(tǒng)的應(yīng)用研究，而對其內(nèi)部技術(shù)原理的研究較為鮮見。[2]

從文獻(xiàn)上來看，計(jì)算機(jī)代數(shù)系統(tǒng)的研究始于James Slagle 創(chuàng)建的Saint 程序，它能夠?qū)瘮?shù)進(jìn)行簡單的積分[3]，在此基礎(chǔ)上，Moses Joel 改進(jìn)了Saint 程序的算法，并建立了一個可以進(jìn)行符號積分的程序SIN[4]。1960 年，Anthony C.Hearn 基于Lisp 語言開發(fā)了一款名為Reduce 的計(jì)算機(jī)代數(shù)系統(tǒng)。[5-6]1968 年，麻省理工學(xué)院的Carl Engleman和Moses Joel 等人開發(fā)了Macsyma 系統(tǒng)。[7]1980年，滑鐵盧大學(xué)研究人員基于C 語言開發(fā)了Maple系統(tǒng)。[4，8]1982 年，William Schelter 開始對Macsyma系統(tǒng)進(jìn)行分支，并命名為Maxima 系統(tǒng)。1986 年，Stephen Wolfram 用C 語言實(shí)現(xiàn)了Mathematica 系統(tǒng)。[9]1989 年，MathWorks 公司發(fā)布了Matlab 中的Symbolic Math Toolbox 工具箱，可以執(zhí)行微分、積分、化簡、變換和方程求解。[10]2006 年，Ondrˇej Cˇertík 基于Python 語言開發(fā)了SymPy 計(jì)算機(jī)代數(shù)系統(tǒng)。2007 年，Waldek Hebisch 基于Axiom 系統(tǒng)分支出了FriCAS 系統(tǒng)，并持續(xù)進(jìn)行開發(fā)和改進(jìn)。

1 計(jì)算機(jī)代數(shù)系統(tǒng)設(shè)計(jì)

1.1 系統(tǒng)功能設(shè)計(jì)

開發(fā)一個功能完備、運(yùn)行穩(wěn)定的計(jì)算機(jī)代數(shù)系統(tǒng)是非常大的工程，除了需要具備計(jì)算機(jī)領(lǐng)域的專業(yè)知識外，還需要對數(shù)學(xué)領(lǐng)域的相關(guān)理論比較熟悉。

本文設(shè)計(jì)的計(jì)算機(jī)代數(shù)系統(tǒng)重點(diǎn)是探索符號計(jì)算相關(guān)的可行技術(shù)路徑，并不完全覆蓋某一個數(shù)學(xué)領(lǐng)域的所有推導(dǎo)規(guī)則。為了方便軟件的部署，這里采用B/S 架構(gòu)，用戶可以通過瀏覽器與系統(tǒng)進(jìn)行交互，客戶端和服務(wù)器通過Ajax 技術(shù)進(jìn)行數(shù)據(jù)通信。另外，系統(tǒng)基于F# SDK 進(jìn)行開發(fā)。F#是微軟推出的一種開源免費(fèi)的函數(shù)式編程語言，語法類似于OCaml。它可以非常方便地實(shí)現(xiàn)特定領(lǐng)域語言（Domain Specific Language，DSL），并進(jìn)行模式匹配，以達(dá)到數(shù)學(xué)表達(dá)式解析和執(zhí)行的目的。計(jì)算機(jī)代數(shù)系統(tǒng)的總體功能設(shè)計(jì)示意圖見圖1。

圖1 系統(tǒng)的總體功能設(shè)計(jì)示意圖

1.1.1 解析器模塊

實(shí)現(xiàn)DSL 語言的詞法、語法和語義分析，并構(gòu)建抽象語法樹（Abstract Syntax Tree，AST）。

1.1.2 化簡模塊

可基于多種化簡規(guī)則實(shí)現(xiàn)對表達(dá)式的化簡操作。一般來說，在經(jīng)過多次遞歸的符號計(jì)算過程后，計(jì)算結(jié)果會出現(xiàn)多層嵌套的現(xiàn)象，且不夠簡潔。而化簡后，可讓結(jié)果看起來更加直觀。

1.1.3 展開模塊

實(shí)現(xiàn)對表達(dá)式的展開操作，特別是對多個表達(dá)式的乘法進(jìn)行展開得到多項(xiàng)式。

1.1.4 求導(dǎo)模塊

實(shí)現(xiàn)對表達(dá)式的求導(dǎo)操作，它是一個遞歸方法，內(nèi)部將常見的求導(dǎo)規(guī)則進(jìn)行逐條歸納，并支持復(fù)合函數(shù)的求導(dǎo)處理。

1.1.5 極限模塊

實(shí)現(xiàn)對表達(dá)式的求極限操作，與求導(dǎo)模塊類似，內(nèi)部需要?dú)w納多個極限規(guī)則，并支持復(fù)合函數(shù)的極限處理。

1.1.6 泰勒級數(shù)模塊

實(shí)現(xiàn)對表達(dá)式的泰勒級數(shù)展開操作，內(nèi)部基于求導(dǎo)模塊，可根據(jù)參數(shù)實(shí)現(xiàn)N 階泰勒級數(shù)展開。

1.1.7 積分模塊

實(shí)現(xiàn)對表達(dá)式的不定積分操作，不定積分比求導(dǎo)復(fù)雜得多，主要理由有兩點(diǎn)：首先，不定積分的推導(dǎo)規(guī)則非常多（需維護(hù)一個符號積分表）；其次，很多不定積分推導(dǎo)規(guī)則涉及條件判斷，有的不定積分甚至需要借助復(fù)雜的算法才能求解。

1.1.8 打印模塊

實(shí)現(xiàn)對抽象語法樹的文本打印操作，它會遞歸解析語法樹，并根據(jù)規(guī)則輸出文本格式，其中的難點(diǎn)是對括號的優(yōu)化，它需要根據(jù)運(yùn)算符的優(yōu)先級和結(jié)合性，來盡量減少括號的嵌套。

1.1.9 繪圖模塊

實(shí)現(xiàn)對表達(dá)式的繪圖操作，目前對2D 圖形支持較好，內(nèi)部可對表達(dá)式進(jìn)行解析，并用循環(huán)生成離散的二維數(shù)據(jù)，借助XPlot 庫實(shí)現(xiàn)2D 圖形的繪制，它會生成HTML 格式的圖形數(shù)據(jù)，之后返回到前端并顯示。

1.1.10 求值模塊

實(shí)現(xiàn)對表達(dá)式的求值操作，如計(jì)算sin（3）*cos（7）的值。下面給出主要功能模塊對應(yīng)的函數(shù)設(shè)計(jì)說明，具體如表1 所示。

表1 系統(tǒng)主要功能函數(shù)

1.2 領(lǐng)域特定語言設(shè)計(jì)

領(lǐng)域特定語言指的是專注于某個應(yīng)用程序領(lǐng)域的計(jì)算機(jī)編程語言。對于計(jì)算機(jī)代數(shù)系統(tǒng)而言，設(shè)計(jì)與實(shí)現(xiàn)一種可處理數(shù)學(xué)表達(dá)式的編譯器是一個關(guān)鍵和難點(diǎn)。[2]一般來說，數(shù)學(xué)領(lǐng)域的公式sin（x^2）-x 可以看作是一個表達(dá)式，而表達(dá)式可以被計(jì)算機(jī)代數(shù)算法處理，比如對兩個表達(dá)式進(jìn)行四則運(yùn)算，或者對其進(jìn)行求導(dǎo)和化簡。表達(dá)式主要由以下要素組成：符號變量、常數(shù)和操作符。符號變量本質(zhì)是一個字符串，類似于編程語言中的變量。常見的變量為：α、β、x、y。常數(shù)可以表示數(shù)值（如7、3.0、3.5），也可以表示數(shù)學(xué)常量（如e）。操作符包括中綴運(yùn)算符和前綴運(yùn)算符，中綴運(yùn)算符如+、-、*、/；前綴運(yùn)算符可以看作是一種數(shù)學(xué)函數(shù)的應(yīng)用，如sin，cos，sqrt。下面給出DSL 語言的BNF語法描述（語法1）。

語法1：

:：=

| "（" "）" | |

:：= "+" | "-" | "*" | "/" | "^"

:：= "sin" | "cos" | "tan" | "cot" |"sec"

| "csc" | "ln" | "..." | "exp"

：：= |

:：= | '.'

：：= |

：：= "Pi" | "..." | "E" | I | PosiInfinity | NegInfinity

:：= | |

：：= "a" |"..." | "z" | "A" |"..." |"Z"

:：= "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9"

1.3 解析器設(shè)計(jì)

有了DSL 語法定義后，下一步的核心工作就是對解析器進(jìn)行設(shè)計(jì)。這里基于FParsec 庫，可對多個語法解析器進(jìn)行組合，從而形成快速處理數(shù)學(xué)表達(dá)式的解析器。

FParsec 庫中的OperatorPrecedenceParser 實(shí)例對象，具有AddOperator 方法，可以讓用戶自行設(shè)置操作符的解析規(guī)則。下面給出操作符的解析規(guī)則說明，具體如表2 所示。

表2 操作符的解析規(guī)則

表2 中的exp 操作符上一行的...表示省略號，而不是操作符。F#語言支持用type 關(guān)鍵字自定義復(fù)合數(shù)據(jù)類型，結(jié)合語法1 給出的BNF 語法描述，下面給出F#語言對數(shù)學(xué)表達(dá)式類型的定義。

代碼1：

type Expr =

| Const of float | Var of string

| Add of Expr * Expr | Subt of Expr * Expr

| Prod of Expr * Expr | Div of Expr * Expr

| Pow of Expr * Expr | Sin of Expr

| Cos of Expr | Tan of Expr | Sec of Expr

| Cot of Expr | Csc of Expr

| ArcSin of Expr | ArcCos of Expr

| Exp of Expr | Ln of Expr | Neg of Expr

| Diff of Expr * Expr

|...

| E | Pi | I | PositiveInfinity | NegativeInfinity

利用設(shè)計(jì)的解析器可以將數(shù)學(xué)表達(dá)式sin（x^2）+log（3×y）-5 解 析 為：Subt（Add（Sin（Pow（Var "x"，Const 2.0）），Log（Prod（Const 3.0，Var "y"））），Const 5.0）。為了更直觀地展示，下面給出解析過程示意圖（見圖2）。

圖2 解析過程示意圖

1.4 模式匹配算法

當(dāng)用戶輸入文本命令后，解析器會對文本進(jìn)行語義解析，并返回抽象語法樹。為了讓計(jì)算機(jī)能自動進(jìn)行公式推理，還需要對抽象語法樹進(jìn)行模式匹配，最終根據(jù)事先定義的推理規(guī)則求出符號計(jì)算的結(jié)果。

F#本身提供了功能非常強(qiáng)大的模式匹配算法功能，可以對表達(dá)式進(jìn)行模式匹配。下面給出F#模式匹配的語法，如語法2 所示。

語法2：

// Match Expression

match expression with

| rule1Left [ when condition1 ] -> rule1Right

| rule2Left [ when condition2 ] -> rule1Right2

|...

從語法2 可知，F(xiàn)#模式匹配中還提供了可選的when 條件判斷支持，這樣就可以更加靈活地對匹配規(guī)則進(jìn)行細(xì)節(jié)處理。

計(jì)算機(jī)代數(shù)系統(tǒng)中所涉及的數(shù)學(xué)表達(dá)式自動推導(dǎo)，從本質(zhì)上來說，都需要事先定義好相關(guān)的推理規(guī)則。當(dāng)然，這個推理規(guī)則需要結(jié)合前面的DSL語義規(guī)則以及解析器來定制。下面給出符號計(jì)算模式匹配算法：

（1）模塊M 從外部獲取抽象語法樹AST；

（2）遍歷系統(tǒng)內(nèi)基于抽象語法樹構(gòu)建的推理規(guī)則表T，利用F#的模式逐條進(jìn)行規(guī)則匹配；

（3）依次取出當(dāng)前推理規(guī)則R 中的左部RL和右部RR，如果RL 匹配AST，則解析出匹配各參數(shù)的值，并替換到RR 中；

（4）如果匹配的RR 中無待遞歸的函數(shù)，則返回當(dāng)前結(jié)果。否則，返回第（1）步。

為了便于對該算法的理解，下面結(jié)合diff（sin（x^2），x）的求導(dǎo)過程來說明：

首先，給出3 條基于抽象語法樹構(gòu)建的求導(dǎo)規(guī)則：

（1）Diff（Sin（e），Var "x"） → Prod（Cos（e），Diff（e，Var "x"））

（2）Diff（Pow（e，Const m），Var "x"） → Prod（Prod（m，Pow（e，Const（m-1））），Diff（e，Var "x"））

（3）Diff（Var "x"，Var "x"）→Const 1

diff（sin（x^2），x）經(jīng)解析器解析后，生成的抽象語法樹為：

Diff（Sin（Pow（Var "x"，Const 2.0）），Var "x"）

其次，遍歷求導(dǎo)規(guī)則表，匹配規(guī)則（1）的左部，其中的參數(shù)e 匹配值Pow（Var "x"，Const 2.0），返回規(guī)則（1）的右部，并替換參數(shù)e，即：

Prod（Cos（Pow（Var "x"，Const 2.0）），Diff（Pow（Var "x"，Const 2.0），Var "x"））

由于右部表達(dá)式中有Diff（Pow（Var "x"，Const 2.0），Var "x"），則繼續(xù)執(zhí)行求導(dǎo)過程，匹配規(guī)則（2）的左部，其中的參數(shù)m 值為2.0，參數(shù)e 為Var "x"，并返回規(guī)則（2）的右部，替換參數(shù)m 和e，即：

Prod（Cos（Pow（Var "x"，Const 2.0）），

Prod（Prod（Const 2.0，Pow（Var "x"，Const（2.0-1））），

Diff（Var "x"，Var "x"）

））

由于右部表達(dá)式中有Diff（Var "x"，Var "x"），因此繼續(xù)執(zhí)行求導(dǎo)過程，匹配規(guī)則（3）的左部，并返回規(guī)則（3）的右部Const 1，即：

Prod（Cos（Pow（Var "x"，Const 2.0）），

Prod（Prod（Const 2.0，Pow（Var "x"，Const（2.0-1））），

Const 1

））

此時的表達(dá)式無Diff 函數(shù)的調(diào)用，因此返回。上述表達(dá)式經(jīng)打印處理后為：

cos（x^2）*2*x^（2-1）*1 →cos（x^2）*2*x

上述算法適用于符號計(jì)算中的求導(dǎo)、求積分、求極限、化簡、打印以及其他基于規(guī)則的功能模塊。

2 系統(tǒng)實(shí)驗(yàn)分析

2.1 系統(tǒng)運(yùn)行環(huán)境

基于F#語言實(shí)現(xiàn)計(jì)算機(jī)代數(shù)系統(tǒng)，需要一定的軟硬件環(huán)境。下面給出系統(tǒng)運(yùn)行的軟硬件平臺配置，如表3 所示。

表3 實(shí)驗(yàn)軟硬件平臺參數(shù)

2.2 系統(tǒng)效果分析

為了驗(yàn)證系統(tǒng)能否對數(shù)學(xué)表達(dá)式進(jìn)行正確的自動推導(dǎo)，下面分類別給出多個測試題，并將系統(tǒng)推理的結(jié)果和SymPy 求出的正確結(jié)果進(jìn)行對比分析。

如果推理結(jié)果二者一致，則評價為正確，此時在系統(tǒng)測試評價表的評價一欄中打勾。具體實(shí)驗(yàn)對比分析結(jié)果如表4 所示。

表4 系統(tǒng)測試評價表

下面給出本計(jì)算機(jī)代數(shù)系統(tǒng)的交互Web 界面，其中的計(jì)算結(jié)果會轉(zhuǎn)換成LaTeX 文本格式，Web 端利用KaTeX 庫進(jìn)行渲染呈現(xiàn)，交互界面如圖3 所示。

圖3 系統(tǒng)交互Web 界面圖

通過實(shí)驗(yàn)對比分析可知，只要是系統(tǒng)中對符號計(jì)算規(guī)則進(jìn)行了歸納，系統(tǒng)就可以自動且正確求出數(shù)學(xué)表達(dá)式的推導(dǎo)結(jié)果，由此可說明本文所探討的技術(shù)路線是可行的，且系統(tǒng)運(yùn)行效果良好。

3 結(jié)語

通過實(shí)驗(yàn)發(fā)現(xiàn)，基于F#強(qiáng)大的模式匹配能力和FParsec 庫實(shí)現(xiàn)的解析器，可以對數(shù)學(xué)表達(dá)式進(jìn)行符號計(jì)算。當(dāng)前，本計(jì)算機(jī)代數(shù)系統(tǒng)還相對初級，功能并不完備，但其中的設(shè)計(jì)思想和技術(shù)路線是可行的。

未來，需要引入更多的推導(dǎo)規(guī)則和符號計(jì)算算法，特別是不定積分的規(guī)則。下一步研究的重點(diǎn)工作有以下兩個方面：一方面，可以參考Mathematica 的積分庫Rubi[11，12]，其規(guī)則大約有5000 條；另一方面，對于Rubi 規(guī)則庫不能求出的積分，可引入Risch 算法[13]進(jìn)行求解。