ISSN 1349-127X (Online)
ISSB 1349-1261 (Paper)
http://www.math.kobe-u.ac.jp/raj

Risa/Asir Journal
Volume 3 (2009)

Editors
Nobuki Takayama (Managing editor)
Toshinori Oaku (Advisory editor)

Risa/Asir Journal will be a step to “Journal of Free Mathematical Software”.
We welcome not only articles related to Computer algebra system Risa/Asir,but also any articles on free mathematical software.
Please visit http://www.math.kobe-u.ac.jp/raj. All articles and attachedsoftware systems will be reviewed.

Risa/Asir Journal vol. 3 (2009), 1--16. 解説記事

Risa/Asir の QUOTE 型 ∗野呂 正行, 高山信毅
(神戸大理)

2010.03.20

Risa/Asir における柔軟な数式の取り扱いを実現するため, 木構造で表現された数式である FNODE 構造体を保持する QUOTE 型を扱えるようにしたのが 2005 年である. これを元に, 標準化をはじめとする QUOTE に対する種々の操作, およびパターンマッチング
による書き換えを実装したライブラリや簡単化のライブラリが実装されるようになってきた. この解説記事では QUOTE 型データの内部構造と共に, これらのライブラリを紹介したい.

1

Risa/Asir における数式の取り扱い

Risa/Asir においては, ユーザにより入力された数式は, いったん FNODE と呼ばれる木構造に変換されたのち, eval() により再帰的に正規内部表現 (Risa
オブジェクト) に変換される. Risa オブジェクトとは, 先頭に共通の識別子
フィールドを持つ一群の構造体であり, arf add() などのトップレベル演算
関数は, 受け取った構造体の識別子を見て, 適切な関数に振り分けるという操作を行う. Risa オブジェクトとしては, 数, 多項式, 有理式, リスト, 配列など
30 種類弱が定義されている. さらに, 数は, 有理数, 浮動小数, 有限体などさらに細かく分類される. いったん Risa オブジェクトに変換されてしまえば,それぞれ固有の方法により, 効率よい演算が適用できるが, 一方で, たとえば多項式が強制的に展開されてしまうなど, 本来の入力が持っていた情報が失われることもある. また, 原則として多項式の積は可換と仮定されているため,微分作用素など, 非可換な対象を扱う場合に不自然な操作を強いられて来た.
例 1 dx を ∂/∂x の意味に使おうと思っても[0] x*dx;
dx*x;∗ 本解説記事は数理研講究録 1514 (2005 年 11 月) の記事 “Risa/Asir における新しい形式の数式の取り扱いについて” (pp.229–235) を加筆修正したのものである.

1[1] dx*x;dx*x;のように, 勝手に順序が変えられてしまう.
また, 以前から指摘されている, Risa/Asir に式の簡単化機能が欠如している点についても, あらゆるものを多項式に変換してから簡単化するのは不自然である.
このような, 数式の柔軟な取り扱いは, Maxima, Maple, Mathematica などの得意とするところであり, これまでは, Risa/Asir の目指すところは, 多項式演算の高速処理であるとして, 特にこのような方向の開発は進めてこなかった. しかし, 使われ方が多様化した結果, より多様な数式の取り扱いが必要となる場面が多くなってきたため, より一般の数式の演算および簡単化, 書き換
え規則による書き換えの実装を目指し, 2005 年に QUOTE 型データ構造の導入を行った. その後 quote.rr(高山による. このファイル名はそのうち変更される), noro rewrite.rr, noro simplify.rr (野呂による), fj simplify.rr(藤本による) などの実験的ライブラリが asir-contrib [2] に含まれるようにな
り, 簡単化, 書き換え規則による書き換えの実装などが部分的に可能となった.
また TEX 形式への変換 (quotetotex, print tex form) なども QUOTE 型を用いて実装されている. この解説記事では QUOTE 型データの内部構造の解説
と共に, これらのライブラリの一部を紹介したい. ベキ関数などを含む式の簡単化を行う fj simplify.rr については, そのうち藤本による解説が書かれることと思う.

2

QUOTE の入力, 基本操作
前節で述べたように, Risa/Asir においては, 入力された数式は, Risa オブジェクトに変換される前に, FNODE と呼ばれる木構造で保持されている. このFNODE をボディ部に持つ Risa オブジェクトである QUOTE 型を定義した. これにより, 評価前の木構造を保持できる.
QUOTE 型に対する四則演算などの基本演算は, 木に対する操作として定義する. さらに, 木に対する一般的な操作 (属性, 子の取り出し, 木の再構成など) を Asir の関数として与えることで, ユーザによる数式の操作が可能とな
る. QUOTE 型に対する操作は, 実際には FNODE に対する操作である. FNODE は(id arg0 arg1 . . .)というリストで表現され, argi の個数, 型は id によりさまざまである. QUOTEの入力, 変換などの基本操作は次の通りである.

• QUOTE の入力

2

QUOTE は quote(Expr) または ‘Expr (バッククォートつき) により入力できる.
• QUOTE と Risa オブジェクトの相互変換
Risa オブジェクトから QUOTE を生成するのは objtoquote(Obj), 逆にQUOTE を評価して Risa オブジェクトを生成するのは eval quote(Expr)
で行う.
• QUOTE の分解, 合成
quote to funargs(Expr) は QUOTE Expr の FNODE の識別子 (fid, 後述), 引数をリストとして返す.
funargs to quote(List) は, その逆である.
例2[0] ctrl("print_quote",2)$[1] quote(1+x+y+x^2);(((1)+(x))+(y))+((x)^(2))
QUOTE 型データは上記のように print quote フラグを 1 か 2 にしないと, 表
示されない. 2 の時は上記のように内部形式を反映した形の中置表現で表示される. 1 の時は前置表現で表示される. たとえば上の例の場合は[b_op,+,[b_op,+,[b_op,+,[internal,1],[internal,x]],[internal,y]],[b_op,^,[internal,x],[internal,2]]]と表示される.

asir-contrib を読み込んだ状態では, 出力関数が print input form (S) の戻り値を表示するようになるため, 上の例では次のような出力を得る.
(asir-contrib)[1355] quote(1+x+y+x^2);
quote(1+x+y+x^2)
なおこの出力関数の変更は set print function でおこなっている. asir-contrib では names.rr で出力関数を print input form に変更している.
asir-contrib を読み込んだ状態で, 読まない状態での出力を見たい場合は, 下の例のように rtostr 関数を用いて表示させるとよい.

(asir-contrib)[1355] ctrl("print_quote",2);[1356] rtostr(quote(1+x+y+x^2));(((1)+(x))+(y))+((x)^(2))

3

以下この解説で asir-contrib の出力を掲載する場合は (asir-contrib) と明
示する.

QUOTE の分解と合成の機能はプログラミングをする場合基礎的となる. このためには, quote to funargs と funargs to quote を用いる.
例 3 [0] ctrl("print_quote",2);

2[1] A=quote(1+x+x^2);((1)+(x))+((x)^(2))[2] B=quote_to_funargs(A);[0,<...quoted...>,(1)+(x),(x)^(2)][3] get_function_name(B[1]);+[4] B=ltov(B);[ 0 <...quoted...> (1)+(x) (x)^(2) ][5] B[3] = quote(x^5);(x)^(5)[6] funargs_to_quote(vtol(B));((1)+(x))+((x)^(5))[7] type(B[1]);23この例では quote to funargs で得られたリストを作り替えてから, funargs to quote
で QUOTE 型に戻して x2 を x5 に置き換えた式を作っている.
上の例のように, quote to funargs は QUOTE をリストの形式で戻す. 戻り
値は [fid, op, arg1, arg2, ...] または [fid, arg1, arg2, ...] なる形式をしている. op 名を知るには関数 get function names を用いる (この名前は将来変更される予定である).

fid の値は以下のとおり (noro simplify.rr より).
#define I_BOP 0#define I_COP 1#define I_AND 2#define I_OR 3#define I_NOT 4#define I_CE 5#define I_PRESELF 6#define I_POSTSELF 7#define I_FUNC 8#define I_FUNC_OPT 9#define I_IFUNC 10
4

#define I_MAP 11#define I_RECMAP 12#define I_PFDERIV 13#define I_ANS 14#define I_PVAR 15#define I_ASSPVAR 16#define I_FORMULA 17#define I_LIST 18#define I_STR 19#define I_NEWCOMP 20#define I_CAR 21#define I_CDR 22#define I_CAST 23#define I_INDEX 24#define I_EV 25#define I_TIMER 26#define I_GF2NGEN 27#define I_GFPNGEN 28#define I_GFSNGEN 29#define I_LOP 30#define I_OPT 31#define I_GETOPT 32#define I_POINT 33#define I_PAREN 34#define I_MINUS 35#define I_NARYOP 36
意味は名前から大体推測できると思う. たとえば[0] ctrl("print_quote",2)$[1] quote_to_funargs(quote(1 && 2));
[2,1,2]であり, 最初の 2 は I AND の値である.
例4

QUOTE の分解と合成には quote to funargs と funargs to quote を用いるのが王道であるが, より簡便な方法として quotetolist 関数を用いることも可能である. この関数は QUOTE 型データをリストに変換する. リス
トに変換することにより失う情報もあるが, QUOTE を利用するための簡便なインタフェースを与えている. なお, asir-contrib には逆を与える関数 (文字列を戻す) quote input form quote list が含まれており, 下の例のように

eval str を組み合わせて元の QUOTE に近いものを復元できる.
5

(asir-contrib)[1364] A=quote(1+x+x^2);
quote(1+x+x^2)[1365] L=quotetolist(A);[b_op,+,[b_op,+,[internal,1],[internal,x]],[b_op,^,[internal,x],[internal,2]]][1366] S=quote_input_form_quote_list(L);
1+x+x^2[1367] eval_str("quote("+S+")");
quote(1+x+x^2)
パッケージ noro simplify.rr にはこれらの関数を利用して余分な括弧を取り去る関数の実装例 (remove paren) がある.

(asir-contrib)[1160] A=noro_simplify.remove_paren(quote(f(1-(x))));
quote(f(1-x))[1161] print_input_form(A);quote(f(1-x))
この例では f (1 − (x)) が f (1 − x) に簡単化されている.
下記は remove paren のコードの一部である.

def remove_paren0(Q,Top){
FA = quote_to_funargs(Q);if ( FA[0] == I_PAREN ) {Arg = remove_paren0(FA[1],1);if ( Top || is_monomial(Arg) )return Arg;
else
return funargs_to_quote([FA[0],Arg]);}else{ 以下省略. }}たとえば Q に quote( (f(x)) ) が入っていると, FA[0]=34=I PAREN であり, FA[1]=quote(f(x)) である. Arg には quote(f(x)) が入る. Top が 1であると, 結局 (f(x)) の外側の括弧が除去されて quote(f(x)) が戻り値となる.

QUOTE のための述語がいくつか用意されている.
• qt is var(Expr) は Expr が不定元に対応する QUOTE なら 1 を戻す.
• qt set coef(Expr) Expr (リスト) で与えられた不定元を変数とする
有理関数体を係数とする.

6

• qt is coef(Expr) は Expr が係数として設定されている有理関数体に属するとき 1 を戻す.
簡単化のプログラムではこれらの述語を活用している.
以上の機能の応用として書かれた asir-contrib の関数を二つ紹介しておく.

1. print tex form は引数を TEX が受け付ける文字列に変換する関数である.
[1355] A=quote((x+alpha)^2/(beta+x+x^2));quote((x+alpha)^2/(beta+x+x^2))[1356] print_tex_form(A);\frac{ ( ( {x}+ \alpha))^{ 2} } { (\beta+ {x}+{x}^{ 2} )}2. 藤本により書かれた simplify (この名前は fj simp.simplify へ変更
される予定) は, 非負実数を引数にもつ巾関数等の簡単化を行なう.
[1357] load("fj_simplify.rr");[1437] simplify((x^(1/3)+y^(1/3))*x^(-1/3)*exp(2*x)*exp(-2*x));((y)^(1/3))*((x)^(-1/3))+1

3

QUOTE の OpenXM による通信
QUOTE を push cmo でサーバに送出すると, quote to funargs の戻り値に似た形のデータが送出される. たとえば quote(1+2) では CMO のリストをもちいて, [ [asir,b_op],+,1,2] が送出される. asir, b op, + は CMOの文字列として送出され, 1, 2 は CMO の整数として送出される. QUOTE のOpenXM での扱いの実装はまだ不完全で, このデータから QUOTE を再構成する関数は実装されていない.
いまのところ quotetolist, quote input form quote list, eval str を用いるのが, 簡便であろう.

4

パターンマッチと非可換代数のための QUOTE の
機能
以上が QUOTE の基本機能であるが, 以下では, パターンマッチと非可換代数への応用を念頭において作成された基礎関数群の解説を行う. サンプルプ
ログラム等は asir-contrib [2] の noro rewrite.rr に含まれている.

7

4.1

FNODE の標準形

FNODE に対するパターンマッチング, 書き換えを容易に行うために, FNODEに対する標準形を定義した. 標準形の計算は qt normalize(Expr[,M ode])
で行う. M ode は後述する展開モード指定である.

nf
sum of monom
monom
nf powf ormula: f ormula | f unctor (nf [, . . .]) | sum of monom: monom [+ · · ·]: [f ormula ∗ ] nf pow [∗ · · ·]: nf | nf nf: Risa object

おおざっぱにいえば, 標準形 nf とは, 標準形のベキ積の Risa オブジェクト
係数つきの和である. ここで, 和は FNODE としては, n 項和として表現され,和を構成する単項式は, ある全順序により整列される. また, 積も n 項積として表現される. すなわち, 標準形は, 入力された数式が, Risa オブジェクトを係数環とする結合代数の元であると見なし, 和の可換性, 積の結合性によりフラットに整理しなおしたものである.
例5[278] ctrl("print_quote",1)$/* FNODE をリストで表示 */[279] ‘(x+y+z);[u_op,(),[b_op,+,[b_op,+,[internal,x],[internal,y]],[internal,z]]][280] qt_normalize(‘(x+y+z));[n_op,+,[internal,x],[internal,y],[internal,z]]2 項演算で表現された式が, 標準形では n 項和で表現されていることが分かる.
これは, Mathematica における標準形 [4] と基本的に同じであるが, 積の可換性を仮定していないこと, および, 係数環をより一般的にしてある点で異なっている1 . さらに, 標準形への変換時に, 積に関する分配則を利用して展開された標準形を得ることもできる.
例6[289] ctrl("print_quote",2)$ctrl(‘‘print_quote’’,2)$/* FNODE を式で表示 */[290] qt_normalize(‘(x+y)^2);((x)+(y))^(2)[291] qt_normalize(‘(x+y)^2,1);((x)^(2))+((x)*(y))+((y)*(x))+((y)^(2))
1 Mathematica において積の Orderless 属性を外すことで, 積を非可換にできるが, 簡単化
において異常な挙動を示すようになる (Ver. 4). Ver. 5 では, 係数まで非可換になる.

8

4.2

項順序および係数体の設定

単項式順序および係数体は可変であり, それぞれ次のような関数が用意されている.

• 単項式順序の設定
標準形中の単項式順序は, 指定がない場合には, システムが決める不定元および関数子の順序から誘導される辞書式順序が適用される. その際,
関数呼び出しは, 単なる不定元より順序が上で, 関数子が等しい場合には引数が辞書式に比較される. qt set ord(V arList) により, V arListに現れる不定元を先頭とし, のこりをシステムが決めるという順序が設定される.

• 係数体の設定
デフォルトでは係数体は数のみからなるが, いくつかのパラメタを係数体の元として扱いたい場合, qt set coef(P aramList) により指定できる. P aramList に指定されたパラメタは, 係数体である可換な有理関数体の不定元として扱われる.
例7[304] qt_normalize(‘(b*x+a*y)*b*y,1);((a)*(y)*(b)*(y))+((b)*(x)*(b)*(y))[305] qt_set_coef([a,b])$[306] qt_normalize(‘(b*x+a*y)*b*y,1);((b^2)*(x)*(y))+((b*a)*((y)^(2)))/* a,b が係数体に入った; x*y > y^2 */[307] qt_set_ord([y,x])$[308] qt_normalize(‘(b*x+a*y)*b*y,1);((b*a)*((y)^(2)))+((b^2)*(x)*(y))/* y^2 > x*y */5

パターンマッチングによる書き換え

Risa/Asir においては, 不定元とプログラム変数は明確に区別されている.
そこで, パターン変数としてプログラム変数を用いることにした. すなわちパターンとは, プログラム変数を含んでもよい QUOTE である. これに対し, いく
つかの書き換え関数を用意した.

• nqt match(Expr,P atten[,M ode])
QUOTE 式 Expr とパターン P attern がマッチしたら 1 を返す. さらに,
P attern 中に含まれるプログラム変数にマッチした値が実際に代入される.

9

• nqt match rewrite(Expr,Rule,M ode)
Rule は [P attern,Action] または [P attern,Condition,Action] である.
この関数は, Expr が P attern にマッチしたら, Action が評価され, その値が返される. その際, Action 中のパターン変数が, マッチした値に置き換えられる. Condition が指定されている場合には, Condition 中のパターン変数が同様に置き換えられ評価され, 0 でない場合に Actionが評価される. マッチしない場合には Expr そのものが返される.
例8[318] nqt_match(‘x*y*z-3*u,‘X*Y+Z);
1[319] [X,Y,Z];[x,(y)*(z),(-3)*(u)][320] nqt_match_rewrite(‘x*y*z,[‘X*Y,‘X+Y],1);((y)*(z))+(x)いずれも実行前に引数が標準形に変換されるが, M ode はその際に展開を行うかどうかを指示する. マッチングにおいては, 最初にマッチした時点の情報が返される2 . Condition および Action にはユーザ定義関数を含めることができる. これにより, 複雑な書き換え規則を書くことができ, また書き換え規則の数を少なく押えることができる. 現状では, Mathematica で可能な, パターン変数にマッチする型の指定ができないため, Condition において型判定を行うことになる. このため, QUOTE に対するいくつかの型判定関数を用意した. これらを用いて, 書き換え規則集合を与えて, 書き換え規則が適用でき
なるなるまで書き換えを続ける関数 qt rewrite(Expr,Rules,M ode) をユーザ関数として記述した.
例 9 (sl2 の展開環)[225] load("noro_rewrite.rr")$[336] Rsl=[[‘h*e,‘e*h+2*e],[‘h*f,‘f*h-2*f],[‘e*f,‘f*e+h]]$0sec(7e-06sec)[337] qt_rewrite(‘e*f^2,Rsl,2);((f)*(f)*(e))+((2)*(f)*(h))+((-2)*(f))
1.776e-15sec(0.008608sec)[338] qt_rewrite(‘h*e^3,Rsl,2);((e)*(e)*(e)*(h))+((6)*(e)*(e)*(e))

2 現状では実装が不完全であり, 同一パターン変数が複数現れるパターンに対してはマッチン
グに失敗する場合がある.

10

6FNODE の順序づけ
今回の実装の目的は, ユーザが気軽に書き換え規則を与えて, 一般に非可換な代数における計算を気軽に試せるような環境を作ることである. 与えられた
書き換え規則の停止性, あるいは合流性に関しては, 項書き換え系の研究者による研究が膨大にあるが, ここでは深入りはしない. ここでは, 無限ループに陥らないような実用的な指針として, FNODE に対する順序づけおよび weightの使用を提案する. この方法は後述するように多項式環や微分作用素環で用いられる weight ベクトルの考え型の自然な一般化であり, 理論的にも興味深い.
例として, 可換性を定義する場合を考える. 数学的には, 任意の X, Y に対し XY = Y X でよいが, たとえばこのまま [‘X ∗ Y, ‘Y ∗ X] という書き換え
規則を書くともちろん停止しない. この場合, 最も安直な解決方法の一つは,

FNODE 間に全順序を入れて, 書き換えた場合に順序が大きくなる場合にのみ書
き換えを行うという方法である. この場合, 積を構成する有限個の FNODE の
並べ変えの中で最も順序が上のものに到達すると停止する. もちろん, Action
が複雑な場合にはこのように簡単には行かないが, 書き換えの方向性を示すものとして全順序を与えることは有効であろう. よって, 書き換え規則に応じて, 全順序をどう選ぶかが問題である.

6.1

FNODE の weight と書き換え

一般に FNODEf の weight w(f ) を

1. f が leaf の場合, 適当な値を与える. 特に係数の weight は 0.
2. f が node の場合, 識別子に応じた関数の, f の子の weight 値を引数とする値をとる.
により再帰的に決めることができる. 和に対しては max(), 積に対しては和,ベキに対しては積を用いると, 次のようになる.

1. w(f + g) = max(w(f ), w(g))
2. w(f g) = w(f ) + w(g)3. w(f n ) = nw(f )以下では, このような weight を有限生成の自由結合代数に対する書き換えに応用することを考える.
係数環を K の上で z1 , . . . , zn , h で生成される自由結合代数 A を

Khz1 , . . . , zn , hiと書く. h を必要に応じて zn+1 と書くこともある.

11

定義 1 A での書き換え規則 (または関係式, 左辺は必ず単項式)

L1 → R1 , . . . , Lm → Rm
が, 同次化 weight ベクトル H について, 同次的書き換え規則であるとは, Ri
が 0 であるかまたは,

degH (Li ) = degH (Ri の任意の項)が成立することである.

Q
Q
ここで degH ( ziei ) は ziei の weight H についての (非可換性を無視した)次数である. つまりXY
e i HidegH ( ziei ) =と定義する (i は重複してあらわれることもある).
例 10

z2 z1 → z1 z2 + h2 , hzi → zi h
は H = (1, 1, 1) についての同次的書き換え規則である. この例は x = z1 , ∂ =z2 とした 1 変数の同次化 Weyl 代数にほかならない.
以下 H のすべての成分は正であると仮定し固定する. また x1 , . . . , xn , hからなるワードに対する well order Â を以下ひとつ固定する. 出現する書き換え規則はとくにことわらない限り全て H について同次的書き換え規則である.
例 11 前の例の書き換え規則z2 z1 → z1 z2 + h2 , hzi → zi hにさらに

z2p+1 → 0, z1 z2 → ph2を加えた規則の集合を Rp と書く. ここで p は自然数である. Rp は H =(1, 1, 1) についての同次的書き換え規則である.
定義 2 n 次元の weight ベクトル w ∈ Rn が同次的書き換え規則 {Li → Ri }および Â について有効 weight ベクトル (admissible weight vector) であるとは次の条件をみたすことである. 以下 w̃ = (w, 0) (h に対する weight を 0にしたもの) とおく.

1. degw̃ (Li ) ≥ degw̃ (Ri )2. 左辺と右辺が同じ w-weight をもつときは 右辺で左辺と同じ w-weightを持つ項たちは順序 Â でかならず小さい.

12

書き換え規則がある正数ベクトル H について同次的であることから, これらの条件により書き換えが停止性をもつことが分かる. さらに次の命題が成り立つ.
命題 1 ワードを正規な形 z1p1 · · · znpn hpn+1 まで書き換える書き換え規則が含まれていると仮定する. このとき次が成り立つ.

1. Reduction(割り算) が多項式環のままの形で成立する.
2. G-algebra [3] の条件のうち, well order の存在条件が成り立たないような書き換え規則に対しても, 有効 weight ベクトルが存在するならば, hを加える斉次化, h を 1 とおくことによる非斉化により, グレブナー基底を計算できるようになる.
この応用に際しては, 与えられた書き換え規則に対し, 有効 weight ベクト
ルを見つける必要がある. この weight に応じて, 書き換え規則の右辺を斉次化すれば, 同次的書き換え規則が得られる.
現在の実装においては, weight ベクトルが設定されない限り, weight による比較は行わない. 関数 qt set weight() により一部の不定元に対して weightが設定されると, 他の不定元の weight は 0 とした weight 比較後に現在設定されている単項式順序が適用される.
例 12[300] qt_set_ord([z1,z2,h])$[301] qt_set_weight([[z1,-1],[z2,1]])$[302] Rule1=[[‘h*z1,‘z1*h], [‘h*z2,‘z2*h], [‘z2*z1,‘z1*z2+h^2]] $[303] Rule2=[[‘z2*z2,‘0], [‘z1*z2,‘h^2]]$[304] F=‘z2^2*(h^2+z1^2)$[305] qt_rewrite(F,Rule1,2);((z2)*(z2)*(h)*(h))+((z1)*(z1)*(z2)*(z2))+((4)*(z1)*(z2)*(h)*(h))+((2)*(h)*(h)*(h)*(h))
注意 1 有効 weight ベクトルが負の成分をもつと非斉次化したあとの reduc-tion の停止性はいえない.

7

書き換え規則の例
以下に, 書き換え規則の例をいくつか紹介する.

例 13 (可換性)[246] qt_normalize(‘(x+y-z)^2,1);((x)^(2))+((x)*(y))+((-1)*(x)*(z))+((y)*(x))+((y)^(2))+((-1)*(y)*(z))+((-1)*(z)*(x))+((-1)*(z)*(y))+((z)^(2))

13

[247] Rcomm=[[‘X*Y,‘nqt_comp(Y*X,X*Y)>0,‘Y*X]]$[248] qt_rewrite(‘(x+y-z)^2,Rcomm,1);((x)^(2))+((2)*(x)*(y))+((-2)*(x)*(z))+((y)^(2))+((-2)*(y)*(z))+((z)^(2))
nqt comp() は比較関数である.
例 14 (外積代数)[249] Rext0=[‘X*Y,‘qt_is_var(X) && qt_is_var(Y) && nqt_comp(Y,X)>0,‘-Y*X]$[250] Rext1=[‘X^N,‘eval_quote(N)>=2,‘0]$[251] Rext2=[‘X*X,‘0]$[252] Rext=[Rext0,Rext1,Rext2]$[253] qt_set_coef([a,b,c])$[254] qt_rewrite(‘(a*x+b*y+c*z)*(b*x+c*y+a*z)*(c*x+a*y+b*z),Rext,1);(-a^3+3*c*b*a-b^3-c^3)*(x)*(y)*(z)行列式の計算に相当する. 変数の積を交代的に書き換える規則を定義している.
例 15 (微分)[255] qt_set_coef([a])$[256] Rd1=[‘d(X+Y),‘d(X)+d(Y)]$[257] Rd2=[‘d(X*Y),‘d(X)*Y+X*d(Y)]$[258] Rd3=[‘d(N),‘qt_is_coef(N),‘0]$[259] Rd=[Rd1,Rd2,Rd3]$[260] qt_rewrite(‘d((x+a*y)^2),Rd,1);(d((x)^(2)))+((a)*(d(x))*(y))+((a^2)*(d((y)^(2))))+((a)*(d(y))*(x))+((a)*(x)*(d(y)))+((a)*(y)*(d(x)))
例 16 (Weyl 代数)

def member(V,L) {for ( I = 0; L != [] && V != car(L); L = cdr(L), I++ );return L==[] ? -1 : I;}
def qt_weyl_vmul(X,K,Y,L) {extern WeylV, WeylDV;
if ( member(X,WeylV) >= 0 || member(Y,WeylDV) >= 0 ) return Y^L*X^K;
if ( WeylV[I=member(X,WeylDV)] != Y ) return Y^L*X^K;
else {
K = eval_quote(K); L = eval_quote(L); M = K>L?L:K;
for ( T = 1, I = 0; I <= M; T = idiv(T*K*L,I+1), I++, L--, L-R += T*Y^L*X^K;
14)

return R;}}[256] WeylV=[‘x,‘y,‘z]$[257] WeylDV=[‘dx,‘dy,‘dz]$[258] qt_set_ord(map(eval_quote,append(WeylV,WeylDV)))$[259] Rweyl=[[‘X^K*Y^L,‘qt_is_var(X)&&qt_is_var(Y)&&nqt_comp(Y,X)>0,‘qt_weyl_vmul(X,K,Y,L)]]$[260] qt_rewrite(‘((x*dy+y*dx)^2),Rweyl,1);(((x)^(2))*((dy)^(2)))+((2)*(x)*(y)*(dx)*(dy))+((x)*(dx))+(((y)^(2))*((dx)^(2)))+((y)*(dy))
Action にユーザ定義関数を用いることにより, Weyl 代数の書き換え規則を一つにまとめている.

8

まとめ

Risa/Asir における数式の中間的表現である FNODE をユーザ言語から操作するためのインタフェースを実装した. これにより, 式を入力したままの形で保存するなどの公式集的な利用, 式の簡単化, TEX 形式への変換などが可能となり, asir-contrib に徐々にライブラリが整備されてきた. さらに, ユーザが定義する書き換え規則による数式の書き換えが可能となった. 書き換えの効率についてはほとんど考慮できていない. 特に, 標準形への変換と書き換えを並行して行うことが必要と考えており, 今後の課題の一つである. また, パ
ターンマッチング自体もまだ完全なものとはいえず, 改良すべき点が多くある. 目的に応じた標準的な書き換え規則集合をデフォルトで提供することも必要である.
この書き換えと weight ベクトルによる単項式比較を組み合わせることにより, 自由結合代数における一般的な書き換えの停止性を論じた. ここで提案した一般化は Weyl 代数の同次化の理論を含む. Risa/Asir で新しく導入した,

QUOTE に対する一般的な weight ベクトルのメカニズム qt_set_weight によりわれわれの理論とアルゴリズムのプロトタイプを容易に試すことが可能である. V. Levandovskyy [3] は G-algebra の概念を導入して, Singular に実装したが, われわれの概念は同次化をとおして, non-well order の一部も含む.
われわれのアプローチにより, G-algebra より広い範囲の algebra を扱うことが可能となる. 一般的な枠組みの応用として, 将来的には D-加群のアルゴリ
ズムを拡張し, Calderon-Moreno 等の導入した algebra を局所的に扱うなどの応用が見込まれる.

15

参考文献
[1] Asir の実験的な関数 (マニュアル).
http://www.math.kobe-u.ac.jp/OpenXM[2] asir-contrib は /usr/local/OpenXM/lib/asir-contrib の下にインストールされている.
ソースコードの場合 OpenXM/src/asir-contrib/packages/src の下にある.
[3] V. Levandovskyy, Non-commutative Computer Algebra for Polynomial
Algebras: Gröbner Bases, Applications and Implementation. Dissertation, Universität Kaiserslautern (2005).
[4] S. Wolfram, The MATHEMATICA Book, Fourth Edition. Cambridge
University Press (1999).

16