4 MP high level data integrations - Prototypes

In MP, a datum is usually communicated as a node packet and composite data as an expression tree. While this approach works well for objects having an heterogeneous and tree-like syntactic structure, it is unnecessarily inefficient for objects which have a more homogenous format (like vectors, matrices, polynomials, etc.). For such objects, we would like to get away from an expression tree representation and support representations which more naturally (and efficiently) reflect the object's internal representation and which avoid the overhead incurred by having to communicate a node packet header for each datum. In addition to the obvious advantage that there would be less data to transmit and to buffer inside an application's interface, parsing is simpler and more efficient, for now blocks of homogeneous data (without headers) can be moved between the interface and the application's internal data structure using efficient memory move operations.

However, communicating headerless data requires establishing mechanisms which ensure that the data can still be correctly parsed. Within the context of MP we considered the following approaches:

1.

In addition to statically defining the semantics of an operator in a dictionary, we give the static definition of an operator's syntax. Figure 2 gives an example. It assumes that we explicitly defined in the Matrix dictionary that the SpIntMat operator is followed by 3*#Arg+2 headerless integer arguments, where the first two integers encode the dimensions and the remaining data are triples encoding the non-zero entries of the matrix.

2.

A MP-defined ``type description'' (i.e., prototype) dictionary specifies constructs (i.e., operators, annotations, etc.) and rules used to dynamically describe the structure of homogenous data. MP and user-defined dictionaries are free to specify the ``expected'' syntax of operators identifying structured objects using these mechanisms. The corresponding prototypes (i.e., type descriptions), however, are always sent with the object at transmission time, so interfaces that know the dictionary may use very efficient routines to parse the objects, and interfaces that do not know the dictionary may still (at least) parse the object. It is in this sense, that we can consider prototyped objects as ``self-describing''.

Approach (1) has the advantage of being most efficient (the amount of type information sent is minimal), but has the disadvantage that the task of parsing requires built-in knowledge of the definitions in a referenced dictionary. Clearly, this approach is inappropriate for a general protocol. Consequently, we decided to pursue (2). As we will show, a careful design of the grammar for the self-describing encoding of headerless data results in mechanisms which are almost as compact as (1) and have the additional advantage that the communicated data can always be syntactically manipulated (e.g., stored, displayed, duplicated, etc.). In other words, the realization of approach (2) is our solution to the efficiency versus generality problem on this syntactic level.