A list-machine benchmark for mechanized metatheory

by Andrew W. Appel and Xavier Leroy.
INRIA Research Report RR-5914, May 2006.

Abstract: We propose a benchmark to compare theorem-proving systems on their ability to express proofs of compiler correctness. In contrast to the first POPLmark, we emphasize the connection of proofs to compiler implementations, and we point out that much can be done without binders or alpha-conversion. We propose specific criteria for evaluating the utility of mechanized metatheory systems; we have constructed solutions in both Coq and Twelf metatheory, and we draw conclusions about those two systems in particular.

List-machine exercise

We provide Coq and Twelf solutions to the benchmark with most proofs and some supporting lemmas removed. They can be used as an exercise in learning Coq or Twelf.
Last modified: Thu May 18 16:19:42 CEST 2006