%% $OpenXM: OpenXM/doc/OpenXM-specs/cmo-basic1.tex,v 1.1.1.1 2000/01/20 08:52:46 noro Exp $
//&jp \section{ 数, 多項式 の  CMO 表現 }
//&eg \section{ CMOexpressions for numbers and polynomials }

/*&C
@../SSkan/plugin/cmotag.h
\begin{verbatim}
#define     CMO_MONOMIAL32  19
#define     CMO_ZZ          20 
#define     CMO_QQ          21
#define     CMO_ZERO        22
#define     CMO_DMS_GENERIC  24
#define     CMO_DMS_OF_N_VARIABLES  25
#define     CMO_RING_BY_NAME   26
#define     CMO_DISTRIBUTED_POLYNOMIAL 31
#define     CMO_RATIONAL       34


#define     CMO_INDETERMINATE  60
#define     CMO_TREE           61
#define     CMO_LAMBDA         62    /* for function definition */
\end{verbatim}

*/

/*&jp
以下, グループ CMObject/Basic1, CMObject/Tree 
および CMObject/DistributedPolynomial
に属する CMObject の形式を説明する.
\noroa{ tagged list を導入すべきか?  cf. SSkan/plugin/cmo.txt }

*/
/*&eg
In the sequel, we will explain on the groups
CMObject/Basic1, CMObject/Tree 
and CMObject/DistributedPolynomial.
*/

/*&jp

\bigbreak
\noindent
Group CMObject/Basic1 requires CMObject/Basic0. \\
ZZ, QQ, Zero, Rational, Indeterminate,$\in$ CMObject/Basic1. \\
\begin{eqnarray*}
\mbox{Zero} &:& ({\tt CMO\_ZERO}) \\ 
& & \mbox{ --- ユニバーサルな ゼロを表す. } \\
\mbox{ZZ}         &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
{\sl byte}\, \mbox{a[m]} ) \\
&:& \mbox{ --- bignum をあらわす. a[i] についてはあとで説明}\\
\mbox{QQ}        &:& ({\tt CMO\_QQ}, {\sl ZZ}\, {\rm a}, {\sl ZZ}\, {\rm b}) \\
& & \mbox{ --- 有理数 $a/b$ を表す. } \\
\mbox{Rational}        &:& ({\tt CMO\_RATIONAL}, {\sl CMObject}\, {\rm a}, {\sl CMObject}\, {\rm b}) \\
& & \mbox{ ---  $a/b$ を表す. } \\
\mbox{Indeterminate}        &:& ({\tt CMO\_INDETERMINATE}, {\sl Cstring}\, {\rm v}) \\
& & \mbox{ --- 変数名 $v$ . } \\
\end{eqnarray*}
*/
/*&eg

\bigbreak
\noindent
Group CMObject/Basic1 requires CMObject/Basic0. \\
ZZ, QQ, Zero, Rational, Indeterminate,$\in$ CMObject/Basic1. \\
\begin{eqnarray*}
\mbox{Zero} &:& ({\tt CMO\_ZERO}) \\ 
& & \mbox{ --- Universal zero } \\
\mbox{ZZ}         &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
{\sl byte}\, \mbox{a[m]} ) \\
&:& \mbox{ --- bignum. The meaning of a[i] will be explained later.}\\
\mbox{QQ}        &:& ({\tt CMO\_QQ}, {\sl ZZ}\, {\rm a}, {\sl ZZ}\, {\rm b}) \\
& & \mbox{ --- Rational number $a/b$. } \\
\mbox{Rational}        &:& ({\tt CMO\_RATIONAL}, {\sl CMObject}\, {\rm a}, {\sl CMObject}\, {\rm b}) \\
& & \mbox{ ---  Rational expression $a/b$. } \\
\mbox{Indeterminate}        &:& ({\tt CMO\_INDETERMINATE}, {\sl Cstring}\, {\rm v}) \\
& & \mbox{ --- Variable name $v$ . } \\
\end{eqnarray*}
*/
/*&C

*/

/*&jp
Indeterminate は変数名をあらわす.
v はバイト列であればなにを用いてもよいが,
システム毎に変数名として用いられるバイト列は制限がある.
各システム xxx は任意の文字列を各システム固有の変数名へ1対1に変換できるように
実装しないといけない.
(これを
{\tt Dx} は {\tt \#dx} と変換するなどの
escape sequence を用いて実現するのは, 無理があるようである.
テーブルを作成する必要があるであろう.)
*/
/*&eg
Indeterminate is a name of a variable.
v may be any sequence of bytes, but each system has its own
restrictions on the names of variables.
Indeterminates of CMO and internal variable names must be translated
in one to one correspondence.
*/

/*&jp 

\noindent
Group CMObject/Tree requires CMObject/Basic1. \\
Tree, Lambda $\in$ CMObject/Basic1. \\
\begin{eqnarray*}
\mbox{Tree}        &:& ({\tt CMO\_TREE}, {\sl Cstring}\, {\rm name},
 {\sl Cstring}\, {\rm cdname}, {\sl List}\, {\rm leaves}) \\
& & \mbox{ --- 名前 name の定数または関数. 関数の評価はおこなわない. } \\
& & \mbox{ --- cdname は空文字列でなければ name の意味が説明されている }\\
& & \mbox{ --- OpenMath CD (content dictionary) の名前. } \\
\mbox{Lambda}        &:& ({\tt CMO\_LAMBDA}, {\sl List}\, {\rm args},
                          {\sl Tree} {\rm body}) \\                          
& & \mbox{ --- body を args を引数とする関数とする. } \\
& & \mbox{ --- optional な引数が必要なときは, leaves の後へつづける.} \\
\end{eqnarray*}
*/
/*&eg 

\noindent
Group CMObject/Tree requires CMObject/Basic1. \\
Tree, Lambda $\in$ CMObject/Basic1. \\
\begin{eqnarray*}
\mbox{Tree}        &:& ({\tt CMO\_TREE}, {\sl Cstring}\, {\rm name},
 {\sl Cstring}\, {\rm cdname}, {\sl List}\, {\rm leaves}) \\
& & \mbox{ --- A function or a constant of name. Functions are not evaluated. } \\
& & \mbox{ --- cdname may be a null. If it is not null, it is the name of}\\
& & \mbox{ --- the OpenMath CD (content dictionary). } \\
\mbox{Lambda}        &:& ({\tt CMO\_LAMBDA}, {\sl List}\, {\rm args},
                          {\sl Tree} {\rm body}) \\                          
& & \mbox{ --- a function with the arguments body. } \\
& & \mbox{ --- optional arguments come after leaves.} \\
\end{eqnarray*}
*/

/*&C

*/

/*&jp
数式を処理するシステムでは, Tree 構造が一般にもちいられる.
たとえば, $\sin(x+e)$ は,
{\tt (sin, (plus, x, e))}
なる Tree であらわすのが一般的である.
Tree の表現を スタックマシンのレベルでおこなうとすると,
{\tt ox\_BEGIN\_BLOCK}, {\tt ox\_END\_BLOCK} で評価を抑制するのが
一つの方法である (cf. Postscript の {\tt \{ }, {\tt \} }).
たとえば上の方法では 
{\tt x, e, plus, sin } を begin block, end block でかこめばよろしい.
われわれはスタックマシンの実装をなるべく簡単にするという立場をとりたい,
また数学オブジェクトを OX スタックマシンと CMObject を混在して表現したく
ない.
したがって,
Tree 構造は Open Math 風の表現をもちいた CMO を導入することにした.
またこのほうが, われわれの想定するシステム xxx において, Open XM 対応が
はるかに容易である.
なお, Tree は, Open Math では, Symbol, Application のメカニズムに相当する.
*/
/*&eg
In many computer algebra systems, mathematical expressions are usually
expressed in terms of a tree structure.
For example,
$\sin(x+e)$ is expressed as
{\tt (sin, (plus, x, e))}
as a tree.
We can   @@@
*/


/*&C

*/
/*&jp
Lambda は関数を定義するための関数である.
Lisp の Lambda 表現と同じ.

\noindent
例: $sin(x+e)$ の表現.
\begin{verbatim}
(CMO_TREE, (CMO_STRING, "sin"), (CMO_STRING, "basic"),
    (CMO_LIST,[size=]1, 
        (CMO_TREE, (CMO_STRING, "plus"), (CMO_STRING, "basic"),
            (CMO_LIST,[size=]2, (CMO_INDETERMINATE,"x"),
                                (CMO_TREE,(CMO_STRING, "e"),  自然対数の底
                                          (CMO_STRING, "basic"))
        ))
    )
)
\end{verbatim}

\noindent
Example:
\begin{verbatim}
sm1> [(plus) (Basic) [(123).. (345)..]] [(class) (tree)] dc ::
Class.tree [    $plus$ , $Basic$ , [    123 , 345 ]  ] 
\end{verbatim}



\bigbreak
次に, 分散表現多項式に関係するグループを定義しよう.

\medbreak
\noindent
Group CMObject/DistributedPolynomials requires CMObject/Basic0,
CMObject/Basic1. \\
Monomial, Monomial32, Coefficient, Dpolynomial, DringDefinition,
Generic DMS ring, RingByName, DMS of N variables $\in$ 
CMObject/DistributedPolynomials. \\
\begin{eqnarray*}
\mbox{Monomial} &:& \mbox{Monomial32}\, |\, \mbox{Zero} \\
\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, {\sl int32}\, n,
{\sl int32}\, \mbox{e[1]}, \ldots,
{\sl int32}\, \mbox{e[n]}, \\
& & \ \mbox{Coefficient}) \\
& & \mbox{ --- e[i] で, $n$ 変数 monomial 
$x^e = x_1^{e_1} \cdots x_n^{e_n}$ の各指数 $e_i$
をあらわす.} \\
\mbox{Coefficient}&:& \mbox{ZZ} | \mbox{Integer32} \\
\mbox{Dpolynomial}&:& \mbox{Zero} \\
& & |\ ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},{\sl int32} m, \\
& & \ \ \mbox{DringDefinition},
[\mbox{Monomial32}|\mbox{Zero}], \\
& &\ \ 
\{\mbox{Monomial32}\}) \\
& &\mbox{--- m はモノミアルの個数である.}\\
\mbox{DringDefinition}
&:& \mbox{DMS of N variables} \\
& & |\ \mbox{RingByName} \\
& & |\ \mbox{Generic DMS ring} \\
& & \mbox{ --- 分散表現多項式環の定義. } \\
\mbox{Generic DMS ring}
&:& ({\tt CMO\_DMS\_GENERIC})\  新版はこちら\\
\mbox{RingByName}&:& ({\tt CMO\_RING\_BY\_NAME}, {\sl Cstring}\  {\rm s}) \\
& & \mbox{ --- 名前 s で, 格納された ring 定義.} \\
\mbox{DMS of N variables}
&:& ({\tt CMO\_DMS\_OF\_N\_VARIABLES}, \\
& & \ ({\tt CMO\_LIST}, {\sl int32}\, \mbox{m},
{\sl Integer32}\,  \mbox{n}, {\sl Integer32}\,\mbox{p} \\
& & \ \ [,{\sl object}\,\mbox{s}, {\sl Cstring}\,\mbox{c}, 
          {\sl List}\, \mbox{vlist},
{\sl List}\, \mbox{wvec}, {\sl List}\, \mbox{outord}]) \\
& & \mbox{ --- m はあとに続く要素の数} \\
& & \mbox{ --- n は変数の数, p は 標数} \\
& & \mbox{ --- s は ring の名前} \\
& & \mbox{ --- c は係数環, QQ, ZZ の場合は文字列で QQ, ZZ と書く.} \\
& & \mbox{ --- vlist は Indeterminate のリスト(新版). 多項式環の変数リスト} \\
& & \mbox{ --- wvec は order をきめる weight vector,} \\
& & \mbox{ --- outord は出力するときの変数順序.} \\
\end{eqnarray*}

RingByName や DMS of N variables はなくても, DMS を定義できる.
したがって, これらを実装してないシステムで DMS を扱うものが
あってもかまわない.

以下, 以上の CMObject  にたいする,
xxx = asir, kan の振舞いを記述する.

\subsection{ Zero}
CMO では ゼロの表現法がなんとうりもあるが,
どのようなゼロをうけとっても,
システムのゼロに変換できるべきである.
(たとえば, asir は 0 はただ一つ.)



\subsection{ 整数 ZZ }

\begin{verbatim}
#define     CMO_ZZ          20 
\end{verbatim}


この節ではOpen xxx 規約における任意の大きさの整数(bignum)の扱いについて
説明する.
Open XM 規約における多重精度整数を表すデータ型 CMO\_ZZ は GNU MPライブ
ラリなどを参考にして設計されていて, 符号付き絶対値表現を用いている.
(cf. {\tt kan/sm1} の配布ディレクトリのなかの {\tt plugin/cmo-gmp.c})
CMO\_ZZ は次の形式をとる.\\
\begin{tabular}{|c|c|c|c|c|}
\hline
{\tt int32 CMO\_ZZ} & {\tt int32 $f$} & {\tt int32 $b_0$} & $\cdots$ &
{\tt int32 $b_{n}$} \\
\hline
\end{tabular} \\
$f$ は32bit整数である.
$b_0, \ldots, b_n$ は unsigned int32 である.
$|f|$ は $n+1$ である.
この CMO の符号は $f$ の符号で定める.
前述したように, 32bit整数の負数は 2 の補数表現で表される.

Open xxx 規約では上の CMO は以下の整数を意味する.
\[
\mbox{sgn}(f)\times (b_0 R^{0}+ b_1 R^{1} + \cdots + b_{n-1}R^{n-1} + b_n R^n).
\]
ここで $R = 2^{32}$ である.
{\tt int32} を network byte order で表現しているとすると,
例えば, 整数 $14$ は CMO\_ZZ で表わすと,
\[
\mbox{(CMO\_ZZ, 1, 0, 0, 0, e)},
\]
と表わす.
これはバイト列では
\[
\mbox{\tt 00 00 00 14 00 00 00 01 00 00 00 0e}
\]
となる.


なお ZZ の 0  ( (ZZ) 0 と書く ) は,
{\tt (CMO\_ZZ, 00,00,00,00)}
と表現する.


\subsection{ 分散表現多項式 Dpolynomial }

環とそれに属する多項式は次のような考えかたであつかう.

Generic DMS ring に属する元は,
変数を $n$ 個持つ 適当な係数集合 $K$ を持つ多項式環 $K[x_1, \ldots, x_n]$ 
の元である.
係数集合 $K$ がなにかは, 実際データを読み込み, Coefficient を見た段階で
わかる.
この環に属する多項式を CMO 形式でうけとった場合, 各サーバはその
サーバの対応する Object  に変換しないといけない. 
この変換の仕方は, 各サーバ毎にきめる.

Asir の場合は, $K[x_1, \ldots, x_n]$ の元は分散表現多項式に変換される.
\noroa{ でも, order はどうなるの? }

{\tt kan/sm1} の場合は事情は複雑である.
{\tt kan/sm1} は, Generic DMS ring にあたる クラスをもたない.
つまり, Default で存在する, $n$ 変数の分散表現多項式環は存在しないわけである.
したがって, {\tt kan/sm1} では, DMS of N variables が来た場合,
これを CurrentRing の元として読み込む.  CurrentRing の変数の数が $n'$
で, $n' < n$ だと新しい多項式環を生成してデータを読み込む.
Order その他の optional 情報はすべて無視する.

DMS の 2 番目のフィールドで,
Ring by Name を用いた場合, 現在の名前空間で変数 yyy に格納された ring object
の元として, この多項式を変換しなさいという意味になる.
{\tt kan/sm1} の場合, 環の定義は ring object として格納されており,
この ring object を 変数 yyy で参照することにより CMO としてうけとった
多項式をこの ring の元として格納できる.





\medbreak \noindent
{\bf Example}:
(すべての数の表記は 16 進表記)
{\footnotesize \begin{verbatim}
Z/11Z [6 variables]
(kxx/cmotest.sm1) run
[(x,y) ring_of_polynomials ( ) elimination_order 11 ] define_ring ;
(3x^2 y). cmo /ff set ;
[(cmoLispLike) 1] extension ;
ff ::
Class.CMO CMO StandardEncoding: size = 52, size/sizeof(int) = 13, 
tag=CMO_DISTRIBUTED_POLYNOMIAL 

  0  0  0 1f  0  0  0  1  0  0  0 18  0  0  0 13  0  0  0  6
  0  0  0  0  0  0  0  2  0  0  0  0  0  0  0  0  0  0  0  1
  0  0  0  0  0  0  0  2  0  0  0  3

ff omc ::
 (CMO_DISTRIBUTED_POLYNOMIAL[1f],[size=]1,(CMO_DMS_GENERIC[18],),
  (CMO_MONOMIAL32[13],3*x^2*y),),
\end{verbatim} }
length は, monomial の数$+2$ である.
$ 3 x^2 y$ は 6 変数の多項式環の元としてみなされている.
%%Prog: (3x^2 y). cmosave   ===> debug/cmodata1.cmo
%%\\ 反省: 分散多項式の定義で,
%%{\tt CMO\_LIST} でなく, {\tt CMO\_DMS} がはじめにくるべきだったのでは?
%%あたらしい 分散多項式の定義は次のようにすべき:
%% 修正済み. 1999, 9/13



\subsection{再帰表現多項式の定義} 

\begin{verbatim}
#define CMO_RECURSIVE_POLYNOMIAL        27
#define CMO_POLYNOMIAL_IN_ONE_VARIABLE  33
\end{verbatim}

Group CMObject/RecursivePolynomial requires CMObject/Basic0, CMObject/Basic1.\\
Polynomial in 1 variable, Coefficient, Name of the main variable,
Recursive Polynomial, Ring definition for recursive polynomials
$\in$ CMObject/RecursivePolynomial \\

\begin{eqnarray*}
\mbox{Polynomial in 1 variable} &:& 
\mbox{({\tt CMO\_POLYNOMIAL\_IN\_ONE\_VARIABLE},\, {\sl int32}\, m, } \\
& & \quad \mbox{ Name of the main variable }, \\
& & \quad \mbox{ \{ {\sl int32} e, Coefficient \}} \\
& & \mbox{ --- m はモノミアルの個数. } \\
& & \mbox{ --- e, Coefficieint はモノミアルを表現している. } \\
& & \mbox{ --- 順序の高い順にならべる. 普通は巾の高い順.} \\
& & \mbox{ ---  e は 1変数多項式の巾をあらわす. } \\
\mbox{Coefficient} &:& \mbox{ ZZ} \,|\, \mbox{ QQ } \,|\, 
\mbox{ integer32  } \,|\,
\mbox{ Polynomial in 1 variable } \\
& & \quad \,|\, \mbox{Tree} \,|\, \mbox{Zero} \,|\,\mbox{Dpolynomial}\\
\mbox{Name of the main variable } &:& 
\mbox{ {\sl int32} v }   \\
& & \mbox{ --- v は 変数番号 (0 からはじまる) を表す. } \\
\mbox{Recursive Polynomial} &:& 
\mbox{ ( {\tt CMO\_RECURSIVE\_POLYNOMIAL}, } \\
& & \quad \mbox{ Ring definition for 
recursive polynomials, } \\
& & \quad
\mbox{ Polynomial in 1 variable}\, | \, \mbox{Coefficient}   \\
\mbox{Ring definition for recursive polynomials } 
& : &  \mbox{ {\sl List} v } \\
& & \quad \mbox{ --- v は, 変数名(indeterminate) のリスト. } \\
& & \quad \mbox{ --- 順序の高い順. } \\
\end{eqnarray*}

\bigbreak
\noindent
実例:
\begin{verbatim}
(CMO_RECURSIEVE_POLYNOMIAL, ("x","y"),
(CMO_POLYNOMIAL_IN_ONE_VARIABLE, 2,      0,  <--- "x"
  3, (CMO_POLYNOMIAL_IN_ONE_VARIABLE, 2, 1,  <--- "y"
       5, 1234,
       0, 17),
  1, (CMO_POLYNOMIAL_IN_ONE_VARIABLE, 2, 1,  <--- "y"
       10, 1,
       5, 31)))
\end{verbatim}
これは,
$$   x^3 (1234 y^5 + 17 ) +  x^1 (y^10 + 31 y^5)  $$
をあらわす.
非可換多項式もこの形式であらわしたいので, 積の順序を上のように
すること. つまり, 主変数かける係数の順番.

\noindent
\begin{verbatim}
sm1
sm1>(x^2-h). [(class) (recursivePolynomial)] dc /ff set ;
sm1>ff ::
Class.recursivePolynomial h * ((-1)) + (x^2  * (1))
\end{verbatim}



int32 と Integer32 の違い.
次にくるデータがかならず int32 とわかっておれば,
int32 を用いる.
次のデータ型がわからないとき Integer32 を用いる.


\subsection{CPU依存の double } 

\begin{verbatim}
#define CMO_64BIT_MACHINE_DOUBLE   40
#define CMO_ARRAY_OF_64BIT_MACHINE_DOUBLE  41
#define CMO_128BIT_MACHINE_DOUBLE   42
#define CMO_ARRAY_OF_128BIT_MACHINE_DOUBLE  43
\end{verbatim}

\noindent
Group CMObject/MachineDouble requires CMObject/Basic0.\\
64bit machine double, Array of 64bit machine double
128bit machine double, Array of 128bit machine double
$\in$ CMObject/MachineDouble \\

\begin{eqnarray*}
\mbox{64bit machine double} &:& 
\mbox{({\tt CMO\_64BIT\_MACHINE\_DOUBLE}, } \\
& & \quad \mbox{ {\sl byte} s1 , \ldots , {\sl byte}} s8)\\
& & \mbox{ --- s1, $\ldots$, s8 は {\tt double} (64bit). } \\
& & \mbox{ --- この表現はCPU依存である.}\\
&&  \mbox{\quad\quad mathcap に CPU 情報を付加しておく.} \\
\mbox{Array of 64bit machine double} &:& 
\mbox{({\tt CMO\_ARRAY\_OF\_64BIT\_MACHINE\_DOUBLE}, {\sl int32} m, } \\
& & \quad \mbox{ {\sl byte} s1[1] , \ldots , {\sl byte}}\, s8[1], \ldots , {\sl byte}\, s8[m])\\
& & \mbox{ --- s*[1], $\ldots$ s*[m] は m 個の double (64bit) である. } \\
& & \mbox{ --- この表現はCPU依存である.}\\
& & \mbox{ \quad\quad mathcap に CPU 情報を付加しておく.} \\
\mbox{128bit machine double} &:& 
\mbox{({\tt CMO\_128BIT\_MACHINE\_DOUBLE}, } \\
& & \quad \mbox{ {\sl byte} s1 , \ldots , {\sl byte}} s16)\\
& & \mbox{ --- s1, $\ldots$, s16 は {\tt long double} (128bit). } \\
& & \mbox{ --- この表現はCPU依存である.}\\
&&  \mbox{\quad\quad mathcap に CPU 情報を付加しておく.} \\
\mbox{Array of 128bit machine double} &:& 
\mbox{({\tt CMO\_ARRAY\_OF\_128BIT\_MACHINE\_DOUBLE}, {\sl int32} m, } \\
& & \quad \mbox{ {\sl byte} s1[1] , \ldots , {\sl byte}} s16[1], \ldots , {\sl byte} s16[m])\\
& & \mbox{ --- s*[1], $\ldots$ s*[m] は m 個の long double (128bit) である. } \\
& & \mbox{ --- この表現はCPU依存である.}\\
& & \mbox{ \quad\quad mathcap に CPU 情報を付加しておく.} 
\end{eqnarray*}

\bigbreak
次に IEEE 準拠の float および Big float を定義しよう.
\begin{verbatim}
#define CMO_BIGFLOAT   50
#define CMO_IEEE_DOUBLE_FLOAT 51
\end{verbatim}

IEEE 準拠の float については,
IEEE 754  double precision floating-point format
(64 bit) の定義を見よ.

\noindent
Group CMObject/Bigfloat requires CMObject/Basic0, CMObject/Basic1.\\
Bigfloat
$\in$ CMObject/Bigfloat \\

\begin{eqnarray*}
\mbox{Bigfloat} &:& 
\mbox{({\tt CMO\_BIGFLOAT}, } \\
& & \quad \mbox{ {\sl ZZ} a , {\sl ZZ} e})\\
& & \mbox{ --- $a \times 2^e$ をあらわす. } \\
\end{eqnarray*}


*/
