IMPLEMENTING PARALLEL REWRITING

Rewriting is a computation paradigm that allows to implement directly an equational specification (eg. an abstract data type). Much work has been done about theoretical aspects of rewriting, which has made this technique of practical interest for programming. The next step is now to provide an efficient implementation. We present in this paper an implementation technique of rewriting on any loosely-coupled parallel architectures. Restricted to one processor, its efficiency is in the same order of magnitude as those of functional languages such as interpreted LISP or ML, and we expect an almost linear increase of the efficiency when increasing the number of processors. This approach allows parallel execution of programs directly from their equationally axiomatized specification, without having at all to explicit the potential parallelism, thus providing a simple and precise operational semantics.