Future work

In order to generalise the existing approach the following problems will need to be considered.

1.

Extend data structures. The approach so far has been based on specific examples. In order to be of wider value, a more general framework needs to be used.

(a)

Work with the group fields and graph types frameworks to extend dataflow analysis to these ideas. These methods will need some modification, since the graph types system does allow structures with runtime dependencies, and the group approach is possibly too general to allow accurate analysis.

(b)

Extend existing approach to a collection of properties, e.g commuting, inverse, parent, etc ... , allowing them to be combined to produce more general families of structures.

2.

Extend program model. One of the main restrictions placed on the expressiveness of the functions is the lack of general predicates on the recursive calls. There are three methods worth considering.

(a)

Follow `fuzzy' approach. If we do not want to restrict the form of such predicates, or allow them to be runtime dependant, we need to follow the ideas in [4] and [1]. The approach would then be to do the best possible with no knowledge of which predicates are evaluated as true. This means to locate the set of all potential sources, and prune away the earlier ones whose execution implies the execution of a later potential source.

(b)

Follow group fields technique, define a subset of the potentially infinite structure that the program operates on. This is similar to ideas in [8], where a `formating language' specifies the structure of allowable path names. The format used is similar to the numbered occurrence languages used by [5]. This approach obviously restricts the expressiveness of the program, but allows for more accuracy in the solutions.

(c)

Use recursive constructs as in [3] to build up a the structure first. The functions then only operate over the existing values. This is similar to the previous approach, but can allow for more complex sub-sets of the structure to be selected.

To summarise, there are many existing approaches to extending the description and manipulation of data structures. Not all of these are geared towards the kind of compile-time analysis that is required to parallelise sequentially written code. The ASAP techniques do address this problem but aim primarily for alias information rather than dataflow analysis. The difference between these is that alias information will discover that two statements access the same item of data, when in fact there may be no true dependence, since the value is overwritten between them. The dataflow approach has the advantage that potentially more independence can be found when the full dataflow of the code is known. The disadvantage is of course that the analysis is much harder, and impossible if insufficient information is available. Inspired by the analysis that can be achieved when `static' structures such as arrays are manipulated, my research will aim to find a more general class of structures for which this quality of analysis is possible. The disadvantage of this is that in many problems the data structures do depend on some run time information. To be more widely applicable my solution will aim to compliment these other methods.