I have extended the node-naming strategy to allow relations between the directions to be included, so that the redundancy in certain recursive functions could be exploited. This required a full path name to be stored for each node, and an algorithm for normalising such a path name was found and proved correct. In order to implement such a scheme, a mapping function from node names to processors was required. A simple static mapping system was used, which can be thought of as first pass allocation system, which would ideally be improved at run-time with a dynamic allocation scheme. The system was analysed so that for a given recursive function and number of processors, a specific amount of the redundancy could be exploited to provide an efficient implementation in parallel. This was backed up by experiments performed on the Cray T3D.
The extension of the mapping scheme also allowed for a class of recursively defined data types to be automatically named, from a simple description supplied by the user. This meant that the node naming scheme could be used without the user explicitly supplying the relevant naming functions. This was used to create a set of library functions that allow a user to manipulate nested recursive structures such as trees and trees of lists in parallel, without explicitly using parallel constructs.