Accession Number : ADA326084
Title : A Simplifier for Untyped Lambda Expressions,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Galbiati, Louis ; Talcott, Carolyn
PDF Url : ADA326084
Report Date : OCT 1990
Pagination or Media Count : 28
Abstract : Many applicative programming languages are based on the call-by-value lambda calculus. 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.
Descriptors : *PROGRAMMING LANGUAGES, ALGORITHMS, OPTIMIZATION, COMPILERS, SYNTAX, CONTROL SEQUENCES, STRUCTURED PROGRAMMING, AUTOMATIC PROGRAMMING.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE