Development of MPT was mainly motivated by the following problem: While the flexibility to represent an object in a variety of formats eases the implementation of an application's ``Put'' interface (the sender can choose to ``Put'' the data in the format which is closest to its internal representation) and is one of the main sources for achieving high efficiency, it complicates the implementation of a receiving application's ``Get'' routines: Instead of having to ``understand'' just one, well-defined representation of an object, a receiver needs to be able to understand the same object in a variety of representations. For example, an integer matrix might be received as a prototyped sparse or dense matrix, or as an ordinary (unprototyped) sparse or dense matrix in an expression tree format. Realizing that it is a cumbersome requirement that every MP interface needs to understand every possible representation of every relevant object, the MPT library provides routines which allow an application to have to understand only one representation of an object. The current MPT library might be considered as a generalization of the MPP library described in [#!sg:BSG1!#]: the data representation used and the prototype mechanisms provided are more general (i.e., not polynomial specific), and a greater variety of tree manipulating routines are provided (see below).
The main data structure MPT operates on is MPT_Tree - a memory representation of a MP tree. A MPT tree closely reflects the structure of the MP encoding: It consists of a MPT_Header and a MPT_Data. A MPT_Header is a pointer to a structure used for storing properties of a MP node header (type, dictionary tag, number of arguments annotations, etc.) and a MPT_Data is a (void *) pointer which is used for storing the respective node data (e.g., value of a number, arguments of an operator, characters of a string, etc.). The explicit separation of the header from the actual data stems from the fact that MPT uses a principle similar to MP for handling prototyped data: the same header structure is used for specifying the type (and, possibly structure) of more than one data item (i.e., prototyped data is stored as compactly as it is communicated).
The main routines provided by MPT are MPT_GetTree(), which reads a MP tree from a MP link and transforms it into a MPT_Tree, and various primitive routines for manipulating MPT_Trees (such as transforming all prototyped data into fully type-specified data, or initializing, copying, deleting, and comparing MPT_Tree's). Additionally, collections of various subject-specific transformations of dictionary-defined objects are provided as add-on libraries (such as the MPP library, which provides transformations between the different polynomial representations [#!sg:BSG1!#], or the MPM library which provides matrix manipulations).
In its most straightforward form, MPT can be used as shown in the top row of arrows of Figure 7. Instead of reading in the data directly from a MP link into its internal representation, an application uses MPT to first read the data into a MPT_Tree, which is subsequently manipulated using the appropriate library or external manipulation routines (e.g., all polynomials are transformed into a sparse recursive representation), and finally transformed from a MPT_Tree into the application's internal representation. This is the easiest approach to implement a MP ``Get'' interface: Not only can one rely on the various manipulation routines for MPT trees to transform a MPT_Tree object into a unique representation, but also the transformation from a MPT_Tree into an application's internal representation is greatly facilitated by the ability to repeatedly walk through the tree in an arbitrary order (which is largely impossible, if we were to read the data directly from a MP link).
However, for objects which could be read directly from the link into an application's internal representation (i.e., objects whose format is nearly identical to the application's ``native'' format), the intermediately generated MPT_Tree representation implies an unnecessary loss of efficiency. To avoid this inefficiency without losing the convenience of the straightforward approach, we use the following solution: After MPT_GetTree() has read the header of a node (including reading all attached annotations), but before reading the actual data packet, the routine MPT_GetApplData() is called with the node header as an argument. MPT_GetApplData() is a pointer to a function which is to be redefined by each application. The intended functionality is as follows: An application checks the type and/or structure of the object as specified by the node header. If the object is in a format which is close to the application's ``native'' format, then the data is read in directly, bypassing MPT_GetTree's data read routines and stored as encapsulated opaque data within a MPT_Tree. Otherwise, the data is read in by the ``normal'' MPT_GetTree routines and subsequently manipulated and transformed as outlined above.
Unfortunately, this optimization approach introduces a duplication of development effort since we need to have two nearly identical set of routines which transform ``native'' objects into the application's internal representation: One set which accomplishes that from MP link data and another set which accomplishes the same from MPT_Tree data. To overcome this duplication, we take advantage of MP's abstract device interface (ADI) [#!mp-disco96!#], and define a new MP transport device - a MP internal memory device - and can consequently bind this internal memory device to a new type of MP link: an internal memory link. The ADI operations are implemented based on the MPT_Tree data structures and on the routines of the MPT library such that writing/reading a MPT_Tree to/from a internal memory MP link merely amounts to pointer assignments. Consequently, instead of having to implement a second set of routines which transform native objects from a MPT_Tree representation, we ``Put'' (``associate'' might be a better verb here) the MPT_Tree to an internal MP memory link, and then can use the same set of ``Get'' routines which read MP link data directly into an applications internal representation (see also the ``back loop'' of Figure 7).
We wish to point out that, based on the MPT library, one is able to implement an MP ``Get'' interface which is nearly optimal w.r.t. efficiency (it can basically be as efficient as specialized ``canned'' ``Get'' routines) and simplicity/convenience (as an API programmer, one basically needs to implement one set of Get routines and can let the MPT library routines do the rest). In other words, MPT is our answer to the generality versus efficiency problem on the programming level.
