Verification of Meta-interpreters

A novel approach to the verification of meta-interpreters is introduced. We apply a general purpose verification method for logic programs, proposed by the authors, to the case study of the Vanilla and other logic meta-interpreters. We extend the standard notion of declarative correctness, and design a criterion for proving correctness of meta-interpreters in a general sense, including amalgamated and reflective meta-interpreters. The contribution of this paper can be summarized as follows: under certain natural assumptions, all interesting verification properties lift up from the object program to the meta-program, including partial correctness, termination, absence of errors, call patterns persistence, correct instances of queries, computed instances of queries. Interestingly, it is possible to establish these results on the basis of purely declarative reasoning, using the mentioned proof method. We believe that the obtained results illustrate the broad applicability of the adopted verification principles.