The OpenMath Standard

2.1.1 Basic OpenMath objects

The Basic OpenMath Objects form the leaves of the OpenMath Object tree. A Basic OpenMath Object is of one of the following.

• (i) Integer.

  Integers in the mathematical sense, with no predefined range. They are "infinite precision" integers (also called "bignums" in computer algebra).

• (ii) IEEE floating point number.

  Double precision floating-point numbers following the IEEE 754-1985 standard [22].

• (iii) Character string.

  A Unicode Character string. This also corresponds to "characters" in XML.

• (iv) Bytearray.

  A sequence of bytes.

• (v) Symbol.

  A Symbol encodes three fields of information, a symbol name, a Content Dictionary name, and (optionally) a Content Dictionary base URI, The name of a symbol is a sequence of characters matching the regular expression described in Section 2.3. The Content Dictionary is the location of the definition of the symbol, consisting of a name (a sequence of characters matching the regular expression described in Section 2.3) and, optionally, a unique prefix called a cdbase which is used to disambiguate multiple Content Dictionaries of the same name. There are other properties of the symbol that are not explicit in these fields but whose values may be obtained by inspecting the Content Dictionary specified. These include the symbol definition, formal properties and examples and, optionally, a Role which is a restriction on where the symbol may appear in an OpenMath object. The possible roles are described in Section 2.1.4.

• (vi) Variable.

  A Variable must have a name which is a sequence of characters matching a regular expression, as described in Section 2.3.

2.1.2 Derived OpenMath Objects

Derived OpenMath objects are currently used as a way by which non-OpenMath data is embedded inside an OpenMath object. A derived OpenMath object is built as follows:

• (i) If $A$ is not an OpenMath object, then $\mathbf{foreign}\left(A\right)$ is an OpenMath foreign object. An OpenMath foreign object may optionally have an encoding field which describes how its contents should be interpreted.

2.1.3 OpenMath Objects

OpenMath objects are built recursively as follows.

• (i) Basic OpenMath objects are OpenMath objects. (Note that derived OpenMath objects are not OpenMath objects, but are used to construct OpenMath objects as described below.)

• (ii) If $A_1$, …, $A_n$  $(n>0)$  are OpenMath objects, then $$\mathbf{application}(A_1,\dots ,A_n)$$ is an OpenMath application object.

• (iii) If $S_1,\dots ,S_n$  are OpenMath symbols, and $A$ is an OpenMath object, and $A_1$, …, $A_n$  $(n>0)$ are OpenMath objects or OpenMath derived objects, then $$\mathbf{attribution}(A,S_1{A}_1,\dots ,S_n{A}_n)$$ is an OpenMath attribution object.

  $A$  is the object stripped of attributions. $S_1,\dots ,S_n$  are referred to as keys and $A_1$, …, $A_n$ as their associated values. If, after recursively applying stripping to remove attributions, the resulting un-attributed object is a variable, the original attributed object is called an attributed variable.

• (iv) If $B$ and $C$ are OpenMath objects, and $v_1$, $\dots$, $v_n$  $(n\ge 0)$ are OpenMath variables or attributed variables, then $$\mathbf{binding}(B,v_1,\dots ,v_n,C)$$ is an OpenMath binding object.

• (v) If $S$ is an OpenMath symbol and $A_1$, …, $A_n$  $(n\ge 0)$ are OpenMath objects or OpenMath derived objects, then $$\mathbf{error}(S,A_1,\dots ,A_n)$$ is an OpenMath error object.

OpenMath objects that are contstructed via rules (ii) to (v) are jointly called compound OpenMath objects

2.1.4 OpenMath Symbol Roles

We say that an OpenMath symbol is used to construct an OpenMath object if it is the first child of an OpenMath application, binding or error object, or an even-indexed child of an OpenMath attribution object (i.e. the key in a (key, value) pair). The role of an OpenMath symbol is a restriction on how it may be used to construct a compound OpenMath object and, in the case of the key in an attribution object, a clarification of how that attribution should be interpreted. The possible roles are:

1. binder The symbol may appear as the first child of an OpenMath binding object.

2. attribution The symbol may be used as key in an OpenMath attribution object, i.e. as the first element of a (key, value) pair, or in an equivalent context (for example to refer to the value of an attribution). This form of attribution may be ignored by an application, so should be used for information which does not change the meaning of the attributed OpenMath object.

3. semantic-attribution This is the same as attribution except that it modifies the meaning of the attributed OpenMath object and thus cannot be ignored by an application, without changing the meaning.

4. error The symbol may appear as the first child of an OpenMath error object.

5. application The symbol may appear as the first child of an OpenMath application object.

6. constant The symbol cannot be used to construct an OpenMath compound object.

A symbol cannot have more than one role and cannot be used to construct a compound OpenMath object in a way which requires a different role (using the definition of construct given earlier in this section). This means that one cannot use a symbol which binds some variables to construct, say, an application object. However it does not prevent the use of that symbol as an argument in an application object (where by argument we mean a child with index greater than 1).

If no role is indicated then the symbol can be used anywhere. Note that this is not the same as saying that the symbol's role is constant.

3.1.1 A Schema for the XML Encoding

The XML encoding of an OpenMath object is defined by the Relax NG schema [8] given below. Relax NG has a number of advantages over the older XSD Schema format [13], in particular it allows for tighter control of attributes and has a modular, extensible structure. Although we have made the XML form, which is given in Appendix B, normative, it is generated from the compact syntax given below. It is also very easy to restrict the schema to allow a limited set of OpenMath symbols as described in Appendix C.

Standard tools exist for generating a DTD or an XSD schema from a Relax NG Schema. Examples of such documents are given in Appendix E and Appendix D, respectively.

# RELAX NG Schema for OpenMath 2


default namespace om = "http://www.openmath.org/OpenMath"

start = OMOBJ

# OpenMath object constructor
OMOBJ = element OMOBJ { compound.attributes,
                        attribute version { xsd:string }?,
                        omel }


# Elements which can appear inside an OpenMath object
omel = 
  OMS | OMV | OMI | OMB | OMSTR | OMF | OMA | OMBIND | OME | OMATTR |OMR

# things which can be variables
omvar = OMV | attvar

attvar = element OMATTR { common.attributes,(OMATP , (OMV | attvar))}


cdbase = attribute cdbase { xsd:anyURI}?

# attributes common to all elements
common.attributes = (attribute id { xsd:ID })?

# attributes common to all elements that construct compount OM objects.
compound.attributes = common.attributes,cdbase

# symbol
OMS = element OMS { common.attributes,
                    attribute name { xsd:NCName},
                    attribute cd { xsd:NCName},
                    cdbase }

# variable
OMV = element OMV { common.attributes,
                    attribute name { xsd:NCName} }

# integer
OMI = element OMI { common.attributes,
                    xsd:string {pattern = "\s*(-\s?)?[0-9]+(\s[0-9]+)*\s*"}}
# byte array
OMB = element OMB { common.attributes, xsd:base64Binary }

# string
OMSTR = element OMSTR { common.attributes, text }

# IEEE floating point number
OMF = element OMF { common.attributes,
                    ( attribute dec { xsd:double } |
                      attribute hex { xsd:string {pattern = "[0-9A-F]+"}}) }

# apply constructor
OMA = element OMA { compound.attributes, omel+ }

# binding constructor 
OMBIND = element OMBIND { compound.attributes, omel, OMBVAR, omel }

# variables used in binding constructor
OMBVAR = element OMBVAR { common.attributes, omvar+ }

# error constructor
OME = element OME { common.attributes, OMS, (omel|OMFOREIGN)* }

# attribution constructor and attribute pair constructor
OMATTR = element OMATTR { compound.attributes, OMATP, omel }

OMATP = element OMATP { compound.attributes, (OMS, (omel | OMFOREIGN) )+ }

# foreign constructor
OMFOREIGN =  element OMFOREIGN {
    compound.attributes, attribute encoding {xsd:string}?,
   (omel|notom)* }

# Any elements not in the om namespace
# (valid om is allowed as a descendant)
notom =
  (element * - om:* {attribute * { text }*,(omel|notom)*}
   | text)

# reference constructor
OMR = element OMR { common.attributes,
                    attribute href { xsd:anyURI }
                  }

Note: In the original edition of OpenMath 2.0 as published, names are specified as being of the xsd:NCName type. When the original edition of OpenMath 2.0 was published, W3C Schema types were defined in terms of XML 1 [15]. This limited the characters allowed in a name to a subset of the characters available in Unicode 2.0, which was far more restrictive than the definition for an OpenMath name given in Section 2.3. The situation has changed with the appearance of XML 1.0 5th edition, and more specifically erratum NE17 in [16], and there is no known contradiction remaining.

3.1.2 Informal description of the XML Encoding

An encoded OpenMath object is placed inside an OMOBJ element. This element can contain the elements (and integers) described above. It can take an optional version (XML) attribute which indicates to which version of the OpenMath standard it conforms. In previous versions of this standard this attribute did not exist, so any OpenMath object without such an attribute must conform to version 1 (or equivalently 1.1) of the OpenMath standard. Objects which conform to the description given in this document should have version="2.0".

We briefly discuss the XML encoding for each type of OpenMath object starting from the basic objects.

Integers

are encoded using the OMI element around the sequence of their digits in base 10 or 16 (most significant digit first). White space may be inserted between the characters of the integer representation, this will be ignored. After ignoring white space, integers written in base 10 match the regular expression -?[0-9]+. Integers written in base 16 match -?x[0-9A-F]+. The integer 10 can be thus encoded as <OMI> 10 </OMI> or as <OMI> xA </OMI> but neither <OMI> +10 </OMI> nor <OMI> +xA </OMI> can be used.

The negative integer $-120$ can be encoded as either as decimal <OMI> -120 </OMI> or as hexadecimal <OMI> -x78 </OMI>.

Symbols

are encoded using the OMS element. This element has three (XML) attributes cd, name, and cdbase. The value of cd is the name of the Content Dictionary in which the symbol is defined and the value of name is the name of the symbol. The optional cdbase attribute is a URI that can be used to disambiguate between two content dictionaries with the same name. If a symbol does not have an explicit cdbase attribute, then it inherits its cdbase from the first ancestor in the XML tree with one, should such an element exist. In this document we have tended to omit the cdbase for clarity. For example:

<OMS cdbase="http://www.openmath.org/cd" cd="transc1" name="sin"/>

is the encoding of the symbol named sin in the Content Dictionary named transc1, which is part of the collection maintained by the OpenMath Society.

As described in Section 2.3, the three attributes of the OMS can be used to build a URI reference for the symbol, for use in contexts where URI-based referencing mechanisms are used. For example the URI for the above symbol is http://www.openmath.org/cd/transc1#sin.

Note that the role attribute described in Section 2.1.4 is contained in the Content Dictionary and is not part of the encoding of a symbol, also the cdbase attribute need not be explicit on each OMS as it is inherited from any ancestor element.

Variables

are encoded using the OMV element, with only one (XML) attribute, name, whose value is the variable name. For instance, the encoding of the object representing the variable $x$ is: <OMV name="x"/>

Floating-point numbers

are encoded using the OMF element that has either the (XML) attribute dec or the (XML) attribute hex. The two (XML) attributes cannot be present simultaneously. The value of dec is the floating-point number expressed in base 10, using the common syntax:

(-?)([0-9]+)?("."[0-9]+)?([eE](-?)[0-9]+)?.

or one of the special values: INF, -INF or NaN.

The value of hex is a base 16 representation of the 64 bits of the IEEE Double. Thus the number represents mantissa, exponent, and sign in network byte order. This consists of a string of 16 digits 0-9, A-F.

For example, both <OMF dec="1.0e-10"/> and <OMF hex="3DDB7CDFD9D7BDBB"/> are valid representations of the floating point number $1\times {10}^{-10}$.

The symbols INF, -INF and NaN represent positive and negative infinity, and not a number as defined in [22]. Note that while infinities have a unique representation, it is possible for NaNs to contain extra information about how they were generated and if this informations is to be preserved then the hexadecimal representation must be used. For example <OMF hex="FFF8000000000000"/> and <OMF hex="FFF8000000000001"/> are both hexadecimal representations of NaNs.

Character strings

are encoded using the OMSTR element. Its content is a Unicode text. Note that as always in XML the characters < and & need to be represented by the entity references < and & respectively.

Bytearrays

are encoded using the OMB element. Its content is a sequence of characters that is a base64 encoding of the data. The base64 encoding is defined in RFC 2045 [2]. Basically, it represents an arbitrary sequence of octets using 64 "digits" (A through Z, a through z, 0 through 9, + and /, in order of increasing value). Three octets are represented as four digits (the = character is used for padding at the end of the data). All line breaks and carriage return, space, form feed and horizontal tabulation characters are ignored. The reader is referred to [2] for more detailed information.

Applications

are encoded using the OMA element. The application whose head is the OpenMath object $e_0$ and whose arguments are the OpenMath objects $e_1$, …, $e_n$ is encoded as <OMA> $C_0$  $C_1$… $C_n$ </OMA> where $C_i$ is the encoding of $e_i$.

For example, $\mathbf{application}(\sin ,x)$ is encoded as:

<OMA>  
  <OMS cd="transc1" name="sin"/> 
  <OMV name="x"/>  
</OMA>

provided that the symbol sin is defined to be a function symbol in a Content Dictionary named transc1.

Binding

is encoded using the OMBIND element. The binding by the OpenMath object $b$ of the OpenMath variables $x_1$, $x_2$, $\dots$, $x_n$ in the object $c$ is encoded as <OMBIND> $B$  <OMBVAR> $X_1$  $\dots$  $X_n$ </OMBVAR> $C$ </OMBIND> where $B$, $C$, and $X_i$ are the encodings of $b$, $c$  and $x_i$, respectively.

For instance the encoding of $\mathbf{binding}(\mathrm{lambda},x,\mathbf{application}(\sin ,x\left)\right)$ is:

<OMBIND>
  <OMS cd="fns1" name="lambda"/>  
  <OMBVAR><OMV name="x"/></OMBVAR>  
  <OMA>
    <OMS cd="transc1" name="sin"/> 
    <OMV name="x"/>  
  </OMA>
</OMBIND>

Binders are defined in Content Dictionaries, in particular, the symbol lambda is defined in the Content Dictionary fns1 for functions over functions.

Attributions

are encoded using the OMATTR element. If the OpenMath object $e$ is attributed with ( $s_1$, $e_1$), …, ( $s_n$, $e_n$) pairs (where $s_i$ are the attributes), it is encoded as <OMATTR> <OMATP> $S_1$  $C_1$ … $S_n$  $C_n$ </OMATP> $E$ </OMATTR> where $S_i$ is the encoding of the symbol $s_i$, $C_i$ of the object $e_i$ and $E$ is the encoding of $e$.

Examples are the use of attribution to decorate a group by its automorphism group:

<OMATTR>    
  <OMATP>
    <OMS cd="groups" name="automorphism_group" />  
    [..group-encoding..] 
  </OMATP>  
  [..group-encoding..] 
</OMATTR>

or to express the type of a variable:

<OMATTR>    
  <OMATP>
    <OMS cd="ecc" name="type" /> 
    <OMS cd="ecc" name="real" />
  </OMATP> 
  <OMV name="x" />
</OMATTR>

A special use of attributions is to associate non-OpenMath data with an OpenMath object. This is done using the OMFOREIGN element. The children of this element must be well-formed XML. For example the attribution of the OpenMath object $\sin \left(x\right)$ with its representation in Presentation MathML is:

<OMATTR>
  <OMATP>
    <OMS cd="annotations1" name="presentation-form"/>  
    <OMFOREIGN encoding="MathML-Presentation">
      <math xmlns="http://www.w3.org/1998/Math/MathML">
        <mi>sin</mi><mfenced><mi>x</mi></mfenced>
      </math>
    </OMFOREIGN>  
  </OMATP>
  <OMA>
   <OMS cd="transc1" name="sin"/> 
   <OMV name="x"/>  
  </OMA>
</OMATTR>

Of course not everything has a natural XML encoding in this way and often the contents of a OMFOREIGN will just be data or some kind of encoded string. For example the attribution of the previous object with its LaTeX representation could be achieved as follows:

<OMATTR>
  <OMATP>
    <OMS cd="annotations1" name="presentation-form"/>  
    <OMFOREIGN encoding="text/x-latex">\sin(x)</OMFOREIGN>  
  </OMATP>
  <OMA>
    <OMS cd="transc1" name="sin"/> 
    <OMV name="x"/>  
  </OMA>
</OMATTR>

For a discussion on the use of the encoding attribute see Section 5.2.

Errors

are encoded using the OME element. The error whose symbol is $s$ and whose arguments are the OpenMath objects or OpenMath derived objects $e_1$, …, $e_n$ is encoded as <OME> $C_s$  $C_1$… $C_n$ </OME> where $C_s$ is the encoding of $s$ and $C_i$ the encoding of $e_i$.

If an aritherror Content Dictionary contained a DivisionByZero symbol, then the object $\mathbf{error}(\mathrm{DivisionByZero},\mathbf{application}(\mathrm{divide},x,0\left)\right)$ would be encoded as follows:

<OME>
  <OMS cd="aritherror" name="DivisionByZero"/>  
  <OMA>
    <OMS cd="arith1" name="divide" />
    <OMV name="x"/>  
    <OMI> 0 </OMI>
  </OMA> 
 </OME>

If a mathml Content Dictionary contained an unhandled_csymbol symbol, then an OpenMath to MathML translator might return an error such as:

<OME>
  <OMS cd="mathml" name="unhandled_csymbol"/>  
  <OMFOREIGN encoding="MathML-Content">
    <mathml:csymbol xmlns:mathml="http://www.w3.org/1998/Math/MathML/"
                    definitionURL="http://www.nag.co.uk/Airy#A">
      <mathml:mo>Ai</mathml:mo>
    </mathml:csymbol>
  </OMFOREIGN> 
 </OME>

Note that it is possible to embed fragments of valid OpenMath inside an OMFOREIGN element but that it cannot contain invalid OpenMath. In addition, the arguments to an OMERROR must be well-formed XML. If an application wishes to signal that the OpenMath it has received is invalid or is not well-formed then the offending data must be encoded as a string. For example:

<OME>
  <OMS cd="parser" name="invalid_XML"/>  
  <OMSTR>
    &ltOMA&gt; &lt;OMS name="cos" cd="transc1"&gt;
      &lt;OMV name="v"&gt; &lt;/OMA&gt;
  </OMSTR> 
 </OME>

Note that the "<" and ">" characters have been escaped as is usual in an XML document.

References

OpenMath integers, floating point numbers, character strings, bytearrays, applications, binding, attributions can also be encoded as an empty OMR element with an href attribute whose value is the value of a URI referencing an id attribute of an OpenMath object of that type. The OpenMath element represented by this OMR reference is a copy of the OpenMath element referenced href attribute. Note that this copy is structurally equal, but not identical to the element referenced. These URI refererences will often be relative, in which case they are resolved using the base URI of the document containing the OpenMath.

For instance, the OpenMath object $$\mathbf{application}(f,\mathbf{application}(f,\mathbf{application}\left(f,a,a\right),\mathbf{application}\left(f,a,a\right)),\mathbf{application}(f,\mathbf{application}\left(f,a,a\right),\mathbf{application}\left(f,a,a\right)))$$

can be encoded in the XML encoding as either one of the XML encodings given in Figure 3.1 (and some intermediate versions as well).

<OMOBJ version="2.0">         <OMOBJ version="2.0">
  <OMA>                         <OMA>
    <OMV name="f"/>               <OMV name="f"/> 
    <OMA>                         <OMA id="t1">
      <OMV name="f"/>               <OMV name="f"/>
      <OMA>                         <OMA id="t11">
        <OMV name="f"/>               <OMV name="f"/>
        <OMV name="a"/>               <OMV name="a"/>
        <OMV name="a"/>               <OMV name="a"/>
      </OMA>                        </OMA>
      <OMA>                         <OMR href="#t11"/>
        <OMV name="f"/>
        <OMV name="a"/> 
        <OMV name="a"/>
      </OMA>                                
    </OMA>                      </OMA>
    <OMA>                       <OMR href="#t1"/>
      <OMV name="f"/>
      <OMA>
        <OMV name="f"/>
        <OMV name="a"/>
        <OMV name="a"/>
      </OMA>
      <OMA>
        <OMV name="f"/>
        <OMV name="a"/>
        <OMV name="a"/>
      </OMA>
    </OMA>
  </OMA>
</OMOBJ>                     </OMOBJ>

3.1.3 Some Notes on References

We say that an OpenMath element dominates all its children and all elements they dominate. An OMR element dominates its target, i.e. the element that carries the id attribute pointed to by the xref attribute. For instance in the representation in Figure 3.1, the OMA element with id="t1" and also the second OMR dominate the OMA element with id="t11".

<OMOBJ version="2.0">
  <OMA id="foo">
    <OMS cd="arith1" name="divide"/>
    <OMI>1</OMI>
    <OMA>
       <OMS cd="arith1" name="plus"/>
       <OMI>1</OMI>
       <OMR xref="foo"/>
    </OMA> 
  </OMA>
</OMOBJ>

<OMOBJ version="2.0">                   <OMOBJ version="2.0">
  <OMA id="bar">                         <OMA id="baz">
    <OMS cd="arith1" name="plus"/>         <OMS cd="arith1" name="plus"/>
    <OMI>1</OMI>                           <OMI>1</OMI>
    <OMR xref="baz"/>                      <OMR xref="bar"/>
  </OMA>                                 </OMA>
</OMOBJ>                               </OMOBJ>

<OMBIND id="outer">
  <OMS cd="fns1" name="lambda"/>
  <OMBVAR><OMV name="X"/></OMBVAR>
  <OMA>
    <OMV name="f"/>
    <OMBIND id="inner">
      <OMS cd="fns1" name="lambda"/>
      <OMBVAR><OMV name="X"/></OMBVAR>
      <OMR id="copy" href="#orig"/>
    </OMBIND>
    <OMA id="orig"><OMV name="g"/><OMV name="X"/></OMA>
  </OMA>
</OMBIND>

3.1.4 Embedding OpenMath in XML Documents

The above encoding of XML encoded OpenMath specifies the grammar to be used in files that encode a single OpenMath object, and specifies the character streams that a conforming OpenMath application should be able to accept or produce.

When embedding XML encoded OpenMath objects into a larger XML document one may wish, or need, to use other XML features. For example use of extra XML attributes to specify XML Namespaces [14] or xml:lang attributes to specify the language used in strings [17].

If such XML features are used then the XML application controlling the document must, if passing the OpenMath fragment to an OpenMath application, remove any such extra attributes and must ensure that the fragment is encoded according to the schema specified above.

3.2.1 A Grammar for the Binary Encoding

Figure 3.3 gives a grammar for the binary encoding ("start" is the start symbol)..

The following conventions are used in this section: [ $n$] denotes a byte whose value is the integer $n$ ( $n$ can range from 0 to 255), { $m$} denotes four bytes representing the (unsigned) integer $m$ in network byte order, [_] denotes an arbitrary byte, {_} denotes an arbitrary sequence of four bytes. Finally, empty stands for the empty list of tokens.

xxxx: $n$, where xxxx is one of symbname, cdname, varname, uri, id, digits, or bytes denotes a sequence of $n$ bytes that conforms to the constraints on xxxx strings. For instance, for symbname, varname, or cdname this is the regular expression described in Section 2.3, for uri it is the grammar for URIs in [7].

3.2.2 Description of the Grammar

An OpenMath object is encoded as a sequence of bytes starting with the begin object tag (values 24 and 88) and ending with the end object tag (value 25). These are similar to the <OMOBJ> and </OMOBJ> tags of the XML encoding. Objects with start token [88] have two additional bytes $m$ and $n$ that characterize the version ( $m.n$) of the encoding directly after the start token. This is similar to <OMOBJ version="m.n">

The encoding of each kind of OpenMath object begins with a tag that is a single byte, holding a token identifier that describes the kind of object, two flags, and a status bit. The identifier is stored in the first five bits (1 to 5). Bit 6 is used as a status bit which is currently only used for managing streaming of some basic objects. Bits 7 and 8 are the sharing flag and the long flag. The sharing flag indicates that the encoded object may be shared in another (part of an) object somewhere else (see Section 3.2.4.2). Note that if the sharing flag is set (in the right column of the grammar in Figure 3.3, then the encoding includes a representation of an identifier that serves as the target of a reference (internal with token identifier 30 or external with token identifier 31). If the long flag is set, this signifies that the names, strings, and data fields in the encoded OpenMath object are longer than 255 bytes or characters.

The concept of structure sharing in OpenMath encodings and in particular the sharing bit in the binary encoding has been introduced in OpenMath 2 (see section Section 3.2.4.2 for details). The binary encoding in OpenMath 2 leaves the tokens with sharing flag 0 unchanged to ensure OpenMath 1 compatibility. To make use of functionality like the version attribute on the OpenMath object introduced in OpenMath 2, the tokens with sharing flag 1 should be used.

To facilitate the streaming of OpenMath objects, some basic objects (integers, strings, bytearrays, and foreign objects) have variant token identifiers with the fifth bit set. The idea behind this is that these basic objects can be split into packets. If the fifth bit is not set, this packet is the final packet of the basic object. If the bit is set, then more packets of the basic object will follow directly after this one. Note that all packets making up a basic object must have the same token identifier (up to the fifth bit). In Figure 3.4 we have represented an integer that is split up into three packets.

Here is a description of the binary encodings of every kind of OpenMath object:

Integers

are encoded depending on how large they are. There are four possible formats. Integers between -128 and 127 are encoded as the small integer tags (token identifier 1) followed by a single byte that is the value of the integer (interpreted as a signed character). For example 16 is encoded as 0x01 0x10. Integers between ${-2}^{31}$  ( $-2147483648$) and $2^{31}-1$  ( $2147483647$) are encoded as the small integer tag with the long flag set followed by the integer encoded in four bytes (network byte order: the most significant byte comes first). For example, 128 is encoded as 0x81 0x00000080. The most general encoding begins with the big integer tag (token identifier 2) with the long flag set if the number of bytes in the encoding of the digits is greater or equal than 256. It is followed by the length (in bytes) of the sequence of digits, encoded on one byte (0 to 255, if the long flag was not set) or four bytes (network byte order, if the long flag was set). It is then followed by a byte describing the sign and the base. This 'sign/base' byte is + (0x2B) or - (0x2D) for the sign or-ed with the base mask bits that can be 0 for base 10 or 0x40 for base 16 or 0x80 for "base 256". It is followed by the sequence of digits (as characters for bases 10 and 16 as in the XML encoding, and as bytes for base 256) in their natural order. For example, the decimal number 8589934592 ( $2^{33}$) is encoded as 0x02 0x0A 0x2B 0x38 0x35 0x38 0x39 0x39 0x33 0x34 0x35 0x39 0x32 and the hexadecimal number xfffffff1 is encoded as 0x02 0x08 0x6b 0x66 0x66 0x66 0x66 0x66 0x66 0x66 0x31 in the base 16 character encoding and as 0x02 0x04 0xab 0xFF 0xFF 0xFF 0xF1 in the byte encoding (base 256).

Note that it is permitted to encode a "small" integer in any "bigger" format.

To splice sequences of integer packets into integers, we have to consider three cases: In the case of token identifiers 1, 33, and 65 the sequence of packets is treated as a sequence of integer digits to the base of $2^7$ (most significant first). The case of token identifiers 129, 161, and 193 is analogous with digits of base $2^{31}$. In the case of token identifiers 2, 34, 66, 130, 162, and 194 the integer is assembled by concatenating the string of decimal digits in the packets in sequence order (which corresponds to most significant first). Note that in all cases only the sequence-initial packet may contain a signed integer. The sign of this packet determines the sign of the overall integer.

Byte	Hex	Meaning		Byte	Hex	Meaning
1	22	begin streamed big integer tag		7	2B	sign + (disregarded)
2	FF	255 digits in packet		8	...	the 255 digits as characters
3	2B	sign +		9	2	begin final big integer tag
4	...	the 255 digits as characters		10	42	68 digits in packet
5	22	begin streamed big integer tag		11	2B	sign + (disregarded)
6	FF	255 digits in packet		12	...	the 68 digits as characters

Figure 3.4 Streaming a large Integer in the Binary Encoding.

Symbols

are encoded as the symbol tags (token identifier 8) with the long flag set if the maximum of the length in bytes in the UTF-8 encoding of the Content Dictionary name or the symbol name is greater than or equal to 256. The symbol tag is followed by the length in bytes in the UTF-8 encoding of the Content Dictionary name, the symbol name, and the id (if the shared bit was set) as a byte (if the long flag was not set) or a four byte integer (in network byte order). These are followed by the bytes of the UTF-8 encoding of the Content Dictionary name, the symbol name, and the id.

Variables

are encoded using the variable tags (token identifiers 5) with the long flag set if the number of bytes in the UTF-8 encoding of the variable name is greater than or equal to 256. Then, there is the number of characters as a byte (if the long flag was not set) or a four byte integer (in network byte order), followed by the characters of the name of the variable. For example, the variable x is encoded as 0x05 0x01 0x78.

Floating-point number

are encoded using the floating-point number tags (token identifier 3) followed by eight bytes that are the IEEE 754 representation [22], most significant bytes first. For example, $1\times {10}^{-10}$  is encoded as 0x03 3ddb7cdfd9d7bdbb.

Character string

are encoded in two ways depending on whether the string is encoded in UTF-16 or ISO-8859-1 (LATIN-1). In the case of LATIN-1 it is encoded as the one byte character string tags (token identifier 6) with the long flag set if the number of bytes (characters) in the string is greater than or equal to 256. Then, there is the number of characters as a byte (if the length flag was not set) or a four byte integer (in network byte order), followed by the characters in the string. If the string is encoded in UTF-16, it is encoded as the UTF-16 character string tags (token identifier 7) with the long flag set if the number of characters in the string is greater or equal to 256. Then, there is the number of UTF-16 units, which will be the number of characters unless characters in the higher planes of Unicode are used, as a byte (if the long flag was not set) or a four byte integer (in network byte order), followed by the characters (UTF-16 encoded Unicode).

Sequences of string packets are assumed to have the same encoding for every packet. They are assembled into strings by concatenating the strings in the packets in sequence order.

Bytearrays

are encoded using the bytearray tags (token identifier 4) with the long flag set if the number of elements is greater than or equal to 256. Then, there is the number of elements, as a byte (if the long flag was not set) or a four byte integer (in network byte order), followed by the elements of the arrays in their normal order.

Sequences of bytearray packets are assembled into byte arrays by concatenating the bytearrays in the packets in sequence order.

Foreign Objects

are encoded using the foreign object tags (token identifier 12) with the long flag set if the number of bytes is greater than or equal to 256 and the streaming bit set for dividing it up into packets. Then, there is the number $n$ of bytes used to encode the encoding, and the number $m$ of bytes used to encode the foreign object. $n$ and $m$ are represented as a byte (if the long flag was not set) or a four byte integer (in network byte order). These numbers are followed by an $n$-byte representation of the encoding attribute and an $m$ byte sequence of bytes encoding the foreign object in their normal order (we call these the payload bytes). The encoding attribute is encoded in UTF-8.

Sequences of foreign object packets are assembled into foreign objects by concatenating the payload bytes in the packets in sequence order.

Note that the foreign object is encoded as a stream of bytes, not a stream of characters. Character based formats (including XML based formats) should be encoded in UTF-8 to produce a stream of bytes to use as the payload of the foreign object.

cdbase scopes

are encoded using the token identifier 9. The purpose of these scoping devices is to associate a cdbase with an object. The start token [9] (or [137] if the long flag is set) is followed by a single-byte (or 4-byte- if the long flag is set) number $n$ and then by a seqence of $n$  bytes that represent the value of the cdbase attribute (a URI) in UTF-8 encoding. This is then followed by the binary encoding of a single object: the object over which this cdbase attribute has scope.

Applications

are encoded using the application tags (token identifiers 16 and 17). More precisely, the application of $E_0$ to $E_1$… $E_n$ is encoded using the application tags (token identifier 16), the sequence of the encodings of $E_0$ to $E_n$ and the end application tags (token identifier 17).

Bindings

are encoded using the binding tags (token identifiers 26 and 27). More precisely, the binding by $B$ of variables $V_1$… $V_n$ in $C$ is encoded as the binding tag (token identifier 26), followed by the encoding of $B$, followed by the binding variables tags (token identifier 28), followed by the encodings of the variables $V_1$ … $V_n$, followed by the end binding variables tags (token identifier 29), followed by the encoding of $C$, followed by the end binding tags (token identifier 27).

Attributions

are encoded using the attribution tags (token identifiers 18 and 19). More precisely, attribution of the object $E$ with ( $S_1$, $E_1$), $\dots$  ( $S_n$, $E_n$) pairs (where $S_i$ are the attributes) is encoded as the attributed object tag (token identifier 18), followed by the encoding of the attribute pairs as the attribute pairs tags (token identifier 20), followed by the encoding of each symbol and value, followed by the end attribute pairs tag (token identifier 21), followed by the encoding of $E$, followed by the end attributed object tag (token identifier 19).

Errors

are encoded using the error tags (token identifiers 22 and 23). More precisely, $S_0$ applied to $E_1$… $E_n$ is encoded as the error tag (token identifier 22), the encoding of $S_0$, the sequence of the encodings of $E_0$ to $E_n$ and the end error tag (token identifier 23).

Internal References

are encoded using the internal reference tags [30] and [30+128] (the sharing flag cannot be set on this tag, since chains of references are not allowed in the OpenMath binary encoding) with long flag set if the number of OpenMath sub-objects in the encoded OpenMath is greater than or equal to 256. Then, there is the ordinal number of the referenced OpenMath object as a byte (if the long flag was not set) or a four byte integer (in network byte order).

External References

are encoded using the external reference tags [31] and [31+128] (the sharing flag cannot be set on this tag, since chains of references are not allowed in the OpenMath binary encoding) with the long flag set if the number of bytes in the reference URI is greater than or equal to 256. Then, there is the number of bytes in the URI used for the external reference as a byte (if the long flag was not set) or a four byte integer (in network byte order), followed by the URI.

3.2.3 Example of Binary Encoding

As a simple example of the binary encoding, we can consider the OpenMath object $$\mathbf{application}(\mathrm{times},\mathbf{application}(\mathrm{plus},x,y),\mathbf{application}(\mathrm{plus},x,z))$$ It is binary encoded as the sequence of bytes given in Figure 3.5.

3.2.4 Sharing

OpenMath 2 introduced a new sharing mechanism, described below. First however we describe the original OpenMath 1 mechanism.

3.2.5 Implementation Note

A typical implementation of the binary encoding comes in two parts. The first part deals with the unshared encodings, i.e. objects starting with the identifier [24].

This part uses four tables, each of 256 entries, for symbol, variables, 8 bit character strings whose lengths are less than 256 characters and 16 bit character strings whose lengths are less than 256 characters. When an object is read, all the tables are first flushed. Each time a sharable sub-object is read, it is entered in the corresponding table if it is not full. When a reference to the shared $i$-th object of a given type is read, it stands for the $i$-th entry in the corresponding table. It is an encoding error if the $i$-th position in the table has not already been assigned (i.e. forward references are not allowed). Sharing is not mandatory, there may be duplicate entries in the tables (if the application that wrote the object chose not to share optimally).

The part for the shared representations of OpenMath objects uses an unbounded array for storing shared sub-objects. Whenever an object has the shared flag set, then it is read and a pointer to the generated data structure is stored at the next position of the array. Whenever a reference of the form [30] [_] is encountered, the array is queried for the value at [_] and analogously for [30+128] {_}. Note that the application can decide to copy the value or share it among sub-terms as long as it respects the identity conditions given by the tree-nature of the OpenMath objects. The implementation must take care to ensure that no variables are captured during this process (see section Section 3.1.3.2), and possibly have methods for recovering from cyclic dependency relations (this can be done by standard loop-checking methods).

Writing an object is simple. The tables are first flushed. Each time a sharable sub-object is encountered (in the natural order of output given by the encoding), it is either entered in the corresponding table (if it is not full) and output in the normal way or replaced by the right reference if it is already present in the table.

3.2.6 Relation to the OpenMath 1 binary encoding

The OpenMath 2 binary encoding significantly extends the OpenMath 1 binary encoding to accommodate the new features and in particular sharing of sub-objects. The tags and structure of the OpenMath 1 binary encoding are still present in the current OpenMath binary encoding, so that binary encoded OpenMath 1 objects are still valid in the OpenMath 2 binary encoding and correspond to the same abstract OpenMath objects. In some cases, the binary encoding tags without the shared flag can still be used as more compact representations of the objects (which are not shared, and do not have an identifier).

As the binary encoding is geared towards compactness, OpenMath objects should be constructed so as to maximise internal sharing (if computationally feasible). Note that since sharing is done only at the encoding level, this does not alter the meaning of an OpenMath object, only allows it to be represented more compactly.

4.2.1 Content Dictionary Status

The status of a Content Dictionary can be either

• official: approved by the OpenMath Society according to the procedure outlined in Section 4.5;

• experimental: under development and thus liable to change;

• private: used by a private group of OpenMath users;

• obsolete: an obsolete Content Dictionary kept only for archival purposes.

4.2.2 Content Dictionary Version Numbers

A version number must consist of two parts, a major version and a revision, both of which should be non-negative integers. In CDs that do not have status experimental, the version number should be a positive integer.

Unless a CD has status experimental, no changes should ever be introduced that invalidate objects built with previous versions. Any change that influences phrasebook compliance, like adding a new symbol to a Content Dictionary, is considered a major change and should be reflected by an increase in the major version number. Other changes, like adding an example or correcting a description, are considered minor changes. For minor changes the version number is not changed, but an increase should be made to the revision number. Note that a change such as removing a symbol should not be made unless the CD has status experimental. Should this be required then a new CD with a different name should be produced so as not to invalidate existing objects.

When the major version number is increased, the revision number is normally reset to zero.

As detailed in Chapter 5, OpenMath compliant applications state which versions of which CDs they support.

4.3.1 The Relax NG Schema for Content Dictionaries

# *********************************************
# 
# Relax NG Schema for OpenMath CD
# 
# *********************************************

default namespace = "http://www.openmath.org/OpenMathCD"

include "openmath2.rnc" {start = CD}

CDComment = element CDComment { text }
CDName = element CDName { xsd:NCName }
CDUses = element CDUses { CDName* }
CDURL = element CDURL { xsd:anyURI }
CDBase = element CDBase { xsd:anyURI }
text-or-om = (text | OMOBJ)*
CDReviewDate = element CDReviewDate { xsd:date }
CDDate = element CDDate { xsd:date }
CDVersion = element CDVersion { xsd:nonNegativeInteger }
CDRevision = element CDRevision { xsd:nonNegativeInteger }
CDStatus = element CDStatus {
   "official" |
   "experimental" |
   "private" |
   "obsolete"}
Description = element Description { text }
Name = element Name { xsd:NCName }
Role = element Role {
   "binder" |
   "attribution" |
   "semantic-attribution" |
   "error" |
   "application" |
   "constant" }
CMP = element CMP { text }
FMP = element FMP { 
  attribute kind {xsd:string}?,
  OMOBJ
  }
# allow embedded OM
Example = element Example { text-or-om }
CDDefinition =
  element CDDefinition {
    CDComment*,
    (Name & Role? & Description),
   (CDComment | Example | FMP | CMP)*
  }
CD =
  element CD {
    (CDComment* & Description? &
     CDName & CDURL? & CDBase? &
     CDReviewDate? & CDDate & CDStatus & 
     CDUses? & 
     CDVersion & CDRevision),
    ( CDDefinition,CDComment* )+
  }


      

4.3.2 Further Description of the CD Schema

We now describe the elements used in the above schema in terms of the abstract description of CDs in Section 4.2. Unless stated otherwise information is encoded as the content of the relevant element.

CDName

The name of the Content Dictionary.

Description

The text occurring in the Description element is used to give a description of the enclosing element, which could be a symbol or the entire Content Dictionary. The content of this element can be any XML text.

CDReviewDate

The review date of the Content Dictionary.

CDDate

The revision date of this version of the Content Dictionary.

CDVersion

The major version number of the CD.

CDRevision

The minor version number of the CD.

CDStatus

The status of the Content Dictionary.

CDBase

The CD base of the CD.

CDURL

The text occurring in the CDURL element should be a valid URL where the source file for the Content Dictionary encoding can be found (if it exists). The filename should conform to ISO 9660 [11].

CDUses

The content of this element should be a series of CDName elements, each naming a Content Dictionary used in the Example and FMPs of the current Content Dictionary. This element is optional and deprecated since the information can easily be extracted automatically.

CDComment

The content of this element should be text that does not convey any crucial information concerning the current Content Dictionary. It can be used in the Content Dictionary header to report the author of the Content Dictionary and to log change information. In the body of the Content Dictionary, it can be used to attach extra remarks to certain symbols.

CDDefinition

The element which contains the definition of an individual symbol.

Name

The name of a symbol.

Role

The role of a symbol: it must be one of binder, attribution, semantic-attribution, error, application, or constant.

Example

The text occurring in the Example element is used to give examples of the enclosing symbol, and can be any XML text. In addition to text the element may contain examples as XML encoded OpenMath, inside OMOBJ elements. Note that Examples must be with respect to some symbol and cannot be "loose" in the Content Dictionary.

CMP

A Commented Mathematical Property.

FMP

A Formal Mathematical Property. It may take an optional kind attribute.

4.4.1 Signature Dictionaries

OpenMath may be used with any type system. One just needs to produce a Content Dictionary which gives the constructors of the type system, and then one may build OpenMath objects representing types in the given type system. These are typically associated with OpenMath objects via the OpenMath attribution constructor.

A Small Type System, called STS, has been designed to give semi-formal signatures to OpenMath symbols and is documented in [5]. The signature file given in Appendix A.3 is based on this formalism. Using the same mechanism, [4] shows how pure type systems can also be employed to assign types to OpenMath symbols.

# *********************************************
# 
# Relax NG Schema for OpenMath CD Signatures
# 
# *********************************************

default namespace = "http://www.openmath.org/OpenMathCDS"

include "openmath2.rnc" { start = CDSignatures }

CDSComment = element CDSComment { text }
CDSReviewDate = element CDSReviewDate { text }
CDSStatus = element CDSStatus {
   "official" |
   "experimental" |
   "private" |
   "obsolete"}
CDSignatures =
  element CDSignatures {
    attlist.CDSignatures,
    (CDSComment)*,
    (CDSReviewDate? & CDSStatus),
    (CDSComment | Signature)*
  }
attlist.CDSignatures =
  attribute cd { xsd:NCName },
  attribute type { xsd:NCName }
Signature = element Signature { attlist.Signature, OMOBJ? }
attlist.Signature = attribute name { text }

<Signature name="plus">
<OMOBJ version="2.0">
 <OMA>
  <OMS name="mapsto" cd="sts"/>
  <OMA>
   <OMS name="nassoc" cd="sts"/> 
   <OMV name="AbelianSemiGroup"/>
  </OMA>
  <OMV name="AbelianSemiGroup"/>
 </OMA>
</OMOBJ>
</Signature>

4.4.2 CDGroups

The CD Group mechanism is a convenience mechanism for identifying collections of CDs. A CD Group file is an XML document used in the (static or dynamic) negotiation phase where communicating applications declare and agree on the Content Dictionaries which they process. It is a complement, or an alternative, to the individual declaration of Content Dictionaries understood by an application. Note that CD Groups do not affect the OpenMath objects themselves. Symbols in an object always refer to content dictionaries, not groups.

For an application to declare that it "understands CDGroup G" is exactly equivalent to, and interchangeable with, the declaration that it "understands Content Dictionaries $x_1$, $x_2$,  …  $x_n$", where $x_1$,  …  $x_n$ are the members of CDGroup G.

# Schema for OpenMath CD groups

# info on the CD group itself

default namespace = "http://www.openmath.org/OpenMathCDG"

CDGroupName = element CDGroupName { xsd:NCName }
CDGroupVersion = element CDGroupVersion { xsd:nonNegativeInteger }
CDGroupRevision = element CDGroupRevision { xsd:nonNegativeInteger }
CDGroupURL = element CDGroupURL { text }
CDGroupDescription = element CDGroupDescription { text }
# info on the CDs in the group
CDComment = element CDComment { text }
CDGroupMember =
  element CDGroupMember {
    CDComment?, CDName, CDVersion?, CDURL?
  }
CDName = element CDName { xsd:NCName }
CDVersion = element CDVersion { xsd:nonNegativeInteger }
CDURL = element CDURL { text }
# structure of the group
CDGroup =
  element CDGroup {
    CDGroupName,
    CDGroupVersion,
    CDGroupRevision?,
    CDGroupURL,
    CDGroupDescription,
    (CDGroupMember | CDComment)*
  }
start = CDGroup

5.1.1 The XML Encoding