3.2.3 Recursive type specifications

To realize recursion in its most general form, we would need mechanisms to attach a ``label'' to any node in a prototype tree so that we could refer to it by name from other points in the prototype tree. While being very powerful, this approach makes parsing of MP data considerably more complicated. It would require a receiver to watch for ``labeled'' prototype nodes and to dynamically maintain a name space of ``labels'' and their associated prototype nodes. Since the data objects we have considered in practice do not require such a general mechanism to express their recursive structure, we currently support only a restricted (static) form of recursion. Instead of attaching a ``label'' (name) to any node in a prototype tree, we only allow ``static labeling'' of structures and union prototype operators and provide common meta type values to refer back to the previosuly designated targets of a recursive union or structure specification.

More precisely, if a Cmt:Proto:RecStruct (resp. Cmt:Proto:RecUnion) common meta type node packet appears in a prototype tree, then the corresponding data (transmitted at data communication time) is of the type as specified by the Cop:Proto:RecStruct (resp. Cop:Proto:RecUnion) common operator packet which, under lexical scope within the same prototype tree, preceded the recursive meta type node packet. By ``lexical scope within the same prototype tree'' we mean that a recursive meta type node packet must have been preceded by a corresponding recursive prototype operator packet within the same prototype tree, and that the ``back reference'' is made to the one which is most closely nested under under lexical scoping rules. So, a Cmt:Proto::RecStruct points back to the most closely nested Cop:Proto::RecStruct, and similarly for RecUnion.

Using recursive metatype node packets and recursive prototype operator node packets we obtain sufficiently powerful means to realize recursive type specification for most cases without having to introduce a dynamic name space for node labels and prototype nodes.

The simple example of a linked-list below illustrates the concepts (also see figure 8).

struct recurse_ex {
  MP_Sint32             a; 
  MP_Real32             b;
  struct recurse_ex *   recurse_ptr;  // self-referencing pointer
}

  

Figure 8: Recursive structure

The prototype on lines 1 - 7 describes a recursive data structure. The Cop:Proto::RecStruct operator on line 2 indicates each argument of the top-level Cop:Proto:Array operator is a structure of three elements and designates this structure for further recursive references (i.e., gives it a ``static'' recursion label to the structure). The third field of this structure on line 5 is a meta operator node packet (used as a pointer), whose prototype on lines 6 - 7 specifies that this is a recursive pointer ``pointing to'' the most closely nested MP_RecStruct within the prototype tree, which is on line 2. Note that the pointer's number-of-arguments field is 0 and that omitting lines 5 and 6 would result in an incorrect ``endless recursive'' type specification. The prototyped data tree immediately follows the prototype tree (line 8 on). The first occurrence of the recursive pointer field appears on line 9. Here the actual number-of-arguments of the Cmop:Proto::Pointer is found. Since it is 1 (non-NULL), another instance of this structure follows (lines 10 - 12). The recursive pointer field of this second structure is shown on line 12. Here the value is 0 indicating that the pointer is NULL. Since this is a recursive data structure, we have reached the end of the ``linked list'' and no more data follows.

Also see section 3.4 for a more complex examples illustrating the use of recursive type specifications.