The full-reducing Krivine abstract machine KN simulates pure normal-order reduction i...
summary
An improved full‑reducing Krivine machine KN is shown to perform the exact same beta reductions, in the same order, as pure normal‑order reduction: a lockstep simulation witnessed by a substitution function that flattens closures. The proof builds a bespoke closure calculus with de Bruijn indices and de Bruijn levels, closure abstractions and administrative expansion rules, and uses structural induction plus properties called index alignment, parameters‑as‑levels and balanced derivations to get a one‑to‑one match of non‑administrative steps.
AI-written summary · about
chapters (5)
related talks
18mA Simple and Efficient Implementation of Strong Call by Need by an Abstract Ma…
40mAn Introduction to Combinator Compilers and Graph Reduction Machines
55mInequalities and Reductions for Nonzero Kronecker Coefficients
15mClosing Remarks
48mA History of Subtyping
15mProducts of Recursive Programs for Hypersafety Verification
13mTowards Compiling Higher-Order Programs to Bayesian Networks
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back