Distributed Partial Evaluation

Partial evaluation is an automatic program transformation that optimizes programs by specialization. We speed up the specialization process by utilizing the natural coarse-grained parallelism inherent in the partial evaluation process. We have supplemented an existing partial evaluation system for the Scheme programming language by a farm-of-workers model for parallel partial evaluation in a network of loosely coupled workstations. Our implementation speeds up specialization by a factor of 2--3 on 6 processors. Keywords functional programming, automatic program transformation, partial evaluation 1 Introduction Partial evaluation is a powerful program-specialization technique based on constant propagation. Given the static (known) parameters of a source program, partial evaluation constructs a residual program---an optimized, specialized version of the program, which on application to the remaining dynamic parameters produces the same result as the original program applied to all pa..