A call-by-need lambda calculus

Citations Over TimeTop 1% of 1995 papers

Abstract

The mismatch between the operational semantics of the lambda calculus and the actual behavior of implementations is a major obstacle for compiler writers. They cannot explain the behavior of their evaluator in terms of source level syntax, and they cannot easily compare distinct implementations of different lazy strategies. In this paper we derive an equational characterization of call-by-need and prove it correct with respect to the original lambda calculus. The theory is a strictly smaller theory than the lambda calculus. Immediate applications of the theory concern the correctness proofs of a number of implementation strategies, e.g., the call-by-need continuation passing transformation and the realization of sharing via assignments.

Related Papers

• → The vectorial λ-calculus(2017)25 cited
• → A typed, algebraic, computational lambda-calculus(2013)4 cited
• Simply Easy! An Implementation of a Dependently Typed Lambda Calculus(2007)