Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6970
 Title: Incremental Reduction in the Lambda Calculus Authors: Field, John H.Teitelbaum, Tim Keywords: computer sciencetechnical report Issue Date: May-1990 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1130 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. URI: http://hdl.handle.net/1813/6970 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat