PARTIAL-EVALUATION TECHNIQUES FOR CONCURRENT PROGRAMS

This paper presents an application of partial evaluation (program spec ialization) techniques to concurrent programs. The language chosen for this investigation is a very simple CSP-like language. A standard bin ding-time analysis for imperative languages is extended in order to de al with the basic concurrent constructs (synchronous communication and nondeterministic choice). Based on the binding-time annotations, a sp ecialization transformation is defined and proved correct. In order to maintain a simple and clear presentation, the specialization algorith m addresses only the data transfer component of the communication; par tial evaluation, the way it is defined here, always generates residual synchronizations. However, a simple approximate analysis for detectin g and removing redundant synchronizations from the residual program (i .e. synchronizations whose removal does not increase the nondeterminis m of a program) can be performed. The paper also addresses pragmatic c oncerns such as improving the binding-time analysis, controlling loop unrolling and the consequences of lifting nondeterminism from run-time to specialization-time. Finally, the power of the newly developed tec hnique is shown in several examples.