|
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.
|
|