Developping parallel programs based on rewriting techniques

Starting with a formal problem specification, we show how to progressively achieve a parallel distributed solution, using convenient transformations of specifications. In order to achieve a solution, we use rewriting techniques applied in the context of transformations. This paper explains the methodology, points out its advantages and its requests. We first, introduce the specification language CO-OPN used to express both abstract specification and implementation. CO-OPN is a structured version of algebraic specification and Petri nets in which adequate notions of equivalence can be formalized to handle the concept of correct transformations. Then we introduce the general technique of applying transformations to get specifications progressively closer to the implementation level. These transformations are classified into two levels, the high level transformation performing abstract modification of algorithm and the low level transformations which are applicable on the specification closer to the implementation. Finally, a concrete example will show how the simple "permutation sort" can be transformed quite automatically in a distributed implementation of a "quick sort" algorithm.