About the efficient reduction of lambda terms

2017/01/16 by Asperti, Andrea
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1701.04240

Abstract

There is still a lot of confusion about "optimal" sharing in the lambda calculus, and its actual efficiency. In this article, we shall try to clarify some of these issues.

Related

• Sharing Equality is Linear
• Reduction Strategies in the Lambda Calculus and Their Implementation through Derivable Abstract Machines: Introduction
• Positive Sharing and Abstract Machines
• A recursive normalizing one-step reduction strategy for the distributive lambda calculus
• Two Decreasing Measures for Simply Typed Lambda-Terms (Extended Version)