A compiled implementation of strong reduction
Authors:
Open Access
- 17 September 2002
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 37 (9) , 235-246
Abstract
Motivated by applications to proof assistants based on dependent types, we develop and prove correct a strong reducer and ß-equivalence checker for the λ-calculus with products, sums, and guarded fixpoints. Our approach is based on compilation to the bytecode of an abstract machine performing weak reductions on non-closed terms, derived with minimal modifications from the ZAM machine used in the Objective Caml bytecode interpreter, and complemented by a recursive "read back" procedure. An implementation in the Coq proof assistant demonstrates important speed-ups compared with the original interpreter-based implementation of strong reduction in Coq.Keywords
This publication has 12 references indexed in Scilit:
- A notation for lambda terms a generalization of environmentsTheoretical Computer Science, 1998
- Functional runtime systems within the lambda-sigma calculusJournal of Functional Programming, 1998
- Type-directed partial evaluation1996
- A framework for defining logicsJournal of the ACM, 1993
- Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machineJournal of Functional Programming, 1992
- Computer Science Logic1991
- An abstract machine for Lambda-terms normalization1990
- The calculus of constructionsInformation and Computation, 1988
- The categorical abstract machineScience of Computer Programming, 1987
- Every planar map is four colorable. Part I: DischargingIllinois Journal of Mathematics, 1977