Andrew Berlin and Daniel Weise, "Compiling Scientific Code Using Partial Evaluation", IEEE Computer, vol. 23, no. 12 (Dec. 1990), pp. 25-37.

Also see: H. Azaria and A. Dvir, ``An Optimizing Compiler for an SPAP Architecture Using AI Tools'', IEEE Computer, vol. 25, no. 6 (June 1992), pp. 39-48.

Dilemma: We would like to be able to write abstract programs in a form that is expressive and elegant, but we need optimized programs that are efficient.

[Rule of thumb: an interpreter typically causes an order-of-magnitude decrease in speed compared to compiled code. Compilation increases the degree of binding between a program specification and the things that will be constant when it runs.]

Partial evaluation can convert a high-level program into a specialized lower-level one. They call languages such as Fortran "mid-level".

Scientific programs are mostly data-independent: much of the computation is straight-line, without branches based on data values. Partial evaluation is especially effective for such programs.

Ways in which partial evaluation provides savings:

• Loop unrolling. [Their technique of following a trace of program execution is more general.]
  • Eliminates code for index variable, incrementing, testing, branching.
  • Makes address calculations constant.
  • Exposes common subexpressions.
• Elimination of many conditional branches.
  • Basic blocks become large. (May break some compilers!)
  • Exposes instruction-level parallelism.
  • Improves parallel or pipelined execution (they were able to use 40 processors with high utilization).
• Unpacks data structures into scalars inside a routine. (cf. common subexpression elimination).
• Optimization: dead-code elimination, constant folding, sign targeting, arithmetic simplification.
• Simplification involving special constants such as 0 and 1: this saved 50% of operations.

Partial evaluation works best when the structure of the system stays constant and only the state changes.

Expansion of large loops at compile time can make the program grow too large.

``The most exciting aspect of this work is the ability of partial evaluation to make abstractly specified programs execute efficiently.''

Partial evaluation allows library routines to be specialized to match the application, rather than vice-versa.