一種計算機代數系統的設計與實現

汪 明

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

0 引言

計算機代數是一門主要研究符號計算算法的學科，它所運算的基本對象是符號，而不是數值。[1]這里的符號可以看作變量，用以表示數學領域中的眾多對象，如實數、復數、多項式、方程、函數、微積分和矩陣等。而數值計算處理的基本對象是數值，由于計算機內部數值是采用浮點類型進行表示的，因此，在運算過程中會出現結果不精確的情況。由于計算機代數系統可以對數學公式進行自動推導，也可以求解某些方程的精確解，因此，在科研和工程計算中都發揮著至關重要的作用。

通過對國內外相關資料進行整理發現，國外對于計算機代數系統的研究起步較早，約始于20世紀60 年代，經過幾十年的研究積累，創造了在業界享有盛譽的產品，如Maple、Mathematica 和Matlab。目前，國內對于計算機代數系統的研究還處于初級階段，很多學者的研究都是基于計算機代數系統的應用研究，而對其內部技術原理的研究較為鮮見。[2]

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

1 計算機代數系統設計

1.1 系統功能設計

開發一個功能完備、運行穩定的計算機代數系統是非常大的工程，除了需要具備計算機領域的專業知識外，還需要對數學領域的相關理論比較熟悉。

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

圖1 系統的總體功能設計示意圖

1.1.1 解析器模塊

實現DSL 語言的詞法、語法和語義分析，并構建抽象語法樹（Abstract Syntax Tree，AST）。

1.1.2 化簡模塊

可基于多種化簡規則實現對表達式的化簡操作。一般來說，在經過多次遞歸的符號計算過程后，計算結果會出現多層嵌套的現象，且不夠簡潔。而化簡后，可讓結果看起來更加直觀。

1.1.3 展開模塊

實現對表達式的展開操作，特別是對多個表達式的乘法進行展開得到多項式。

1.1.4 求導模塊

實現對表達式的求導操作，它是一個遞歸方法，內部將常見的求導規則進行逐條歸納，并支持復合函數的求導處理。

1.1.5 極限模塊

實現對表達式的求極限操作，與求導模塊類似，內部需要歸納多個極限規則，并支持復合函數的極限處理。

1.1.6 泰勒級數模塊

實現對表達式的泰勒級數展開操作，內部基于求導模塊，可根據參數實現N 階泰勒級數展開。

1.1.7 積分模塊

實現對表達式的不定積分操作，不定積分比求導復雜得多，主要理由有兩點：首先，不定積分的推導規則非常多（需維護一個符號積分表）；其次，很多不定積分推導規則涉及條件判斷，有的不定積分甚至需要借助復雜的算法才能求解。

1.1.8 打印模塊

實現對抽象語法樹的文本打印操作，它會遞歸解析語法樹，并根據規則輸出文本格式，其中的難點是對括號的優化，它需要根據運算符的優先級和結合性，來盡量減少括號的嵌套。

1.1.9 繪圖模塊

實現對表達式的繪圖操作，目前對2D 圖形支持較好，內部可對表達式進行解析，并用循環生成離散的二維數據，借助XPlot 庫實現2D 圖形的繪制，它會生成HTML 格式的圖形數據，之后返回到前端并顯示。

1.1.10 求值模塊

實現對表達式的求值操作，如計算sin（3）*cos（7）的值。下面給出主要功能模塊對應的函數設計說明，具體如表1 所示。

表1 系統主要功能函數

1.2 領域特定語言設計

領域特定語言指的是專注于某個應用程序領域的計算機編程語言。對于計算機代數系統而言，設計與實現一種可處理數學表達式的編譯器是一個關鍵和難點。[2]一般來說，數學領域的公式sin（x^2）-x 可以看作是一個表達式，而表達式可以被計算機代數算法處理，比如對兩個表達式進行四則運算，或者對其進行求導和化簡。表達式主要由以下要素組成：符號變量、常數和操作符。符號變量本質是一個字符串，類似于編程語言中的變量。常見的變量為：α、β、x、y。常數可以表示數值（如7、3.0、3.5），也可以表示數學常量（如e）。操作符包括中綴運算符和前綴運算符，中綴運算符如+、-、*、/；前綴運算符可以看作是一種數學函數的應用，如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 解析器設計

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

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

表2 操作符的解析規則

表2 中的exp 操作符上一行的...表示省略號，而不是操作符。F#語言支持用type 關鍵字自定義復合數據類型，結合語法1 給出的BNF 語法描述，下面給出F#語言對數學表達式類型的定義。

代碼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

利用設計的解析器可以將數學表達式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 模式匹配算法

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

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

語法2：

// Match Expression

match expression with

| rule1Left [ when condition1 ] -> rule1Right

| rule2Left [ when condition2 ] -> rule1Right2

|...

從語法2 可知，F#模式匹配中還提供了可選的when 條件判斷支持，這樣就可以更加靈活地對匹配規則進行細節處理。

計算機代數系統中所涉及的數學表達式自動推導，從本質上來說，都需要事先定義好相關的推理規則。當然，這個推理規則需要結合前面的DSL語義規則以及解析器來定制。下面給出符號計算模式匹配算法：

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

（2）遍歷系統內基于抽象語法樹構建的推理規則表T，利用F#的模式逐條進行規則匹配；

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

（4）如果匹配的RR 中無待遞歸的函數，則返回當前結果。否則，返回第（1）步。

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

首先，給出3 條基于抽象語法樹構建的求導規則：

（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）經解析器解析后，生成的抽象語法樹為：

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

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

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

由于右部表達式中有Diff（Pow（Var "x"，Const 2.0），Var "x"），則繼續執行求導過程，匹配規則（2）的左部，其中的參數m 值為2.0，參數e 為Var "x"，并返回規則（2）的右部，替換參數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"）

））

由于右部表達式中有Diff（Var "x"，Var "x"），因此繼續執行求導過程，匹配規則（3）的左部，并返回規則（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

））

此時的表達式無Diff 函數的調用，因此返回。上述表達式經打印處理后為：

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

上述算法適用于符號計算中的求導、求積分、求極限、化簡、打印以及其他基于規則的功能模塊。

2 系統實驗分析

2.1 系統運行環境

基于F#語言實現計算機代數系統，需要一定的軟硬件環境。下面給出系統運行的軟硬件平臺配置，如表3 所示。

表3 實驗軟硬件平臺參數

2.2 系統效果分析

為了驗證系統能否對數學表達式進行正確的自動推導，下面分類別給出多個測試題，并將系統推理的結果和SymPy 求出的正確結果進行對比分析。

如果推理結果二者一致，則評價為正確，此時在系統測試評價表的評價一欄中打勾。具體實驗對比分析結果如表4 所示。

表4 系統測試評價表

下面給出本計算機代數系統的交互Web 界面，其中的計算結果會轉換成LaTeX 文本格式，Web 端利用KaTeX 庫進行渲染呈現，交互界面如圖3 所示。

圖3 系統交互Web 界面圖

通過實驗對比分析可知，只要是系統中對符號計算規則進行了歸納，系統就可以自動且正確求出數學表達式的推導結果，由此可說明本文所探討的技術路線是可行的，且系統運行效果良好。

3 結語

通過實驗發現，基于F#強大的模式匹配能力和FParsec 庫實現的解析器，可以對數學表達式進行符號計算。當前，本計算機代數系統還相對初級，功能并不完備，但其中的設計思想和技術路線是可行的。

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