Mechanizing Matching Logic in Coq

Matching logic is a formalism for specifying and reasoning about structures using patterns and pattern matching. Growing in popularity, matching logic has been used to define many logical systems such as separation logic with recursive definitions and linear-temporal logic. Despite this, there is no way for a user to define his or her own matching logic theories using a theorem prover, with maximal assurance of the properties being proved. Hence, in this work, we formalized a version of matching logic using the Coq proof assistant. Specifically, we create a new version of matching logic that uses a locally nameless representation, where quantified variables are unnamed in order to aid verification. We formalize the syntax, semantics, and proof system of this representation of matching logic using the Coq proof assistant. Crucially, we also verify the soundness of the formalized proof system, thereby guaranteeing that any matching logic properties proved in our Coq formalization are indeed correct. We believe this work provides a previously unexplored avenue for defining and proving matching logic theories and properties.