1. Introduction

Briefly, a prototype is a syntax tree providing type and structuring information about a composite data object. This report expands and explains in detail the definition and use of prototypes within the Multi Protocol (MP). Readers are referred to [1,3] for a general description of MP and to [2] for a more general overview of the ideas and philosophy behind MP prototypes.

An important requirement that drives many of the design decisions discussed here is that an MP Tree should always be parsable at the syntactic level. This means that a receiver may have no understanding of the dictionaries (i.e., semantics) involved, but should still be able to parse, manipulate, and echo the MP Tree (that is, process the tree at the syntactic level).

An implication of this decision is that MP does not support purely static definitions of composite data objects in a dictionary. By contrast, this is exactly the approach taken by XDR [4] in which an object is statically defined in a file and an object-specific filter routine is responsible for encoding it on the sending side. In this scenario, only data is transmitted and no type or structuring information is supplied; rather, this information is hardcoded into the filter. The sender assumes the receiver knows the type of data arriving and has a corresponding object-specific filter which can decode the incoming data.

In MP, on the other hand, a composite object must be transmitted either as an MP Tree using only node packets or using a prototype to describe the structure and content of the object, with the (usually headerless) "pure" data from the object following the prototype. The use of prototypes does not preclude the possibility of writing efficient routines for sending and receiving mathematical objects. Instead of decoding each datum by interpreting the prototype, a receiver can simply check the entire prototype to ensure that the incoming data meets the expectations of a compiled read routine. The sending side is simpler: An object-specific routine may efficiently marshall the user's data structure, including sending the prototype describing the object.

There are several competing goals in specifying the syntax and semantics of prototypes:

1.

Efficiency - This is the motivation for including protoypes within MP; to overcome the cost of communicating full node packets when the data has a homogeneous format. In addition to reducing the amount of data transmitted, this approach also allows the use of efficient compiled routines for encoding and decoding the data.

2.

Flexibility - A prototype must be able to represent a wide variety of data structures, including arrays, lists, structures (records), pointers (and recursive structures using pointers), and should do so in a way that naturally reflects the organization of the data structure.

3.

Simplicity - The concept of prototypes must be simple, as must the process of creating prototypes. The interpretation of a prototype must be unambiguous. Relatedly, the design of prototypes must not greatly complicate the implemenation of the protocol-application interface.

Section 2 briefly reviews the general syntax rules governing data communicated by MP and motivates the need for prototypes. The formal definition of prototypes is given in section 3. A number of examples are also given to make the definitions more concrete and to further illustrate the advantages of this approach. A short discussion of the use of tree specifications with respect to prototypes is given in section 3.3.

Notice that we do not define in this report how particular mathematical objects such as polynomials or matrices should be represented. This is done in the dictionaries covering the mathematical areas where these objects occur. We furthermore do not define in this report formal mechanisms for mapping syntactic data structures to MP encodings. This is done in the report describing the MP Data Definition Language (DDL) []. Instead, what we describe here are the means which MP provides to develop efficient and compact encodings of these objects.