Linearization via Rewriting (Long Version)
By: Ugo Dal Lago, Federico Olimpieri
Potential Business Impact:
Makes computer math proofs simpler and faster.
We introduce the structural resource lambda-calculus, a new formalism in which strongly normalizing terms of the lambda-calculus can naturally be represented, and at the same time any type derivation can be internally rewritten to its linearization. The calculus is shown to be normalizing and confluent. Noticeably, every strongly normalizable lambda-term can be represented by a type derivation. This is the first example of a system where the linearization process takes place internally, while remaining purely finitary and rewrite-based.
Similar Papers
Formalizing Representation Theorems for a Logical Framework with Rewriting
Logic in Computer Science
Makes computer code translations easier to check.
A Modular Lean 4 Framework for Confluence and Strong Normalization of Lambda Calculi with Products and Sums
Logic in Computer Science
Proves math rules for computer programs perfectly.
Lazy Linearity for a Core Functional Language
Programming Languages
Makes computer programs use resources correctly.