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.