Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Incremental Reduction in the Lambda Calculus
Authors: Field, John H.
Teitelbaum, Tim
Keywords: computer science
technical report
Issue Date: May-1990
Publisher: Cornell University
Abstract: An incremental algorithm is one that takes advantage of the fact that the function it computes is to be evaluated repeatedly on inputs that differ only slightly from one another, avoiding duplication of common computations. We define here a new notion of incrementality for reduction in the untyped $\lambda$-calculus and describe an incremental reduction algorithm, $\Lambda^{inc}$. We show that $\Lambda^{inc}$ has the desirable property of performing non-overlapping reductions on related terms, yet is simple enough to allow a practical implementation. The algorithm is based on a novel $\lambda$-reduction strategy that may prove useful in a non-incremental setting as well. Incremental $\lambda$-reduction can be used to advantage in any setting where an algorithm is specified in a functional or applicative manner.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1130.pdf2.57 MBAdobe PDFView/Open
90-1130.ps585.44 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us