Accession Number:

ADA326084

Title:

A Simplifier for Untyped Lambda Expressions,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Galbiati, Louis
• Talcott, Carolyn

Report Date:

1990-10-01

Pagination or Media Count:

28.0

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