%% $OpenXM: OpenXM/doc/OpenXM-specs/formal-expression.tex,v 1.8 2020/03/14 01:21:56 takayama Exp $
//&jp \section{ CMO の形式的表現方法 }
//&eg \section{ A formal expression of CMO }

/*&jp
前の節で CMO の表現方法を形式的に定義せず, 
CMO のPrimitive の表現法を説明したが,
ここでは, CMO の Lisp 風表現 (Lisp-like expression)
である
CMOexpression
および前節で説明した CMO の標準 encoding 法をもう一度説明する.
% (タグの省略記法がほしい.)
*/
/*&eg
In the previous section, we have explained the format of CMO's in the
Primitive group.
In this section, we will introduce CMOexpression which is like the 
bracket expression of Lisp. 
We again explain a standard encoding method of CMO,
which we have already explained in the previous section, but
the explanation is more formal.
*/

/*&jp

まず, CMOexpression を形式的に 拡張 BNF 記法を用いて定義しよう.
タイプライタフォントでかかれた記号は終端記号を意味する.
``:'' は定義を意味する. ``$|$'' は''または''を意味する.
\{ X \} は X の 0 回以上の繰り返しを表す.
[ x ] は X が 0 回または 1 回出現することを表す.
この記法を用いると CMOexpression は次のように定義できる.

*/
/*&eg

Let us define CMOexpression by the extended BNF expression.
Symbols in the type writer fonts mean terminals.
``:'' means a definition.
``$|$'' means ''or''.
\{ X \} is a repetition of X of more than or equal to 0 times.
[ x ] stands for X or nothing.
By using this notation, CMOexpression is defined as follows.

*/

/*&C
\begin{eqnarray*}
\mbox{CMOexpression}  
&:& \quad
\mbox{\tt (} \mbox{\tt cmo\_tag} \ 
\{ \mbox{ expression} \} \mbox{\tt )}\\
\mbox{expression}
&:& \quad  \mbox{CMOexpression} \\
&   &|\   \mbox{\tt int32}  \\
&   &|\   \mbox{\tt string} \\
&   &|\   \mbox{\tt byte} \\
\end{eqnarray*}
*/
/*&jp
終端記号 {\tt int32} は, 32 bit integer を表す, 10 進または 16 進の数字の
列である.
終端記号 {\tt string} は''文字''の列である.
終端記号 {\tt byte} は 8 bit データを表す, 10 進または 16 進の数字の列である.
*/
/*&eg
Terminal {\tt int32} is signed 32 bit integer. 
Terminal {\tt string} is a byte array which usually expresses a string.
Terminal {\tt byte} is 8 bit data.
*/

/*&jp
CMOexpression にあらわれる各要素を区切るために {\tt ,} (コンマ) を用いてもよい.
{\tt cmo\_tag} は {\tt CMO\_} で始まる定数である.
CMOexpression で表現される object を CMObject と呼ぶ.

*/
/*&eg
The comma ({\tt ,}) may be used to separate each element in CMOexpressions.
{\tt cmo\_tag} is a constant that starts with {\tt CMO\_}.

*/

/*&jp
この表記法 CMOexpression を利用して, CMO Primitive の object を記述
してみよう.
Object 自体の構造を説明するため,
BNF をもうすこし拡張して, 非終端記号, 終端記号名のみならず, 変数の
名前も書くことにする. こうすることにより, object の意味の説明も容易になる
からである. また ``---'' でコメントのはじまりを表すものとする. 
*/
/*&eg
Let us describe CMO's in the Primitive group.
In order to explain the meaning of objects,
we may also put variable names to CMOexpressions.
The start of comments are denoted by ``---''.
*/
/*&jp
たとえば, (CMObject の) 32 bit integer である integer32 を
BNFで定義すれば,
\begin{center}
Integer32 \  : \ ({\tt CMO\_INT32}, {\tt int32})
\end{center}
と書くのが本来の書き方による記法であるが, ここでは,
\begin{eqnarray*}
\mbox{Integer32} \  &:& \ ({\tt CMO\_INT32}, {\sl int32}\  n) \\
& & \  \mbox{--- 32 bit integer $n$ を表す. } \\
\end{eqnarray*}
と書くことを許すことにする.
このように書くことにより, 非終端記号  Integer32 は,
\begin{center}
Integer32 \  : \ ({\tt CMO\_INT32}, {\tt int32})
\end{center}
のように, 終端記号 {\tt CMO\_INT32} と {\tt int32} を成分にもち,
CMObject の 
({\tt CMO\_INT32}, {\sl int32}\ n)
は, 
32 bit integer $n$ を表現しているんだということが, 1 行でわかる.
*/
/*&jp
この記法を用いて, 前節で導入した, Primitive の CMObject を
形式的に定義しよう.
*/
/*&eg
By using this notation, let us define formally CMObjects in the group
Primitive.
*/

/*&C

\bigbreak
\noindent
Group CMObject/Primitive  requires nothing. \\
Error2, Null, Integer32, Datum, Cstring, Mathcap, List $\in$ CMObject/Primitive. \\
Document of CMObject/Primitive is at {\tt http://www.math.kobe-u.ac.jp/OpenXM}
(in English and Japanese) \\
\begin{eqnarray*}
\mbox{Error2}&:& ({\tt CMO\_ERROR2}, {\sl CMObject}\, \mbox{ob}) \\
\mbox{Null}  &:& ({\tt CMO\_NULL}) \\
\mbox{Integer32}
&:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
\mbox{Datum} &:& ({\tt CMO\_DATUM}, {\sl int32}\, \mbox{n}, {\sl byte}\, 
\mbox{data[0]}, 
\ldots , {\sl byte}\, \mbox{data[n-1]}) \\
\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\,  \mbox{ n}, 
{\sl string}\, \mbox{s}) \\
\mbox{Mathcap}&:& ({\tt CMO\_MATHCAP},{\sl CMObject}\,  \mbox{ob} ) \\
\mbox{List} &:& 
\mbox{({\tt CMO\_LIST}, {\sl int32}\, m, {\sl CMObject}\, ob[0], $\ldots$,
{\sl CMObject}\, ob[m-1])} \\
& & \mbox{---  m is the length of the list.} 
\end{eqnarray*}

*/


//&jp Cstring で, {\sl string} s の部分を {\tt byte} に分解すれば,
//&eg In the definition of ``Cstring'', if we decompose  ``{\sl string} s'' into bytes, then  ``Cstring'' should be defined as
/*&C
\begin{eqnarray*}
\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\,  \mbox{ n}, 
{\sl byte}\, \mbox{s[0]},
\ldots, {\sl byte}\ \mbox{s[n-1]})
\end{eqnarray*}
*/
//&jp となる.
/*&jp
また, 
``Group CMObject/Primitive  requires nothing''
は, 以下は, グループ CMObject/Primitive の定義であり,
このグループの CMObject を定義するのに, 要請される CMObject のグループは
ないことを示す.
``Error2, Null, Integer32, Datum, Cstring, Mathcap, List
$\in$ CMObject/Primitive''
は, グループ CMObject/Primitive には,  Error2, Null, Integer32,
Datum, Cstring なるクラスの object が属することを示す.
*/
/*&eg
``Group CMObject/Primitive  requires nothing''
means that there is no super group to define CMO's in the group Primitive.
``Error2, Null, Integer32, Datum, Cstring, Mathcap, List
$\in$ CMObject/Primitive''
means that
Error2, Null, Integer32, Datum, Cstring
are members of the group CMObject/Primitive.
*/

/*&C

*/

/*&jp 
では, 実際のデータの表現の例をみてみよう.
たとえば, 32 bit integer の 1234 は,
*/
/*&eg
Let us see examples.
32 bit integer 1234 is expressed as
*/
/*&C
\begin{center}
({\tt CMO\_INT32}, 1234)
\end{center}
*/
/*&jp
とかく.
文字列 ``Hello''  は
*/
/*&eg
The string ``Hello'' is expressed as
*/
/*&C
\begin{center}
({\tt CMO\_STRING}, 5, "Hello")
\end{center}
*/
//&jp と書く.

/*&C

*/
/*&jp
CMOexpression と, CMObject の区別を理解しておくのは重要である.
たとえば
\begin{center}
({\tt CMO\_INT32}, 234, "abc",({\tt CMO\_STRING}))
\end{center}
は CMOexpression ではあるが, CMObject ではない.
これは, 文法的には正しいプログラムだが, なにをやるのかは全く不明な
プログラムと似ている.

*/

/*&jp
さて, Open math 風 (\cite{openmath}) 
の XML 表現法も可能であり, その場合は, 上の二つの例は次のように
書く.
*/
/*&eg
CMO's are expressed by XML like Open Math (\cite{openmath}).
See example below.
*/

/*&C

\begin{verbatim}
<cmo>
 <cmo_int32>
   <int32> 1234 </int32>
 </cmo_int32>

 <cmo_string>
   <int32 for="length"> 5 </int32>
   <string> "Hello" </string>
 </cmo_string>
</cmo>
\end{verbatim}
*/

//&jp \noindent cmo\_string は次のようにあらわしてもよい.
//&eg \noindent cmo\_string may be expressed as follows.
/*&C
\begin{verbatim}

<cmo>
 <cmo_string>
   <int32 for="length"> 5 </int32>
   <byte> 'H' </byte> <byte> 'e' </byte>    <byte> 'l' </byte>
   <byte> 'l' </byte> <byte> 'o' </byte>
 </cmo_string>
</cmo>
\end{verbatim}
*/

//&jp \noindent この場合の cmo\_string の DTD による定義は次のようになる. \\
//&eg \noindent In this case, the DTD for cmo\_string is as follows; \\
//&C \verb+  <!ELEMENT cmo_string (int32, byte*)>  +
/*&C

\bigbreak
*/

/*&jp
次に, 標準 encoding 法を説明しよう.
標準 encoding 法では, cmo\_tag を ネットワークバイトオーダーの
32 bit integer {\tt int32} に,
その他のフィールドは, 定義に記述されているデータ型に従い,
byte データ {\tt byte} かまたは 
ネットワークバイトオーダーの 32 bit integer {\tt int32} に, 変換する.
*/
/*&eg
Let us explain the standard encoding method.
All {\tt int32} data are encoded into network byte order 32 bit integers
and byte data are encoded as it is.
*/

/*&C

*/

/*&jp
高速の通信方法を用いて
効率を重視する接続の場合には, {\tt int32} を network byte order
に変換する操作がおおきなオーバヘッドとなることが
報告されている.
100Mbps の通信路で 12Mbytes の {\tt CMO\_ZZ} の転送では 
約 90\% の時間が network byte order への変換についやされているという
実験データもある.
効率を重視した encoding 法については後述する \ref{subsection:byteorder}.
*/
/*&eg
When we are using a high speed network,
the translation from the internal expression of 32 bit integers to
network byte order may become a bottle neck.
There are experimental data which presents that 90 percents of the transmission
time are used
for the translation to the network byte order to send {\tt CMO\_ZZ} of size
12M bytes.
We used a 100Mbps network.
In a later section \ref{subsection:byteorder}, 
we will discuss a protocol to avoid the translation.
*/

/*&C

*/

/*&jp
標準 encoding と CMOexpression の間の変換は容易である.
前節で用いたデータの表記法,
たとえば, 
*/
/*&eg
The translation between the standard encoding and CMOexpression
is easy.
For example,
*/
/*&C
\begin{center}
\begin{tabular}{|c|c|}
\hline
{\tt int32 CMO\_INT32}& {\tt int32 1234}  \\ 
\hline
\end{tabular} 
\end{center}
*/
/*&jp
は, CMOexpression 
*/
/*&eg
is the encoding of the CMOexpression
*/
/*&C
\begin{center}
({\tt CMO\_INT32}, 1234)
\end{center}
*/
/*&jp
の 標準 encoding 法による表現である.
*/

/*&C

\bigbreak

*/

/*&jp
(実験的)
CMO および OX packets は XML 規格 \cite{xml} に準拠している.
XML 規格の Attribute を binary encode するために
特別なタグ \\
*/
/*&eg
(Experimental)
CMO and OX packets are complient to XML specification \cite{xml}.
In order to encode ``Attribute'' in XML in our binary format,
we have a tag: \\
*/
//&C \verb! #define CMO_ATTRIBUTE_LIST  (LARGEID+3) !  \\
/*&jp
を用意してある.
*/
/*&jp
たとえば Attribute {\tt font="Times-Roman" }  は \\
*/
/*&eg
For example, the attibute {\tt font="Times-Roman" } is encoded as \\
*/
/*&C
\begin{verbatim}
 (CMO_ATTRIBUTE (CMO_LIST 
                  (CMO_LIST (CMO_STRING,"font") (CMO_STRING, "Times-Roman"))))
\end{verbatim}
*/
/*&jp
と encoding される.
*/
//&C  
/*&jp
この特別な CMO tag {\tt CMO\_ATTRIBUTE\_LIST} 以外は,
XML 表現では XML のタグとして理解される.
*/
/*&eg
All tags except this special CMO tag {\tt CMO\_ATTRIBUTE\_LIST}
are XML tags in the CMO/XML expression.
*/
/*&jp
CMO/XML で {\it comment}, {\it for} と名前がついた
attributes は CMO binary expression にはエンコードされない.
*/
/*&eg
CMO/XML attributes such as {\it comment}, {\it for}
are not encoded in the CMO binary expression.
*/