Tags:Coq, Lambda calculus and Reduction strategies
Abstract:
We present a generic framework for the specification and reasoning about reduction strategies in the lambda calculus representable as sets of term decompositions. It is provided as a Coq formalization that features a novel format of phased strategies. It facilitates concise description and algebraic reasoning about properties of reduction strategies. The formalization accommodates many well-known strategies, both weak and strong, such as call by name, call by value, head reduction, normal order, full β-reduction, etc. We illustrate the use of the framework as a tool to inspect and categorize the “zoo” of existing strategies, as well as to discover and study new ones with particular properties.
The Zoo of Lambda-Calculus Reduction Strategies, and Coq