Simplifier for Untyped Lambda Expressions

摘要

Many applicative programming languages are based on the call-by-value lambdacalculus. For these languages tools such as compilers, partial evaluations, and other transformation systems often make use of rewriting systems that incorporate some form of beta reduction. For purposes of automatic rewriting it is important to develop extensions of beta-value reduction and to develop methods for guaranteeing termination. This paper describes an extension of beta-value reduction and a method based on abstract interpretation for controlling rewriting to guarantee termination. The main innovations are (1) the use of rearrangement rules in combination with beta-value reduction to increase the power of the rewriting system and (2) the definition of a non-standard interpretation of expressions, the 'generates' relation, as a basis for designing terminating strategies for rewriting. (Copyright (c) 1990 by Louis Galbiati and Carolyn Talcott.)