%% $OpenXM: OpenXM/doc/OpenXM-specs/cmo-basic1.tex,v 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*} */