Return to formal-expression.tex CVS log

Up to [local] / OpenXM / doc / OpenXM-specs

Annotation of OpenXM/doc/OpenXM-specs/formal-expression.tex, Revision 1.6

1.6     ! takayama    1: %% $OpenXM: OpenXM/doc/OpenXM-specs/formal-expression.tex,v 1.5 2000/09/08 18:57:49 takayama Exp $
1.1       noro        2: //&jp \section{ CMO の形式的表現方法 }
                      3: //&eg \section{ A formal expression of CMO }
                      4:
                      5: /*&jp
                      6: 前の節で CMO の表現方法を形式的に定義せず,
1.3       noro        7: CMO のPrimitive の表現法を説明したが,
1.1       noro        8: ここでは, CMO の Lisp 風表現 (Lisp-like expression)
                      9: である
                     10: CMOexpression
                     11: および前節で説明した CMO の標準 encoding 法をもう一度説明する.
                     12: % (タグの省略記法がほしい.)
                     13: */
                     14: /*&eg
1.3       noro       15: In the previous section, we have explained the format of CMO's in the
                     16: Primitive group.
1.1       noro       17: In this section, we will introduce CMOexpression which is like the
                     18: bracket expression of Lisp.
                     19: We again explain a standard encoding method of CMO,
                     20: which we have already explained in the previous section.
                     21: */
                     22:
                     23: /*&jp
                     24:
                     25: まず, CMOexpression を形式的に 拡張 BNF 記法を用いて定義しよう.
                     26: タイプライタフォントでかかれた記号は終端記号を意味する.
                     27: ``:'' は定義を意味する. ``$|$'' は''または''を意味する.
                     28: \{ X \} は X の 0 回以上の繰り返しを表す.
                     29: [ x ] は X が 0 回または 1 回出現することを表す.
                     30: この記法を用いると CMOexpression は次のように定義できる.
                     31:
                     32: */
                     33: /*&eg
                     34:
                     35: Let us define CMOexpression by the extended BNF expression.
                     36: Symbols in the type writer fonts mean terminals.
                     37: ``:'' means a definition.
                     38: ``$|$'' means ''or''.
                     39: \{ X \} is a repetition of X of more than or equal to 0 times.
                     40: [ x ] stands for X or nothing.
                     41: By using this notation, CMOexpression is defined as follows.
                     42:
                     43: */
                     44:
                     45: /*&C
                     46: \begin{eqnarray*}
                     47: \mbox{CMOexpression}
                     48: &:& \quad
                     49: \mbox{\tt (} \mbox{\tt cmo\_tag} \
                     50: \{ \mbox{ expression} \} \mbox{\tt )}\\
                     51: \mbox{expression}
                     52: &:& \quad  \mbox{CMOexpression} \\
                     53: &   &|\   \mbox{\tt int32}  \\
                     54: &   &|\   \mbox{\tt string} \\
                     55: &   &|\   \mbox{\tt byte} \\
                     56: \end{eqnarray*}
                     57: */
                     58: /*&jp
                     59: 終端記号 {\tt int32} は, 32 bit integer を表す, 10 進または 16 進の数字の
                     60: 列である.
                     61: 終端記号 {\tt string} は''文字''の列である.
                     62: 終端記号 {\tt byte} は 8 bit データを表す, 10 進または 16 進の数字の列である.
                     63: */
1.2       noro       64: /*&eg
1.1       noro       65: Terminal {\tt int32} is signed 32 bit integer.
                     66: Terminal {\tt string} is a byte array which usually expresses a string.
                     67: Terminal {\tt byte} is 8 bit data.
                     68: */
                     69:
                     70: /*&jp
                     71: CMOexpression にあらわれる各要素を区切るために {\tt ,} (コンマ) を用いてもよい.
                     72: {\tt cmo\_tag} は {\tt CMO\_} で始まる定数である.
                     73: CMOexpression で表現される object を CMObject と呼ぶ.
                     74:
                     75: */
                     76: /*&eg
                     77: The comma ({\tt ,}) may be used to separate each element in CMOexpressions.
                     78: {\tt cmo\_tag} is a constant that starts with {\tt CMO\_}.
                     79:
                     80: */
                     81:
                     82: /*&jp
1.3       noro       83: この表記法 CMOexpression を利用して, CMO Primitive の object を記述
1.1       noro       84: してみよう.
                     85: Object 自体の構造を説明するため,
                     86: BNF をもうすこし拡張して, 非終端記号, 終端記号名のみならず, 変数の
                     87: 名前も書くことにする. こうすることにより, object の意味の説明も容易になる
                     88: からである. また ``---'' でコメントのはじまりを表すものとする.
                     89: */
                     90: /*&eg
1.3       noro       91: Let us describe CMO's in the Primitive group.
1.1       noro       92: In order to explain the meaning of objects,
                     93: we may also put variable names to CMOexpressions.
                     94: The start of comments are denoted by ``---''.
                     95: */
                     96: /*&jp
                     97: たとえば, (CMObject の) 32 bit integer である integer32 を
                     98: BNFで定義すれば,
                     99: \begin{center}
                    100: Integer32 \  : \ ({\tt CMO\_INT32}, {\tt int32})
                    101: \end{center}
                    102: と書くのが本来の書き方による記法であるが, ここでは,
                    103: \begin{eqnarray*}
                    104: \mbox{Integer32} \  &:& \ ({\tt CMO\_INT32}, {\sl int32}\  n) \\
                    105: & & \  \mbox{--- 32 bit integer $n$ を表す. } \\
                    106: \end{eqnarray*}
                    107: と書くことを許すことにする.
                    108: このように書くことにより, 非終端記号  Integer32 は,
                    109: \begin{center}
                    110: Integer32 \  : \ ({\tt CMO\_INT32}, {\tt int32})
                    111: \end{center}
                    112: のように, 終端記号 {\tt CMO\_INT32} と {\tt int32} を成分にもち,
                    113: CMObject の
                    114: ({\tt CMO\_INT32}, {\sl int32}\ n)
                    115: は,
                    116: 32 bit integer $n$ を表現しているんだということが, 1 行でわかる.
                    117: */
                    118: /*&jp
1.3       noro      119: この記法を用いて, 前節で導入した, Primitive の CMObject を
1.1       noro      120: 形式的に定義しよう.
                    121: */
                    122: /*&eg
                    123: By using this notation, let us define formally CMObjects in the group
1.3       noro      124: Primitive.
1.1       noro      125: */
                    126:
                    127: /*&C
                    128:
                    129: \bigbreak
                    130: \noindent
1.3       noro      131: Group CMObject/Primitive  requires nothing. \\
                    132: Error2, Null, Integer32, Datum, Cstring, Mathcap, List $\in$ CMObject/Primitive. \\
                    133: Document of CMObject/Primitive is at {\tt http://www.math.kobe-u.ac.jp/OpenXM}
1.1       noro      134: (in English and Japanese) \\
                    135: \begin{eqnarray*}
                    136: \mbox{Error2}&:& ({\tt CMO\_ERROR2}, {\sl CMObject}\, \mbox{ob}) \\
                    137: \mbox{Null}  &:& ({\tt CMO\_NULL}) \\
                    138: \mbox{Integer32}
                    139: &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
                    140: \mbox{Datum} &:& ({\tt CMO\_DATUM}, {\sl int32}\, \mbox{n}, {\sl byte}\,
                    141: \mbox{data[0]},
                    142: \ldots , {\sl byte}\, \mbox{data[n-1]}) \\
                    143: \mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\,  \mbox{ n},
                    144: {\sl string}\, \mbox{s}) \\
                    145: \mbox{Mathcap}&:& ({\tt CMO\_MATHCAP},{\sl CMObject}\,  \mbox{ob} ) \\
                    146: \mbox{List} &:&
                    147: \mbox{({\tt CMO\_LIST}, {\sl int32}\, m, {\sl CMObject}\, ob[0], $\ldots$,
                    148: {\sl CMObject}\, ob[m-1])} \\
                    149: & & \mbox{---  m is the length of the list.}
                    150: \end{eqnarray*}
                    151:
                    152: */
                    153:
                    154:
                    155: //&jp Cstring で, {\sl string} s の部分を {\tt byte} に分解すれば,
                    156: //&eg In the definition of ``Cstring'', if we decompose  ``{\sl string} s'' into bytes, then  ``Cstring'' should be defined as
                    157: /*&C
                    158: \begin{eqnarray*}
                    159: \mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\,  \mbox{ n},
                    160: {\sl byte}\, \mbox{s[0]},
                    161: \ldots, {\sl byte}\ \mbox{s[n-1]})
                    162: \end{eqnarray*}
                    163: */
                    164: //&jp となる.
                    165: /*&jp
                    166: また,
1.3       noro      167: ``Group CMObject/Primitive  requires nothing''
                    168: は, 以下は, グループ CMObject/Primitive の定義であり,
1.1       noro      169: このグループの CMObject を定義するのに, 要請される CMObject のグループは
                    170: ないことを示す.
                    171: ``Error2, Null, Integer32, Datum, Cstring, Mathcap, List
1.3       noro      172: $\in$ CMObject/Primitive''
                    173: は, グループ CMObject/Primitive には,  Error2, Null, Integer32,
1.1       noro      174: Datum, Cstring なるクラスの object が属することを示す.
                    175: */
                    176: /*&eg
1.3       noro      177: ``Group CMObject/Primitive  requires nothing''
                    178: means that there is no super group to define CMO's in the group Primitive.
1.1       noro      179: ``Error2, Null, Integer32, Datum, Cstring, Mathcap, List
1.3       noro      180: $\in$ CMObject/Primitive''
1.1       noro      181: means that
                    182: Error2, Null, Integer32, Datum, Cstring
1.3       noro      183: are members of the group CMObject/Primitive.
1.1       noro      184: */
                    185:
                    186: /*&C
                    187:
                    188: */
                    189:
                    190: /*&jp
                    191: では, 実際のデータの表現の例をみてみよう.
                    192: たとえば, 32 bit integer の 1234 は,
                    193: */
                    194: /*&eg
                    195: Let us see examples.
                    196: 32 bit integer 1234 is expressed as
                    197: */
                    198: /*&C
                    199: \begin{center}
                    200: ({\tt CMO\_INT32}, 1234)
                    201: \end{center}
                    202: */
                    203: /*&jp
                    204: とかく.
                    205: 文字列 ``Hello''  は
                    206: */
                    207: /*&eg
                    208: The string ``Hello'' is expressed as
                    209: */
                    210: /*&C
                    211: \begin{center}
                    212: ({\tt CMO\_STRING}, 5, "Hello")
                    213: \end{center}
                    214: */
                    215: //&jp と書く.
                    216:
                    217: /*&C
                    218:
                    219: */
                    220: /*&jp
                    221: CMOexpression と, CMObject の区別を理解しておくのは重要である.
                    222: たとえば
                    223: \begin{center}
                    224: ({\tt CMO\_INT32}, 234, "abc",({\tt CMO\_STRING}))
                    225: \end{center}
                    226: は CMOexpression ではあるが, CMObject ではない.
                    227: これは, 文法的には正しいプログラムだが, なにをやるのかは全く不明な
                    228: プログラムと似ている.
                    229:
1.4       takayama  230: */
                    231:
                    232: /*&jp
1.1       noro      233: さて, Open math 風 (\cite{openmath})
1.4       takayama  234: の XML 表現法も可能であり, その場合は, 上の二つの例は次のように
1.1       noro      235: 書く.
1.4       takayama  236: */
                    237: /*&eg
1.6     ! takayama  238: It is possible to express CMO by XML like Open Math (\cite{openmath}).
1.4       takayama  239: See example below.
                    240: */
                    241:
                    242: /*&C
                    243:
1.1       noro      244: \begin{verbatim}
1.6     ! takayama  245: <cmo>
        !           246:  <cmo_int32>
        !           247:    <int32> 1234 </int32>
        !           248:  </cmo_int32>
        !           249:
        !           250:  <cmo_string>
        !           251:    <int32 for="length"> 5 </int32>
        !           252:    <string> "Hello" </string>
        !           253:  </cmo_string>
        !           254: </cmo>
1.1       noro      255: \end{verbatim}
                    256: */
                    257:
1.6     ! takayama  258: //&jp \noindent cmo\_string は次のようにあらわしてもよい.
        !           259: //&eg \noindent cmo\_string can also be expressed as follows.
1.1       noro      260: /*&C
1.6     ! takayama  261: \begin{verbatim}
        !           262:
        !           263: <cmo>
        !           264:  <cmo_string>
        !           265:    <int32 for="length"> 5 </int32>
        !           266:    <byte> 'H' </byte> <byte> 'e' </byte>    <byte> 'l' </byte>
        !           267:    <byte> 'l' </byte> <byte> 'o' </byte>
        !           268:  </cmo_string>
        !           269: </cmo>
        !           270: \end{verbatim}
        !           271: */
1.1       noro      272:
1.6     ! takayama  273: //&jp \noindent この場合の cmo\_string の DTD による定義は次のようになる. \\
        !           274: //&eg \noindent In this case, the DTD for cmo\_string is as follows; \\
        !           275: //&C \verb+  <!ELEMENT cmo_string (int32, byte*)>  +
        !           276: /*&C
        !           277:
        !           278: \bigbreak
1.1       noro      279: */
                    280:
                    281: /*&jp
                    282: 次に, 標準 encoding 法を説明しよう.
                    283: 標準 encoding 法では, cmo\_tag を ネットワークバイトオーダーの
                    284: 32 bit integer {\tt int32} に,
                    285: その他のフィールドは, 定義に記述されているデータ型に従い,
                    286: byte データ {\tt byte} かまたは
                    287: ネットワークバイトオーダーの 32 bit integer {\tt int32} に, 変換する.
                    288: */
                    289: /*&eg
                    290: Let us explain the standard encoding method.
                    291: All {\tt int32} data are encoded into network byte order 32 bit integers
                    292: and byte data are encoded as it is.
                    293: */
                    294:
                    295: /*&C
                    296:
                    297: */
                    298:
                    299: /*&jp
                    300: 高速の通信方法を用いて
                    301: 効率を重視する接続の場合には, {\tt int32} を network byte order
                    302: に変換する操作がおおきなオーバヘッドとなることが
                    303: 報告されている.
                    304: 100Mbps の通信路で 12Mbytes の {\tt CMO\_ZZ} の転送では
                    305: 約 90\% の時間が network byte order への変換についやされているという
                    306: 実験データもある.
                    307: 効率を重視した encoding 法については後述する.
                    308: */
                    309: /*&eg
                    310: When we are using a high speed network,
                    311: the translation from the internal expression of 32 bit integers to
                    312: network byte order may become a bottle neck.
                    313: There are experimental data which presents that 90 percents of the transmission
                    314: time are
                    315: for the translation to the network byte order to send {\tt CMO\_ZZ} of size
                    316: 12M bytes on a 100Mbps network.
                    317: In a later section, we will discuss a protocol to avoid the translation.
                    318: */
                    319:
                    320: /*&C
                    321:
                    322: */
                    323:
                    324: /*&jp
                    325: 標準 encoding と CMOexpression の間の変換は容易である.
                    326: 前節で用いたデータの表記法,
                    327: たとえば,
                    328: */
                    329: /*&eg
                    330: The translation between the standard encoding and CMOexpression
                    331: is easy.
                    332: For example,
                    333: */
                    334: /*&C
                    335: \begin{center}
                    336: \begin{tabular}{|c|c|}
                    337: \hline
                    338: {\tt int32 CMO\_INT32}& {\tt int32 1234}  \\
                    339: \hline
                    340: \end{tabular}
                    341: \end{center}
                    342: */
                    343: /*&jp
                    344: は, CMOexpression
                    345: */
                    346: /*&eg
                    347: is the encoding of the CMOexpression
                    348: */
                    349: /*&C
                    350: \begin{center}
                    351: ({\tt CMO\_INT32}, 1234)
                    352: \end{center}
                    353: */
                    354: /*&jp
                    355: の 標準 encoding 法による表現である.
                    356: */
                    357:
1.4       takayama  358: /*&C
                    359:
                    360: \bigbreak
                    361:
                    362: */
                    363:
                    364: /*&jp
                    365: (実験的)
1.6     ! takayama  366: CMO および OX packets は XML 規格に準拠している.
1.4       takayama  367: XML 規格の Attribute を binary encode するために
                    368: 特別なタグ \\
                    369: */
                    370: /*&eg
                    371: (Experimental)
1.6     ! takayama  372: CMO and OX packets are complient to XML specification.
1.4       takayama  373: In order to encode ``Attribute'' in XML in a binary format,
                    374: we have a tag: \\
                    375: */
                    376: //&C \verb! #define CMO_ATTRIBUTE_LIST  (LARGEID+3) !  \\
                    377: /*&jp
                    378: を用意してある.
                    379: */
                    380: /*&jp
                    381: たとえば Attribute {\tt font="Times-Roman" }  は \\
                    382: */
                    383: /*&eg
                    384: For example, the attibute {\tt font="Times-Roman" } is encoded as \\
                    385: */
                    386: /*&C
                    387: \begin{verbatim}
                    388:  (CMO_ATTRIBUTE (CMO_LIST
                    389:                   (CMO_LIST (CMO_STRING,"font") (CMO_STRING, "Times-Roman"))))
                    390: \end{verbatim}
                    391: */
                    392: /*&jp
                    393: と encoding される.
                    394: */
1.5       takayama  395: //&C
1.4       takayama  396: /*&jp
                    397: この特別な CMO tag {\tt CMO\_ATTRIBUTE\_LIST} 以外は,
                    398: XML 表現では XML のタグとして理解される.
                    399: */
                    400: /*&eg
                    401: All tags except this special CMO tag {\tt CMO\_ATTRIBUTE\_LIST}
                    402: are XML tags in the CMO/XML expression.
                    403: */
1.1       noro      404: