$Id: tr.oxt,v 1.29 2005/05/04 05:42:12 taka Exp $
$OpenXM: OpenXM/src/asir-contrib/testing/tr-ja.oxt,v 1.8 2005/05/04 05:47:03 takayama Exp $

注意: testing/tr.rr では quote を quotetolist で list に変換して扱うため,
      下の仕様とはことなり, list 型でデータを戻す場合も多い.
      ユーザ言語で書いている関係上 pn(x) を pn("x") としている. 
      他にも同様な関数があり.

このファイルから texi ファイルを作成するには以下のように入力して下さい.
oxgentexi は OpenXM/src/util の下にあります.

nkf -e tr.oxt | oxgentexi --noSorting --title 'Term rewriting functions for Risa/Asir' --author 'Nobuki Takayama' >t.texi

begin: AAA01|

@c ---------------------------------------------------------
@section 変数パターンと関数パターン


変数パターン

pn(x)                    任意のものにマッチ. マッチしたものを x に bind.
pn(x,qt_is_integer(x))

Todo; fn は多分いらない. qt_is_function(x) で OK.
fn(f)                    任意の関数にマッチ. マッチした関数名を f に bind.
fn(f,pn(x),pn(y))        任意の関数にマッチ. マッチした関数名を f に bind.
                         f の引数を x, y に bind               


パターンは quote で与える.
予約語  tr.and, tr.or, tr.not  はパターンのマッチに関して論理演算をおこなう.
たとえば
quote(tr.and(pn(x,"qt.is_integer"),pn(x,"qt.is_non_negative",x)))
は x が 整数で - が先頭についていない場合マッチする.

end:

begin: AAA011|

@c ---------------------------------------------------------
@section 実装のための補助関数

@itemize @bullet
@item @code{quotetolist}, @code{listtoquote}, @code{listtoquote_str}
   quote と list の間の変換.
@item @code{quote_to_funargs}, @code{funargs_to_quote}, @code{get_function_name}
  quote と funarg 形式の変換. 実験的関数のマニュアルを参照.
@item @code{quotetoobj}, @code{eval_quote}
   quote と object の間の変換.
@item @code{quote_input_form}, @code{ctrl("print_quote",1)},
   quote と文字列の間の変換.
@item @code{quote_flatten}
   実験的関数のマニュアルを参照.
@end itemize

end:

begin: AAA02|

@section quote に対する基本関数  (module qt の関数)

end:


begin: qt.node(Q)
 quote データ {Q} の node を取り出す.
 example: qt.node(quote(1+2*3))     
        ["b_op","+"]  (現在の実装ではこれが戻る)
end:


begin: qt.nchild(Q)
 quote データ {Q} の 子供の数を戻す.
 example: qt.nchild(quote(1+2*3))     2 を戻す.
end:


begin: qt.child(Q,K)
 quote データ {Q} の {K} 番目の子供を戻す.
 example: qt.child(quote(1+2*3),1)     quote(2*3) を戻す.
 example: qt.child(quote(1+2*3),0)     quote(1) を戻す.
end:

begin: hoge|
@c --------------------------------------------------------------------
@section quote に対する述語
end:

begin: qt.is_integer(Q)
 quote データ {Q} が整数なら 1
 example: qt.is_integer(quote(0))     
end:

begin: qt.is_dependent(Q,x)
 quote データ {Q} が不定元 {x} を含むと 1, 含まないと 0.
 example: qt.is_dependent(quote(1+1/x),x)
end:

begin: qt.is_function(Q)
 quote データ {Q} が関数のとき 1, そうでないとき 0.
 example: qt.is_function(f(x,y));
end:

begin: qt.is_minus(Q)
 quote データ {Q} が形式的に -1 より始まるとき 1.
 example: qt.is_minus(quote(-1/x));
 ref: qt.add_paren, qt.add_paren0
end:

begin: qt.is_rational(Q)
 quote データ {Q} が形式的に有理数の時 1.
 example: qt.is_rational(quote(1/2));
 ref: qt.cancel_number
end:

begin: hoge2|
@c --------------------------------------------------------------------
@section quote に対するコンストラクタ
end:

begin: qt.zero()
 quote 0 を戻す.
end:

begin: qt.id(Qobj)
 quote object {Qobj} をそのまま戻す.
end:

begin: qt.replace(Qobj,[[x,Valuex],[y,Valuey],...])
   quote object {Qobj} の中の x を Valuex, y を Valuey, ... に置き換えた
   quote object を戻す.
   description:
    課題; x, y は大文字も許すか? @var{Qobj} も元々含まれている大文字を評価して置き換える
    関数も必要か?

   example: qt.replace(quote(sin(x*@pi)), [[x,quote( (2*t+3) )]])
end:

   qt.replace は asir-contrib の base_replace と似た機能.
   quote の内部に大文字ではじまる変数(評価する)が書けないため.

begin: qt.parenthesis(Qobj)
   quote object {Qobj} の中の括弧が足りないときには補い, 多いときには取り去った
   quote object を作る.
   +, *, /, ^, - 等について asir の文法での演算子の強さを仮定する.
  description:
  参考;  
   @itemize
   @item まだ書いてない.
   @item noro_simplify.rr  の @code{noro_simplify.remove_paren()} 
      がすでに実現づみ?
        (加える方はだめみたい)
         @code{flatten()} や @code{quote_to_funargs()} を利用してる模様.
   @item 実験的関数マニュアルの @code{quote_flatten} も参照 (この関数ない).
   @end itemize

end:

begin: qt.eval(Qobj,type)
   Qobj を asir の他の object に変換.
  description:
   @code{eval_quote()} がすでに実現づみ.
   実装してない.

end:

begin: qt.qt(Obj)
   asir の Obj を quote 型に変換.  
   description:
     @code{objtoquote()} がすでに実現づみ.  実装してない.

end:

begin: qt.cancel_number(Q)
   Quote {Q} の中で有理数があれば通分する.
   ref: qt.is_rational
end:

begin: qt.add_paren(Q)
  +- があれば ( ) を加える. まだ bug いり.
  description: Taylor 展開を計算するために作った.
end:

begin: qt.add_paren0(Q)
  無条件に {Q} を ( ) する.
end:


begin: qt003|
@c --------------------------------------------------------------------
@section tr その他
end:

begin: qt.vars(Q)
 {Q} に現れる変数を戻す.
 description: @code{vars(Obj)} の qt 版.
 example:
  [2306] qt.vars(objtoquote((x-y-1)^4/z+y^q));
  [x,y,z,q]
end:

begin: qt.etov_pair(Q)
 {Q} に p^q の形の元を探して [p,q] をリストにして戻す.
 description:  
   @itemize  @bullet
   @item @code{dp_etov} の類似を作るための準備(2005/05/04).
   @end itemize
 example:
[2410] ctrl("print_quote",1);
1
[2411]  qt.etov_pair(quote(3*x^4*y^(-3)));
[[[internal,y],[u_op,(),[u_op,-,[internal,3]]]],[[internal,x],[internal,4]]]
end:

begin: tr|

@c --------------------------------------------------------------------
@section tr (term rewriting) のトップレベルの関数 (module tr の関数)

end:

begin: tr.match0(Qobj,P)
 quote データ {Qobj} が パターン {P} に適合すれば 1 を戻し, そうでなければ 0
 を戻す. 
 example: tr.match0(quote(1+2*3),quote(pn(x)+pn(y)))        
                 x に quote(1), y に quote(2*3)           
          tr.match0(quote(1+2*3),quote(pn(x)+pn(y,"qt.is_integer",y)))
                 qt.is_integer(2*3) は 0 なので y にはマッチしない.
end:

begin: pn(X)
  pn(x) は任意の quote object にマッチし, 名前 x をつける.
description:
  tr.match0(quote(1+2*3),quote(pn(x)+pn(y)))  は 1 を戻すが,
  tr.match0(quote(1+2*3),quote(pn(x)+pn(y,tr.is_integer,x))) は 0 をもどす.
  2*3 は integer から作られた fnode ではあるが integer ではないので qt.is_integer
  が 0 を戻すため.
end:
                 
begin: tr.match0_act(Qobj,P,Act)
 quote データ {Qobj} が パターン {P} に適合すれば {Act} を呼び出しその値を戻す.
 パターン {P} にマッチしないときは 0.

 example: tr.match0_act(quote(1+2*3),quote(pn(x)+pn(y)),[myadd,x,y])                   
end:

begin: tr.or_match0_act(Qobj,Rules)
end:

begin: tr.apply_rule1(Qobj,P,Act)
 quote データ {Qobj} の木を幅優先探索し, 
 パターン {P} に適合するものがあるときは {Act} を呼び出しその値を戻す.
 つまり top node が {P} に適合するか調べ, 適合しない場合はその子供に
  tr.apply_rule1 を適用する (ここが tr.match_act とは異なる). 
 マッチしない場合は Qobj をそのまま戻す (これが再帰的に適用される).

description:
 ここで sin_int(X) は X が integer の時は quote(0) を戻し,
 そうでないときは quote(sin(X*@@pi)) を戻す.
 深さ優先で書き換えをするには 関数 sin_int の中でまた tr.apply_rule1 を呼び出せば
 よい.

 example: tr.apply_rule1(quote(1+sin(2*@pi)),quote(sin(pn(x)*@pi)),[sin_int,x])
end:


begin: tr.apply_or_rules(Qobj,Rules)
 quote データ {Qobj} の木を幅優先探索し, 
 ルール {Rules} に適合するものがあるときはルールに記述された action を
 呼び出す. {Rules} には複数のルールを書くことが一つでも適用可能なルールが
 あれば再帰的に呼び出される.

end:

begin: hoge4|
@section tr 内部関数
end:

begin: tr.apply_function0(Qobj,BindingTable)
end:

begin: tr.rp(Qobj,P,A)
end:

begin: tr.make_binding(Qobj,P)
end:


begin: zzz00|

@section 例題

end:

begin: zzz01|
例題  sin(整数*@@pi) を 0 に.
example:
   /* 準備 */
   extern P,A;
   P=quote(sin(pn(x)*@pi));  /* パターン */
   A=[sin_int,x]             /* action, action 関数 */ 
   def sin_int(X) {
     X = tr.apply_rule1(X,P,A); /* 子供に [P,A] を再帰的に適用 */  
     if (qt.is_integer(X)) return qt.zero();
     else qt.replace(sin(y*@pi),[[y,X]]);  /* sin(x*@pi) をそのまま戻す.*/ 
   }

   /* 計算 */
   Qobj=quote(1+sin(sin(2*@pi)*@pi)*sin((1/2)*@pi));
   tr.apply_rule1(Qobj,P,A);
end:
   
@c ------------------------------------------------------
@section 例題 Mathematica の N[ ] 相当の関数をユーザが書けるように.

begin: zzz02|
例題 Mathematica の N[ ] 相当の関数をユーザが書けるように.
example:
    nn(sin(cos(@pi)+sqrt(2))) 
    --> nn(sin(nn(cos(nn(@pi)))+nn(sqrt(nn(2)))))
   Prog; test1-tr.rr の test4().

  qt.map_arg 関数を用いる.
  def test4() {
    Rule=[quote(nn(pn(f))),["qt.map_arg",nn,f]];
    /* nn で囲まれたものがあれば, nn をその内部に再帰的に apply する */
    R0 = quote(nn(sin(1/2)*cos(1/3)));
    print(print_input_form(R0));
    R=tr.apply_rule1(R0,Rule[0],Rule[1]);
    return R;
  }

end:

@c ---------------------------------------------------------
@section 例題  不定積分

begin: zzz03|
例題  不定積分
example:
   /* integral(f+g) => integral(f)+integral(g) */
   S1=[quote(integral(pn(f)+pn(g))),
       [int_linear1,f,g]];
   def int_linear1(X,Y) {
      return qt.replace(quote(integral(f)+integral(g)),[[f,X],[g,Y]]);
   }

   /* integral(c*f) => c*integral(f) */
   def qt.independent(F,X) { return !qt.dependent(F,X); }
   S2=[quote(integral(pn(c,"qt.independent",c,x))*f)),
       [int_linear2,c,f]];
   def int_linear2(X,Y) {
      return qt.replace(quote(c*integral(f)),[[c,X],[f,Y]]);
   }

   apply_or_rules(quote(integral(a*x^2+x+2/x)),[S1,S2]);
   これをこれ以上書き換えが起きないまで繰り返す.
   このルールの場合答えは
   a*integral(x^2)+integral(x)+integral(2/x);   

   quote(integral(x^pn(n))) --> x^(n+1)/(n+1) or log(x) を書く.
end:

@c ---------------------------------------------------------
@section 例題  簡単な構文解析

begin: zzz04|sortKey: zzz04
description:

例題  簡単な構文解析

example:
   式(expression) は 式+式 | 式*式 | (式) | 整数

   extern R1,R2,R3,R4,S1,S2,S3,S4;
   /* 文法を満たすかどうかの check 用. Action 部は 1 か 0 */
   R1=[quote(pn(x,is_expression(x))+pn(y,is_expression(y))), 1];
   R2=[quote(pn(x,is_expression(x))*pn(y,is_expression(y))), 1];
   R3=[quote((pn(x,is_expression(x)))), 1];
   R4=[quote(pn(x,qt.is_integer(x))), 1];
   def is_expression(Qobj) {
     R = [R1,R2,R3,R4];
     A = apply_or_match0(Qobj,R);
     if (A == 0) return 0; else return 1;
   }

   /* 計算用. R1,R2,R3,R4 と左は共通. */
   S1=[quote(pn(x,is_expression(x))+pn(y,is_expression(y))), [myadd,x,y]];
   S2=[quote(pn(x,is_expression(x))*pn(y,is_expression(y))), [mymul,x,y]];
   S3=[quote((pn(x,is_expression(x)))), ["qt.id",x]];
   S4=[quote(pn(x,qt.is_integer(x))), ["qt.id",x]]; 

   def eval_expression(Qobj) {
     S = [S1,S2,S3,S4];
     return apply_or_rules(Qobj,S);
   }

   def myadd(X,Y) {
     return qt.qt(qt.eval(X,1)+qt.eval(Y,1));
   }

   def mymul(X,Y) {
     return qt.qt(qt.eval(X,1)*qt.eval(Y,1));
   }

   /* 計算 */
   tr.eval_expression(quote(1+2*(3+15)));
end:

begin: misc|

@section 考え方についての概説

 トップレベルの関数達.  (stylesheet の考えに似てる.)

  iterator の一種.

  yacc に似てる.

@section デバッガー

  選択すべきルールが沢山あるときは, 警告する機能.

  無限ループの|検出.

end:

begin: exp|

@c ------------------------------------------------
@section 実験的関数

end:

begin: qt.map_arg(F,Q)
 関数 F を quote データ {Q} の すべてのノードに再帰的に
 apply した quote データを戻す.
 example: qt.map_arg(nn,quote(sin(@pi)+2/3))
           nn(nn(sin(nn(@pi)))+nn(nn(2)/nn(3)))
end:

begin: todo|

@section  Todo

@subsection ユーザ定義の中置演算子

   tfb の書き方を導入.

@subsection 数学よりの例題

数学的におもしろい例題をなるべく沢山用意する.
これらの例題に対して tr が試作品を作るのに有効であるということをいう.

 例; gcd 計算の多項式 reduction を tr で実現.

 例; 冪級数の計算を quote で実現.
        sort や expand は組み込みで.

 例; Mathematica の Expand[], Toghether[] 相当のもの.

 例; D の掛け算を パターンマッチで実現.  
    holonomic 関数を係数とする微分作用素環での計算.

 例; (x^(1/n))^n --> x 等.

 例; 記号微分と微分環での計算.
       y''+xy=0,  y''=y^2+x 等.  index 付きの変数生成が必要. idxtov

 例; QE, 論理式.

 例; 外積代数. 

 例; 岩波, 応用数学, 神保のソリトンの本にあるような fermion 等の例.


 例;
   Bergman, George M.
   The diamond lemma for ring theory.
   Advances in Math. 29 (1978), no. 2, 178--218.
   にあるような非可換代数の例.

end:

begin: new-functions|

@section   まだスケッチのみの関数仕様

  qt.ltor, qt.rtol ; 木の構造の変換; 例 (x*y)*z --> x*(y*z)

end:

begin: idx|

@subsection Index つき変数

end:

begin: idxtov(X,I)
  idxtov({X},{I}) は変数 {X}_{I} を戻す.
  {I} はスカラーかリスト.
 example:
  idxtov(x,i)  は x_i を戻す. 
 description:
  idxtov(x,[i,j])  は x_i_j を生成.  x_i_i の index (idx) 属性 を [i,j] に. 

  @code{util_v()} とほぼ同じ.

  x_i の index (idx) 属性 を i に. 
  base_name 属性を  x に.
  不定元の属性を利用することにより高速に index をとりだせて index つき変数の
  代りができる.

end:

begin: vtoidx(X)
  vtoidx(x_i) は [x,i] を戻す. 
description:
  @code{util_index()} とほぼ同様.
  
 属性の検索なので高速. idx 属性が無い場合は i を設定.

  idxtov 関数は 関数名にも使えるようにする? --> 微分環対応.

  qt.function(名前, 引数) --> quote(名前(引数)) を生成.  
   index 付き関数は微分環の取扱に必要.
end:

begin: powerSeries|

@subsection 冪級数, dp の pretty print.

  巾級数の取扱, dp の pretty print のため.
  qt.qttodp(Qobj | vlist,  order?)  quote から dp を作る. 
       exponent が数でないと作れず.
  qt.dptoqt(Qobj | vlist)  dp から quote を作る.  vlist は属性で対応?

  qt.expand, qt.sort, qt.ht, qt.rest, qt.mtov も基礎関数として欲しい.

end:

begin: MonomialSimplifier|

@subsection モノミアルを標準形へ (builtinで?)

example:
  x^1 --> x   
  (x*y)*(z*t) --> x*y*z*t
  x*2*y*4     --> 8*x*y      (指定した変数以外は可換とする)
  x*x^3       --> x^4
  x*(-y)*z    --> -x*y*z
  ((x))       --> x   これは noro_simplify.rr noro_simplify.remove_paren() が対応
 

end:

4/15 夜.  実装は明日講義の準備の終了後か?
begin: qt.gtlex(f,g)
{f} は {g} より quote tree の lex order で大きい.
description:
  quote tree の lex order は次のように決める.  
  @itemize
  @item 不定元は不定元の順序.
  @item 不定元より +, - , *, /, ^ 等の node は大きい.
        たとえば x < power(x,2)  (power(x,2) は x^2 の意味)
  @item あとは再帰的. times(x,y) < power(x,y) だが,
        times(x,y) と times(p,q) は x と p の比較,  これできまらないなら,
        y, q の比較.
  @end itemize

end:

begin: qt.dtoq(F,V)
分散表現多項式 {F} を quote に変換する.
{V} は変数リスト.
description:
 @itemize @bullet
 @item 変数リストが空のときは x_1, x_2, ... を用いる.
 @item Changelog. 2005/4/21
 @end itemize
example:
  F=dp_ptod((x-y-z)^3,[x,y]);
  qt.dtoq(F,[]);
  quote(x_1^3+(-3)*x_1^2*x_2+3*x_1*x_2^2+(-1)*x_2^3+(-3*z)*x_1^2
       +6*z*x_1*x_2+(-3*z)*x_2^2+3*z^2*x_1+(-3*z^2)*x_2+(-z^3))
ref: qt.qtod 
end:

begin: qt.qtod(F,V)
quote {F} を 分散表現多項式に変換する.
{V} は変数リスト.
description:
 変数リストが空のときは x_1, x_2, ... を用いる.
ref: qt.qtod 
end: