2. Syntax of MP and Prototype Annotations

The syntax of data transmitted by MP may be described by five levels:

1.

Messages

2.

Trees

3.

Node Packets

4.

Data limbs¹

5.

Annotation Packets

On its highest level, an MP message is the unit of communication between applications, bracketed by BeginMsg and EndMsg markers. On the MP API level, messages are separated by a concluding MP_EndMsgReset() call on the sending side, and by a MP_SkipMsg() or MP_InitMsg() call on the receiving side.

A message consists of zero or more MP Trees, although usually one tree per message is communicated. An MP Tree is built from node packets, annotations packets, and data limbs and might be thought of as the MP equivalent of an expression used by most CASs.

A data limb consists of ``pure'' data; no type information is directly attached to data limbs. Instead, their type is implictly encoded by the place at which a data limb appears in an MP Tree. Using the MP API, data limbs are usually sent using IMP_Put<type>() routines (e.g., IMP_PutSint32()) and received using IMP_Get<type>() routines (e.g., IMP_GetSint32()). In the style of the MP API, we will use the notation IMP_<type> in this report to refer to a data limb (e.g., IMP_Sint32 refers to a data limb that is four bytes long and encodes an Sint32 value).

An annotation packet consists of a header which, for valuated annotations, is immediately followed by an MP Tree. Whether or not an annotation is valuated is encoded in the annotation header. A node contains exactly as many annotation packets as is specified in the node packet header. Annotation packets are usually sent using MP_PutAnnotationPacket() and received using MP_GetAnnotationPacket().

A node packet consists of a header, and, possibly, a data limb. The header encodes the type of the node (indicating the type of the data carried in its data field), a dictionary tag field identifying the dictionary in which the node's value is defined (for relevant types), the number of annotation packets attached to the node, and, for operator node packets (see below), the number of arguments of the node. On the MP API level, node packets are usually sent using MP_Put<type>Packet() routines (e.g., MP_PutSint32Packet()) and received using MP_Get<type>Packet() routines (e.g., MP_PutGetPacket()). Following the style of the MP API, we will use the notation MP_<type> in this report to refer to a node packet (e.g., MP_Sint32 refers to an Sint32 node packet). From a syntactic point of view, node packets are furthermore categorized w.r.t. two criteria:

1.

basic versus operator node packets
Basic node packets appear at the leaves of an MP Tree and may not be followed by argument packets. In contrast, operator packets have arguments and are therefore interior nodes of an MP Tree.

2.

common versus ordinary node packets
Unlike an ``ordinary'' node packet, a common node packet does not have a separate data limb containing the node's value, but instead has the node's value carried in the node packet header. In contrast, the header of an ordinary node packet is immediately followed by a data limb which encode's the node's value.

By default, the arguments of an operator node packet are again MP Trees. However, when all arguments of an operator have a homogeneous syntactic format, it is possible to minimize the overhead incurred by the node packet headers of the arguments. An array of floating point numbers is a good example, but the data could be more structured - an array of complex or rational numbers, or a polynomial or generators of an ideal.

To enable such minimizations, we extend the valid syntax of MP Trees by providing special annotations and operators in the prototype dictionary (MP_ProtoDict) which define mechanisms for communicating the arguments of an operator node packet as data limbs.

To specify that the arguments of an operator node packet are data limbs (i.e., are not normal MP Trees), a prototype annotation must be used:

• The prototype annotation is defined in the prototype dictionary (as MP_AnnotProtoPrototype). The annotation must have the valuated and required flags set. For clarity and to distinguish the MP Tree for an expression from the MP Tree following a prototype annotation, we will refer to the latter as a prototype tree. Furthermore, the block of data described by a prototype tree is referred to as a prototyped data tree.

  More formally, the syntax of a prototype annotation packet is:
   
  <Prototype AP> ::= AP(MP_Prototype)<MP TypeSpec>
   
  where AP(x) is an Annotation Packet of type x.

• A prototype annotation may only be attached to an operator node packet.

• If a <Prototype AP> appears as an annotation to an operator node packet and the <MP TypeSpec> that follows denotes a valid prototype tree, then all of the operator's arguments are of the type specified in <MP TypeSpec>.
• A valid prototype tree may only consist of meta types, meta operators, and four designated operators defined in the prototype dictionary (see the next section for details), and otherwise satisfies the syntactic rules of an MP Tree.
• If an annotation is attached to a node in the prototype tree, it applies to every instance of the data in the prototyped data tree described by that node. This is a very cost effective mechanism for providing supplemental information about a potentially large block of data.

We make a distinction between prototype specification time, the time at which the prototype is transmitted, and data communication time, the time at which the data described by the prototype is transmitted.