Program Logics for Homogeneous Meta-Programming

A meta-program is a program that generates or manipulates another program; in homogeneous meta-programming, a program may generate new parts of, or manipulate, itself. Meta-programming has been used extensively since macros were introduced to Lisp, yet the authors have little idea how formally to reason about meta-programs. They show the applicability of their approach by reasoning about example meta-programs from the literature. They also demonstrate that their logics are relatively complete in the sense of Cook, enable the inductive derivation of characteristic formulae, and exactly capture the observational properties induced by the operational semantics.