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.8

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