Transforming Interpreters into Inverse Interpreters by Partial Evaluation

摘要

The experiments in this paper apply the idea of prototyping programming language tools from robust semntics: we used a partial evaluator (Similix) to turn interpreters into inverse interpreters. This way we generated inverse interpreters for several small languages including interpreters for Turing machines, an applied lambda calculus, a flowchart language, and a suset of Java bytecode. Limiting factors of offline partial evaluation were the polyvariant specialization scheme with its lack of generalization; advantages were the availability of higher-order values to specialize a breadth-first tree traversal. This application of self-applicable partial evaluation is different from the classical Futamura projections that tell us how to translate a program by specialization of an interpreter.