A self-applicable partial evaluator for the lambda calculus

Abstract

A description is given of theoretical and a few practical aspects of an implemented self-applicable partial evaluator for the call by value untyped lambda calculus with constants, conditionals, and a fixed point operator. A partial evaluator that is both high-order and self-applicable is also described. A solution to the problem of binding time analysis is presented. The partial evaluator is simple, completely automatic, and implemented in a side-effect free subset of Scheme. It has been used to compile, to generate compilers, and to generate a compiler generator.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>