An Algebra for Higher-Order Terms

Title:	An Algebra for Higher-Order Terms
Author:	Lars Hupel
Contributor:	Yu Zhang
Submission date:	2019-01-15
Abstract:	In this formalization, I introduce a higher-order term algebra, generalizing the notions of free variables, matching, and substitution. The need arose from the work on a verified compiler from Isabelle to CakeML. Terms can be thought of as consisting of a generic (free variables, constants, application) and a specific part. As example applications, this entry provides instantiations for de-Bruijn terms, terms with named variables, and Blanchette’s λ-free higher-order terms. Furthermore, I implement translation functions between de-Bruijn terms and named terms and prove their correctness.
BibTeX:	@article{Higher_Order_Terms-AFP, author = {Lars Hupel}, title = {An Algebra for Higher-Order Terms}, journal = {Archive of Formal Proofs}, month = jan, year = 2019, note = {\url{http://isa-afp.org/entries/Higher_Order_Terms.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	BSD License
Depends on:	Datatype_Order_Generator, Lambda_Free_RPOs, List-Index
Used by:	CakeML_Codegen
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.