Evaluating Call-By-Need on the Control Stack

2010/09/16 by Stephen Chang, David Van Horn, Chang, Stephen +3
Computer Science · #Advanced Database Systems and Queries #D.3.1 #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Programming Languages (cs.PL) #cs.PL

paper · pdf · doi:10.48550/arxiv.1009.3174

Symposium on Trends in Functional Programming (TFP 2010), Norman, Oklahoma, May 2010

arxiv created 2010/09/16 · openalex publication_date 2010/09/16 · arxiv updated 2010/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Ariola and Felleisen's call-by-need λ-calculus replaces a variable occurrence with its value at the last possible moment. To support this gradual notion of substitution, function applications-once established-are never discharged. In this paper we show how to translate this notion of reduction into an abstract machine that resolves variable references via the control stack. In particular, the machine uses the static address of a variable occurrence to extract its current value from the dynamic control stack.

Related

• Reduction Strategies in the Lambda Calculus and Their Implementation through Derivable Abstract Machines: Introduction
• The Call-by-need Lambda Calculus, Revisited
• An Abstract Machine for Strong Call by Value
• Small-step and big-step semantics for call-by-need
• Crumbling Abstract Machines