A partial evaluator, and its use as a programming tool

摘要

Programs which perform partial evaluation, beta-expansion, and certain optimizations on programs, are studied with respect to implementation and application. Two implementations are described, one “interpretive” partial evaluator, which operates directly on the program to be partially evaluated, and a “compiling” system, where the program to be partially evaluated is used to generate a specialized program, which in its turn is executed to do the partial evaluation. Three applications with different requirements on these programs are described. Proofs are given for the equivalence of the use of the interpretive system and the compiling system in two of the three cases. The general use of the partial evaluator as a tool for the programmer in conjunction with certain programming techniques is discussed.