In this chapter, we set aside the problem involving functions with commutative recursive calls, and consider the problem of implementing a set of library functions that allow a user to produce code that will manipulate a recursive structure on a parallel machine, such as the Cray T3D. We first turn to the problem of how to describe the structure of such data types.
In languages that allow pointer based data structures, such as C, Pascal or ML, there is a considerable amount of freedom over what structures can be defined and manipulated. Since the aim to provide a library of routines rather than a compiled language, there will have to be some restrictions on the kind of structures that can be created using my system. Also, the node naming method requires that all processors have complete knowledge about the layout of the whole structure from the outset. This negates the possibility of allowing nodes to be connected arbitrarily. So we will consider only the kind of structures where this complete knowledge applies. This will primarily consist of data types such as trees and lists, although it will be possible to use bi-directional links and nested structures. Finally, the idea of commutative directions will allow the structures arising from the evaluation of recursive functions to be handled, plus irregularly shaped `diamond DAG' structures.